Apuntes Criptografiamoderna

Apuntes de Criptografı́a
Fernando Virdia
Versión 0.0.1, junio 2024
OTP PRG PRP DSS TDP
PR-OTP PRF Hash DDH
CPA SKE MAC CCA KEM CPA PKE
AE CCA PKE
Figure 1: Mapa de los primitivos criptográficos que vamos a ver. En amarillo, primitivos sujetos
a postulado. En verde, primitivos que reciben una demostración matemática de seguridad. En
naranja, primitivos para los cuales no damos una demostración formal.
1
Clase 0: introducción
Fernando Virdia, versión: 0.0.1, junio 2024
Esta clase se encuentra en forma de diapositivas en https://apuntes.indcpa.com.
2
Clase 1: preliminares matemáticos I
1 Preliminares
1.1 Números y conjuntos
Usamos Z>0 para representar el conjunto de Números enteros positivos {1, 2, 3, . . . }. Dado n ∈ Z>0 ,
denotamos con [n] el conjunto {1, 2, . . . , n}.
Usamos ∅ para representar el conjunto vacı́o, ∅ = { }. Usamos |S| para representar la cardinalidad
de S.
Dado un valor lógico V definimos JV K := 1 si V es verdadero, y JV K ( := 0 si V es falso.
0 si b = c,
Dados dos bits b, c ∈ {0, 1}, escribimos b ⊕ c = b XOR c = Jb ̸= cK =
1 si b ̸= c.
ℓ
Usamos {0, 1} para representar el conjunto de cadenas de ℓ bits. Si ℓ = ∗, las cadenas pueden ser
arbitrariamente largas. Dada una cadena de bits c, denotamos |c| el numero de bits en c.
Si b = b1 b2 . . . bn y c = c1 c2 . . . cn son dos cadenas de n bits, escribimos b ⊕ c para representar la
cadena d = d1 d2 . . . dn donde di = bi ⊕ ci .
Lemma 1 (Desigualdad triangular) Dados x, y ∈ R, |x + y| ≤ |x| + |y|.
1.2 Probabilidad
Dado un conjunto finito S, usamos U (S) para representar la distribución de probabilidad uniforme
sobre S. Una variable aleatoria X distribuida según U (S), X ∼ U (S), es tal que
1
Pr[X = x] = ∀x ∈ S.
|S|
Dado un segundo conjunto S ′ , y una función f : S → S ′ , podemos definir una secunda variable
aleatoria Y = f (X). La distribución de Y no es necesariamente la misma de X. A veces escribimos
Pr [Y = y]
X∼U (S)
para indicar Pr[Y = y] = Pr[f (X) = y] cuando X ∼ U (S).

Dadas dos variable aleatorias A y B, la probabilidad condicional de A = a dado B = b puede
definirse de varias maneras. En este curso consideramos Pr[A = a | B = b] como la probabilidad que
A = a asumido que ya se sabe que B = b (por ejemplo, A podrı́a ser el resultado de un experimento,
donde B determina parte de la aleatoriedad del mismo). Se mantiene que si Pr[B = b] > 0,
Pr[A = a ∧ B = b]
Pr[A = a | B = b] = .
Pr[B = b]
Dados eventos A = a y B = b:
• Pr[A ̸= a] = 1 − Pr[A = a],
• Pr[A = a | B = b] = 1 − Pr[A ̸= a | B = b].1
Teorema 1 (Teorema de la probabilidad total, informal) Dada una variable aleatoria B con
valores en un conjunto finito S, podemos descomponer el evento A = a como
X
Pr[A = a] = Pr[A = a ∧ B = b]
b∈S
X
= Pr[A = a | B = b] · Pr[B = b].
b∈S
Lemma 2 (Union bound, cota de la unión) Dados eventos A1 , . . . , An ,

" n # n
_ X
Pr[A1 ∨ A2 ] ≤ Pr[A1 ] + Pr[A2 ], e iterando, Pr Ai ≤ Pr[Ai ].
i=1 i=1
1 Demostración: Pr[B=b∧A=a]+Pr[B=b∧A̸=a]
1= Pr[B=b]
= Pr[A = a | B = b] + Pr[A ̸= a | B = b].
3
1.3 Aleatoriedad
Postulado 1 Dado un conjunto finito R, podemos tomar muestras ri de la distribución uniforme
sobre R, ri ∼ U (R).
Comentario 1 Generalmente consideramos R = {0, 1}n con n ∈ Zn .
Comentario 2 Generalmente, llamamos una tal muestra ri ∼ U (R), monedas (“coins”). A veces
$
escribimos ri ←
− R.
Definición 1 (Algoritmo aleatorio) Sea A un algoritmo con conjunto de inputs I y conjunto

de outputs O. Decimos que A es aleatorio si dado x ∈ I, A(x) es una variable aleatoria con valor
A(x) ∈ O.
En criptografı́a, definimos la variante “de-randomizada” A de A como la función A : I ×R → O
tal que
∀y ∈ O, Pr[A(x) = y] = Pr [A(x, r) = y].
r∼U (R)
Generalmente abusamos notación y escribimos A(x; r) en lugar de A(x, r).
En criptografı́a trabajamos con “adversarios” que interceptan comunicaciones e intentan vulner-

arlas de varias maneras. Estos adversarios son modelados como algoritmos aleatorios, que corren
en tiempo ≤ t. En criptografı́a a menudo argumentamos que dos variables aleatorias tienen una
distribución muy “parecida”. A través del siguiente teorema, eso nos permite de prever los logros
de un adversario.
Teorema 2 (Informal, “data processing inequality”) Dadas dos variables aleatorias X, Y

con distribución “parecidas”, y dada una función o algoritmo aleatorio A, las variables aleatorias
A(X), A(Y ) “se parecen” al menos cuanto X e Y .
Definición 2 (función aleatoria) Sea D un conjunto, y R un conjunto finito. Decimos que

f : D → R es una función aleatoria, si cada salida f (x) fue muestreada aleatoriamente en R.
Generalmente, f puede ser realizada a través de la siguiente maquina de estados.
f (x)
1 : if L = ⊥ :
2 : L←[] // una tabla hash
3 : if x ̸∈ L :
$
4 : L[x] := y ←
−R
5 : return L[x]
Si D es un conjunto finito, esta definición coincide con la de una función muestreada uniforme-
mente del conjunto (finito) {f | f : D → R} de funciones de D a R.
Comentario 3 (Algoritmos “eficientes”) Durante este curso vamos a ver varios algoritmos
usados para cifrar y autenticar datos. Aunque no los tratamos de manera asintótica, vamos a
requerir implı́citamente que estos algoritmos sean eficientes. Cifrado y autenticado generalmente
tardan tiempo proporcional a |input|. Para un input de pocos bits, estas operaciones suelen tardar
pocos milisegundos o menos (en Linux, corran openssl speed para ver un ejemplo).
4
Clase 2: cifrado simétrico, secreto perfecto
2 One-Time Pads y secreto perfecto

Introducimos la noción de cifrado simétrico.
Definición 3 (SKES, cifrado simétrico) Sean K, M, C tres conjuntos. Decimos que Π =
(Gen, Enc, Dec) forman un cifrado simétrico (SKES, “secret-key encryption scheme”) con espacio
de llaves K, espacio de mensajes M, y espacio de cifrados C, si
• Gen es un algoritmo aleatorio, Gen : ∅ → K;
• Enc es un algoritmo (posiblemente aleatorio), Enc : K × M → C;
• Dec es un algoritmo determinista Dec : K × C → M;

tales que
Pr[Dec(k, Enc(k, m; $)) = m] = 1,
k∼Gen(),
$ en Enc
donde Gen, Enc y Dec son “eficientes”.
m∈M
c = Enc(k, m)
Enc Dec m′ ∈ M
Gen k∈K
Figure 2: Uso de un cifrado simétrico. Consideramos el cifrado c ser expuesto al adversario.
Comentario 4 Generalmente consideramos K, M, C ⊂ {0, 1}∗ en la criptografı́a simétrica.
Comentario 5 Generalmente consideramos K finito, y Gen() consiste en muestrear la distribución

$
uniforme k ←
− U (K).
Dada la sintaxis de un SKES, queremos encontrar definiciones que capturen la “seguridad” del
mensaje cifrado c = Enc(k, m).
PREGUNTA: Alguna idea de como definir la seguridad de c?
1. Podrı́amos pedir que dado c, un adversario no aprenda k. Y si aprende m?

2. Podrı́amos pedir que dado c, un adversario no aprenda m. Y si aprende la primera mitad de
m?
3. Podrı́amos pedir que dado c, no aprenda ninguna información sobre m. Y si alguna infor-
mación es publica, por ejemplo que todo m ∈ M está escrito en castellano?
Definición 4 (Secreto perfecto, Shannon) Sea Π = (Gen, Enc, Dec) un SKES. Decimos que Π
ofrece secreto perfecto si dada la variable aleatoria k ∼ Gen(),
∀m0 , m1 ∈ M, c ∈ C, Pr [Enc(k, m0 ) = c] = Pr[Enc(k, m1 ) = c].

k∼Gen()
Comentario 6 Un SKES que otorga secreto perfecto leakea que m ∈ M. Por ejemplo, si M =
{0, 1}ℓ , leakea que |m| = ℓ.
5
Ejemplo 1 (Cifrario de Cesar) Sea K = {0, 1, . . . , 9}, M = {0, 1, . . . , 9}∗ . Supongamos m =
m0 , m1 , m2 ∈ M. Para cifrar m con llave k, sumamos mi +k mod 10 para i = 1, 2, 3. Por ejemplo,
m = 123, k = 3 =⇒ c = 456.
El cifrado de Cesar otorga secreto perfecto? No! Por ejemplo, dado m0 = 123, m1 = 555,
c = 567, podemos observar que
Pr[c = Enc(k, m0 )] > 0 (existe una llave k valida)

Pr[c = Enc(k, m1 )] = 0.
Una definición equivalente de secreto perfecto requiere
∀m ∈ M, c ∈ C, Pr[M = m | C = c] = Pr[M = m].
En nuestro ejemplo, ver C = 567 implica la imposibilidad de que M = 555, por lo cual aprendemos
algo sobre M viendo C, Pr[M = m | C = c] ̸= Pr[M = m].
Definición 5 (One-Time Pad) Sean n ∈ Z>0 , K = M = C = {0, 1}n . Π = (Gen, Enc, Dec) es
un one-time pad (OTP), si
Gen() Enc(k, m) Dec(k, c)

$
1 : k←
−K 1 : c←m⊕k 1 : m′ ← c ⊕ k
2 : return k 2 : return c 2 : return m′
Teorema 3 El OTP ofrece secreto perfecto.
Demostración. Sean n ∈ Z>0 , m0 , m1 ∈ {0, 1}n , c ∈ {0, 1}n .
Pr [Enc(k, m0 ) = c] = Pr[k ⊕ m0 = c] (def. de Enc)

k∼U (K)
= Pr[k = c ⊕ m0 ]
= 2−n (dado k ∼ U (K))
= Pr[k = c ⊕ m1 ]
= Pr[k ⊕ m1 = c]
= Pr[Enc(k, m1 ) = c].
Teorema 4 (Teorema de Shannon) Sea Π = (Gen, Enc, Dec) un SKES con secreto perfecto.
Entonces |K| ≥ |M|.
Demostración. Por contradicción, supongamos |K| < |M|. Idea: vamos a construir m0 , m1 , c, tales
que Pr[Enc(k, m0 ) = c] > 0 y Pr[Enc(k, m1 ) = c] = 0.
Fijemos k0 ← Gen(), m0 ∈ M, c = Enc(k0 , m0 ).
=⇒ Pr [Enc(k, m0 ) = c] ≥ Pr [k = k0 ] > 0.
k∼Gen() k∼Gen()
Ahora definamos el conjunto S := {Dec(k, c) | ∀k ∈ K} ⊂ M. Notamos que |S| ≤ |K| < |M|.
Dado que S ⊂ M y |S| < |M|, sabemos que M\S = {m | m ∈ M y m ̸∈ S} = ̸ ∅. Elijamos
m1 ∈ M\S. Supongamos que ∃k ∈ K tal que Enc(k, m1 ) = c. Si ası́ fuera, dado que Π es un
SKES, sabemos que Dec(k, c) = Dec(k, Enc(k, m1 )) = m1 , lo que implicarı́a que m1 ∈ S. Por lo
tanto ̸ ∃k ∈ K tal que Enc(k, m1 ) = c
=⇒ Pr [Enc(k, m1 ) = c] = 0.
k∼Gen()
Esto contradice la suposición que Π brinde secreto perfecto. Por lo tanto, |K| ≥ |M|. □
PREGUNTA: Por que “one-time”? Alguna idea? Vamos a ver la razón próximamente.
6
Comentario 7 El teorema de Shannon nos dice que para obtener secreto perfecto, se requiere
una llave secreta k grande al menos tanto cuanto el mensaje que se quiere ocultar. Esto nos
pondrı́a frente a la situación paradójica por la cual comunicar de manera segura un mensaje requiere
comunicar de manera segura una clave no mas breve.
La única ventaja del OTP es la a-sincronı́a. La clava puede ser comunicada de antemano, y el
mensaje determinado solo luego. Esto probablemente aun se usa en algunas embajadas.2
En la próxima clase vamos a ver nuevos postulados que nos van a permitir superar las limita-
ciones del teorema de Shannon.
Ataque 1 (OTP) Supongamos A ve c ∈ C. Que aprende sobre m? Dado cualquier m ∈ M, si

k ← m ⊕ c, Dec(k, c) = k ⊕ c = (m ⊕ c) ⊕ c = m. A solamente puede aprender que m ∈ M (⇒
aprende |m|), y que comunicación cifrada ocurrió. Usando padding extra se podrı́a “obfuscar” |m|,
y comunicando a intervalos regulares información “nula”, podrı́a “obfuscarse” que la comunicación
ocurrida fue significativa. Notamos que estos ataques están “fuera” de la definición de secreto perfecto,
y no la contradicen.
2 https://archive.is/mmbtX#selection-1025.0-1025.238
7
Clase 3: seguridad computacional y pseudoaleato-
riedad
Ahora vamos a ver relajaciones de la noción de secreto perfecto, y vamos a usar un nuevo
postulado para construir algoritmos de cifrado mas eficientes del OTP.
Es común en criptografı́a relajar las definiciones de seguridad, en cambio de eficiencia. Vemos un

ejemplo.
Definición 6 (One-time ε-secrecy) Decimos que un SKES tiene one-time ε-secrecy (OT ε-
secrecy) si dada la variable aleatoria k ∼ Gen(),
∀m0 , m1 ∈ M, c ∈ C, |Pr[Enc(k, m0 ) = c] − Pr[Enc(k, m1 ) = c]| ≤ ε.
Comentario 8 Un SKES con OT ε-secrecy con ε = 0 otorga secreto perfecto.
EJERCICIO: [BS23, Exercise 2.5]: OT ε-secrecy =⇒ |K| ≥ (1 − ε)|M|
Comentario 9 Lo mas cercano ε a 0, lo mas cercano OT ε-secrecy al secreto perfecto, y lo mas

cercano lo que un adversario A puede hacer dado un cifrado salido de un SKES con OT ε-secrecy
a lo que puede hacer con un cifrado salido de un cifrado con secreto perfecto.
En la practica, tratamos que ε ∈ [2−256 , 2−128 ]. Si ε < 2−λ , decimos que un SKES ofrece λ-bits
de seguridad estadı́stica.
Comentario 10 Por que “one-time”? Supongamos que Alicia quiere comunicar con Bob, y com-
parte una clave de OTP k muestreada k ∼ Gen(). Alicia y Bob deciden de cifrar dos mensajes
usando la misma clave:
c1 = k ⊕ m1
c2 = k ⊕ m2 .
Si un adversario A observa los cifrados c1 y c2 en transito, que puede aprender sobre m1 y m2 ?
c1 ⊕ c2 = (k ⊕ m1 ) ⊕ (k ⊕ m2 )
= m1 ⊕ m2 .
Esto es un problema! Por ejemplo, si m1 es un mensaje predecible, digamos Pr[m1 = m1 ] ≈ 1, A

puede adivinar, y determinar que m2 = c1 ⊕ c2 ⊕ m1 con probabilidad ≈ 1.
El OTP otorga seguridad si la llave (“pad”) k se usa una sola vez (“one-time”). No garantiza
nada si la llave se la usa mas de una vez.
Comentario 11 OT ε-secrecy solo garantiza confidencialidad. No otorga garantı́as de integridad.

Si Alicia usa un OTP para comunicarle a su banco que quiere pagar m = $4 = $1002 a un
negociante, y este intercepta el cifrado
c = c0 c1 . . . c9 = k0 k1 . . . k6 k7 k8 k9
⊕ 0 0 . . . 0 1 0 0,
lo intercepta y transmite c′ = c ⊕ (10 . . . 0) al banco, este decifrarı́a
m′ = k ⊕ c′ = $(1000000100)2 = $ 29 + 22 = $516,
costandole a Alicia mucho mas.
Hemos visto como se puede relajar una definición de seguridad. Ahora vamos a introducir un
nuevo postulado.
8
3 PRGs, PRFs, PRPs
Ahora vamos a definir 3 familias de objetos criptográficos que vamos a utilizar para construir
mejores cifrados.
Definición 7 (PRG) Sea G : {0, 1}ℓ → {0, 1}m una función, implementable como un algoritmo
determinista eficiente. Generalmente ℓ < m. Dado un adversario aleatorio A y un bit b ∈ {0, 1},
definimos el siguiente experimento ExpPRG (A, b)
ExpPRG (A, 0) ExpPRG (A, 1)

$ $
1 : − {0, 1}ℓ
s← 1 : − {0, 1}m
y←
2 : b′ ← A(G(s)) 2 : b′ ← A(y)
3 : return b′ 3 : return b′
Decimos que G es un generador (ε, t)-pseudoaleatorio (PRG, “pseudorandom generator”), si para

todo adversario A que corre en tiempo ≤ t, la ventaja de A es
Adv(ExpPRG , A) := Pr[ExpPRG (A, 0) ⇒ 1] − Pr[ExpPRG (A, 1) ⇒ 1] ≤ ε.
s ∼ U ({0, 1}ℓ ) PRG k ≈ U ({0, 1}m )
9
Clase 4: definiciones de seguridad “bit-guessing”
Comentario 12 Este tipo de definición dice que A no logra distinguir el experimento “b = 0” del
experimento “b = 1”, si ε ≈ 0.
Esta intuición puede ser formalizada usando la equivalente definición de “bit-guessing”: bajo
las condiciones de Definition 7, G es un (ε, t)-PRG si dado el experimento ExpPRG ,
ExpPRG (A)
$
1 : b←
− {0, 1}
2 : b′ ← ExpPRG (A, b)
3 : return Jb = b′ K
1 ε
Adv(ExpPRG , A) := Pr[ExpPRG (A) ⇒ 1] − ≤ .
2 2
Lemma 3 Bajo las condiciones de Definition 7,
Adv(ExpPRG , A) = 2 · Adv(ExpPRG , A).
Demostración. Usando el teorema de la probabilidad total,
Pr[ExpPRG (A) ⇒ 1] = Pr[b′ = b]

: 1/2 : 1/2
= Pr[b′ = b | b = 0] 0] + Pr[b′ = b | b = 1]

