Yael Tauman Kalai — Cryptographic Excellence

Yael Tauman Kalai — Cryptographic Excellence

Well done to Yael Tauman Kalai’s award of the 2022 ACM Prize in Computing. She has worked with some of the greats in cryptography, including with Ron Rivest, Shafi Goldwasser, and Adi Shamir. Her most cited paper relates to “How To Share A Secret”:

How to share a secret

A ring signature is a digital signature that is created by a member of a group that each has its own keys. With this, it will not be possible to determine the person in the group who has created the signature. They were initially created by Ron Rivest, Adi Shamir, and Yael Tauman in 2001 [1]. We will generate a number of public keys, but only one key pair for the signer. The signer users the public keys of the others in the ring, but apply their private key, in order to sign for all the entities in the ring. No one will be able to tell which of the private keys has been used.

And so there has been a leak of information at the White House. Donald Trump calls in his Cyber Security leads, and tells them, “I know one of you leaked the information, but I can’t tell which one”. How can Donald tell that one of his chiefs leaked the information, but not know which one? Well, this can be achieved with a ring signature, and which provides anonymity, unforgivably, and collusion resistance.

A ring signature is a digital signature that is created by a member of a group that each has their own keys. It is then not possible to determine the person in the group who has created the signature. The method was initially created by Ron Rivest, Adi Shamir, and Yael Tauman in 2001, and who proposed the White House leak dilemma.

In a ring signature, we define a group of entities who each have public/private key pairs of (P1, S1), (P2, S2), …, (Pn, Sn). If we want entity i to sign a message (message), they use their own secret key (si) but the public keys of the others in the group (m,si,P1…Pn). It should then be possible to check the validity of the group by knowing the public key of the group, but not possible to determine a valid signature if there is no knowledge of the private keys within the group.

