Semantic Security (16 min)

1
00:00:00,000 --> 00:00:03,911
Mi meta para los próximos segmentos es mostrar que si usamos un
PRG seguro, podremos

2
00:00:03,911 --> 00:00:07,892
obtener una secuencia o flujo seguro. Lo primero que tenemos que hacer
es definir cual es el

3
00:00:07,892 --> 00:00:11,679
significado de que un flujo de datos sea seguro?
Así que cada vez que definimos la seguridad siempre

4
00:00:11,679 --> 00:00:15,174
es terminos de żqué es lo que el atacante puede hacer?
y żqué es lo que el atacante esta

5
00:00:15,174 --> 00:00:18,670
intentando hacer? En el contexto de cifrado de flujo
recuerde que estos sólo se utilizan

6
00:00:18,670 --> 00:00:22,737
con una llave de una sola vez (onetime key),
y como
resultado, la mayoria de las veces el atacante solo

7
00:00:22,737 --> 00:00:26,754
puede ver el texto cifrado con la llave que
estamos utilizando.żY como nos vamos

8
00:00:26,754 --> 00:00:30,772
a limitar a los atacantes ? A la capacidad de obtener
básicamente un texto cifrado. Y, de hecho,

9
00:00:30,772 --> 00:00:34,641
más adelante vamos a permitir que el
atacante pueda hacer mucho, mucho, mucho más, pero

10
00:00:34,641 --> 00:00:38,460
por ahora sólo vamos a darle un texto cifrado.
Y lo que queremos encontrar, ,

11
00:00:38,460 --> 00:00:42,560
what does żqué significa que el cifrado sea seguro?
Así que la primera definición que

12
00:00:42,560 --> 00:00:46,892
viene a la mente es básicamente para decir

bueno tal vez queremos exigir que el atacante no

13
00:00:46,892 --> 00:00:50,718
puede realmente recuperar la clave secreta.

Bueno por lo que dado el texto cifrado el atacante

14
00:00:50,718 --> 00:00:54,609
no debe ser capaz de recuperar la clave secreta.

Pero esa es una definición terrible

15
00:00:54,609 --> 00:00:58,717
porque pesa mas en la falla de nuestro genial cifrado
pero es la manera como ciframos el

16
00:00:58,717 --> 00:01:02,855
mensaje usuando una clave K es como básicamente
sale en mensaje. Bueno este es

17
00:01:02,855 --> 00:01:07,427
un sistema de cifrado sí brillante,
por supuesto
no hace nada dado un mensaje que acaba

18
00:01:07,427 --> 00:01:12,000
de generar un mensaje con el texto cifrado.

Esto no es un esquema de cifrado

19
00:01:12,000 --> 00:01:16,029
particularmente bueno; Sin embargo, dado el
texto
cifrado,hace que nuestro desvalido atacante

20
00:01:16,029 --> 00:01:20,493
no pueda recuperar la clave, porque él no sabe
cuál es la clave.Y así, como resultado

21
00:01:20,493 --> 00:01:24,630
esta cifrado que claramente es inseguro,
se considera segura bajo este

22
00:01:24,793 --> 00:01:28,636
requisito de seguridad. Así que esta
definición no será buena. Bueno por lo que si

23
00:01:28,636 --> 00:01:32,317
recuperando la clave secreta es el camino equivocado
para definir la seguridad. Así que la próxima cosa que

24
00:01:32,317 --> 00:01:35,999
puede intentar es básicamente, es decir
el atacante no se preocupa por

25
00:01:35,999 --> 00:01:39,680
la clave secreta, lo que realmente le importa es el
texto plano. So maybe it should be

26
00:01:39,680 --> 00:01:43,518
Así que tal vez debería ser difícil para el atacante
recuperar el texto completo. Pero incluso eso no funciona porque

27
00:01:43,518 --> 00:01:48,223
vamos a pensar en el siguiente el siguiente
esquema de cifrado. Así que suponemos

28
00:01:48,223 --> 00:01:53,436
que lo que este esquema de encriptación
hace es que se necesitan dos mensajes,así que voy a utilizar dos

29
00:01:53,436 --> 00:01:58,014
líneas para indicar la concatenación de dos
mensajes: linea M0 , Linea M1, de

30
00:01:58,014 --> 00:02:03,100
manera que concatenamos M0 y M1. Ahora imagine
lo que el sistema hace es realmente hace la salida de

