CMPT 404 — Cryptography and Protocols
Outline Solutions to Exercises on Message Authentication Schemes, CCA Security and Number Theory. 1. Given f : f0; 1gn ! f0; 1gn, define f0 : f0; 1g2n ! f0; 1g2n as follows: for x; r 2 f0; 1gn define f0(x◦r) = f(x) ◦ r. (Where ◦ denotes concatenation.) Prove that if f(·) is a one-way permutation then so is f0(·). Note first that if f is a permutation then so is f0. Suppose that f0−1 is computable in polynomial time. Then, given y = f(x), set y0 = y ◦ 0 where 0 is the all-zero string of appropriate length. Find x ◦ 0 = f0−1(y0). Thus f−1 is computable in polynomial time, a contradiction. 2. Consider the following variant of CMA-security for MACs: instead of giving the adversary black boxes for both the signing and verification algorithms, give it only a black box for the signing algorithm. Let’s call this definition CMA’-security. That is, A pair of algorithms (Sign; Ver) (with Sign : f0; 1gn × f0; 1gm ! f0; 1gt, Ver : f0; 1gn × f0; 1gm × f0; 1gt ! f0; 1g) is a (T; ")-CMA’-secure MAC if for every x; k, Verk(x; Signk(x)) = 1 andf or every T-time Adv, if we run the following experiment: • Choose k − f0; 1gn • Give adversary access to black box for Signk(·) • Adversary wins if it comes up with a pair hx0; s0i such that (a) x0 is not one of the messages that the adversary gave to the black box Signk(·) and (b) Verk(x0; s0) = 1. Then the probability Adv wins is at most ". (Sign; Ver) is CMA’-secure if there are super-polynomial functions T; " such that for every n, (Sign; Ver) is (T (n); "(n))-CMA’-secure. In other words, there is no polynomial-time Adv that succeeds with polynomial probability to break it. A MAC scheme has unique tags if for every message there is only one tag that passes verification. An equivalent way of stating this property is that the verification algorithm on input x and t outputs 1 if and only if Sk(x) = t. Note that the MAC scheme we saw in class has this property. Prove that for MACs with unique tags, CMA security and CMA’ security are equivalent (e.g., such a scheme is (T; ")-CMA secure if and only if it is (T 0; "0)-CMA’ secure for some T 0,"0 polynomially related to T; ". (The condition of unique tags is important — if a MAC scheme does not have unique tags then these notions may not be equivalent.) Since in the case of CMA-security an adversary is more powerful than for CMA’-security, every CMA-secure MAC is also CMA’-secure. So let (Sign; Ver) be a T; "-CMA’ secure MAC. Suppose that it is not CMA-secure, and Adv is an efficient adversary. We construct an efficient adversary Adv0 that does not get access to the verification box, and therefore yields a contradiction with CMA’-security of (Sign; Ver). Adv0 - choose k at random from f0; 1g - run Adv - whenever Adv asks to sign a message P return Signk(P ) - whenever Adv asks to verify a pair (P; s), output 1 if s = Signk(P ), otherwise output 0 - when Adv comes up with a pair (P; s), output this pair To show violation of CMA’-security it suffices to observe that on a verification request (P; s) the new adversary Adv0 answers 1 if and only if s = Signk(P ), and, due to the unique tag property, if and only if Ver(P; s) = 1. Therefore Adv0 perfectly simulates verification requests of Adv, and so violation of CMA’-security follows from violation of CMA-security by Adv.
Información del documento
- Subido en
- 12 de noviembre de 2022
- Número de páginas
- 4
- Escrito en
- 2022/2023
- Tipo
- Examen
- Contiene
- Preguntas y respuestas