Research output per year
Research output per year
Masayuki Abe, Jan Camenisch, Rafael Dowsley, Maria Dubovitskaya
Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review
Complex cryptographic protocols are often constructed in a modular way from primitives such as signatures, commitments, and encryption schemes, verifiable random functions, etc. together with zero-knowledge proofs ensuring that these primitives are properly orchestrated by the protocol participants. Over the past decades a whole framework of discrete logarithm based primitives has evolved. This framework, together with so-called generalized Schnorr proofs, gave rise to the construction of many efficient cryptographic protocols. Unfortunately, the non-interactive versions of Schnorr proofs are secure only in the random oracle model, often resulting in protocols with unsatisfactory security guarantees. Groth and Sahai have provided an alternative non-interactive proof system (GS-proofs) that is secure in the standard model and allows for the "straight line" extraction of witnesses. Both these properties are very attractive, in particular if one wants to achieve composable security. However, GS-proofs require bilinear maps and, more severely, they are proofs of knowledge only for witnesses that are group elements. Thus, researchers have set out to construct efficient cryptographic primitives that are compatible with GS-proofs, in particular, primitives that are structure-preserving, meaning that their inputs, outputs, and public keys consist only of source group elements. Indeed, structure-preserving signatures, commitments, and encryption schemes have been proposed. Although deterministic primitives such as (verifiable) pseudo-random functions or verifiable unpredictable functions play an important role in the construction of many cryptographic protocols, no structure-preserving realizations of them are known so far. As it turns out, this is no coincidence: in this paper we show that it is impossible to construct algebraic structure-preserving deterministic primitives that provide provability, uniqueness, and unpredictability. This includes verifiable random functions, unique signatures, and verifiable unpredictable functions as special cases. The restriction of structure-preserving primitives to be algebraic is natural, in particular as otherwise it is not possible to prove with GS-proofs that an algorithm has been run correctly. We further extend our negative result to pseudorandom functions and deterministic public key encryption as well as non-strictly structure-preserving primitives, where target group elements are also allowed in their ranges and public keys.
Original language | English |
---|---|
Title of host publication | Theory of Cryptography |
Subtitle of host publication | 11th Theory of Cryptography Conference, TCC 2014 San Diego, CA, USA, February 24-26, 2014 Proceedings |
Editors | Yehuda Lindell |
Place of Publication | Berlin Germany |
Publisher | Springer |
Pages | 713-738 |
Number of pages | 26 |
ISBN (Electronic) | 9783642542428 |
ISBN (Print) | 9783642542411 |
DOIs | |
Publication status | Published - 2014 |
Externally published | Yes |
Event | Theory of Cryptography Conference 2014 - San Diego, United States of America Duration: 24 Feb 2014 → 26 Feb 2014 Conference number: 11th https://link.springer.com/book/10.1007/978-3-642-54242-8 (Proceedings) |
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 8349 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | Theory of Cryptography Conference 2014 |
---|---|
Abbreviated title | TCC 2014 |
Country/Territory | United States of America |
City | San Diego |
Period | 24/02/14 → 26/02/14 |
Internet address |
|
Research output: Contribution to journal › Article › Research › peer-review