Cryptography Concepts and Security Analysis
1. Consider the mono-alphabetic substitution cipher (Lecture 1, slide 20). What is the size of its key space? -26!
2. Consider the poly-alphabetic substitution cipher (Lecture 1, slide 22). What is the size of its key space? -26^t (that is, 26 to the power of t)
3. You know that a meaningful plaintext in a language with an x-letter alphabet is encrypted using either the mono-alphabetic substitution cipher or the poly-alphabetic substitution cipher (with a key of t random numbers in [1,x], for a known value of t; here, assume t=16 and x=18) -(a) mono-alphabetic substitution cipher; (b) 2 to the power of 60
4. Which of these statements summarizes an equivalent form of the perfect secrecy notion? -All above
5. Which of these is not a property of the one-time pad? – It is very efficient with respect to the amount of randomness needed in encryption and decryption
6. Consider the one-time pad encryption scheme for message space, key space and ciphertext space equal to {0,1}. Assume message m … from the message space and let c denote the ciphertext. Select the right values for the following probabilities: Prob[m = 0], Prob[c = 1|m = 0] – 0.5, 0.5
7. Consider using the shift cipher on message space {A,…,Z}. Analyze the security of the resulting encryption scheme. – Satisfies perfect secrecy (R: message space {A,…,Z} means only one character is ever encrypted. which is one- time pad. The one-time pad encryption scheme. In the shift cipher it takes a point on the alphabet, and it randomly shifts it. is means it does not depend on the plain text at all from point of view, other choose are all False.)
8. Consider an extension of the shift cipher where a random and independent shift is applied for each message character. Analyze the security of the resulting encryption scheme. -Satisfies perfect secrecy(R: shifting every character on the alphabet, so in this scheme for every character in the alphabet, once we apply the random shift to the one collector, we going to random place in the alphabet. If we apply new random shift in new character, we going another random independent place, in the end the cipher text will be in a sequence of random characters, again, they are not leaking any information about the plain text)
9. How would you modify the poly-alphabetic substitution cipher so that the resulting schemes satisfies decryption correctness and perfect secrecy? – Setting the key length t to be equal to the message length. (R: with set the key like t equal to the message this schemes becomes what other scheme – one time pad. T equal to the length of the message, and independent shift for every character as well. so both side are equal to the message length)
10. Consider the one-time pad encryption scheme. Replace the XOR operation with the AND operation. Does the resulting scheme satisfy decryption correctness and perfect secrecy?-It satisfies neither. (R: Replace the XOR operation with the AND operation in the one time pad encryption scheme, for this cases, the scheme does not apply the satisfy decryption correctness. For example, if the key is 0, no matter the message is, you cipher test will be 0 as well. so they can never correctness and does not apply perfect security).
1. Assume f, g are such that f(n) = O(g(n)). For which of the following X, does g(n)=X(f(n)) hold?-X=Ω
2. Assume f, g are such that f(n) = o(g(n)). For which of the following X, does g(n)=X(f(n)) hold?– X=ω
3. Assume f,g are such that f(n) = O(g(n)) and f(n) = Ω(g(n)). For which of the following X, does g(n)=X(f(n)) hold?-X=Θ
4. In an encryption scheme, let Enc denote the encryption algorithm, Dec denote the decryption algorithm, and A denote the adversary’s algorithm. Furthermore, let e(n), d(n), denote the running times of algorithms Enc, Dec, respectively, and let a(n) denote the minimum running.., where n is the security parameter. When designing this scheme following the principles of modern cryptography, which of these relationships would you use to choose your algorithms? – e(n),d(n)=O(n^c) and a(n)=Ω(2^{cn}) for some constant c (R: e(n),d(n),a(n)=O(n^c) for some constant c and e(n),d(n),a(n)=Ω(2^{cn}) for some constant care not good in our question. since they are responded the polynomial-time, and not efficient in this scheme. We require the super-polynomial time to break the scheme. e(n),d(n)=O(n^c) and a(n)=Ω(2^{cn})is efficient for the algorithms, we want choose that)
5. Informally, BPP is the class of languages that can be decided by a probabilistic algorithm in polynomial time with an error probability of at most 1/3 on any instance. More formally, a language L is in BPP if there exists a probabilistic algorithm A that runs in polynomial time and satisfies the following: if x is in L then A(x) returns 1 with probability at least 2/3; if x is not in L then A(x) returns 1 with probability at most 1/3. By performing independent repetitions of algorithm A and taking the majority output, one can amplify the (2/3; 1/3) gap to (1 – 2^{-k}; 2^{-k}), which is extremely close to (1,0)… It is known that P is in BPP, and while it is conjectured that P = BPP, this is actually unknown. It is also unknown whether BPP is in NP. Consider the following statements: (1) if L1 is polynomial-time reducible to L2, and L2 is in BPP, then L1 is in P; (2) if L1 is polynomial-time reducible to L2, and L2 is in BPP, then L1 is in NP. These statements are, respectively: -unknown, unknown(R:R: by repeating algorithm A and taking the majority output. In other words, if L2 is in BPP, then L1 is in BPP if L1 is polynomial-time reducible to L2. L1 is unknown in P, so we cannot divide by it. If L1 is polynomial-time reducible to L2, and L2 is in BPP, then L1 is in NP. It is also unknown if BPP is in NP since L1 is same as L2)
6. Which of the listed features are enjoyed by one-way functions -hard to invert, easy to compute
7. Which of the listed features are enjoyed by trapdoor functions?-Easy to invert with a trapdoor, Easy to compute, Hard to invert
8. Which of the following features are enjoyed by hard-core predicates for a function F? -Hard to compute from F’s output, Easy to compute from F’s input
9. For a still merely intuitive notion of “secure”, which cryptographic primitives are sufficient to construct a “secure” public-key cryptosystem?-a one-way trapdoor permutation f is sufficient since a hard-core predicate can be constructed for any one-way function, including f(R: rational: we need permutation always, since a hard-core predicate can be constructed for any one-way function, including f)
10. Assume you want to construct a public-key cryptosystem using the principles of modern cryptography, and you are allowed to choose languages L1, L2 such that your cryptosystem can be proved secure assuming that deciding L1 is easy and L2 is hard; from which of the following complexity classes would you pick L1 and L2? -L1 from BPP and L2 from (NP minus BPP) (R: we want Alice and Bob run BPP algo, since is more efficient to solved easy questions. we want NP, so they can also handle hard question L2)
1.What is gcd(x,y) in the following two input scenarios: 1. y divides x 2.11.y, 2.1
2. Which of these algorithms can be used to compute gcd(a,b)? Is this algorithm efficient?-scan all integers in [1,min(a,b)] and output the max integer dividing both a and b; it is not efficient(R:this is some kind of Euclid’s algorithm, Since it dividing both a and b its not efficient. It’s allow the min array a and b dividing by at least one)
3.Which of these algorithms can be used to compute the inverse of an integer y modulo n? Is this algorithm efficient? – scan all integers x in [1,n] and output x (if any) such that xy = 1 mod n; it is not efficient.
4.Consider algorithms B.10, B.11, B.12, and B.13 in the [KL] textbook. Which one(s) among these does not run in polynomial time in the input length? -B.12 (Modular Exponentiation using Repeated Multiplication)
5.Recall that Factoring is the problem of computing, on input a positive integer n, a factorization of n in terms of integer powers of prime numbers. One can formulate variants of this problem that are “easy” or “hard” depending on the (sub)set of integers from which n is chosen. Define the trial division algorithm D to solve the factoring problem and study its running time t_D(n). Given this algorithm and its running time, we want to infer considerations on factoring n being easy or conjectured to be hard when n is chosen among products of two primes. Let m_easy(n) be a value for min(p, q) such that factoring n is easy and m_hard(n) be a value for min(p, q) such that factoring n may be conjectured to be hard. Which functions would you select as most meaningful for t_D(n), m_easy(n), m_hard(n)?– t_D(n)=O(square root of n); m_easy(n)=O(poly(log n)); m_hard(n)=O(square root of n) (R:t_D(n) has to be square roof of n; m_easy(n) be a value for min(p, q) such that factoring n is easy , which is match O(poly(log n)). p is very small, q is very large, So when we do division algorithm, we can find P easily. In m_easy(n) be a value for min(p, q) such that factoring n is easy and m_hard(n) be a value for min(p, q) such that factoring n may be conjectured to be hard, both p and q are suare root of n, they are about same size)
6. Consider the following three assumptions: 1.The hardness of factoring integers that are product of two primes of the same length; 2.The hardness of inverting the RSA function; 3. The hardness of computing the trapdoor in the RSA permutation. Determine which of them is known to be sufficient or not to construct a trapdoor permutation. Which of the following statements is true? – (3),(2),(1) is sufficient
7. You have to choose the length of the modulus n for the RSA trapdoor permutation in use within your public-key cryptosystem. The attacker has one of the following resources: (a) a single computer, (b) a collection of computers distributed across the Internet, or (c) a fully functional quantum computer (you can assume one exists for the purpose of answering this question). Which of the following lengths for n would you choose? – (a): 2048; (b): 4096; (c): I would not use RSA
8. Consider the following three problems: 1. Factoring integers that are product of two primes of the same length; 2. Inverting the RSA function; 3. Computing the trapdoor in the RSA permutation. Choose all statements below which you think are true. -The hardness of (1) or (2) is sufficient to construct a one-way function; The hardness of (2) or (3) is sufficient to construct a one-way function; The hardness of (1) or (3) is sufficient to construct a one-way function (R: all of those 3 option are true. RSA is one way function. for 3. Computing, is same cases as RSA, so it’s again one way function. product of two primes of the same length are one way function as well. since is can be factor)
9. Let T denote the RSA trapdoor permutation, d its trapdoor, n and e its public values, and p,q be the (secret) prime factors of n. Is the problem of computing T easy or (conjectured to be) hard, in the sense of complexity theory. If you think it is “easy”, also select which algorithm you would use to solve the problem, among the following: modular exponentiation (ME), greatest common divisor (GCD). If you think it is “hard”, also select which assumption you would use to prove that the problem is hard, among the following: factoring (F) and RSA (RSA). –Easy/ME
10. Let T denote the RSA trapdoor permutation, d its trapdoor, n and e its public values, and p,q be the (secret) prime factors of n. Is the problem of inverting T easy or (conjectured to be) hard, in the sense of complexity theory. If you think it is “easy”, also select which algorithm you would use to solve the problem, among the following: modular exponentiation (ME), greatest common divisor (GCD). If you think it is “hard”, also select which assumption you would use to prove that the problem is hard, among the following: factoring (F) and RSA (RSA). -Hard/RSA
11. Let T denote the RSA trapdoor permutation, d its trapdoor, n and e its public values, and p,q be the (secret) prime factors of n. Is the problem of inverting T, when given d as an additional input, easy or (conjectured to be) hard, in the sense of complexity theory. If you think it is “easy”, also select which algorithm you would use to solve the problem, among the following: modular exponentiation (ME), greatest common divisor (GCD). If you think it is “hard”, also select which assumption you would use to prove that the problem is hard, among the following: factoring (F) and RSA (RSA). –Easy/ME(R: It’s inverting T, but the question is given d as an additional input, so it’s Easy in modular exponentiation (ME))
12. Let T denote the RSA trapdoor permutation, d its trapdoor, n and e its public values, and p,q be the (secret) prime factors of n. Is the problem of computing d from inputs n and e easy or (conjectured to be) hard, in the sense of complexity theory. If you think it is “easy”, also select which algorithm you would use to solve the problem, among the following: modular exponentiation (ME), greatest common divisor (GCD). If you think it is “hard”, also select which assumption you would use to prove that the problem is hard, among the following: factoring (F) and RSA (RSA). –Hard/F
13. Let x be a large integer. Is the problem of determining whether x is prime easy or (conjectured to be) hard, in the sense of complexity theory? If you think it is “easy”, also select which algorithm you would use to solve the problem, among the following: primality test (PT), greatest common divisor (GCD). If you think it is “hard”, also select which assumption you would use to prove that the problem is hard, among the following: factoring (F) and RSA (RSA). –Easy/PT(R: The probabilistic Miller-Rabin primality testing algorithm runs in polynomial time, and it’s easy. Since the problem was determining whether x is prime is prime easy or (conjectured to be) hard, which the input integer is prime)
14. Let a,b be large integers. Is the problem of determining whether a nd b are coprime easy or (conjectured to be) hard, in the sense of complexity theory? If you think it is “easy”, also select which algorithm you would use to solve the problem, among the following: primality test (PT), greatest common divisor (GCD). If you think it is “hard”, also select which assumption you would use to prove that the problem is hard, among the following: factoring (F) and RSA (RSA). – Easy/GCD
15. Let c,d be large, same-length, primes, and let n=cd. Is the problem of factoring n easy or (conjectured to be) hard, in the sense of complexity theory? If you think it is “easy”, also select which algorithm you would use to solve the problem, among the following: primality test (PT), greatest common divisor (GCD). If you think it is “hard”, also select which assumption you would use to prove that the problem is hard, among the following: factoring (F) and RSA (RSA). – Hard/F
1. For any random variables X,Y, let us denote as “X ci Y” the fact that random variables or distributions X and Y are computationally indistinguishable. Evaluate whether the following 4 statements are true (T) or false (F): 1) if X ci Y then Y ci X; 2) if X ci Y and Y ci X then X = Y, 3) if X ci Y then Y = X, and; 4) if X = Y then X ci Y. Which of these sequences gives the correct evaluation of the above statements?- T, F, F, T
2. Let f be a one-way permutation, G be pseudo-random generator, and hc be a hard-core predicate for f. Consider the following 4 distributions: 1) (f(x),hc(x)), for random n-bit string x; 2) (f(x),b), where x is a random n-bit string and b is a random bit; 3) a random (n+1)-bit string y; and 4) the (n+1)-bit output of G on input a random n-bit seed s. Which of these distributions are computationally indistinguishable?–1,2,3, and 4
3. Assume random seeds s1 and s2 satisfy |s1|=|s2|=n, let F be a one-way permutation, HC be a hard-core predicate for F, and consider the functions defined as follows: G1(s1,s2)=s1xors2,G2(s1,s2)=(F(s1), F(s2), HC(s1, s2)).Which of the above are pseudo-random generators? -Only G2
4. Assume random seeds s1 and s2 satisfy |s1|=|s2|=n, let F be a one-way permutation, HC be a hard-core predicate for F, and consider the functions defined as follows: H1(s1,s2) = (s1,s1 xor s2, s2), H2(s1,s2) = (F(s1), F(s1) xor F(s2), HC(s1, s2)). Which of the above are pseudo-random generators? – Only H2
5. Denote by F a pseudo-random function, by P a pseudo-random permutation, by RF a random function and by RP a random permutation. Which pairs among the above are computationally instistinguishable (c.i.)? -The outputs of every pair among all 4 are c.i.
6. Let F(k,.) be a pseudo-random function and k denote its input key. Which of the following functions is a pseudo-random permutation? – None of the above(A 1-round cascaded iteration of P(k,(a,b))=(a,F(k,a)xor b) ; A 3-round cascaded iteration of P(k,(a,b))=(a,F(k,a)xor b))
7. Let F(k,.) be a pseudo-random function and k denote its input key. Which of the following functions is a pseudo-random permutation? -A 3-round cascaded iteration of P(k,(a,b)) = (b,F(k,b) xor a)
8. Consider the following pseudo-randomness primitives: 1. a pseudo-random generator; 2. a pseudo-random function; 3. a pseudo-random permutation Which of them can be constructed by assuming the hardness of factoring integers that are product of two large primes of the same length? none among – all three(none; a pseudo-random generator but neither a pseudo-random function nor a pseudo-random permutation; a pseudo-random generator and a pseudo-random function but not a pseudo-random permutation)
9. You have to choose a pseudo-random generator as a component of your cryptography solution. Your application calls for a scheme that has the strongest security and does not care much about efficient runtime performance. Among which class of pseudo-random generator would you choose it? – A scheme based on a hard number theory problem
10. Theory recap: An oracle adversary is an adversary that makes queries to an oracle and obtains answers, before making a determination about the oracle. To prove that a permutation P is not a pseudo-random permutation, it suffices to show an efficient oracle adversary that can distinguish, with not negligible probability, the case in which its oracle is P from the case in which its oracle is a random permutation RP with the same input and output domains as P. To obtain an algorithm that makes this distinction, it suffices to find one or more distinguishing conditions among the adversary’s query inputs and query outputs such that: (a) if the oracle is P, then the condition holds with high (e.g., 1) probability; (b) if the oracle is RP, then the condition holds with low (e.g., negligible) probability. Question: Define the “extended FT transform” as the permutation that maps (L,M,R) to (M xor R,f_k(M) xor L,f_k(R) xor L), where k is a random key, f is a pseudo-random function, and L,M,R are n-bit strings, for some large integer n. Which of the following conditions are distinguishing conditions (based on a single input) for the 1-round iteration of the extended FT transform? Notation: (L,M,R) denotes the input of the extended FT transform and (L’,M’,R’) denotes the 1-round output of the extended FT transform on input (L,M,R) – (M=R) and (L’=0)
1. Which among these are the differences between the following two security notions? perfect indistinguishability secrecy (equivalent to perfect secrecy), as defined for classical symmetric encryption schemes message indistinguishability (also labelled as IND or EAV), as defined for modern symmetric encryption schemes – In perfect indistinguishability the adversary’s algorithm is not restricted to run in polynomial time and his advantage has to be equal to 0 while in EAV the adversary’s algorithm runs in polynomial time and his advantage can be greater than 0 2. For symmetric encryption schemes, which among these are the differences between the following two security notions? indistinguishability (also labelled as IND or EAV) indistinguishability in the presence of chosen message attacks (also labelled as IND-CMA) – In the IND-CMA notion, the adversary can additionally and repeatedly query the E(k,.) algorithm as an oracle, and can later use these queries and responses to generate the two challenge plaintexts m(0) and m(1) and its guess for which message was encrypted as c
3. The notation a^b is used to denote a with b as exponent. Let G:{0,1}^n–>{0,1}^{2n} be a pseudo-random generator and consider the following symmetric encryption scheme (KG,E,D), where KG generates a random string k; E, on input key k and a message bit b, returns c = G(k) xor 1^{2n} if b=1, where 1^{2n} denotes a 2n-bit string of 1’s, or c = G(k) if b=0; D is naturally defined so to satisfy the decryption correctness property. Which of the following security notions is satisfied by (KG,E,D)? -security in the sense of indistinguishability in the presence of eavesdropping attacks 4. The notation a^b is used to denote a with b as exponent.
Let F:{0,1}^n–>{0,1}^{n} be a pseudo-random function and consider the following symmetric encryption scheme (KG,E,D), where KG generates a random string k; E, on input key k and a string m, randomly chooses r and returns c = (r, F(k,0) xor m); D is naturally defined so to satisfy the decryption correctness property. Which of the following security notions is satisfied by (KG,E,D)?
-security in the sense of indistinguishability in the presence of eavesdropping attacks 5. The notation a^b is used to denote a with b as exponent. Let P:{0,1}^n–>{0,1}^{n} be a pseudo-random permutation and consider the following symmetric encryption scheme (KG,E,D), where KG generates a random string k; E, on input key k and an n-bit string m, returns c = (m xor P(k,r),r), for some n-bit random string r; D is naturally defined so to satisfy the decryption correctness property. Which of the following security notions is satisfied by (KG,E,D)? -Security in the sense of indistinguishability against chosen message attacks (IND-CPA) and security in the sense of indistinguishability against adaptive chosen message attacks (adaptive-IND-CPA) 6.You are asked to choose a block cipher as part of the implementation of a secure system for applications that are highly demanding both in security and efficiency. Which of the following ones would you choose? -AES 7. Which one among the following block cipher modes of operation, on an input of the type (x,y,x), always returns an output of the type (z,w,z)? – Here, x,y,z,w denote equal-length message blocks, such that x is different than y, and z is different than w
8. We want to design a new block cipher based on substitution/permutation networks. Which of the following sets of principles should we apply? -Set the key and block length equal to at least 128 bits; use S-boxes to achieve confusion effect; use permutations and mixing to achieve a diffusion effect; achieve the avalanche effect; use a large number (say, at least 10) of rounds 9. When choosing a previously designed 128-bit block cipher for some real-life application, we want to ensure that this cipher is somewhat resistant to known attacks, including ciphertext-only, known-plaintext, known-ciphertext, chosen-ciphertext, differential and linear attacks. Which of the following is a realistic goal for such a cipher? (Here, the notation x^y denotes x raised to the power y.) –The cipher should appear to be secure in the presence of all these attacks from any algorithm running in time at most equal to a specific large constant, such as 2^{100} block cipher calculations) 10.You are asked to choose a block cipher mode of operation as part of the implementation of an efficient and secure system for applications such as a streaming multi-party conferencing event. Which of the following choices would you go with? -Either OFB or Counter
1. Let F be a pseudo-random function and consider the following p)roposed construction for a Tag algorithm in a MAC: Tag(k,(m1,m2)) = (r, F(k,r) xor F(k,m2) xor F(k,m1)), for a random r. Here, notation is as follows: (m1,m2) denotes the concatenation of m1 and m2; F(k,m) is the output of F on input key k and string m, and Tag(k,(m1,m2)) denotes algorithm Tag on input key k and, as message, (m1,m2). Which of the following statements is true? You can assume the KG algorithm returns a random key k and the Verify algorithm follows the typical approach of running the Tag algorithm to check the tag. -The MAC is not existentially unforgeable in the presence of chosen message attacks(R:F(k,r) is not helping simple attack, we know this attack is body attacks) 2.Let F be a pseudo-random function and consider the following proposed constructions for a Tag algorithm in a MAC: Tag(k,(m1,m2)) = F(k, m2 xor F(k,m1)).Here, notation is as follows: (m1,m2) denotes the concatenation of m1 and m2; F(k,m) is the output of F on input key k and string m, and Tag(k,(m1,m2)) denotes algorithm Tag on input key k and, as message, (m1,m2). Which of the following statements is true? You can assume the KG algorithm returns a random key k and the Verify algorithm follows the typical approach of running the Tag algorithm to check the tag-The MAC is existentially unforgeable in the presence of chosen message attacks (CBC. two blocks)
3. Assume students randomly choose their answers to a homework similar to this one, with 18 questions, of 4 possible answers each (of which only 1 is correct). Using an appropriate result in [KL, appendix A] (e.g., Lemma A.16), calculate the smallest number of students so that with probability at least 0.5 at least two students give the same answers to all questions. Which of these ranges does this number belong to? (Here, the notation a^b denotes a to the power of b, and the notation [c,d) means all numbers between c and d-1.) -[2^{16},2^{32})(R: possible combination is 4^18 4. Let H be a collision-resistant hash function that on input a key k and a message m, returns an L-bit output H(k,m), and consider the following construction: H'((k1,k2),(m1,m2)) = (H(k1,m1),H(k2,m2)). That is, H’ takes as input two random keys k1 and k2, and two messages m1, m2 and returns the concatenation of H(k1,m1) and H(k2,m2). Design a birthday-type attack to find collisions in construction H’ with probability at least 1/2. Which is the smallest number of evaluations of H that you can find to be sufficient for your attack? (Here, the notation a^b denotes a to the power of b.) –O(2^{L/2}) evaluations of H(R: We first need find the first part of the output((H(k1,m1)),it will give 2 collisions of 1and 1 prime, and then we find 2nd(H(k2,m2)))2 collisions of 2 and 2 prime, so our collisions of each prime is M1,M2,this is input, 1prime and 2prime is other input) 5. Let H be a collision-resistant hash function that on input a key k and a message m, returns an L-bit output H(k,m), and consider the following construction: H”((k1,k2);m) = (H(k1;m),H(k2;m)). That is, H” takes as input two random keys k1 and k2, and one message m and returns the concatenation of H(k1,m) and H(k2,m). Design a birthday-type attack to find collisions in construction H” with probability at least 1/2. Which is the smallest number of evaluations of H that you can find to be sufficient for your attack? (Here, the notation a^b denotes a to the power of b.) -O(2^L) evaluations of H (R: we can not combine this equation to find collisions for each single one, collisions for single for both will be 5,6.-(collisions in both side), there are just not only one of them, best can do is run 2^L for attack, so the run time of it is xx) [6Note: when the cipher text is dissymmetric or part it, you can choose message attack]
6. Consider the following symmetric encryption scheme (KG,E,D), which uses a pseudo-random permutation P, with inverse P^{-1}, and a message authentication scheme (Gen, Tg, Vrfy) with unique tags. The key generation algorithm KG returns randomly chosen keys k1, k2. On input keys k1,k2 and message m, the encryption ..E randomly chooses r, computes x = P(k1;m) and returns ciphertext c = (x,Tg(k2;x)). On input keys k1,k2 (returned by KG) and ciphertext c, the decryption algorithm D writes c as (c1,c2), verifies whether Vrf(k2;(c1,c2))=1; if yes, it writes x as (x1,x2) and returns message m’ = P^{-1}(k1;x1), otherwise it returns an error message. Which is the strongest security notion satisfied by the scheme (KG,E,D) among the listed notions below?-security in the sense of indistinguishability against eavesdropping attacks(R: we can recognize the encryption m is running twice wait for same x there, for best is) 7. Consider the following symmetric encryption scheme (KG,E,D), which uses a pseudo-random permutation P, and a message authentication scheme (Gen, Tg, Vrfy) with unique tags(de). The key generation algorithm KG returns randomly chosen keys k1, k2. On input keys k1,k2 (returned by KG) and message m, the encryption algorithm E randomly chooses r, computes x = (r, m xor P(k1;r)) and returns ciphertext c = (x,Tg(k2;m)). On input keys k1,k2 (returned by KG) and ciphertext c, the decryption algorithm D writes c as (c1,c2), verifies whether Vrf(k2;(c1,c2))=1; if yes, it writes x as (x1,x2) and returns message m’ = P(k1;x1) xor x2, otherwise it returns an error message. Which is the strongest security notion satisfied by the scheme (KG,E,D) among the listed notions below?-security in the sense of indistinguishability against eavesdropping attacks(R: Tg(k2,m) is unique, which mean 2nd de, but is not secure) 8. Consider the password verification scheme defined at the end of Application Case Study 1. Which attacks (or combination of attacks) suffice to impersonate a user choosing a password from a not large enough space?-Server intrusion and dictionary attack suffice to impersonate a user(psw is send encryption, and random sort)
9. Let a,b,c be positive integers, and let H be a collision-intractable hash function, assumed to behave like a random function. Consider the following crypto-puzzle: Given an a-bit string y, find a b-bit string x such that H(x) = (y,z), for some c-bit string z. Which of these is the probability of solving the crypto-puzzle after 1 evaluation of H? (Here, p^q denotes p to the power of q). – 2^{-a}(R :no c choose value of a) 10. Let a,b,c,k be positive integers, and let H be a collision-intractable hash function,.. behave like a random function. Consider.. crypto-puzzle: Given an a-bit string y, find a b-bit string x such that H(x) = (y,z),.. for t–>infinity, of (1-1/t)^{tk} is 1/e^k, for e equal to about 2.718. Which of the following would you use as the number of evaluations of H needed to solve the crypto-puzzle,except with probability-k*2^a (R: the probability that the crypto-puzzle is solved with one evaluation is 1/2^a. Thus, the probability that the crypto-puzzle is not solved with one evaluation is less than (1-1/2^a). To reduce this probability to e^{-k}, as requested by question 10, we use k*2^a evaluations, so that the probability that the crypto-puzzle is not solved is less than (1-1/2^a)^{k*2^a}. If we set t=2^a, we can use the calculus limit in the question 10 statement, and obtain that the probability value (1-1/2^a)^{k*2^a} = 1/e^k, as desired)