2.3 Q3 This question is about PRF, MAC, cryptographic hash functions and more. 2.3.1 A ( ( - BlockChain applications use collision resistant hashing in order to prove that the user a certain amount of effort/work. Specifically, assume we have the hash function family H which is CRHF (with a key). We set the security parameter to be n = 80. In order to prove work, we choose key k with length 80 randomly for H(80) : {0,1}* + {0,1}80 and send it to the user. The user is asked to find two messages m, m2 0,180 such that: H80)(m) = H (80)(m2) 180 Describe what will the user's actions and give an upper limit to the number of calls to H(80, that the user needs to perform until the user will find the two messages with a probability of or higher. Try your best to make as many function calls as possible. Apply the analysis using the ROM model. Meaning, assume that instead of choosing H (80 like before, by choosing k randomly, choose H (80 such that each output over given input is chosen randomly and will be saved (in case it will be asked about later) when it is being asked about. The user has oracle access to H(80) 4 2.3.2 B 080 Like A but here find two messages like in A but we demand m = Meaning, like in A you need to define an algorithm for the user and give a upper bound over the function calls of H(80) 2.3.3 It is known that in RSA, the attacker is trying to encrypt a message m = 0 that accidentaly doesn't satisfy ged(m, N) = 1 and then he would be able to quickly figure out the secret key. In this question, we ignore the problem that textbook RSA is not CPA safe (vulnerable to cipher text only attacks) and we focus on finding the key in this case. 1. a Explain how we can find the secret key given N and message m as described (of course, if it has been found by "accident" it doesn't need to be explained). 2. b Explain, by calculating, why given the public key N = P1 P2, the choice of m randomly from Zm will give m as required in a only by a negligible probability (on the length of input N in bits). Meaning, it is highly unlikely to find m by chance. 2.3.4 D Given a deterministic signature scheme that is assumed to be secure: KeyGen(1"), Sig(sk, m), Verify(pk, m, tag) Construct an accurate MAC scheme that is based on this signature scheme and prove it is secure. 2.3.5 E Prove the security of a signature scheme without using the assumptions of computational difficulties satisfy a proof that P + NP. Meaning explain how the claim: (KeyGen(1"), Sig(sk, m), Verify(pk, m, tag)) is secure signature system implies P + NP. 5 HINT: You can use the theorem from complexity theory that if P = NP, then for all languages in NP, not only there is an efficient algorithm that verifies there exists a witness for x, but there exists an efficient algorithm that also finds a suitable witness if it exists (or says it doesnt exists). 2.3.6 F In this question we assume DLOG is hard. Describe accurately (using pseudo-code) how to create a secure Block-Cipher. Meaning, How to create a family of PRF F(k, x) such that in addition to every function that accepts values from ke {0,1}" and operats on input x in length n, fx(x) = F(k, x) is invertible efficiently Note: If you want, you can create a family with longer keys. Meaning, function of the form fx(x) = F(k, x) such that for security parameter n, x comes from {0,1}", the output is in {0,1}" but the k comes from a larger domain e.g {0,1}4n 2.3 Q3 This question is about PRF, MAC, cryptographic hash functions and more. 2.3.1 A ( ( - BlockChain applications use collision resistant hashing in order to prove that the user a certain amount of effort/work. Specifically, assume we have the hash function family H which is CRHF (with a key). We set the security parameter to be n = 80. In order to prove work, we choose key k with length 80 randomly for H(80) : {0,1}* + {0,1}80 and send it to the user. The user is asked to find two messages m, m2 0,180 such that: H80)(m) = H (80)(m2) 180 Describe what will the user's actions and give an upper limit to the number of calls to H(80, that the user needs to perform until the user will find the two messages with a probability of or higher. Try your best to make as many function calls as possible. Apply the analysis using the ROM model. Meaning, assume that instead of choosing H (80 like before, by choosing k randomly, choose H (80 such that each output over given input is chosen randomly and will be saved (in case it will be asked about later) when it is being asked about. The user has oracle access to H(80) 4 2.3.2 B 080 Like A but here find two messages like in A but we demand m = Meaning, like in A you need to define an algorithm for the user and give a upper bound over the function calls of H(80) 2.3.3 It is known that in RSA, the attacker is trying to encrypt a message m = 0 that accidentaly doesn't satisfy ged(m, N) = 1 and then he would be able to quickly figure out the secret key. In this question, we ignore the problem that textbook RSA is not CPA safe (vulnerable to cipher text only attacks) and we focus on finding the key in this case. 1. a Explain how we can find the secret key given N and message m as described (of course, if it has been found by "accident" it doesn't need to be explained). 2. b Explain, by calculating, why given the public key N = P1 P2, the choice of m randomly from Zm will give m as required in a only by a negligible probability (on the length of input N in bits). Meaning, it is highly unlikely to find m by chance. 2.3.4 D Given a deterministic signature scheme that is assumed to be secure: KeyGen(1"), Sig(sk, m), Verify(pk, m, tag) Construct an accurate MAC scheme that is based on this signature scheme and prove it is secure. 2.3.5 E Prove the security of a signature scheme without using the assumptions of computational difficulties satisfy a proof that P + NP. Meaning explain how the claim: (KeyGen(1"), Sig(sk, m), Verify(pk, m, tag)) is secure signature system implies P + NP. 5 HINT: You can use the theorem from complexity theory that if P = NP, then for all languages in NP, not only there is an efficient algorithm that verifies there exists a witness for x, but there exists an efficient algorithm that also finds a suitable witness if it exists (or says it doesnt exists). 2.3.6 F In this question we assume DLOG is hard. Describe accurately (using pseudo-code) how to create a secure Block-Cipher. Meaning, How to create a family of PRF F(k, x) such that in addition to every function that accepts values from ke {0,1}" and operats on input x in length n, fx(x) = F(k, x) is invertible efficiently Note: If you want, you can create a family with longer keys. Meaning, function of the form fx(x) = F(k, x) such that for security parameter n, x comes from {0,1}", the output is in {0,1}" but the k comes from a larger domain e.g {0,1}4n