Эффективные KDM безопасные схемы шифрования независимых открытых ключей

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:12, 14 декабря 2015.
Efficient Circuit-Size Independent Public Key Encryption with KDM Security
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Tal Malkin [@: 1]
Moti Yung [@: 2]
Isamu Teranishi [@: 3]
Опубликован 2011 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Безопасное шифрование для сообщений, зависящих от ключей (KDM) это новая область, которая привлекла много исследователей в последние годы. Грубо говоря, безопасная KDM схема по отношению к множеству функций обеспечивает безопасность, даже если шифруется KDM сообщение для любого . Мы представляем эффективную схему построения шифрования открытого ключа, которая KDM безопасна для широкого класса функций . Наше множество функций включает функции, вычисляемые полиномиальными модульными арифметическими цепочками (MAC); мы представляем множество как программы прямой линии, вычисляющие многомерные многочлены (расширенная схема включает в себя все рациональные функции, числитель и знаменатель для которых описаны в работе). В отличие от предыдущих схем, наша является гибкой: размер зашифрованного текста зависит от степени многочленов, и поэтому все параметры схемы являются полностью независимыми от размера функций или количества секретных ключей (пользователей). Мы отметим, что хотя KDM безопасность имеет практическое применение, все предыдущие работы со стандартной моделью либо имеют неэффективные результаты, при общих множествах функций, либо справедливы для небольшого набора линейных функций. Эффективность нашей схеме намного больше по сравнению с предыдущими результатами.

Введение

Работа с системами с открытыми ключами, защищенными от злоумышленников, имеющих возможность запрашивать тексты шифровок, является очень активной областью исследований в настоящее время. Исходные схемы, разработанные в этой области, назывались "круговыми" [CL01] Camenisch, J., Lysyanskaya, A.: An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001) </ref> и позволяли шифровать секретный ключ или линейную функцию секретного ключа; позже, были рассмотрены более общие функций, и безопасность этих схем называлась безопасностью для KDM сообщений [BRS02] Black, J., Rogaway, P., Shrimpton, T.: Encryption-Scheme Security in the Presence of Key-Dependent Messages. In: Nyberg, K., Heys, H.M. (eds.)SAC 2002. LNCS, vol. 2595, pp. 62–75. Springer, Heidelberg (2003) </ref>. В частности, мы говорим, что схема шифрования с открытым ключом (PKE) KDM [ ] безопасна (где является классом функций), если она является безопасной даже по отношению к противнику, имеющему открытые ключи и имеющему доступ к шифрованию KDM сообщений для адаптивно выбранных функций .

Недавние исследования, первоначально мотивированные тем, что в некоторых системах ключи шифруют другие ключи (благодаря самой схеме или неправильному использованию протоколов), показали наличие других причин для изучения KDM безопасности. С теоретической точки зрения, KDM безопасность может быть использована, чтобы "примирить" два основных подхода к безопасности, безопасность на основе неразличимости и Долево-Яо безопасность [AR00] Abadi, M., Rogaway, P.: Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption). In: Watanabe, O.,Hagiya, M., Ito, T., van Leeuwen, J., Mosses, P.D. (eds.) TCS 2000. LNCS,vol. 1872, pp. 3–22. Springer, Heidelberg (2000); J. Cryptology 15(2), 103–127 (2002), J. Cryptology 20(3), 395 (2007) </ref> [ABHS05] Ad˜ao, P., Bana, G., Herzog, J., Scedrov, A.: Soundness of Formal Encryption in the Presence of Key-Cycles. In: di Vimercati, S.d.C., Syverson, P.F., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 374–396.Springer, Heidelberg (2005)</ref> [BPS08] Backes, M., Pfitzmann, B., Scedrov, A.: Key-dependent message security under active attacks - BRSIM/UC-soundness of Dolev-Yao-style encryption with key cycles. In: CSF 2007, pp. 112–124 (2008); Journal of Computer Security 16(5), 497–530 (2008)</ref>. Это понятие имеет удивительную связь с другими фундаментальными понятиями, криптографической ловкостью [ABBC10] Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic Agility and Its Relation to Circular Encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403–422. Springer, Heidelberg (2010) </ref>, и запутыванием[CKVW10] Canetti, R., Tauman Kalai, Y., Varia, M., Wichs, D.: On Symmetric Encryption and Point Obfuscation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 52–71. Springer, Heidelberg (2010) </ref>. С практической точки зрения, KDM безопасности имеет ключевое значение для разработки некоторых криптографических протоколов. Например, это понятие используется в анонимных учетных системах [CL01] Camenisch, J., Lysyanskaya, A.: An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001)</ref>, где KDM безопасное шифрование используется, чтобы препятствовать делегации полномочий. Другим примером является полно-гомоморфное шифрование, где KDM безопасность используется для достижения неограниченного построения [G09] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169–178 (2009)</ref>.

