Number Theory

Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint

Abstract

We address the problem of polynomial time factoring RSA moduli N ₁ = p ₁ q ₁ with the help of an oracle. As opposed to other approaches that require an oracle that explicitly outputs bits of p ₁, we use an oracle that gives only implicit information about p ₁. Namely, our oracle outputs a different N ₂ = p ₂ q ₂ such that p ₁ and p ₂ share the t least significant bits. Surprisingly, this implicit information is already sufficient to efficiently factor N ₁, N ₂ provided that t is large enough. We then generalize this approach to more than one oracle query.

Alexander May, Maike Ritzenhofen

The Security of All Bits Using List Decoding

Abstract

The relation between list decoding and hard-core predicates has provided a clean and easy methodology to prove the hardness of certain predicates. So far this methodology has only been used to prove that the O(loglogN) least and most significant bits of any function with multiplicative access —which include the most common number theoretic trapdoor permutations— are secure. In this paper we show that the method applies to all bits of any function defined on a cyclic group of order N with multiplicative access for cryptographically interesting N. As a result, in this paper we reprove the security of all bits of RSA, the discrete logarithm in a group of prime order or the Paillier encryption scheme.

Paz Morillo, Carla Ràfols

A New Lattice Construction for Partial Key Exposure Attack for RSA

Abstract

In this paper we present a new lattice construction for a lattice based partial key exposure attack for the RSA cryptography. We consider the situation that the RSA secret key d is small and a sufficient amount of the LSBs (least significant bits) of d are known by the attacker. We show that our lattice construction is theoretically more efficient than known attacks proposed in [2,7].

Yoshinori Aono

Subset-Restricted Random Walks for Pollard rho Method on ${\mathbf{F}_{p^m}}$

Abstract

In this paper, we propose a variant of the Pollard rho method. We use an iterating function whose image size is much smaller than its domain and hence reaches a collision faster than the original iterating function. We also explicitly show how this general method can be applied to multiplicative subgroups of finite fields with large extension degree.

The construction for finite fields uses a distinctive feature of the normal basis representation, namely, that the p-th power of an element is just the cyclic shift of its normal basis representation, when the underlying field is of characteristic p. This makes our method appropriate for hardware implementations. On multiplicative subgroups of ${\mathbf{F}_{p^m}}$, our method shows time complexity advantage over the original Pollard rho method by a factor of approximately $\frac{3p-3}{4p-3}\sqrt{m}$.

Through the MOV reduction, our method can be applied to pairing-based cryptosystems over binary or ternary fields. Hence our algorithm suggests that the order of subgroups, on which the pairing-based cryptosystems rely, needs to be increased by a factor of approximately m.

Minkyu Kim, Jung Hee Cheon, Jin Hong

Applications and Protocols

Signing a Linear Subspace: Signature Schemes for Network Coding

Abstract

Network coding offers increased throughput and improved robustness to random faults in completely decentralized networks. In contrast to traditional routing schemes, however, network coding requires intermediate nodes to modify data packets en route; for this reason, standard signature schemes are inapplicable and it is a challenge to provide resilience to tampering by malicious nodes.

We propose two signature schemes that can be used in conjunction with network coding to prevent malicious modification of data. Our schemes can be viewed as signing linear subspaces in the sense that a signature σ on a subspace V authenticates exactly those vectors in V. Our first scheme is (suitably) homomorphic and has constant public-key size and per-packet overhead. Our second scheme does not rely on random oracles and is based on weaker assumptions.

We also prove a lower bound on the length of signatures for linear subspaces showing that our schemes are essentially optimal in this regard.

Dan Boneh, David Freeman, Jonathan Katz, Brent Waters

Improving the Boneh-Franklin Traitor Tracing Scheme

Abstract

