Question 1.
(a) The scheme is (5,3), so n = 5 and ( = 3. The polynomial will be quadratic. a\ = g394097 mod 101021 = 12117, o2 = 5394097 mod 101021 = 30858 and S = 394097. The polynomial is a(x} = aYx + a,2x2 + S = 12117a; + 30858a;2 + 394097 mod 567997.
Using the polynomial we can calculate shares for each of the five users: (1,437072), (2,541763), (3,140173), (4,368296) and (5,90138).
(b) The three shares create a system of three equations with three variables:
a-i + a2 + S = 438827,
(1)
3ai +9a2 + S = 133864.
2oi+4a2 + S = 273042,
(2)
(3)
After solving the system we get S = 63222 mod 567997.
Question 2.
(a) ai = 113 a-i = 169
v = 83 mod 311
Verification is done by: 7 —a^ * a2^ * vr mod p
1) (20. 27,(18. 29));
7 =11318 * 16929 * 8327 mod 311 - 15 * 250 * 243 - 20 mod 311 -> correct transcript
2) (20, 4,(18, 26)):
7 =11318 * 16929 * 834 mod 311 = 15 * 195 * 32 = 300 f 20 -> not correct, transcript
3) (24, 4,(15, 26)):
7 =11315 * 16926 * 834 mod 311 = 250 * 195 * 32 = 24 -> correct transcript
4) (24, 27,(15, 29)):
-: =11315 * 16929 * 8327 mod 311     250 * 2511 * 243     120 f 24-   mil correct transcript (b) yi = k\ + ai * r mod q V2 = fa + oq * r mod q
I took two correct transcripts: (20, 27,(18, 29)) and (24, 4,(15, 26)) and decided to try both possibilities:
1) Transcript (20. 27,(18. 29)) was first and (24, 4,(15, 26)) was second:
I got these 4 equations by using (fci)a — 3 s* (fci)i + 4 mod 31 and (£2)2 — 5 * (£2)1 + 3 mod 31:
18 = fcL - 01 * 27 mod 31
15 = 3 * fa + 4 + 01 * 4 mod 31 29 = fa - a-2 * 27 mod 31 26 = 5 * fa + 3 + a2 * 4 mod 31 From the first two:
fci = 18 - 27 * 01 mod 31 -> 15 = 3 * (18 - 27*ai) + 4 + 4 * m mod 31
II = -81 * «1 + 4 * o,i - 54 mod 31 11 = 16 * 01 + 23 mod 31
19 = 16 * O] mod 31
01 = 19 * 16"1 mod 31 = 19 * 2 mod 31 = 7 From the second two:
fa ~ 29 - 27 * o2 mod 31 -> 26 - 5 * (29 - 27 * a2) I 3 I 4 * a2 mod 31
2 = 24 * a2 mod 31
02 = 2 * 24-1 mod 31 = 2 * 22 mod 31 = 13
2) Transcript (24, 4,(15, 26)) was first and (20, 27,(18, 29)) was second: Hy similar computations I got:
15 = fci + 4 * ai mod 31
18 - 3 * fa I 4 I 27 * 01 mod 31
18 = 3 * (15 - 4 * ai) + 4 - 27 * 0,1 mod 31 -> a± = 0
26 = fa + 4 * a2 mod 31
29 - 5 * fca + 3 + 27 * a2 mod 31
29 = 5 * (26 - 4 * a2) + 3 - 27 * a2 mod 31 -> a2 = 25
But I didn't even need to control the second case, because I can verify that 01 = 7 and a2 = 13 is right solution from:
v = ajal * a2a2 mod p - 113"7 * 169"13 mod 311 = 7"1 * 91"' mod 311 - 89 * 270 - 83 -> so these recovered keys 01, a2 are correct (the inverses can be computed by ext.eucl.algorithm).
Question 3.
Lets denote treshold as T, F is field marshal, G is general, C is colonel and ,1/ is major.
From assignment we know, that: F>T
3G > T -¥ G > |
2G + 5C>T->2*f+5C>r->C> g
G + 7C + 15M >T->| + 7*-^ + 15M >T->- M>^
Now for condition that any number of Colonels or Majors cannot launch the
missile without General it must holds:
50 * C + 100 * M < T
but we get that:
50 * ^ + 100 * ^ < T
Which is obviously not true. Thus there is no single instance of a threshold secret sharing scheme that would satisfy all conditions,
Question 4.
(a)
No. Because when we take second and third column combination (2,2) appears 3 times and repetition count is 1.
('■') i.
OA(2,7,2)
This array exists and here is an example:
(I	0	II	0	0	0	0
0	0	(1	1	1	1	1
0	1	1	0	0	1	1
0	1	1	1	1	0	0
1	0	1	0	1	0	1
1	0	1	1	0	1	0
1	1	(1	1)	1	1	0
]	1	0	J	i)	0	1
ii.
OA(2,8,2)
Lets assume that such orthogonal array exists. Then it must hold
But in our case
2 > -^-
and 2<|
Thus there is no such orthogonal array.
Question 5.
(a) We can see that the verification will succeed for any 60:
Alice sends: j : r2(*Y = (r.s6)
Alice sends: y = rsh   mod n
In case Bob sends the challenge 6 = 2 to Alice, she calculates y = rs2 mod n and sends it to Bob. Since v = S mod n, Alice opens her commitment by revealing r, as Bob can calculate r = yv~l. However, because of the assumption that it's computationally infeasible for Bob to find y/v mod n, s remains secret.
(b) If Eve can guess the challenge, she can calculate her commitment for 6 = 0,1 as described in the slides, either by sending x = r2 for 6 = 0 or x = r2v~l for 6=1, then she responds with y = r to Bob's challenge.
1Of course Bob docs not. need to know r, he just needs to know x = r2, which Alice sends first as her commitment.
In case the challenge is 6 = 2, she sends her commitment as x = r2 and as a response she sends y = rv, since sb = s2 = v mod n. Here is how Bob correctly verifies her response:
Eve sends commitment: x = r2   mod n Bob sends challenge: 6 = 2 Eve sends response: y = rs2 = rv   mod n Bob verifies: xvh = r2v2 = (rv)2 = y2   mod n
As the part (a) suggests, in this case she can also fool Bob if he sends the challenge b — 0, as she can just send y = r as a response, which Bob verifies as y2 = xv = r2.
Actually we can generalize this method for all possible values of b. Eve just needs to correctly guess if the challenge will be odd or even. Then she calculates x = r2 for even b or x = r2v_1. After Bob responds with his challenge, she calculates her response y = rvz, x being the number of even / odd numbers between 0 and 6. So in case of even numbers, x = |, in case of odd numbers x =
For example, this is how it works for 6 = 3:
3- 1
2
Eve sends commitment: x = r2v~l   mod n
Bob sends challenge: 6 = 3 Eve sends response: y = rrf = rv    mod n Bob verifies: xif = r2v2 = (rv)2 = y2   mod n
For 6 = 5, her response would be y = rv2 and the verification would be xv5 = r2v 1v5 =
r2v4 = y2.
This implies that the probability of fooling Bob is still 2-' for t rounds, therefore Alice and Bob did not improve the security of this protocol.
Question 6.
Let A be an arbitrarily chosen t — (g,n, 1) orthogonal array. Using ql rows of A as codewords of our new code, we construct code C. We prove that code C is a q-ary maximum distance separable |n.k]-code as follows. Suppose that d(C) < n — t (and therefore that C is not a maximum distance separable code with aforementioned properties). Then there exist two codewords x.y € C such that they match on at least t columns. Within these columns the rows of x,y are the same which is a contradiction since we have constructed the code from an orthogonal array with A = 1.
Now we show that the other side of the equivalence holds. Let C be a q-ary maximum distance separable |n,k]-code. M = q"-^1, "We construct aMxn array A by taking the codewords of C to be the rows of A. Consider the restriction of A to any subset of n - d + 1 columns. The qn~d+^ (n — d + I)-tuplcs obtained from the rows of A must all be different (otherwise two codewords would be less than d bits apart). Since there are qn~d+l different (n — d + l)-tuples, every possible (n — d+l)-tuple occurs in exactly one row of A in this restriction, Since this holds for all the possible subsets of n — d + 1 columns of A, we have shown that A is a (n — d + 1) — (q, n, t) orthogonal array.