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


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
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
2022-02-09: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.