Почти все предыдущие работы по KDM безопасности были сосредоточены на поиске KDM [ ] (стандартные модели) безопасных схем кодирования открытого ключа шифрования для класса функций , что осуществимо без уделения внимания эффективности. KDM безопасность для крупнейшего множества функций - всех функции ограниченной булевой схемы - была достигнута Бараком, Хайтнером, Хофхайнцем и Ишайем [BHHI10] Barak, B., Haitner, I., Hofheinz, D., Ishai, Y.: Bounded Key-Dependent Message Security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS,vol. 6110, pp. 423–444. Springer, Heidelberg (2010)</ref>, следуя предыдущим работам, таким как [BHHO08] Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-Secure Encryption from Decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008) </ref> [BHHO08] Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-Secure Encryption from Decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008)</ref>. Тем не менее, схемы во всех этих работах крайне неэффективны. Например, даже самая эффективная схема из работы </ref> требует вычисления возведений в степень для используемой группы на каждый бит секретного ключа. Здесь является параметром безопасности. Это приводит к наличию потерь по сравнению со стандартным Эль-Гамалевым шифрованием, где можно зашифровать бит, выполнив возведений в степень. Работа Аппельбаума, Кеша, Пайкерта и Сахаи [ACPS09] Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems.In: C 2009, pp. 595–618 (2009) </ref> является единственной, в который изучен эффективные и безопасные KDM схемы и предложена гораздо более эффективная схема, чем у других авторов. Тем не менее, эта работа KDM безопасна только для линейных классов функций. Мы обсуждаем предыдущие работы более подробно в разделе 1.7.

Наши задачи

Эффективное шифрование с большим количеством запросов. В этой работе мы рассматриваем проблемы поиска эффективных KDM безопасных схем, которые позволяют противнику выбирать из большого множества функций для секретного ключа. Эффективность схемы должна быть сопоставима с Эль-Гамалевым шифрованием (по крайней мере, для постоянного множества функций), представляющим из себя семантически безопасное шифрование (и значительно лучшее, чем в предыдущих работах</ref>, в которых требуется, по крайней мере, вычислений для Эль-Гамалева случая).

Построение эффективной KDM [ ] безопасной схемы для больших является сложной задачей, а техники из предыдущих работ являются неэффективными для этого. Действительно, все предыдущие работы в стандартной модели, либо дают неэффективные результаты, либо обладают заметные вычислительными затратами [CCS09] Camenisch, J., Chandran, N., Shoup, V.: A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 351–368. Springer, Heidelberg (2009)</ref>[BG10] Brakerski, Z., Goldwasser, S.: Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability (or: Quadratic Residuosity Strikes Back). In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 1–20. Springer, Heidelberg (2010), Full paper is available at eprint 2010/226 </ref>, либо применимы к небольшому классу функций, таких как линейные .

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

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

Наши результаты

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

Грубо говоря, наша схема обеспечивает KDM безопасность для многочленов и рациональных функций (отношений двух многочленов) для набора целых чисел ( по модулю), позволяющую неограниченное число ключей, схемы неограниченных размеров, вычисляющие многочлены, степень которых ограничена лишь временем шифрования. Это первый раз, когда определяется гибкость, и первый раз, когда для KDM безопасности достигнут такой уровень гибкости (без зависимости от количества ключей, без зависимости от времени генерирования ключей в схеме, при зависимости только от степени, даже не размера, схемы и времени шифрования). Мы приводим также общее доказательство с тремя режимами для KDM безопасности, которое использовалось в предыдущих работах, включая наши.

Далее мы описываем данные вопросы.

Классы функций

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

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

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

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

для

Эта функция может быть легко вычислена MAC схемой (с полиномиальным числом цепочек), но она имеет экспоненциальное число слагаемых при расширении.

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

Свойства предлагаемых схем

Построим две эффективные интеллектуальные KDM-безопасные PKE схемы следующим образом:

KDM Безопасность: Наши схемы будут и безопасными, соответственно, где является произведением двух простых чисел и .

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

Гибкость параметров: В наших схемах, в первый раз, число ключей для функции , число для расчетов MAC схемой (то есть, размер схемы), и общая степень для могут быть свободно выбраны противником. В частности, наши схемы будут KDM безопасными даже при условии, что противник может выбрать эти параметры произвольно и адаптивно, и когда полностью неограниченны, а необходимо в качестве входных данных на стадии шифрования. (Очевидной верхней границей для этих параметров является количество шагов для самого противника, что составляет некоторый многочлен ). Это также означает, что сторона, которая проводит шифрование, может выбрать, какие защищать в каждой шифровке, в зависимости от уровня чувствительности или риска предполагаемой KDM атаки.

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

Доказательство для модели с тремя режимами

