id: Гость   вход   регистрация
текущее время 14:31 28/03/2024
Владелец: unknown (создано 10/07/2013 15:49), редакция от 10/07/2013 15:49 (автор: unknown) Печать
Категории: криптография, алгоритмы, протоколы
http://www.pgpru.com/Новости/2013/УниверсальныйВычислительныйЭкстракторКакКонкретизацияСлучайногоОракула
создать
просмотр
редакции
ссылки

10.07 // Универсальный вычислительный экстрактор как конкретизация случайного оракула


В 1993 году Беллэйр и Роговэй предложили парадигму случайного оракула (RO). RO — это гипотетическая функция, которая выдаёт истинно случайный ответ на любой запрос и запоминает его. При повторении ранее поступавшего запроса RO извлекает предыдущий сгенерированный ответ из памяти. В реальности, никакая функция не может выполнить роль RO, т.к. внутреннее состояние такой функции и требуемые затраты памяти должны быть бесконечными.


Общий способ конструирования протоколов в модели RO (ROM) состоит из двух шагов:


  1. Спроектировать схему, доказать её безопасность в ROM при условии, что алгоритм схемы и противник имеют доступ к RO. Иначе говоря, противник всегда имеет доступ к схеме, но она может получать на вход значения как от него, так и от RO.
  2. Определить, что будет конкретно использоваться в качестве RO, чтобы получить схему в стандартной модели, которая и будет выполнена и применена.

Определение предполагается производить через семейство функций H за счёт замены вызова RO в ROM-схеме через определение детерминированной функции H.Ev(hk, ·), определяемой ключом hk←$H.Kg(1λ), где λ — параметр безопасности. Ключ hk может быть помещён в открытый ключ или ключ, определяемый схемой. В 1993 году Беллэйр и Роговэй указали, что если H "будет вести себя как RO", то полученная схема будет безопасной в стандартной модели. Также они указали на то, что конкретизация H может быть выполнена эвристически посредством криптографических хэш-функций. Последовавшим фундаментальным опасением стала недостаточность доказательства безопасности определяемой схемы. Канетти, Голдрайх и Халеви показали в 1998 году, что такая недостаточность может привести к созданию некоторых схем, безопасных в ROM, но в которых RO нельзя заменить никаким семейством функций безопасным способом. Контраргументы сторонников ROM свелись к тому, что такие примеры слишком надуманны и "естественные" ROM-схемы остались невзломанными. После этого были попытки создания менее искуственных схем, выявляющих неполноту ROM-доказательств.


Ключевой проблемой в слабости доказательств конкретизированных схем стало ещё более фундаментальное последствие, заключающееся в отсутствии определения того, что собственно значит для семейства функций, что "они ведут себя как RO", что могло бы послужить принятию функции как допущения на котором строились бы доказательства. Определение псевдослучайнй функции (PRF), которое хорошо работало в симметричных схемах, становится неадекватным, поскольку PRF-безопасность опирается на незнание противником ключа. Коллизионная стойкость (Collision-resistance — CR) крайне недостаточна для любого нетривиального использвания RO.


Попытки заменить RO т.н. совершенными однонаправлеными вероятностными хэш-функциями (Perfectly One-Way Probabilistic Hash Functions — POWHFs), т.н. неповреждаемыми (non-malleable) хэш-функциями показали ограниченную применимость. И даже попытка использования дополнения в схеме RSA (RSA-OAEP) считается малоуспешной с т.з. полноты доказательства стойкости.


Исследователи Mihir Bellare, Viet Tung Hoang и Sriram Keelveedhi с кафедры компьютерных наук и инженерных разработок Калифорнийского университета Сан-Диего и Дэвис предложили новый подход в преодолении ограничений, связанных с трудностями конкретизации случайного оракула при его выполнении на основе реальных функций. Для определения безопасности хэш-функций (в т.ч., использующих ключ), они предложили использовать определение в модели UCE — универсального вычислительного экстрактора. Краткое неформальное определение UCE-безопасности звучит достаточно просто: запросы к функции должны давать на выходе ответ, неотличимый от случайного, с допуском на некоторую утечку, даже если противник знает ключ, до тех пор, пока эта утечка не позволяет вычислить вход. По мнению авторов, такой подход способен заменить эвристистически доказуемый подход на основе ROM на доказываемый (доказанный, доказательный) в рамках UCE.


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


