Расширение домена для MAC за гранью барьера рождения

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:04, 20 декабря 2015.
Domain Extension for MACs Beyond the Birthday Barrier
MAC.png
Авторы Yevgeniy Dodis[@: 1] and
John Steinberger[@: 2]
Опубликован 2011 г.
Перевели Nikolay Morozov
Год перевода 2015 г.
Скачать оригинал


Аннотация. Взяв код опознавательного сообщения от до битов (например: фиксированный ключ блокирующего кода) с защитой этого кода против запросов, мы разработали переменную длину MAC'а, достигая степени безопасности множества против запросов общей длиной в . В частности, наша конструкция является первой, нарушившей «барьер рождения» для расширения домена MAC от некомпрессионных базисных элементов, так как граница нашей безопасности распространяется даже на множества (при условии, что является наилучшим ). В противоположность этому, предыдущая лучшая конструкция для расширения домена MAC для базисных элементов от до бит, по Додису и Штайнбергеру, достигла степени безопасности MAC в , что означает, что не может пересечь «барьер рождения» в .

Введение

Большинство базисных элементов в симметричной криптографии построены из блочных шифров, таких как AES. В этой статье мы сконцентрируемся на вопросе проектирования переменной заданной длинны (VIL) кода аутентификации сообщений (MAC) из блочных шифров. Этот вопрос очень хорошо изучен, как мы покажем это ниже. Тем не менее, за редким исключением, большинство существующих конструкций и их исследование делают следующие два допущения: (а) Псевдослучайность: блочный шифр моделируется как псевдослучайные перестановки (PRP); и (б) Секретность промежуточных итогов: атакующий узнает только поведение VIL-MAC ввода / вывода, но не узнает ни одного промежуточного результата. Додис отмечал: каждое из этих предположений может быть как чрезмерно сильным, так и просто слишком нереальным в следующих двух сценариях.

Расширение доменов MAC. Это наш главный вопрос. Так как желаемый MAC базисных элементов должен быть всего лишь непредсказуемым, было бы весьма желательно предположить, что блочный шифр в такой же мере непредсказуем, в отличие от псведослучайности. Действительно, кажется, что предположение, что блочный шифр непредсказуем гораздо слабее, чем предположение о полной псевдослучайности: чтобы отказаться от последнего, все, что нужно сделать – это предсказать один бит из «случайно-выглядящей» информации о блочном шифре с вероятностью немного большей, чем , в то время как созданный образец требует полного вычисления значения блочного шифра на новой точке с нетривиальной вероятностью. Например, в неоднородной модели, любой блочный шифр (на самом деле, даже нетривиальный псевдослучайный генератор) с -битным ключом может быть очень легко отличен от случайного с преимуществом в . Насколько нам известно, не существует границ ниже для отказа от непредсказуемости, что означает, что близкая к безопасность MAC может быть возможна для такого блочного шифра.

Иначе говоря, пока мы надеемся на то что существующие блочные шифры на самом деле являются PRP, вполне разумно предположить, что их MAC безопасность может быть на порядок лучше, чем их же PRP безопасность. Таким образом, если мы можем разработать VIL-MAC, безопасность которого тесно связана с непредсказуемостью блочных шифров, эта система безопасности может быть более надежной, чем MAC, анализ которой предполагает псевдослучайность шифра.

Конечно, можно понадеяться на то, что существующий блок-шифр, который основан на системе VIL-MACS, такой как, например, CBC-MAC [1][2] или HMAC [3][4] (чьи функция сжатия также используют блочный шифр) на самом деле уже безопасны, тогда как блочный шифр непредсказуем. К сожалению, как разобрано у Додиса и со-авторов [5][6][7] ( особенно [7]) - это не так. За редким исключением, которые скоро будут упомянуты, стандартные конструкции совершенно не безопасны, когда иллюстрированы примером непредсказуемых блочных шифров, часто, несмотря даже на простые доказательства безопасности, когда кто-то проектирует блочный шифр как PRP.

Устойчивость к боковым каналам. Даже если блочный шифр является очень хорошим PRP, на практике многие криптографические внедрения становятся так называемой жертвой различных форм атаки со стороны боковых каналов [8][9][10][11][12], где физическая реализация криптографических примитивов может выдать дополнительную информацию, такую как время вычисления, энергопотребление, излучение/шум/тепловыделение и так далее. Таким образом, люди, следящие за данными приборами безопасности, обращают особое внимание на обеспечение безопасности блочных шифров, таких как AES, и на любого рода атаки со стороны боковых каналов. Хотя это может быть непростой задачей, представляется разумным, что специализированная реализация технического оборудования AES может быть весьма устойчива к традиционным формам атаки со стороны боковых каналов. С другой стороны, когда блочный шифр используется в некоторых более сложных приложениях, таких как например разработка VIL-MAC, “устойчивых к утечке” структур данных для каждого из таких приложений, вместо того чтобы сделать это для одного строительного блока фиксированной длины(как AES). Руководствуясь этими соображениями, Додис и со-авторы [5][6][7] предложили модель, в которой  “внутренности” структуры данных блочного шифра считаются безопасными, как обычно, но все внешние входы/выходы могут стать потенциальными жертвами утечки (например через боковой канал). Чтобы дать этой модели название, одновременно делая ее более обобщенной, мы говорим, что конструкция (детерминистического) MAC P, использующего низкий уровень ключевого примитива(ов) f "прозрачна" (w.r.t. f), если: (a) ключ для P состоит только из одного из большого количества ключей для f; (b) делая запрос от М к P, атакующий не только получает P (M), но также и все пары ввода/вывода для каждого сигнала, направленного к f, сделанного во время вычисления P (M). Так как P детерминирован, и все ключи "находятся внутри" f, это действительно предоставляет атакующему всю расшифровку P (M), за исключением того, что происходит во время посылки сигналов к f. Возвращаясь к нашей установке, мы заинтересованы в создании "прозрачного" VIL-MAC из блочного шифра. Как мы увидим далее, этот вопрос очень нетривиален, даже если блочный шифр будет предположен псевдослучайным, не говоря о том, что непредсказуемым. Действительно, как и наблюдалось [5][6][7], большинство существующих VIL-MAC, включая CBC-MAC [1][2] и HMAC [3][4], показывают свою абсолютную незащищенность от того, когда промежуточные результаты "утекают" к атакующему, даже при случае с PRP.

