0:00:00.000,0:00:03.911
Моя цель для следующих нескольких сегментов, чтобы показать вам, что если мы используем безопасное PRG, мы будем

0:00:03.911,0:00:07.892
получите безопасный поток безопаснее. Первое, что нам нужно сделать, это определить, что делает это

0:00:07.892,0:00:11.679
означает для потока, безопаснее быть надежным? Так, всякий раз, когда мы определяем безопасности мы всегда

0:00:11.679,0:00:15.174
определение с точки зрения того, что может злоумышленник ду? И то, что злоумышленник

0:00:15.174,0:00:18.670
пытаетесь сделать? В контексте потоковых шифров Помните, что они используются только

0:00:18.670,0:00:22.737
onetime ключом и в результате наиболее злоумышленник когда-либо увидите является

0:00:22.737,0:00:26.754
только один cypher текст, зашифрованный с помощью ключа, который мы используем. И поэтому мы будем

0:00:26.754,0:00:30.772
ограничить нападавшие? способность в основном получать только один cypher текста. И в

0:00:30.772,0:00:34.641
факт позже мы собираемся позволить злоумышленнику сделать гораздо, гораздо, гораздо больше, но

0:00:34.641,0:00:38.460
для теперь мы просто собираюсь дать ему один cypher текст. И мы хотели найти,

0:00:38.460,0:00:42.560
что это означает для cypher безопасным? Так что первое определение,

0:00:42.560,0:00:46.892
приходит на ум в основном сказать, а может быть мы wanna требуют, чтобы злоумышленник

0:00:46.892,0:00:50.718
не удается восстановить фактически секретный ключ.[br]Ладно, так дано зашифрованного текста вам

0:00:50.718,0:00:54.609
не должно быть в состоянии восстановить секретный ключ. Но это страшное определения

0:00:54.609,0:00:58.717
потому что думать о падающих блестящий шифр но, как мы шифровать

0:00:58.717,0:01:02.855
сообщение с использованием ключа K является в основном мы просто вывести сообщение. Ладно это

0:01:02.855,0:01:07.427
Это блестящий шифр да, конечно, это не что-нибудь, учитывая сообщение просто

0:01:07.427,0:01:12.000
вывести сообщение как зашифрованного текста.[br]Это не особенно хорошее шифрование

0:01:12.000,0:01:16.029
Схема; Однако учитывая зашифрованного текста, главным образом сообщение бедных злоумышленник

0:01:16.029,0:01:20.493
нельзя восстановить ключ, потому что он не знает, что это ключ. И так как результат

0:01:20.493,0:01:24.630
Этот шифр, который явно является небезопасной, будет считаться безопасным по этому

0:01:24.793,0:01:28.636
требования безопасности. Так что это определение будет не хорошо. О ' кей поэтому он имеет

0:01:28.636,0:01:32.317
восстановление секретный ключ — неправильный путь для определения настроек безопасности. Так что следующее, что мы

0:01:32.317,0:01:35.999
может любопытное попытка является в основном просто сказать, ну, может быть, злоумышленник не заботится о

0:01:35.999,0:01:39.680
секретный ключ, то, что он действительно заботится о представляют собой обычный текст. Поэтому, возможно, она должна быть

0:01:39.680,0:01:43.518
жесткий злоумышленнику восстановить весь обычный текст. Но даже это не

0:01:43.518,0:01:48.223
работать, потому что давайте думать о следующей схемы шифрования. Предположим, так

0:01:48.223,0:01:53.436
Эта схема шифрования делает это, он принимает два сообщения, поэтому я собираюсь использовать два

0:01:53.436,0:01:58.014
линии для обозначения объединения двух сообщений M0 линии, линия M1 средства

0:01:58.014,0:02:03.100
СЦЕПИТЬ M0 и M1. И представьте, что схема делает это действительно выходы

0:02:03.100,0:02:08.060
M0 в ясной и объединять что шифрования M1. Возможно, даже

0:02:08.060,0:02:13.337
использование одной подушечкой раз все в порядке? И поэтому здесь злоумышленник является собираешься быть присвоен один

0:02:13.337,0:02:17.478
зашифрованный текст. И его целью будет восстановить весь мультифункциональной. Но