Pr[b
= Pr[b
=
1].
Ahora notamos que por definición de ExpPRG ,
Pr[b′ = b | b = 0] = Pr[ExpPRG (A, 0) ⇒ 0] = 1 − Pr[ExpPRG (A, 0) ⇒ 1],

y Pr[b′ = b | b = 1] = Pr[ExpPRG (A, 1) ⇒ 1].
De consecuencia,
1
Adv(ExpPRG , A) = Pr[b′ = b] −
2
1 1
= (Pr[b′ = b | b = 0] + Pr[b′ = b | b = 1]) −
2 2
1 1
= 1 − Pr[ExpPRG (A, 0) ⇒ 1] + Pr[ExpPRG (A, 1) ⇒ 1] −
2 2
1
= Pr[ExpPRG (A, 1) ⇒ 1] − Pr[ExpPRG (A, 0) ⇒ 1]
2
1
= Adv(ExpPRG , A).
2
□
Comentario 13 Este misma equivalencia vale para la mayor parte de los experimentos que con-
sideramos en criptografı́a.
Comentario 14 Que quieren decir exactamente (ε, t)?
10
G
{0,1}ℓ
{0,1}2ℓ {0,1}2ℓ
distribución distribución
pseudoaleatoria uniforme
El output de G(·) ∈ {0, 1}m es muy lejano de ser uniforme en {0, 1}m , si uno puede ver “de
una” la distribución.
$
La definición de (ε, t)-PRG no dice que G(s ←− {0, 1}ℓ ) ∼ U ({0, 1}m ) si no que un adversario
A que corre en tiempo ≤ t no puede distinguirlas!
En otras palabras, si un “(ε, t)-atacante” es un adversario que termina en tiempo ≤ t con
ventaja > ε, un sistema (ε, t)-seguro es un sistema para el cual no existen (ε, t)-atacantes: un
atacante requiere correr por tiempo > t para obtener ventaja > ε, o si corre en tiempo ≤ t obtiene
solamente ventaja ≤ ε.
Contra un sistema (ε, t)-seguro pueden existir atacantes “triviales”.
• Por ejemplo, si G : {0, 1}ℓ → {0, 1}m con m = 2ℓ es un (ε, t)-PRG, el siguiente atacante
corre en tiempo ≈ 2ℓ y gana con ventaja ≈ 1 − 2ℓ :
A(y ∈ {0, 1}m )

1 : L = {}
2 : for x ∈ {0, 1}ℓ :
3 : L ← L ∪ {G(x)}
4 : if y ∈ L return “PRG” (b′ = 0)
5 : else return “random” (b′ = 1).
Claramente, A corre en tiempo ≈ 2ℓ .

EJERCICIO: Demuestren que Adv(ExpPRG , A) ≈ 1 − 2−ℓ
Su ventaja es Adv(ExpPRG , A) = Pr[ExpPRG (A, 0) ⇒ 1] − Pr[ExpPRG (A, 1) ⇒ 1] , con Pr[ExpPRG (A, 0) ⇒
1] = 0 (si b = 0, entonces y ∈ L y A adivina b′ = 0 siempre correctamente), y con
Pr[ExpPRG (A, 1) ⇒ 1] = Pr[y ̸∈ L], que dado b = 1 ⇔ y ̸∈ L pasa con probabilidad
ℓ
≈ (1 − 2−m )2 ≈ 1 − 2ℓ · 2−m = 1 − 2−ℓ .
Esto quiere decir que contra un PRG G : {0, 1}ℓ → {0, 1}2ℓ siempre existe un (ε ≈ 1−2−ℓ , t ≈
2ℓ )-atacante.
• En el otro extremo, se considere el siguiente atacante:
A(y ∈ {0, 1}m )

1 : z ← G(00 . . . 0)
2 : if y = z return “PRG” (b′ = 0)
3 : else return “random” (b′ = 1).
EJERCICIO: Demuestren que A es un (ε ≈ 2−ℓ , t ≈ 1)-atacante. (Idea: el espacio

G({0, 1}ℓ ) es mas chico de {0, 1}2ℓ .)
$
Aquı́ A corre en tiempo t ≈ 1, pero con pésima ventaja: Pr[ExpPRG (A, 0) ⇒ 1] = Pr[G(s ← −
{0, 1}ℓ ) ̸= G(0 . . . 0)] ≈ 1 − 2−ℓ , mientras Pr[ExpPRG (A, 1) ⇒ 1] = Pr[y ̸= G(0 . . . 0)] ≈ 1 −
2−2ℓ , que implica Adv(ExpPRG , A) ≈ 2−ℓ −2−2ℓ ≈ 2−ℓ . Por lo cual existe un (ε ≈ 2−ℓ , t ≈ 1)-
atacante.
11
Comentario 15 Generalmente, si un sistema ofrece algún tipo (ε, t)-“X-security”, decimos que
ofrece log2 (t/ε) “bits de seguridad X”. Dado λ = log2 (t/ε), obtenemos ε = 2−λ · t, indicando que
con λ bits de seguridad, es necesario trabajar ≈ 2λ tiempo para tener ventaja ≈ 1.
log 2 t
cones
128
126
hic sunt dra
124
log 2 (t/ε) = λ = 128
122
120
118
116
114
ε
0.0 0.2 0.4 0.6 0.8 1.0
Regresemos al problema del OTP: para cifrar mensajes m ∈ {0, 1}m precisamos transmitir
de manera segura una clave k ∼ U ({0, 1}m ).
PREGUNTA: Como podemos usar un PRG?
$
− {0, 1}m con una clave pseudoaleatoria k ← G(s),
Idea: Podemos remplazar la clave aleatoria k ←
$
− {0, 1}ℓ es mas corta que m.
donde s ←
Definición 8 (PR-OTP) Sean ℓ, m ∈ Z>0 con ℓ < m, K = {0, 1}ℓ , M = C = {0, 1}m . Sea
G : {0, 1}ℓ 7→ {0, 1}m un PRG. Π = (Gen, Enc, Dec) es un one-time pad pseudoaleatorio (PR-
OTP, “pseudorandom OTP”), si
Gen() Enc(k, m) Dec(k, c)

$
1 : k←
−K 1 : c ← m ⊕ G(k) 1 : m′ ← c ⊕ G(k)
2 : return k 2 : return c 2 : return m′
Comentario 16 El nuevo cifrado no otorga secreto perfecto. En la demostración del OTP, el

pasaje clave era
Pr[k = c ⊕ m0 ] = Pr[k = c ⊕ m1 ] ∀m0 , m1 , c
Dado G : {0, 1}5 → {0, 1}10 , no todo valor en {0, 1}10 tiene una “pre-imagen” en {0, 1}5 . Es posible
que ∃m0 , m1 , c tales que Pr[G(k) = c ⊕ m0 ] > 0 y Pr[G(k) = c ⊕ m1 ] = 0.
PREGUNTA: Alguien tiene alguna idea de que podemos intentar demostrar?

Idea: Podrı́amos intentar demostrar OT ε-secrecy?
Como vimos, dándole suficiente tiempo al adversario, todo PRG es inseguro. Las demostra-
ciones en criptografı́a son del tipo “si ∃ un ataque en el esquema ⇒ ∃ un ataque en el componente”,
y solo tienen sentido si creemos que ∄ un ataque en el componente.
Necesitamos una definición de seguridad que considere un adversario con tiempo limitado.
Definición 9 (One-time (ε, t)-secrecy) Sea Π = (Gen, Enc, Dec) un SKES. Dado un adversario
A = (A1 , A2 ) y un bit b ∈ {0, 1}, definimos el experimento ExpOTS (A, b),
ExpOTS (A, b) m1 , m2
ExpOTS (A, b)
1 : k ← Gen()
c A
2 : m0 , m1 , σ ← A1 () k ← Gen()
3 : c ← Enc(k, mb ) c ← Enc(k, mb ) b′
′
4 : b ← A2 (c, σ)
5 : return b′
b′
12
Decimos que Π otorga one-time (ε, t)-secrecy3 si para cualquier adversario A que corre en
tiempo ≤ t y produce mensajes de igual de largo |m0 | = |m1 |, su ventaja (“advantage”) en distin-
guir b = 0 de 1 es
Pr[ExpOTS (A, 0) ⇒ 1] − Pr[ExpOTS (A, 1) ⇒ 1] ≤ ε.
Hasta ahora habı́amos visto definiciones de seguridad “information-theoretical” (secreto per-

fecto; “para cualquier A . . . Pr = Pr”), y “estadistica” (ε-secrecy, “para cualquier A . . . | Pr − Pr | ≤
ε”). Finalmente llegamos a una definición de seguridad “computacional”:
“para cualquier A en tiempo ≤ t. . . | Pr − Pr | ≤ ε”.
Es esta relajación de requisitos que nos permite de obtener la mayor parte de las garantı́as crip-
tográficas.
3 “EAV-security” en [KL20], “semantic security” en [BS23].
13
Clase 5: “one-time-pad” pseudoaleatorio
Lemma 4 Sea G un (ε, t)-PRG. Un PR-OTP ΠG que utiliza G, otorga (ε′ , t′ )-secrecy con ε′ = 2ε
y t′ ≈ t.
Demostración. Supongamos de haber encontrado un adversario A que corre en tiempo ≤ t′ y que

tiene ventaja Adv(ExpOTS , A) > ε′ cuando “juega”. A partir de A construiremos B que corre en
tiempo t ≈ t′ y que juega ExpPRG .
𝓑
m0, m1 ∈ {0, 1}m
ExpPRG(𝓑, b)
(|m0| = |m1|)
B(y ∈ {0, 1}m )
y ∈ {0, 1}m b←$ {0, 1}
c ← y ⨁ mb 𝓐
$
1 : b←
− {0, 1}
2 : m0 , m1 , σ ← A1 () c
3 : c ← y ⊕ mb b' ∈ {0, 1}
4 : b′ ← A2 (c, σ)
⟦b = b'⟧
5 : return Jb = b′ K
Calculemos Adv(ExpPRG , B):

• Si B recibe y ← G(s) en ExpPRG , internamente crea para A el mismo ambiente de la versión
“bit-guessing” de ExpOTS . Por lo tanto,
Pr[ExpPRG (B, 0) ⇒ 1] = Pr[ExpOTS

ΠG (A) ⇒ 1].
$
• Si B recibe y ←
− {0, 1}m , simula nuevamente ExpOTS para A, pero en este caso es con un
cifrado OTP!
Pr[ExpPRG (B, 1) ⇒ 1] = Pr[ExpOTS
OTP (A) ⇒ 1].
Abusando la notación, sea b′ ← A2 (c ← y ⊕ mb ) y repliquemos la demostración de Lemma 3,

para obtener
∀b Pr[ExpPRG (B, 1) ⇒ 1] = Pr[b′ ⇒ b]

1
= Pr[b′ = b | b = 0] + Pr[b′ = b | b = 1]
2
1 1
= + Pr[b′ = 1 | b = 1] − Pr[b′ = 1 | b = 0] .
2 2
Dado que y ∼ U ({0, 1}m ),4 y ⊕ m0 ∼ y ⊕ m1 ∼ U ({0, 1}m ).5 De acuerdo, las variables aleatorias
A2 (y ⊕ m0 ) y A2 (y ⊕ m1 ) tienen la misma distribución.
Pr[A2 (y ⊕ m0 ; R) = b | R = r] = Pr[(y ⊕ m0 ) ∈ A−1

2 (b) | R = r]
y
X
= Pr[c = y ⊕ m0 ]
y
c∈∈A−1
2 (b)|R=r
X
= Pr[c = y ⊕ m1 ]
y
c∈∈A−1
2 (b)|R=r
= Pr[(y ⊕ m1 ) ∈ A−1
2 (b) | R = r]
= Pr[A2 (y ⊕ m1 ; R) = b | R = r].
y
4O equivalentemente, como corolario del secreto perfecto del OTP.

5y⊕ m0 y y ⊕ m1 no son independientes, pero tienen la misma distribución. A2 nunca ve ambas variables al
mismo tiempo.
14
Sigue que,
Pr[b′ = 1 | b = 1] = Pr[A2 (y ⊕ m1 ) = 1]
= Pr[A2 (y ⊕ m0 ) = 1]
= Pr[b′ = 1 | b = 0],
y por lo tanto Pr[ExpPRG (B, 1) ⇒ 1] = 21 , y
ε ≥ Adv(ExpPRG , B) = Pr[ExpPRG (B, 0) ⇒ 1] − Pr[ExpPRG (B, 1) ⇒ 1]

1
= Pr[ExpOTS (A) ⇒ 1] −
2
1 ε′
= Adv(ExpOTS , A) = Adv(ExpOTS , A) > ,
2 2
dado que por suposición G es un (ε, t)-PRG. Claramente, t′ ≈ t y ε′ < 2ε. Por lo tanto PR-OTP
otorga (ε′ = 2ε, t′ ≈ t)-secrecy. □
Comentario 17 Otorgar (ε′ = 2ε, t′ ≈ t)-secrecy quiere decir que un atacante contra ΠG tiene
t
al máximo doble de la ventaja de un atacante contra G. En términos de bit-security, log2 ( 2ε )=
t
log2 ( ε ) − 1, i.e. solamente “un bit” de seguridad es perdido.
Si quisiéramos determinar la seguridad concreta en bits, necesitarı́amos una construcción conc-
reta de G, la cual determinarı́a (ε, t).
Ahora vamos a ver dos primitivas relacionadas al PRG, utilizadas para construir PRGs y mas.
Definición 10 (PRF) Sean K, R dos conjuntos finitos, D un conjunto. Sea F : K × D → R una

función implementable como algoritmo determinista eficiente.
ExpPRF (A, b) R(x)

$
1 : k←
−K 1 : if x ̸∈ L :
2 : L←[] 2 : y←
−R
$
3 : if b = 0 : O(·) ← F (k, ·) 3 : L[x] ← y

4 : else : O(·) ← R(·) 4 : return L[x]
5 : b′ ← AO(·) ()
6 : return b′
Decimos que F es una familia de funciones (ε, t, q)-pseudoaleatoria indexada por k ∈ K (PRF,
“pseudorandom function family”), si dado cualquier adversario A que corre en tiempo ≤ t y hace
≤ q queries (consultas) a O(·), tiene ventaja
Adv(ExpPRF , A) := Pr[ExpPRF (A, 0) ⇒ 1] − Pr[ExpPRF (A, 1) ⇒ 1] ≤ ε.
x F (k, ·) F (k, x) o x F (k, ·) F (k, x)
Comentario 18 Bajo el perfil teórico, un PRG requiere un input aleatorio, y retorna un solo
output pseudoaleatorio. Una PRF F (k, ·) : D → R tolera q inputs xi ∈ D no necesariamente
aleatorios, retornando siempre output pseudoaleatorio.
15
Clase 6: cifrados de bloque
Definición 11 (PRP) Sean K, D dos conjuntos finitos. Sea π : K × D → D una función, tal que
∀k ∈ K, π(k, ·) : D → D tiene una inversa π −1 (k, ·) : D → D (tal que ∀x ∈ D, π(k, π −1 (k, x)) =
π −1 (k, π(k, x)) = x). Sean π y π −1 implementables como algoritmos deterministas eficientes.
ExpPRP (A, b) P (x)

$
1 : k←
−K 1 : if x ̸∈ L :
2 : L←[] 2 : y←
$
− D\{L[x] | ∀x ∈ L}
3 : if b = 0 : O(·) ← π(k, ·) 3 : L[x] ← y
4 : else : O(·) ← P (·) 4 : return L[x]
5 : b′ ← AO(·) ()
6 : return b′
Decimos que π es una familia de permutaciones (ε, t, q)-pseudoaleatoria indexada por k ∈ K (PRP,
“pseudorandom permutation family”), o un cifrado de bloques, si dado cualquier adversario A que
corre en tiempo ≤ t y hace ≤ q queries a O(·), tiene ventaja
Adv(ExpPRP , A) := Pr[ExpPRP (A, 0) ⇒ 1] − Pr[ExpPRP (A, 1) ⇒ 1] ≤ ε.
Comentario 19 Una permutación π con D = {0, 1}d permuta cadenas en D, no bits en una
cadena. Por ejemplo, dado d = 3, π(k, 010) podrı́a ser 111, aunque estas cadenas tengan diferentes
números de bits = 1.
Comentario 20 Por motivos históricos y prácticos, los algoritmos de cifrado de bloque, o PRP,
son entre los componentes mas usados (correctamente y no) y estudiados de la criptologı́a. Hoy
en dı́a, el mas utilizado es el Advanced Encryption Standard (AES), que tolera D = {0, 1}128 y
presenta tres variantes: AES-128, con |k| = 128, AES-192, con |k| = 192, AES-256, con |k| = 256.
Se estima que AES-λ ofrece λ = log2 (t/ε) bits de seguridad (ε, t, q)-PRP.
k ∈ K, λ bits
m ∈ M, 128 bits AES-λ c ∈ C, 128 bits
Los algoritmos de cifrado de bloque se utilizan a menudo en “modos de operacion”. Pueden

haber oı́do de ECB-mode (un modo prácticamente siempre inseguro), CBC-, CTR-, GCM-. . . No
vamos a estudiar todos estos, dados que a menudo pensar en términos de modos de operación, en lu-
gar que en términos de modelos de seguridad, puede resultar en la introducción de vulnerabilidades
en protocolos. En efecto, vamos a cubrir métodos equivalentes al CTR y GCM.
PRGs, PRFs y PRPs son equivalentes, o sea:
• PRP ⇒ PRF: “PRP-PRF switching lemma”
• PRF ⇒ PRP: “Feistel networks”
• PRF ⇒ PRG: F (k, x1 )|| · · · ||F (k, xq )
• PRG ⇒ PRF: “GGM”
En el resto del curso, usaremos este postulado.
Postulado 2 Dados (ε, t, q), las (ε, t, q)-PRP existen.
Completamos este tema, construyendo PRFs de PRPs, y PRGs de PRFs.
16
3.1 De PRP a PRF
La idea de esta construcción es que una PRP es una PRF, si A observa pocos outputs. Para
demostrarlo, primero vemos dos lemas requeridos.
Lemma 5 (Difference lemma, lema de la diferencia) Sean E1 , E2 , Z tres eventos donde
E1 ∧ Z ⇐⇒ E2 ∧ Z.
Entonces |Pr[E1 ] − Pr[E2 ]| ≤ Pr[Z].
Comentario 21 “Si se necesita Z para distinguir E1 de E2 , la probabilidad de distinguirlos es al

máximo la probabilidad de que Z suceda.”
Demostración. Calculamos
|Pr[E1 ] − Pr[E2 ]| = (Pr[E1 ∧ Z] +

Pr[E
1 ∧ Z]) − (
Pr[E
2 ∧ Z] + Pr[E2 ∧ Z])
= |Pr[E1 ∧ Z] − Pr[E2 ∧ Z]|.
Dado que 0 ≤ Pr[Ei ∧ Z] ≤ Pr[Z], con i = 1, 2,
=⇒ |Pr[E1 ∧ Z] − Pr[E2 ∧ Z]| ≤ Pr[Z].
Lemma 6 (Birthday bound, paradoja del cumpleaños) Dados q ∈ Z>0 , R un conjunto

finito, y z1 , . . . , zq ∈ R muestreados zi ∼ U (R) de manera independiente,
q(q − 1)
Pr[∃i ̸= j : zi = zj ] ≤
2|R|
Demostración. Calculamos
 
_
Pr[∃i ̸= j : zi = zj ] = Pr  zi = zj 
i̸=j
X
≤ Pr[zi = zj ] (por la cota de la unión)
i̸=j

X 1 q 1 q(q − 1)
= = = .
|R| 2 |R| 2|R|
i̸=j
Comentario 22 El birthday bound es una cota superior “tight” o “ajustada”, o sea que el valor
efectivo de la probabilidad de colisión es muy cercano a la cota. Efectivamente, también se puede
demostrar una cota inferior muy cercana, de ≈ q(q−1)
4|R| [KL20, Lemma A.15].
1.0 p
q= |R| = 2 64
cota inferior de Pr[colisión]
0.8 cota superior de Pr[colisión]
0.6
|R| = 2 128
0.4
0.2
0.0 q
243 248 253 258 263 268 273 278 283
Figure 3: Visualizando
p las cotas en función de q, vemos que la probabilidad “salta” de ≈ 0 a ≈ 1
alrededor de q = |R|.
17
Clase 7: PRP ⇒ PRF
Lemma 7 (PRP-PRF switching lemma) Sea π : K × D → D una (ε, t, q)-PRP. Entonces π

es una (ε′ , t′ , q ′ )-PRF con t′ = t, q ′ = q, ε′ = ε + q(q−1)
2|D| .
Demostración. Supongamos que A sea un adversario contra π usado como una PRF con R = D,
y que evalúa O(·) sobre inputs distintos, sin perdida de generalidad. Observando ExpPRF (A, 0)
y ExpPRP (A, 0), notamos que del punto de vista de A son experimentos idénticos si F = π en
ExpPRF ,
⇒ Pr[ExpPRF (A, 0) ⇒ 1] = Pr[ExpPRP (A, 0) ⇒ 1].
Calculamos,
PRP
Adv(ExpPRF , A) = Pr[Exp
PRF
(A, 0) ⇒ 1] − Pr[ExpPRF (A, 1) ⇒ 1]
:

= Pr[ExpPRP (A, 0) ⇒ 1] − Pr[ExpPRP (A, 1) ⇒ 1] + Pr[ExpPRP (A, 1) ⇒ 1] − Pr[ExpPRF (A, 1) ⇒ 1]

| {z }
=0
PRP PRP
≤ Adv(Exp , A) + Pr[Exp (A, 1) ⇒ 1] − Pr[ExpPRF (A, 1) ⇒ 1] . (por desig. triangular)
Ahora notamos que ExpPRP (A, 1) y ExpPRF (A, 1) son idénticos desde el punto de vista de A, dado
que el siguiente evento no sucede:
Z = “∃i ̸= j : R(xi ) = R(xj ) durante ExpPRF (A, 1)′′
Usando el lema de la diferencia,
Pr[ExpPRP (A, 1) ⇒ 1] − Pr[ExpPRF (A, 1) ⇒ 1] ≤ Pr[Z].
Dado que R(·) muestrea U (R) = U (D) de manera independiente si los inputs son distintos (en
cuanto π es una PRP), por la paradoja del cumpleaños Pr[Z] ≤ q(q−1)
2|R| , y de consecuencia
q(q − 1)
Adv(ExpPRF , A) ≤ Adv(ExpPRP , A) + .
2|D|
Comentario 23 El PRP-PRF switching lemma nos permite construir una PRF con R = D.
Existen construcciones con R =
̸ D, como la PRF “GGM”.
Comentario 24 Este tipo de diferencia en ventaja en función de numero de queries implica a

menudo
√ la necesidad de limitar la durada de las claves secretas usadas. Si en este caso q ≈
D permitirı́a distinguir una PRP de una PRF. A menudo esto implica concretamente ataques
concretos, como https: // sweet32. info .
Lemma 8 (PRF ⇒ PRG) Sea F una (ε, t, q)-PRF con R = {0, 1}r . Sean x1 , . . . , xq ∈ D ele-
mentos distintos (xi ̸= xj , ∀i ̸= j). Definimos G : K → {0, 1}r·q ,
G(s ∈ K)
1 : for i = 1, . . . , q :
2 : yi ← F (k, xi )
3 : return y1 || · · · ||yq
G es un (ε′ , t′ )-PRG con ε′ = ε, t′ ≈ t.
Demostración. Supongamos un adversario A que juega ExpPRG (A, b). Sea B el siguiente adversario
contra la PRF.
18
BO
1 : for i = 1, . . . , q :
2 : yi ← O(xi )
′
3 : b ← A(y1 || · · · ||yq )
4 : return b′
Si b = 1 en ExpPRF , O(·) = R(·),
=⇒ yi ∼ U ({0, 1}r )
=⇒ y ∼ U ({0, 1}r·q )
=⇒ Pr[ExpPRF (B, 1) ⇒ 1] = Pr[ExpPRG (A, 1) ⇒ 1].
Si b = 0, O(·) = F (k, ·) con k ∼ U (K),
=⇒ yi = F (k, xi )
=⇒ y = G(k)
=⇒ Pr[ExpPRF (B, 0) ⇒ 1] = Pr[ExpPRG (A, 0) ⇒ 1].
Sigue que Adv(ExpPRG , A) = Adv(ExpPRF , B), y claramente t′ ≈ t. □

No vamos a ver GGM y Feistel en detalle, dado que las demostraciones se vuelven bastante
difı́ciles.
Feistel inverse Feistel

x y F (k, y) ⊕ F (k, y) ⊕ x = x
F (k, ·) F (k, ·)
y y
L L
F (k, y) ⊕ x
(a) Una ronda de Feistel, junto a su inversa.
(b) Múltiples rondas.
Figure 4: PRF ⇒ PRP: Feistel network. Imagenes adaptadas de [Ros21, Constructions 6.9, 6.11],
usadas con permiso del autor.
19
Figure 5: PRG ⇒ PRF: construcción GGM (Goldreich-Goldwasser-Micali). Credito de ima-
gen: [Ros21].
Comentario 25 No toda combinación de primitivos otorga seguridad. Por que lo siguiente no

funciona?
• Sea G un PRG. F (k, x) := G(k) ⊕ x no es una PRF.
• Sea F una PRF. G(k) := F (1, k)|| · · · ||F (q, k) no es (necesariamente) un PRG.
• Sea G un PRG. G′ (k) := G(k)||G(k) no es un PRG.

• Sea G un PRG. G′ (k1 ||k2 ) := G(k1 ) ∧ G(k2 ) no es un PRG.
Un resumen:
Inicialmente empezamos con el OTP: secreto perfecto, pero |k| = |m|.
Introducimos PRG/PRF/PRP: (ε, t)-secrecy, pero |k| < |m|.
Aun tenemos dos problemas:
• No podemos cifrar mas de un mensaje: c1 ⊕ c2 = m1 ⊕ m2 .
• No podemos garantizar la integridad de los mensajes: Dec(k, c ⊕ ∆) = m ⊕ ∆.

Usando PRFs, podemos resolver ambos.
20
Clase 8: confidencialidad para mensajes múltiples
4 Cifrar más de un mensaje

Como anteriormente, queremos poder usar un SKES, pero generar mas de un mensaje.
Alicia 𝒜 Bob
c1
c2
Enc(k, · ) Enc(k, · )
c3
c4
c5
Dec(k, · ) Dec(k, · )
c6
PREGUNTA: Ideas sobre como definiré seguridad “multi-mensajes”?
Podrı́amos permitirle a A de ver c1 , . . . , cn . Vamos a hacer algo mas: le vamos a permitir pedir
el cifrado de mensajes arbitrarios! O sea: sin darle la clave k, le vamos a otorgar un oráculo que
calcula Enc(k, ·).
PREGUNTA: Esto podrı́a parecer insólito: como podrı́a A acceder a Enc(k, ·)? Ideas?
• Los mensajes podrı́an ser previsibles, dándole a A m y Enc(k, m).

• A podrı́a tener control del input directamente, por ejemplo si es un comerciante que introduce
en el POS el valor a cobrar, y quiere usar (m, Enc(k, m)) para aprender la clave k.
• A podrı́a saber que el mensaje cifrado es consecuente a alguna acción propia.
Nos inspiramos a la definición de secreto perfecto, donde el adversario trata de distinguir

Enc(k, m0 ) de Enc(k, m1 ). En este caso imponemos |m0 | = |m1 | dado que toleraremos M = {0, 1}∗ .
Definición 12 (IND-CPA security) Sea Π = (Gen, Enc, Dec) un SKES.
ExpCPA (A, b) O(m0 , m1 )

1 : k ← Gen() 1 : if |m0 | ̸= |m1 |
′ O : return ⊥
2 : b ← A () 2
′ 3 : c ← Enc(k, mb )
3 : return b
4 : return c
Decimos que Π otorga (ε, t, q)-indistinguibilidad bajo ataques de mensaje elegido (IND-CPA, “in-
distinguishibility under chosen-plaintext attacks”), si para todo adversario A que corre en tiempo
≤ t y hace ≤ q queries a O, su ventaja es
Adv(ExpCPA , A) := Pr[ExpCPA (A, 0) ⇒ 1] − Pr[ExpCPA (A, 1) ⇒ 1] ≤ ε.
21
Comentario 26 Existen definiciones “intermedias” entre (ε, t)-secrecy y (ε, t, q)-IND-CPA. Como
referencia, vean [KL20] o [BS23].
Ejemplo 2
• El OTP no otorga IND-CPA, dado que A puede pedir O(0n , 0n ) ⇒ k, y obtenida k, puede
pedir O(0n , 1n ) ⇒ bn ⊕ k, y ası́ recuperar b.
• Ningún SKES donde Enc(k, ·) es determinista puede otorgar IND-CPA! En cuanto el siguiente
ataque aplica:
1. c1 ← O(0n , 0n )
2. c2 ← O(0n , 1n )
3. Si c1 = c2 , entonces b = 0. Si c1 ̸= c2 , entonces b = 1.
Definición 13 (PRF-CTR) Sea F : K×D → R una (ε, t, q)-PRF con D = {0, 1}d y R = {0, 1}r .
Definimos un SKES Π = (Gen, Enc, Dec) con M = {0, 1}ℓ·r y C = {0, 1}ℓ·r+d , para algún ℓ ≤ 2d /2.
Gen() Enc(k, m) Dec(k, c = (c0 , c1 , . . . , cℓ ))

$
1 : k←
−K 1 : m1 || . . . ||mℓ ← m, donde |mi | = r 1 : for i = 1, . . . , ℓ :
2 : return k 2 : c0 ←
$ d
− [0, 2 ), equiv. {0, 1} d 2 : yi ← F (k, c0 + i − 1 mod 2d )
3 : for i = 1, . . . , ℓ : 3 : mi ← yi ⊕ ci
4 : yi ← F (k, c0 + i − 1 mod 2 ) d 4 : m ← m1 || . . . ||mℓ
5 : ci ← yi ⊕ mi 5 : return m
6 : c ← (c0 , c1 , . . . , cℓ )
7 : return c
Si usamos una PRP/cifrado de bloques en lugar de F , Π es el modo de cifrado “counter mode”

(CTR).
m1 m2 m3 ···
$ +1 +1 +1
F (k, ·) F (k, ·) F (k, ·) ···
⊕ ⊕ ⊕
c0 c1 c2 c3 ···
Figure 6: Diagrama de Enc en PRF-CTR. Imagen adaptada de [Ros21, Construction 8.3], usada
con permiso del autor.
Comentario 27 El PRF-CTR puede ser paralelizado de manera simple, dado que los yi son
pueden ser calculados de manera independiente. Por lo tanto tiene muy buena eficiencia al cifrar
mensajes muy largos.
Comentario 28 Para descifrar, no es necesario “invertir” F . Esto sugiere que si m es largo

entre (ℓ − 1) · r y ℓ · r, se pueden “cortar” los últimos bits de yn en Enc, resultando en un cifrado
mas corto.
22
Clase 9: seguridad del cifrado “modo counter”
Teorema 5 Sean F , Π como en Definition 13. Si F es una (ε, t, q)-PRF, Π es (ε′ , t′ , q ′ )-IND-CPA
con t′ ≈ t, q ′ = q/ℓ, ε′ = 2 · ε + 2 · q 2 · ℓ/|D|.
Demostración. Dado un adversario A que juega ExpCPA , definimos B que juega ExpPRF ,
O
B O(·) E(m0 , m1 ) Enc
g (m)
$ O
1 : b̂ ←
− {0, 1} 1 : c ← Enc
g (m )
b̂ Lo mismo de Enc en Π,
2 : b̂′ ← AE () 2 : return c pero remplazando F (k, ·)
′
3 : return Jb̂ = b̂K con O(·)
Notamos que el entorno de A en ExpPRF (B, 0) es idéntico a la variante “bit-guessing” ExpCPA (A).
Sigue que
Pr[ExpPRF (B, 0) ⇒ 1] = Pr[ExpCPA (A) ⇒ 1].
Lamentablemente, no es claro como calcular Pr[ExpPRF (B, 1) ⇒ 1] directamente. Por lo tanto,
definimos un nuevo experimento Exp(B),
g idéntico a ExpPRF (B, 1) pero donde remplazamos el
oráculo O que le viene dado a B:
• En ExpPRF (B, 1), O(·) = R(·), una función muestreada aleatoriamente.
$
• En Exp(B),
g remplazamos O(·) con un algoritmo aleatorio R̂(x) = “return $ ← − {0, 1}r ”
r
que retorna elementos muestreados de U ({0, 1} ), ignorando el valor x en input. Esto quiere
decir que mientras Pr[R(x) ̸= R(x)] = 0, Pr[R̂(x) ̸= R̂(x)] = 1 − 2−r , en cuanto R̂ no es
una función.
Sea G := Pr[ExpPRF (B, 1) ⇒ 1] − Pr[Exp(B)
g ⇒ 1] . Definir Exp
g nos permite calcular,
Pr[ExpCPA (A) ⇒ 1] = Pr[ExpPRF (B, 0) ⇒ 1]
= Pr[ExpPRF (B, 0) ⇒ 1] − Pr[ExpPRF (B, 1) ⇒ 1] + Pr[ExpPRF (B, 1) ⇒ 1]

| {z }
= 0
≤ Adv(ExpPRF , B) + Pr[ExpPRF (B, 1) ⇒ 1] − Pr[Exp(B)

g ⇒ 1] + Pr[Exp(B)
g ⇒ 1]
| {z }
= 0
PRF
≤ Adv(Exp , B) + G + Pr[Exp(B)
g ⇒ 1]
Empezamos calculando Pr[Exp(B)

g ⇒ 1]. La vista de A en Exp(B)
g es tal que la i-esima query a E
retorna
E(m0,i , m1,i ) = (c0,i , mb̂,i,1 ⊕ R̂(zi,1 ), . . . , mb̂,i,j ⊕ R̂(zi,j ), . . . , mb̂,i,ℓ ⊕ R̂(zi,ℓ ))
donde zi,j = c0,i + j − 1 mod 2d , y donde R̂(zi,j ) ∼iid U ({0, 1}r ). En particular, esta vista es
independiente de b̂ dado que
Pr[m0,i,j ⊕ R̂(zi,j ) = cj,i ] = Pr[R̂(zi,j ) = cj,i ⊕ m0,i,j ]

= 2−r
= Pr[R̂(zi,j ) = cj,i ⊕ m1,i,j ]
= Pr[m1,i,j ⊕ R̂(zi,j ) = cj,i ].
$
Al ser la salida b̂′ ← AE () independiente de b̂ ←
− {0, 1},
1
Pr[b̂′ = b̂] = Pr[Exp(B)
g ⇒ 1] = ,
2
23
y de consecuencia
1
Adv(ExpCPA , A) = Pr[ExpCPA (A) ⇒ 1] − ≤ Adv(ExpPRF , B) + G.
2
Nos queda calcular G, la ventaja de distinguir ExpPRF (B, 1) de Exp(A). g Notamos que la sola
diferencia entre estos juegos es que R(·) es una función, por lo que R(x) es un valor fijo, y R̂ no.
Esta diferencia puede solo ser notada si O(·) viene llamado sobre un mismo input zi,j mas de una
vez durante el experimento.
Sea Z := “∃(i, j) ̸= (i′ , j ′ ) : zi,j = zi′ ,j ′ ” el evento por el cual O(·) viene llamado sobre un input
repetido durante el experimento. Notamos que ExpPRF (B, 1) y Exp(A) g son idénticos si Z no ocurre.
Por lo tanto, usando el lema de la diferencia,
G = Pr[ExpPRF (B, 1) ⇒ 1] − Pr[Exp(A)

g ⇒ 1] ≤ Pr[Z].
Sea colli,i′ el evento “hay una colisión entre {zi,1 , . . . , zi,ℓ } y {zi′ ,1 , . . . , zi′ ,ℓ }”. En particular, sea
esta zi,j = zi′ ,j ′ .
Por suposición, ℓ ≤ 2d /2. Esto quiere decir que
Pr[colli,i′ | i′ = i] = 0,
dado que no puede haber una colisión en {zi,j = c0,i + j − 1 mod 2d }ℓj=1 en cuanto ℓ elementos no
son suficientes para circular modulo 2d y colisionar. Por lo tanto
′ :0
Pr[colli,i′ ] = Pr[coll i,i
′ |
i = i ] Pr[i = i′ ] + Pr[colli,i′ | i ̸= i′ ] Pr[i ̸= i′ ] ≤ Pr[colli,i′ | i ̸= i′ ].

Supongamos entonces que i ̸= i′ . Queremos calcular la probabilidad de una colisión entre
(zi,1 , . . . , zi,ℓ ) y (zi′ ,1 , . . . , zi′ ,ℓ ).
ℓ –1 posiciones de colision
zi,1 zi,2 ... zi,ℓ

...
zi,1 zi,2 ... zi,ℓ
zi’,1 zi’,2 ... zi’,ℓ
zi,1 zi,2 ... zi,ℓ
...
zi,1 zi,2 ... zi,ℓ
zi,1 zi,2 ... zi,ℓ
ℓ posiciones de colision
Para que haya una colisión, zi,1 tiene que tener un valor que sobreponga las dos secuencias.
Solo hay 2 · ℓ − 1 tales valores posibles, lo que implica que Pr[colli,i′ | i ̸= i′ ] = 2·ℓ−1
2d
. Finalmente,
podemos calcular
 
q2 · ℓ

_ X q 2·ℓ−1 q · (q − 1) 2 · ℓ
Pr[Z] = Pr  colli,i′  ≤ Pr[colli,i′ ] ≤ d
≤ · d ≤ d
′ ′
2 2 2 2 2
i̸=i i̸=i
Con esto, podemos completar el calculo de la ventaja de A, recordando que
q2 · ℓ

Adv(ExpCPA , A) = 2·Adv(ExpCPA , A) ≤ 2· Adv(ExpPRF , B) + Pr[Z] ≤ 2· Adv(ExpPRF , B) + d ,
2
2·q 2 ·ℓ
lo que nos da t′ ≈ t, q ′ = q/ℓ, y ε′ = 2 · ε + 2d
. □
24
Comentario 29 Nuevamente vemos una diferencia en ventaja relacionada a una probabilidad de
colisión. Este tipo de ataque es verosı́mil, como en el caso del ataque https: // sweet32. info .
Finalmente podemos cifrar múltiples mensajes de ℓ “bloques” de r bits de largo. Si un mensaje es
> ℓ bloques, se lo puede transmitir como dos mensajes. Formalmente, se lo puede demostrar como
un lema.
Lemma 9 (fixed-length IND-CPA ⇒ variable-length IND-CPA) Sea Π = (Gen, Enc, Dec)
un SKES que otorga seguridad (ε, t, q)-IND-CPA. Sea Π′ = (Gen′ , Enc′ , Dec′ ) un SKES con
• Gen′ = Gen,
• Enc′ (k, (m1 , m2 )) := (Enc(k, m1 ), Enc(k, m2 )),

• Dec(k, (c1 , c2 )) := (Dec(k, c1 ), Dec(k, c2 )).
Π′ es (ε′ , t′ , q ′ )-IND-CPA.
EJERCICIO: Determina (ε, t, q).
25
Clase 10: adversarios activos e integridad de datos
5 Integridad de mensajes
Hasta ahora pudimos garantizar la seguridad si A se limita a observar cifrados en transito. Ahora
consideren el siguiente escenario
Cifrado interceptado y alterado

Alicia A Bob
Enc Dec
m 7−−→ c c 7→ c ⊕ ∆ c ⊕ ∆ 7−−→ m′ ̸= m
En este caso, un SKES no nos brinda garantı́as.
PREGUNTA: Alguien conoce algún método para chequear la integridad de datos?
Idea: Usar un checksum/hash.

Estas son funciones H : {0, 1}∗ → {0, 1}ℓ que “parecen aleatorias” (mas detalles luego).
Intento de autenticado con un hash

Alicia A Bob
Enc Dec
m 7−−→ (c, H(c)) c 7→ c ⊕ ∆ (c ⊕ ∆, H(c ⊕ ∆)) 7−−→ m′ ̸= m
H(c ⊕ ∆)
No funciona (a lo sumo, hashing ofrece “integridad sin adversarios”, aunque un código de

corrección de errores es una mejor solución a ese problema). Ideas?
Si proponen c||H(m):
• “Con acceso a OEnc , A puede c′ ← OEnc (m′ , m′ ) y transmitir c′ ||H(m′ ).
Idea: Y si... usamos una PRF?
Intento de autenticado con una PRF

Alicia A Bob
Enc Dec
m 7−−→ (c, PRF(k, c)) c 7→ c ⊕ ∆ (c ⊕ ∆, ??) 7−−→??
PRF(k, c ⊕ ∆)??
Para saber si funciona, necesitamos una definición de seguridad. Que sintaxis queremos? Sirve
para verificar la autenticidad de un “mensaje” (que puede ser un cifrado).
26
m∈M
τ ← Tag(k, m)
Tag Ver 1/0
Gen k∈K
Definición 14 (MAC) Sean M, T conjuntos, K un conjunto finito. Decimos que Π = (Gen, Tag, Ver)
es un código de autenticación de mensajes (MAC, “message authentication code”) con espacio de
llave K, de mensajes M, y de etiquetas (tags) T , si
• Gen es un algoritmo aleatorio Gen : ∅ → K,
• Tag es un algoritmo (posiblemente aleatorio) Tag : K × M → T ,

• Ver es un algoritmo (posiblemente aleatorio) Ver : K × M × T → {0, 1},
donde
∀k ∈ K, m ∈ M, Pr[Ver(k, m, Tag(k, m)) = 1] = 1.
Comentario 30 Para proteger comunicaciones, va a ser necesario transmitir un tag τ junto a los
datos transmitidos. Por eso, idealmente queremos que τ sea lo mas corto posible. Posiblemente |τ |
seria independiente de |m|.
Comentario 31 Un sistema con Tag determinista tiene la ventaja de que Ver es muy simple:
Ver(k, m, τ ) := JTag(k, m) = τ K.
Dada la sintaxis arriba, cualquier Π = (Gen, Tag, Ver) es un MAC si Ver(k, m, τ ) := 1. Necesi-
tamos definir una noción de seguridad para que “1 ← Ver(k, m, τ )” tenga un significado.
Definición 15 (MAC security) Sea Π = (Gen, Tag, Ver) un MAC con espacios K, M, T .
ExpMAC (A) T (m)

1 : k ← Gen() 1 : τ ← Tag(k, m)
2 : Q ← {} 2 : Q ← Q ∪ {(m, τ )}
∗ ∗ T : return τ
3 : (m , τ ) ← A () 3
∗ ∗
4 : // (m , τ ) ̸∈ Q
5 : b ← JVer(k, m∗ , τ ∗ ) = 1K
6 : return b
Decimos que Π es (ε, t, q)-fuertemente infalsificable en un ataque de mensajes elegidos (SUF-CMA,

“strongly unforgeable under chosen-message attacks”), si cualquier adversario A que corre en
tiempo ≤ t y usa ≤ q queries a T (·), y que retorna (m∗ , τ ∗ ) ̸∈ Q, tiene ventaja
Adv(ExpMAC , A) := Pr[ExpMAC (A) ⇒ 1] ≤ ε.
Comentario 32 Hay cosas que se pueden cuestionar en esta definición.

• A gana si genera un cualquier nuevo tag, inclusive sobre un mensaje que ha ya sido autenti-
cado. Que problema hay en generar una nueva etiqueta para algo que sabemos ser autentico?
• Al A le permitimos generar tags. Por que también no verificarlos? Podemos notar que para Π
con Ver(k, m, τ ) := JTag(k, m) = τ K, T (·) puede ser usado también para verificar. Usaremos
esta definición y tipo de MAC para simplificar la exposición. Mas allá de la estructura de
Ver, se puede demostrar que otorgarle oráculos de verificación al adversario no lo ayuda de
manera significativa [BS23, § 6.2].
27
• La noción le permite a A de mandar “replays” de mensajes previamente autenticados. Estas
no son falsificaciones, y de cualquier manera pueden si ser peligrosas para el usuario. Piensen
en el replay de una orden de compra.
Ahora si podemos demostrar que usar una PRF nos permite autenticar datos.
Lemma 10 (PRF ⇒ fixed-length MAC) Sea F : K × D → R una (ε, t, q)-PRF. Definimos un
MAC Π = (Gen, Tag, Ver)
Gen() Tag(k, m) Ver(k, m, τ )

$
1 : k←
−K 1 : τ ← F (k, m) 1 : τ ′ ← F (k, m)
2 : return k 2 : return τ 2 : return Jτ ′ = τ K
Π es un MAC con espacio de claves K, de mensajes M = D, y de tags T = R. Π ofrece (ε′ , t′ , q ′ )-

seguridad MAC con ε′ = ε + |R|
1
, t′ ≈ t, q ′ = q − 1.
Demostración. Construimos un adversario B que juega ExpPRF .
B O () T (m)
∗ ∗ T
1 : (m , τ ) ← A () 1 : τ ← O(m)
∗ ∗
2 : if O(m ) = τ : 2 : return τ
3 : return 0 (“PRG′′ )
4 : else :
5 : return 1 (“random′′ )
Consideremos ExpPRF (B, 1), donde O es una función realmente aleatoria, R.
Pr[ExpPRF (B, 1) ⇒ 0] = Pr[R(m∗ ) = τ ∗ ].
Por definición de seguridad MAC, A retorna un par (m∗ , τ ∗ ) no visto antes. Dado que R tiene una
sola imagen de m∗ , A tiene que nunca haber evaluado R(m∗ ) para poderlo retornar. Por ende,
tuvo que adivinar el valor τ ∗ ∈ R. Dado que R es una función aleatoria, Pr[R(m∗ ) = τ ∗ ] = |R|
1
.
Ahora consideramos ExpPRF (B, 0). Aquı́ O = F (k, ·), una PRF. Por construcción, el entorno
de A dentro de B en ExpPRF (B, 0) es idéntico al de A en ExpMAC , cuando el Tag(k, ·) = F (k, ·).
Sigue que
Pr[ExpPRF (B, 0) ⇒ 0] = Pr[F (k, m∗ ) = τ ∗ ] = Pr[Ver(k, m∗ , τ ∗ ) = 1] = Pr[ExpMAC (A) ⇒ 1].
Usando la desigualdad triangular,
A(ExpMAC , A) = Pr[ExpMAC (A) ⇒ 1]

= Pr[ExpPRF (B, 0) ⇒ 0]
= Pr[ExpPRF (B, 0) ⇒ 0] − Pr[ExpPRF (B, 1) ⇒ 0] + Pr[ExpPRF (B, 1) ⇒ 0]

PRF
≤ 1 − Pr[Exp (B, 0) ⇒ 1] − 1 − Pr[ExpPRF (B, 1) ⇒ 1] + Pr[ExpPRF (B, 1) ⇒ 0]
= Adv(ExpPRF , B) + Pr[ExpPRF (B, 1) ⇒ 0]

1
= Adv(ExpPRF , B) +
|R|
Dado que A y B corren en tiempos parecidos, y que B hace una query mas a O que A a T , Π es
(ε′ , t′ , q ′ )-MAC con ε′ = ε + |R|
1
, t′ ≈ t, q ′ + 1 = q. □
Comentario 33 Un MAC con espacios de mensajes {0, 1}d con d < ∞ (“fixed-length”), puede
ser limitante en la mayor parte de los casos. Hay varias maneras de extender la amplitud de los
mensajes. Vamos a ver una técnica que utiliza funciones de hash.
28
Clase 11: seguridad informal y uso de funciones de
hash
6 Funciones de hash
Las funciones de hash son el primitivo criptográfico probablemente mas conocido. Si alguna vez
intentarlo programar el login de una pagina web, probablemente las hayan encontrado (MD5,
SHA1–3 las mas conocidas). Son también un primitivo a menudo usado incorrectamente, poniendo
cuentas online en riesgo.
Definición 16 (Hash, informal) Una función H : {0, 1}∗ → {0, 1}ℓ se dice de “hash criptografico”
si satisface las siguientes propiedades:
• Puede ser implementada con un algoritmo determinista eficiente.
• “Preimage resistance”: dado h ∈ {0, 1}ℓ , es difı́cil encontrar x tal que H(x) = h.
• “Second preimage resistance”: dado (x, H(x)), es difı́cil encontrar x′ ̸= x tal que H(x′ ) =
H(x).
• “Collision-resistance” (CR): es difı́cil encontrar x ̸= x′ tal que H(x) = H(x′ ).
Comentario 34 Por que definiciones informales? Por que para cada propiedad, existen adver-
sarios eficientes! Por ejemplo:
• CR: dado que |{0, 1}∗ | > {0, 1}ℓ , colisiones existen necesariamente. Como H es una
función‘ fija, supongamos que x, x′ sean una colisión. A := return (x, x′ ) es un algoritmo
eficiente que retorna una colisión con probabilidad 1. Simplemente, no lo conocemos.
• Preimage resistance: es común que funciones de hash sean evaluadas en inputs de baja en-
tropı́a, predecibles. Por lo tanto es plausible que en una aplicación practica, dado h, un
algoritmo pueda retornar x tal que H(x) = h. Esta falta de entropı́a en entrada diferencia
“preimage resistance” de la definición de “seguridad PRG”.
• La falta de entropı́a en las entradas también impide una definición de second preimage resis-
tance.
Sin definiciones formales, demostrar seguridad de construcciones que las usan no es comple-
tamente posible. A menudo usamos el “modelo del oráculo aleatorio” (ROM, “random oracle
model”), que asume que H es una función completamente aleatoria. Alternativamente, algunos
textos asumen que el hash toma en input una clave, aunque en realidad no es ası́.
Lemma 11 (informal) Sea H una función de hash.

1. Collision resistance ⇒ second-preimage resistance.
2. Second-preimage resistance ⇒ preimage resistance.
3. Collision resistance ⇒ preimage resistance.
4. Collision resistance ̸⇒ “partial” preimage resistance.
Demostración. (informal) Por casos:

1. Sea A un adversario que rompe second-preimage resistance: dado (x, H(x)) retorna x′ ̸= x
tal que H(x′ ) = H(x). Podemos elegir un x ∈ {0, 1}∗ cualquiera, calcular x′ ← A(x, H(x)).
Siendo el espacio de input infinito, es improbable que x = x′ . Por lo tanto podemos retornar
una colisión (x, x′ ).
2. Sea B un adversario que rompe preimage resistance: dado h retorna x tal que H(x) = h.
En input (x, H(x)) podemos calcular x′ ← B(H(x)). Siendo el dominio de H infinito,
probablemente x ̸= x′ , y pudimos encontrar una second preimage.
29
3. Sea B como arriba. El mismo razonamiento da una colisión, si elegimos nosotros x en primer
lugar.
4. Mas allá del punto 3., es posible construir funciones que son collision resistant y por lo
tanto “preimage resistant”, pero para las cuales si existe un adversario que rompe preimage
resistance sobre un subconjunto bien definido del espacio
( de input.
0||x si |x| = n,
Sea G una función de hash CR. Definimos H(x) := Por inspección, H
1||G(x) si |x| = ̸ n.
es CR dado que colisiones donde H(x) = 0 . . . son imposibles y colisiones con H(x) = 1 . . .
implican colisiones en G. Sin embargo, si h = H(x) = 0 . . . , |h| = n + 1, x puede ser
recuperado a partir de h.
□
x= x1 x2 x3 ··· xk |x|
h h h ··· h h MDh (x)

y0
Figure 7: Una manera común de construir funciones de hash es usando PRPs o PRFs iteradas
según el diseño de Merkle-Damgard (MD). Imagen tomada de [Ros21, Construction 11.2], usada
con permiso del autor.
Lemma 12 (fixed-length MAC + CR hash ⇒ arbitrary-length MAC, hash-then-MAC)

Sea Π = (Gen, Tag, Ver) un fixed-length (ε′ , t′ , q ′ )-MAC con M = {0, 1}ℓ , y H : {0, 1}∗ → {0, 1}ℓ
un CR-hash. Definimos un MAC Π′ = (Gen′ , Tag′ , Ver′ ),
Gen′ () Tag′ (k, m) Ver′ (k, m, τ )

$
1 : k←
− Gen 1 : h ← H(m) 1 : h ← H(m)
2 : return k 2 : τ ← Tag(k, h) 2 : b ← Ver(k, h, τ )
3 : return τ 3 : return b
Π′ ofrece (ε′ , t′ , q ′ )-seguridad MAC con t′ ≈ t, q ′ = q, ε′ ≤ ε + Pr[coll], donde coll es la probabilidad

que un adversario contra Π produzca una colisión en H.
Demostración. Usamos un adversario A contra Π′ para definir un adversario B contra Π.
BT O(m)
1 : Q ← { }, S ← { } 1 : h ← H(m)
∗ ∗ O : τ ← T (h)
2 : (m , τ ) ← A () 2
∗ ∗ : Q ← Q ∪ {(h, τ )}
3 : h ← H(m ) 3
∗ ∗ : S ← S ∪ {(m, τ )}
4 : if (h , τ ) ∈ Q : 4
5 : return (⊥, ⊥) 5 : return τ

∗ ∗
6 : else return (h , τ )
NB: El conjunto S (en gris) simplifica el análisis, pero no es requerido por B.

Empezamos expandiendo la ventaja de A contra Π′ en términos de Π.
Adv(ExpMAC , A) = Pr[ExpMAC (A) ⇒ 1] = Pr[Ver′ (k, m∗ , τ ∗ ) ⇒ 1]

= Pr[Ver(k, H(m∗ ), τ ∗ ) ⇒ 1] = Pr[Ver(k, h∗ , τ ∗ ) ⇒ 1]
(
∗ ∗ ((((∗ ∗
((((
= Pr[Ver(k,( h( , τ() ⇒ 1 | (h , τ ) ∈ Q] · Pr[(h∗ , τ ∗ ) ∈ Q]
(((( ∗ ∗
+ Pr[Ver(k, h , τ ) ⇒ 1 | (h∗ , τ ∗ ) ̸∈ Q] · ( ∗ ∗((( (
Pr[(h
((,( τ ) ̸∈ Q]
≤ Pr[(h∗ , τ ∗ ) ∈ Q] + Pr[Ver(k, h∗ , τ ∗ ) ⇒ 1 | (h∗ , τ ∗ ) ̸∈ Q]
Luego notamos que si (h∗ , τ ∗ ) ̸∈ Q, entonces B es un adversario valido para ExpMAC respecto a Π,
dado que retorna una nueva falsificación. Por lo tanto,
Pr[Ver(k, h∗ , τ ∗ ) ⇒ 1 | (h∗ , τ ∗ ) ̸∈ Q] = Pr[ExpMAC (B) ⇒ 1] = Adv(ExpMAC , B).
30
De otro modo, supongamos que (h∗ , τ ∗ ) ∈ Q. Por suposición de que A juega ExpMAC contra
Π′ , sabemos que retorna una nueva falsificación (m∗ , τ ∗ ) ̸∈ S = {(mi , τi )}i . Aplicando H a los
mensajes retornados y “quieriados” por A, sigue que
(H(m∗ ), τ ∗ ) = (h∗ , τ ∗ ) ∈ Q = {(H(mi ), τi )}i =⇒ ∃mi ̸= m∗ tal que H(mi ) = H(m∗ ).
Lo que quiere decir que B encuentra una colisión en H, usando m∗ . =⇒ Pr[(h∗ , τ ∗ ) ∈ Q] ≤ Pr[coll].
Juntando las tres desigualdades,
Adv(ExpMAC , A) ≤ Pr[(h∗ , τ ∗ ) ∈ Q] + Pr[Ver(k, h∗ , τ ∗ ) ⇒ 1 | (h∗ , τ ∗ ) ̸∈ Q]

≤ Pr[coll] + Adv(ExpMAC , B).
Por inspección de A y B, t′ ≈ t, q ′ = q y ε′ = ε + Pr[coll].

□
Comentario 35 Requerir un MAC y un hash construidos de manera independiente puede ser

costoso en hardware. Construcciones tipo HMAC se especializan en construir hash-then-MAC
compactos a partir de funciones de hash de tipo Merkle-Damgard.
6.1 Side quest: hashing de contraseñas

Imaginen tener que desarrollar un sistema de login para una pagina web.
Idealmente: quieren investigar como se usan las librerı́as de “2-factor autentication”, y pro-
tocolos tipo FIDO.
Tradicionalmente, se usan contraseñas. Los siguientes son dos escenarios comunes e inseguros.
• El servidor guarda una base de datos con una tabla
usuario clave
[email protected] “messi10”
.. ..
. .
Cual es el problema? Probablemente Maria utiliza esa clave en otras paginas. Si el server
viene vulnerado y el DB es leakeado, A podrı́a obtener acceso a cuentas mas importantes.
• (Solución que se encuentra en muchos, pésimos, tutoriales):
usuario clave
[email protected] H(“03/14/1994”)
.. ..
. .
SHA-256(“03/14/1994”) = ac144fd70bcfcc4a2aa2cd97c4221b82ad03c5fe05c8347fa3e6f29b1e0a36ca,
y H es preimage- y collision-resistant, por lo cual recuperar la clave (o una equivalente) es
difı́cil. Cual es el problema?
1. H es una función fija

2. La clave tiene “poca entropia”.
Si A leakea el DB, puede comparar los hashes con valores de input comunes para los cuales
precomputó el output. Tablas de tales valores se llaman comúnmente “rainbow tables”.
Software tipo “John the Ripper”6 puede ser usado junto a rainbow tables para recuperar
inputs. Si A conoce H(“01/01/1900”), H(“02/01/1900”), . . . , H(“31/12/2024”), va a poder
reconocer la clave de Jorge en el DB.
Ahora dos soluciones validas:
6 https://www.openwall.com/john/
31
• “salt and hash”,
usuario salt clave

$ ℓ
[email protected] s←
− {0, 1} H(s||“mafalda”)
$
[email protected] s′ ←
− {0, 1}ℓ H(s′ ||“dragonball”)
.. .. ..
. . .
$
Al registrar cada usuario, una nueva cadena aleatoria (salt) s ←− {0, 1}ℓ es generada. El
hash es hecho sobre “s||clave”, y el resultado es guardado junto al salt. De esta manera
el login puede ser verificado, pero cada usuario recibe una función de hash “diferente”. Es
improbable que el adversario haya precomputado H(s||x), para el s especifico del usuario,
volviendo el ataque mas improbable (aunque x tenga poca entropı́a, s||x tiene mucha).
Nota: esta es una estrategia “folclórica”. No hemos demostrado seguridad, en cuanto no
tenemos una definición de seguridad. Formalizaciones y demostraciones sobre este escenario
son muy recientes (Farshim & Tessaro [FT21], EUROCRYPT 2021).
• Aun mejor: “salt and hash”, donde el hash es una función diseñada para guardar contraseñas:
Argon2 (IETF RFC9106).
Comentario 36 No hay salt and hash bueno lo suficiente para protegerte del usar una clave
previsible como “dragonball”. De otra parte, las soluciones de password managing pueden ser
complicadas para el usuario común. Por esa razón, soluciones “multi-factor” son recomendables.
32
Clase 12: confidencialidad e integridad, el cifrado
autenticado
7 Cifrado Autenticado
Resumen: hemos conseguido
• cifrados para mensajes múltiples y arbitrariamente largos
• MACs para cadenas de bits arbitrariamente largas
Que nos falta: integrar ambos mecanismos.
Vamos a protegernos de ambos escenarios limitando la posibilidad de A de modificar cifrados.
Definición 17 (INT-CTXT) Sea ⊥ un sı́mbolo que indica rechazo. Sea Π = (Gen, Enc, Dec) un
SKES con ⊥ ∈ M, tal que Dec puede retornar ⊥ si recibe un cifrado no valido.
ExpCTXT (A) E(m)

$
1 : k←
− Gen() 1 : c ← Enc(k, m)
2 : Qc ← {} 2 : Qc ← Qc ∪ {c}
3 : c∗ ← AE () 3 : return c
∗
4 : // c ̸∈ Qc
5 : m∗ ← Dec(k, c∗ )
6 : b ← Jm∗ ̸= ⊥K
7 : return b
Decimos que Π otorga (ε, t, q)-integridad de cifrado (INT-CTXT, “ciphertext integrity”), si cualquier
adversario A que corre en tiempo ≤ t y hace ≤ q queries a O, y que retorna c∗ ̸∈ Qc , tiene ventaja
Adv(ExpCTXT , A) := Pr[ExpCTXT (A) ⇒ 1] ≤ ε.

Comentario 37 Claramente, PRF-CTR no satisface INT-CTXT, dado que (c0 , c1 ⊕ ∆) descifra
a m ⊕ ∆ para cualquier ∆.
Definición 18 (AE) Sea Π un SKES. Decimos que Π otorga cifrados (εCPA , εCTXT , t, q)-autenticados
(AE, “authenticated encryption”), si otorga seguridad (εCPA , t, q)-IND-CPA y (εCTXT , t, q)-INT-
CTXT.
Comentario 38 Bajo definición de seguridad AE, A no puede distinguir entre cifrados de men-
sajes diferentes por IND-CPA, y no puede tampoco generar nuevos cifrados validos (de la nada, o
modificando cifrados que obtuvo a través de un oráculo de cifrado) por INT-CTXT.
Comentario 39 Un SKES que otorga AE, también otorga una noción que no vamos a explorar
de inmediato, IND-CCA. ExpCCA es igual a ExpCPA , pero A tiene acceso a oráculos de cifrado
E(m0 , m1 ) y de descifrado D(c), donde el segundo puede ser utilizado solamente para descifrar
cifrados no retornados por E(·, ·). En el ámbito de la criptografı́a simétrica, AE ⇒ IND-CCA
dado que A no puede generar cifrados validos a menos de no obtenerlos de E(·, ·).
Definición 19 (EtM) Sean Π = (GenΠ , Enc, Dec) un SKES, y Σ = (GenΣ , Tag, Ver) un MAC.
Definimos el SKES Π′ = (Gen′ , Enc′ , Dec′ ) “encrypt-then-MAC” (EtM).
Gen′ () Enc′ (k, m) Dec′ (k, c)

1 : ke ← GenΠ () 1 : (ke , km ) ← k 1 : (ke , km ) ← k
Σ : ce ← Enc(ke , m) : (ce , τ ) ← c
2 : km ← Gen () 2 2
3 : k ← (ke , km ) 3 : τ ← Tag(km , ce ) 3 : b ← Ver(km , ce , τ )

4 : return k 4 : c ← (ce , τ ) 4 : m ← Dec(ke , ce )
5 : return c 5 : if b = 1 :
6 : return m
7 : else return ⊥
33
Lemma 13 Sean Π, Σ, Π′ como en Definition 19. Supongamos que Π otorga (εCPA , t, q)-IND-
CPA y Σ otorga (εMAC , t, q)-MAC. Entonces Π′ otorga (ε′CPA , ε′CTXT , t′ , q ′ )-AE con ε′CPA = εCPA ,
ε′CTXT = εMAC , t′ ≈ t, q ′ = q.
Demostración. Por definición de AE, necesitamos demostrar que

• Π′ otorga (ε′CPA , t′ , q ′ )-IND-CPA,
• Π′ otorga (ε′CTXT , t′ , q ′ )-INT-CTXT.

IND-CPA: Podria parecer “obvio”, dado que un cifrado de Π′ incluye un cifrado de Π. (Vamos
a ver que no siempre esto es inmediato). Dado un adversario A contra Π′ que juega ExpCPA ,
construimos B contra Π que juega ExpCPA ,
B E () O(m0 , m1 )
Σ
1 : km ← Gen () 1 : ce ← E(m0 , m1 )
′ O : τ ← Tag(km , ce )
2 : b ← A () 2
′ 3 : c ← (ce , τ )
3 : return b
4 : return c
Del punto de vista de AO , el ambiente dentro de B es idéntico al de ExpCPA (A, b). Dado que B
retorna el output de A,
Pr[ExpCPA (B, b) ⇒ 1] = Pr[ExpCPA (A, b) ⇒ 1], ∀b ∈ {0, 1}.
De consecuencia, Adv(ExpCPA , B) = Adv(ExpCPA , A), t′ ≈ t y q ′ = q, y Π′ otorga (εCPA , ≈ t, q)-

IND-CPA.
INT-CTXT: Ahora supongamos que un adversario A contra ExpCTXT , y construyamos B contra

ExpMAC .
B T () O(m)
Π
1 : ke ← Gen () 1 : ce ← Enc(ke , m)
∗ O : τ ← T (ce )
2 : c ← A () 2
3 : (c∗e , τ ∗ ) ← c∗ 3 : c ← (ce , τ )
4 : // c∗e es el mensaje “tagueado” 4 : return c
5 : return (c∗e , τ ∗ )
Por definición de seguridad INT-CTXT, A retorna c∗ ̸∈ Qc . Dado que Π′ produce cifrados c =

(ce , Tag(km , ce )), podemos usar A para generar un par (m∗ , τ ∗ ) donde m∗ ← c∗e . De tal manera,
notamos que Qc en ExpCTXT corresponde a Q en ExpMAC , dado que cada cifrado generado por
O(·) corresponde a un tag generado en T (·). Por lo tanto,
c∗ = (c∗e , τ ∗ ) ̸∈ QC en ExpCTXT ⇒ (m∗ = c∗e , τ ∗ ) ̸∈ Q en ExpMAC ,
y B es un adversario valido bajo la definición de seguridad MAC.

también observamos que el entorno de A en B es idéntico a su entorno en ExpCTXT . Sigue que
podemos calcular
Pr[ExpMAC (B) ⇒ 1] = Pr[Ver(k, m∗ , τ ∗ ) = 1] (en ExpMAC )

= Pr[Ver(km , c∗e , τ ∗ ) = 1] (en ExpCTXT de Π′ ).
Por definición de m = Dec′ (km , c = (ce , τ )), ‘Ver(km , ce , τ ) = 0’ ⇒ ‘m = ⊥’. Por contra-positivo,
es equivalente que ‘m ̸= ⊥’ ⇒ ‘Ver(km , ce , τ ) = 1’. Sigue que
Pr[ExpMAC (B) ⇒ 1] = Pr[Ver(km , c∗e , τ ∗ ) = 1] ≥ Pr[m∗ ̸= ⊥] = Pr[ExpCTXT (A) ⇒ 1].
Por lo tanto, tenemos ε′CTXT ≤ εMAC , y por construcción de B, t′ ≈ t, q ′ = q, y Π′ otorga

(εMAC , ≈ t, q)-INT-CTXT.
Y por lo tanto, Π′ otorga (εCPA , εMAC , ≈ t, q)-AE. □
34
Comentario 40 Si definiéramos la seguridad MAC de manera que a A le fuera permitido generar
nuevos tags τ ′ a partir de un mensaje ya etiquetado por T (·) (o sea, el MAC no serı́a “fuertemente”
infalsificable), el resultante cifrado EtM no otorgarı́a AE. Esto es porque A podrı́a ver un valido
cifrado c = (ce , τ ) y generar un nuevo cifrado c′ = (ce , τ ′ ). Esto podrı́a ser un problema en el
caso especifico de EtM, pero la definición de IND-CTXT es general, y no tendrı́a que solamente
funcionar para EtM.
Ejemplo 3 Combinar esquemas AE puede no otorgar trivialmente AE. Considérese el esquema

natural obtenido concatenando cifrados: Enc′ (k, m1 ||m2 ) := Enc(k, m1 )||Enc(k, m2 ), donde Enc
es parte de un SKES que otorga AE, y cada componente del cifrado c = (c1 , c2 ) es descifrado
individualmente. Este sistema no otorga AE, por que?
Dado un cifrado (c1 , c2 ) valido, el cifrado (c2 , c1 ) es también valido. Esto quiere decir que A
puede generar nuevos cifrados validos, invalidando INT-CTXT.
Comentario 41 AE nos permite de detectar si un cifrado es autentico. Pero no impide que A

reordene, elimine o repita cifrados en transito desde Alicia a Bob. Sin embargo, podemos intentar
detectar este tipo de ataque en el nivel aplicativo, definiendo números de secuencia. Esto general-
mente resulta en consideraciones dependientes de la aplicación, y que pueden encontrarse al menos
parcialmente fuera del dominio de la criptografı́a.
Comentario 42 En algunas aplicaciones a nivel de red, puede ser necesario transmitir datos cifra-
dos, junto a meta-datos (e.g., “packet headers”) públicos. Por ejemplo, los meta-datos podrı́an
ser útiles para “routear” los paquetes de datos. En esta situación, una primitiva conocida como
“authenticated encryption with associated data” (AEAD) puede ser útil. Esta garantiza confiden-
cialidad de datos, e integridad del cifrado y de los meta-datos. Los dos AEAD mas famosos son
AES-GCM y Chacha20-Poly1305.
Definición 20 (Un AEAD de ejemplo) Sean Π = (GenΠ , Enc, Dec) un SKES, Σ = (GenΣ , Tag, Ver)
un arbitrary-length MAC. Definimos un AEAD
Gen′ () Enc′ (k, d , m) Dec′ (k, d , c)

1 : ke ← GenΠ () 1 : (ke , km ) ← k 1 : (ke , km ) ← k
Σ
2 : km ← Gen () 2 : ce ← Enc(ke , m) 2 : (ce , τ ) ← c
3 : k ← (ke , km ) 3 : τ ← Tag(km , d ||ce ) 3 : b ← Ver(km , d ||ce , τ )
4 : return k 4 : return (ce , τ ) 4 : m ← Dec(ke , ce )
5 : if b = 1 :
6 : return m
7 : else return ⊥
Comentario 43 No proponemos una definición de seguridad AEAD. Invitamos el lector a con-

sultar [BS23, § 9.5].
Con esto terminamos la componente simétrica. Hemos aprendido a cifrar y transmitir cifrados
de manera segura entre dos partes Alicia y Bob que comparten una misma clave secreta k. Pero
como pueden llegar Alicia y Bob a compartir tal clave? Claro, podrı́an compartirla de antemano de
persona, de manera de estar seguras que ningún adversario A pueda verla, pero esto no es conve-
niente. Todos los dı́as navegamos a paginas web, posiblemente por la primera ves, y hacemos pagos
online con diferentes entidades. Pre-compartir claves con todas seria prácticamente imposible.
En la segunda parte del curso vamos a ver como transmitir mensajes de manera segura a
entidades con las cuales no nos hemos nunca comunicado.
35
Clase 13: preliminares matemáticos II
8 Grupos, y Suposiciones de Dificultad

A la base de gran parte de la PKC hay objetos de naturaleza algebraica: grupos, anillos, cuerpos.
Nosotros vamos a intentar cubrir la menor cantidad posible, quedando cerca de lo utilizado en la
practica.
Definición 21 (grupo abeliano) Sea G un un conjunto, × una operación binaria × : G × G →

G. Decimos que G = (G, ×) es un grupo abeliano si
1. × es asociativa: (a × b) × c = a × (b × c), ∀a, b, c ∈ G.
2. Existe un elemento neutro e ∈ G tal que a × e = e × a = a, ∀a ∈ G.
3. Cada elemento a tiene un inverso a−1 , tal que a × a−1 = a−1 × a = e, ∀a ∈ G.
4. × es conmutativa: a × b = b × a, ∀a, b ∈ G.
Si |G| ≤ ∞, decimos que G es finito, y que |G| es el orden de G. A menudo abusamos notación y
escribimos a ∈ G en lugar de a ∈ G.
Ejemplo 4 • (Z, +) es un grupo abeliano

• (Z, ·) no es un grupo abeliano. (Q, ·) tampoco. (Q\{0}, ·) lo es. (R\{0}, ·) también.
• Sea Zn el conjunto de los enteros “modulo n”. (Zn , +) es un grupo abeliano.
Comentario 44 En un grupo podemos “exponenciar”: si a ∈ G, an := a × a × · · · × a (n veces).

Las comunes reglas valen:
• an × am = an+m ,
• (an )m = anm = amn = (am )n ,
• a1 · a−1 = a0 = e.
En el caso de un grupo donde usamos “+”, como (Z, +), el exponente es un factor: a + · · · +
a (n veces) = n × a.
Definición 22 (subgrupo) Sea G = (G, ×) un grupo, y sea S ⊂ G un subconjunto de G. Si

S = (S, ×) forma un grupo, decimos que S es un subconjunto de G.
Ejemplo 5 Sea G = (Z, +). S = (2Z, +) = ({2n | n ∈ Z}, +) es un subgrupo de G.
Definición 23 (grupo cı́clico) Un grupo G = (G, ×) se dice cı́clico si existe g ∈ G tal que el
grupo ⟨g⟩ “generado” g,
⟨g⟩ := ({g n | n ∈ Z}, ×),
es G, o sea G = ⟨g⟩.
Ejemplo 6 (Z, +) es cı́clico, y generado por ±1.
Lemma 14 Dado un grupo G = (G, ×) de orden primo |G| = p, G es cı́clico y generado por
cualquier elemento no neutro.
Ejemplo 7 (Zp , +) es cı́clico. Cualquier 1 ≤ g < p lo genera. Por ejemplo, sea p = 3.
1 es un generador 2 es un generador
1 mod 3 = 1 2 mod 3 = 2
1+1 mod 3 = 2 2+2 mod 3 = 4 mod 3 = 1
1+1+1 mod 3 = 3 2+2+2 mod 3 = 6 mod 3 = 0
1 + 1 + 1 + 1 mod 3 = 4 mod 3 = 1 2+2+2+2 mod 3 = 8 mod 3 = 2
36
Aquı́ podrı́amos adentrarnos en mas detalles sobre los grupos usados en criptografı́a, pero se
vuelve muy matemático. En su lugar, vamos a definir tres problemas matemáticos relacionados, y
un postulado. En criptografı́a, usamos familias de grupos que satisfacen el postulado.
Definición 24 (DLOG, informal) Sea G un grupo cı́clico. Dados g, h ∈ G, el problema del

logaritmo discreto (DLOG, “discrete logarithm”) requiere recuperar x ∈ Z tal que g x = h, o sea
“x = logg h”.
Comentario 45 DLOG es fácil de resolver en (Z, +) y (R\{0}, ×):

• (Z, +): recordando que “g x ” es x · g, x · g = h ⇐⇒ x = h/g.
• (R\{0}, ×): g x = h ⇐⇒ x = logg h, donde log es el logaritmo “comun”.
$
Definición 25 (CDH, informal) Sea G un grupo cı́clico finito con generador g. Sean x ←
− [|G|],
$
y←− [|G|] muestreados independientemente. El problema computacional de Diffie-Hellman (CDH,
“computational Diffie-Hellman”) requiere, dados (g, g x , g y ), calcular g xy = (g x )y = (g y )x .
Comentario 46 CDH no puede ser mas difı́cil de DLOG (o sea, resolver DLOG ⇒ resolver
CDH). Supongamos que O es un oráculo que calcula (g, g x ) 7→ x. Dados (g, g x , g y ), calculamos
x
(g y )O(g,g ) = (g y )x = g xy .
Lemma 15 Sea G = ⟨g⟩ un grupo finito. Dada la variable aleatoria z ∼ U ([|G|]), g z es una
variable aleatoria g z ∼ U (G).
Demostración.
1
∀h ∈ G, Pr [g z = h] = Pr[z = logg h] = .
z∼U ([|G|]) |G|
□5
Definición 26 (DDH) Sea G = ⟨g⟩ un grupo cı́clico. Para simplificar notación, supongamos que
g es un “parámetro publico”, o sea un elemento fijo y disponible públicamente. Definimos el juego
ExpDDH .
ExpDDH (A, b)
$
1 : x←
− [|G|]
$
2 : y←
− [|G|]
3 : if b = 0
4 : z ←x·y
5 : else
$
6 : z←
− [|G|]
7 : b′ ← A(g x , g y , g z )
8 : return b′
Decimos que DDH es (ε, t)-difı́cil en G si cualquier adversario A que corre en tiempo ≤ t tiene
ventaja
A(ExpDDH , A) := Pr[ExpDDH (A, 0) ⇒ 1] − Pr[ExpDDH (A, 1) ⇒ 1] ≤ ε.
Finalmente introducimos un nuevo postulado:

Postulado 3 Para cualquier valor de (ε, t), existe un grupo cı́clico finito G tal que DDH es (ε, t)-
difı́cil en G.
Comentario 47 Por motivos criptoanalı́ticos, es generalmente deseable que G tenga orden primo.
37
Clase 14: intercambio de claves de Diffie–Hellman
38
Clase 15: cifrado de clave publica “one-time”
9 Cifrado de Clave Publica

Como en el caso simétrico, empezamos definiendo nociones de cifrado.
Definición 27 (PKES, cifrado asimétrico o de clave publica) Sean Kp , Ks , M, C conjun-

tos. Decimos que Π = (Gen, Enc, Dec) forman un cifrado asimétrico o de clave publica (PKES,
“public-key encryption scheme”) con espacio de claves publicas Kp , de claves privadas Ks , de
mensajes M, y de cifrados C, si
• Gen es un algoritmo aleatorio, Gen : ∅ → Ks × Kp que retorna una tupla (sk, pk). Decimos
que sk es una clave privada, o secreta, (“secret key”) y que pk es una clave publica (“public
key”).
• Enc es un algoritmo (posiblemente aleatorio), Enc : Kp × M → C.
• Dec es un algoritmo determinista Dec : Ks × C → M.
Decimos que Π es δ-correcto si
Pr[Dec(sk, Enc(pk, m; $)) ̸= m] ≤ δ,

(sk,pk)∼Gen(),
$ en Enc
donde Gen, Enc y Dec son “eficientes” (corren en tiempo ≈ log2 (|m|)).
Comentario 48 Al definir SKES, requerimos que fueran δ-correcto con δ = 0. No es ası́ con
PKES, porque varias técnicas para construir PKE resulta en sistemas eficientes si δ ≳ 0 pero
menos eficientes con δ = 0. En el curso vamos a ver solo sistemas con δ = 0.
Comentario 49 En nuestra definición usamos conjuntos M y C. En practica, es común que al

generar claves, implı́citamente fijemos Mpk ⊂ M y Cpk ⊂ C donde se encuentran los mensajes y
cifrados.
Comentario 50 Diferentemente de SKE, a menudo Ks , Kp , M, C no son conjuntos de cadenas

de bits.
Muchas de las ideas desarrolladas para SKE pueden ser adaptadas a PKE. Una diferencia
crucial es que A recibe pk, al ser una clave publica, y esto le permite cifrar mensajes sin requerir
un oráculo.
Definición 28 (OT-IND-CPA) Sea Π = (Gen, Enc, Dec) un PKES.
ExpOT-CPA (A, b) O(m0 , m1 )

1 : (sk, pk) ← Gen() 1 : if disabled = 1 :
2 : disabled ← 0 2 : return ⊥
3 : b′ ← AO (pk) 3 : disabled ← 1
4 : return b′ 4 : c∗ ← Enc(pk, mb )
5 : return c∗
Decimos que Π otorga one-time (ε, t)-indistinguibilidad bajo ataques de mensaje elegido (OT-IND-
CPA, “one-time indistinguishibility under chosen-plaintext attacks”), si cualquier adversario A que
corre en tiempo ≤ t tiene ventaja
Adv(ExpOT-CPA , A) := Pr[ExpOT-CPA (A, 0) ⇒ 1] − Pr[ExpOT-CPA (A, 1) ⇒ 1] ≤ ε.
Comentario 51 Aunque esta definición le ofrece a A un solo cifrado para distinguir b, a menudo
la preferimos a una definición que ofrezca q ≥ 1 cifrados. Esto es porque demostrar OT-CPA es
mas fácil, y porque OT-IND-CPA ⇒ IND-CPA.
39
Vamos ahora a definir el PKES de ElGamal. Puede ser visto como una versión no interactiva
del KEX de Diffie-Hellman.
Definición 29 (ElGamal PKE) Sea G = (G, ×) un grupo cı́clico generado por g. Sean Ks =
[|G|], Kpk = M = C = G.
Gen() Enc(pk = g x , m) Dec(sk = x, c = (c0 , c1 ))

$ $
1 : x←
− [|G|] 1 : y←
− [|G|] 1 : m′ ← c1 × c−x
0
2 : sk ← x 2 : c0 ← g y
2 : return m′
3 : pk ← g x 3 : c1 ← (g x )y × m
4 : return (sk, pk) 4 : c ← (c0 , c1 )
5 : return c
Observamos que Π es δ-correcto con δ = 0, dado que
m′ = c1 × c−x
0 =
x
(g )y × m × y −x
(g ) = m ∀x, y ∈ [|G|].
Lemma 16 (ElGamal PKE + (ε, t)-DDH ⇒ OT-IND-CPA) Sea G = ⟨g⟩ un grupo cı́clico
tal que DDH es (ε, t)-difı́cil. Sea Π el PKES de ElGamal definido sobre G con generador g.
Entonces Π otorga (ε′ , t′ )-OT-IND-CPA con ε′ = 2 · ε, t′ ≈ t.
Demostración. Supongamos un adversario A contra ExpOT-CPA . Definimos un adversario B

contra ExpDDH .
B(g x , g y , g z ) O(m0 , m1 )
1 : disabled ← 0 1 : if disabled = 1 :
2 :
$
b̂ ←
− {0, 1} 2 : return ⊥
3 : disabled ← 1
3 : b̂′ ← AO (g x )
4 : c∗ ← (g y , g z · mb̂ )
4 : if b̂′ = b̂ :
5 : return c∗
5 : return 0 //“z = x · y”
6 : else
7 : return 1 //“z ∼ U ([|G|])”
Recordemos la versión “bit-guessing” de ExpOT-CPA :
ExpOT-CPA (A)
$
1 : b̂ ←
− {0, 1}
2 : b̂′ ← ExpOT-CPA (A, b̂)
3 : return Jb̂′ = b̂K
Usando la misma demostración de Lemma 3, sabemos que

1 1
Adv(ExpOT-CPA , A) := Pr[ExpOT-CPA (A) ⇒ 1] − = Adv(ExpOT-CPA , A).
2 2
Por inspección, podemos ver que el entorno de A en ExpDDH (B, 0), es idéntico al de A en ExpOT-CPA (A)
si pk = g x y c∗0 = g y . Por ende,
Pr[ExpDDH (B, 0) ⇒ 1] = Pr[ExpOT-CPA (A) ⇒ 0] = 1 − Pr[ExpOT-CPA (A) ⇒ 1]

1 1
⇐⇒ Pr[ExpDDH (B, 0) ⇒ 1] − = − Pr[ExpOT-CPA (A) ⇒ 1]
2 2
1 1
⇐⇒ Adv(ExpOT-CPA , A) = Pr[ExpOT-CPA (A) ⇒ 1] − = Pr[ExpDDH (B, 0) ⇒ 1] − .
2 2
Dentro de ExpDDH (B, 1), A recibe (g x , g y , g z · mb̂ ), donde g z ∼ U (G), independientemente de

(g x , g y ). Por lo tanto, la vista de A es independiente de b̂, dado que
1
Pr[h = g z · m0 ] = Pr[g z = h · m−1
0 ]= = Pr[g z = h · m−1 z
1 ] = Pr[h = g · m1 ]
|G|
40
Al ser el valor b̂′ retornado por A independiente de b̂, y al ser b̂ ∼ U ({0, 1}), sigue que
1
Pr[b̂′ ̸= b̂] = Pr[ExpDDH (B, 1) ⇒ 1] = .
2
Finalmente,
Adv(ExpOT-CPA , A) = 2 · Adv(ExpOT-CPA , A)
1
= 2 · Pr[ExpDDH (B, 0) ⇒ 1] −
2
= 2 · Pr[ExpDDH (B, 0) ⇒ 1] − Pr[ExpDDH (B, 1) ⇒ 1]
= 2 · Adv(ExpDDH , B).
Claramente, t′ ≈ t, ε′ = 2 · ε, y Π ofrece (2ε, ≈ t)-OT-IND-CPA. □
41
Clase 16: cifrado de clave publica multi-mensaje
Definición 30 (IND-CPA) Sea Π = (Gen, Enc, Dec) un PKES.
ExpCPA (A, b) O(m0 , m1 )

1 : (sk, pk) ← Gen() 1 : c ← Enc(pk, mb )
′ O : return c
2 : b ← A (pk) 2
′
3 : return b
Decimos que Π otorga (ε, t, q)-indistinguibilidad bajo ataques de mensaje elegido (IND-CPA, “in-
distinguishibility under chosen-plaintext attacks”), si cualquier adversario A que corre en tiempo
≤ t y usa ≤ q queries a O, tiene ventaja
Adv(ExpCPA , A) := Pr[ExpCPA (A, 0) ⇒ 1] − Pr[ExpCPA (A, 1) ⇒ 1] ≤ ε.
Comentario 52 Respecto a la definición simétrica, no escribimos explı́citamente el requisito |m1 | =

|m2 | simplemente por que los conjuntos de mensaje sólidamente no son naturalmente {0, 1}∗ . De
cualquier manera, el leak de información sobre m ∈ M a través de c queda presente.
Lemma 17 (OT-IND-CPA ⇒ IND-CPA) Sea Π = (Gen, Enc, Dec) un PKES que ofrece (ε, t)-
OT-IND-CPA. Entonces ofrece (ε′ , t′ , q)-IND-CPA con ε′ = q · ε, t′ ≈ t.
Demostración. Supongamos un adversario A que usa q queries contra ExpCPA . Definimos q adver-
sarios B1 , . . . , Bq contra ExpOT-CPA .
BiE (pk) O(m0 , m1 )

1 : cnt ← 0 1 : cnt ← cnt + 1
′ O : if cnt < i :
2 : b ← A (pk) 2
3 : return b′ 3 : c ← Enc(pk, m0 )
4 : elseif cnt = i :
5 : c ← E(m0 , m1 )
6 : else :
7 : c ← Enc(pk, m1 )
8 : return c
Notemos que siendo Π (ε, t)-OT-IND-CPA,
Pr[ExpOT-CPA (Bi , 0) ⇒ 1] − Pr[ExpOT-CPA (Bi , 1) ⇒ 1] ≤ ε ∀i ∈ [q].
Inspeccionemos el patrón de como los Bi les responden queries a A dentro de ExpOT-CPA (Bi , b).
En lo siguiente escribimos E(m) en lugar de Enc(pk, m).
numero de query
adversario b 1 ... i−1 i i+1 ... q
B1 1 E(m1 ) ... E(m1 ) E(m1 ) E(m1 ) ... E(m1 )
B1 0 E(m0 ) ... E(m1 ) E(m1 ) E(m1 ) ... E(m1 )
..
.
Bi−1 1 E(m0 ) ... E(m1 ) E(m1 ) E(m1 ) ... E(m1 )
Bi−1 0 E(m0 ) ... E(m0 ) E(m1 ) E(m1 ) ... E(m1 )
Bi 1 E(m0 ) ... E(m0 ) E(m1 ) E(m1 ) ... E(m1 )
Bi 0 E(m0 ) ... E(m0 ) E(m0 ) E(m1 ) ... E(m1 )
Bi+1 1 E(m0 ) ... E(m0 ) E(m0 ) E(m1 ) ... E(m1 )
..
.
Bq 0 E(m0 ) ... E(m0 ) E(m0 ) E(m0 ) ... E(m0 )
42
Notamos el siguiente patrón:
∀i < q, Pr[ExpOT-CPA (Bi , 0) ⇒ 1] = Pr[ExpOT-CPA (Bi+1 , 1) ⇒ 1]. (⋆)
también notamos que del punto de vista de A, ExpCPA (A, 1) es idéntico a ExpOT-CPA (B1 , 1), y
ExpCPA (A, 0) es idéntico a ExpOT-CPA (Bq , 0). Por lo tanto,
Adv(ExpCPA , A) = Pr[ExpCPA (A, 0) ⇒ 1] − Pr[ExpCPA (A, 1) ⇒ 1]
= Pr[ExpOT-CPA (Bq , 0) ⇒ 1] − Pr[ExpOT-CPA (B1 , 1) ⇒ 1]
Pr[ExpOT-CPA (Bq , 0) ⇒ 1]
− Pr[ExpOT-CPA (Bq , 1) ⇒ 1] + Pr[ExpOT-CPA (Bq−1 , 0) ⇒ 1]
= | {z }
= 0 por (⋆)
− Pr[ExpOT-CPA (B1 , 1) ⇒ 1]
≤ Adv(ExpOT-CPA , Bq ) + Pr[ExpOT-CPA (Bq−1 , 0) ⇒ 1] − Pr[ExpOT-CPA (B1 , 1) ⇒ 1]
Pr[ExpOT-CPA (Bq−1 , 0) ⇒ 1]
− Pr[ExpOT-CPA (Bq−1 , 1) ⇒ 1] + Pr[ExpOT-CPA (Bq−2 , 0) ⇒ 1]
OT-CPA
≤ Adv(Exp , Bq ) + | {z }
= 0 por (⋆)
− Pr[ExpOT-CPA (B1 , 1) ⇒ 1]
≤ Adv(ExpOT-CPA , Bq ) + Adv(ExpOT-CPA , Bq−1 ) + Pr[ExpOT-CPA (Bq−2 , 0) ⇒ 1] − Pr[ExpOT-CPA (B1 , 1) ⇒ 1]

..
.
2
X
≤ Adv(ExpOT-CPA , Bk ) + Pr[ExpOT-CPA (B1 , 0) ⇒ 1] − Pr[ExpOT-CPA (B1 , 1) ⇒ 1]
k=q
1
X 1
X
OT-CPA
= Adv(Exp , Bk ) ≤ ε = q · ε.
k=q k=q
Notamos que Bi y A corren en tiempo parecido, por lo que t′ ≈ t, y que si A usa ≤ q queries,
ε′ ≤ q · ε. Por lo tanto, si Π es (ε, t)-OT-IND-CPA, entonces también es (q · ε, ≈ t, q)-IND-CPA. □
Comentario 53 La técnica que acabamos de usar se llama argumento hı́brido (“hybrid argu-
ment”), porque requiere definir experimentos “ibridos” entre ExpCPA (A, 0) y ExpCPA (A, 1) con los
cuales calculamos la ventaja total, utilizando la ventaja de distinguir pares de hı́bridos.
Comentario 54 Lemma 17 implica un modo de cifrar mensajes m ∈ {0, 1}∗ arbitrariamente

largos. Sea m = m1 , m2 , . . . , mn una cadena de n bits. Podemos generar una cadena de cifrados
Enc′ (pk, m ∈ {0, 1}n ) := (Enc(pk, g m1 ), Enc(pk, g m2 ), . . . , Enc(pk, g mn ))
donde g mi es g 1 si mi = 1 y g 0 = e si mi = 0. Si Π es (ε, t, q)-IND-CPA con q ≥ n, el cifrado es

seguro. Notablemente, no solo esta técnica es muy ineficiente (vamos a ver una mejor alternativa),
si no que también no funciona con nociones de seguridad mas fuertes, como IND-CCA.
43
Clase 17: cifrado hı́brido, el modelo KEM-DEM
9.1 Cifrado hı́brido

Es interesante observar que en practica, el costo de un cifrado a clave publica es generalmente mas
alto del de un cifrado simétrico. Lanzando openssl speed rsa aes en mi laptop:
• En 10s, 6852 descifrados y 344141 cifrados de RSA-3072 (“128 bits de seguridad”), mensaje
de ≈ 3000 bits
• En 10s, 941746 cifrados o descifrados de AES-128 CBC-mode, mensaje de ≈ 131072 bits
Por este motivo, aunque es técnicamente posible usar sistemas como ElGamal para mensajes
arbitrariamente largos, en la practica PKE y KEX ambos utilizan una primera fase a clave publica
para generar claves para un SKES. En el caso de PKE, este método se llama de cifrado hı́brido
(“hybrid encryption”). Por ejemplo, sean Π = (Gen, Enc, Dec) un PKES, Π′ = (Gen′ , Enc′ , Dec′ ) un
SKES. Podemos cifrar una clave k de Π′ utilizando Π, y luego cifrar un mensaje arbitrariamente
largo utilizando Enc′ (k, ·). Transmitiendo ambos cifrados, es posible recuperar el mensaje.
k m
pk PKE Enc SKE Enc’
c c′
Una técnica mas común hoy en dı́a es remplazar el PKES con un mecanismo de encapsulamiento
de claves (KEM, “key-encapsulation mechanism”). Se puede pensar un KEM cono un sistema
de cifrado de “mensajes al azar”. Esta restricción generalmente le permite a un KEM ser mas
compacto y eficiente que un PKES que ofrece similar seguridad.
k
pk Encaps SKE Enc’
c c′
Un sistema hı́brido que utiliza un KEM se lo llama también KEM-DEM, donde el cifrado
simétrico tiene el rol de mecanismo de encapsulamiento de datos (DEM, “data-encapsulation mech-
anism”).
En la próxima clase, vamos a definir que es un KEM, y vamos a proponer definiciones de
seguridad PKE y KEM cercanas a AE, o sea “IND-CCA”. Vamos a ver un KEM que ofrece OT-
IND-CCA, y utilizarlo para construir un PKE “KEM-DEM” que ofrece seguridad IND-CCA.
44
Ası́ como en el caso de la criptografı́a simétrica, la noción de IND-CPA no nos protege de
un adversario capaz de manipular cifrados. Por ejemplo, si c = (c0 , c1 ) = (g y , g xy · m1 ) cifra un
elemento m1 ∈ G, un adversario puede generar c′ = (c0 , c1 · m2 ) para obtener un cifrado de m1 · m2 ,
de manera parecida a como se modifican cifrados simétricos CTR.
En el caso de SKES, definimos la noción de cifrado autenticado (AE), para capturar este tipo
de ataque. En este caso, definimos una nueva noción, de indistinguibilidad bajo ataques de cifrado
elegido (IND-CCA), donde le otorgamos al adversario un nuevo oráculo D(c) que dado un cifrado
c retorna Dec(sk, c) al adversario.
Una similar noción es posible con SKES también, pero innecesaria dado que AE ⇒ IND-CCA.
Cifrados elegidos son una mayor preocupación en el caso de PKE, dado que cualquiera con la clave
publica puede cifrar, y que las claves publicas pueden quedar en uso mas tiempo de las claves
secretas de los cifrados simétricos.
En la practica, un oráculo de descifrado podrı́a suceder en sistemas de cifrado de email, donde
un proveedor de correo electrónico “Daniel” podrı́a modificar un correo “De Alicia para Bob:
Enc(pkBob , m)” en “De Dan para Bob: Enc(pkBob , m)”. Al responderle a Dan, Bob podrı́a citar
los contenidos originales de m, resultando en un oráculo de descifrado.
Del punto de vista mas teórico, otorgar un oráculo D(c) y de cualquier manera obtener seguridad
IND-CCA captura la noción de que A no puede obtener c = Enc(pk, mb ), modificarlo en c′ ̸= c y
recuperar mb ← D(c′ ), por lo que aunque el cifrado no está “autenticado” de la misma manera
de que un cifrado simétrico AE si lo está, modificar cifrados en transito no le otorga al adversario
ninguna ventaja respecto a extrapolar información sobre el mensaje cifrado.
Definición 31 ( OT- IND-CCA) Sea Π = (Gen, Enc, Dec) un PKES.
Exp OT- IND-CCA

(A, b) O(m0 , m1 ) D(c)
1 : (sk, pk) ← Gen() 1 : if disabled = 1 : 1 : if c ∈ Q :
2 : return ⊥ 2 : return ⊥
2 : disabled ← 0
3 : m ← Dec(sk, c)
3 : Q ← {} 3 : disabled ← 1
4 : return m
4 : b′ ← AO(·), D(·) (pk) 4 : c ← Enc(pk, mb )
5 : return b ′ 5 : Q ← Q ∪ {c}
6 : return c
Decimos que Π otorga (ε, t, qe , qd )-indistinguibilidad bajo ataques de cifrado elegido (IND-CCA, “in-
distinguishibility under chosen-ciphertext attacks”), si cualquier adversario A que corre en tiempo
≤ t, realiza ≤ qe queries a O ( one-time: qe = 1) y realiza ≤ qd queries a D, tiene ventaja
OT- IND-CCA OT- IND-CCA OT- IND-CCA

Adv(Exp , A) := Pr[Exp (A, 0) ⇒ 1] − Pr[Exp (A, 1) ⇒ 1] ≤ ε.
Lemma 18 (OT-IND-CCA ⇒ IND-CCA) Sea Π = (Gen, Enc, Dec) un PKES que ofrece (ε, t, 1, qd )-
IND-CCA (i.e. OT-IND-CCA). Entonces ofrece (qe · ε, ≈ t, qe , qd )-IND-CCA con qe ∈ Z>0 .
Demostración. La demostración es idéntica a la de Lemma 17. □

Para obtener PKE que otorgue seguridad IND-CCA, vamos a utilizar una construcción KEM-
DEM.
Definición 32 (KEM, mecanismo de encapsulado de claves) Sean Kp , Ks , M, C conjun-

tos. Decimos que Π = (Gen, Encaps, Decaps) forman un mecanismo de encapsulamiento de claves
(“key-encapsulation mechanism”, KEM) con espacio de claves publicas Kp , de claves privadas Ks ,
de claves a encapsular M, y de cifrados o “encapsulados” C, si
• Gen es un algoritmo aleatorio, Gen : ∅ → Ks × Kp que retorna una tupla (sk, pk);
• Encaps es un algoritmo aleatorio, Encaps : Kp → M × C que retorna una clave k y un encap-
sulamiento c de k;
• Decaps es un algoritmo determinista Dec : Ks × C → M, que decapsula c;
donde Gen, Encaps y Decaps son “eficientes”. Decimos que Π es δ-correcto si
Pr[(k, c) ← Enc(pk; $) : Decaps(sk, c) ̸= k] ≤ δ.

(sk,pk)∼Gen(),
$ en Encaps
45
Comentario 55 En el resto del curso, consideramos solamente KEMs 0-correctos.
Ahora podemos definir una noción de “KEM IND-CCA”.
Definición 33 (OT-IND-CCA KEM) Sea Π = (Gen, Encaps, Decaps) un KEM.
ExpKEM-OT-CCA (A, b) D(c)

1 : (sk, pk) ← Gen() 1 : if c = c∗ :
∗
2 : (k0 , c ) ← Encaps(pk) 2 : return ⊥
3 : k1 ←
$
−M 3 : k ← Decaps(sk, c)
4 : return k
4 : b′ ← AD (pk, kb , c∗ )
5 : return b′
Decimos que Π otorga “one-time” (ε, t, qd )-indistinguibilidad bajo ataques de cifrado elegido (KEM
IND-CCA, “indistinguishibility under chosen-plaintext attacks”), si cualquier adversario A que
corre en tiempo ≤ t, y realiza ≤ qd queries a D, tiene ventaja
Adv(ExpKEM-OT-CCA , A) := Pr[ExpKEM-OT-CCA (A, 0) ⇒ 1] − Pr[ExpKEM-OT-CCA (A, 1) ⇒ 1] ≤ ε.
46
Clase 18: transformada de Fujisaki-Okamoto
Para construir un KEM OT-IND-CCA, vamos a utilizar una variante de la “transformada de

Fujisaki-Okamoto” (FO, “Fujisaki-Okamoto transform”). Esta nos permite combinar un PKES
que otorga IND-CPA, con dos funciones de hash, obteniendo un KEM OT-IND-CCA!
Hay muchas variantes de FO [HHK17], y esta no debe considerarse la única manera o la manera
“correcta”.
Definición 34 (KEM FO) Sea M un conjunto finito. Sean Π = (GenΠ , EncΠ , DecΠ ) un PKES
donde Π.R es el espacio de monedas de EncΠ , Π.M es el de mensajes, y Π.C es el de cifrados, G
una función de hash G : Π.M → Π.R, H una función de hash H : Π.M × Π.C → M. Definimos
el KEM Π′ = (Gen, Encaps, Decaps) con espacio de claves a encapsular M,
Gen() Encaps(pk) Decaps(sk, c)

$
1 : Π
(sk, pk) ← Gen () 1 : m←
−M 1 : m′ ← DecΠ (sk, c)
2 : return (sk, pk) 2 : c ← EncΠ (pk, m; G(m)) 2 : if m′ = ⊥ :
3 : k ← H(m, c) 3 : return ⊥
4 : return (k, c) 4 : c′ ← EncΠ (pk, m′ ; G(m′ ))
5 : if c′ ̸= c :
6 : return ⊥
7 : k ← H(m′ , c)
8 : return k
Teorema 6 (OT-IND-CPA PKE + ROM ⇒ OT-IND-CCA KEM, informal) Sea Π, G,

y H un PKES y dos funciones de hash como indicadas en Definition 34. Si Π otorga OT-IND-
CPA y es “γ-spread”(∀(sk, pk) ← GenΠ (), m, c : Pr [EncΠ (pk, m; r) = c] ≤ γ,) con γ ≈ 0,
r∼U (Π.R)
y se consideran G y H como “oráculos aleatorios” (o sea, funciones muestreadas uniformemente
al momento de la query, y disponibles al adversario como oráculos), entonces el FO KEM Π′
construido como en Definition 34 otorga seguridad KEM OT-IND-CCA.
Comentario 56 Acabamos de introducir una nueva noción: “spreadness”. La mayorı́a de los

IND-CPA PKES otorgan spreadness. Si no es ası́, cualquier IND-CPA PKE puede ser modificado
para otorgar spreadness de manera sencilla [BS23, Exercise 12.10]. ElGamal PKE es naturalmente
γ-spread con γ = 1/|G|.
Demostración. Una demostración formal de esta variante FO puede obtenerse combinando Teore-
mas 3.2 y 3.3 en [HHK17]. □
Comentario 57 La intuición de por que FO otorga IND-CCA es que el paso de re-cifrado dentro
de Decaps garantiza de que cualquier cambiamiento aportado a un cifrado en transito c resultarı́a
en c′ ̸= c que no pasarı́a decapsulación.
Con un OT-IND-CCA KEM disponible, podemos finalmente generar un OT-IND-CCA PKE,

utilizando el método KEM-DEM. Junto a Lemma 18, esto resulta en IND-CCA PKE.
Teorema 7 (OT-IND-CCA KEM + AE ⇒ OT-IND-CCA PKE, informal) Sea Π = (Gen, Encaps, Decaps)
un KEM, y Π′ = (Gen′ , Enc′ , Dec′ ) un SKES, tales que el espacio Π.M de claves a encapsular de
$
Π es igual al espacio de claves Π′ .K de Π′ , Π.M = Π′ .K, y que Gen′ () = “k ←
− Π′ .K”. Sea
hy hy hy hy
Π = (Gen , Enc , Dec ) el PKES obtenido de manera KEM-DEM,
Genhy () Enchy (pk, m) Dechy (sk, c = (c0 , c1 ))

1 : (sk, pk) ← Gen() 1 : k, c0 ← Encaps(pk) 1 : k ← Decaps(sk, c0 )
2 : return (sk, pk) 2 : c1 ← Enc′ (k, m) 2 : m′ ← Dec′ (k, c1 )
3 : c ← (c0 , c1 ) 3 : return m′
4 : return c
47
Si Π otorga KEM OT-IND-CCA y Π′ otorga AE, entonces Πhy otorga PKE OT-IND-CCA.
Comentario 58 Para demostrar el teorema, los pasos son

1. demostrar que AE ⇒ una noción simétrica de OT-IND-CCA.
2. demostrar que Πhy otorga PKE OT-IND-CCA,
3. Utilizar Lemma 18 para obtener PKE IND-CCA.
Una demostración de Item 1 se encuentra en [BS23, Theorem 9.1]. Para demostrar Item 2, la idea
es de asumir un adversario A que juega una variante Exp de ExpOT-IND-CCA contra Πhy con dos
parámetros, Exp(A, b, b̂). A tiene que adivinar b dado un cifrado
$
(c0 , Enc′ (kb̂ , mb )), donde (k0 , c0 ) ← Encaps(pk) y k1 ←
− Π.M = Π′ .K.
Enchy (m0 ) ′
queremos Πhy ′
Enchy (m1 )
X0,0 := c0 , Enc (k0 , m0 ) X0,1 := c0 , Enc (k0 , m1 )
PKE OT-IND-CCA
indistinguibles por indistinguibles por

Π KEM IND-CCA Π KEM IND-CCA
indistinguibles por
X1,0 := c0 , Enc′ (k1 , m0 ) X1,1 := c0 , Enc′ (k1 , m1 )

′
Π OT-IND-CCA
Notamos que:
1. Si b̂ = 0, entonces (c0 , Enc′ (k0 , mb )) = Enchy (mb ), por lo que para demostrar el resultado,
queremos una cota superior para la distancia entre los {Exp(A, b, 0)}b .
2. Xb,b̂ es una función de la variable aleatoria Yb̂ := (c0 , kb̂ ) (la función es fmb (x, y) 7→ (x, Enc′ (y, mb ))).
3. Por Π ser un IND-CCA KEM, Yb,0 y Yb,1 son indistinguibles. Por data processing inequality
(Theorem 2), también lo tienen que ser Xb,0 y Xb,1 .
4. Enc′ (k1 , m0 ) y Enc′ (k1 , m1) son indistinguibles por ser Π′ un OT-IND-CCA SKES.
La semejanza de X0,0 con X0,1 , de X0,1 con X1,1 y X1,1 con X0,1 nos da el resultado.
Comentario 59 Con los cifrados del curso, Podrı́amos realizar un IND-CCA PKE combinando
un FO KEM basado sobre ElGamal PKE, junto a un AE obtenido como EtM. Un cifrado parecido
y que también otorga IND-CCA es parte del estándar ISO/IEC 18033-2 para cifrado de claves pub-
licas, bajo el nombre de DHIES (ECIES si G es una curva elı́ptica). El próximo-de-ser-estándar-
FIPS ML-KEM para cifrados post-cuánticos, llamado también Kyber, es un OT-IND-CCA KEM
obtenido de un tipo de postulado similar a DDH, a través de una variante de FO parecida a la que
nosotros vimos.
48
Clase 19: autenticado de clave publica
10 Firmas digitales
Finalmente Alicia y Bob pueden comunicar de manera segura, sin tener que intercambiar y proteger
una clave secreta intercambiada de antemano: solo requieren la clave publica del otro.
Por ejemplo, Bob podrı́a publicar pkB en un directorio publico, tipo la guı́a telefónica. Alicia
bajarı́a pkB , y mandarı́a Enc(pkB , “De Alicia: esta es mi clave: pkA ”) a Bob, para poder intercam-
biar mensajes.
PREGUNTA: Falta algo?
• Como hace Bob para saber que fue justamente Alicia a mandarle el mensaje? 7→ Alicia
podrı́a publicar su clave en la guı́a.
• Sobre todo, como hace Alicia para saber que pkB le pertenece a Bob?
Para resolver este problema, necesitamos dos componentes mas: firmas digitales, y una in-
fraestructura de claves publicas. En esta sección, vamos a construir firmas digitales.
Las firmas digitales sirven para comprobar la autenticidad de un mensaje m, sin requerir una
clave secreta compartida. Pueden pensarlo como una versión publica de los MACs, y por eso
sintaxis y noción de seguridad son parecidas.
m∈M
σ ← Sign(sk, m)
Sign Ver 1/0
Gen sk ∈ Ks
pk ∈ Kp
Las firmas pueden solo ser generadas con sk, y pueden solo ser verificadas con pk.
Definición 35 (DSS) Sean Kp , Ks , M, Σ conjuntos. Sea Π = (Gen, Sign, Ver) una tripla de
algoritmos eficientes, tales que
• Gen es un algoritmo aleatorio, Gen : ∅ → Ks × Kp que retorna una tupla (sk, pk);
• Sign es un algoritmo posiblemente aleatorio, Sign : Ks × M → Σ que retorna una firma σ;
• Ver es un algoritmo determinista Ver : Kp × M × Σ → {0, 1}, que retorna 1 si la firma es
“valida” y 0 si no.
Decimos que Π es un esquema de firma digital (DSS, “digital signature scheme”) δ-completo si
∀m ∈ M, Pr [Ver(pk, m, Sign(sk, m; $)) ̸= 1] ≤ δ.

(sk,pk)∼Gen(),
$ en Sign
Comentario 60 Como en el caso de PKE, el espacio de mensajes “firmables” puede depender de

pk, Mpk ⊂ M.
Si recuerdan, un MAC seguro se dice “fuertemente infalsificable”, y excluye que A pueda

retornar una tupla (m∗ , σ ∗ ) validos y “nuevos”. Vamos a usar una definición parecida para los
DSS.
49
Definición 36 (SUF-CMA) Sea Π = (Gen, Sign, Ver) un DSS. Definimos un experimento ExpSUF .
ExpSUF (A) S(m)

1 : (sk, pk) ← Gen() 1 : σ ← Sign(sk, m)
2 : Q ← {} 2 : Q ← Q ∪ {(m, σ)}
∗ ∗ S : return σ
3 : (m , σ ) ← A (pk) 3
∗ ∗
4 : // (m , σ ) ̸∈ Q
5 : b ← Ver(pk, m∗ , σ ∗ )
6 : return b
Decimos que Π es (ε, t, q)-fuertemente infalsificable bajo ataques de mensaje elegido (SUF-CMA,
“strongly unforgeable under chosen-message attacks”) si cualquier A que corre en tiempo ≤ t,
realiza ≤ q queries a S, y retorna (m∗ , σ ∗ ) ̸∈ Q, tiene ventaja
Adv(ExpSUF , A) := Pr[ExpSUF (A) ⇒ 1] ≤ ε.
Comentario 61 En la definición de seguridad MAC, se podı́a discutir si darle a A acceso a

un oráculo Ver(k, ·). Esta discusión no existe con DSS, dado que Ver(pk, ·) puede ser evaluada
públicamente.
Existen principalmente cuatro maneras de realizar DSS: con protocolos de identificación, con
funciones de puerta trasera, con funciones de hash y con “MPC-in-the-head”. Nosotros vamos a
cubrir el segundo método, en su forma clásica a través permutaciones de puerta trasera, que es
comúnmente utilizado en practica.
La idea es la siguiente: dado un conjunto D finito, f : D → D es una permutación (o biyección)
públicamente computable, tal que f −1 : D → D es difı́cil de computar, a menos de no conocer una
“puerta trasera”.
f (·) f (x) f −1 (y) f −1 (·)

x y x y
fácil difı́cil
ft−1 (y) ft−1 (·)

x y
fácil
Para firmar un mensaje, podrı́amos usar f como clave publica, t como clave secreta, y generar
firmas σ de mensajes invirtiendo f , y calculando f (σ) como verificación.
Definición 37 (TDP) Sean T , F dos conjuntos. Sea Π = (Gen, Eval, Invert) una tripla de algo-
ritmos, tales que
• Gen es un algoritmo aleatorio, Gen : ∅ → T ×F que retorna una tupla (t, f ), con f : Df → Df
una permutación sobre un conjunto finito Df , que puede depender de f .
• Eval es un algoritmo determinista, Eval : F × Df → Df que dado (f, x) retorna f (x);

• Invert es un algoritmo determinista Invert : T × F × Df → Df , que dados (t, f, y) retorna
f −1 (y).
Decimos que Π es una permutación de puerta trasera (TDP, “trapdoor permutation”).
La dificultad de invertir una TDP se la puede “capturar” con una definición de seguridad.
Definición 38 (OW TDP) Sean Π = (Gen, Eval, Invert) una TDP. Definimos ExpOW ,
50
ExpOW (A)
1 : (t, f ) ← Gen()
$
2 : y←
− Df
3 : x ← A(f, y)
4 : return Jf (x) = yK
Decimos que Π es (ε, t)-unidireccional (OW, “one-way”), si cualquier A que corre en tiempo ≤ t
tiene ventaja
Adv(ExpOW , A) := Pr[ExpOW (A) ⇒ 1] ≤ ε.
Comentario 62 Notamos que el experimento requiere y ∼ U (Df ), y requiere que a A no le sean

dados oráculos de inversión! Esto puede volver las demostraciones mas difı́ciles.
Esto nos trae a nuestro ultimo postulado.

Postulado 4 Dado (ε, t), existen TDPs que son (ε, t)-OW seguras.
51
Clase 20: firmas “full-domain hash”
Vamos ahora a definir un DSS que utiliza TDPs y funciones de hash para firmar m ∈ {0, 1}∗ .
Definición 39 (TDP-FDH, o “hash-then-invert”) Sea Π = (Gen, Eval, Invert) una TDP, y
sea {Hf }f una familia de funciones de hash Hf := {0, 1}∗ → Df , donde f : Df → Df . Definimos
el DSS Π′ = (Gen′ , Sign′ , Ver′ ) de hash de dominio completo (FDH, “full-domain hash” o “invert-
then-sign”),
Gen′ () Sign′ (sk = (t, f ), m) Ver′ (pk = f, σ)

1 : (t, f ) ← Gen() 1 : h ← Hf (m) 1 : h ← Hf (m)
2 : sk ← (t, f ) 2 : σ ← Invert(t, f, h) 2 : h′ ← Eval(f, σ)
3 : pk ← f 3 : return σ 3 : return Jh′ = hK
4 : return (sk, pk)
Comentario 63 Mas allá del tipo de primitiva usado, la mayorı́a de los DSS efectivamente firman
hashes de un mensaje, no el mensaje directamente (“hash-then-sign”). “Deshacer” la estructura
algebraica de m puede ser útil para obtener seguridad. Por ejemplo, esto es necesario si se usa la
famosa TDP de Rivest, Shamir y Adleman (RSA).
Comentario 64 Usamos m ∈ {0, 1}∗ , pero uno podrı́a definir TDP-FDH sobre cualquier dominio
R tal que H : R → Df es una función de hash.
Comentario 65 Como habrán notado, el esquema es muy parecido a usar una PRF para realizar
un MAC, remplazando la PRF (o PRP!) con la TDP.
Finalmente, demostramos que una TDP-FDH otorga SUF-CMA.
Teorema 8 (OW TDP + ROM ⇒ SUF-CMA) Sea Π una TDP, y sea Π′ el resultante DSS
obtenido como TDP-FDH. Supongamos que la familia {Hf }f es compuestas de funciones total-
mente aleatorias. Sea qS ≥ 1 el numero de queries a S(·) que le permitimos a un adversario A
contra Π′ . Si Π es (ε, t)-OW entonces Π′ es (ε′ , t′ , q ′ )-SUF-CMA con t′ ≈ t, q ′ = qS , y ε ≈ e · qS · ε,
donde e = 2, 71828 . . . es la constante de Napier.
Demostración. Sea A un adversario contra TDP-FDH. Para simplificar la demostración, vamos a
suponer que A retorna una posible firma falsificada σ ∗ sobre un mensaje m∗ solo luego de calcular
H(m). Si no fuera de ser ası́, podrı́a falsificar una firma correctamente solamente con probabilidad
1
|Df | . Sea p ∈ (0, 1) una constante, el cual valor determinaremos mas tarde. Vamos a definir B, un
adversario que juega ExpOW contra la TDP. Dado que suponemos la función H ser completamente
aleatoria, vamos a suponer que cuando A requiere H(m), calcula este valor a través de un oráculo,
que nosotros vamos a remplazar.
(f, y)
pk pk B
Algo sucede. . . m
A A
Ĥ(m)
Algo sucede. . .
H(·) B Ĥ(·)
m
Algo sucede. . .
H(m)
(m∗ , σ ∗ ) (m∗ , σ ∗ )
52
Esto puede parecer raro, pero puede ser pensado de la siguiente manera. Supongamos que A
es un programa en C, y precisa calcular un hash H(m). Posiblemente, A obtenga H a través de
una librerı́a de enlace dinámico (una DLL) contra la cual viene compilado, dado que es improbable
que la estructura de la función de hash tenga un impacto sobre la dificultad de falsificar una firma
(es común suponer que los hashes son “preimage resistant”).
Obtenido A, el adversario B decide de re-compilarla contra una diferente DLL, que implementa
otra función aleatoria Ĥ(·). La intuición es que esto no tendrı́a que reducir la probabilidad de A
de retornar una falsificación (m∗ , σ ∗ ) respecto al DSS TDP-FDH con hash Ĥ, dado que A es un
algoritmo aleatorio, y H es una función aleatoria, por lo que la distribución de la variable aleatoria
AĤ (f, y) es la misma que la de AH (f, y).
Decimos que este tipo de demostración se encuentra en el modelo del oráculo aleatorio (ROM,
“random oracle model”). Mucho ha sido debatido sobre el ROM. [KM15] cubre los aspectos mas
importantes del debate. A menudo este modelo nos permite demostrar la seguridad de esquemas
mas eficientes [BR93], que resisten la “prueba del tiempo” una ves desplegados. Por ejemplo, la
demostración de que FO es IND-CCA, también se encuentra en el ROM.
B(f, y) Ĥ(m) S(m)

1 : p ← // un valor particular ∈ (0, 1) 1 : if m ∈ L : 1 : Ĥ(m)
2 : Q ← {} 2 : (. . . , h) ← L[m] 2 : (σ, h) ← L[m]
3 : L←[] 3 : return h 3 : if σ = ⊥ :
4 : pk ← f 4 : // si no, m ̸∈ L: 4 : ERROR
5 : (m∗ , σ ∗ ) ← AS(·), Ĥ(·) (pk) 5 : r←
$
− (0, 1) 5 : Q ← Q ∪ {(σ, m)}
6 : ∗ ∗
// (m , σ ) ̸∈ Q 6 : if r < p : // con pr. p 6 : return σ
∗
7 : x←σ $
7 : σ←
− Df
8 : return x
8 : h ← Eval(f, σ)
9 : L[m] ← (σ, h)
10 : else : // con pr. 1 − p
11 : h←y
12 : L[m] ← (⊥, h)
13 : return h
Observamos el punto de vista de A “dentro” de B. Al calcular Ĥ(m), dos cosas pueden pasar:
• Si r < p, generamos σ ∼ U (Df ), y retornamos h := f (σ). Dado que f es una permutación,
h = f (σ) también es uniformemente aleatorio, h ∼ U (Df ).

1
∀y ∈ Df , Pr [f (σ) = y] = Pr [σ = f −1 (y)] =
σ∼U (D) σ∼U (D) |Df |
Por lo tanto, Ĥ(m) ∼ U (Df ).

• Si r ≥ p, retornamos y, que por suposición fue generado ∼ U (Df ) en ExpOW .
En ambos casos, Ĥ(m) ∼ U (Df ), como A se espera. En el ROM, esta técnica se llama “progra-
mación del oráculo aleatorio”.
Al calcular S(m), primero forzamos el calculo de Ĥ(m). Luego,
• Si h = Ĥ(m) fue generado en el ramo “r < p” de Ĥ, entonces retornamos σ = f −1 (h) a A,
de manera que σ ∼ U (Df ), y Ver(pk, m, σ) = Jf (σ) = Ĥ(m)K = 1, como A se espera. Esto
es posible porque generamos primero σ y luego h = f (σ), por lo que no requerimos invertir
f para simular la firma.
• Si h fue generado en el ramo r ≥ p, entonces σ = ⊥, y no podemos simular el algoritmo
de firma. Esto le causa a B de terminar su ejecución retornando un ERROR y fallando en el
ataque. Denotamos este evento, E, y el e vento que no ocurra un error, E.
Calculamos:
Pr[ExpOW (B) ⇒ 1] ≥ Pr[ExpOW (B) ⇒ 1 ∧ E ∧ Ĥ(m∗ ) = y]
= Pr[ExpOW (B) ⇒ 1 | E ∧ Ĥ(m∗ ) = y] · Pr[E ∧ Ĥ(m∗ ) = y].
Notamos dos hechos:
53
1. Como B retorna el output de A,
dado E ∧ Ĥ(m∗ ) = y, “A falsifica la única firma posible de m∗ , dentro de B” =⇒ “ExpOW (B) ⇒ 1”
2. “E ∧ Ĥ(m∗ ) = y” =⇒ “A no puede distinguir B de ExpSUF ” (ie, la distribución de A dentro

de ExpSUF = la distribución de A dentro de B dado que “E ∧ Ĥ(m∗ ) = y”).
Sigue que
Pr[ExpOW (B) ⇒ 1 | E ∧ Ĥ(m∗ ) = y] ≥ Pr[A falsifica la firma de m∗ dentro de B | E ∧ Ĥ(m∗ ) = y] (por hecho 1)
SUF
= Pr[Exp (A) ⇒ 1]. (por hecho 2)
Finalmente, observamos que los eventos E y Ĥ(m∗ ) = y son independientes, dados como B
muestrea r dentro de Ĥ, y dado que por suposición A nunca pide S(m∗ ). Por lo tanto,
Pr[E ∧ Ĥ(m∗ ) = y] = Pr[E] · Pr[Ĥ(m∗ ) = y] ≥ pqS · (1 − p).
Finalmente, coleccionamos los resultados arriba y
Pr[ExpOW (B) ⇒ 1] ≥ Pr[ExpOW (B) ⇒ 1 | E ∧ Ĥ(m∗ ) = y] · Pr[E ∧ Ĥ(m∗ ) = y]

≥ Pr[ExpSUF (A) ⇒ 1] · pqS · (1 − p)
Adv(ExpOW , B)
⇐⇒ Adv(ExpSUF , A) ≤ .
pqS · (1 − p)
Como notamos al comienzo de la demostración, podemos elegir cualquier p ∈ (0, 1). Para
obtener la mejor cota superior de Adv(ExpSUF , A) (o sea, la cota superior mas baja posible),
queremos elegir el valor p = p0 que maximiza el denominador, g(p) = pqS · (1 − p), con p ∈ (0, 1).
1. Calculamos la derivada:
d qS d
g ′ (p) = [p ] (1 − p) + pqS [1 − p]
dp dp
= qS · pqS −1 (1 − p) + pqS · (−1)
= pqS −1 (qS − qS · p − p)
qS +1 − 1 1
g ′ (p) = 0 ⇔ qS − qS · p − p = qS − p(qS + 1) = 0 ⇔ p = =1− =: p0 .
qS + 1 qS + 1
2. Verificamos que es un máximo:

d qS −1 d
g ′′ (p) = [p ](qS − qS · p − p) + pqS −1 [qS − qS · p − p]
dp dp
qS −2
= (qS − 1) · p (qS − qS · p − p) + pqS −1 (−qS − 1)
= pqS −2 ((qS − 1) · (qS − qS · p − p) − p · (qS + 1))
= pqS −2 (qS · (qS − qS · p − p) − (qS − qS · p − p) − p · (qS + 1)))
= pqS −2 qS2 − qS2 · p − qS · p − qS + qS · p + p − p · qS − p)

= pqS −2 qS2 − qS2 · p − qS · p − qS +

·
qS p+p −p ·
qS − p)

= pqS −2 · qS · (qS − qS · p − p − 1)
=⇒ g ′′ (p0 ) = pq0S −2 · qS · (( −(qS(· (
p− p − 1) = −qS · pq0S −2 < 0.
(
qS( (
Dado que g ′′ (p0 ) es negativo, p0 = 1 − 1

qS +1 es un máximo de g (el único, dado g ′ (p)).
p0
g ′′ (p0 ) < 0
Ahora calculamos el denominador en p0 ,

qS
1 1
g(p0 ) = 1 − · 1− 1−
qS + 1 qS + 1
54
qS +1 qS +1
1 − qS1+1 1 1 − 1
qS +1 1
= · = ·
1
1 − qS +1 q + 1 q +1 1 qS +1
qS +1 − qS +1
S S
qS +1
1 1
= 1− ·
qS + 1 qS
n
1 − n1 = 1/e y que qS ≫ 1,

Dado que limn→∞
1 1
g(p0 ) ≈ · .
e qS
1
Por lo tanto, si dentro de B asignamos p ← p0 = 1 − qS +1 ,
Adv(ExpOW , B)
Adv(ExpSUF , A) ≤ ≲ e · qS · Adv(ExpOW , B),
g(p0 )
y t′ ≈ t, q ′ = qS y ε′ ≈ e · qS · ε. □
Comentario 66 Notamos que las propiedades de H como función de hash no juegan un rol directo
en la demostración. Esto es porque ignoramos ser H un hash, y la consideramos una oráculo de
función aleatoria. De manera sutil, decidimos suponer que los ataques no van a ser causados
por un adversario A que invierta o ataque la estructura interna de H, y como esta posiblemente
interactúe con la estructura de la TDP.
Comentario 67 (Error en la demostración) Como sutilmente observado por un alumne, esta

demostración tiene un error: el caso “r ≥ p”, donde Ĥ(m) = y, hace que con probabilidad 1 − p la
salida de Ĥ sea y. Del punto de vista de A, esto tendrı́a que ocurrir solamente si el conjunto Df
1
de salida de H tuviera tamaño |Df | = 1−p , lo que no ocurre en general.
La demostración se puede arreglar de manera relativamente simple, pero requiere que (Df , ×)
sea un grupo bajo alguna operación binaria × donde la operación de inversión sea implementable
de manera eficiente, y que la TDP otorgue una propiedad mas: dada f : Df → Df , esta tiene que
ser no solo una permutación sobre Df , si no también un isomorfismo de grupos, o sea ∀x, y ∈
Df , f (x) × f (y) = f (x × y).7 Como consecuencia, f −1 también es un isomorfismo.8 Al momento
de calcular por i-esima vez el ramo r > p dentro de Ĥ, generamos un valor si ∼ U (Df ), que
guardamos en la tabla hash L como dato accesorio, y retornamos y × f (si ) en lugar de simplemente
y. Al ser cada si uniforme e independiente, y f una permutación, cada y × f (si ) es un elemento
uniformemente aleatorio e independiente en Df ,9 y A no observa ninguna diferencia entre Ĥ
respecto a un oráculo H efectivamente aleatorio. Una vez que A retorna una firma falsificada
σ ∗ = f −1 (Ĥ(m∗ )) = f −1 (y × f (si )) = f −1 (y) × f −1 (f (si )) = f −1 (y) × si , el adversario B puede
recuperar f −1 (y) = σ ∗ × si −1 , y retornarlo (en lugar de simplemente retornar x ← σ ∗ ).
Aunque el requisito de que f sea un isomorfismo de grupos puede parecer algo exótico, en la
practica las dos principales TDPs (de RSA y de Rabin) lo satisfacen. En particular, en el caso de
RSA, Df = Z∗N con N = p · q, y f (x) = xe mod N es un isomorfismo dado que es invertible (por
como e es elegido), y que f (x) × f (y) = xe · y e mod N = (x · y)e mod N = f (x · y).
7 En este caso, el isomorfismo es de (Df , ×) hacia si mismo, por lo que f es un “automorfismo”.

8 Dado a × b = f (f −1 (a)) × f (f −1 (b)) = f (f −1 (a) × f −1 (b)), aplicamos f −1 obteniendo f −1 (a × b) = f −1 (a) ×
f −1 (b).
9 ∀h ∈ D , Pr[y × f (s ) = h] = Pr[f (s ) = y −1 × h] = Pr[s = f −1 (y −1 × h)] = 1/ D .
f i i i f
55
Clase 21: infraestructuras de claves publicas
56
References
[BR93] Mihir Bellare and Phillip Rogaway. Random oracles are practical: a paradigm for de-
signing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and
Communications Security, CCS ’93, page 62–73, New York, NY, USA, 1993. Association
for Computing Machinery.
[BS23] Dan Boneh and Victor Shoup. A Graduate Course in Applied Cryptography. Self-
published, January 2023. Version 0.6, https://toc.cryptobook.us.
[FT21] Pooya Farshim and Stefano Tessaro. Password hashing and preprocessing. In Advances in
Cryptology – EUROCRYPT 2021: 40th Annual International Conference on the Theory
and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021,
Proceedings, Part II, page 64–91, Berlin, Heidelberg, 2021. Springer-Verlag.
[HHK17] Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A modular analysis of the
fujisaki-okamoto transformation. In Theory of Cryptography Conference, pages 341–371.
Springer, 2017.
[KL20] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chapman
and Hall/CRC, December 2020.
[KM15] Neal Koblitz and Alfred J Menezes. The random oracle model: a twenty-year retrospec-
tive. Designs, Codes and Cryptography, 77:587–610, 2015.
[Ros21] Mike Rosulek. The Joy of Cryptography. Self-published, January 2021. https:
//joyofcryptography.com.
57

Apuntes Criptografiamoderna

Cargado por

Copyright:

Formatos disponibles

Apuntes Criptografiamoderna

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Apuntes Criptografiamoderna

Cargado por

Copyright:

Formatos disponibles

Apuntes de Criptografı́a

OTP PRG PRP DSS TDP

PR-OTP PRF Hash DDH

CPA SKE MAC CCA KEM CPA PKE

Esta clase se encuentra en forma de diapositivas en https://apuntes.indcpa.com.

para indicar Pr[Y = y] = Pr[f (X) = y] cuando X ∼ U (S).

Lemma 2 (Union bound, cota de la unión) Dados eventos A1 , . . . , An ,

Comentario 1 Generalmente consideramos R = {0, 1}n con n ∈ Zn .

Definición 1 (Algoritmo aleatorio) Sea A un algoritmo con conjunto de inputs I y conjunto

Generalmente abusamos notación y escribimos A(x; r) en lugar de A(x, r).

En criptografı́a trabajamos con “adversarios” que interceptan comunicaciones e intentan vulner-

Teorema 2 (Informal, “data processing inequality”) Dadas dos variables aleatorias X, Y

Definición 2 (función aleatoria) Sea D un conjunto, y R un conjunto finito. Decimos que

2 One-Time Pads y secreto perfecto

• Dec es un algoritmo determinista Dec : K × C → M;

donde Gen, Enc y Dec son “eficientes”.

Figure 2: Uso de un cifrado simétrico. Consideramos el cifrado c ser expuesto al adversario.

Comentario 4 Generalmente consideramos K, M, C ⊂ {0, 1}∗ en la criptografı́a simétrica.

Comentario 5 Generalmente consideramos K finito, y Gen() consiste en muestrear la distribución

1. Podrı́amos pedir que dado c, un adversario no aprenda k. Y si aprende m?

∀m0 , m1 ∈ M, c ∈ C, Pr [Enc(k, m0 ) = c] = Pr[Enc(k, m1 ) = c].

Pr[c = Enc(k, m0 )] > 0 (existe una llave k valida)

Una definición equivalente de secreto perfecto requiere

∀m ∈ M, c ∈ C, Pr[M = m | C = c] = Pr[M = m].

Gen() Enc(k, m) Dec(k, c)

Teorema 3 El OTP ofrece secreto perfecto.

Demostración. Sean n ∈ Z>0 , m0 , m1 ∈ {0, 1}n , c ∈ {0, 1}n .

Pr [Enc(k, m0 ) = c] = Pr[k ⊕ m0 = c] (def. de Enc)

Ataque 1 (OTP) Supongamos A ve c ∈ C. Que aprende sobre m? Dado cualquier m ∈ M, si

Es común en criptografı́a relajar las definiciones de seguridad, en cambio de eficiencia. Vemos un

∀m0 , m1 ∈ M, c ∈ C, |Pr[Enc(k, m0 ) = c] − Pr[Enc(k, m1 ) = c]| ≤ ε.

Comentario 8 Un SKES con OT ε-secrecy con ε = 0 otorga secreto perfecto.

EJERCICIO: [BS23, Exercise 2.5]: OT ε-secrecy =⇒ |K| ≥ (1 − ε)|M|

Comentario 9 Lo mas cercano ε a 0, lo mas cercano OT ε-secrecy al secreto perfecto, y lo mas

Si un adversario A observa los cifrados c1 y c2 en transito, que puede aprender sobre m1 y m2 ?

Esto es un problema! Por ejemplo, si m1 es un mensaje predecible, digamos Pr[m1 = m1 ] ≈ 1, A

Comentario 11 OT ε-secrecy solo garantiza confidencialidad. No otorga garantı́as de integridad.

lo intercepta y transmite c′ = c ⊕ (10 . . . 0) al banco, este decifrarı́a

costandole a Alicia mucho mas.

ExpPRG (A, 0) ExpPRG (A, 1)

Decimos que G es un generador (ε, t)-pseudoaleatorio (PRG, “pseudorandom generator”), si para

Adv(ExpPRG , A) := Pr[ExpPRG (A, 0) ⇒ 1] − Pr[ExpPRG (A, 1) ⇒ 1] ≤ ε.

s ∼ U ({0, 1}ℓ ) PRG k ≈ U ({0, 1}m )

Lemma 3 Bajo las condiciones de Definition 7,

Adv(ExpPRG , A) = 2 · Adv(ExpPRG , A).

Demostración. Usando el teorema de la probabilidad total,

Pr[ExpPRG (A) ⇒ 1] = Pr[b′ = b]

Ahora notamos que por definición de ExpPRG ,

Pr[b′ = b | b = 0] = Pr[ExpPRG (A, 0) ⇒ 0] = 1 − Pr[ExpPRG (A, 0) ⇒ 1],

Comentario 14 Que quieren decir exactamente (ε, t)?

A(y ∈ {0, 1}m )

Claramente, A corre en tiempo ≈ 2ℓ .

A(y ∈ {0, 1}m )

EJERCICIO: Demuestren que A es un (ε ≈ 2−ℓ , t ≈ 1)-atacante. (Idea: el espacio

Gen() Enc(k, m) Dec(k, c)

Comentario 16 El nuevo cifrado no otorga secreto perfecto. En la demostración del OTP, el

PREGUNTA: Alguien tiene alguna idea de que podemos intentar demostrar?

Hasta ahora habı́amos visto definiciones de seguridad “information-theoretical” (secreto per-

3 “EAV-security” en [KL20], “semantic security” en [BS23].

|Pr[E1 ] − Pr[E2 ]| = (Pr[E1 ∧ Z] +

Feistel inverse Feistel