On the Impossibility of Structure-Preserving Deterministic Primitives

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Masayuki Abe, NTT Secure Platform Laboratories, NTT Corporation
  • ,
  • Jan Camenisch, IBM Research - Zurich
  • ,
  • Rafael Dowsley
  • ,
  • Maria Dubovitskaya, IBM Research - Zurich

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
JournalJournal of Cryptology
Pages (from-to)239-264
Number of pages26
Publication statusPublished - 2019

    Research areas

  • Groth–Sahai proofs, Structure-preserving cryptography, Unique signatures, Verifiable random functions

See relations at Aarhus University Citationformats

ID: 164779715