Paper 2022/1545

On Structure-Preserving Cryptography and Lattices

Dennis Hofheinz, ETH Zurich
Kristina Hostakova, ETH Zurich
Roman Langrehr, ETH Zurich
Bogdan Ursu, ETH Zurich

The Groth-Sahai proof system is a highly efficient pairing-based proof system for a specific class of group-based languages. Cryptographic primitives that are compatible with these languages (such that we can express, e.g., that a ciphertext contains a valid signature for a given message) are called "structure-preserving". The combination of structure-preserving primitives with Groth-Sahai proofs allows to prove complex statements that involve encryptions and signatures, and has proved useful in a variety of applications. However, so far, the concept of structure-preserving cryptography has been confined to the pairing setting. In this work, we propose the first framework for structure-preserving cryptography in the lattice setting. Concretely, we - define "structure-preserving sets" as an abstraction of (typically noisy) lattice-based languages, - formalize a notion of generalized structure-preserving encryption and signature schemes capturing a number of existing lattice-based encryption and signature schemes), - construct a compatible zero-knowledge argument system that allows to argue about lattice-based structure-preserving primitives, - offer a lattice-based construction of verifiably encrypted signatures in our framework. Along the way, we also discover a new and efficient strongly secure lattice-based signature scheme. This scheme combines Rückert's lattice-based signature scheme with the lattice delegation strategy of Agrawal et al., which yields more compact and efficient signatures. We hope that our framework provides a first step towards a modular and versatile treatment of cryptographic primitives in the lattice setting.

Available format(s)
Publication info
structure-preserving cryptography lattices verifiably-encrypted signatures zero-knowledge proofs
Contact author(s)
hofheinz @ inf ethz ch
kristina hostakova @ inf ethz ch
roman langrehr @ inf ethz ch
bogdan ursu @ inf ethz ch
2022-11-08: approved
2022-11-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dennis Hofheinz and Kristina Hostakova and Roman Langrehr and Bogdan Ursu},
      title = {On Structure-Preserving Cryptography and Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1545},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.