Для наших доказательств безопасности, мы даем общие рамки для доказательств KDM безопасности, доказательство для модели с тремя режимами, в котором разъясняется его структура и освещаются важные части. На деле, определение KDM безопасности включает в себя противника, который может получить доступ к алгоритму шифрования, запрашивая шифровки для и получая либо правильный зависящую от ключа шифровку, либо случайную бит шифровку; противник не должен быть в состоянии провести различие между этими двумя случаями. Чтобы доказать безопасность, мы должны смоделировать случай, когда наличие любого противника нарушает основные предположения. Тем не менее, это проблематично, потому что без секретного ключа не ясно, как можно смоделировать вычисление шифровки для функций, зависящих от ключа, однако, с секретным ключом, эти два случая могут быть различимы, и нарушение основного предположения не дает никакого противоречия.

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

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

Методики

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

- Построим эффективную интеллектуальную KDM-безопасную PKE схему по отношению к умеренно большому и простому множеству . - Сократим KDM безопасность PKE по отношению к достаточно большому и сложному множеству до KDM безопасности по отношению к , за счет "сжатия" структуры MAC схемы в простую структуру .

Важно аккуратно выбирать , чтобы оно не было слишком большим или слишком маленьким. Мы выбираем как множество одномерных многочленов и строим KDM схему по отношению к , на основе новой идеи, каскадной Пайлер и Эль-Гамалевой шифровке, и показываем ее соответствие KDM безопасности.


KDM схема для одномерных многочленов: каскадная Пайлер Эль-Гамалева шифровка. Мы исходим из предыдущих работ (в частности, [BG10]), достигших KDM безопасности для линейных функций и битов. Преобразование их в интеллектуальные блочные схемы для секретных ключей осуществляется следующим образом1. Шифрование сообщений M в итоговой схеме [BG10] представляет из себя зашифрованный текст вида , где только А(М) зависит от сообщения (шифровка Эль-Гамаля); нашей отправной точкой была работа [KTY09]. KDM безопасность опирается на тот факт, что, когда сообщение является линейной функцией вида f(х) = ах + b секретного ключа х, его шифровка неотличима от шифровки , не зависящей от (ах + b), а только от а, b (таким образом можно провести моделирование с использованием ключа х). Чтобы расширить это свойство на , которое является многочленом f(х) степени d, мы обозначаем , и можем утверждать, как и выше, что зашифрованный текст неотличим от . Теперь правое слагаемое не зависит от секретного ключа, а левое зависит, но только как степень d-1 многочлена . Наша "каскадная Пайлер Эль-Гамалева" схема, таким образом, шифрует левой элемент, чтобы получить , и применить ту же идею для понижения степени на единицу. Мы можем продолжить рекурсивное построение этих пар, каждый раз шифруя левый элемент новой шифровкой. Окончательный зашифрованный текст мы выводим как набор, состоящий из всех правых элементов и последнего левого.

Сокращение от MAC схем до одномерных многочленов. Для того чтобы добиться нашего общего класса для большинства ключей, мы уменьшаем их количество, устанавливая секретные ключи как сумму из одного "секретного" ключа μ и "разницы" для μ2.Затем многочлен , вычисленный MAC схемой, может быть повторно интерпретирован как одномерный для μ. А именно, KDM безопасность по отношению к сводится до KDM безопасности по отношению к одномерному многочлену . Важный момент в приведенном процессе состоит в том, что коэффициенты для могут быть вычислены за полиномиальное время, если f является элементом из . Этот факт позволяет использовать полиномиальные по времени алгоритмы при моделировании. Именно поэтому мы используем .

Вторая схема: Безопасность для частных MAC схем. Зашифрованным текстом в нашей второй схеме для сообщения M является набор , где Enc является шифрованием первой схеме и R является случайно выбранным элементом. Значения и являются шифровками «числителя» и «знаменателя» для KDM сообщения и они вычисляются двумя MAC функциями f’ и f”. Здесь . Очевидно, что шифрование (C’, C”) KDM сообщения имеет распределение для случайно выбранного S. В этой связи мы успешно снижаем KDM безопасность второй схемы до KDM безопасности шифровок из первой схемы. Единственная проблема здесь в том, что знаменатель может быть равен 0 и, следовательно, в этом случае не может быть определена. Но мы можем преодолеть эту проблему, изменив немного схему и тщательно проводя доказательство.

Связанные работы и сравнение с нашими схемами

Рис.1 показывает сравнение предыдущих схем с нашими. Здесь κ является параметром безопасности. Обратим внимание, что все схемы, за исключением [CCS09] являются KDM-CPA безопасными, в то время как [CCS09] является KDM-CCA2 безопасной.

