How To Make Small Commitments
In this short blog post I will give a high-level explanation of a recent result which will be published at the 11th Conference on Security and Cryptography for Networks next week. This post is targeted at the general public and ideally your grandparents should understand it when you explain it to them over the dinner table at a family event (though I have to admit that the result itself is quite technical, and many grandparents may simply not care about cryptography). This work started years ago and parts of it already appeared in my PhD thesis which I submitted in the end of 2016. But it took us a while to converge to the current state. This is joint work with Ivan Damgård, Sabine Oechsner, Vadim Lyubashevsky and Chris Peikert.
In our work, we present an efficient way to realize a cryptographic primitive called a commitment. These commitments are one of the most fundamental building blocks in modern cryptography. Whenever you try to construct a secure protocol they come in very handy: they have tons of applications when it comes to keeping a bad party from harming the flow of the protocol or when you need to decouple inputs of parties.
To explain what commitments actually are, let me tell a story of Alice and Bob. Alice just recently decided that she wants to buy a car, while Bob has one standing in his garage which he would like to sell. Now let’s say that both of them meet so that Alice can have a look at the car and its quality. After that, she has a price like $10,000 in mind which she would honestly pay to get the car. Bob, on the other hand, thinks that clearly his car is worth $14,000. They agree to pick the price in the middle of how they estimate the value as the final price.
But let’s say Alice knows in advance that Bob will demand $14,000 from her. Then she could instead pick $8,000 as her price and would save $1,000. Similarly, Bob could just raise the price to steer it into a direction which is more favorable to him if he knew Alice’s bid ahead of making his offer (we assume that, without that knowledge, Alice and Bob would be honest). Now one of them has to come forward with his price first, so is all lost? Well, here’s a simple real-world protocol to solve this problem:
- Alice takes a sheet of paper and, without Bob being able to spy on her, writes $10,000 on this sheet. Then she puts it into an envelope so that Bob cannot see it.
- Bob, upon seeing this envelope, tells her that $14,000 is the amount that he demands.
- Alice then opens the envelope and shows the $10,000 which are written on the sheet to Bob.
- Alice buys the car for $12,000 and has a blast in California with her new car while Bob buys an electric scooter because he needs to get to work and these seem trendy right now.
This envelope is what cryptographers call a commitment: it is binding, namely Alice cannot change her opinion about what is inside the envelope once it’s closed and in front of both of them. At the same time, it is hiding because whatever Bob says is now independent of Alice’s offer — he simply cannot peek into the envelope without Alice’s help. Commitments have been around for at least 35 years (if we date them back to Manuel Blum’s famous “coin flipping over the phone”).
As you may have guessed, people have been constructing commitment schemes before. Ours has three advantages: 1) it is post-quantum secure 2) it permits efficient zero-knowledge proofs for relations among commitments; and 3) it is efficient and flexible. Meeting all three requirements simultaneously turned out to be not as easy as we thought, but here are some details.
Post-Quantum Security
Quantum computers share a lot of their fate with fusion reactors: whenever you ask scientists, they will be realized 10 years from now. Also, when you ask them again 10 years later. But similar to recent breakthroughs in the construction of fusion technology, engineers have made huge progress in realizing the first quantum computers that may be useful for something. Why is that important? Because the cryptography which secures almost everything on the internet today is based on algorithms which quantum computers can break. Coincidentally, also commitment schemes which have these efficient proof protocols and are efficient themselves are based on the same assumptions which such computers render insecure. Therefore we constructed ours from so-called lattice-based assumptions. These are conjectured to be secure against these new machines, and many submissions for post-quantum algorithms to the recent NIST challenge rely on them as well. There have also been other commitment schemes which use this assumption, such as those due to Benhamouda et al. and Kawachi et al., to just name two.
Efficient Zero-Knowledge Proofs
Zero-Knowledge proofs are a seemingly magical toy from the crypto toolbox which can do things as the following: Alice makes a commitment C to a value x and gives this commitment C to Bob. Now Alice convinces Bob about the following: she knows what is inside the commitment and he does not learn any information about x, only that she knows what it is. The protocol which Alice will use to convince Bob is called a zero-knowledge proof of knowledge. It might seem counter-intuitive why Alice would run such a proof, but imagine that Alice gave Bob a commitment C which comes from someone else…
Even better, these proofs can show more complex statements: Alice can send commitments X,Y and Z to Bob and show that she knows what is in each of them, and if you open the first and the second and add the opened values together, then this gives the same as what is stored in commitment Z. This allows to compute with commitments, which is of crucial importance when using these as parts in other protocols. The commitments which we construct have as efficient proofs as previous work.
Efficient and Flexible
In addition to the above two criteria, there are two more which set our scheme apart from previous work. First, in comparison to its most direct competitor it allows for commitments that are a factor 6 smaller (while also having smaller proof sizes). This makes it preferable for practical applications.
This improvement in size is directly related to the flexibility of our construction. We allow to choose how hard either the binding or the hiding property should be. That means, whoever uses the scheme can set the binding to be computational, which means if Alice has enough computational power to break lattice-based cryptography then she could change the value in the envelope. At the same time, the hiding can be statistical meaning that a Bob with unlimited computational power only has an overwhelmingly small chance to learn information about the committed value. At the same time, we can also reverse this (computationally hiding, statistically binding) if the application needs these demands — or have both properties being computational, which yields the smallest parameters.
I would now very gladly like to tell you how exactly we do all of this, but unfortunately this is too technical for a post on this page (see picture on the left). I’d therefore encourage you to take a look at the paper, or at least tell your grandma or grandpa about commitments and zero-knowledge proofs next Christmas…
TL;DR: We construct the currently most efficient commitment scheme from structured lattice assumptions. Depending on the parameters chosen, our scheme can be either computationally or statistically binding or hiding. It furthermore permits efficient proofs of relations among commitments.