Traitor tracing schemes are cryptographically secure broadcast methods that allow identification of conspirators: if a pirate key is generated by k traitors out of a static set of ℓ legitimate users, then all traitors can be identified given the pirate key. In this paper we address three practicality and security issues of the Boneh-Franklin traitor-tracing scheme. In the first place, without changing the original scheme, we modify its tracing procedure in the non-black-box model such that it allows identification of k traitors in time $\tilde{O}(k^2)$, as opposed to the original tracing complexity $\tilde{O}(\ell)$. This new tracing procedure works independently of the nature of the Reed-Solomon code used to watermark private keys. As a consequence, in applications with billions of users it takes just a few minutes on a common desktop computer to identify large collusions. Secondly, we exhibit the lack of practical value of list-decoding algorithms to identify more than k traitors. Finally, we show that 2k traitors can derive the keys of all legitimate users and we propose a fix to this security issue.

Pascal Junod, Alexandre Karlov, Arjen K. Lenstra

Modeling Key Compromise Impersonation Attacks on Group Key Exchange Protocols

Abstract

A key exchange protocol allows a set of parties to agree upon a secret session key over a public network. Two-party key exchange (2PKE) protocols have been rigorously analyzed under various models considering different adversarial actions. However, the analysis of group key exchange (GKE) protocols has not been as extensive as that of 2PKE protocols. Particularly, the security attribute of key compromise impersonation (KCI) resilience has so far been ignored for the case of GKE protocols. We first model the security of GKE protocols addressing KCI attacks by both outsider and insider adversaries. We then show that a few existing protocols are not secure even against outsider KCI attacks. The attacks on these protocols demonstrate the necessity of considering KCI resilience. Finally, we give a new proof of security for an existing GKE protocol under the revised model assuming random oracles.

M. Choudary Gorantla, Colin Boyd, Juan Manuel González Nieto

Zero-Knowledge Proofs with Witness Elimination

Abstract

Zero-knowledge proofs with witness elimination are protocols that enable a prover to demonstrate knowledge of a witness to the verifier that accepts the interaction provided that the witness is valid for a given statement and additionally the witness does not belong to a set of eliminated witnesses. This set is determined by a public relation Q (that parameterizes the primitive) and the private input of the verifier. Zero-knowledge proofs with witness elimination thus call for a relaxation of the zero-knowledge property and are relevant in settings where a statement has a multitude of witnesses that may attest to its validity. A number of interesting issues arise in the design of such protocols that include whether a protocol transcript enables the verifier to test for witness after termination (something akin to an “offline dictionary attack”) and whether the prover should be capable of understanding whether her witness is eliminated. The primitive is motivated by the setting of identification schemes where a user wishes to authenticate herself to an access point while preserving her anonymity and the access point needs to certify that the user is eligible while at the same time making sure she does not match the identity of a suspect user that is tracked by the authorities. We call such primitives anonymous identification schemes with suspect tracking.

In this work we formalize zero-knowledge proofs with witness elimination in the universal composability setting and we provide a general construction based on smooth projective hashing that is suitable for designing efficient schemes. As an illustration of our general construction we then present an explicit efficient scheme for proving knowledge of a Boneh-Boyen signature with witness elimination. Our scheme requires the design of a smooth projective hash function for the language of linear ElGamal ciphertexts. Along the way we demonstrate how zero-knowledge proofs with witness elimination naturally relate to the primitives of password-based key exchange and private equality testing.

Aggelos Kiayias, Hong-Sheng Zhou

Multi-Party Protocols

Distributed Public-Key Cryptography from Weak Secrets

Abstract

We introduce the notion of distributed password-based public-key cryptography, where a virtual high-entropy private key is implicitly defined as a concatenation of low-entropy passwords held in separate locations. The users can jointly perform private-key operations by exchanging messages over an arbitrary channel, based on their respective passwords, without ever sharing their passwords or reconstituting the key.

Focusing on the case of ElGamal encryption as an example, we start by formally defining ideal functionalities for distributed public-key generation and virtual private-key computation in the UC model. We then construct efficient protocols that securely realize them in either the RO model (for efficiency) or the CRS model (for elegance).