0:02:17.478,0:02:21.702
бедные злоумышленник не может сделать этого, потому что здесь, возможно мы зашифрованы M1 с использованием один

0:02:21.702,0:02:25.872
Раз Pad, поэтому злоумышленник не может восстановить фактически M1, потому что мы знаем

0:02:25.872,0:02:30.043
Один раз Pad является безопасным, учитывая только один зашифрованный текст. Так что это строительство

0:02:30.043,0:02:34.055
отвечали бы определение, но к сожалению явно это не безопасный

0:02:34.055,0:02:37.962
Схема шифрования потому, что мы просто утечка половину обычного текста. M0 —

0:02:37.962,0:02:42.185
полностью доступных злоумышленнику таким образом, даже хотя он не может восстановить в все

0:02:42.185,0:02:46.462
обычный текст он может быть в состоянии восстановить большую часть в виде обычного текста, и это явно

0:02:46.462,0:02:50.658
Необеспеченные. Поэтому, конечно, мы уже знаем решение, к этому и мы говорили о

0:02:50.658,0:02:54.747
Шэнон определение безопасности perfect тайны, где идея Шеннона был в

0:02:54.747,0:02:58.835
тот факт, когда злоумышленник перехватывает зашифрованный текст, он должен учиться абсолютно no

0:02:58.835,0:03:02.818
Информация о равнина текстов. Он не должен даже узнать один бит

0:03:02.818,0:03:07.221
обычный текст или даже он не должны узнать, он даже не должны быть в состоянии предсказать, немного

0:03:07.221,0:03:11.205
бит о торгах в виде обычного текста.[br]Абсолютно никакой информации о обычного текста.

0:03:11.205,0:03:14.926
Так что давайте очень кратко напомнить Шеннона концепции безопасной PFS

0:03:14.926,0:03:19.442
в основном мы сказали, что вы знаете учитывая шифра, мы сказали, что шифр совершенный

0:03:19.442,0:03:25.069
тайны если дано два сообщения с той же длины так случается, что распределение

0:03:25.069,0:03:30.167
шифр текстов. Но если мы выбираем случайный ключ и мы смотреть на распределение

0:03:30.167,0:03:34.838
шифр тексты, мы шифровать M0, мы получим точно такое же распределение, когда мы

0:03:34.838,0:03:39.257
Шифруйте M1. Интуиция здесь был, что если Консультативного наблюдает шифра тексты

0:03:39.257,0:03:43.839
Тогда он не знает ли он пришел от распределения в результате шифрования

0:03:43.839,0:03:48.203
M0 или он пришел от распределения в результате шифрования M1. И, как

0:03:48.203,0:03:52.513
результат, он не может сказать ли мы зашифрованным M0 или M1. И это верно для всех

0:03:52.513,0:03:56.877
сообщения из той же длины и, как следствие плохой злоумышленник не знает, действительно

0:03:56.877,0:04:01.212
какое сообщение зашифровано. Конечно, мы уже говорили, что это определение является слишком

0:04:01.212,0:04:05.400
сильный в том смысле, что он требует очень длинные ключи, если шифр имеет короткие

0:04:05.400,0:04:09.535
ключи не могут удовлетворить возможно это определение в частности потоковых шифров

0:04:09.535,0:04:14.328
может удовлетворить это определение. Ладно, так что давайте попробуем немного ослабить определение

0:04:14.328,0:04:19.114
и давайте думать для предыдущего сегмента, и мы можем сказать, что вместо требования

0:04:19.114,0:04:23.841
двух распределений быть абсолютно идентичными, то, что мы можем потребовать, является то, что

0:04:23.841,0:04:28.686
двух распределений просто быть вычислительно неразличимы. Другими словами бедных,

0:04:28.863,0:04:33.353
эффективное злоумышленник не может отличить двух распределений хотя

0:04:33.353,0:04:37.815
дистрибутивы могут отличаться очень, очень, очень. Что просто пример для

0:04:37.815,0:04:42.580
один распределения и образца для другой дистрибутив злоумышленник не может сказать

0:04:42.580,0:04:47.120
распространение он получил образец из.[br]Оказывается, это определение является на самом деле

