From Garbled Circuits to Millionare Problems … Meet Andrew Chi-Chih Yao

From Garbled Circuits to Millionaire Problems … Meet Andrew Chi-Chih Yao

I had to smile when I read more about Andrew C Yao …

“He asks them to write exercises using LaTex, a software package especially designed for writing papers.”

And I smile because my own students are currently writing up their coursework on cryptography, and I’ve asked them to do it in LaTeX, too. Education should be about excelling and pushing yourself to learn new things, and there are few things better for sharing research than LaTeX.

Andrew Chi-Chih Yao was born in 1946, and is currently a Dean at Tsignhua University. He actually did two PhDs. The first was in Physics at Harvard University and completed in 1972, and then the second was completed in 1975 in Computer Science at the University of Illinois. After this, he worked at Stanford University and then the University of California, Berkeley. One of his first major contributions was the Yao test [3] and where a sequence of words passes his test if they cannot be distinguished from random generation.

Yao’s Millionaire Problem

Within Yao’s paper in 1982 [2], he outlined a problem of identifying a way for two millionaires to find out which of them had the most money, and where there did not trust anyone to determine this, and for them not to reveal how much money they had:

It was the start of multiparty computation (MPC), and zero-knowledge proofs. In Millionaire’s Problem, we can determine which of two millionaires has the most money, without them giving away their money. The method involves us using RSA encryption. For this I’ve used Example 4 from here:

e=79
d=1019
N=3337

and select a prime number:

p=631

We define I as Bob’s millions, and J as Alice’s millions:

J =4
I =5

Next, we select a random number U:

U=randint(0,2000)

And compute the C value (which is the RSA encryption process):

Now Alice calculates:

C - J + 1

She shares this with Bob, and Bob calculates 10 values:

Bob then takes these values, and if for the i-th value, and the rest, he will one he will add one onto the value. These are then sent back to Alice.

Alice now computes:

If the j-th value is the same as G, Alice has more money or the same, else Bob has more money.

Garbled Circuits

In 1986, Yao invented the concept of garbled (or scrambled) circuits, and which was a way to pass information in a private way, and still process it [1]:

So let’s say that Bob and Alice just don’t trust each other. They have had a bad time, but they still want to make some decisions and don’t even trust their lawyer anymore. They then agree on a secure protocol, where they must either both agree to something (A & B) or one of them just has to agree (A or B), or when just one agrees and the other does not agree (A xor B). This is a simple logic function.

Let’s say they agree to both agree on something, so we have an AND function (A & B). We now create a scrambled AND gate. For this we get:

A B Z
0 0 0
0 1 0
1 0 0
1 1 1

Now Bob created four encryption keys K(a=0), K(a=1), K(b=0) and K(b=1). Now he will go ahead and encrypt the four possible outputs (in this case “0”, “0”, “0”, and “1”), using the two encryption keys associated with the bits. For example the output:

A=0, B=0, Z=0

will encrypt the output (“0), with the keys of K(a=0) and K(b=0).

In Python here is the code [here]:

Bob then passes the cipher_text values (cipher_text00 … cipher_text11) to Alice, and provides the key for his input. If he says YES, then he passes keyX_1, otherwise, he will pass keyX_0.

Now Alice receives the four values and Bob’s key. Now she uses obviously transfer to gain the key for her answer. If she says YES, we obtain the key for keyY_1, without Bob actually knowing that he says YES. If she says NO, she gets keyY_0.

In the end, she will have two keys and she tries all the ciphers:

and the only one she can open is the one that matches Bob and Alice’s decision.

To illustrate, let’s say that Bob and Alice say “No”, so their inputs to the AND function will be 0 and 0. Now Bob encrypts the four outputs with the four keys, but the only ones which will open up the outputs will be the keys for a zero input for A and for B. Bob passes his key, without revealing his input as K(a=0), and Alice receives her key through an oblivious transfer:

The demo is here.

Conclusions

Andrew Chi-Chih Yao is a world-class researcher and was a naturalized US citizen, but in 2014, he decided to move back to China in order to strengthen research in his country of birth:

“If we follow the right path, Tsinghua’s efforts in computer science will lead to great scientific breakthroughs in the coming several years. And if we continue to make a strong effort, Tsinghua University’s Computer Science curriculum will become a world-class discipline in the future”

References

[1] Yao, A. C. C. (1986, October). How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) (pp. 162–167). IEEE.

[2] Yao, A. C. (1982, November). Protocols for secure computations. In 23rd annual symposium on foundations of computer science (sfcs 1982) (pp. 160–164). IEEE.

[3] Yao, A. C. (1982, November). Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) (pp. 80–91). IEEE.