闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC/MA 414 Cryptography

Homework 1

January 26, 2023

1 [35 pts (5 pts each)] Multiple Choice

Perfect Security and Computational Security

1. In a nutshell, Kerckhoff’s Principle says that when we prove/disprove the security of a cryptographic scheme we must assume that:

(a) The adversary knows the distribution of the inputs and the keys of Alice and Bob. (b) The adversary knows that Alice and Bob will use a secret key in their computation.

2. For an encryption scheme to be perfectly secure, it should be the case that:

(a) Given a ciphertext input, the adversary should not be able to find the key via

brute force, even if the adversary has unbounded running time

(b) Given a ciphertext input, the adversary should not be able to learn the entire

message encrypted in the ciphertext, even if the adversary has unbounded running time

(c) Given a ciphertext input, the adversary should not be able to distinguish if the message encrypted is m or m\ , for any pair of messages m,m\ in the message space M

3. Formally, an encryption scheme (Gen, Enc, Dec) for message space M and ciphertext space C is perfectly secure if:

(a) 3 a message distribution M such that, Am ∈ M and Ac ∈ C:

Pr[M = m|C = c] = Pr[M = m]

(b) A message distributions M, for any pair of messages m,m\ ∈ M: Pr[M = m] = Pr[M = m\]

(d) both are true

PRG and Computational security

1. A hard problem in the context of cryptography is:

(a) A problem where the instances of the problem are almost never encountered in

real life applications, but that are very useful for cryptography. An example is prime factorization of numbers , we don’t really need to factor numbers in our everyday life, but this problem is useful in cryptography.

(b) A problem where instances of the problem are currently impossible to solve, but

we do not know if they will be solvable in the future.

(c) A problem where instances of the problems are possible to solve, but we currently do not know any algorithm that solves any instance of the problem running in time that is polynomial in the size of the instance.

2. In computational security:

(a) The security of a scheme is guaranteed, as long as the adversary does not guess

the key

(b) The security of a scheme is analyzed under the assumption that the adversary has

a fixed running time and can win with a fixed but very small probability

(c) The security of a scheme is analyzed under the assumption that the adversary runs in time that is polynomial in the security parameter

3. The purpose of a PRG is to:

(a) Take as input a random seed and output a key for an encryption scheme

(b) Take as input a message and output a random looking encryption of that message

4. In the PRG game, we have a distinguisher D that aims to distinguish between the output of some algorithm G : {0, 1}n → {0, 1}ℓ(n) and a truly random generator. What input does D receive at the start of the game?

(a) The value y = G(s)

(b) The seed s used by the algorithm G

(d) A value y of length ℓ(n)

2 [15 pts] Mod-5 OTP

Let M = {0, 1, 2, 3} and the message distribution be uniform.

The key space is K (chosen uniformly) from K = {0, 1, 2, 3, 4}.

Enc(k,m) = k + m mod 5

Dec(k,c) = c − k mod 5

Prove or disprove whether this encryption scheme satisfies correctness and perfect security.

Rubric we will use.

• Intuition:

– Correct conclusion on correctness: 1 pts.

– Correct conclusion on perfect security: 2 pts.

– Intuitive justification of the conclusion: 2 pts.

• Correctness: Correct proof or counterexample: 3 pts.

• Perfect Security: Proof or counterexample:

– Correct logic in the proof: 4 pts.

– Correct probability: 3 pts.

3 [50 pts] PRGs

3.1 [25 pts] Candidate PRG Q

Let G1 : {0, 1}n → {0, 1}2n be a secure Pseudorandom Generator. Let G2 : {0, 1}n → {0, 1}2n be a distinct secure Pseudorandom Generator. Let Q : {0, 1}n −1 → {0, 1}2n be the following algorithm:

Q(s)