0:04:47.120,0:04:51.716
почти сразу, но она все еще немного слишком сильным, что до сих пор не могут быть удовлетворены, так

0:04:51.716,0:04:56.200
Мы должны добавить еще одно ограничение, и что, что вместо того чтобы сказать что это

0:04:56.200,0:05:00.797
определение должно иметь справедливы для всех M0 и M1. Это провести для только пары M0 M1

0:05:00.797,0:05:05.208
что нападавшие могли фактически экспонат. Хорошо, так что это на самом деле

0:05:05.208,0:05:10.038
приводит нас к определению семантики безопасности. И поэтому, опять же это семантика

0:05:10.038,0:05:15.050
безопасность для один раз, зашифрованный ключ, другими словами когда злоумышленник является только данного

0:05:15.050,0:05:19.819
текст. И это путь, мы определяем семантической безопасности путем определения двух экспериментов,

0:05:19.819,0:05:24.562
Ладно мы определить эксперимент 0 и эксперимент 1. И вообще мы будем

0:05:24.562,0:05:29.230
Думайте о них, как экспериментов скобки B, где B может быть ноль или один. Хорошо, так что

0:05:29.230,0:05:32.890
путь, эксперимент определяется следующим, у нас есть противника это

0:05:32.890,0:05:37.161
пытаясь сломать систему. Противник A, что любопытное аналог статистической

0:05:37.161,0:05:41.279
тесты в мире псевдо случайных генераторов. А затем делает challenger

0:05:41.279,0:05:45.093
следующее, так что действительно у нас есть два претендентов, но претенденты настолько

0:05:45.093,0:05:49.414
аналогичные, что мы можем просто описать их как единый претендент, что в одном случае принимает

0:05:49.414,0:05:53.634
его входов биты равным нулю, и другой случай принимает его входов, бит со значением

0:05:53.634,0:05:57.193
один. И позвольте мне показать вам, что делать эти претенденты. Первое, что

0:05:57.193,0:06:01.349
Челленджер собираешься сделать это является собираешься выбрать случайный ключ, а затем противника

0:06:01.349,0:06:06.076
в основном собирается вывести два сообщения M0 и M1. Хорошо, так это явный

0:06:06.076,0:06:11.039
пара сообщений, которые злоумышленник хочет быть оспорены на и как обычно мы не

0:06:11.039,0:06:15.766
пытаясь скрыть длину сообщений, мы требуем что сообщения равно

0:06:15.766,0:06:21.643
Длина. А затем challenger в основном будет шифрования M0

0:06:21.643,0:06:25.890
или шифрования M1, ладно, так в эксперименте 0 challenger выведет

0:06:25.890,0:06:30.301
Шифрование M0. В эксперименте 1 претендент будет выводить шифрования

0:06:30.301,0:06:34.385
М1. Ладно, так что разница между двумя экспериментов. И затем

0:06:34.385,0:06:38.796
противник пытается угадать в основном ли ему шифрования M0

0:06:38.796,0:06:44.051
или шифрования M1. Хорошо, так вот немного нотации Давайте

0:06:44.051,0:06:50.260
Определите события ВБ быть события, что эксперимент B противника вывода один.

0:06:50.260,0:06:55.084
Хорошо, так что это просто событие, что в основном в эксперименте нулевой W0 означает, что

0:06:55.084,0:07:00.342
противник вывести один, а в эксперименте, один W1 означает противника один. И

0:07:00.342,0:07:05.291
Теперь мы можем определить преимущества этого противника, в основном сказать, что это

0:07:05.291,0:07:10.425
под названием семантика безопасности преимущество противника A против схемы E,

0:07:10.425,0:07:15.497
чтобы быть разница вероятности этих двух событий. Другими словами мы находимся

0:07:15.497,0:07:20.136
Глядя на ли противник действует по-разному, когда ему

0:07:20.136,0:07:24.818
Шифрование M0 от когда ему шифрования M1. И я хочу сделать

0:07:24.818,0:07:29.201
Конечно, это ясно, так что я собираюсь сказать это еще один раз. Так что в эксперимент ноль, он был

0:07:29.201,0:07:33.530
Учитывая шифрования M0 и в эксперименте, один он получил шифрования