We conclude by showing that our distributed protocols generalize to a broad class of “discrete-log”-based public-key cryptosystems, which notably includes identity-based encryption. This opens the door to a powerful extension of IBE with a virtual PKG made of a group of people, each one memorizing a small portion of the master key.

Michel Abdalla, Xavier Boyen, Céline Chevalier, David Pointcheval

Asynchronous Multiparty Computation: Theory and Implementation

Abstract

We propose an asynchronous protocol for general multiparty computation. The protocol has perfect security and communication complexity $\mathcal{O}(n^2|C|k)$, where n is the number of parties, |C| is the size of the arithmetic circuit being computed, and k is the size of elements in the underlying field. The protocol guarantees termination if the adversary allows a preprocessing phase to terminate, in which no information is released. The communication complexity of this protocol is the same as that of a passively secure solution up to a constant factor. It is secure against an adaptive and active adversary corrupting less than n/3 players. We also present a software framework for implementation of asynchronous protocols called VIFF (Virtual Ideal Functionality Framework), which allows automatic parallelization of primitive operations such as secure multiplications, without having to resort to complicated multithreading. Benchmarking of a VIFF implementation of our protocol confirms that it is applicable to practical non-trivial secure computations.

Ivan Damgård, Martin Geisler, Mikkel Krøigaard, Jesper Buus Nielsen

Multi-Party Computation with Omnipresent Adversary

Abstract

Secure multi-party computation (MPC) protocols enable a set of n mutually distrusting participants P ₁, ..., P _n, each with their own private input x _i, to compute a function Y = F(x ₁, ..., x _n), such that at the end of the protocol, all participants learn the correct value of Y, while secrecy of the private inputs is maintained. Classical results in the unconditionally secure MPC indicate that in the presence of an active adversary, every function can be computed if and only if the number of corrupted participants, t _a, is smaller than n/3. Relaxing the requirement of perfect secrecy and utilizing broadcast channels, one can improve this bound to t _a < n/2.

All existing MPC protocols assume that uncorrupted participants are truly honest, i.e., they are not even curious in learning other participant secret inputs. Based on this assumption, some MPC protocols are designed in such a way that after elimination of all misbehaving participants, the remaining ones learn all information in the system. This is not consistent with maintaining privacy of the participant inputs. Furthermore, an improvement of the classical results given by Fitzi, Hirt, and Maurer indicates that in addition to t _a actively corrupted participants, the adversary may simultaneously corrupt some participants passively. This is in contrast to the assumption that participants who are not corrupted by an active adversary are truly honest.

This paper examines the privacy of MPC protocols, and introduces the notion of an omnipresent adversary, which cannot be eliminated from the protocol. The omnipresent adversary can be either a passive, an active or a mixed one. We assume that up to a minority of participants who are not corrupted by an active adversary can be corrupted passively, with the restriction that at any time, the number of corrupted participants does not exceed a predetermined threshold. We will also show that the existence of a t-resilient protocol for a group of n participants, implies the existence of a t’-private protocol for a group of n′ participants. That is, the elimination of misbehaving participants from a t-resilient protocol leads to the decomposition of the protocol.

Our adversary model stipulates that a MPC protocol never operates with a set of truly honest participants (which is a more realistic scenario). Therefore, privacy of all participants who properly follow the protocol will be maintained. We present a novel disqualification protocol to avoid a loss of privacy of participants who properly follow the protocol.

Hossein Ghodosi, Josef Pieprzyk

Identity-Based Encryption

Blind and Anonymous Identity-Based Encryption and Authorised Private Searches on Public Key Encrypted Data

Abstract

Searchable encryption schemes provide an important mechanism to cryptographically protect data while keeping it available to be searched and accessed. In a common approach for their construction, the encrypting entity chooses one or several keywords that describe the content of each encrypted record of data. To perform a search, a user obtains a trapdoor for a keyword of her interest and uses this trapdoor to find all the data described by this keyword.