Наш главный результат. Мотивированные этими приложениями, мы задаем тот же самый вопрос что и Додис и со-авторы [5][6][7], который одновременно обращается к обеим вышеупомянутым проблемам.

Вопрос 1. Можно ли создать "прозрачный" VIL-MAC P из блочного шифра , который только принят "непредсказуемым"?

Как ранее было упомянуто, большинство стандартных VIL-MAC, состоящих из блочных шифров, не справляются с задачей адресовать либо MAC-сохранение, либо прозрачность (даже с PRP).Таким образом, мы обращаемся к известным безопасным подходам. Как оказывается, все они следовали принципу Эн и Беллар [13] сперва составляя сжатие Weakly Collision Resistant (WCR) хеш-функцию от до битов, для , тогда выполнение итераций этого WCR фиксированной длины , используя некоторые вариации метода Меркла-Дамгарда, и, наконец, создавая новый блочный шифр. По Пренелю и ван Уршоту [14], любая конструкция этого вида может в лучшем случае достигнуть "безопасности рождения". Транслированный к установкам MAC-сохранения, даже если наш оригинальный MAC не может быть подделан с вероятностью , использующий запросов, получившийся VIL-MAC P не может обладать большей безопасностью чем , что означает, что не может пересечь , даже если , как предполагается, имеет значение (самое лучшее) .

Интересно, что даже достижение "безопасности рождения" является достаточной тяжелой операцией, когда допускается непредсказуемость блочного шифра. Первая безопасная конструкция Додиса и Пуния [6], основанная на сети Фейстеля, достигла безопасности лишь . Граница была улучшена до Додисом, Пиетзаком и Пунией [5], которые использовали “улучшенную CBC” конструкцию. Наконец, Додис и Штейнбергер [7] показали (практически) безопасность , используя новый анализ функции сжатия Шримптона-Стема [15]. Все эти конструкции были также прозрачны.

Мы задаемся вопросом - возможно ли спроектировать (по возможности, прозрачный) VIL-MAC, состоящий из блочных шифров с постоянной безопасностью рождения. Если не может быть подделан с вероятностью , используя запросов, мы бы хотели создать VIL-MAC P с безопасностью по значению близкой к , подразумевая, что она будет значима даже для значений , приближающихся к , в то время как предполагается имеет значение (самое лучшее) . В качестве нашего главного результата, мы отвечаем на этот вопрос утвердительно. Неофициально (см. Раздел 4 для подробностей).

TemplateTheoremIcon.svg Теорема Теорема 1
Существуют установленные многочлены и и конструкция P прозрачного VIL-MAC от -битного блочного шифра , такого что скорость в квадрате равна и безопасность MAC против запросов, имеющих длину , в лучшем случае представляет собой , где –это безопасность MAC от запросов . В частности, эта граница важна для и приближающимся к значению .
Доказательство
Без доказательства.

Связанные работы. Как мы уже упомянули, задача достижения безопасности за границей барьера рождения для создания VIL-MAC из непредсказуемых блочных шифров была открыта до начала нашей работы. Фактически, единственное расширение домена для MAC за границей безопасности барьера рождения было достигнуто только недавно Ясуда [16] и Ли и Стейнбергером [17]. Однако, оба результата начинались с сокращающегося MAC-а строго больше чем к бит. Как мы увидим далее, создание таких сокращающихся MAC-ов (с безопасностью за барьером рождения) из непредсказуемых блочных шифров очень нетривиально, и будет одной из ключевых задач, которую мы решим во время доказательства нашего основного результата. (Однако, хотим отметить, что наш результат не просто сводится к построению к разрядного MAC-а, а не -битного до -битного MAC-а).

Другая связанная область это область для создания VIL псевдослучайных функций (PRF) с безопасностью за границей барьера рождения от PRP, или более широко, PRF фиксированной длины. В частности были найдены несколько таких конструкций [18][19][20][21][22][23]. Однако, предельно ясно, что ни одна из них не работает ни для расширения домена MAC, ни для создания VIL-MAC (уже не говоря о PRF), когда промежуточные результаты вычисления пропущены. Например, заключение нашего основного результата, давая прозрачный VIL-MAC от - обеспечивает PRP с безопасностью , кажется новшеством.

