The Pedersen Commitment
I have been lucky enough to speak to some of the most amazing people who have built the core of security on the Internet, and a person near the top of my list is … Torben P. Pedersen. So a few weeks ago, I was so happy to speak to him.
The Pedersen Commitment
So how do we create a world where we can store our secrets in a trusted and then reveal them when required? Let’s say I predict the outcome of an election, but I don’t want to reveal my prediction until after the election. Well, I could store a commitment to my prediction, and then at some time in the future I could reveal it to you, and you can check against the commitment I have made. Anyone who views my commitment should not be able to see what my prediction is.
This is known as Pedersen Commitment, and where we produce our commitment and then show the message that matches the commitment. In its core form, we can implement a Pedersen Commitment in discrete logs [here]. But blockchain, IoT, Tor, and many other application areas, now use elliptic curve methods, so let’s see if we can make a commitment with them. The classic paper is here:
So before the interview with Torben, here’s an outline of the Pedersen Commitment:
Interview
Bill: Okay, so tell me a bit about yourself, and what got you into cryptography?
Torben: Well, I was studying computer science at university in Aarhus, and I just thought it was an interesting subject that was somewhere between computer science and mathematics.
Bill: And so you invented a method that we now know as the Pedersen Commitment. What motivated you to do that? And how does it work? And how do you think it will be used in the future?
Torben: Well, the reason I worked with this, was that I was working with verifiable secret sharing. There was, at the time, a method for doing non-interactive verifiable secret sharing based on a commitment which was unconditionally binding and computationally hiding. At the time, there was also inefficient commitments, that had the property of being unconditionally hiding, and I thought it would be nice to have a verifiable secret share where you don’t have to rely on any computational assumptions, in order to be sure that your secret is not revealed when you do a secret share.
Torben: Then there was a paper which created an authentication scheme very similar to Schnorr. But it’s used a similar idea for a useful commitment. And that was kind of the combination of those two (the existing non-interactive verifiable secret sharing and the ideas form this authentication scheme), which motivated me to do verifiable secret sharing. And the commitment scheme was, of course, an important part of that because it had unconditioned hiding property, and it had the mathematical structure that was needed for the secret sharing.
Bill: And it has scaled into an elliptic curve world. But with elliptic curves and discrete logs now under threat, how would you see it moving forward into a possible post-quantum crypto world?
Torben: The good thing about the commitment scheme is that it is unconditional hiding. Of course, you can be sure that your private information is not leaked, even in case a quantum computer is constructed. But of course, the protocols that are using this one have to see what effect does it have if one, for example using a quantum computer, can change ones mind about a commitment. So you need to see how that would affect those protocols.
Bill: So an example use of the commitment could be of a secret say someone voting in an election. So you would see when the commitment was made, and then when the vote was cast. Then the person could reveal what their votes actually was. Now it’s been extended into zero-knowledge methods to prove that you have enough cryptocurrency to pay someone without revealing the transactions. How does that world evolve where you only see an anonymized ledger, and which can scare some people, but for others that is a citizen-focused world? How do you see your commitment evolving into privacy-preserving ledgers?
Torben: I go back to what we’re doing at Concordium where we have a blockchain which gives a high assurance about the privacy of the users acting on the blockchain. At the same time, using zero-knowledge proof, we set it up in such a way that designated authorities — if they under certain circumstances, for example, are given a court order — they will be able to see to link an account on the blockchain for that particular person. So, actually the zero-knowledge proofs and the commitment schemes — and all that — is used to guarantee the privacy of the users acting on the blockchain, and there are also regulatory requirements, that it must be possible to identify people who misbehave on the blockchain.
Bill: Yeah, that’s a difficult thing, and it’s probably where the secret is stored. So, if the secret stored in the citizen’s wallet, then only they can reveal that. And if the secret needs to be stored, for money laundering by an agency could hold it.
Torben: Actually we do not have to store the secret of the user. But there are other keys which allow us to link the account with a particular user. That is something which only designated parties can do. So we have one party which is the identity provider with issues and identity to a user and other parties called anonymity reworkers. And those parties will have to work together in order to link an account to a user. We use zero-knowledge proofs when creating the account to assure that account is created in such a way that it is possible for you to trace back the account to the user.
Bill: And in terms of zero-knowledge proofs, there is a sliding scale from highly complex methods that you would use for Monero and anonymized cryptocurrencies, to the simpler ones to Fiat Shamir implementation. And they are probably unproven in terms of their impact for performance and for security. Where is the sweet spot? What methods do you think are the best for that?
Torben: I think we need to see improvements in zero-knowledge proofs in order to have really efficient blockchains and non-interactive zero-knowledge proofs on a blockchain. So I definitely think we need some work on that. There are some acceptable non-interactive zero-knowledge proofs for the moment. We are using Bulletproofs for the moment together with Shamir shares on it, in order to make it non-interactive. But I think there are some technologies like zkSnarks and zkStarks, but I think there’s room for improvement.
Bill: And what do you think the key challenges within cryptography just now What do we need to be working on in the next three to five years?
Torben: Yeah, so the biggest challenge, as you already mentioned, and that’s what happens if we have a quantum computer that can break the assumptions that a lot of the constructions are based on today. Whether we have a quantum computer, I don’t know, but we need to be prepared. We have some post-quantum algorithms, which I think also are quite complex, and it would be nice to have something that was more efficient and better to use. I think there’s also room for work on that aspect.
Bill: And obviously, to create some toolkits that move away from an Ethernet world and where the Internet was really built on the seven-layer model — and it’s flawed. We perhaps need to rebuild on a toolkit of math, so that we actually have a solid foundation. I know that Hyperledger is starting to build these tools for developers. When we do see that rebuilding happening, and where are the toolkits going to come from?
Torben: Toolkits could come from blockchain companies such as Concordium, for example. It could also come from the community with sponsored projects. If we can build up an infrastructure that allows people to use blockchains in the ledger, without trusting a particular one particular party, so that they can create a trust, which is probably lacking on the Internet today. It’s very difficult, as with the current Internet it is very difficult to know if you can trust someone or not. I hope blockchain technology can help create an infrastructure for that. There’s a long way to go. We need good public permissionless blockchains for that, so you don’t have to rely on a particular party for this. Obviously, that is sufficient, but there’s quite some way to go.
Bill: How do you change the approach of governments and industries that have been around for hundreds of years. So if you look at the legal industry, they still typically only accept wet signatures. They might have a GIF of a signature and add it to a PDF, but that’s as far as it goes. So how are we going to really transform governments and, and existing industries to really accept that digital signatures are the way to do these things?
Torben: Yeah, I think it’s a bit dangerous, you know, accepting these GIFs of signatures and digital signatures which are not really cryptographically secure. I’m not a big fan of that. I’d like to see us moving to digital signatures, which are the way that we originally envisaged in the cryptographic world, and where the party who signs the signature is in control of the key which created the digital signature. I hope you’ll see a movement towards that level of security.
Bill: And could you tell me a little bit about the Concordium Foundation and what’s objectives on what it hopes to achieve?
Torben: So our vision is to create a public permissionless blockchain that can help to create trust across industries. We want to enable entities such as businesses and private persons, to interact or act privately on the blockchain. At the same time, it’s very important for us not to create an infrastructure, which allows criminals to misuse it, and for some money laundering problem. Thus we want to create an environment where it’s possible to identify people who misbehave or break the rules. And that is why we have this identity layer as part of our blockchain.
Bill: And what got you into blockchain?
Torben: I think the technology is very interesting. There’s a lot of things you said based on a lot of pretty old cryptography. There’s also new developments, for example, the zero-knowledge proofs. So there’s new and new developments or developments. So very interesting. I mean, it’s not necessarily what I was interested in, but when I did research many years ago. That’s probably what I wanted to work with. I have been working with cryptography — mostly in mostly for the financial sector for 25 years. And that’s also very interesting. There are challenges and it’s also nice to get back to the sort of basis that I worked with many years ago.
Bill: You took a route into industry but obviously you could have gone into academia and you could become a professor and have an academic research team.
Torben: I think it was because I wanted to work with practical aspects of using cryptography. What I’ve been in research for some years and I thought I needed to try something else. And I was very keen to see how it would be used in practice and be part of that. So that’s why I made that step.
Bill: What does our digital world look like that’s made up of tokens, cryptographic tokens, consensus systems and digital identities. And you think that that world will come anytime soon that we can trade assets, we can have digital assets that can be traded.
Torben: Well, it depends on what you mean by soon. I think we will have some way to go. I think the use of blockchains for trading tokens, for handling tokens, and for registering tokens, is an obvious thing, but we also need to bring value to businesses or projects. To have something that people can feel it and control. We need to make sure that information is protected the right way, even though it is registered on a public blockchain, for example.
Conclusions
More to come. If you are interested, here’s Mimblewimble, and which uses the commitments:
