1970-01-01

(2026-01) Faster Short Pairing-Based NIZK Proofs for Ring LWE Ciphertexts

• [[Olivier Bernard]]
• [[Sarah Elkazdadi]]
• [[Benoit Libert]]
• [[Arthur Meyre]]
• [[Jean-Baptiste Orfila]]
• [[Nicolas Sarlin]]

2026-01-08

• #cryptography
• #paper

Abstract

Several works explored the use of discrete-logarithm-based zero-knowledge proof systems in order to prove the validity of Ring LWE ciphertexts and/or FHE ciphertexts. A technique suggested by del Pino {\it et al.} (PKC'19) notably enables proofs of $1$KB for the task of proving the validity of NewHope ciphertext using a variant of BulletProofs. A recent work of Libert (PKC'24) described a pairing-based adaptation of del Pino {\it et al.}'s approach with proofs of $3$ or $6$ group elements. While space-efficient, the latter solution is rather expensive in terms of proving time. In this work, we provide new NIZK arguments for the Ring-LWE-based public-key scheme proposed by Joye (CT-RSA'24), which is used in a variant of TFHE. The new schemes feature slightly longer proofs than in earlier pairing-based constructions with short proofs, but the prover is much faster. The number of exponentiations is reduced by a factor $\approx 7$ and the common reference string is compressed by a factor $\approx 9$ (and reduced to $1.5$MB for practically relevant parameters). We provide implementation results that confirm these estimations.