Возможно, самая близкая к нашей работа это статья Маурера и Тессаро [24], которые показали, как создать случайный оракул переменной длины из -до- битого случайного оракула. Их конструкция, проанализированная в независимых работах [25][26], имеет постоянную полиномиальную скорость (точно так же как наша разработка) и безопасность , для любого . Однако, эти два параметра настройки несравнимы. С другой стороны, работа Маурера-Тессаро должна встроить “неразличимый имитатор” для их установки (которой нужно “извлечение ввода”, не требуемое в нашей установке). Однако, они брали действительно случайную функцию и могли использовать различные вычисления вероятности при получении результата. В нашей установке непредсказуем только блочный шифр, поэтому мы должны сделать явное приведение к невозможности взлома, что делает процесс существенно более деликатными.

Схема Нашей Конструкции

Наша конструкция состоит из нескольких автономных уровней. В качестве дополнительной пользы, некоторые из этих уровней (см. ниже) представляют собой потенциально независимый интерес и могут быть также использованы в других целях.

Шаг 1: Сокращение до -TO- WCR и MAC -TO-. Во-первых, мы обращаем внимание, что вышеупомянутый барьер рождения [14] из подхода Эн-Беллар больше не работает, если мы встраиваем хеш-функцию WCR F от до бит (для некоторого , например ). А именно, “день рождения на битах” все еще может дать достаточно неплохую безопасность . Однако, даже если мы преуспеваем при этом за границей барьера безопасности рождения (который будет одним из наших ключевых результатов), мы теперь также должны создать "конечный" MAC G от до бит. Таким образом, использование известных методик, но с различными параметрами (см. Лемму 1 и рис. 1), наша проблема уменьшается до создания WCR F от до бит и MAC G от до бит (оба за барьером рождения).

Шаг 2: Сокращение до функций без покрытий. Оказывается, что обе эти задачи — конструкция функции WCR F и конструкция MAC G – могут быть решены при помощи более сильного (ключевого) примитива, который мы вводим далее – функция без покрытий (cover-free). Неформально, имитовставка от (у нас будет ) до (для некоторого параметра ), где принадлежит названа cover-free (CF) если, предоставив доступ оракула к , невозможно произвести последовательность (отдельных) запросов принадлежит таким образом, что для некоторых , принадлежащих для всех l, принадлежащих [t]. Другими словами, для каждого нового запроса одна из координат должна быть "раскрыта" предыдущими координатами этого же индекса. Случай соответствует стандарту к -разрядной безопасности WCR, однако лучшая (и в особенности за границей барьера безопасности рождения), cover-free безопасность может быть достигнута при больших значениях .

Во-первых, как изображено на левой стороне рис. 2, мы можем составить CF с независимо-ключевыми блочными шифрами , определяя , где . Мы видим, что получившийся является безопасным MAC от бит до бит. То есть, MAC безопасность сильно связана c CF безопасностью и безопасностью MAC f (см. Лемму 2). Новая подделка для также даст новую подделку для по крайней мере одного из с СF безопасностью . Так как , то мы уже получаем необходимое до бит MAC.

Что в данном случае еще более интересно, на правой стороне рис. 2 мы показываем, как составить CF функцию с с независимыми ключевыми блочными шифрами (в варианте режима "двойного канала" [27]), чтобы получить функцию WCR F от бит до бит. Более того, безопасность WCR F будет "примерно" , где это CF безопасность и это MAC безопасность (см. Лемму 3). Таким образом, пока мы можем создать CF с безопасностью , близкой к , безопасность WCR F также будет такой же. Доказательство этого результата использует "the bin-filling bin-guessing" игры Додиса и Штейнбергера [7].

Подводя итог, можно сказать, что наша задача создания VIL-MAC P таким образом уменьшается лишь до создания СF функции с безопасностью , где это безопасность MAC основного -бит до -бит примитива . Мы также хотим создать функцию CF с как можно меньшим (которое играет важную роль, так как эффективность P, включая размер ключа, пропорциональна ). См. Лемму 4.

Шаг 3: Создание CF функций. Этот шаг, безусловно, является наиболее важной частью нашей конструкции. Вдохновением для этой конструкции послужила вышеупомянутая статья, написанная Маурером и Тессаро [24], которые показали, как спроектировать случайный оракул VIL из -до--битового случайного оракула. Как мы уже говорили, свойства [24] несравнимы с нашими, тем более, что мы не можем сделать предположение о (псевдо)случайности нашего блочного шифра. Однако, наша конструкция CF функций весьма похожа на соответствующие "cover-free"-уровневые конструкции [24]. Хотя мы и производили некоторые изменения (фактически, упрощения) конструкции [24], наши исследования сильно отличаются от [24]. Наша CF конструкция имеет три уровня, которые мы неформально называем комбинаторным, криптографическим и алгебраическим. Нетерпеливый читатель может посмотреть на рис. 3 для конкретного примера (с и другим примечанием, объясненным ниже).