We present a searchable encryption scheme that allows users to privately search by keywords on encrypted data in a public key setting and decrypt the search results. To this end, we define and implement two primitives: public key encryption with oblivious keyword search (PEOKS) and committed blind anonymous identity-based encryption (IBE). PEOKS is an extension of public key encryption with keyword search (PEKS) in which users can obtain trapdoors from the secret key holder without revealing the keywords. Furthermore, we define committed blind trapdoor extraction, which facilitates the definition of authorisation policies to describe which trapdoor a particular user can request. We construct a PEOKS scheme by using our other primitive, which we believe to be the first blind and anonymous IBE scheme.

We apply our PEOKS scheme to build a public key encrypted database that permits authorised private searches, i.e., neither the keywords nor the search results are revealed.

Jan Camenisch, Markulf Kohlweiss, Alfredo Rial, Caroline Sheedy

Anonymous Hierarchical Identity-Based Encryption with Constant Size Ciphertexts

Abstract

We propose an anonymous Hierarchical Identity-Based Encryption (anonymous HIBE) scheme that has constant size ciphertexts. This means the size of the ciphertext does not depend on the depth of the hierarchy. Moreover, our scheme achieves the lowest computational cost because during the decryption phase the computational cost of decryption is constant. The security can be proven under reasonable assumptions without using random oracles because it is based on the composite order bilinear group. Our scheme achieves selective-ID security notion.

Jae Hong Seo, Tetsutaro Kobayashi, Miyako Ohkubo, Koutarou Suzuki

Towards Black-Box Accountable Authority IBE with Short Ciphertexts and Private Keys

Abstract

At Crypto’07, Goyal introduced the concept of Accountable Authority Identity-Based Encryption as a convenient tool to reduce the amount of trust in authorities in Identity-Based Encryption. In this model, if the Private Key Generator (PKG) maliciously re-distributes users’ decryption keys, it runs the risk of being caught and prosecuted. Goyal proposed two constructions: the first one is efficient but can only trace well-formed decryption keys to their source; the second one allows tracing obfuscated decryption boxes in a model (called weak black-box model) where cheating authorities have no decryption oracle. The latter scheme is unfortunately far less efficient in terms of decryption cost and ciphertext size. In this work, we propose a new construction that combines the efficiency of Goyal’s first proposal with a very simple weak black-box tracing mechanism. Our scheme is described in the selective-ID model but readily extends to meet all security properties in the adaptive-ID sense, which is not known to be true for prior black-box schemes.

Benoît Libert, Damien Vergnaud

Removing Escrow from Identity-Based Encryption

New Security Notions and Key Management Techniques

Abstract

Key escrow is inherent in identity-based encryption (IBE). A curious key generation center (KGC) can simply generate the user’s private key to decrypt a ciphertext. However, can a KGC still decrypt if it does not know the intended recipient of the ciphertext? We answer by formalizing KGC anonymous ciphertext indistinguishability ($\mathcal{ACI-KGC}$).

We find that all existing pairing-based IBE schemes without random oracles, whether receipt-anonymous or not, do not achieve KGC one-wayness, a weaker notion of $\mathcal{ACI-KGC}$. In view of this, we first show how to equip an IBE scheme by Gentry with $\mathcal{ACI-KGC}$. Second, we propose a new system architecture with an anonymous private key generation protocol such that the KGC can issue a private key to an authenticated user without knowing the list of users identities. This also better matches the practice that authentication should be done with the local registration authorities instead of the KGC. Our proposal can be viewed as mitigating the key escrow problem in a different dimension than distributed KGCs approach.

Sherman S. M. Chow

Signatures

On the Theory and Practice of Personal Digital Signatures

Abstract

