On the impossibility of structure-preserving deterministic primitives

Masayuki Abe, Jan Camenisch, Rafael Dowsley, Maria Dubovitskaya

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)


In structure-preserving cryptography over bilinear groups, cryptographic schemes are restricted to exchange group elements only, and their correctness must be verifiable only by evaluating pairing product equations. Several primitives, such as structure-preserving 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 cryptographic protocols, no structure-preserving realizations of them are known. This is not coincident: 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, otherwise it would not be known how to verify correctness only by evaluating pairing product equations. 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
Pages (from-to)239-264
Number of pages26
JournalJournal of Cryptology
Issue number1
Publication statusPublished - 2019
Externally publishedYes


  • Groth–Sahai proofs
  • Structure-preserving cryptography
  • Unique signatures
  • Verifiable random functions
  • On the impossibility of structure-preserving deterministic primitives

    Abe, M., Camenisch, J., Dowsley, R. & Dubovitskaya, M., 2014, Theory of Cryptography : 11th Theory of Cryptography Conference, TCC 2014 San Diego, CA, USA, February 24-26, 2014 Proceedings. Lindell, Y. (ed.). Berlin Germany: Springer, p. 713-738 26 p. (Lecture Notes in Computer Science ; vol. 8349).

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

    Open Access
    5 Citations (Scopus)

Cite this