Шаг 3A: Использование вводо-ограничивающего семейства. Этот чисто комбинаторный шаг является таким же, что и в [24], и также является самым "дорогим" шагом нашей конструкции. Мы будем использовать безключевую функцию от до (здесь - параметр, который называется ограничивающим ввод функциональным семейством (IRFF; см. Определение 1). У IRFF есть свойство, что после того, как любая делает запрос к , число новых вводов , для которого -кортеж покрыт объединением , "не намного больше”, чем , и это должно быть справедливо даже когда почти . Напомним, что наша конечная цель состоит в том, чтобы убедиться в том, что весьма проблематично сделать любой такой новый ввод . В то время как IRFF-ы не вполне устраивают (и не могут!) нас, они гарантируют, что для атакующего остается немного способов "покрыть" новые вводы старыми вводами.

Мы обсуждаем известные конструкции IRFF в Разделе 4, но упоминаем, что конструкция IRFF является полностью комбинаторной и близко связана с конструкциями определенных типов очень неуравновешенных двудольных экспандеров. Несмотря на то, что эта область уже хорошо изучена, данные типы экспандеров еще не полностью поняты, и в особенности "критические" установки параметров, относящихся к нашему случаю, не были объектом большого внимания. Поэтому, хотя существование IRFF с “хорошими параметрами” известно (и приводят к асимптотической границе утвержденной в Теореме 1), определенные конструкции довольно неэффективны. Однако, поскольку эти параметры и эффективность улучшены будущим исследованием в вычислительной сложности, будет улучшена и наша конечная конструкция.

Шаги 3B-C: Добавление путаницы и смешивание. Вспомним, что IRFF преобразуют наш ввод в -кортеж . Чтобы получить окончательный -кортеж для нашей CF функции , мы предположим, что будем повторять данные двуступенчатые процедуры (шаги и ) раз, каждый раз с ново-составленным блочным шифром с ключом (таким образом общее количество ключей блочного шифра для будет ). Во-первых, мы передаем все значения через блочный шифр (“шаг путаницы”), получая значения . Это - криптографический уровень "путаницы". Далее мы алгебраически "смешиваем" все значения через установленное, степени , многомерное полиномиальное ,math>\ p ~ \, \! </math> (см. Уравнение 3). Это дает нам, один из выводов значений .

Интуицию для последних двух шагов тяжело объяснить. На высоком уровне, шаг путаницы (оценивающий ), несомненно, должен был сделать сокращение неподдельности, в то время как смешивающий шаг использует тот факт, что у полиномов невысокой степени есть всего несколько корней, таким образом, "нетривиальное" столкновение на выводе даст возможность предположить одно из значений , которые мы пытаемся подделать. Конечно, трудность состоит в том, чтобы успешно угадать, когда и где произойдет нетривиальное столкновение с , с вероятностью примерно , где - гарантия, данная IRFF (таким образом, близко к ). Оказывается, есть тривиальный способ угадывания с "рожденной" вероятностью , даже когда . Конечно, такая вероятность слишком мала, и это - то, почему мы и повторяем шаги раз, для соответственно выбранного параметра . Мы показываем, что необходимая стратегия предположения может быть уменьшена до анализа двух "bin-filling bin-guessing" игр. Значимость таких игр для расширению домена MAC была впервый введена Додисом и Штейнбергером [7]. К сожалению, эти две игры значительно более сложны чем игра [7] или, чем игра, используемая при доказательстве Леммы 3. Тем не менее, как наш наиболее сложный технический шаг, мы показываем, что обе игры могут быть выиграны с вероятностью примерно . Таким образом, выбирая (например, ), мы добираемся до желаемой границы .

Эффективность. Наша конечная конструкция VIL-MAC использует ключей для , где минимальное значение . Теоретически, мы можем уменьшить ключевой материал до единственного ключа для методом введения через установленные зарезервированные входные биты. А именно, чтобы моделировать (наибольшие) ключей таким образом, мы должны резервировать бит ввода (и "усечь" то же самое число бит в выводе), эффективно уменьшая длину блока конструкции от до . Из-за усечения вывода, мы также должны предположить не хватающие бит вывода, не возвращенных нашим фальсификатором, подвергаясь (приемлемому) дополнительному ухудшению барьера безопасности.

Наш конечный VIL-MAC также достигает нормы, примерно пропорциональной . Достижение низкого значения (полученного из комбинаторной части IRFF) более проблематично (см. Раздел 4), хотя экзистенциально можно также сделать . Следовательно, наилучшая скорость, которой мы можем достигнуть при нашем подходе, это . Поэтому, мы прежде всего рассматриваем наш результат как важный результат выполнимости, также как и результат Маурера и Тессаро [24]. Однако, наша выполнимость открывает путь для будущих, потенциально более эффективных конструкций.

Начальные Сведения

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

Для MAC мы рассматриваем следующую игру, где A - несовершенный противник с доступом оракула к :

Game Forge (A, f):

; ,

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

uде максимум взят по всем противникам A, делающим максимум запросов, имеющих общую длину (после дополнения, если требуется) и "продолжительности" на хотя бы T. "Продолжительность" определена, как полная продолжительность эксперимента, включая время, необходимое, чтобы вычислить ответы к запросам А. Кроме того, мы "объявляем" конечный проверочный запрос (и его длина) к A (так, чтобы A сделал запросов, если принадлежит ; иначе говоря, мы просим A подтвердить его же собственную подделку, если он попытается ее сделать).Когда длина установлена (то есть для некоторого принадлежащего ), является функцией и нам становится легко игнорировать последний параметр, записывая вместо .

Слабая стойкость к коллизиям или “wcr” безопасность функционального семейства - это максимальное преимущество противника в обнаружении коллизии для случайно вычисленного члена , когда этому участнику предоставлен доступ к оракулу. Мы пишем для увеличения преимущества перед всеми противниками А, создавая наибольшее количество запросов максимальной продолжительности . (Здесь мы не измеряем полную длину запроса, поскольку мы лишь измерим wcr безопасность входных конструкций установленной длины.) Мы опускаем формальный псевдокод - основанное определение этого стандартного понятия, но напоминаем, что противник должен сделать запросы, проверяющие его коллизию, а не просто вывести пару коллизии.

Зная длину блока и сообщение , мы предполагаем, что - это не-суффиксное кодирование длины a множителей бит (например, структура Меркла — Дамгарда для , которая предполагает длину как длину последнего блока). Кроме того, учитывая две ключевых функции сжатия : , мы объявляем имитовставку как

Где и каждый состоит из бит для всех принадлежащих принадлежащих (см. рис.1).

Доказательство следующей (стандартной) леммы есть в полной версии [28]:


Рис. 1. Вид нашей конструкции .


Лемма 1. Пусть , и рассматривают как функцию ключевого пространства . Тогда, для ,

Проще говоря, Лемма 1 сокращает нашу задачу до создания, от -bit до -bit примитив , функций сжатия F и G таким образом, чтобы у F была wcr безопасность за границей барьера рождения, и G имел mac безопасность за границей барьера рождения, основанные только на mac безопасности (то есть, нарушение wcr безопасности F должно означать нарушение mac безопасности , и, аналогично, нарушение mac безопасности G так же должно означать нарушение mac безопасности ).

Наконец, введем статье понятие "cover-free" семейства имитовставок . Здесь является определяющим параметром, и мы описываем выход, как как , где принадлежит для каждого . В "cover-free" игре противник посылает запросы по различным точкам и выигрывает, если для какого-либо каждый блок выхода “покрыт” предыдущим выходом, подразумевающим .

Такая игра образует следующее: Game Cover(A,g):

;

Если образует различные запросы по , что , для любого , Тогда A побеждает; Иначе, A проигрывает.

Мы определяем "cover-free" (CF) незащищенность как где максимум берется по всем противникам A, принимающим больше решений, и по времени T, с тем же условием, что указано выше для времени работы. Мы (неформально) говорим, что семейство функций свободно от перекрытий, чтобы обозначить, что маленькие свободные от перекрытий незащищенности.


Рис. 2. Слева - композиция . Справа - параллельная композиция .


Данное (свободное от перекрытий) семейство функций , где l-ый блок задан функцией и семейством функций , обозначим следующее семейство функций , как: . где и , и - сокращение для конкатенации (см. рис. 2). Так же обозначим параллельную композицию: от f и g определяется .

Другими словами, - просто конкатенация двух функций , состоящая из экземпляров с таким же g-ключом и независимых f-ключей.

Напомним, что наша конструкция MD[F,G] принимает как параметры ключевые сжатия функций и . Рассмотрим свободное от перекрытий семейство функций и семейство функций , примем , и введем:

(1)

(2)

для всех . Спецификация нашей конструкции, таким образом, в настоящее время сводится к определению свободного от перекрытий семейства функций . Отметим, что -бит до -бит семейство функций является параметром схемы (не основанной на низкоуровневых примитивах), тогда как должно быть получено из , и его "cover-free" безопасность сводится к mac безопасности от ; см. в следующем разделе детали построения конструкции .

Напомним, что по Лемме 1 мы заинтересованы в ограничении и с точки зрения . Для достижения этой цели, мы применим две леммы, что верхняя граница и как функция от и . Доказательства обоих лемм даны в полной версии [28].

Лемма 2. Пусть . Тогда .

Лемма 3. Пусть . Тогда .

(Заметим, что, в отличии от Лемм 1 и 2, доказательство Леммы 3 не тривиально. В частности, оно требует анализа "balls-and-bins" игры того типа, который использовался в [7].) Объединяя Леммы 1, 2 и 3, получаем:

Лемма 4. Пусть и пусть F,G будут как в (1) и (2). Тогда, если :

.

Лемма 4 уменьшает сокращает создания "cover-free" семейства функций по сравнению с семейством функций так, что может быть ограничена с точки зрения . Это тема следующего раздела и главное техническое достижение статьи.

Когда имитовставка построена из более маленьких примитивов, где ключ функции состоит из конечного набора ключей для меньших примитивных (который потенциально вызван несколько раз с различными ключами), понятия MAC, WCR и "cover-free" безопасности обычно распространяются на очевидные модели, где противник получает полную транскрипцию функционального расчета на каждый запрос, вплоть до обращения к примитивным (а именно, вызовы примитивов более низкого уровня оказываются такими же, как вызовы оракула в транскрипции, чтобы не раскрыть примитивные ключи). На деле, все результаты и доказательства этой статьи могут быть (легко) интерпретированы и справедливы в этой сложной «очевидной» модели. Однако, чтобы сделать восприятие более простым, мы в дальнейшем не будем упоминать об этом.

Построение семейства свободных от перекрытий функций от MAC

Этот раздел содержит наш основной результат, а именно, конструкцию семейства свободных от перекрытия функций основанных на n до n битных примитивах, которая достигает безопасности за пределами рождения, предполагая только хорошую MAC безопасность, состоящую из примитивов. В ходе статьи мы отметили, что незашифрованная функция не может быть свободной от перекрытий против информационно-теоретических противников пока или же пока t настолько большой, как желаемый уровень безопасности, который дает значения t слишком большие, чтобы быть практичным в большинстве настройках.

Наша конструкция использует понятие семейства вводо-ограниченных функций (IREF), введенных Маурэром и Тэссаро. Следующее определение слегка модифицировано под наши нужды.

Определение 1. Пусть и пусть - IRFF есть множество функций таких, что и для всех и всех , (ii) для всех существует такое, что , и (iii) для всех подмножеств таких, что мы имеем

.

Конструкции семейства вводо-ограниченных функций обсуждались в Разделе [19].


Рис. 3. Иллюстрация свободных от перекрытий функции для параметров : r = 2, t = 3. Дополнительные пути не показаны на диаграмме, вход каждого по i-ым наборам копии p. 


Наше семейство свободных от перекрытия функций также взято из [24]. Конструкция принимает в качестве параметров , и целые числа и -IRFF есть примитив вида n до n бит (в дальнейшем будет использоваться как член семейства функций следующего вида , возможно фиксированный ключ блока шифров). Конструкция также использует (конкретную, незашифрованную) функцию , описанную ниже. Пусть объявлена как:

,

где

для (См. рис. 3). Для мы получили семейство имитовставок вида путем создания экземпляра с членом семейства функций ; однако, мы выбрали незашифрованное обозначение (в котором неявно зашифрованы), когда возможно сократить накладные расходы.

Для функции есть полином:

(3)

где есть -битные строки, рассматриваемые как элементы поля . Важнейшими свойствами являются:

I. Обратимость. Для любых и любых значений , таких, что не равны 0, есть несколько значений , таких, что , и эти значения эффективно пронумерованы.

II. Коллизия обратимости. Для любых и для любых значений , таких, что не равно , существует несколько значений , такие, что

,

и эти значения рационально счетные.

Оба свойства легко доказать, если исходить из того факта, что является многочленом типа , где с не зависит от . Майер и Тессаро используют конструкцию, отличную от , которая не обязательно удовлетворяет вышеуказанным свойствам, требующим увеличения набора функций до набора , где v колеблется от 1 до [m/n + 1].

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

TemplateTheoremIcon.svg Теорема Теорема 2
Пусть будет – IRFF, пусть будет семейством функций, и рассмотрим в качестве ключевого семейства функций пространства путем установки для любых . Тогда

(4)

для любых , где и

где – время, необходимое для поиска всех корней многочлена степени r на поле размером . При и имеем

Доказательство
Пусть - противник для игры , которая запущена во время Т и имеет вероятность успеха . Этого достаточно, чтобы спроектировать противника B для игры с преимуществом по крайней мере

что это выполняется за время .


B имеет доступ к случайному члену f функции. выбирает случайные ключи и случайный индекс . Далее симулирует с оракулом , подтверждая функцию с не равным если и подтверждая c , используя его оракул. Кроме того, В «забывает» значение , обрабатывает каждую из функций , как оракул и пытается подделать любой из них, совершая лишь одну такую поддельную попытку во время игры. Так как имеет шанс подделывания, равный 1/t, если делает правильную подделку, этого достаточно для для выполнения подделки с минимальный шансом, равным

для того, чтобы подделать с минимальным шансом Проще рассмотреть измененную версию , которую мы назовем просто А, которая непосредственно выпускает F- запросы; точнее, А выпускает последовательность запросов , где и каждый ; В отвечает на запрос с кортежем . Мы можем предположить, что А никогда не делает один и тот же запрос дважды. Пусть для . Отметим, что

которое ограничивает ввод свойством . Также пусть для и поместим для любых (которые В может подсчитывать после его ответов А на i-ый запрос пока ). Мы говорим А «победил в большой игре без прикрытия» в i- ый запрос, если существует для , такой как для . Очевидно, что существует А такой же продолжительности как A', чье преимущество в основной игре по крайней мере также велико, как , в то время как А может просто симулировать A' и задавать различные F- запросы, необходимые для подсчета ответов на запросы A'; по определению, А побеждает, если A' выигрывает . (Легко проверить, что если A' делает запросы , такие как , тогда А побеждает в главной игре без прикрытия к тому времени, как закончит выдавать запросы, необходимые для подсчета ответов к запросу от A'). Таким образом, достаточно подделать В одной из F- функций с вероятностью как минимум . Теперь мы рассматриваем В как простой ответ на F- запросы А (в противоположность вычислительным ответам к - запросам), хотя в действительности B выполняет полное вычисление, включая моделирование A' из А.

Мы рассматриваем каждое значение как "лунку" с t – "слотами" ; l-ый слот лунки s "получает шар" или "наполняется" в запросе (а именно, если лунка уже существует в данной точке), если , или если . Как только лунка получает шар в слот, слот становится полным. Слот не может получить более одного шара и лунки никогда не удаляются; мы отмечаем, что никаких лотков не существует при старте, и что лотки создаются по i-ому запросу. Согласно этим определениям, А точно выигрывает "интенсивную" игру без прикрытия в случае, если какая-либо лунка наполняется (то есть все ее слоты становятся полными). Полезно изобразить А и В играющими в состязательную игру, в которой А побеждает, если заполняет лунку, а В не подделывает одну из функций , и где В побеждает иным способом (фактически, мы можем изобразить А выбирающим ответы к запросам, в то время как В наблюдает и пытается угадать ответ до разоблачения). Мы говорим, что шар l лунки "ранний", если и «поздний» в противоположном случае; таким образом шар – ранний, только лишь если он добавлен в лунку с тем же А–запросом, который создал лоток. B запускает одну из двух различных стратегий подделывания с равной вероятностью. Первая стратегия создана для того, чтобы предотвратить появление слишком большого количества ранних шаров в лунке, в то время как вторая – для предотвращения А от заполнения лунок(вторая стратегия хороша лишь в том случае, если не слишком много ранних шаров появляются в лунках, откуда появляется потребность в первой стратегии ). Мы называем эти две стратегии "раннее предотвращение" и "позднее предотвращение"; несмотря на эти названия, мы подчеркиваем, что эти две стратегии не запускаются последовательно; напротив, В сначала кидает монетку, чтобы решить, какую стратегию использовать.

Начнем с описания ранней стратегии В. Пусть как замечено выше, , так что Q – верхняя граница общего числа лунок, созданных во время игры. Цель ранней стратегии В заключается в том, чтобы препятствовать А в создании, для каждых или большего количества лотков , каждый из которых имеет k или более ранних шары. Иными словами, мы лишь требуем выполнения стратегии (то есть подделывание функции с "достаточно высокой" вероятностью), если имеется некоторое , такое как или большее количество лотков созданы с k или большим количеством ранних шаров внутри. Мы моделируем раннюю стратегию предотвращения через немного упрощенную игру шаров в лунках, описанную ниже. Чтобы соединить эту игру с "настоящей" игрой между А и В, полезно сначала рассмотреть процесс посредством которого создаются лунки, а ранние шары добавляются к ним. Рассмотрим запрос , сделанный А. Тогда

и элементы - это новые лунки, созданные этим запросом. Каждая лунка имеет t слотов и "значение" l-ого слота s показывается, когда В делает запрос  ; после того, как значение раскрыто, ранний шар добавляется в l-ый слот s согласно тому, существует ли там такой, что , или нет (заметим, что в этой точке известен для всех ). Таким образом, процесс заполнения недавно созданных лунок с ранними шарами состоят из t "фаз" (запросы , которые В последовательно создает), где l- ая фаза одновременно показывает свойства l-ых слотов всех новых лунок, и получают ли эти слоты ранние шары или нет. Следующая игра шаров в лунках таким образом резюмирует процесс создания новых лотков и ранних шаров.

‘Раннее предотвращение’ Игра шаров-и-лунок. Эта игра проходит между двумя противниками и . Параметрами являются целые числа . Правила следующие : - Игра продолжается раундов. Во время раунда называется некое число лунок, что . - В начале каждого раунда лунки пусты. У каждой лунки есть t слотов. Каждый раунд состоит из t фаз. Во время l- ой фазы открывает, в каких из лунок есть l-ые слоты "занятые мячом". - Перед каждой фазой каждого раунда позволяют тайно предсказать лоток, который получит шар на этой фазе; выигрывает, если угадывает правильно, но угадывать разрешается лишь раз за всю игру. - Пусть будет числом лунок, получивших k или более мячей в раунде i, и пусть , где сумма подсчитывается за все раунды. Тогда должен заполнить такие лунки, что для как минимум одного значения

В полной версии мы показываем стратегию для , которая дает как минимум шансов победить в игре, вне зависимости от стратегии . Таким образом, если или более лунок получают k или более ранних шаров для некоторого , и если В использует эту стратегию, то у В есть шанс правильного предугадывания, прежде чем ответ на какой –либо запрос дан, что значение, возвращенное этим запросом, приведет к слоту l некоторых (определенных) лунок , получая ранний шар. Чтобы угадать , В продолжает выбирать случайные , и решать , чтобы угадать (так как s получат ранний шар в слот l точно тогда, когда существует такой, что )

Для того чтобы увидеть, что действительно "разрешима", два разных обстоятельства должны быть приняты во внимание, согласно тому, справедливо ли или нет. Если , тогда был создан более ранним запросом А и значения его слотов известны, в особенности значение l-ого слота. Пусть , пусть будет единственным индексом, таким, что и пусть . Тогда все значения известны B, кроме значения , которое необходимо угадать, используя уравнение:

(5)

По условию (i) Определения , что из-за свойства "инертности" p есть несколько значений , которые находят решение (5). Более точно, потому что является отличным от нуля многочленом r в , В должен выбрать из r корней , где просто константа. Во втором случае, и не известны (также как только вычисляется). Пусть , пусть будет уникальным индексом, таким, что и пусть для Тогда все значения известны В, за исключением и В необходимо найти решение

(6)

(это - ) для (или как минимум для ). Но  ; так как  ; также, из-за приемистости следует значение "Столкновения обратимости" p такое, что есть несколько значений , являющихся решением (6); фактически, эти самые r - различные корни , считающиеся многочленом в . Термин в Теореме 2 содержит стоимости поиска корня для В , которые встречаются в вычислениях всего один раз. Естественно, дальнейшее предположение В об и правильном корне разрушает вероятность создания правильной подделки, даже если правильно предположено, что ранний шар будет добавлен в слоту лунки. Но исправить это расхождение легко: у B есть шанс по крайней мере правильного предположения s' и шанс по крайней мере 1/r правильного угадывания корня. Таким образом, если или больше лунок каждый получат k или более ранних шаров для некоторых , и если В использует стратегию "раннего предотвращения" (которую мы только что описали), тогда у В есть шанс подделки

как минимум . Так как В использует эту стратегию с вероятностью 1\2, можем предположить, что меньше, чем лунок получают k ранних шаров для каждого , или, иначе, B достигает необходимой вероятности успеха . Теперь обсудим стратегию "позднего предотвращения" для B. Здесь B пытается предотвратить от A от заполнения лунки с t шарами, предполагая появление поздних шаров. Заметим, что если запрос приведет к тому, что какой – нибудь поздний шар будет помещен в l-ый слот лунки s, тогда и значения будут уже известны до ответа на запрос Более того, факт того, что запрос привел к появлению позднего шара в лунке s, означат, что есть некий такой, что для неких запросы уже были сделаны для , и (значение станет известным, когда будет отвечен). Пусть и , все из которых известны В, кроме . Тогда, если В правильно угадал поздний шар, он появится в l-ом слоте лунки s и он также правильно угадал значение , и можно предсказать , решив

(7)

для , для которых есть максимум r решений. (Это второй, и последнее раз, когда мы требуем "обратимости" свойств p). Исходя из этих вычислений, эта игра шаров-и-лунок моделирует задание "позднего предотвращения" B, но не включает угадывание корня для (7):

‘Позднее предотвращение’ игра шаров-и-лунок. Эта игра проходит между двумя противниками и . Параметры – целые числа . Правила следующие: - Игра затрагивает "лунки" со слотами t в каждой, где каждый слот может как содержать шар, так и нет. В начале игры лунок нет. Лунки добавляются в игру так, как описано ниже, и никогда не удаляются. - Игра делится на раундов, каждая их которых состоит из t «фаз». - В начале раунда i называет некоторое число такое, что . Если , то этап пропускается. - Во время фазы l раунда выбирает подмножество (возможно пустое) из уже существующих лунок, в чьем l-ом слоте еще нет шара, и одновременно помещает шары во все его l-ые слоты. Кроме того, помечает каждый помещенный шар номером от 1 до . (Допускается существование множества шаров с одним именем и не все пометки должны обязательно существовать). - В конце раунда i вводит новых лунок в игру, по возможности уже имеющих шары. На всем протяжении игры общее число новых лунок, введенных с k или более шарами, должно быть меньше для всех . - До каждой фазы каждого раунда позволяется тайно угадать лунку, который во время этой фазы получит шар и метку для этого шара; побеждает в случае, если угадывает и то, и другое. За всю игру разрешается угадывать лишь один раз. - должен к концу игру заполнить некоторые лотки t шарами. Заметим, что все новые лунки, введенные в конце этапа i, соответствуют всем элементам , и что соответствует . "Метка" для шара, помещенного в лунку s, в фазе l соответствует элементу такому, что , обсужденному выше. (В "настоящей игре" между А и В могут существовать несколько элементов , таких, что более точная модель позволит выбрать непустой список меток – больше одной метки для каждого шара; таким образом, пытаясь минимизировать преимущество угадывания , будет автоматически делать каждый из этих списков единичным ).

В полной версии мы представляем стратегию для о "позднем предотвращении", которая будет удачной с вероятностью , невзирая на стратегию . Стратегия "позднего предотвращения" В состоит лишь из соединения стратегии с угадыванием корня (7). Таким образом, пока меньше, чем лунок получают k или более ранних шаров для , пока А заполняет некоторые лунки t шарами и пока В использует свои стратегию "позднего предотвращения", В имеет шанс подделывания как минимум

Если В использует стратегию "позднего предотвращения", то это на 1\2 дает гарантию успеха.

Выводы

Подставляя в Лемму 4 посредством нашей неприкрытой функции и используя Теорему 2 при m = 3n , получаем :

TemplateTheoremIcon.svg Теорема Теорема 3
Пусть будет , пусть , и рассмотрим в качестве семейства имитовставок пространства , как в Теореме 2. Определим посредством (1), (2) с . Тогда:

(8)

где и , пока и где

В частности, когда и (то есть ) и , имеем

(9)

Доказательство
Без доказательства.


По умолчанию мы должны применить вторую часть Теоремы 3, где t=n. В порядке интерпретации (9) мы должны знать, какие значения и K достижимы через IRFF и знать для этих IRFF, так как это определяет . Вопрос реализации IRFF уже изучался Майером и Тессаро, они сузили его до конструкции определенных типов крайне несбалансированных двудольных экспандеров. Хотя они тщательно изучались, до сих пор эти типы экспандеров еще не поняты до конца, и, в частности, установка относящихся к нашему случаю параметров не была объектом усиленного внимания. Мы затронули границы, достигнутые двумя явными конструкциями, так же как и достигнутые неявными, вероятностными конструкциями. Во всех случаях мы устанавливаем . Заметим, что может быть всегда ограничена сверху путем присоединения трех функций к IRFF, который прочитывает каждый блок входных данных через их тождество. Более того, мы легко можем усилять состояние (i) Определения 1, пока . Так как размеры семейств под вопросом и в любом случае являются многочленами n, мы подводим итог, не обращая на них дальнейшего внимания.

Экзистенциальные конструкции. Возможная конструкция [24] достигает с и . В этом случае . Тогда правая сторона (9) становится равной

.

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

Расширение [29]. Экспандеры Та-Шимы, Уманса и Цукермана дают ясную с и . В этом случае . Правая сторона (9) становится равной

.

Предполагая, что , мы можем достичь безопасности запроса до (Заметим, что эта конструкция со всех точек зрения лучше, чем предложенная Майером и Тессаро). Расширители [30].

Экспандеры Гурусвами, Уманса и Венкатесана дают ясную с и для любых (0,1). В этом случае . Мы можем задать . Для константы правая сторона (9) опять становится равной

.

Полагая , небезопасность, таким образом, незначительна, пока . Преимущество этой конструкции заключается в том, что она позволяет рационально инвертировать время (в противоположность для предыдущих конструкций ) . Объяснение. Предположение действительно лишь, пока не позволяет совершать исчерпывающий поиск ключевого пространства ; предположим, что что последние две конструкции имеют размер , это подразумевает, что наши верхние границы имеют смысл лишь, если