0:07:33.530,0:07:37.700
М1. Теперь мы просто заинтересованы в ли противника вывода 1 или нет.

0:07:37.700,0:07:42.356
... В этих экспериментах. Если в обоих экспериментах, противник вывода 1 с

0:07:42.356,0:07:47.013
же вероятность того, что означает противника не смог отличить

0:07:47.013,0:07:51.549
два эксперимента. Эксперименты ноль, в основном выглядит противника же

0:07:51.549,0:07:56.206
как эксперимент один, потому что в обоих случаях загрузить один с одинаковой вероятностью.

0:07:56.206,0:08:01.286
Однако если противник имеет возможность вывода 1 в одном эксперименте с значительно

0:08:01.286,0:08:05.761
различные вероятности чем в другой эксперимент, то противник был

0:08:05.761,0:08:10.266
фактически в состоянии отличить двух экспериментов. Хорошо так... Говорить об этом больше

0:08:10.266,0:08:14.455
формально по существу преимущество снова потому что это различие двух

0:08:14.455,0:08:18.918
вероятностей преимущество это число между 0 и 1. Если преимущество

0:08:18.918,0:08:22.886
близка к нулю, что означает, что противник был не в состоянии отличить

0:08:22.886,0:08:27.129
эксперимент ноль от эксперимента, один.[br]Однако если преимущество близко к одной,

0:08:27.129,0:08:31.538
Это означает, что противник был очень хорошо различать эксперимент ноль от

0:08:31.538,0:08:36.112
эксперимент один и что действительно означает, что он был в состоянии отличить шифрования

0:08:36.112,0:08:40.299
от M0 от шифрования M1 Ладно?Так что это определение. На самом деле

0:08:40.299,0:08:44.055
Это просто определение преимущество и определение является только то, что

0:08:44.055,0:08:47.714
Вы ожидаете в основном, что мы будем говорить, что схема симметричного шифрования

0:08:47.714,0:08:52.346
семантически обеспечить, если для всех эффективных противников здесь я положил их в кавычки

0:08:52.346,0:08:56.932
Опять же «для всех эффективных противников преимуществом является незначительным.» Другими словами,

0:08:56.982,0:09:01.808
нет эффективного противника можно отличить от шифрования Шифрование M0

0:09:01.808,0:09:06.103
M1, и в основном это то, что он неоднократно говорит что для этих двух

0:09:06.103,0:09:10.759
сообщения, которые противник смог выставить он не смог отличить

0:09:10.759,0:09:15.064
Эти два дистрибутивы. Теперь я хочу показать вам это, на самом деле это очень

0:09:15.064,0:09:19.595
элегантные определение. Это может показаться не так сразу, но я хочу показать вам некоторые

0:09:19.595,0:09:24.410
последствия этого определения, и вы увидите, почему определение именно путь

0:09:24.410,0:09:28.601
это. Ладно, так что давайте рассмотрим несколько примеров. Поэтому первый пример Предположим

0:09:28.601,0:09:33.190
у нас есть сломанной шифрование схему, иными словами Предположим, что у нас есть противник a

0:09:33.190,0:09:38.285
что-то зашифрованного текста он способен всегда выводят наименее

0:09:38.285,0:09:44.149
значащий бит в виде обычного текста. Ладно так учитывая шифрования M0, этот противник

0:09:44.149,0:09:48.799
способен вывести наименее значимых бит M0. Так что это страшное

0:09:48.799,0:09:52.911
шифрование схему потому что он в основном утечек наименее значимых бит

0:09:52.911,0:09:57.128
обычный текст, только что зашифрованный текст. Поэтому я хочу показать вам, что эта схема является

0:09:57.128,0:10:01.609
Поэтому семантически безопасных так что вроде показывает, что если система является семантически

0:10:01.609,0:10:05.931
безопасный чем нет никакой злоумышленник этого типа. Ладно, так что давайте посмотрим, почему это система

0:10:05.931,0:10:10.254
семантически небезопасно, хорошо, так что мы собираешься делать это мы 're gonna основном использовать

0:10:10.254,0:10:14.366
Наш противник, который имеет возможность узнать наши самые незначительные биты, мы собираемся