Пояснения Рис.1: "Размер" представляет собой число цепочек в MAC схеме, вычисляющих функции в случае наших схем. Колонка "Гибкость параметров" описывает гибкость параметров n,d, для функции . "Ограниченность KeyGen" означает, что нужно исправить максимум параметров перед генерированием ключей, KDM безопасность выполняется лишь тогда, когда параметр меньше максимального, и эффективность схемы зависит от этого максимума. "Ограниченность Enc" означает, что мы не должны фиксировать такие максимумы, и KDM безопасность имеет место для всех значений параметра, но параметр необходим для шифрования, и эффективность схемы зависит от его значения. "Неогр." означает, что схема (на всех стадиях) не зависит от значения этого параметра. Колонка "текст шифровки на сообщение" представляет собой соотношение между длиной шифровки текста и длиной сообщения. Отметим, что мы можем улучшить свойства известных схем на рис.1 за счет использования известных методик:

- Используя технику из работы [ACPS09], значение "текст шифровки на сообщение " из работ [BHHO08] и [BG10] может быть сведено к O(1). - Если функция ограничена полиномами, [BHHI10] может быть неограниченна в n.

Сравнение с [ACPS09]: Они имеют дело только с линейными функциями по сравнению с нашим большим множеством MAC схем, и они основаны на LWE предположении, в то время как у нас работает DCR предположение.


Сравнение с [BHHI10, A11]: Эти схемы достигают KDM безопасности по отношению к крупнейшему множеству функций (большему, чем у нас), хотя их схемы это результат, полученный из применения неэффективных безопасных вычислений. Важно знать возможности таких KDM схем, но они не сопоставимы с более эффективными схемами, независимыми от размеров, как в нашем случае. Это особенно важно с учетом применения таких схем. Размер для схемы ограничен в [BHHI10, A11], в то время как в нашей схеме он неограничен, и требуется только ограничение степени d.

Рис.1. Параметры для наших схем и предыдущих работ.

Сравнение с [BHHO08, BGK09, BG10]: Впервые KDM безопасность была достигнута в [BHHO08]. Их схема была использована в качестве основы для работ [BGK09] и [BG10], в которых достигнута KDM безопасность по отношению ко множеству многочленов постоянной степени для битов секретных ключей (как мы сказали, они могут описывать и блоки ключей, а не биты). Степени многочленов в [BGK09, BG10] должны быть ограничены константой (потому что длина текста шифровки в этих схемах растет экспоненциально с ростом этой степени), и, следовательно, алгоритм KeyGen ограничен. В противоположность этому, в наших схемах степени многочленов ограничены только шифрованием, а число слагаемых может быть также полиномиально. Для схемы [BG10] число пользователей ограничено алгоритмом KeyGen, в то время как оно неограниченно в наших схемах. Наконец, схемы [BGK09, BG10] (и в меньшей степени [BHHO08]) менее эффективны, чем наши.

Другие связанные работы. Понятие KDM безопасности было определено Блеком, Рогевейем и Шримптоном в [BRS02], хотя и Камениш и Лисянская в [CL01] самостоятельно определили аналогичное понятие, называемое схематичным шифрованием ранее. Ранее работы по KDM безопасности изучались в рамках модели случайного алгоритма. В [BDU08] показано, что известные OAEP шифровки являются KDM безопасными. В [HK07] обобщено понятие KDM безопасности для псевдослучайных функций. Построение KDM безопасных схем в стандартной моделе давно является открытой проблемой. Она была частично решена в [HU08] для случая симметричного шифрования ключей. Первый PKE, который является KDM безопасным в стандартной модели, был предложен в работе Боне, Галеви, Гамбурга и Островского [BHHO08]. Первый CCA2 и KDM безопасный PKE был предложен в [CCS09]. Общее преобразование, начиная с KDM безопасного PKE для определенного класса функций и до широкого класса, показанного в [A11]. Примеры PKE, которые удовлетворяют семантической безопасности, но не KDM (в частности, 2 этапные) безопасности были независимо показаны в работах [GH10] и [ABBC10]. В [HH09] показано, что безопасность схемы шифрования для "достаточного большого" не может быть доказана так как доказательство сокращения безопасности работает с функцией и противниками как с черными ящиками. Связь между адаптивной моделью Долева-Яо и обобщенной версией KDM безопасности изучаются в [BPS08], в то время, последующие связи KDM безопасности с ловкостью и запутыванием показаны в [ABBC10] и [CKVW10], соответственно. Мы отправляем читателя к работе [MTY11] для изучения итогов KDM безопасности и их приложений.

Предварительные сведения

Обозначения и терминология: Для натуральных чисел n, m ≤ n , пусть [n] и [m..n] будут множествами {1,...,n} и {m,..,n}, соответственно. Для действительного х, [x] будет обозначать наибольшее число, не превышающее x.

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

