Advancements in quantum computers drive the need for systems that have post quantum security. This has lead for developments into polynomial commitment schemes (PCSs) that are plausibly post quantum secure. Many zkSNARKs have been based on group theoretic security assumptions that can be broken with sufficiently powerful quantum computers. A notable exception is Plonky2. Plonky2 uses FRI which uses hash functions to maintain intregity in a post quantum world.
Greyhound is a new polynomial commitment scheme (PCS). This scheme is based on a lattice-based assumption for its security. As such, Greyhound is plausibly post quantum secure.
Greyhound is not the first lattice-based polynomial commitment. However, it is the first one that appears to be pratical in terms of its complexities for proving evaluations of the committed polynomial. Specifically, Greyhound emits a proof of size O(\mathsf{polylog}(N)), the verification is O(\sqrt{N}) and proving time is O(N) where N is a bound on the committed polynomial.
What other interesting properties does Greyhound possess?
- No trusted setup! The public parameters are randomly generated matrices.
- Plausibly homomorphic(?). Mathematically, as discussed in the meeting, Greyhound appears to be homomorphic. However, it may have issues with the verifier’s norm checks. I will investigate this further, and post an update.
These properties make Greyhound a very exciting polynomial commitment scheme to investigate further.
Visit the IFT ZK Meeting Notes for additional resources, and the video (To be posted) of this meeting. And join in the conversation.