Интересной перспективой является унификация разных схем, за счёт более полного понимания, какие именно качества RO им требуются. Ещё более интересным является применимость UCE в доказательствах, не требующих RO ("криптография без случайного оракула") и возможность сводимости некоторых RO-схем к схемам без RO, но на основе UCE. Т.о., некоторые разновидности UCE, по мнению авторов, могут служить заменой RO.


Понятие "вычислительного экстрактора" использовалось для примитивов, которые могут извлекать псевдослучайные данные из распределений, имеющих значение вычислительной минимальной энтропии. UCE-безопасные семейства вместо этого могут извлекать случайность из непредсказуемых распределений. В них может быть или не быть минимальной вычислительной энтропии в формально определяемом смысле, но непредсказуемость используется как смягчение требований, что отражено в его названии. "Универсальный" — означает возможность производить действия начиная с любого (непредсказуемого) распределения.


Определение UCE включает противника S, также называемого источником (Source), которому предосталяется оракул Hash, который как и ранее являлся H.Ev(hk, ·), для ключа hk←$H.Kg(1λ) при условии, что бит запроса b равен 1, или RO в противоположном случае. Если не требовать вычисления b для S, то если отрицать его hk, мы снова окажемся в PRF и если дать ему hk, то безопасность будет недостижима. Поэтому, от S не требуется попытка определить b. Вместо этого, он должен предоставить противнику-сообщнику D, которого называют различитель (Distinguisher), некоторую информацию L, которую называют утечкой (Leakage). Различитель при получении ключа hk должен определить b.


Ясно, что безопасность недостижима для произвольного типа утечек. Так, например, источник может включить в L точку x и результат y = Hash(x) от своего оракула на x, и D на основе знания hk может протестировать, верно ли выражение y = H.Ev(hk, x). Для этого на источник накладывается дополнительное ограничение, называемое непредсказуемостью. Это значит, что прогнозирующий противник P (Predictor), на основании утечки, полученной от источника в случайной (b = 0) игре не имеет вычислительных возможностей найти любой из входов, которые поступали в качестве запросов от источника оракулу. Важно, что непредсказуемость является свойством источника, а не семейства функций H.


