Krüptograafilised protokollid 2021/22 sügis

Homework 3: Garbled Circuits

First part: Do the previous year's homework. The online AES calculator that this document references seems to be nicely online, still.

Second part: Evaluate the same circuit again. However, this time it has been garbled as follows:

• Point-and-permute, garbled row reduction, and free XOR-s are in use. The comment about correct keys always beginning with 00000000₁₆ no longer applies. The comment about encodings of the output bits is also invalid. You can find a XOR calculator at http://xor.pw/.
• For point-and-permute, the order of ciphertexts in the garblings of gates is (0,0), (0,1), (1,0), (1,1), where these pairs are the lsb-s of the "left" and "right" incoming key, respectively.
• . For garbled row reduction, we have removed the row corresponding to the key lsb-s 0 and 0. The removed ciphertext is 00...0.

The keys corresponding to the inputs are the following:

• x0: 1b8db2b95fbe9ce389c240fd51b0eb64
• x1: 626956b242435d17cadb12c56ab245f8
• x2: 645ade3bac261faab3f94626bebb012e
• x3: 950accf8e5afd06a366485a98d384400

Gate AND0 is encoded with the ciphertexts

1. aae385dbc85f502d9cea6928a4927ad4
2. 9e990e5195e4770b2daf16bd271c5138
3. a5cd19bc6cef841302b3e0cd134d1f8a

Gate AND1 is encoded with the ciphertexts

1. b2e599a0a9bd60fb5353767da66523fa
2. 7c277c503d2d1d664706912d828f8ba3
3. d8935493edb8e41afdedb042cd51abae

Gate AND2 is encoded with the ciphertexts

1. adcbb7cee98f9a01a42d38ac580bd97c
2. 2627585840d5cbd83b888d06fa951814
3. b35d67f44a3b35956d93d0cbe41f17c0

An output gate is encoded with two bits b0 and b1. The output corresponding to that gate is obtained by decrypting the ciphertext 00...0₁₆ with the obtained key, taking the lsb of the result, and then XOR-ing it with either b0 or b1, where the index of the bit b is equal to the lsb of the key.

Gate y0, y1, and y2 are encoded with bits (0,1), (0,0), and (0,0), respectively.

Third part: Garble that circuit. Use point-and-permute, garbled row reduction, free XORs, and half-gates. Let the starting values be the following:

• Δ = c647279b7d184a131dd4d15f2a953415
• k0^0 = 2e3d85a05f9d762cf0a4e9e0774717d2
• k1^0 = 1eb07b4500ab0a3fce720c5199e04c13
• k2^0 = 58fd680c59202087e394e6b5c15779c4
• k3^0 = 375c13df8add097a96dd9ccd74449d5d

(everything else should be determined by these values).

In your solution, please explain in a quite detailed manner, what you are doing.

Additional terms:

1. The homework is individual. You are expected to do your own thinking.
2. The solution can be presented in any text format.
3. If you will be late, please alert the lecturer in advance.

Deadline: November 15th, 2021, 23:59 EEST.

Delivery:: upload through the course website (see below)