We take a step towards a more realistic modeling of personal digital signatures, where a human user, his mobile equipment, his PC and a server are all considered as independent players in the protocol, and where only the human user is assumed incorruptible. We then propose a protocol for issuing digital signatures on behalf of the user. This protocol is proactively UC-secure assuming at most one player is corrupted in every operational phase. In more practical terms, this means that one can securely sign using terminals (PC’s) that are not necessarily trusted, as long as the mobile unit and the PC are not both corrupted at the same time. In other words, our solution cannot be broken by phising or key-logging via the PC. The protocol allows for mobile units with very small computing power by securely outsourcing computation to the PC and also allows usage of any PC that can communicate properly. Finally, we report on the results of a prototype implementation of our solution.

Ivan Damgård, Gert Læssøe Mikkelsen

Security of Blind Signatures under Aborts

Abstract

We explore the security of blind signatures under aborts where the user or the signer may stop the interactive signature issue protocol prematurely. Several works on blind signatures discuss security only in regard of completed executions and usually do not impose strong security requirements in case of aborts. One of the exceptions is the paper of Camenisch, Neven and shelat (Eurocrypt 2007) where the notion of selective-failure blindness has been introduced. Roughly speaking, selective-failure blindness says that blindness should also hold in case the signer is able to learn that some executions have aborted.

Here we augment the work of Camenisch et al. by showing how to turn every secure blind signature scheme into a selective-failure blind signature scheme. Our transformation only requires an additional computation of a commitment and therefore adds only a negligible overhead. We also study the case of multiple executions and notions of selective-failure blindness in this setting. We then discuss the case of user aborts and unforgeability under such aborts. We show that every three-move blind signature scheme remains unforgeable under such user aborts. Together with our transformation for selective-failure blindness we thus obtain an easy solution to ensure security under aborts of either party and which is applicable for example to the schemes of Pointcheval and Stern (Journal of Cryptology, 2000).

We finally revisit the construction of Camenisch et al. for simulatable adaptive oblivious transfer protocols, starting from selective-failure blind signatures where each message only has one valid signature (uniqueness). While our transformation to achieve selective-failure blindness does not preserve uniqueness, it can still be combined with a modified version of their protocol. Hence, we can derive such oblivious transfer protocols based on unique blind signature schemes only (in the random oracle model), without necessarily requiring selective-failure blindness from scratch.

Marc Fischlin, Dominique Schröder

Security of Sanitizable Signatures Revisited

Abstract

Sanitizable signature schemes, as defined by Ateniese et al. (ESORICS 2005), allow a signer to partly delegate signing rights to another party, called the sanitizer. That is, the sanitizer is able to modify a predetermined part of the original message such that the integrity and authenticity of the unchanged part is still verifiable. Ateniese et al. identify five security requirements for such schemes (unforgeability, immutability, privacy, transparency and accountability) but do not provide formal specifications for these properties. They also present a scheme that is supposed to satisfy these requirements.

Here we revisit the security requirements for sanitizable signatures and, for the first time, present a comprehensive formal treatment. Besides a full characterization of the requirements we also investigate the relationship of the properties, showing for example that unforgeability follows from accountability. We then provide a full security proof for a modification of the original scheme according to our model.

Christina Brzuska, Marc Fischlin, Tobias Freudenreich, Anja Lehmann, Marcus Page, Jakob Schelbert, Dominique Schröder, Florian Volk

Identification of Multiple Invalid Signatures in Pairing-Based Batched Signatures

Abstract

This paper describes new methods in pairing-based signature schemes for identifying the invalid digital signatures in a batch, after batch verification has failed. These methods efficiently identify non-trivial numbers of invalid signatures in batches of (potentially large) numbers of signatures.

Our methods use “divide-and-conquer” search to identify the invalid signatures within a batch, but prune the search tree to substantially reduce the number of pairing computations required. The methods presented in this paper require computing on average O(w) products of pairings to identify w invalid signatures within a batch of size N, compared with the O(w (log₂(N/w) + 1)) [for w < N/2] that traditional divide-and-conquer methods require. Our methods avoid the problem of exponential growth in expected computational cost that affect earlier proposals which, on average, require computing O(w) products of pairings.