31
00:02:03,100 --> 00:02:08,060
M0 en texto plano y concatena con la encripción
de M1. Tal vez aunque estemos usando

32
00:02:08,060 --> 00:02:13,337
una libreta de una vez (One Time Pad) żsi?
Y aquí el atacante va a dar con un

33
00:02:13,337 --> 00:02:17,478
texto cifrado. su objetivo sería recuperar los
los textos planos. But the

34
00:02:17,478 --> 00:02:21,702
Pero el pobre atacante pobres no pueden leer nada porque el
texto M1 fue cifrado usado la libreta de una sola vez

35
00:02:21,702 --> 00:02:25,872
(One Time Pad )de forma que el ataquente no puede
recuperar M1 porque nosotros sabemos que el

36
00:02:25,872 --> 00:02:30,043
One Time Pad es seguro dato un solo
texto cifrado. De acuerdo con esto nosotros

37
00:02:30,043 --> 00:02:34,055
habremos de satisfacer la definición pero
desafortunamente este no es un esquema

38
00:02:34,055 --> 00:02:37,962
de cifrado correcto porque simplemente
la mitad del texto no esta cifrado. M0 esta

39
00:02:37,962 --> 00:02:42,185
completamente disponible para el atacante
aun cuando el no pueda recuperar completamente

40
00:02:42,185 --> 00:02:46,462
todo el texto plano, ya que el el capaz de recuperar
mucho del texto plano y esto es claramente

41
00:02:46,462 --> 00:02:50,658
Inseguro. Por supuesto que nosotros contamos con la
solicion y esta es tomada de la

42
00:02:50,658 --> 00:02:54,747
definición de Shanos de la seguridad perfecta de la
secrecia, donde la idea de Sahnnon es que de

43
00:02:54,747 --> 00:02:58,835
facto cuando el atacante intercepta un texto
cigrado, el no puede apredender nada acerca de

44
00:02:58,835 --> 00:03:02,818
la información contenida en el texto plano.
El ni siquiera deberia aprender un poco acerca de

45
00:03:02,818 --> 00:03:07,221
texto plano o aún, el no deberia ser capaz de
predecir ni un pequeńo bit acerca

46
00:03:07,221 --> 00:03:11,205
de
de nuestro texto plano, esto es, absolutamente
nada acerca de nuestro texto plano

47
00:03:11,205 --> 00:03:14,926
Así que vamos a recordar muy brevemente
el concepto de Shannon de la secrecia perfeta

48
00:03:14,926 --> 00:03:19,442
basicamente el nos dijo que dato un texto
cifrado, decimos que el cifrado tiene secrecia

49
00:03:19,442 --> 00:03:25,069
perfecta si datos dos mensajes del mismo tamańo
se da la circuntancia que la distribución en los
it so happens that the distribution

50
00:03:25,069 --> 00:03:30,167
textos cifrados es igual. Pero si tomamos una clave
aleatoria y miramos en la distribución de

51
00:03:30,167 --> 00:03:34,838
los textos cifrados, encontramos que M0 tendrá
exactamente la misma distribucion que cuando

52
00:03:34,838 --> 00:03:39,257
cifremos M1. La intuciones es que si un observado
mira los textos cifrados

53
00:03:39,257 --> 00:03:43,839
el no es capaz de hacer nada con la
distribución del resultado del cifrado

54
00:03:43,839 --> 00:03:48,203
M0 ya que su distribucione es similar a la
distribución de encriptar M1. Y como resultado

55
00:03:48,203 --> 00:03:52,513
el observador no nos puede decir si es el
cifrado de M0 o de M1. Y esto es verdadero para todos

56
00:03:52,513 --> 00:03:56,877
los mensajes de la misma longitud y como
resultado nuestro pobre atacante no puede conocer

57
00:03:56,877 --> 00:04:01,212
que mensaje fue encriptado. Por supuesto nosotros no
Por supuesto, ya hemos dicho que esta definición es demasiado

58
00:04:01,212 --> 00:04:05,400
fuerte en el sentido de que requiere que las claves de cifrado
realmente largas, si el cifrado fue corto

59
00:04:05,400 --> 00:04:09,535
las claves posiblemente no puedan satisfacer esta definición
en un flujo de cifrado particular

60
00:04:09,535 --> 00:04:14,328
Bueno, vamos a intentar debilitar
la definicion en un pequeńo bit

