On the impossibility of structure-preserving deterministic primitives

Masayuki Abe, Jan Camenisch, Rafael Dowsley, Maria Dubovitskaya

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

5 Citations (Scopus)


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 languageEnglish
Title of host publicationTheory of Cryptography
Subtitle of host publication11th Theory of Cryptography Conference, TCC 2014 San Diego, CA, USA, February 24-26, 2014 Proceedings
EditorsYehuda Lindell
Place of PublicationBerlin Germany
Number of pages26
ISBN (Electronic)9783642542428
ISBN (Print)9783642542411
Publication statusPublished - 2014
Externally publishedYes
EventTheory of Cryptography Conference 2014 - San Diego, United States of America
Duration: 24 Feb 201426 Feb 2014
Conference number: 11th
https://link.springer.com/book/10.1007/978-3-642-54242-8 (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceTheory of Cryptography Conference 2014
Abbreviated titleTCC 2014
Country/TerritoryUnited States of America
CitySan Diego
Internet address


  • Groth-Sahai proofs
  • structure-preserving primitives
  • unique signatures
  • Verifiable random functions

Cite this