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 › peerreview
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 zeroknowledge 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 socalled generalized Schnorr proofs, gave rise to the construction of many efficient cryptographic protocols. Unfortunately, the noninteractive 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 noninteractive proof system (GSproofs) 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, GSproofs 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 GSproofs, in particular, primitives that are structurepreserving, meaning that their inputs, outputs, and public keys consist only of source group elements. Indeed, structurepreserving signatures, commitments, and encryption schemes have been proposed. Although deterministic primitives such as (verifiable) pseudorandom functions or verifiable unpredictable functions play an important role in the construction of many cryptographic protocols, no structurepreserving 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 structurepreserving 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 structurepreserving primitives to be algebraic is natural, in particular as otherwise it is not possible to prove with GSproofs that an algorithm has been run correctly. We further extend our negative result to pseudorandom functions and deterministic public key encryption as well as nonstrictly structurepreserving 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 2426, 2014 Proceedings 
Editors  Yehuda Lindell 
Place of Publication  Berlin Germany 
Publisher  Springer 
Pages  713738 
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/9783642542428 (Proceedings) 
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  8349 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
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 › peerreview