Paper 2022/1545

On Structure-Preserving Cryptography and Lattices

Dennis Hofheinz, ETH Zurich
Kristina Hostáková, ETH Zurich
Roman Langrehr, ETH Zurich
Bogdan Ursu, Consensys
Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in PKC 2024
Keywords
structure-preserving cryptographylatticesverifiably-encrypted signatureszero-knowledge proofs
Contact author(s)
hofheinz @ inf ethz ch
kristina hostakova @ inf ethz ch
roman langrehr @ inf ethz ch
bogdan ursu @ inf ethz ch
History
2024-01-22: revised
2022-11-07: received
See all versions
Short URL
https://ia.cr/2022/1545
License
Creative Commons Attribution
CC BY

BibTeX

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