Implementation of post-quantum zero-knowledge (ZK) proofs, and applications (public verifiability of fhevm, threshold verifiable random function (tVRF) and other use-cases)

[matth-rambaud]

• Library targeted: TFHE-rs, for applications to fhEVM

• Overview: Implementation of post-quantum zero-knowledge (ZK) proofs, and applications (public verifiability of fhevm, threshold verifiable random function (tVRF) and other use-cases)

• Complete and detailed description:
  We propose to implement zero-knowledge (ZK) proofs based on the hardness of lattice problems, hence, which are sound even if the prover uses a quantum computer.

—> Technically, for any public linear map L, we will implement a ZK proof of knowledge of a preimage by L, of small size, of any public y. Concretely: prove knowledge of a small secret x s.t. L(x)=y. ←-

To this end, we will use the state of the art framework called “LANES+” (Crypto’23 , Esgin et al https://eprint.iacr.org/2022/141 , following Lyubashevsky-Attema-Nguyen-Esgin-Seiler “Practical lattice-based zero-knowledge proofs for integer relations” CCS’20 ; “Practical exact proofs from lattices: New techniques to exploit fully-splitting ring” Asiacrypt’20 ; and “Practical product proofs for lattice commitments.” Crypto’20 ).

Although it looks simple, this ZK is essentially all what is needed for most use-cases:

(1) Proofs of knowledge of a plaintext, at least for the encryption schemes published by Zama ( Joye https://eprint.iacr.org/2021/1402.pdf and the thresholdized version https://eprint.iacr.org/2023/815.pdf ).
(2) Proofs that interactive threshold decryptions and interactive bootstrappings are correct.
(3) Non-Interactive secret shared randomness generation, a.k.a. “pseudorandom secret sharing” (PRSS), which is used in (2). How to do it efficiently is an innovation of ours which we plan to implement, please see below.

We now give more details on (1) (2) (3) and on our planned contributions and implementations.

—------------------------------------
(1) (i) The TGLWE schemes published by Zama enjoy encryption algorithms of which the ZK proofs of correct encryption boil down to knowledge of preimages (secret key, secret randomness) of a public linear map (determined by the public key and public ciphertext). Thus our proposed contribution seems enough for this use-case.

(ii) In addition, we will also develop and implement ZK proofs that encrypted inputs satisfy a public linear relation. This applies to a new use-case which we are developing (ongoing research details available on demand).

(iii) Finally, ZK proofs of linear relations are enough to prove equality of an encrypted input with the opening of a public lattice-based commitment. This is the starting point to apply any commit-and-prove ZK system, in order to prove complicated predicates on the secrets, such as with the “lattice-based Bulletproofs” of Crypto’21 ( https://eprint.iacr.org/2021/307 ). We did not plan to implement such ZK proof of equality, however we could make it an extension of our project upon request of Zama.

—------------------------------------
(2) At least for the threshold TGLWE scheme “Noah’s Ark “ published by Zama, evaluation of a decryption share is a mere linear map applied on the secret key + small secret-shared flooding noise, and with coefficients determined by the public ciphertext. The same threshold decryption technique is also used for the interactive bootstrapping method published by Loftus-Orsini-Patra-Smart-Choudhury at Asiacrypt’13. The only difference is that, instead of a small flooding noise, the intermediary outputs are hidden by a large secret shared mask. We will implement the essential ingredient, which is the non-interactive generation and verifiable opening of small secret-shared randomness: see (3) below. We do not plan to instantiate our ZK on the end-to-end use-cases (2). However upon request, we could make an extension of our project to address it with the precise parameters required by the fhevm.

—------------------------------------
(3) The method currently proposed by Zama https://eprint.iacr.org/2023/815.pdf Fig.12 to generate secret shared randomness is not practically verifiable, because it would require players proving correct evaluation of AES in zero-knowledge. We will rectify this and instead instantiate the required pseudorandom function (PRF) with the verifiable lattice-based PRF of Crypto’23 (Esgin et al https://eprint.iacr.org/2022/141 ). Precisely, we will implement a verifiable pseudorandom secret sharing (vPRSS) with output values of small sizes. Then, we will enrich it with the functionality required for (2), namely: verifiable opening, all-at-once, of the evaluation of a linear map applied to {small vPRSS outputs, together with other secret-shared values, e.g., decryption keys}.

• Estimate of the grant we would like to receive:
  % Reward: 7500E =
  3500E for 6 months base internship salary of Todd Cauet (Master 2 MIC Université de Paris),
  % + 4200E = 700E6 months bonus salary for Todd Cauet
  % + 1050 = 350E3months bonus salary (50% time) of Hippolyte Muziot (Sorbonne Université - ENS Rennes)
  % + 1500E of equipment
  % 0E for the supporting team dedicated to this project: Pierre-Alain Fouque + a research engineer (IRISA Rennes); Weiqiang Wen + Matthieu Rambaud (Télécom Paris) + Hippolyte Muziot
  % + 2500E for the visits in Rennes or Paris of the team members.

• Papers, articles, existing implementation…
  Related links and academic references are given inline in the description above.
  In addition, here are two implementations which could help us:
  [LNS20] the ZKs of Lyubashevsky-Seiler-NGuyen CCS’20 https://eprint.iacr.org/2020/1183.pdf : https://github.com/gregorseiler/irelzk
  the Go library “Lattigo” http://github.com/ldsec/lattigo. Developed by EPFL and used to evaluate their CCS’23 paper for verifiable threshold FHE, called “Pelta” https://eprint.iacr.org/2023/642.pdf .

[zama-bot]

Hello matth-rambaud,

Thank you for your Grant application! Our team will review and add comments in your issue! In the meantime:

1. Join the FHE.org discord server for any questions (pick the Zama library channel you will use).
2. Ask questions privately: [email protected].

[zaccherinij]

Hi there,

Thank you very much for your interest in what we do at Zama, and your proposition for a grant. For now, we will not follow up with your proposition. But we invite you to keep an eye on this repository as we will launch new bounties soon, if you're interested in playing with Zama libs.

Cheers,
JZ