Semantic Security (16 min)

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

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

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

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

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

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

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

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

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

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

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

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

не удается восстановить фактически секретный ключ.
Ладно, так дано зашифрованного текста вам

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

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

сообщение с использованием ключа K является в основном мы просто вывести сообщение. Ладно это

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

вывести сообщение как зашифрованного текста.
Это не особенно хорошее шифрование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Информация о равнина текстов. Он не должен даже узнать один бит

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

бит о торгах в виде обычного текста.
Абсолютно никакой информации о обычного текста.

Так что давайте очень кратко напомнить Шеннона концепции безопасной PFS

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

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

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

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

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

Тогда он не знает ли он пришел от распределения в результате шифрования

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

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

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

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

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

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

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

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

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

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

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

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

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

распространение он получил образец из.
Оказывается, это определение является на самом деле

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

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

определение должно иметь справедливы для всех M0 и M1. Это провести для только пары M0 M1

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

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

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

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

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

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

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

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

тесты в мире псевдо случайных генераторов. А затем делает challenger

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

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

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

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

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

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

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

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

Длина. А затем challenger в основном будет шифрования M0

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

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

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

противник пытается угадать в основном ли ему шифрования M0

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

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

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

противник вывести один, а в эксперименте, один W1 означает противника один. И

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

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

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

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

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

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

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

М1. Теперь мы просто заинтересованы в ли противника вывода 1 или нет.

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

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

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

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

Однако если противник имеет возможность вывода 1 в одном эксперименте с значительно

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

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

формально по существу преимущество снова потому что это различие двух

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

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

эксперимент ноль от эксперимента, один.
Однако если преимущество близко к одной,

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

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

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

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

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

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

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

нет эффективного противника можно отличить от шифрования Шифрование M0

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

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

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

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

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

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

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

что-то зашифрованного текста он способен всегда выводят наименее

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

способен вывести наименее значимых бит M0. Так что это страшное

шифрование схему потому что он в основном утечек наименее значимых бит

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

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

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

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

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

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

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

алгоритм B, мы собираемся быть алгоритм B и B собирается использовать алгоритм

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

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

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

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

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

challenger собирается делать? Challenger собирается дать нам

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

в эксперименте 1. И затем мы просто направить этот зашифрованный текст противника

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

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

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

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

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

Описывает семантической безопасности противника.
И теперь вы скажите мне, что такое семантическая

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

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

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

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

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

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

противник B для вывода одного в эксперименте один хорошо он всегда выводит один, снова

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

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

противник полностью сломал системы.
Итак мы рассматриваем, так под семантической

безопасности, в основном просто выведение наименее значимых бит вполне достаточно, чтобы

перерыв системы под определение семантического безопасности. Ладно теперь интересные

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

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

бит число семь возможно XOR всех битов в сообщении и так далее

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

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

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

M0 и М1, такие что под одну вещь что они узнали, что он является значение ноль и затем

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

бит сообщения затем M0 и M1 будет просто имеют различные

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

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

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

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

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

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

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

Это больше, чем, что это совершенно безопасным.
Итак, давайте посмотрим, почему это правда. Ну так

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

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

Это он собираешься выводятся два сообщения M0 и M1 той же длины.

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

M0 или шифрования M1 под одно время pad.

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

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

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

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

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

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

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

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

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

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

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

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

безопасный. Теперь самое интересное здесь, это не только семантически безопасным, это

семантически безопасный для всех противников.
Мы даже не ограничивать

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

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

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

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

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

семантически безопасный.