0:10:14.366,0:10:18.372
Используйте его сломать семантической безопасности, поэтому мы будем использовать его чтобы отличить

0:10:18.372,0:10:22.755
эксперимент zero из эксперимента, один хорошо так что здесь является то, что мы собираемся делать. Мы находимся

0:10:22.755,0:10:26.987
алгоритм B, мы собираемся быть алгоритм B и B собирается использовать алгоритм

0:10:26.987,0:10:31.165
алгоритм A в его живот. Итак, первое, это будет происходить в

0:10:31.165,0:10:35.608
курс challenger собирается выбрать случайный ключ. Первое, это происходит

0:10:35.608,0:10:39.762
произойдет это, что нам нужно вывести два сообщения. Сообщения, которые мы собираемся

0:10:39.762,0:10:43.493
для вывода в основном собираются иметь по-разному значащих бит. Таким образом, одна

0:10:43.493,0:10:47.727
сообщение идет до конца с нуля и одно сообщение идет до конца с одним. Теперь то, что

0:10:47.727,0:10:51.205
challenger собирается делать? Challenger собирается дать нам

0:10:51.205,0:10:55.238
шифрование или M0, M1, в зависимости от ли в эксперимент 0 или

0:10:55.238,0:10:59.120
в эксперименте 1. И затем мы просто направить этот зашифрованный текст противника

0:10:59.120,0:11:03.871
Ладно так противника а. Теперь, что является собственностью противника A? Учитывая шифра

0:11:03.871,0:11:08.505
текст, противник A может сказать нам что наименее значимых битов в виде обычного текста.

0:11:08.505,0:11:13.374
Другими словами противника собирается вывести наименее значимых битов M0 или M1

0:11:13.374,0:11:17.892
но низкий, и вот это в основном бит б. И тогда мы просто

0:11:17.892,0:11:23.050
собирается вывода, что, как наш гость, так пусть? s назвать эту вещь B премьер хорошо так что теперь это

0:11:23.050,0:11:28.376
Описывает семантической безопасности противника.[br]И теперь вы скажите мне, что такое семантическая

0:11:28.376,0:11:33.593
преимущество безопасности этого противника? Ну так давайте посмотрим. В эксперименте нулю что такое

0:11:33.593,0:11:38.775
вероятность того, что противник B выводит один? Хорошо в эксперимент нулевой, это всегда

0:11:38.775,0:11:43.704
Учитывая шифрования M нулю и, следовательно, противник всегда выводится A

0:11:43.704,0:11:48.633
наименее значимых бит M нулевой который всегда бывает равным нулю. В эксперименте

0:11:48.633,0:11:53.120
ноль, B всегда выводит ноль. Поэтому вероятность того, что выводит один равен нулю.

0:11:53.120,0:11:57.827
Однако в эксперименте, один, мы дали шифрования M1. Так как вероятно

0:11:57.827,0:12:02.783
противник B для вывода одного в эксперименте один хорошо он всегда выводит один, снова

0:12:02.783,0:12:07.428
свойства алгоритма A и, следовательно, преимущество в основном является одним.

0:12:07.428,0:12:12.384
Так что это огромное преимущество, это как большой, как это собираешься получить. Это означает, что это

0:12:12.384,0:12:17.091
противник полностью сломал системы.[br]Итак мы рассматриваем, так под семантической

0:12:17.091,0:12:22.295
безопасности, в основном просто выведение наименее значимых бит вполне достаточно, чтобы

0:12:22.295,0:12:27.187
перерыв системы под определение семантического безопасности. Ладно теперь интересные

0:12:27.187,0:12:32.388
Здесь конечно же заключается в том, что это не просто о наименее значимых бит, в

0:12:32.388,0:12:37.117
факт сообщения например значащий бит, вы знаете

0:12:37.117,0:12:42.040
бит число семь возможно XOR всех битов в сообщении и так далее

0:12:42.040,0:12:46.552
и так далее какой-либо информации, любой бит о обычного текста, они могут быть

0:12:46.552,0:12:50.814
узнал в основном, будет означать, что система не является семантически secure. Так

0:12:50.814,0:12:55.532
в основном все, что противник будет нужно сделать бы придумать два сообщения

