The Wonderful CL Signature: Meet Jan and Anna
What I love about research, and especially cryptography, is that it is about people, and not large faceless companies with billions of dollars to spend on research. With this, a single person can do more than all of the research conducted in the labs of a big company. These are generally people with creativity, passion and a drive to address fundamental issues.
Research, at its worst, is a paper mill of dull and uninspiring work, and where many go through the motions of publishing for the sake of it. But, at its best, it involves researchers coming up with breakthroughs that no one could ever conceive of and which fundamentally advances and changes our world. It’s about people like Hellman, Diffie, Rivest, Shamir, ElGamal, Merkle, and Adleman, and so many other giants whose shoulders we build the security and trust of the Internet.
And, so, when two of your favouriate cryptography researchers get a prize, it’s always a great feeling[here]:
and here they are:
At Real World Crypto 2024, they received the Levchin Prize — and which is awarded to work that has stood the test of time. The award recognizes the work they did together while at IBM — and which had one of the best cryptography research infastructrures in the world.
Anonymous Credentials — CL Signatures
We have several problems on the Internet. The first is that we have our identities harvested by companies such as Facebook and Google, and the second is that we must now prove things — such as our age or our location — and in doing so, we are revealing our information to others. So how can we create a trusted digital world, where we prove things, without revealing our sensitive information?
We have barely got to the point where we can digitally sign our documents, and where many industries still rely on wet signatures. With this, we create a public key (pk) and a private key (sk) and then use our private key to sign something. This then creates a signature (S). Our public key then validates the entity which signed it. But whenever we sign a document, it often reveals our identity, and, possibly other parts of our identity (such as our age, address, and so on). In many cases, though, such as being served in a bar, Peggy should just have to prove that she is over 18 years old, and not have to reveal her name, date of birth and address.
So in a paper-based system, Peggy will have some ID which has a unique identifier that only a trusted entity will be able to create. This might be a driver’s licence which has a government watermark on the card. But in an electronic system how do we create the equivalent? Well, normally we use public key encryption to prove identity.
In a credential based system, we create credentials which are signed by a given entity. For example, if Peggy (the prover) is over 18, she will create a credential that will be signed by her private key of the entity which proves that she is over 18 to Victor (the verifier):
Name: Peggy
Address: 10 Alice Road
Credential 1: Over 18
-- Signed: Peggy.But what if Peggy doesn’t want to reveal her identity, and stay anonymous? How can she now reveal that I am over 18, without revealing anything else about her credentials, and for Peggy to get the credentials in an anonymous way? For this, we need an anonymous credential system, and one of the most widely used is the Camenisch-Lysyanskaya (CL) signature [1]:
Within Camenisch-Lysyanskaya signature (known as a signature with efficient protocols), Peggy can pass Victor a signature which proves “I am over 18”, and which will not reveal any other of her credentials. It thus allows:
- Secure two-party computation. This allows a signer (such as the DVLC) to issue a signature to Peggy (the owner of the signature) without learning all the messages that are being signed, or the full signature.
- Zero-knowledge proof. This allows Peggy to prove the required signature on a number of messages, without giving away the signature (or additional sub-information on the messages).
And so Peggy is happy. She has asked the DVLC to prove that she is over 18, and they have provided the signature, of which they have no way of knowing how she is using it, and then Peggy can use this in the bar — or anywhere else — to prove she is over 18.
The implementaiton is here:
Other related work includes advanced signatures [2]:
Verifiable Encryption
So Alice has some ciphertext. How does Bob prove to Alice that he has used a certain key to encrypt the message? Well, one way is for Bob to provide a Non-interactive Zero-Knowledge Proof (NIZK), and which will not only prove the party who encrypted the message but also the party who has the secret key.
The encryption key might have been sourced from Trent and who has a public key (pk) and a secret key (sk). Then Bob might encrypt his secret key with Trent’s public key (pk) and then give this to Alice. Alice might then ask Bob to prove that the ciphertext will be decrypted using Trent’s secret key (sk). Bob is thus a proxy in-between and using Trent’s public key to encrypt his secret key.
For this, we bind to some public data — known as a label — within the encryption and decryption processes. Alice thus attaches a label to the ciphertext that defines the conditions for decryption, such as related to the expiration time or to Alice’s identity. If the decryption then takes place with a different label, it will not reveal anything about the original message. Along with this, verifiable encryption can be used by Alice to ask Trent for a proof that he has decrypted the ciphertext correctly.
Another application is within a fair exchange of data, and where Bob and Alice exchange data. With this, either both of them will receive the data or none of them. If one party pulls out, it should not be possible for the other party to get the other party’s data. Bob and Alice will then use Trent’s public key to encrypt the data. The label within the verifiable encryption will ensure that the exchange mechanism is properly enacted and the verifiable decryption ensures that it is performed correctly by Trent.
The method we will implement will use the Coinbase Krytology library and is based on a classic paper from Jan Camenisch and Victor Shoup [here][3]:
With this, we create ciphertext with the secret key, and then which can be decrypted with the public key. There is also a proof created that it has been encrypted with a defined public key. Each ciphertext has a proof triplet of {u, e, v} and which relates to a challenge (c) and responses of m and r.
We can use the Kryptology library developed by Coinbase [here] to implement the Camenisch-Shoup method [here]:
package mainimport (
"fmt"
"math/big"
"os" "github.com/coinbase/kryptology/pkg/verenc/camshoup"
)var (
testP = B10("37313426856874901938110133384605074194791927500210707276948918975046371522830901596065044944558427864187196889881993164303255749681644627614963632713725183364319410825898054225147061624559894980555489070322738683900143562848200257354774040241218537613789091499134051387344396560066242901217378861764936185029")
testQ = B10("89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164815053566739")
testP1 = B10("153739637779647327330155094463476939112913405723627932550795546376536722298275674187199768137486929460478138431076223176750734095693166283451594721829574797878338183845296809008576378039501400850628591798770214582527154641716248943964626446190042367043984306973709604255015629102866732543697075866901827761489")
testQ1 = B10("66295144163396665403376179086308918015255210762161712943347745256800426733181435998953954369657699924569095498869393378860769817738689910466139513014839505675023358799693196331874626976637176000078613744447569887988972970496824235261568439949705345174465781244618912962800788579976795988724553365066910412859")
)func B10(s string) *big.Int {
x, ok := new(big.Int).SetString(s, 10)
if !ok {
panic("Couldn't derive big.Int from string")
}
return x
}func main() { argCount := len(os.Args[1:])
val := "1000"
if argCount > 0 {
val = os.Args[1]
} fmt.Printf("Message: %s\n", val) fmt.Printf("\n=== Generating keys ===\n")
group, _ := camshoup.NewPaillierGroupWithPrimes(testP, testQ) domain := []byte("My Domain") ek, dk, _ := camshoup.NewKeys(1, group) res1, _ := dk.MarshalBinary()
fmt.Printf(" Decryption key (first 25 bytes): %x\n", res1[:50])
res2, _ := ek.MarshalBinary()
fmt.Printf(" Encryption key (first 25 bytes): %x\n", res2[:50]) fmt.Printf("\n=== Encrypting data with proof ===\n")
msg, _ := new(big.Int).SetString(val, 10) cs, proof, _ := ek.EncryptAndProve(domain, []*big.Int{msg}) res3, _ := cs.MarshalBinary()
fmt.Printf(" Encrypted data (first 25 bytes): %x\n", res3[:50]) res4, _ := proof.MarshalBinary()
fmt.Printf(" Proof (first 25 bytes): %x\n", res4[:50]) rtn := ek.VerifyEncryptProof(domain, cs, proof) if rtn != nil {
fmt.Printf("We have not proven the key\n")
} else {
fmt.Printf("We have proven the key\n")
} fmt.Printf("\n=== Let's try with the wrong keys ===\n")
group, _ = camshoup.NewPaillierGroupWithPrimes(testP, testQ) ek2, _, _ := camshoup.NewKeys(1, group) _, proof1, _ := ek2.EncryptAndProve(domain, []*big.Int{msg}) rtn1 := ek.VerifyEncryptProof(domain, cs, proof1) if rtn1 != nil {
fmt.Printf("We have not proven the key\n")
} else {
fmt.Printf("We have proven the key\n")
} fmt.Printf("\n=== Now decrypted ciphertext ===\n\n")
dmsg, _ := dk.Decrypt(domain, cs) enc, _ := cs.MarshalBinary()
fmt.Printf("Encrypted (showing first 25 bytes): %x\n", enc[:50]) fmt.Printf("Decrypted: %s\n", dmsg[0])}A sample run shows that a valid encryption key produces a valid proof, and then an invalid one generates an incorrect proof [here]:
Message: 1000=== Generating keys ===
Decryption key (first 25 bytes): 01ff037949f368fc3ac355ecc9eab7c2b6d1e099981acb477654aed35dcfaf12946359fca1d553bedecebd1c40389408d057
Encryption key (first 25 bytes): 01ff034019af1c7dfa022c9bf17e2bfe5909d67a202b7203ff0ca1152a9e5f8bfcc82d890f76aa810c6857a245ec5a8a5d28=== Encrypting data with proof ===
Encrypted data (first 25 bytes): 01800401753d8c131446725e7d6d7b8613d5b966063aba8a59bb9df1c776b725c67c5c8e2861b397b0dc55933d8eafa85edc
Proof (first 25 bytes): 01800209e575d9bf533322f513cda8c44d5d0413401f189b77ac9f1365552dbef03d1ce4b098358b4e635577bfae7e76f231
We have proven the key=== Let's try with the wrong keys ===
We have not proven the key=== Now decrypted ciphertext ===Encrypted (showing first 25 bytes): 01800401753d8c131446725e7d6d7b8613d5b966063aba8a59bb9df1c776b725c67c5c8e2861b397b0dc55933d8eafa85edc
Decrypted: 1000Set Membership — CCS08
So, let’s say there’s a number of winning tickets in a lottery of [654, 703, 991, 1011], can I prove I have a value which is in this set, and without giving away the number on my ticket? Well, one of my favouriate researchers — Jan Camenisch — created a method where we can prove that we have a value in a set of values, and without giving our value away [1]. The paper was produced in 2008, and is often referred to as CCS08 (after its authors). With this, we provide a zero-knowledge proof that σ is included in a discrete set Φ. This set is represented as 64-bit integers and could thus be hashed version of the string.
Method
So, let’s say there’s a number of winning tickets in a lottery of [654, 703, 991, 1011], can I prove I have a value which is in this set? For this, Jan Camenisch et al created a method where we can prove that we have a value in a set of values, and without giving our value away [1]. The paper was produced in 2008, and is often referred to as CSS08. With this, we provide a zero-knowledge proof that σ is included in a discrete set Φ. This set is represented as 64-bit integers, and could thus be hashed version of string.
The paper was produced in 2008, and is often referred to as CSS08 [4]. With this, we provide a zero-knowledge proof that σ is included in a discrete set Φ. This set is represented as 64-bit integers, and could thus be hashed version of string. The code used is [5][here]:
package main
import (
"crypto/rand"
"fmt"
"os"
"strconv"
"strings"
"github.com/0xdecaf/zkrp/ccs08"
"go.dedis.ch/kyber/v3/pairing/bn256"
)
func StringToIntArray(A string) []int64 {
strs := strings.Split(A, " ")
ary := make([]int64, len(strs))
for i := range ary {
v, _ := strconv.Atoi(strs[i])
ary[i] = int64(v)
}
return ary
}
func main() {
tofind := 6
set := "1 2 3 4 5"
argCount := len(os.Args[1:])
if argCount > 0 {
tofind, _ = strconv.Atoi(os.Args[1])
}
if argCount > 1 {
set = os.Args[2]
}
s := StringToIntArray(set)
p, _ := ccs08.SetupSet(s)
fmt.Printf("To find: %d\n", tofind)
fmt.Printf("Set: %v\n", s)
r, _ := rand.Int(rand.Reader, bn256.Order)
proof_out, err := ccs08.ProveSet(int64(tofind), r, p)
if err != nil {
fmt.Printf("Error %s", err.Error())
return
}
result, err2 := ccs08.VerifySet(&proof_out, &p)
if err2 != nil {
fmt.Printf("Error %s", err.Error())
return
}
if result == true {
fmt.Printf("\nProof that %d is in [%v]\n\n", tofind, set)
} else {
fmt.Printf("\nDid not find value in array\n")
}
fmt.Printf("Proof: C= %s\n", proof_out.C)
fmt.Printf("Proof: D= %s\n", proof_out.D)
fmt.Printf("Proof: V= %s\n", proof_out.V)
}Now, when we can try if 3 is included in a set of [1, 2, 3, 4, 5, 6][here]:
To find: 3
Set: [1 2 3 4 5 6]
Proof that 3 is in 1 2 3 4 5 6
Proof: C= bn256.G2((19027679596361727465830466691714590027150250928743100188329248607389451375082,16949628276016363601794894538213922177395443826498276657422770803261495066169), (5699393798569477841978040021820316268277614436097958436753449789474039110118,8806612708159320381692367829880243948618090450626214010787274656678555437726), (5236041996946827246272430617707245970400478318225497342948916690172135694053,9938720226749779124332076293433564025582280697351896039484171140878978368112))
Proof: D= bn256.G2((3055385285225682457170931824984084710557591129970555220631679154490160538007,16741863869001983303859601610226823943417933471155831914781932489026213480048), (8851887114736475637449165663341713980374824686853280533381963095602317456359,529833433432526140282887716252910899691512855350147520271943056326737960188), (0,1))
Proof: V= bn256.G2((5389494577184098706147450878418556221050036083334693733955352021661432953834,6692919577824347552839485052008328374223293481178835104263907115847795868964), (1914193116904688737702450702033754563518223052612828372842693950285070367730,14918588892877446422261524405322282796423663255426519483236776812327905525652), (16911356167497400501411690244093098585964473813732663002213275613039696596134,5188262128010807626583488468074248822613977405555581853697113883066450076566))Now, when we can try if 7is included in a set of [1, 2, 3, 4, 5, 6][here]:
To find: 7
Set: [1 2 3 4 5 6]
Error Could not generate proof. Element does not belong to the interval.Camenisch Oblivious Transfer
The Camenisch Oblivious Transfer method allows us to send a number of messages, and where the sender cannot determine which ones have been selected:
The following allows us to define a data array, and then pick an element of the array and reveal the contents, without the sender knowing which one we have picked [6]:
Conclusions
Well done to Anna and Jan. A deserved award!
References
[1] Camenisch, J., & Lysyanskaya, A. (2001). An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In Advances in Cryptology — EUROCRYPT 2001: International Conference on the Theory and Application of Cryptographic Techniques Innsbruck, Austria, May 6–10, 2001 Proceedings 20 (pp. 93–118). Springer Berlin Heidelberg.
[2] Camenisch, J., & Lysyanskaya, A. (2004, August). Signature schemes and anonymous credentials from bilinear maps. In Annual International Cryptology Conference (pp. 56–72). Springer, Berlin, Heidelberg. The code on this page implements Section 3.2: [here]
[3] Camenisch, J., & Shoup, V. (2003, August). Practical verifiable encryption and decryption of discrete logarithms. In Annual International Cryptology Conference (pp. 126–144). Springer, Berlin, Heidelberg.
[4] Camenisch, J., Chaabouni, R., & Shelat, A. (2008, December). Efficient protocols for set membership and range proofs. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 234–252). Berlin, Heidelberg: Springer Berlin Heidelberg.
[5] https://github.com/0xdecaf/zkrp
[6] Camenisch, J., & Neven, G. (2007, May). Simulatable adaptive oblivious transfer. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 573–590). Springer, Berlin, Heidelberg.
