Greyhound: Fast Polynomial Commitments from Lattices
Abstract
In this paper, we propose Greyhound, the first concretely efficient polynomial commitment scheme from standard lattice assumptions. At the core of our construction lies a simple sigma protocol for proving evaluations for polynomials of bounded degree N with verifier time complexity $O(\sqrt{N})$. By composing it with the LaBRADOR proof system (CRYPTO 2023), we obtain a succinct proof of polynomial evaluation (i.e. polylogarithmic in N) that admits a sublinear verifier runtime. To highlight practicality of Geyhound, we provide implementation details including concrete sizes and runtimes. Notably, for large polynomials of degree at most $N=2^{30}$, the scheme produces evaluation proofs of size 93KB, which is 8000X smaller than the recent lattice-based construction by Albrecht et al. (EUROCRYPT 2024), and three orders of magnitude smaller than Ligero (CCS 2017) and Brakedown (CRYPTO 2023).
Authors’ notes
“Greyhound” offers new method for efficiently verifying polynomial calculations
Lattice-based cryptography is an approach for constructing security primitives. It is based on problems from an area of mathematics called “geometry of numbers.” The three post-quantum cryptography algorithms, developed by IBM, which NIST selected for standardization are lattice-based.
A commitment scheme is a fundamental tool in cryptography that allows one party to “commit” to a value while keeping it hidden, with the ability to reveal it later. Think of it like sealing a letter in an envelope. The commitment locks the value inside (hides it), and when the time is right, the envelope can be opened to reveal the original value (proving it). Commitment schemes are important because they are used in cryptographic protocols, including zero-knowledge proofs, secure multi-party computation, and blockchain technologies. They ensure that data can be securely hidden until it's appropriate to reveal it, which is critical for privacy and security in digital communications.
Greyhound is a specific type of commitment scheme called a “polynomial commitment scheme.” This means it’s designed to commit to a polynomial (a mathematical expression involving sums of powers) so that one can later prove that a certain value is the result of evaluating the polynomial at a specific point without revealing the polynomial itself. This is useful in many cryptographic applications, such as verifying transactions or computations securely and privately.
Greyhound is a specific type of commitment scheme called a polynomial commitment scheme.
The main idea behind Greyhound is to create a system that can quickly and securely prove that a polynomial has been evaluated correctly, even when the polynomial is very large. Greyhound is built on a basic proof system that can verify these calculations with a time complexity that scales with the square root of the polynomial's degree (how complex the polynomial is). Combined with another advanced proof system developed by IBM, called LaBRADOR, it allows for very fast verification that doesn't require checking the entire polynomial, making it more efficient. LaBRADOR is another innovation from the IBM cryptography team presented at Crypto 2023.
To show how practical Greyhound is, IBM scientists have implemented and verified that it can produce very small proof sizes. For example, for large polynomials with up to 230 terms, Greyhound's proof size is just 93KB. This is 8,000 times smaller than a similar method proposed by other researchers recently and much smaller than earlier methods. Consider this analogy. Previously, the letter that we described in the background section was as large as a public swimming pool (8,000x). Greyhound reduces the size of the letter to a regular format (1x). Mathematically, the pool size is 10x30m = 300m2. If you divide this by 8,000, you get an area of 37 cm2 which corresponds to a standard letter size.
Business areas impacted by commitment schemes
-
Blockchain and Cryptocurrencies: Commitment schemes are essential for ensuring the integrity of transactions on a blockchain. They allow users to commit to transactions or data without revealing it until a specific condition is met. Greyhound could make these processes faster and more efficient, enabling more scalable and private blockchain systems.
-
Finance and Auditing: In financial services, commitment schemes can be used to ensure the privacy and security of sensitive financial data during audits. For example, a company could commit to its financial statements in a way that allows an auditor to verify the correctness of certain numbers without revealing the entire dataset, preserving confidentiality while ensuring accuracy.
-
Supply Chain Management: Commitment schemes can help verify the authenticity and integrity of data in supply chains. For instance, a company might commit to a record of goods being produced and shipped without revealing proprietary details, allowing downstream partners to verify that the goods match the committed record.
-
Data Privacy in Healthcare: In healthcare, commitment schemes could allow for the secure sharing of patient data between institutions. For example, a hospital could commit to patient records in a way that allows other parties to verify certain aspects (like eligibility for a study) without accessing the entire medical history, protecting patient privacy.
In short, Greyhound is a faster and more efficient way to verify large polynomial calculations using secure cryptographic methods. This makes it a valuable tool in areas where data integrity and privacy are essential, particularly in industries like blockchain, finance, supply chain, and healthcare.