Lattice and hashes: the state of the art for fully homomorphic encryption with zero-knowledge proofs.
The world of cryptography has made significant strides in the past few years, driven by the increasing need for privacy and scalability in blockchain applications. Two critical cryptographic tools that have gained significant research attention are Zero-Knowledge Proofs (ZKPs) and Fully Homomorphic Encryption (FHE). With FHE you can perform computations on encrypted data. However, there is no assurance that the performed computations on encrypted data was done correctly. This is where ZKP could be used. One could send encrypted data to a server in-the-cloud (or blockchain), and receive the resulting computation, still encrypted, with a proof attesting to the accuracy of the alterations done on that server; i.e. verifiable private computation.
That is great! Why is this not used everywhere?
There be dragons in the details! Read more to learn about the current state of the art of FHE with ZKP, the benefits of their convergence, and what it means for the future of private computation.
I am lost. What are ZKP and FHE?
To better appreciate the convergence of ZKP and FHE, it's essential to understand the fundamentals of both cryptographic tools.
Zero-Knowledge Proofs (ZKPs) are cryptographic protocols that allow a party (the prover) to demonstrate the validity of a statement without revealing any other information about the statement. This enables privacy-preserving data sharing and trustless computation.
Fully Homomorphic Encryption (FHE) is a form of encryption that allows computations to be performed directly on encrypted data without requiring decryption. The result, when decrypted, will be the same as if the computation had been performed on the original data. FHE offers robust security and privacy, enabling secure data processing and sharing.
Lattice meet hashes.
Can these two technologies be used together in a harmonious way? Using FHE with ZKPs is unfortunately non-trivial. Both toolsets have mathematical structures that when put together do not work well. FHE generally uses lattice based structures, while ZKP use elliptic curves and hashes. When proving lattice relationships you end up using polynomials with 1000s of coefficients. Large polynomials make prover times untenable for normal consumer facing applications.
The naïve reaction when faced with this fact is: why not use the same sort of maths? Indeed, there has been research done on lattice based ZKP systems. The state-of-the-art in these systems create large proofs, in a less efficient manner — when compared to elliptic curve based ZKP [1]. The most recent proposal for a lattice based ZKP [2] gives improvement gains for systems that use known lattice-based commitment schemes. The authors note that any further improvements would require a re-think in approach or 'improvements in fundamental lattice primitives'.
Are we stuck assuming that a server doing processing in FHE-schemes is non-malicious — trust, don't verify? Recent work on verifiable Fully Homomorphic Encryption [3] explores systems such as Rinocchio [4] that have native support for FHE friendly rings! ... It seems that even such a system has trouble efficiently representing state-of the-art FHE. Firstly the rings used in Rinocchio for FHE, only provide 60 bits of computational soundness. The authors need to fortify this with three additional rounds of soundness amplification. Finally, some computations such as relinearization are not supported as Rinocchio can only do arithmetic ring operations.
It seems that even a scheme that can handle the same math primitives results in very slow prover times. This puts its use out-of-reach for any application that requires timeliness. Lattice and ring based systems for verifiable FHE are interesting subjects for future research and improvements.
Is there a middle ground?
What if we had application specific ZKP with FHE? For example, only specific I/O needed to be verified to be correctly computed. This could be used in applications and blockchains, without the prohibitive costs of using a full verifiable FHE scheme. Sunscreen is one such startup building tooling for this. In their work on smartFHE [5], they propose a system that uses the 'Bulletproof' ZKP schemes with short discrete log proofs [6]. They prove the well-formedness of FHE ciphertexts and then use Bulletproofs [7] for proving users' private account balances and inputs.
In a private smart contract system, the user could provide a ZKP demonstrating certain features of their private inputs. These would be verified by miners who then update a public shared state. In many such systems ZKP are put on a pedestal and drive most of the process of privacy. In contrast to this a FHE-ZKP backed system would provide end-to-end privacy with support for light weight clients and private shared state. One could even go as far to say, that any non-trivial decentralized FHE based solution requires that the computations done remotely, provide a ZKP attesting to the accuracy of computations.
Application specific verifiable FHE (verifiable FHE 2.5) systems are likely to be dominant performers in the near term as they allow for optimizations on an ad-hoc basis. One can use ZKP when they are appropriate and only prove specific facts about FHE computations. One could even imagine systems that decrypt locally at specified intervals, and use a ZKP to process well-formedness and any computations done before re-encryption; this would allow an application to work around the expensive noise-growth seen with FHE in general.
Our folding based verifiable FHE scheme: Tatami-FHE
Above we wrote that polynomials with 1000s of coefficients are needed for proofs about lattice relationships. This is a fundamental bottleneck in proof size and prover time for verifiable FHE schemes. However, it turns out that you do not need the full power or machinery of a SNARK to make proofs for lattice based relationships.
We propose using a folding scheme based on Nova [8], which results in a proof about all of the work done with much better efficiency. Relaxed R1CS can be used as before to represent relationships, however since we are not using a SNARK until after the last step of recursion, the blowup in coefficients does not negatively contribute to total runtime as much as it would in a recursive system that runs a SNARK at each iteration.
The short discrete log proof system features a vector Pedersen commitment [6]. Nova requires that the commitment scheme used is additively homomorphic (i.e. Pedersen, or lattice based). With these facts we explore ways in which we can combine the two systems to create a practical verifiable FHE scheme.
A Ring-LWE based FHE cipher-text can be written as:
A~s = ~t (1)
A is the public key, ~t is the ciphertext, and ~s consists of the randomness and the message. All operations are performed over some polynomial ring Rq = Zq[X]/(f) for some integer q and a monic, irreducible polynomial f ∈ Z[X] of degree d.
The main result of previous work is an efficient protocol for proving knowledge of ~s with small coefficients in equation (1) [6]. They do this by creating a joint Pedersen commitment t = Com(~s) to all the coefficients in ~s. They then prove in zero-knowledge that these coefficients, when interpreted as a polynomial vector ~s, also satisfy (1). At the same time, the proof will show that the coefficients of ~s are valid Ring-LWE cipher-texts. I.e. they are within the required ranges. With multiple Ring-LWE cipher-texts ~t1, . . . ,~tk, the size of the proof is only an additive factor of O(log k) larger than the proof for one equation in (1).
With short discrete log proofs we can ensure Alice is giving valid BFV cipher-texts that has certain properties (is a positive value, is binary, etc), it does not prove whether the computations on the encrypted data was done in a correct manner by Bob. In intermediate systems a deterministic FHE circuit is used, and the work stops here for the FHE portion. Bulletproofs or other systems are used to make proofs about changes to values used in computation. By using the same blinding factor in both systems a verifier can check that a user has committed to the same values. This allows them to determine that in both proof systems the same inputs were used, at a cost of running two separate systems and proving lattice relations among them.
In Nova we have relaxed R1CS which takes the form:
AZ ◦ BZ = uCZ + E (2)
E is a vector that absorbs the cross terms that arise from the folding two relaxed R1Cs instance. u is scalar which absorbs an extra factor of r in the expanded form of equation (2). An additive homomorphic scheme is used because the cross terms E, would grow as folding is done in further iterations. E' = comm(E).
By using a folding scheme with relaxed R1CS we can combine the commitments used in the short discrete log proof scheme into E', while allowing the other lattice relationship constraints to remain as R1CS constraints. Rather than using two separate proof systems we use one folding scheme that hold both. The provers work will be dominated by two multiexponentiations of size O(|F|) in contrast to the full work of each Bulletproof or Rinocchio instance as computation progresses. In this way, we can then more efficiently prove that a cipher-text is not only valid, but lattice-based computations done with it are also valid.
We can leverage the same benchmarks used in previous work to test our idea [3]. CIRCOM implementations can be used from here [10], with a Nova backend found here [11] (future post on the results). We expect that repeated structures will have optimal results with our 'folding' based TatamiFHE scheme. We can further optimize with joint Pedersen commitments and their additively homomorphic property.
Future work
A folding scheme that removes the need for a universal circuit has been proposed with Supernova [9]. FHE circuits can be split into separate portions for each function required in computation. This would allow the amount of total constraints covered in the relaxed R1Cs instance to be reduced in an a'la carte fashion. It would also be possible to better parallelize tasks across machines.
Combining Zero-Knowledge Proofs (ZKP) and Fully Homomorphic Encryption (FHE) holds immense potential for the future of private computation. As we've seen, challenges persist in combining the two cryptographic tools efficiently. However, ongoing research and innovative solutions such as application-specific verifiable FHE and our proposed Tatami-FHE scheme bring us closer to a practical verifiable FHE system.
The convergence of ZKP and FHE has the potential to revolutionize private computation in various applications, including blockchain technology and decentralized systems. As research continues to advance, we can expect to see more secure, efficient, and robust solutions to support privacy in a world where data is increasingly sensitive and valuable.
Interested in reading more 👇
If you are a team working on either ZKP or FHE, we would love to hear from you! If you are an investor interested in our work please reach out via Twitter. @icme_app.