Краткие рандомизированные кодировки

From CryptoWiki
Jump to: navigation, search

Contents

Постановка задачи защиты информации

Понятие Рандомизированные Кодировки было введено сотрудниками департамента компьютерных наук Израильского Института Технологий «Technion» Ювалем Ишаем и Эялем Кашилевитцом [IK00]. Рандомизированные Кодировки позволяют представить сложную (комплексную) функцию f(x) с помощью некоторого отображения f^(x), получающего на выходе закодированное значение x функцией f(x). Основная проблема заключается в том, как осуществить отображение сложных функций f(x) в более простые функции отображения f^(x). Юваль Ишай и Эяль Кашилевитц выделили три вида эффективных Рандомизированных Кодировок , полученных из функции:

  • Краткие Рандомизированные Кодировки (Succinct Randomized Encodings).
  • Компактные Рандомизированные Кодировки (Compact Randomized Encodings).
  • Сублинейные Рандомизированные Кодировки (Sublinear Randomized Encodings).

При работе с Краткими Рандомизированными Кодировками основной целью является определение времени, требуемого для вычисления значений функцией отображения f^(x) [BGL+15]. Краткие Рандомизированные Кодировки являются работой следующих исследователей:

  • Нир Битанский (Массачусетский Институт Технологий);
  • Саньям Гарг (Калифорнийский университет, Беркли);
  • Худжая Лин (Калифорнийский университет, Санта Барбара);
  • Рафаэль Пасс (Корнеллский Университет);
  • Сидхарт Теланг (Корнеллский Университет).

Теоретические основы решения задачи

Вычисляются:

  • время T^, затраченное на вычисление функцией отображения f^(x);
  • время T, требуемое для вычисления функциейf(x).

Время T^, затрачиваемое на вычисление функцией отображения, значительно меньше, чем время T. Для отображения в функцию f^(x) применяется специальная программа П в виде:

Время T^ зависит от сложности функции отображения, размеров входных и выходных данных. Схема работы обеспечивает вычислительную конфиденциальность программы П и основывается на «обфускации неразличимости» (indistinguishability obfuscation или iO) для относительно простого контура, созданного через реализации, основанные на полиномиальных и мультилинейных отображениях.[BV15a]
Применяются Краткие Рандомизированные Кодировки в работе важных приложений, таких как:

  • «Краткие неразличимые обфускаторы», где программа обфускатора iO(П) вычисляет ту же функцию П с аргументом x изначально ограниченного размера. Обфускация П работает примерно также быстро, как и кодирование вычислений программы П при любых входящих значениях x. При этом исследователи применяют субэкспоненциальную обфускацию защиты для контуров.
  • «Краткое функциональное шифрование», где применяется ключ из программы П, позволяющий расшифровать при помощи функции П(x) шифровки любого открытого текста x изначально ограниченного размера. Формирование ключа происходит также быстро, как и процесс кодирования.
  • «Краткое многоразовое искажение», устойчивая форма Рандомизированных Кодировок, где любые входящие значения x могут быть закодированы отдельно от программы П, независимо от времени выполнения и сложности программы П.
  • «Делегат открытой проверки двойных сообщений», когда проверка результата долгих вычислений, осуществляемых программой П от аргумента x происходит также быстро, как и процесс кодирования. Благодаря Кратким Рандомизированным Кодировкам показывается, как можно схему работы с любыми двойными сообщениями преобразовать в более простую не интерактивную систему, где можно повторно использовать сообщения.

Главным методом алгоритма является общий метод сжатия фрагментарных искаженных вычислений, не раскрывая никакой информации о внутренних случайных процессах, применяемых для искажения данных. Краткие Рандомизированные Кодировки имеют важные отличия от базовых Рандомизированных Кодировок. Эти отличия называются «краткими» свойствами, они приведены ниже:

  • Устранение зависимости от вычислений функции отображения на каждом шаге. Когда функция f^(x) уже задана программой П, происходит отображение функции кодированияf^(x). В Рандомизированных Кодировках функция отображения вычисляется на каждом шаге и в результате вычислений увеличиваются выходные данные. В Кратких Рандомизированных Кодировках функция отображения вычисляется только на первом шаге, таким образом зависимость от постоянного вычисления функция отображений в данном случае устранена. Это в свою очередь придает гибкости в вычислениях.
  • Гибкие вычисления. Алгоритм Кратких Рандомизированых Кодировок позволяет уменьшит нагрузку при больших размерах схемы работы, требующей много ресурсов. Дополнительно Краткие Рандомизированые Кодировки позволяют уменьшить рабочую нагрузку на стороне декодера за счет устранения лишних вызовов для получения результирующей информации.
  • Оптимизация времени декодирования. В идеале декодирование должно занимать как можно меньше времени, а время декодирования должно быть как можно ближе к времени расчета по функции. Краткие Рандомизированные Кодировки позволяются оптимизировать время декодирования.


Основные криптографические конструкции и их стойкость

Краткие Рандомизированные Кодировки применяются для различных моделей вычислений. В общем виде схема работы всех моделей вычислений Кратких Рандомизированных Кодировок выглядит следубщим образом:

  • Генерация функции отображения. Данный этап обозначается как Garb.
  • Шифрование данных на каждом этапе. Данный этап обозначается как Encode.
  • Оценка времени расшифровки. Данный жтап обозначается как Eval.