Группа Пайлера: Пусть N будет произведением двух простых чисел и Т будет 1+N. Определим три подмножества для , (наборы квадратичных вычетов, составные квадратичные вычеты, корни для множеств, а именно:

Теорема 1 ([Р99, DJ01, KTY09]). Существует полиномиальный по времени вычислимый биективный гомоморфизм , удовлетворяющий следующему свойству:

Кроме того, выполняется следующее свойство:

Определение 2. (Предположение о выборе составных вычетов (DCR) [P99, DJ01]). Пусть s ≥ 2 будет числом. Тогда существует такой генератор Gen для результата N от двух безопасных простых чисел, что следующее значение пренебрежимо для к и для любого противника A:

Наше DCR предположение немного отличается от оригинала в [P99, DJ01], где g берется из в первой (или второй) игре, но наше предположение следует за исходным, за счет возведения g в квадрат.

KDM безопасность

Схема шифрование открытого ключа: В данной работе схема шифрования открытого ключа имеет генератор Setup для параметров системы prm, таких, как описание группы, и все пользователи широко используют этот параметр, как входы для трех других алгоритмов.

Описание функций: Как и в предыдущих работах, мы предполагаем, что все функции f имеют некоторый многочлен размера D. (В случае с нашими схемами, D является MAC схемой или MAC вычисляющей f). Через мы обозначим функцию, соответствующую D.

KDM безопасность: Для схемы шифрования открытых ключей и ее пространств секретных ключей SkSp и сообщений MeSp, выполнено

Для упрощения мы предполагаем, что SkSp и MeSp зависят только от параметров системы prm. Для натурального числа n и бита b, рассмотрим следующую игру:

В этой игре A разрешается делать адаптивные запросы:

- Если A делает i-й запрос new из , то он генерирует i-ю пару ключей и посылает в качестве ответа. - Если A делает i-й запрос (i,D) из , где i [n] и D является описанием функции , алгоритм отвечает на следующие запросы C ( является некоторым фиксированным элементом MeSp и n это число ключей, созданных ):

Мы будем утверждать, что схема безопасна, если следующая величина пренебрежима для любого n и любого алгоритма А.

Можно легко проверить, что данное определение не зависит от выбора , если удовлетворяет свойству неразличимости. Наше определение KDM безопасности сильнее, чем в предыдущих работах [BRS02, BHHO08]: оно позволяет противнику адаптивно получить новый ключ, в то время как предыдущие работы [BRS02, BHHO08] этого не позволяли. (Другими словами, используя терминологию раздела 1.4, число ключей n становится "неограниченным"). Некоторые известные схемы (например, [BG10]) требуют фиксации максимального n до генерирования ключей, и KDM безопасность в них может быть доказана только тогда, когда n меньше заданного максимума. Наша схема не требует фиксации n и поэтому в ней может быть доказано строгое свойство KDM безопасности.

Модульные арифметические схемы

Определение 3 (модульные арифметические схемы (MAC)). Модульной арифметической схемой D (MAC) будет схема, входы для которой это переменные и константы , и в ней выполняются операции +, -, или • для более . (Подчеркнем, что цепочки в данном случае неограниченны). Для MAC-D схемы, количество операций в D называется размером D. Обратим внимание, что в нашем случае MAC схемы эквивалентны программам прямой длины с неограниченным количеством регистров. Очевидно, что функция, вычисляемая MAC схемой является многочленом из . Мы обозначим как функцию f, когда MAC-D схема вычисляет f. Для натуральных чисел , представляет множество всех рациональных функций, которые могут быть вычислены с помощью некоторой MAC-D схемы с размером и 3.Здесь n определяет число входов для D.

KDM безопасные схемы по отношению к MAC схемам с ограниченной степенью

Каскадные Пайлер Эль-Гамалевы шифровки: Наша схема, называемая d каскадной Пайлер Эль-Гамалевой, рекурсивно вычисляется следующим образом. Сначала проводится "Пайлер Эль-Гамалева" шифровка для сообщения M, где Т=1+N и . Затем левое слагаемое текста шифровки также шифруется по "Пайлеру Эль-Гамалю" и получаем для , где . Затем мы задаем как . (обратим внимание, что большая часть шифровки не зависит от сообщения и может быть осуществлена автономно с учетом границы для степени, как Эль-Гамалева схема, но с существенно большей производительностью). d каскадная Пайлер Эль-Гамалева схема шифровки сообщения М это множество


Подробная схема: В нашей схеме используются параметры безопасности κ и ξ, а s ≥ 2 и d это целые положительные числа. Схема осуществляется следующим образом: - Создается N значений из двух простых чисел с бит длиной . Выбирается случайным образом, и выводится . (Через Т мы обозначаем 1+N.)


3 – Общая степень многочленов не может быть вычислимой из D за полиномиальное время. Но этот факт не является проблемой в нашем случае, потому что мы можем легко вычислить верхнюю границу для общей степени из D.


- Выбирается случайным образом, вычисляется , и выводится .

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


- C раскладывается как и выводится

Где L это функция, заданная в теореме 1.

Безопасность: Мы докажем следующую теорему в разделе 6.

Теорема 4 (KDM безопасность нашей схемы по отношению к ). Для любых многомерных параметра безопасности к, предложенная схема является KDM безопасной по отношению к в рамках DCR предположения.

В частности, для любых многомерных и любого полиномиального по времени противника A, нарушающего KDM безопасность нашей схемы, существует противник B, нарушающий DCR предположение в и удовлетворяющий


Где q является количеством запросов для A, определяет число вычислительных шагов для компьютеров, а Е обозначает полные вычислительные затраты для . Мы можем показать более строгий вариант теоремы 4, где противник может сразу выбирать параметры когда он делает запросы шифровок. (В частности, d становится ограниченным, а неограниченным, как указано в разделе 1.4). Доказательство этого строгого уровня безопасности аналогично доказательству теоремы 4. Поэтому мы его опускаем.

KDM безопасные схемы по отношению к частным MAC схемам с ограниченными степенями

В этом разделе приводится общее преобразование из безопасной схемы в безопасную схему, где определяет множество многочленов из , а это множество всех рациональных функций для . Применяя это преобразование к нашей первой схеме, мы можем получить безопасную схему. Трудность в создании безопасных схем заключается в том, что знаменатель для может быть равен 0 (или, может быть необратимым): это становится проблемой при доказательстве безопасности схемы, поскольку моделирование в доказательстве (которое не знает sk) не может знать, является ли обратимым или нет. Поэтому мы должны изменить нашу схему и доказать ее безопасность так, чтобы можно было смоделировать состояние противника, даже не зная обратимости . Мы учитываем сложность факторизации модулей K. Тогда не возможно будет найти значение , которое будет не нулевым, но и необратимым. (Если находится такое , то можно факторизовать К путем вычисления ). Таким образом, можно предположить, что значение либо обратимо, либо равно 0. Затем мы определяем значение функции с следующим образом, где 1/0 и 0/0 являются специальными символами. Обратим внимание, что мы не обязаны рассматривать другой случай (то есть случай, когда не равна 0, но необратима), в соответствии с приведенным выше обсуждением. Пусть будет схемой шифрования открытого ключа, чьи секретные ключи и сообщения берутся из для некоторого целого К. Преобразование схем из осуществляется следующим образом. - Объем сообщений из равен . Здесь, 1/0 и 0/0 являются специальными символами. - Представляет из себя тоже, что и - Выбирается случайным образом и вычисляется

После чего выводится

- разбивает C на и вычисляет

После чего выводится 1/0, если и . Выводится 0/0, если . В противном случае выводится .

Теорема 5. Предполагается сложность факторизации К. Предположим также следующее свойство: для любых , функция будет являться элементом Далее безопасность для подразумевает безопасность для схемы. Доказательство. (примерное) Противник B для безопасности схемы создается из противника А для безопасности схемы следующим образом. B принимает открытый параметр prm и множество открытых ключей в качестве входных данных и передает их к А. Когда А посылает запрос и пары описаний MAC схем, B случайным образом выбирает , задает значения Е’ и Е” для описания функций , соответственно, посылает запросы , получает ответы C’ и С” от соперника, и посылает (С’,С”) обратно к А в качестве ответа на запрос. Если А выводит бит , то B выводит бит . Из-за сложности факторизации К, значения будут либо обратимыми, либо равными 0. Таким образом, мы можем рассмотреть . Таким образом,

Сообщения, которые В должен зашифровать в приведенных выше случаях, это , 1/0, и 0/0 соответственно. Это означает, что состояние А смоделированное противником B идентично настоящему. Приведенное доказательство сложно выполнимо, если факторизация К легко осуществима, потому что А может послать такой запрос (D’, D”), что будет равна 0, но необратима. Это означает, что К не может быть равно Ns-1 для s ≥ 3.

Доказательство для модели с тремя режимами

Краткий обзор

Данное доказательство вводится для преодоления дилеммы, описанной в разделе 1.5. Она имеет три режима, так называемые стандартный, поддельный, и скрытый. Стандартный режим соответствует исходной игре для KDM безопасности. Другие два режима заключаются в следующем. (См. рис.2)

Рис. 2. Доказательство для модели с тремя режимами.

Поддельный режим: Этот режим позволяет вычислить "поддельные тексты шифровок" с помощью запросов противника (i,D), но без использования секретных ключей. Поддельные тексты должны быть неотличимы от текста из стандартного режима, при условии, когда при моделировании известны секретные ключи. Это неразличимость не может быть доказана при отсутствии секретных ключей. Вместо этого мы должны доказать это свойство для безопасности случайности шифрования. Данная неразличимость является важной частью доказательства KDM безопасности.

Скрытый режим: Этот режим позволяет вычислять "скрытый текст" без помощи запросов противника (i,D) и секретных ключей. Скрытый текст должен быть неотличим от поддельного, в предположении, что при моделировании не известны секретные ключи. Обратим внимание, что знания секретных ключей не требуется потому, что поддельный и скрытый тексты могут быть вычислены без использования секретных ключей. Данная неразличимость может быть показана, с использованием стандартных криптографических аргументов для безопасности секретных ключей. Так как скрытый текст не зависит от запроса противника D, KDM безопасность четко выполняется.

Формальное описание

Модель с тремя режимами для схемы представляют из себя пару поддельных режимов и скрытый режим . Входы и выходы для алгоритма задаются следующим образом. - принимает открытые параметры prm , натуральное число n в качестве входов и выводит n пар ключей . - принимает те же входы, что и , ключи и . - берет в качестве входных данных открытые параметры prm, набор открытых ключей , , натуральное число i, а также описание D для функций из и выводит C. - принимает те же входы, что и за исключением D и выводит C. Доказательство KDM безопасности схемы по отношению к множеству функций осуществляется за счет того, что вероятность успеха для А в такая же, как и в двух последующих играх и , но с незначительными различиями.

Где А разрешается делать адаптивное количество запросов. Он может отправить в качестве запроса бит строку и пару . Здесь i ∈ [n] это целые числа и D является описание функций в . От алгоритмов получаются следующие ответы:

- возвращает , созданный KgFake (в GameFake) или KgHide (в GameHide).

В конечной игре текст шифровки больше не зависит от f, запрашиваемой противником А. Таким образом, справедлива следующая теорема. Теорема 6. Предполагая, что для любого полиномиального противника А существует такая малая функция , что различия между будут меньше для любого , тогда схема будет безопасность. Как уже отмечалось, доказательство известных KDM безопасных схем в стандартных моделях [BHHO08, ACPS09, BG10] может быть интерпретировано, как указано выше.

Доказательство безопасности первой схемы

Интерактивная векторная лемма

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

  •  : , , Выводит
  •  : , , Выводит

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

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

Для преимущество в определяется как

TemplateLemmaIcon.svg Лемма «Лемма 1 ((DCR) Интерактивная векторная лемма при полная версия в ).»
Для ни один полиномиальный противник не может иметь пренебрежимое преимущество в при DCR предположении.


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

Доказательство для случая, когда число n ключей равно 1


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

Противник в этой игре берет открытые параметры и один открытый ключ в качестве входов. Всякий раз, когда посылает в качестве запроса «описание» функции в , называемое , претендент отправляет обратно

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

Безопасность доказывается здесь на основе доказательства для модели с тремя режимами из раздела 5. Алгоритмы KgFake и EncFake определяются следующим образом.

  •  : Тот же алгоритм, что , за исключением того, что он устанавливает для нулевой строки.
  •  : Разделяет и как и . Берется и вычисляется для . Пусть . Вычисляется и выводится "поддельные текст"

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

посылает запросы и получает соответствующие ответы (где ). Далее В выбирает , вычисляет , вычисляет при и отправляет их обратно к А

Если А выводит бит b’, тогда B выводит его и останавливается. По определению B, разница между двумя вероятностями и незначительна. Алгоритмы в GameHide, то есть KgHide и EncHide, определяются следующим образом.


- KgHide (prm): Берется и выводится .(Она устанавливает aux для нулевой строки). - EncHide (prm, рk, aux): Разделяет prm и рk как (s,N,g) и pk = h. Берется и вычисляется для . Вычисляется и выводится "скрытый текст"

А именно, EncHide выводит .

Мы покажем, что разница незначительна. С этой целью противник B для игры IVk для k = 2 создается следующим образом. B принимает входы (s,N,g,h) передает к А. Если А делает запрос D, тогда . Затем В задает

посылает запросы и получает ответы (где ) и передает обратно к А

Если А выводит бит b’, тогда B выводит его и останавливается. По определению B, разница между двумя вероятностями и незначительна. Согласно теореме 6, наши схемы KDM безопасны.

Суть доказательства для общего случая

В данной версии работы мы приведем только основные идеи доказательства. Они также применимы для доказательства в разделе 6.2, за исключением того, что мы уменьшаем секретов до одного секрета для KgFake и EncFake.

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

, для ,

Другими словами, вычисляется только для одного секрета . Доказательство, таким образом, сводится к случаю, когда число секретов равно . Описание EncFake также изменяется, чтобы быть согласованным с новым KgFake. В частности, EncFake принимает , и запрос противника и вычисляет . Здесь является множеством , удовлетворяющее следующим уравнения для . здесь обозначает суммарную степень для

.

EncFake затем выводит "поддельную шифровку"

где для . (Подчеркнем, что вычисляется с использованием i-го открытого ключа , где это часть запроса

TemplateLemmaIcon.svg Лемма «Лемма 2»
Принимая и MAC-D описание, может быть вычислен за полиномиальное время.


KgHide и EncHide могут быть построены аналогично. Доказательства неразличимости для игр аналогичны разделу 6.2.

Благодарности

Мы благодарим Звика Бракерски и Евгения Вахлиса за помощь в некоторых обсужденных проблемах. Мы также благодарим Звика, Шафи Гольдвассера, Яэля Тауман Калая и анонимных рецензентов конференции Eurocrypt за полезные комментарии относительно нашей работы.

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

  1. Columbia University E-mail: [1]
  2. Google Inc E-mail: [2]
  3. NEC Japan E-mail: [3]

Примечания

Литература

  1. [AR00] Abadi, M., Rogaway, P.: Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption). In: Watanabe, O.,Hagiya, M., Ito, T., van Leeuwen, J., Mosses, P.D. (eds.) TCS 2000. LNCS,vol. 1872, pp. 3–22. Springer, Heidelberg (2000); J. Cryptology 15(2), 103–127 (2002), J. Cryptology 20(3), 395 (2007)
  2. [ABBC10] Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic Agility and Its Relation to Circular Encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403–422. Springer, Heidelberg (2010)
  3. [ABHS05] Ad˜ao, P., Bana, G., Herzog, J., Scedrov, A.: Soundness of Formal Encryption in the Presence of Key-Cycles. In: di Vimercati, S.d.C., Syverson, P.F., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 374–396.Springer, Heidelberg (2005)
  4. [A11] Applebaum, B.: Key-Dependent Message Security: Generic Amplification and Completeness Theorems. In: Paterson, K.G. (ed.) EUROCRYPT 2011.LNCS, vol. 6632, pp. 506–525. Springer, Heidelberg (2011)
  5. [ACPS09] Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems.In: C 2009, pp. 595–618 (2009)
  6. [BDU08] Backes, M., D¨urmuth, M., Unruh, D.: OAEP Is Secure under Key-Dependent Messages. In: Pieprzyk, J.(ed.) ASIACRYPT 2008. LNCS,vol. 5350, pp. 506–523. Springer, Heidelberg (2008)
  7. [BPS08] Backes, M., Pfitzmann, B., Scedrov, A.: Key-dependent message security under active attacks - BRSIM/UC-soundness of Dolev-Yao-style encryption with key cycles. In: CSF 2007, pp. 112–124 (2008); Journal of Computer Security 16(5), 497–530 (2008)
  8. [BHHI10] Barak, B., Haitner, I., Hofheinz, D., Ishai, Y.: Bounded Key-Dependent Message Security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS,vol. 6110, pp. 423–444. Springer, Heidelberg (2010)
  9. [BRS02] Black, J., Rogaway, P., Shrimpton, T.: Encryption-Scheme Security in the Presence of Key-Dependent Messages. In: Nyberg, K., Heys, H.M. (eds.)SAC 2002. LNCS, vol. 2595, pp. 62–75. Springer, Heidelberg (2003)
  10. [BG10] Brakerski, Z., Goldwasser, S.: Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability (or: Quadratic Residuosity Strikes Back). In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 1–20. Springer, Heidelberg (2010), Full paper is available at eprint 2010/226
  11. [BGK09] Brakerski, Z., Goldwasser, S., Kalai, Y.: Circular-Secure Encryption Beyond Affine Functions. e-print. 2009/511
  12. [BHHO08] Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-Secure Encryption from Decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008)
  13. [BV98] Boneh, D., Venkatesan, R.: Breaking RSA May Not Be Equivalent to Factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp.59–71. Springer, Heidelberg (1998)
  14. [CCS09] Camenisch, J., Chandran, N., Shoup, V.: A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 351–368. Springer, Heidelberg (2009)
  15. [CL01] Camenisch, J., Lysyanskaya, A.: An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001)
  16. [CKVW10] Canetti, R., Tauman Kalai, Y., Varia, M., Wichs, D.: On Symmetric Encryption and Point Obfuscation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 52–71. Springer, Heidelberg (2010)
  17. [DJ01] Damg˚ard, I., Jurik, M.: A Generalization, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System. In: Kim, K.- c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001)
  18. [G09] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169–178 (2009)
  19. [GH10] Green, M., Hohenberger, S.: CPA and CCA-Secure Encryption Systems that are not 2-Circular Secure. e-print. 2010/144
  20. [HH09] Haitner, I., Holenstein, T.: On the (Im)Possibility of Key Dependent Encryption. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 202–219. Springer, Heidelberg (2009)
  21. [HK07] Halevi, S., Krawczyk, H.: Security under key-dependent inputs. In: ACM CCS 2007, pp. 466–475 (2007)
  22. [HU08] Hofheinz, D., Unruh, D.: Towards Key-Dependent Message Security in the Standard Model. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 108–126. Springer, Heidelberg (2008)
  23. [KTY09] Kiayias, A., Tsiounis, Y., Yung, M.: Group Encryption. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 181–199. Springer, Heidelberg (2007)
  24. [MTY11] Malkin, T., Teranishi, I., Yung, M.: Key Dependent Message Security: Recent Results and Applications. In: ACM CODASPY (2011)
  25. [P99] Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)