We compare the expected performance of our batch verification methods with previously published divide-and-conquer and exponential cost methods for Cha-Cheon identity-based signatures [6]. However, our methods also apply to a number of short signature schemes and as well as to other identity-based signature schemes.

Brian J. Matt

Encryption

CCA-Secure Proxy Re-encryption without Pairings

Abstract

In a proxy re-encryption scheme, a semi-trusted proxy can transform a ciphertext under Alice’s public key into another ciphertext that Bob can decrypt. However, the proxy cannot access the plaintext. Due to its transformation property, proxy re-encryption can be used in many applications, such as encrypted email forwarding. In this paper, by using signature of knowledge and Fijisaki-Okamoto conversion, we propose a proxy re-encryption scheme without pairings, in which the proxy can only transform the ciphertext in one direction. The proposal is secure against chosen ciphertext attack (CCA) and collusion attack in the random oracle model based on Decisional Diffie-Hellman (DDH) assumption over $\mathbb{Z}_{N^2}^*$ and integer factorization assumption, respectively. To the best of our knowledge, it is the first unidirectional PRE scheme with CCA security and collusion-resistance.

Jun Shao, Zhenfu Cao

Compact CCA-Secure Encryption for Messages of Arbitrary Length

Abstract

This paper proposes a chosen-ciphertext secure variant of the ElGamal public-key encryption scheme which generates very compact ciphertexts for messages of arbitrary length. The ciphertext overhead (i.e., the difference between ciphertext and plaintext) is one group element only. Such a property is particularly useful when encrypting short messages such as a PIN or a credit card number in bandwidth-critical environments. On top of the compact overhead, the computational cost for encryption and decryption are almost the same as plain ElGamal encryption. The security is proven based on the strong Diffie-Hellman assumption in the random oracle model.

Masayuki Abe, Eike Kiltz, Tatsuaki Okamoto

Verifiable Rotation of Homomorphic Encryptions

Abstract

Similar to verifiable shuffling (mixing), we consider the problem of verifiable rotating a given list of homomorphic encryptions. The offset by which the list is rotated (cyclic shift) should remain hidden. Basically, we will present zero-knowledge proofs of knowledge of a rotation offset and re-encryption exponents, which define how the input list is transformed into the output list. We also briefly address various applications of verifiable rotation, ranging from ‘fragile mixing’ as introduced by Reiter and Wang at CCS’04 to applications in protocols for secure multiparty computation and voting.

We present two new, efficient protocols. Our first protocol is quite elegant and involves the use of the Discrete Fourier Transform (as well as the Fast Fourier Transform algorithm), and works under some reasonable conditions. We believe that this is the first time that Fourier Transforms are used to construct an efficient zero-knowledge proof of knowledge.

Our second protocol is more general (requiring no further conditions) and only slightly less efficient than the DFT-based protocol. Unlike the previously best protocol by Reiter and Wang, however, which relies on extensive use of verifiable shuffling as a building block (invoking it four times as a sub-protocol), our construction is direct and its performance is comparable to the performance of a single run of the best protocol for verifiable shuffling.

Sebastiaan de Hoogh, Berry Schoenmakers, Boris Škorić, José Villegas

New Cryptosystems and Optimizations

A Practical Key Recovery Attack on Basic TCHo

Abstract

TCHo is a public key encryption scheme based on a stream cipher component, which is particular suitable for low cost devices like RFIDs. In its basic version, TCHo offers no IND-CCA2 security, but the authors suggest to use a generic hybrid construction to achieve this security level. The implementation of this method however, significantly increases the hardware complexity of TCHo and thus annihilates the advantage of being suitable for low cost devices. In this paper we show, that TCHo cannot be used without this construction. We present a chosen ciphertext attack on basic TCHo that recovers the secret key after approximately d ^3/2 decryptions, where d is the number of bits of the secret key polynomial. The entropy of the secret key is $\log_2\binom{d}{w}$, where w is the weight of the secret key polynomial, and w is usually small compared to d. In particular, we can break all of the parameters proposed for TCHo within hours on a standard PC.