0:12:55.532,0:13:00.249
M0 и М1, такие что под одну вещь что они узнали, что он является значение ноль и затем

0:13:00.249,0:13:04.626
Другая вещь, значение, это один. Так например, если A смог узнать XOR

0:13:04.626,0:13:08.775
бит сообщения затем M0 и M1 будет просто имеют различные

0:13:08.775,0:13:13.265
XOR для всех битов их сообщений, и затем этот противник A будет

0:13:13.265,0:13:18.174
также быть достаточно сломать семантической безопасности. Так, в основном хорошо для шифра

0:13:18.174,0:13:23.203
семантически безопасна, то раскрывается не бит информации

0:13:23.203,0:13:27.392
эффективное противника. Хорошо, так это именно концепция совершенной тайне только

0:13:27.392,0:13:31.318
применяется только эффективным противников, вместо того, чтобы все противников. Так что следующий

0:13:31.318,0:13:35.045
вещь, которую я хочу показать вам это фактически один раз pad фактически является

0:13:35.045,0:13:38.821
семантически безопасным, они лучше быть семантически безопасных потому что это в самом деле,

0:13:38.821,0:13:42.773
Это больше, чем, что это совершенно безопасным.[br]Итак, давайте посмотрим, почему это правда. Ну так

0:13:42.773,0:13:47.010
Опять же, это один из этих экспериментов, так, предположим, что у нас есть противника, что претензии

0:13:47.010,0:13:51.449
сломать семантической безопасности один раз pad. Первый, собираешься сделать противника

0:13:51.449,0:13:55.874
Это он собираешься выводятся два сообщения M0 и M1 той же длины.

0:13:55.874,0:13:59.667
Теперь то, что он получает обратно, как вызов? Как вызов он получает либо шифрования

0:13:59.667,0:14:03.988
M0 или шифрования M1 под одно время pad.

0:14:03.988,0:14:07.886
И он пытается различать эти два возможных шифр тексты, которые он получает, право?

0:14:07.886,0:14:12.259
В эксперименте нулю, он получает шифрования M0 и в эксперименте, один, он получает

0:14:12.259,0:14:16.579
Шифрование M1. Ну так позвольте мне спросить вас, что такое преимущество противника

0:14:16.579,0:14:21.297
A против один раз патент? Так что я помню, что свойство те I

0:14:21.297,0:14:26.208
имел это что, что K, XOR M0 распространяется одинаково к K, XOR M1.

0:14:26.208,0:14:31.187
Другими словами эти дистрибутивы являются абсолютно идентичными распределения,

0:14:31.187,0:14:36.026
дистрибутивов, идентичны. Это свойство XOR. Если мы XOR случайных pad

0:14:36.026,0:14:40.674
K ни с чем, M0 или M1, мы получаем равномерное распределение. Так как в

0:14:40.674,0:14:45.382
случаях, алгоритм A дается как вклад точно такое же распределение. Может быть

0:14:45.382,0:14:50.209
равномерное распределение по текстам шифра. И поэтому он является собираешься себя точно

0:14:50.209,0:14:55.036
же в обоих случаях, потому что оно было дано точное распределение в качестве входных данных. И, как

0:14:55.036,0:14:59.699
результат, его преимущество равен нулю, что означает, что бывший pad является семантически

0:14:59.723,0:15:04.148
безопасный. Теперь самое интересное здесь, это не только семантически безопасным, это

0:15:04.148,0:15:08.244
семантически безопасный для всех противников.[br]Мы даже не ограничивать

0:15:08.244,0:15:12.450
Противники эффективным. Не противник, неважно, как вы умны, нет

0:15:12.450,0:15:16.875
противник сможет отличить K XOR M0 от K XOR M1, потому что два

0:15:16.875,0:15:21.299
Дистрибутивы являются идентичными. Ладно так один раз pad является семантически безопасный. Ладно,

0:15:21.299,0:15:25.559
так что завершает нашего определения семантической безопасности, так что следующее, что мы

0:15:25.559,0:15:30.093
доказать собирается сделать для безопасных PRG, фактически подразумевает, что поточный шифр

0:15:30.093,0:15:31.186
семантически безопасный.