Paper 2019/057
Short Discrete Log Proofs for FHE and RingLWE Ciphertexts
Rafael del Pino, Vadim Lyubashevsky, and Gregor Seiler
Abstract
In applications of fullyhomomorphic encryption (FHE) that involve computation on encryptions produced by several users, it is important that each user proves that her input is indeed wellformed. This may simply mean that the inputs are valid FHE ciphertexts or, more generally, that the plaintexts $m$ additionally satisfy $f(m)=1$ for some public function $f$. The most efficient FHE schemes are based on the hardness of the RingLWE problem and so a natural solution would be to use latticebased zeroknowledge proofs for proving properties about the ciphertext. Such methods, however, require largerthannecessary parameters and result in rather long proofs, especially when proving general relationships. In this paper, we show that one can get much shorter proofs (roughly $1.25$KB) by first creating a Pedersen commitment from the vector corresponding to the randomness and plaintext of the FHE ciphertext. To prove validity of the ciphertext, one can then prove that this commitment is indeed to the message and randomness and these values are in the correct range. Our protocol utilizes a connection between polynomial operations in the lattice scheme and inner product proofs for Pedersen commitments of Bünz et al. (S&P 2018). Furthermore, our proof of equality between the ciphertext and the commitment is very amenable to amortization  proving the equivalence of $k$ ciphertext / commitment pairs only requires an additive factor of $O(\log{k})$ extra space than for one such proof. For proving additional properties of the plaintext(s), one can then directly use the logarithmicspace proofs of Bootle et al. (Eurocrypt 2016) and Bünz et al. (IEEE S&P 2018) for proving arbitrary relations of discrete log commitment. Our technique is not restricted to FHE ciphertexts and can be applied to proving many other relations that arise in latticebased cryptography. For example, we can create very efficient verifiable encryption / decryption schemes with short proofs in which confidentiality is based on the hardness of RingLWE while the soundness is based on the discrete logarithm problem. While such proofs are not fully postquantum, they are adequate in scenarios where secrecy needs to be futureproofed, but one only needs to be convinced of the validity of the proof in the prequantum era. We furthermore show that our zeroknowledge protocol can be easily modified to have the property that breaking soundness implies solving discrete log in a short amount of time. Since building quantum computers capable of solving discrete logarithm in seconds requires overcoming many more fundamental challenges, such proofs may even remain valid in the postquantum era.
Metadata
 Available format(s)
 Publication info
 Published by the IACR in PKC 2019
 Keywords
 ZeroKnowledge ProofsBulletproofsFHEVerifiable EncryptionRingLWE Encryption
 Contact author(s)

Rafael Del Pino @ ens fr
vadim lyubash @ gmail com
gseiler @ inf ethz ch  History
 20190125: received
 Short URL
 https://ia.cr/2019/057
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/057, author = {Rafael del Pino and Vadim Lyubashevsky and Gregor Seiler}, title = {Short Discrete Log Proofs for {FHE} and Ring{LWE} Ciphertexts}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/057}, year = {2019}, url = {https://eprint.iacr.org/2019/057} }