Mathias Herrmann, Gregor Leander

An Algebraic Surface Cryptosystem

Abstract

We construct a public-key cryptosystem based on an NP-complete problem in algebraic geometry. It is a problem of finding sections on fibered algebraic surfaces; in other words, we use a solution to a system of multivariate equations of high degrees. Our cryptosystem is a revised version of the algebraic surface cryptosystem (ASC) we constructed earlier (cf. [AG04, AG06]). We revise its encryption algorithm to avoid known attacks. Further, we show that the key size of our cryptosystem is one of the shortest among those of post-quantum public-key cryptosystems known at present.

Koichiro Akiyama, Yasuhiro Goto, Hideyuki Miyake

Fast Multibase Methods and Other Several Optimizations for Elliptic Curve Scalar Multiplication

Abstract

Recently, the new Multibase Non-Adjacent Form (mbNAF) method was introduced and shown to speed up the execution of the scalar multiplication with an efficient use of multiple bases to represent the scalar. In this work, we first optimize the previous method using fractional windows, and then introduce further improvements to achieve additional cost reductions. Moreover, we present new improvements in the point operation formulae. Specifically, we reduce further the cost of composite operations such as quintupling and septupling of a point, which are relevant for the speed up of multibase methods in general. Remarkably, our tests show that, in the case of standard elliptic curves, the refined mbNAF method can be as efficient as Window-w NAF using an optimal fractional window size. Thus, this is the first published method that does not require precomputations to achieve comparable efficiency to the standard window-based NAF method using precomputations. On other highly efficient curves as Jacobi quartics and Edwards curves, our tests show that the refined mbNAF currently attains the highest performance for both scenarios using precomputations and those without precomputations.

Patrick Longa, Catherine Gebotys

Group Signatures and Anonymous Credentials

Revocable Group Signature Schemes with Constant Costs for Signing and Verifying

Abstract

Lots of revocable group signature schemes have been proposed so far. In one type of revocable schemes, signing and/or verifying algorithms have O(N) or O(R) complexity, where N is the group size and R is the number of revoked members. On the other hand, in Camenisch-Lysyanskaya scheme and the followers, signing and verifying algorithms have O(1) complexity. However, before signing, updates of the secret key are required. The complexity is O(R) in the worst case. In this paper, we propose a revocable scheme with signing and verifying of O(1) complexity, where no updates of secret key are required. The compensation is the long public key of O(N). In addition, we extend it to the scheme with $O(\sqrt{N})$-size public key, where signing and verifying have constant extra costs.

Toru Nakanishi, Hiroki Fujii, Yuta Hira, Nobuo Funabiki

An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials

Abstract

The success of electronic authentication systems, be it e-ID card systems or Internet authentication systems such as CardSpace, highly depends on the provided level of user-privacy. Thereby, an important requirement is an efficient means for revocation of the authentication credentials. In this paper we consider the problem of revocation for certificate-based privacy-protecting authentication systems. To date, the most efficient solutions for revocation for such systems are based on cryptographic accumulators. Here, an accumulate of all currently valid certificates is published regularly and each user holds a witness enabling her to prove the validity of her (anonymous) credential while retaining anonymity. Unfortunately, the users’ witnesses must be updated at least each time a credential is revoked. For the know solutions, these updates are computationally very expensive for users and/or certificate issuers which is very problematic as revocation is a frequent event as practice shows.