Различные модели вычислений:

  • Классы случайных алгоритмов. Формально, производительность алгоритма есть случайная величина, определяемая случайными битами. Таким образом, либо время работы, либо выходные данные (либо и то, и другое) являются случайными величинами. Краткие Рандомизированные Кодировки определяют классы для своих соответствующих рандомизированных алгоритмов аналогично процессу создания классов в случайных алгоритмах.
  • Классы (произвольных) полиномиально-размерных алгоритмов. Краткие Рандомизированные Кодировки определяют для своих произвольных полиномиально-размерных классов аналогично процессу создания классов в полиномиально-арзмерных алгоритмах.
  • Классы четко структурированных алгоритмов. Для того чтобы избежать повторения определения для различных классов машин, в Кратких Рандомизированных Кодировках есть возможность применения общих классов алгоритмов, которые могут быть созданы с классами, описывающих различные специфические объекты. Например, Краткие Рандомизированные Кодировки работают с классами алгоритмов, которые являются четко структурированными.

Практические применения криптографических конструкций, особенности их реализации

Применение Кратких Рандомизированных Кодировок в большинстве случаев позволяет экономить ресурсы во время коммуникаций и вычислений. Одно из таких применений можно увидеть в работе с протоколом конфиденциального вычисления (MPC). Приложения, работающие на основании протокола MPC, используют подобную схему работы, когда применяется известная всем участникам конфиденциальных вычислений функция от значения x. Когда функция f(x) уже задана программой П, происходит первое отображение Краткой Рандомизированной Кодировки f^(x). Далее при следующих вычислениях отображение не вычисляется, а декодирование осуществляется в самом конце, тогда можно наблюдать заметное уменьшение накладных расходов, пропорциональных размеру контура, применяемого при вычислении f^(x).

С практической точки зрения применение Рандомизированных Кодировок в сложных вычислениях функций П вряд ли будет слишком быстрым и эффективным, например, при фиксированном полиномиальном времени. Применение «Краткой неразличимой обфускации» (iO) для любых моделей вычислений (например, обфускаторы в Машинах Тьюринга) непосредственно подразумевает наличие Кратких Рандомизированных Кодировок. Конструкции обфускации iO и прямые конструкции Кратких Рандомизированных Кодировок основаны на следующих вычислительных процедурах:

  • «Извлекаемый свидетель шифрования» (Extractable witness encryption). [GGSW13]
  • «Краткие не интерактивные аргументы» (Succinct non-interactive arguments). [GW11]
  • «Обфускация с различными входными данными» (Differing-inputs obfuscation). [ABG+13]

Демонстрация возможностей Кратких Рандомизированных Кодировок можно посмотреть в работе следующих приложений:

  • Приложение 1: Краткие неразличимые обфускаторы. Краткие обфускаторы ion применяются при ограниченных возможностях вычислений. Неразличимость здесь означает, что краткие обфускации двух программ, имеющих одинаковые значения результатов на выходе и времени при всех входных значениях аргумента x некоторого изначально ограниченного размера n являются вычислительно неотличимыми. Конструкция базируется на субэкспоненциальной iO, в то время как любая форма кратной iO реализуется через [ABG+13] различающиеся входные обфускации в конъюнкции с краткими не интерактивными аргументами (которые уже влекут за собой сильные «краткие» свойства).
  • Приложение 2: Краткое функциональное шифрование и многоразовое искажение. Недавний скачок в изучении обфускации привел к тому, что наблюдается продвижение в исследованиях функционального шифрования. В настоящее время функциональное шифрование, основанное на методиках неразличимости обфускации, для всех схем может быть создано из iO. Для моделей вычислений с краткими представлениями, работающими с Краткими Рандомизированными Кодировками, имеющих секретный ключ skП, позволяющий расшифровать П(х) из кодированных значений х, время вычислений оказывается значительно быстрее, чем время, требуемое для работы программы П(х). Однако, здесь достижение аналогично кратким обфускациям iO, требуются по факту те же самые не фальсифицированные предположения или допущения. Базируется на создании не кратко функциональных схем шифрования, показывающих что Краткие Рандомизированные Кодировки могут быть сконструированы без ориентации на субэкспоненциальные жесткие переменные.
  • Приложение 3: Открытое подвергающееся проверке делегирование и краткие NIZKs. Краткие Рандомизированные Кодировки непосредственно подразумевают схему делегирования одного круга для вычисления полиномиального времени, осложняющегося ограниченным пространством. Главной особенностью схемы является её открытость и доступность для проверки, это означает, что сообщениями процедуры верификатора можно проверить информацию, не запрашивая какой-либо секретной проверки. Все предыдущие открытые подвергающие проверке данных схемы полагались на разного рода предположения или доказывались только для случайных oracle. Ещё одной характерной особенностью данной схемы является то, что она гарантирует конфиденциальность ввода для верификатора. Схема делегирования базируется только на Рандомизированных Кодировках (и одно-направленных функций), и, таким образом, может быть основана только на полиномиальных предположениях.
  • Другие приложения. Авторы Кратких Рандомизированных Кодировок пересмотрели предыдущие приложения (не Кратких) Рандомизированных Кодировок и отмечают полученные «кратные» функции.

Глоссарий

Библиографический указатель

Перейти к Списоку литературы

назад на Главную страницу

назад к Оглавлению



Мальцева Н. А.

2016

Назад