• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 1 fuera de 4 páginas
Examen

CMPT 404 — Cryptography and Protocols

Document preview thumbnail
Vista previa 1 fuera de 4 páginas

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
$10.69

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Seller avatar
Los indicadores de reputación están sujetos a la cantidad de artículos vendidos por una tarifa y las reseñas que ha recibido por esos documentos. Hay tres niveles: Bronce, Plata y Oro. Cuanto mayor reputación, más podrás confiar en la calidad del trabajo del vendedor.
BESTGRADED
5.0
(2)
Vendido
33
Seguidores
24
Artículos
1951
Última venta
1 año hace



Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes

Ups! No podemos cargar tu documento ahora. Inténtalo de nuevo o contacta con soporte.