In this paper, we propose a new dynamic accumulator scheme based on bilinear maps and show how to apply it to the problem of revocation of anonymous credentials. In the resulting scheme, proving a credential’s validity and updating witnesses both come at (virtually) no cost for credential owners and verifiers. In particular, updating a witness requires the issuer to do only one multiplication per addition or revocation of a credential and can also be delegated to untrusted entities from which a user could just retrieve the updated witness. We believe that thereby we provide the first authentication system offering privacy protection suitable for implementation with electronic tokens such as eID cards or drivers’ licenses.

Jan Camenisch, Markulf Kohlweiss, Claudio Soriente

Controlling Access to an Oblivious Database Using Stateful Anonymous Credentials

Abstract

In this work, we consider the task of allowing a content provider to enforce complex access control policies on oblivious protocols conducted with anonymous users. As our primary application, we show how to construct privacy-preserving databases by combining oblivious transfer with an augmented anonymous credential system. This permits a database operator to restrict which items each user may access, without learning anything about users’ identities or item choices. This strong privacy guarantee holds even when users are assigned different access control policies and are allowed to adaptively make many queries. To do so, we show how to augment existing anonymous credential systems so that, in addition to certifying a user’s attributes, they also store state about the user’s database access history. Our construction supports a wide range of access control policies, including efficient and private realizations of the Brewer-Nash (Chinese Wall) and Bell-LaPadula (Multilevel Security) policies, which are used for financial and defense applications. In addition, our system is based on standard assumptions in the standard model and, after an initial setup phase, each transaction requires only constant time.

Scott Coull, Matthew Green, Susan Hohenberger

Erratum to: Public Key Cryptography – PKC 2009

Abstract

Erratum to: S. Jarecki and G. Tsudik (Eds.) Public Key Cryptography – PKC 2009 DOI: 10.1007/978-3-642-00468-1

The book was inadvertently published with an incorrect name of the copyright holder. The name of the copyright holder for this book is: © Springer-Verlag Berlin Heidelberg. The book has been updated with the changes.

Stanisław Jarecki, Gene Tsudik

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Number Theory

Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint

The Security of All Bits Using List Decoding

A New Lattice Construction for Partial Key Exposure Attack for RSA

Subset-Restricted Random Walks for Pollard rho Method on ${\mathbf{F}_{p^m}}$

Applications and Protocols

Signing a Linear Subspace: Signature Schemes for Network Coding

Improving the Boneh-Franklin Traitor Tracing Scheme

Modeling Key Compromise Impersonation Attacks on Group Key Exchange Protocols

Zero-Knowledge Proofs with Witness Elimination

Multi-Party Protocols

Distributed Public-Key Cryptography from Weak Secrets

Asynchronous Multiparty Computation: Theory and Implementation

Multi-Party Computation with Omnipresent Adversary

Identity-Based Encryption

Blind and Anonymous Identity-Based Encryption and Authorised Private Searches on Public Key Encrypted Data

Anonymous Hierarchical Identity-Based Encryption with Constant Size Ciphertexts

Towards Black-Box Accountable Authority IBE with Short Ciphertexts and Private Keys

Removing Escrow from Identity-Based Encryption

Signatures

On the Theory and Practice of Personal Digital Signatures

Security of Blind Signatures under Aborts

Security of Sanitizable Signatures Revisited

Identification of Multiple Invalid Signatures in Pairing-Based Batched Signatures

Encryption

CCA-Secure Proxy Re-encryption without Pairings

Compact CCA-Secure Encryption for Messages of Arbitrary Length

Verifiable Rotation of Homomorphic Encryptions

New Cryptosystems and Optimizations

A Practical Key Recovery Attack on Basic TCHo

An Algebraic Surface Cryptosystem

Fast Multibase Methods and Other Several Optimizations for Elliptic Curve Scalar Multiplication

Group Signatures and Anonymous Credentials

Revocable Group Signature Schemes with Constant Costs for Signing and Verifying

An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials

Controlling Access to an Oblivious Database Using Stateful Anonymous Credentials

Erratum to: Public Key Cryptography – PKC 2009

Backmatter