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

Muhammed F. Esgin; Ron Steinfeld; Dongxi Liu; Sushmita Ruj

Paper 2022/141

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

Muhammed F. Esgin

, Monash University, CSIRO's Data61

Ron Steinfeld

, Monash University

Dongxi Liu

, CSIRO's Data61

Sushmita Ruj

, UNSW Sydney

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. Thanks to the flexibility of LANES+, other exact proof systems can also be supported. 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 generalized results for challenge difference invertibility, a fundamental soundness security requirement for many proof systems.

Note: Clarified some discussion about range proof (last paragraph of P.26 and last paragraph of P.32)

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in CRYPTO 2023
Keywords: Lattice Zero-Knowledge Proof Post-Quantum Learning with Rounding Verifiable Random Function
Contact author(s): muhammed esgin @ monash edu
ron steinfeld @ monash edu
dongxi liu @ data61 csiro au
sushmita ruj @ unsw edu au
History: 2023-09-01: last of 2 revisions; 2022-02-09: received; See all versions
Short URL: https://ia.cr/2022/141
License: 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},
      url = {https://eprint.iacr.org/2022/141}
}