Наконец, в требования безопасности включается, что для каждого непредсказуемого источника S и каждого различителя D, преимущество S, D в определении b незначительно. Формальное определение такого требования дано в работе как UCE1. Вариант UCE2 заменяет требование непредсказуемости требованием "reset-security", в итоге, более слабое требование приводит к созданию более стойкой функции: UCE2-безопасность всегда включает в себя и UCE1-безопасность. Как UCE1, так и UCE2 включают в себя единственный ключ хэширования. Многоключевые варианты описаны как mUCE1 и mUCE2 соответственно. В рассматриваеомй работе можно более подробно ознакомиться с определениями UCE-функций, алгоритмами, диаграммами соотношений и рассуждениями о возможности построения дополнительных классов UCE. Интересно, что UCE1 не включает в себя PRF, а UCE2 не включает CR. Вопрос о включении PRF в UCE2 остаётся открытым. Это позволяет строить тонкие доказательства стойкости протоколов, в которых не требуются все свойства случайного оракула: некоторые схемы могут оставаться стойкими и без коллизионной стойкости или без псевдослучайности (например, при внешней рэндомизации).


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


  1. Детерминированное шифрование с открытым ключом (Deterministic PKE). В D-PKE ROM-схеме сообщение m шифруется открытым ключом ek обработкой случайного оракула ekm для получения результата броска монеты r и последующего шифрования m в схеме IND-CPA PKE (шифрование с открытым ключом, стойкое к неразличимости на подобранных шифртекстах). Использование определения для добавления к открытому ключу hk←$H.Kg(1λ) и замены RO на H.Ev(hk, ·), позволило улучшить доказательство, впервые достигнув положительных результатов по некоторым критериям в стандартной модели и повысить практичность.
  2. Шифрование с локингом сообщений (MLE). В конвергентном шифровании (CE), сообщение m шифруется детерминированным симметричным шифрованием за счёт ключа, который выводится из самого сообщения посредством RO. Эти схемы используются коммерческими провайдерами облачных хранилищ данных для экономии места. Авторам удалось применить в этой схеме UCE1 и доказать требуемые свойства в стандартной модели.
  3. Hardcore функции. Hardcore-функция HC(f) для односторонней функции f извлекает x битов таким образом, что они остаются неотличимыми от случайных даже при знании f(x). RO является идеальной HC-функцией, т.к. RO(x) может вернуть любое число псевдослучайных битов при наличии f(x), если f — односторонняя. Семейство UCE1 может безопасно заменять RO, наподобие того, как безопасные hardcore-функции для любых односторонних функций могут извлекать сколько угодно битов.
  4. Шифрование с открытым ключом BR93 PKE. Простая и естественная схема шифрования ROM IND-CPA PKE шифрует сообщение m путём выбора случайного x и получения (f(x), RO(x) ⊕ m), где f — односторонняя функция с секретом для открытого ключа. Авторами показано, что замена RO на UCE1 сохраняет IND-CPA безопасность.
  5. Маскировка точечных функций. Точечная функция имеет непустой выход только в одной точке. Вместо ранее предлагавшихся ROM обфускаций точечных функций, авторы предложили конструкцию в стандартной модели за счёт использования mUCE1.
  6. Безопасное симметричное шифрование с ключом, зависящим от сообщения (KDM SE). Простая и эффективная схема ROM KDM SE осуществляла шифрование сообщения m на ключе K, выборе случайного r и получении (r, RO(rK)⊕m). Если случайное значение r в этой схеме играет роль нового хэшированного ключа, то для шифрования m логично применить hk←$H.Kg(1λ) и получить (hk, H.Ev(hk, K)⊕m). Авторы показывают, что если H является mUCE1-безопасной, то такая схема KDM-безопасна в стандартной модели. При этом достигается неадаптивная KDM-безопасность. Такая схема является более практичной, чем другие KDM-схемы, безопасные в стандартной модели.
  7. Симметричное шифрование, устойчивое к атакам со связанными ключами (RKA-secure SE). Схемы симметричного шифрования, стойкие против атак со связанными ключами, должны сохранять безопасность даже если шифрование проводится посредством ключей, выводимых из оригинального ключа за счёт применения функций получения производных ключей. Предыдущие схемы предоставляли безопасность для алгебраических функций выведения ключей, таких как линейные и полиномиальные функции над ключевым пространством, которое является частной группой, зависимой от схемы. Авторы предлагают схему "наилучшей возможной" безопасности, в которой функции выведения производных ключей должны удовлетворять только тем требованиям, которые необходимы для безопасности, в частности иметь непредсказуемый выход. Более того, в таких схемах ключи — это двоичные строки, а не элементы групп, что покрывает большинство простых практических атак, таких как проведение операции XOR ключа с константой. Для этого предлагаются только mUCE1-безопасные семейства функций.
  8. Трудно-коррелируемое безопасное хэширование. Требования к хэш-функциям с коррелированным входом (Correlated Input Hash — CIH) были сформулированы в некоторых работах и были предложены примеры их реализаций на основе RKA-безопасных блочных шифров. Однако их стойкость в стандартной модели оставалась открытой. Авторы решили эту проблему, показав, что UCE1-безопасные функции могут быть использованы для достижения CIH-безопасности.
  9. Безопасное хранилище. Существует ROM-протокол, позволяющий клиенту убедиться, что сервер полностью хранит его файл, но эта конструкция такова, что хотя сама она RO-неразличима, но может оказаться неудачной при попытке замены RO. В противоположность этому, авторы успешно применили UCE1.
  10. OAEP. Для RSA-OAEP авторы провели замены как с помощью UCE1, так и UCE2, получив результаты, пригодные для частного случая и более универсальных областей применения.
  11. Адаптивно-безопасные искажения. Проверяемый аутсорсинг и одноразово выполняемые программы наряду с наличием специальных токенов требуют адаптивно безопасных схем. Использование UCE2-схем вместо ROM-схем позволяет существенно уменьшить размеры токенов и впервые обосновать стойкость таких схем в рамках стандартной модели.

Указанные теоретические выкладки и приведённые результаты их использования в доказательстве стойкости протоколов говорят о большой перспективе использования модели универсального вычислительного экстрактора в проектировании криптографических протоколов и изучении их стойкости. Приведёт ли это к такой же смене парадигм, как введение случайного оракула в 1993 году, покажет время. Но уже сейчас можно сделать вывод об удачном расширении, дополнении и развитии RO-модели за счёт UCE-модели.


Результаты своих исследований авторы представят в докладе на конференции CRYPTO-2013.


Источник: Cryptology ePrint Archive


 
Несколько комментариев (7) [показать комментарии/форму]
Общая оценка документа [показать форму]
средний балл: +3респондентов: 2