How To Make Small Commitments

Carsten Baum
Aug 29, 2018 · 6 min read
Image for post
Image for post
By Oscar Ivan Esquivel Arteaga on Unsplash

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.

Image for post
Image for post
By Markus Spiske on Unsplash

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:

  1. 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.
  2. Bob, upon seeing this envelope, tells her that $14,000 is the amount that he demands.
  3. Alice then opens the envelope and shows the $10,000 which are written on the sheet to Bob.
  4. 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

Efficient Zero-Knowledge Proofs

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

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.

Image for post
Image for post
Our construction (in a nutshell…)

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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store