So let’s say that Trent, Bob, Eve and Alice are in a group, and they each have their own public key and secret key. Bob now wants to sign a message from the group. He initially generates a random value v, and then generates random values (si) for each of the other participants, but takes his own key (si and uses it to determine a different secret key, and which reverse of the encryption function. He next takes the message and takes a hash of it, and thus creates a key (k). This key will be used with symmetric encryption to encrypt each of the elements of the ring (Ek, and each element of the ring uses an EX-OR function from the previous element (Figure 1). Each of the random values for the other participants are then encrypted with the public key of the given participant. Bob then computes the value of ys in order to create the ring (the result of the ring must equal v). He will then inverse this value to produce the equivalent private key (xs). Bob now releases the overall signature, and the random x values, along with the computed secret key. To check the signature, the receiver just computes the ring, and checks that the result matches the sent signature.

The basic method is:

We will end up with the signature (v=Ek(u)), and which completes the ring.

The following is an outline presentation [slides]:

The following defines some code [taken from here][here]:

package main
import (
    "strconv"
    "os"
    "fmt"
    "encoding/hex"

    "go.dedis.ch/kyber/v3"
    "go.dedis.ch/kyber/v3/group/edwards25519"
    "go.dedis.ch/kyber/v3/sign/anon"
    
)
func main() {
    
    m:="Hello"
    n:=3

    argCount := len(os.Args[1:])
        if (argCount>0) {m= string(os.Args[1])}
        if (argCount>1) {n,_= strconv.Atoi(os.Args[2])}
    M := []byte(m) 

    suite := edwards25519.NewBlakeSHA256Ed25519()
    // Create an anonymity set of random "public keys"
    X := make([]kyber.Point, n)
    for i := range X { // pick random points
        X[i] = suite.Point().Pick(suite.RandomStream())
        
    }
    fmt.Printf("Public keys: %s\n\n",X)
    // Make just one of them an actual public/private keypair (X[mine],x)
    mine := 1                                      // only the signer knows this
    x := suite.Scalar().Pick(suite.RandomStream()) // create a private key x
    X[mine] = suite.Point().Mul(x, nil)            // corresponding public key X
    // Generate the signature
    fmt.Printf("Private key of signer: %s\n\n",x)
    fmt.Printf("Public key of signer: %s\n\n",X[1])

    sig := anon.Sign(suite, M, anon.Set(X), nil, mine, x)
    fmt.Print("Signature:\n" + hex.Dump(sig))

    // Verify the signature against the correct message
    tag, _ := anon.Verify(suite, M, anon.Set(X), nil, sig)
    if tag == nil || len(tag) != 0 {
        panic("Verify returned wrong tag")
    }
    fmt.Printf("\n\nSignature has been verified")

}

A sample run is [here]:

Message: Hello
Public keys: [81753b549e40804617759c9cba6878b494b8cf1d82651c504040d52acc2eb694 c45ae8f669e313183cbc7bbd6369e9423aa12c20d30da38deba7fe8da14c408a 94d45114ef11eeba37c1c9e37bd375f8f3af7b690cd7de54b9ab20e876c7e288 5dd0b5464b971d3776941a9f0df9330f1bb54423e3d12fb41b6175bc1549ba10 789c14943c31a0d56c65c75b0e0fdcc5dc7242b3a750802f1cbbcd711a3a9bce]
Private key of signer: 9c7ecf02d2f0b18c470e2f0e6a0cc7b3f966b87757bab56ca3fbfdd7116ac10e
Public key of signer: 01cad592c6ca5a9b397dbc15662a297a274df1f79da5dd336b9dea46a83f7399
Signature:
00000000  4c e1 3a b6 31 2d cb 79  69 91 1a 05 2a f8 46 0b  |L.:.1-.yi...*.F.|
00000010  a5 b2 ea cb 5e 21 ff 23  d4 6b 03 f5 07 e4 58 0d  |....^!.#.k....X.|
00000020  82 a1 49 c5 e8 f0 0a 3d  00 ec 64 e0 1a 1a 36 91  |..I....=..d...6.|
00000030  3d 5e 53 9e 81 66 b4 ba  54 cb bd c9 00 73 b3 04  |=^S..f..T....s..|
00000040  1d a0 d8 5f a3 33 78 08  cf c5 57 3f 69 f4 49 48  |..._.3x...W?i.IH|
00000050  47 aa d3 7e ae f3 d2 66  9e b0 37 80 c7 34 f5 0a  |G..~...f..7..4..|
00000060  76 11 9b 2a 79 1d e0 5e  2d 21 c1 26 ec cc 18 a1  |v..*y..^-!.&....|
00000070  c0 27 f1 96 0a eb 40 d2  a3 c1 11 5e 6f 08 da 02  |.'....@....^o...|
00000080  bd 86 53 73 2c 94 b6 04  9a 05 0a 86 1f 2c d1 1e  |..Ss,........,..|
00000090  ca f4 d8 60 b3 4e 36 ed  74 fd d4 32 23 06 b1 0a  |...`.N6.t..2#...|
000000a0  11 b5 0b 4c f2 e0 f4 45  d9 e9 a9 3c 26 c2 78 c5  |...L...E...-&.x.| 
000000b0  12 ee d7 5b 2a 65 65 c9 bf b1 31 2a eb 34 b8 04   |...[*ee...1*.4..|
Signature has been verified

Offline/online signatures

In Nov 1988, Micali, Goldreich and Evan submitted a patent that allows for a pre-computation element so that a message could be signed without the requirement to be online. It involved two main stages. The first was a precomputed value that was independent of the message (s1), and the second for a one-time public key (s2) This page uses an offline/online signature scheme, based on the paper: “An online/offline signature scheme based on the strong rsa assumption” [2]. Within this method, Alice has a public and a private key. Whilst she is offline, she can create a number of offline key pairs, and which she can use to sign a message when she is online.

In this method, we generate two prime numbers p and q and which are:

The coding is [here]:

import random
import hashlib
import math
from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes
import sys
import sympy
primebits=32
msg="hello"

if (len(sys.argv)>1):
  primebits=int(sys.argv[1])
if (len(sys.argv)>2):
  msg=(sys.argv[2])
if primebits>48: primebits=48

while (True): 
  p_1 = getPrime(primebits, randfunc=get_random_bytes)
  p=2*p_1+1
  if (sympy.isprime(p)): break;
while (True): 
  q_1= getPrime(primebits, randfunc=get_random_bytes)
  q=2*q_1+1
  if (sympy.isprime(q)): break;

g=3
n=p*q
s=random.randint(0,2**32)
X1 = pow(g,s,n)

print (f"Message: {msg}")
print (f"\np={p}, q={q}, n={n}")
print (f"p'={p_1}, q'={q_1}")
print ("\nOffline pair:")
print (f"s'={s}, X={X1}")

a = hashlib.md5(msg.encode())
b = a.hexdigest()
H=int(b, 16)
r = (s*H) % (p_1*q_1)
print (f"X={X1}, r={r}")

res1= pow(g,r,n)
res2 = pow(X1,H,n)
print (f"\ng^r mod n={res1}\nX^H(m) = {res2}")
if (res1==res2): print("Signature proven")
res3=sympy.gcd(H,r)
print (f"\n\nRes3={res3}")
if (res3<pow(2,int(2*math.sqrt(128)),n)): print ("Agreement")

A sample run is [here]:

Message: Hello
p=22005907214787629663, q=28302012508433361623, n=622811461252343452952085601595080623049
p'=11002953607393814831, q'=14151006254216680811
Offline pair:
s'=2479550251, X=477042813831727728995906390188334982865
X=477042813831727728995906390188334982865, r=110311308473964283357072898432008088810
g^r mod n=549994792011473692396468826533301533213
X^H(m) = 549994792011473692396468826533301533213
Signature proven

Res3=1
Agreement

The method presented by Even, Goldreich and Micali was not very practical, and so Adi Shamir and Yael Tauman improve this method in 2001 [3] . For this they introduced a trapdoor hash function to create a hash-sign-switch. This allows any signature scheme to work in an off-line/on-line mode.

Conclusions

Over the past two decades, Yael Tauman Kalai has continued to lead in cryptographic research, including in areas around delegated computing and homomorphic encryption.

References

[1] Rivest, R. L., Shamir, A., & Tauman, Y. (2001, December). How to leak a secret. In International conference on the theory and application of cryptology and information security (pp. 552–565). Springer, Berlin, Heidelberg.

[2] Yu, P., & Tate, S. R. (2007, May). An online/offline signature scheme based on the strong rsa assumption. In 21st International Conference on Advanced Information Networking and Applications Workshops (AINAW’07) (Vol. 1, pp. 601–606). IEEE [here].

[3] Shamir, A., & Tauman, Y. (2001). Improved online/offline signature schemes. In Advances in Cryptology — CRYPTO 2001: 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19–23, 2001 Proceedings 21 (pp. 355–367). Springer Berlin Heidelberg.