CAS CS538: Cryptography.
January 21, 2023
Due: 10pm Mon Jan 30
Homework 1
Homework preparation and submission instructions: You are encouraged to collaborate with your fellow students and consult external resources in solving the homework problems. Figuring out the problems together is more effective and more fun! However, you should write the solution on your own without looking at your fellow students solutions, and list all external resources and collaborators.
Solutions should be submitted electronically on Gradescope – instructions will be posted on Piazza.
You can handwrite your solution, scan and submit, but typeset solutions will make the grader happier, which in turn may well make you happier. In particular, students are encouraged to use the LaTeX text editor to write solutions. If you do not yet know LaTeX then this is an excellent opportunity to learn, as it is the best software for preparing high quality scientific text. It is also an absolute must for graduate students.
Preliminary task:
Read Section 0.2 in the Joy of Cryptography by Mike Rosulek https://web.engr.oregonstate.edu/ ~rosulekm/crypto/chap0.pdf. Make sure you are comfortable with the notations and that you can com- fortably solve the exercises at the end of the section. There is no need to submit solutions.
Question 1: (60 points, at 15 each except (d))
In this question you will be asked to prove mathematical statements. Recall that a proof is a sequence of mathematical statements, such that the last statement is the conclusion of the theorem, and each state- ment is either an axiom, or an assumption, or else is it follows from previously made statements in the proof. In your proofs below, you may use elementary axioms of arithmetic (commutativity, associativity, distributivity), as well as the following theorem:
Theorem 1 (Division Theorem) If n is a positive integer and a is any integer, then there are unique integers q (called “quotient”) and r (called “remainder”) such that 0 ≤ r < n and n = qa + r.
Do not use anything else; if you feel you need to use some other fact that you cannot prove, clearly state the fact and explain that you don’t know how to prove it. Please use words like “because” and “therefore” in your proofs: a collection of equations without any logical connectors is impossible to understand.
Be careful to use definitions of % and ≡k precisely, as defined in the reading. We will use notation a|n (pronounced “a divides n” or “n is divisible by a”) to denote that the remainder r in the division theorem is 0, i.e., n = qa for an integer q.
(a) Let p > 2 be a prime (that is, for all positive x, y, if p|xy then p|x or p|y). Prove that, for any integers a ̸≡p 0, r and s, if ra ≡p sa, then r ≡p s. (Note that you don’t yet know that “division” modulo p exists, so you cannot “cancel” a nor multiply both sides by “1/a”.)
(b) Let p > 2 be a prime. Prove that, for any integer a ̸≡p 0, the values a%p,(2a)%p,(3a)%p,…,((p− 1)a) % p hit every element in the set 1, 2, 3, . . . , p − 1 exactly once. (Hint: think of multiplication by a modulo p as a function — you need to prove that it is a bijection. Use the previous part. )
(c) Prove Fermat’s little theorem: Let p > 2 be a prime. if a ̸≡p 0, then ap−1 ≡p 1. (Hint: multiply together the p−1 values a,2a,3a,…,(p−1)a and use the previous part.)
(d) Pronounce Fermat correctly (it’s like “fur+Ma” and not like “fur+Matt”).
(e) Prove that every non-zero element modulo p has an inverse: for every a ̸≡p 0, there exists b such that
ab ≡p 1. b is called the “inverse of a modulo p.”
浙大学霸代写 加微信 cstutorcs
Question 2: (45 points, at 15 each)
Now that we know inverses (except for 0) exist modulo any prime p, we will denote the modular inverse of a by (1/a)%p or (a−1)%p and define modular division c/a%p as c(a−1)%p. When it is clear that we are working modulo p, we will omit %p.
Zp denotes set of values the values {0, . . . , p − 1} with addition, subtraction, multiplication, and division (except by 0) modulo p. A set with such operations is called a field. Z∗p denotes all of Zp except 0, with the multiplication and division operations. A set with such operations is called a group.
Because multiplication and division are well-defined in Z∗p, raising to positive and negative integer powers is also well-defined (positive powers correspond to repeated multiplication, negative powers correspond to repeated division, and x0 is defined to be 1 for every x). Fractional powers are more complicated, and we will not deal with them now.
Let g ∈ Z∗p. The order of g is the smallest positive integer k such that gk ≡p 1. On first problem, you proved Fermat’s little theorem, which says gp−1 ≡p 1. Thus, for any g ∈ Z∗p, the order of g is at most p − 1.
(a) Prove that for any g, the order of g divides p−1. Hint: suppose the order of g is k. Let p−1 = kq+r, where 0 ≤ r < k (you know such k and r exist by the division theorem). Consider gr.
(b) Prove that if the order of g is k and a ≡k b for some integers a and b, then ga ≡p gb (note the different subscripts of ≡).
(c) Provetheconverseofpart(b): iftheorderofgiskandga ≡p gb forsomeintegersaandb,thena≡k b (note the different subscripts of ≡). Thus, you know that for any g of order k, exponents work modulo k.
Code Help, Add WeChat: cstutorcs
Question 3: (60 points, at 12 each)
Recall the definition of one way functions from the first lecture: A function f : D → R for some domain D and range R is (Tf , Ti , ε)-one way if there exists an algorithm F that, given x ∈ D computes f (x) in time Tf , and in addition for any algorithm A that runs in time Ti, we have
Prob[x←$ D ; A(f(x))=x′ : f(x′)=f(x)]<ε. (1)
(Recall that the expression inside the Prob[...] should be read from left to right, where the expressions between the semicolumns describe steps in the probability experiment, and the expression to the right of the column describes the event measured in the experiment - where the probability is taken over all the random choices made in all steps of the experiment. The notation “x ←$ D” means “the random variable x is drawn uniformly from domain D”.)
(a) Show that, without loss of generality, we can assume that the algorithm A is deterministic. That is, show that if f is (Tf , Ti, ε)-one way with respect to deterministic algorithms (i.e., with respect to algorithms that are not allowed to make random choices), then f is (Tf , Ti, ε)-one way even with respect to randomized algorithms (i.e. with respect to algorithms that can make random choices during their execution). [Hint: show the counter-positive statement, namely start from a randomized algorithm for inverting f and obtain a deeterministic one.]1
Say that a function f : D → R is (Tf,Ti,ε)-uniform-output one way if we change (1) to require that it is hard to invert a random element in the range, namely we require that for any algorithm A that runs in time Ti, we have
Prob[y←$ R; A(y)=x : f(x)=y]<ε.
(b) Prove or disprove: If f is (Tf , Ti, ε)-one way then f is also (Tf , Ti, ε)-uniform-output one way. (To prove, argue why the statement is necessarily true for all f. To disprove, assume you are given a one way function f and show how to transform it into a function f′ that is still one way but not uniform-output one way.
(c) Prove or disprove: If f is (Tf , Ti , ε)-uniform-output one way then f is also (Tf , Ti , ε)-one way.
(d) * Prove or disprove: If there exist (Tf , Ti , ε)-one way functions then there exist also (Tf′ , Ti′ , ε′ )-uniform-
output one way functions, with a potentially different domain and range, and where (Tf′ , Ti′, ε′) are polyno-
miallyrelatedto(T ,T,ε),i.ethereexistsaconstantc>0suchthatT′