The Mighty Jan … Cryptographic Genius!
The Mighty Jan … Cryptographic Genius!
Everyone in cybersecurity (hopefully) knows about Bruce Schneier and Ron Rivest. But, there’s another person that you should know about … Jan Camenisch:
He now is the CTO and Cryptographer of DFINITY, and, since 1998, Jan has consistently produced research outputs of rigor, novelty and sheer brilliance [here]:
One of the most interesting things about his work is that his methods often take a few years to come to the fore, and create a significant impact. I suppose that’s a feature of cryptographic research, and where few people can actually see the potential of a new method until it is actually coded and used in a real-life environment.
Jan’s research core happened when he was hosted in the IBM Zurich Research Lab, but has since moved to Definity, and still producing research outputs that are some of the best in the whole of the computer science research area.
Verifiable Encryption … When Jan Met Victor
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 uses 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 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][1]:
With this, we create ciphertext with the secret key, and then which can be decrypted with the public key. There is also 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: 1000And, Jan is back working with Victor Shoup, with a fantastic new paper on the Internet Computer Consensus (ICC) family of protocols and which support Byzantine fault-tolerant with the Internet Computer [here][2]:
Unlinkable IDs … Jan and Anja
Jan’s worked with Anja Lennman while at IBM, and they produced some amazing outputs. Two of the best related to privacy-preserving methods in the usage of citizen identifiers.
We have data sources which can span across the public sector. This might relate to health records, tax records, and so on. The nightmare situation for many is where governments create a data lake, and where all of your data is linked and merged. This would allow your GP to see your tax return, and the tax inspector the chance to see your health record. An improved solution is thus for citizens to own their own identity, and then allow them to link it between disparate systems.
So, let’s say that you don’t trust your government to match your identity across different data systems. Two of the best method proposed for this matching are known as CL-15 and CL-17:
- [CL-15] Camenisch, Lehmann. (Un)linkable Pseudonyms for Governmental Databases. CCS’15. [Link][3]
- [CL-17] Camenisch , Lehmann. Privacy-preserving User-auditable Pseudonym Systems. IEEE EuroSP’17 [4].
Within these papers, Camenisch and Lehmann outline a way that the user can own their own ID (UID), and then store a pseudonym on System A (PsIDA), and another one on System B (PsIDB). A controller then links the two IDs together, but cannot tell the identity of the person involved.
In this case System A has a value of xa, and System B has a value of xb. Next the user ID (UID) is then used to generate the pseudo ID in each system. For System A the pseudo ID will be UID^{xa}, and in System B it will be UID^{xb}. Because the security of discrete logs, neither System A nor System B can determine the value of UID:
Now we want to link Bob from System A to System B. First System A encrypts is pseudo-ID (PsIDA) with the public key of System B:
Next we use homomorphic encryption to raise this cipher to the power of xb/xa:
This is the same as:
The controller can then pass this cipher value to System B, and through the wonder of homomorphic encryption we get:
System B can then use its private key to get:
And thus System B will know the pseudo ID, but the controller or System A cannot tell the ID stored on System A. Isn’t that magic? A sample run is [here]:
UID: 43
ID1: 929293739471222707
ID2: 21611482313284249
xa: 11
xb: 10e: 65537
N: 509628704099738411389114128951088319
p: 826182604440061657
q: 616847536320538967
RSA Encryption parameters. Public key: [e,N].Cipher1: 458944241885995240133251377203010898
Derived ID2: 21611482313284249And we see the magic, and where ID1 has been transformed into ID2 using RSA encryption alongside homomorphic encryption! The source code in RSA is:
import pyprimes
import sysimport random
import mathdef extended_euclidean_algorithm(a, b):
"""
Returns a three-tuple (gcd, x, y) such that
a * x + b * y == gcd, where gcd is the greatest
common divisor of a and b. This function implements the extended Euclidean
algorithm and runs in O(log b) in the worst case.
"""
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = b, a while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t return old_r, old_s, old_t
def inverse_of(n, p):
"""
Returns the multiplicative inverse of
n modulo p. This function returns an integer m such that
(n * m) % p == 1.
"""
gcd, x, y = extended_euclidean_algorithm(n, p)
assert (n * x + p * y) % p == gcd if gcd != 1:
# Either n is 0, or p is not a prime number.
raise ValueError(
'{} has no multiplicative inverse '
'modulo {}'.format(n, p))
else:
return x % p
def rabinMiller(n):
s = n-1
t = 0
while s&1 == 0:
s = s/2
t +=1
k = 0
while k<128:
a = random.randrange(2,n-1)
#a^s is computationally infeasible. we need a more intelligent approach
#v = (a**s)%n
#python's core math module can do modular exponentiation
v = pow(a,s,n) #where values are (num,exp,mod)
if v != 1:
i=0
while v != (n-1):
if i == t-1:
return False
else:
i = i+1
v = (v**2)%n
k+=2
return Truedef isPrime(n):
#lowPrimes is all primes (sans 2, which is covered by the bitwise and operator)
#under 1000. taking n modulo each lowPrime allows us to remove a huge chunk
#of composite numbers from our potential pool without resorting to Rabin-Miller
lowPrimes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179
,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269
,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367
,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461
,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571
,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661
,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773
,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883
,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
if (n >= 3):
if (n&1 != 0):
for p in lowPrimes:
if (n == p):
return True
if (n % p == 0):
return False
return rabinMiller(n)
return Falsedef generateLargePrime(k):
#k is the desired bit length
r=100*(math.log(k,2)+1) #number of attempts max
r_ = r
while r>0:
#randrange is mersenne twister and is completely deterministic
#unusable for serious crypto purposes
n = random.randrange(2**(k-1),2**(k))
r-=1
if isPrime(n) == True:
return n
return "Failure after "+`r_` + " tries."
import randomval=0
bits=60p= generateLargePrime(bits)
q= generateLargePrime(bits)
n=p*qe=65537PHI=(p-1)*(q-1)d=inverse_of(e,PHI)uid = 11
xa = 23
xb = 7if (len(sys.argv)>1):
uid=int(sys.argv[1])
if (len(sys.argv)>2):
xa=int(sys.argv[2])
if (len(sys.argv)>3):
xb=int(sys.argv[3])id1=pow(uid,xa,n)
id2=pow(uid,xb,n)print "ID1:\t\t",id1print "ID2:\t\t",id2
print "xa:\t\t",xa
print "xb:\t\t",xbprint "\ne:\t\t",e
print "N:\t\t",n
print "p:\t\t",p
print "q:\t\t",qprint "RSA Encryption parameters. Public key: [e,N]."cipher1=pow(id1,e,n)print "\nCipher1:\t",cipher1val=pow(cipher1,xb,n)
val=pow(val,inverse_of(xa,PHI),n)val=pow(val,d,n)
print "Derived ID2:",valOblivious Transfer
Oblivious Transfer methods allow information to be passed from Bob to Alice, and without Bob knowing which of the data element that Alice has selected. In 2007, Jan presented this groundbreaking method [5]:
The actual method is defined in Figure 2 on Page 12 of the paper [5]:
In this case we will 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. The outline coding using the library from the MIRACL library [here] is [here]:
package main
import (
"fmt"
"github.com/miracl/core/go/core"
"github.com/miracl/core/go/core/BN254"
"math/rand"
"time"
"os"
"strconv"
)
func FP12toByte(F *BN254.FP12) []byte {
const MFS int = int(BN254.MODBYTES)
var t [12 * MFS]byte
F.ToBytes(t[:])
return(t[:])
}
func randval() *core.RAND {
s1 := rand.NewSource(time.Now().UnixNano())
r1 := rand.New(s1)
rng := core.NewRAND()
var raw [100]byte
for i := 0; i < 100; i++ {
raw[i] = byte(r1.Intn(255))
}
rng.Seed(100, raw[:])
return rng
}
func main() {
M := []int{17, 29, 35, 47, 20,16,47,48,19,55}
A:=make([]*BN254.ECP2, len(M))
B:=make([]*BN254.FP12, len(M))
sig:=3 // Element to select
argCount := len(os.Args[1:])
if (argCount>0) {
sig,_= strconv.Atoi(os.Args[1])
if (sig>=len(M)) { sig=0; fmt.Printf("Setting search item to zero") }
}
fmt.Printf("\nData %d\n",M)
fmt.Printf("Element to OT %d\n\n",sig)
q := BN254.NewBIGints(BN254.CURVE_Order)
// r:=BN254.Randomnum(q,randval())
s:=BN254.Randomnum(q,randval())
x:=BN254.Randomnum(q,randval())
P1 := BN254.ECP_generator()
P2 := BN254.ECP2_generator()
// g:=BN254.G2mul(P2,r)
h:=BN254.G1mul(P1,s)
for i := 0; i < len(M); i++ {
ival:=BN254.NewBIGint(i)
e := BN254.Modadd(x,ival,q)
e.Invmodp(q)
A[i]=BN254.G2mul(P2,e)
}
for i := 0; i < len(M); i++ {
Z := BN254.Ate(A[i],h); Z=BN254.Fexp(Z)
Z.Mul(BN254.NewFP12int(M[i]))
B[i]=Z
fmt.Printf("Pairing %d e(Ai,h):\t%x\n",i,FP12toByte(B[i])[:20])
}
//// Now send Ai, Bi to selector and choose one
v:=BN254.Randomnum(q,randval())
V:=BN254.G2mul(A[sig],v)
fmt.Printf("\nSending v %s\n",V.ToString())
/// Sender sends back W
W:=BN254.Ate(V,h); W=BN254.Fexp(W)
// Selector now gets W and recovers the message:
fmt.Printf("\nPairing 1 e(Ai,h):\t%x\n",FP12toByte(B[sig])[:20])
v.Invmodp(q)
W=W.Pow(v)
fmt.Printf("\nPairing 2 e(Ai,h):\t%x\n",FP12toByte(W)[:20])
W.Inverse()
Message:=BN254.NewFP12copy(B[sig])
Message.Mul(W)
fmt.Printf("\nResult:\t%x\n",FP12toByte(Message)[:20])
for i := 0; i <= 50; i++ {
z:=BN254.NewFP12int(i)
if Message.Equals(z) { fmt.Printf("Success! Element %d is %d",sig,i) }
}
}A sample run is [here]:
Data [17 29 35 47 20 16 47 48 19 55]
Element to OT 7
Pairing 0 e(Ai,h): 1d70bdcd29f699bbc4bca4e01dfb87c0f0e023de
Pairing 1 e(Ai,h): 118f825d49c074f94b86ebdb2b97ef6b952764ea
Pairing 2 e(Ai,h): 082235a74ad3241197f6886db466e2f199d4070b
Pairing 3 e(Ai,h): 02a2b5e2e73fceed0a4495d18008c95e83b9f645
Pairing 4 e(Ai,h): 105e83504d71ea4e4009380cd4650fefe2064903
Pairing 5 e(Ai,h): 110546d09d8ba4d021561496ca95a31d75b9a965
Pairing 6 e(Ai,h): 0d8850515128394eae26b1a17885479e4d0bace9
Pairing 7 e(Ai,h): 0ba7bcc62463a3de61e21d78d95e1331dcee9d0f
Pairing 8 e(Ai,h): 13bbaf46f1f1efc8ae963d4b4ae45fcc966c69ad
Pairing 9 e(Ai,h): 0c04b9e3e1a11be387324d1bde388d49a3519fa6
Sending v ([20c36bd146a4fa2896b7fff29f537183e118b6e07de6ade081b5e825c30fd6df,0836dfc5c53e60b0a773a69afc7e84776df8b201b7a9d0133c6938847d3d0337],[085a922280bcbd9d692fc3789d11a0a076081e097a84720d2148c367546debdf,14aab968fab91ab135f099c553a211a80be4c96450ff6e4b6500d2e797e69985])
B value: 0ba7bcc62463a3de61e21d78d95e1331dcee9d0f
W value: 183a5a2d94c2136b14f67d552f31f5c11dff9df0
Result (B/W^{1/v}): 0000000000000000000000000000000000000000
Success! Element 7 is 48Jan and Hyperledger
IBM has supported the development of the Hyperledger Fabric permissioned ledger service. Overall, we can see Jan’s input in many areas of privacy within Hyperledger, including the usage of Idemix:
Idemix is a cryptographic protocol suite, which provides strong authentication as well as privacy-preserving features…hyperledger-fabric.readthedocs.io
Conclusions
I have scratched the surface of Jan’s work, but, if you have time, please go and read some of his papers. Perhaps Jan’s current job title of “CTO and Cryptographer” gives away his underlying passion, and where he is possibly just as proud of being a Cryptographer than as a CTO.
References
[1] 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.
[2] Camenisch, J., Drijvers, M., Hanke, T., Pignolet, Y. A., Shoup, V., & Williams, D. (2022, July). Internet computer consensus. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (pp. 81–91).
[3] Camenisch, J., & Lehmann, A. (2015, October). (Un) linkable pseudonyms for governmental databases. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (pp. 1467–1479).
[4] Camenisch, J., & Lehmann, A. (2017, April). Privacy-preserving user-auditable pseudonym systems. In 2017 IEEE European Symposium on Security and Privacy (EuroS&P) (pp. 269–284). IEEE.
[5] 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.