Question 1.
Coin-flipping protocol for p=43, q=71, x=123.
(i) Alice chooses primes p = 43, g = 71, keeps them secret and sends Bob n = p * q = 3053.
(ii) Bob chooses random x £ {1,..., ^: x=123. Now he computes y = x2 mod n = 1232 = 2917 mod 3053 and sends y to Alice and tells her to guess x - if she guesses the correct x, she will win.
(iii) Alice now computes the square roots with the knowledge of p and q. We can use the property of the two primes, that actually are Blum primes (equal 3 modulo 4).
x = ±y^   mod p
t = ±y *    mod q
x = ±2917^-   mod 43 = ±6   mod 43
x = ±2917^   mod 71 = ±19   mod 71
Now we can use Chinese remainder theorem to compute the four square roots modulo p. The inverse number modulo p can be computed using Extended Euclidean algorithm.
mi = 43, mj = 71, M = mi *
Mi = M/mi = 71, Mz = M/ma = 43
JV, = Aff1   mod ml = 71_1 = 20   mod 43
Ni = M2_1   mod m2 = 43_1 = 38   mod 71
t= ±G* 71 * 20 ± 19*43 *38   mod 3053
So the four square roots modulo n are 2930, 1898, 123, 1155. Prom these, Alice chooses randomly one of the two smallest (as the two largest are just n minus one of the two lowest x) and tells Bob which one she chose, for example by saying the position and value of the leftmost bit, on which the two smallest x differ.
(iv) Bob tells Alice if she is right or wrong and therefore the result of the coin-flipping. If there are some doubts, Alice reveals p and q and Bob reveals x.
Question 2.
The protocol starts with Alice choosing a random input x £ {0,1}" —5-{0,1 }n. Alice then computes f(x) and sends it to Bob. Bob now guesses the parity of Alice's input and tells Alice. If he guesses correctly. Bob wins, otherwise Alice wins. Bob can verify the result by making Alice send him the input x.
This protocol is secure. Since the function is bijective, there's no other y / x such that f(x) = f(y) and thus Alice commits to her x by sending f(x) and cannot change her choice later to cheat. On the other hand, since no information can be gained about the input of function / from its input. Bob has no way of computing the parity of x from f{x).
Question 3.
(a) Alice can easily reveals r and x. Bob checks if grh? mod p is equal to the message, which he received in the commitment phase.
(b) Binding is computational. Suppose it. is computationally feasible to compute r, r* E Zp, such that commit (rpc) = commit (r1, X1). That means that
gThx = g^h?   mod p
sV =$V niodp g*+** = gT'+^   mod p
r + kx = t + kx'   mod q
kx — kx' =t — r   mod q
k(x — x1) = t* —t   mod q
r' -t k =-- mod q
X — X
So to be able to open the commitment in both ways is as hard as. calculating the discrete logarithm problem for h with basis g E 1^>-
Hiding is information theoretic. It can be simply seen by the fact that the distribution grh:z is independent of X, so gT and grh are statistically indistinguishable, because the value r is random value.
(c) It doesn't help Bob. Knowledge of k doesn't help him. For every x' there exists a unique value r1 such that
r = k(x — x ) + t   mod q
Without further knowledge of r or x, every pair (rxT) that satisfies the commitment is equally likely So if Bob only knows k he cannot deduce any information from the commitment.
(d) She can cheat.  Let's assume that she commits with grhx mod p.  Then she can cheat by calculating rT for any x' and revealing (r\ x') instead of (r, x).
Question 4.
Alice calculates all g(x, yi)yg(x7 ^2),... ,g(xty\y\), expresses them in binary arid inputs g(x,i) as the i-th input into the 1-out-of-k OST protocol. Bob upon inputing y learns g{x,y) and communicates it to Alice. Because OST protocol does not Teveal x to Bob, all he can learn about x is can be deduced from g(x, y). Reversely, since OST protocol does not reveal anything about Bob's choice, all Alice learns about y can be deduced from g(x,y). This is therefore an instance of a secure function evaluation for arbitrery function g.
Question 5,
We will provide a physical (non-cryptographic) wto-knowledge protocol for killer sudoku, which combines element of sudoku and kakuro, Jioth of them have rather simple /,ero-knowk>dge protocols, no we will just, combine them, We need a rather large amount of dichromatic cards (e.g. red and black) and envelops.
If envelope represents el number k, (hen it- has inside k red cards and !> k blaek cards Black raid are there so I he envelopes appear indistinguishable,
St hip:
9x9 grid: Kach cell lias an envelojie corresponding to I lie solution of I lie cell.
Cages: Each cage needs to have assigned a set of envelopes representing the missing (not. in the
solution) numbers.
I'lnliiinl:
(i) To verify row, column or nonet (3 x !i grid). Peggy lakes the I) envelopes from the si incline based on Victor's choice, shullles I hem in a way I hey cannol be tampered with [I his may require a misled iird party or other mechanisms ensuring honesty or we']] jusl assume an almighty abstract shulJle functionality exists), Shullled envelopes are given to Victor,
{ii) Victor ojiens each envelope and verifies that all !) envelopes contain numbers from I to 9.
(iii) To verify a cage (unique numbers) of Victor's choice, Peggy 1 akes I he envelopes from the given cage and also envelops assigned 1o the cage with missing numbers. Envelopes are s]milled and given to Victor,
(iv) Victor opens each envelope and verifies thai all !) envelopes contain numbers from 1 lull.
(v) To verify a cage (sum) of Victor's choice. Peggv lakes 1he envelopes from the given cage, Envelopes are opened face down and card are s] mi lied and given lo Vji lor.
(vi) Victor 1 hen verifies thai I he number of red cards corresponds lo the sum of the cage.
After ii rounds Victor should have enough statistical evidence, that Peggy indeed knows the solution,
Question 6
Under the assumption that there exists a statistically binding mid coinputalionalhj lading hit commitment scheme, there exists a zero-hiowiedgc proof for any NP language (Gvldreich, Micuii, Wigder-stm, 19'Ji).
Hamilronian parh is also known to ho an NP-compWf1 problrm, therefore it. has a zrro-knowledge protocol to verify the solution.
Question f.
Let's assume that we have identical container for each grade. We arrange them in a line, and write labels with grades in front of each container, one for each container, 1 pur a folded slip of paper saying Yes in the container of the grade, which I received. I put also folded slip of paper saying No in the other containers, that represent the other grades. My colleague does the same. Then we remove the labels, and shuffle the containers at random. Then wc look inside the containers to see if one of them contains two slips saying Yes. Inspiration is from Solution 10: click here.
Question 8.
There is a message hidden in a microdot in the colon following "Lewis Carroll" with a text steganographia in Greek letters aTe-yai/ojpafiia.