61
00:04:14,328 --> 00:04:19,114
y pensar en lo que se vio en el segmento anterior
y nosotros vamos a decir que en lugar de requerir

62
00:04:19,114 --> 00:04:23,841
de dos distribuciones que sean absolutamente
identicas que es lo que nosotros podemos requerir, esto es

63
00:04:23,841 --> 00:04:28,686
que las dos distribuciones sean computacionalmente
indistinguibles. En otras palabras, que un pobre atacante

64
00:04:28,863 --> 00:04:33,353
no pueda distinguir entre las dos distribuciones
aun cuando estas sean

65
00:04:33,353 --> 00:04:37,815
muy, muy, pero muy diferentes.
Si entregamos una muestra de

66
00:04:37,815 --> 00:04:42,580
una distribucion y un ejemplo de otra
distribucion, el atacante no podrá decirnos que

67
00:04:42,580 --> 00:04:47,120
distribución corresponde a cada ejemplo dado.
Resulta que esta definicipin es actualmente

68
00:04:47,120 --> 00:04:51,716
considerada correcta, pero aun aspi es considerada
un poco demasiado fuerte,ya que todavía no puede satisfacer

69
00:04:51,716 --> 00:04:56,200
ańadir uno o mas restricciones y
y es que en lugar de decir que esta

70
00:04:56,200 --> 00:05:00,797
definicion deberia ser posible para todas las M0 y M1.
Se trata de mantener por pares sólo M0 M1

71
00:05:00,797 --> 00:05:05,208
que los atacantes puedan actualmente exhibir.
Bueno por lo que este hecho

72
00:05:05,208 --> 00:05:10,038
nos lleva a la definición de la semántica
de la seguridad.Y así, una vez más se trata de semántica

73
00:05:10,038 --> 00:05:15,050
segura para claves de una sola vez, en otras palbras
cuando el atacante solo obtuvo un solo texto

74
00:05:15,050 --> 00:05:19,819
cibrado. Y así, la forma en que definimos la semántica
de la seguridad es definiendo dos experimentos,

75
00:05:19,819 --> 00:05:24,562
Bueno, nosotros definieremos el experimento 0 y
el experimento 1. Y mas generalmente nosotros habremos

76
00:05:24,562 --> 00:05:29,230
de pensaar de etos esperimentos como B parentesis.
donde B puede ser cero o uno. Esto esta bien si

77
00:05:29,230 --> 00:05:32,890
la realización de estos experimentos es realizada como
sigue, nosotros tenemos un adversario que esta intentando

78
00:05:32,890 --> 00:05:37,161
romper el sistema. Un adversario A, que
es el análogo de realizar

79
00:05:37,161 --> 00:05:41,279
las pruebas estadisticas en el mundo de los pseudo
generadores aleatorios. Y entonces cuando el adversario hace

80
00:05:41,279 --> 00:05:45,093
lo siguiente, o realmente tenemos dos adversarios,
pero los adversarios son similares

81
00:05:45,093 --> 00:05:49,414
que nosotros podemos describirlos como un
solo adversario que en un cado toma

82
00:05:49,414 --> 00:05:53,634
la entradas de bit establecidas a cero y en
en otros casos toma estas entradas extablecidas

83
00:05:53,634 --> 00:05:57,193
a uno. Y ahora permitamen mostrar lo que estos
adversarios hacen. La primera cosa que el

84
00:05:57,193 --> 00:06:01,349
adversario va a realizar es probar una clave
aleatioria y entonces el adversario

85
00:06:01,349 --> 00:06:06,076
basicamente va la salida tomada de los dos mensajes
M0 y M1. Bueno, esto es en un par de mensajes

86
00:06:06,076 --> 00:06:11,039
explitos que el atacante quiere desafiar y es
usual que nosotros no intentamos

87
00:06:11,039 --> 00:06:15,766
esconder la longitud de los mensajes,
nosotros requerimos que el mensaje sea de igual

88
00:06:15,766 --> 00:06:21,643
longitud. Y entonces el adversario basicamente
habra de obtener la salida del cifrado de M0

89
00:06:21,643 --> 00:06:25,890
o el cifrado de M!. Bueno, de hecho en el
experimento 0, el adversario habra de tomar la salida

90
00:06:25,890 --> 00:06:30,301
del cifrado de M0. En el experimento 1 el adversario
tomara la salida del cifrado de

91
00:06:30,301 --> 00:06:34,385
M1. Bueno, esta es la diferencia entre los experimentos.