BU CAS CS 538.
Discussion 1 Solution Logistics. TA:
Office hour: Friday 2:30-4pm at CCDS 10th floor lounge (right by Ran Canetti’s office 1041) Definition 1. A group is a set S and an operation # with the following properties:
• Closeness: ∀a,b ∈ S, a#b ∈ S
Copyright By PowCoder代写 加微信 powcoder
• Associativity: ∀a, b, c ∈ S, (a#b)#c = a#(b#c) • Identity: ∃I ∈ S s.t.∀a ∈ S, a#I = I#a = a
• Inverse: ∀a∈S,∃b∈S,s.t. a#b=b#a=I
Definition 2. The order of an element in group ⟨S,#⟩ (i.e. a group with set S and operation #) is defined as the minimum i, s.t. ai = I, where I is the identity element of the group. If the order of a is equal to |S|, a is a generator of the group.
Definition 3. The multiplicative group modulo n, Z∗n, is the group formed by integers coprime to n from the set {1, 2, …, n − 1} under multiplication modulo n.
When p is a prime. The multiplicative group modulo p is Z∗p := {1, 2, …, p − 1}.
Definition 4. The Discrete Log Problem: given a large prime p and a,b ∈ Z∗p, find i s.t. ai = b mod p .
Problem 1.
(a) Show an example of a finite group that does not have a generator.
(b) Find the order of all the elements in Z∗11 except 1. How many subgroups are there? Which elements are generators?
(c) Is there any group in which discrete log is easy?
(a) Z∗8 = {1,3,5,7}
(b) |2|=10,|3|=5,|4|=5,|5|=5,|6|=10,|7|=10,|8|=10,|9|=5,|10|=2.
2, 6, 7, and 8 are generators. There are two subgroups: {1, 3, 4, 5, 9} and {1, 10}.
(c) Yes, for instance in Zp, additive group modulo p, because the discrete log problem is
defined wrt the group operation and not necessarily multiplication.
InZp,ai =a+a+…+a=ai=b,andicanbeeasilycomputedasb/a.
BU CAS CS 538. 2
Problem 2.
(a) Let f : {0, 1}n → {0, 1}n be any one-way function. Is f 2 = f (f (x)) one-way?
(b) Let f : {0, 1}n → {0, 1}n be a one-way permutation function. Is f 2 = f (f (x)) one-way? Solution.
(a) No. A counterexample is as follows: Suppose that f is constructed from some strong one-way function f ′ : {0, 1}n/2 → {0, 1}n/2 in the following way
{0}n if x1 = 0 f(x1||x2) = {0}n/2||f′(x2) otherwise
Then, f2(x) = 0 for any x and is therefore very easy to invert.
(b) Yes. We will prove f2 is also one-way by contrapositive, i.e. if f2 is not one-way, then f is not one-way.
Assume that there exists an efficient adversary A who can invert f 2 with non-negligible probability. That is, ∀x ∈ {0,1}n, given the input y = f2(x) = f(f(x)), A outputs x′ efficiently, and Pr[f2(x′) = y] is non-negligible.
We now do a reduction to show that if such an A exists for f2, then we can use A to build an efficient adversary A′ who can invert f with non-negligible probability. A′ is constructed as follows:
∀x ∈ {0,1}n, given the input y′ = f(x), A′ computes y = f(y′) = f(f(x)) and passes y to A. When A outputs x′, A′ also outputs x′.
Since f is a permutation function (which means it is one-to-one and onto), Pr[f(x′) = y′] = Pr[f(f(x′)) = f(y′)] = Pr[f2(x′) = y] is also non-negligible. Therefore, A′ is an efficient adversary who can invert f with non-negligible probability. This is a contradiction.
Thus, f2 must also be one-way.
Problem 3. Given n = 25, design a secure cipher E = (E, D) defined over (K, M, C) where
|K| = |M| = n.
Solution. First of all, the one-time pad will not work here because n is not a power of 2 (make sure you understand why).
Consider the following “addition mod n” variation of the one-time pad. This is a cipher E = (E, D) defined over (K, M, C) where |K| = |M| = |C| = {0, 1, 2, …, n − 1}.
Encryption and decryption are defined as:
E(k, m) = (k + m) mod n D(k, c) = (−k + c) mod n
BU CAS CS 538. 3 E is correct because ∀k ∈ K, ∀m ∈ M, we have:
D(k,E(k,m)) = (−k + ((k + m) mod n)) mod n = (−k + (k + m)) mod n
= m mod n =m
E is perfectly secure because ∀m ∈ M, ∀c ∈ C, and a uniformly random k ∈ K,
Pr[E(k, m) = c] = Pr[(k + m) mod n = c] = Pr[k = (c − m) mod n]
Thus, the distribution of E(k,m) is independent of m (i.e. the distributions for different m’s are the same). Invoking Theorem 2.1 (iii) ⇒ (i) in Boneh and Shoup’s textbook “A Graduate Course in Applied Cryptography”, this shows that E is perfectly secure.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com