Paper 2022/141

Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs

Muhammed F. Esgin, Ron Steinfeld, Dongxi Liu, and Sushmita Ruj

Abstract

In this work, we study hybrid exact/relaxed zero-knowledge proofs from lattices, where the proved relation is exact in one part and relaxed in the other. Such proofs arise in important real-life applications such as those requiring verifiable PRF evaluation and have so far not received significant attention as a standalone problem. We first introduce a general framework, LANES+, for realizing such hybrid proofs efficiently by combining standard relaxed proofs of knowledge RPoK and the LANES framework (due to a series of works in Crypto'20, Asiacrypt'20, ACM CCS'20). The latter framework is a powerful lattice-based proof system that can prove exact linear and multiplicative relations. The advantage of LANES+ is its ability to realize hybrid proofs more efficiently by exploiting RPoK for the high-dimensional part of the secret witness while leaving a low-dimensional secret witness part for the exact proof that is proven at a significantly lower cost via LANES. We apply our LANES+ framework to construct substantially shorter proofs of rounding, which is a central tool for verifiable deterministic lattice-based cryptography. Based on our rounding proof, we then design an efficient long-term verifiable random function (VRF), named LaV. LaV leads to the shortest VRF outputs among the proposals of standard (i.e., long-term and stateless) VRFs based on quantum-safe assumptions. Of independent interest, we also present a general framework for the construction of efficient VRFs (in the random oracle model) and generalized results for challenge difference invertibility, a fundamental soundness security requirement for many proof systems.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
LatticeZero-Knowledge ProofPost-QuantumLearning with RoundingVerifiable Random Function
Contact author(s)
muhammed esgin @ monash edu
ron steinfeld @ monash edu
dongxi liu @ data61 csiro au
sushmita ruj @ unsw edu au
History
2022-02-09: received
Short URL
https://ia.cr/2022/141
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/141,
      author = {Muhammed F.  Esgin and Ron Steinfeld and Dongxi Liu and Sushmita Ruj},
      title = {Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/141},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/141}},
      url = {https://eprint.iacr.org/2022/141}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.