Функц. шифрование внутреннего продукта: достижение шифротекстов постоянного размера с адаптивной безопасностью и поддержкой отрицания

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 05:58, 5 ноября 2015.
Functional Encryption for Inner Product: Achieving Constant-Size Ciphertexts with Adaptive Security or Support for Negation
Functional Encryption for Inner Product.png
Авторы Nuttapong Attrapadung[@: 1], Benoît Libert[@: 2]
Опубликован 2010 г.
Сайт Homepage of The International Association for Cryptologic Research
Перевели Alexei Shcherbakov
Год перевода 2015 г.
Скачать оригинал


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

Содержание

Введение

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

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

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


Связанные работы. Первые упоминания о функциональном шифровании восходят к работам Sahai и Waters [3], которые впоследствии были расширены в [4], [5]. Их концепция, называемая шифрованием на основе атрибутов (ABE), позволяет отправителю зашифровать данные под набор атрибутов , в то время как специалисты создают секретные ключи для политик контроля доступа . Права расшифровки имеет любой у кого есть секретный ключ для политики такой, что . Схемы широковещательного шифрования на основе идентификации (IBBE) [6], [7], [8], [9] и отзыва (IBR) [10] могут также рассматриваться как системы функционального шифрования где шифротексты зашифрованные для набор сущностей : в IBBE (соотв. IBR) системах, расшифрование требует наличия секретного ключа sk_{id} для которого (cоотв. .

Вышеперечисленные системы функционального шифрования только скрывающие полезную нагрузку, так как они держат зашифрованные сообщения скрытыми от неавторизованных групп пользователей, но не скрывают их основной набор атрибутов. Схемы предикатного шифрования [11], [12], [13], [14] кроме того обеспечивают анонимность, так как шифротексты скрывают набор атрибутов с которыми они связаны, что позволяет [15], [16] эффективные поиски по зашифрованной информации. В [12], Катз, Сахаи и Уотерс разработали схему предикатного шифрования для внутренних продуктов: шифротекст зашифрованный для вектора атрибутов может быть открыт любым ключом , таким что . Как показано в [18], шифрования внутреннего продукта (IPE) достаточно, чтобы сделать функциональное шифрование для ряда отношений соответствующих оценке многочленов или формулам CNF/DNF.


Наш вклад. Будучи весьма полезной, схема IPE [12] стремится к анонимизации шифротекстов, что делает ее слишком сложной для преодоления барьера линейной сложности (в векторе длины n) с точки зрения длины шифротекста. Действительно, кажется очень трудным избежать зависимости от большой длины при обеспечении анонимности: например, анонимные FE конструкции [11], [17] страдают от таких же затрат. Схожая проблема возникает в контексте широковещательного шифрования, где единственная известная схема [18], которая скрывает набор приемника также имеет шифротексты длины .

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

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

Наша первая IPE система достигает адаптивной безопасности, в отличие от селективной модели, используемой в [12], где противник должен выбрать целевой вектор шифротекста заранее. Чтобы достичь адаптивной безопасности, мы в основном используем метод, используемый в полностью защищенных IBE Уотерсa [19], хотя мы также должны ввести новый трюк, названный “n-equation technique” с тем, чтобы иметь дело с богатой структурой IPE. Наша система непосредственно дает первую адаптивно безопасную схему широковещательного шифрования на основе идентификации с постоянным размером шифротекстов в стандартной модели. Предыдущая IBBE с шифротекстами размера была либо только с селективной безопасностью на основе идентификации [6], [8][9], [7] или в модели случайного оракула [20]. Среди IBBE систем предоставляющих компактные шифротексты (включая модель с селективной безопасностью на основе идентификации), наша модель первая полагается на простые предположения (т.е. без предположений q-типа) в группах простого порядка.

Стоит отметить, что техники, разработанные Левко и Уотерсом [21] могут быть применены к конструкции Боне и Гамбурга [9] для получения полностью безопасной IBBE с короткими шифротекстами в группах составного порядка. Тем не менее, ранее не было известно как получить такую схему в группах простого порядка (по крайней мере не полагаясь на отсутствие вычислимого изоморфизма в ассиметричных парных конфигурациях). Действительно, несмотря на недавний прогресс [22], до сих пор нет способа черного ящика для перевода криптосистем, основанных на сопряжении из групп составного порядка, в простой. В частности, фреймворк Фримана [22] не применим к [21].

Наш второй вклад — это IPE системы для ненулевых внутренних продуктов: шифротексты зашифрованные для вектора могут быть расшифрованы с использованием , только если , которые — без сохранения анонимности — решают вопрос, оставленный открытым Катзом, Сахаи и Уотерсом [12][Раздел 5.4]. Схема заключает в себе первый основанный на идентификации механизм отзыва с шифротекстами размером . Как и в схемах Левко, Сахаи и Уотерса [10], его безопасность анализируется в неадаптивной модели, где противник должен выбрать каких пользователей атаковать с самого начала игры.[прим.: 1] В сравнении с [10], где шифротексты растут линейно вместе с числом отозванных пользователей и открытых/секретных ключей, имеющих постоянный размер, наша основная конструкция IBR выполняется двойственным образом, так как размер ключей зависит от максимального числа отозванных пользователей. В зависмости от применения, можно предпочесть ту или иную схему. Мы покажем как обобщить обе реализации и получить компромисс между размерами шифротекста и ключа (и без предположений о максимальном числе отозванных пользователей): вторую схему [10] и нашу можно рассматривать как лежащие на противоположных концах спектра.

С теоретической стороны, наша ненулевая IPE реализация оказывается частным случаем более общего примитива, который мы называем обратное пространственное шифрование, которое мы определяем как обратный режим пространственного шифрования примитива Боне и Гамбурга [9]. А именно, ключи соответствуют подпространствам и могут расшифровать шифротексты зашифрованные точками, которые лежат за пределами подпространства. Этот обобщенный примитив оказывается нетривиальным для реализации и нам пришлось использовать полностью обобщенную форму нашей новой техники “n-equation”. Предложенная схема доказала безопасность при нестандартном предположении определенном в [10].


Наши техники. Ядро техники нашей схемы ненулевого IPE будет использоваться на протяжении всей статьи, в том числе в нашей адаптивно безопасной нулевой IPE схеме. Это можно рассматривать аналогично факту того, что полностью безопасная IBE Уотерса [19] использует технику отзыва [10]. Наша ненулевая IPE также опирается на [19]. Тем не менее, факт того, что ненулевая IPE имеет более богатую структуру чем схема отзыва и преследуемая цель получения шифротекста постоянного размера, вместе мешают нам использовать их техники напрямую. Для описания трудностей, которые возникают, для начала мы обрисуем в общих чертах схему отзыва Левко-Сахаи-Уотерса в ее простейшей форме, где требование безопасности не предъявляется и где только один пользователь отозван.

Конструкция 1. (Упрощенная схема отзыва)
: пусть билинейные группы простого порядка и включают . Открытый ключ . Мастер ключ .
выбираем и выводим секретный ключ для идентификатора как .
шифруем M и определяем отозванные выбирая и вычисляя .
расшифрование вычисляет если . Затем вычисляет как .


Схема может быть объяснена рассмотрением ключа и шифротекста как формирования нелинейной системы из 2-х уравнений в экспоненте с переменными .


.

Вычисление равнозначно решению системы, которое возможно, когда (и, таким образом требуется ). В частном случае, расшифрование вычисляет линейную комбинацию (в экспоненте) с коэффициентами из первой строки которыми являются . В [10], это называется "2-equation technique". Схема расширена до размерности n, т.е., отзыв n пользователей , используя n локальных независимых систем из двух уравнений.

for ,

Что дает 2n компонентов шифротекста , каждый из которых соответствует доле из таких что . Расшифрование на j-ой системе возвращает , если . Сочетание этих результатов наконец дает .

Мы нацелены на постоянный размер шифротекстов для ненулевых IPE схем размерности n. При попытке использовать технику 2-х уравнений с n измерениями, возникают следующие сложности. Во-первых, условие "расшифруемости" не может быть разложено так просто как в схеме отзыва, которое разлагается как соединение для . Во-вторых, размер шифротекста был .

Для решения этого, мы введем технику называемой “n-equation technique”. Во-первых, мы используем n секретных показателей и пусть функция — "главный" показатель пока служат как “возмущенные” факторы. Интуитивно, мы создали систему из n линейных уравнений вида:

        

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

 

где утверждается что det. Переводя это концептуальное представление обратно в алгоритмы, мы получим базовую ненулевую IPE схему. Исходя из этого, мы предлагаем две схемы для ненулевых IPE: первая является частным случаем схемы инвертированного пространственного шифрования в разделе 5.1, в то время как вторая доказывает безопасность под простыми преположениями и будет приведена в разделе 5.2.

Организация. В предстоящих разделах, синтаксис и приложения функционального шифрования описаны в разделах 2 и 3. Мы описываем наш нулевой режим IPE системы в разделе 4. Наши инвертированные схемы подробно описаны в разделе 5.

Определения

Синтаксис и определение безопасности для функционального шифрования

Пусть — булева функция, где и обозначают пространства "ключевого атрибута" и "атрибута шифротекста". Схема функционального шифрования (FE) для R состоит из следующих алгоритмов.

  • принимает на вход параметр безопасности и схема описания des (которая обычно описывает измерение n), и на выходе дает открытый мастер ключ pk и секретный мастер ключ msk.
  • принимает на вход ключевой атрибут и мастер ключ msk. На выходе дает секретный ключ расшифрования .
  • принимает на вход атрибут шифротекста , сообщение , и открытый ключ pk. На выходе дает шифротекст C.
  • получает шифротекст C с его атрибутом y и ключ расшифрования с его атрибутом , на выходе дает сообщение M или .

Нам требуется стандарт корректности расшифрования, то есть, для всех , все , все , все , и все ,

  • Если , тогда .
  • Если R(x,y) = 0, Decrypt(Encrypt(y,M,pk),sk_x)= \bot </math> с вероятностью около 1.

Терминология и варианты. Мы ссылаемся на любой примитив шифрования A который может быть использован как функциональное шифрования путем изменения его соответствующей функции Для FE примитива A, мы можем определить два варианта:

  • Парный вариант, обозначается Dual(A), определяется путем установки и и . В парном варианте, роли атрибутов ключа и шифротекста изменены местами относительно тех, которые были в оригинальном примитиве.
  • Инвертированный вариант, обозначается , определяется с использованием тех же доменов как в A и установкой . Состояние, таким образом, противоположно оригинальному примитиву.

Определение безопасности. Схема FE для функции полностью безопасна если ни один PPT противник не имеет большого преимущества в этой игре.

Установка. Посылающий вызов запускает Setup(n) и получает открытый ключ pk для .

Запрос Фаза 1. Посылающий вызов отвечает на запросы секретного ключа для возвратом .

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

Запрос Фаза 2. Противнику разрешается делать последующие запросы секретного ключа под тем же ограничением, что и выше, т.е., . 'Угадывание. Противник дает предположение и выигрывает, если . В игре, 's преимущество, как правило, определяется как .

(Совместно-)Выборочная Безопасность. Мы также рассмотрим понятие выборочной безопасности [23][24], где должна выбрать атрибут посылающего вызов перед фазой установки, но может адаптивно выбирать запросы ключа для . Можно считать это двойным понятием, где должно подавать на выход q запросов ключа для векторов атрибутов перед фазой установки, но может адаптивно выбирать целевой атрибут посылающего вызов . Мы ссылаемся на этот сценарий как на модель совместно-выборочной безопасности, которая полезна в некоторых приложения таких как отзыв. По определению, оба понятия несравнимы и мы пока не знаем об их взаимосвязи.

Мы покажем как один FE примитив может быть получен из другого. Следующая полезная лемма из [9] описывает достаточный критерий для импликации.

TemplateLemmaIcon.svg Лемма «Предположение 1 (Вложенная Лемма[9]).»
Рассмотрим примитивы шифрования A,B которое могут быть использованы как функциональное шифрование для функций , соответственно. Предположим что существуют эффективные инъективные отображения и такие что . Пусть — это конструкция для примитива B. Тогда мы построим для примитива A из применяя отображения ко всем атрибутам ключа и атрибутам шифротекста, соответственно. Точнее, мы используем точно такой же алгоритм установки и, определим поколение ключа и процедуры шифрования как и , соответственно. Тогда, если безопасна, такова же . Это справедливо для адаптивных, выборочных, совместно-выборочных моделей безопасности.


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

TemplateConsequenceIcon.svg Следствие Следствие 1
предполагает и .


Сложность предположений в билинейных группах

Мы рассматриваем группы простого порядка p с эффективно вычисляемой таблицей такой что для любого и и когда бы ни . В этих группаx, мы предполагаем сложность проблем Билинейного решения Диффи-Хэлмана и Линейного решения [25].

TemplateDifinitionIcon.svg Определение «Определение 1: Решение билинейной проблемы Диффи-Хэлмана (DBDH)»
(DBDH) в это получение элементов with ,чтобы решить или .
TemplateDifinitionIcon.svg Определение «Определение 2: Решение линейной проблемы (DLIN)»
(DLIN) в состоит в получении кортежа with и , принимая решение or .

Требования функционального шифрования и их значение

Шифрование внутреннего продукта и его следствия

Мы подчеркиваем силу IPE показывая его значение в этом разделе. Каждый примитив определяется путем описания соответсвующей булевой функции . Затем мы покажем, как построить один примитив из другого с помощью точного описания отображения атрибутов. Таким образом, корректность и безопасность следствия вложенной леммы. В целом, подход выводится тем же путем как в [12]. Новый вклад, который мы также рассмотрим это инвертированный вариант примитивов, который будет полезен для схем ненулевой полиномиальной оценки и отзыва. Значение для инвертированных вариантов вытекает из Следствия 1.


Внутренний продукт. Схема шифрования внутреннего продукта (IPE) над , для некоторого простого p, определяется следующим образом. Обе области атрибутов .

Здесь мы рассмотрим два различных режима IPE. Первый – это нулевой режим IPE, где тогда и только тогда, когда . Другой — это инвертированый примитив, который мы называем ненулевым режимом IPE, где тогда и только тогда, когда .


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

Учитывая схему IPE над , можно получить систему функционального шифрования для полиномиальной оценки при помощи следующего вложения. Для атрибута ключа, мы отображаем полином к . Относительно атрибутов шифротекстов, каждый элемент отображается вектором . Корректность и безопасность соблюдаются поскольку всякий раз когда . Случай ненулевой оценки может быть аналогично получен из ненулевого режима IPE, использующего те же самые отображения, в силу Следствия 1.

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

OR, AND, DNF, CNF формулы. Теперь рассмотрим схему для некоторых булевых формул, которые оценивают дизъюнкцию, конъюнкцию и их расширения к дизъюнктивым или конъюктивным нормальным формам. В качестве примера, функциональное шифрование схемы для булевой формулы может быть определена как тогда и только тогда, когда или или . Это может быть получено из функционального шифрования для нулевой оценки одномерного полинома степени меньшей, чем n, генерируя секретный ключ для , и позволяя отправителям шифрование для .

Другие фундаментальные случаи можно рассматривать точно так же как в [12] и как показано ниже. В [12] только не инверсные политики (первые три случая ниже и их расширения) были рассмотрены. Схемы поддерживающие отрицательные политики (последние три случая ниже и их расширения) введены в этой статье. Инверсный случай может быть реализован как IPE для ненулевой оценки. Можно объединить эти случаи, чтобы получить DNF, CNF формулы. Ниже, выбирается с помощью .[прим.: 2]


На основе идентификатора шифрования вещания и отзыва. Пусть является идентичным пространством. На основе схемы шифрования вещания (IBBE) для максимального n получатели в зашифрованном тексте являются функциональным шифрованием для определенным с помощью . Система IBBE может быть построена с помощью функционального шифрования для . Чтобы зашифровать сообщение для получателя, множество , шифруется с помощью политики .

Точно так же, на основе идентификации отзыва (IBR) [10] для большинства n отзывов зашифрованный текст может быть преобразован в инвертированную IBBE, т.е., .

Пространственное шифрование

Напомним теперь понятие пространственной шифрования [9]. Для матрицы M элементы которой находятся в и вектор , определим соответствующую им размерность пространства как . Пусть является совокупностью всех размерностей пространств внутри . То есть,, где является множеством всех матриц в .

Понятие пространственного шифрования был мотивировано Боне и Гамбургом [9]. Оно имеет много приложений, как это в частности означает, схемы трансляции HIBE и схемы с множеством полномочий. Тем не менее, его связь с шифрованием внутреннего продукта не исследована до сих пор. В разделе 4.1, мы докажем, что пространственное шифрование предполагает шифрование внутреннего продукта, предоставляя простое отображение атрибута.

В результате самостоятельного интереса, мы также рассмотрим примитивное инвертированное пространственное шифрование (а именно, FE, которое определено с помощью и обеспечим конструкцию в разделе 5.1. Из этой схемы и Следствия 1 вместе с нашими выводами о результатах нулевого режима IPE из пространственного шифрования, мы получим конструкцию ненулевого режима IPE.

Функциональное шифрование нулевого внутреннего продукта

Разминка: Избирательно безопасный нулевой IPE пространственного шифрования

Сначала покажем, что пространственное шифрование подразумевает нулевую IPE. Для ключевого атрибута, обозначим to an - размерность пространства с матрицей


Для любого , затем мы имеем . Поэтому мы можем вывести ее значение с помощью вложения леммы.

В [9], Боне и Гамбург описали избирательно безопасную конструкцию пространственного шифрования, которая достигает шифротекстов постоянного размера (обобщая Boneh-Boyen-Goh HIBE [26]). Таким образом, мы сразу получаем избирательно безопасную схему IPE с шифротекстами постоянных размеров, как показано ниже.

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

Конструкция 2. (Избирательно безопасный нулевой IPE)
: выбирает билинейные группы простого порядка с генератором . Он выбирает .Пусть . Открытый ключ . Мастер ключ .
: выбирает и анализирует как и возвращает если . Выводит закрытый ключ как , где

.

: алгоритм шифрования сначала выбирает . Анализирует как и вычисляет шифротекст как

.

: алгоритм расшифрования вычисляет сообщение, ослепляющее такой фактор, как .


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

TemplateTheoremIcon.svg Теорема Теорема 1
Конструкция 2 является избирательно безопасной при n-Решение Билинейного предположения Диффи-Хеллмана (см. [9] для описания последнего).
Доказательство
Без доказательства.


Адаптивно безопасный нулевой IPE при простых моделях

Расширим вышеупомянутый выборочно безопасный нулевой IPE, чтобы приобрести адаптивную безопасность, применяя двойной системный метод Уотерса [19]. Однако, мы должны использовать технику “n-equation technique” противоположно технике с 2 уравнениями, используемой для IBE в [19]. Причина состоит в том, что мы имеем дело с трудностями, являющимися результатом более богатой структуры IPE и скопления шифротекстов в постоянном числе элементов, аналогично тому, что мы описали в разделе 1.

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

Конструкция 3.(Адаптивно безопасный нулевой IPE)
: выбирает билинейные группы простого порядка . Затем выбирает генераторы и выбирает . Пусть и . Открытый ключ состоит из

Мастер ключ определен для

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

: зашифровать , выбрать и вычислить , где


: вычисляет и затем , также как . Наконец восстанавливает исходный текст как .



Корректность показана в приложении A.1, , в то время как остальное следует из [19]. Как мы видим, у шифротекстов тот же самый размер как в схеме IBE [19], независимо от того, насколько большой вектор . Кроме того, расшифрование влечет за собой постоянное число объединенных оценок (в то время как шифротексты имеют сложность пар для расшифрования в [12]).

TemplateTheoremIcon.svg Теорема Теорема 2
Конструкция 3 адаптивно безопасна при DLIN и DBDH предположениях.
Доказательство
Доказательство использует методологию двойной системы, подобную [19], которая включает шифротексты и закрытые ключи, которые могут быть нормальными или полуфункциональными.
Полуфункциональные шифротексты генерируются первым вычислительным нормальным шифротекстом и затем выбирая прежде заменяя , соответственно, на

От нормального ключа , полуфункциональные ключи получаем, выбрав и заменив на


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

- реальная игра нападения, но проблема состоит в том, что шифротекст полуфункционален.

(для ) идентичен за исключением того, что на запросы первого i закрытого ключа поколения отвечают, возвращая полуфункциональный ключ.

такая же, как Game q, но проблема состоит в том, что шифротекст является полуфункциональным шифрованием случайного элемента из вместо актуального обычного текста.

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

Неразличимость и так же как и неразличимость и может быть доказана точно так же, как и в [19] а детали приведены в полной версии статьи.

TemplateLemmaIcon.svg Лемма «Лемма 1»
Если DLIN является трудной, неотличима от .


TemplateLemmaIcon.svg Лемма «Лемма 2»
Для любого , если противник может отличить от , мы можем создать отличительный признак для проблемы DLIN .


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

Чтобы решить это, мы используем секретный вектор показателя и вставляем образец DLIN так, чтобы мог моделировать только ключ в k-ом запросе с тегами и шифротекст вызова для с которые подчиняются отношению: , где является матрицей, определенной в Eq.(2). Мы, таким образом, здесь концептуально используем технику n-equation technique. В частности, следует, что если у нас есть тогда имеем, что


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

Proof. Отличительный признак получает aи решает, если .

Установка. Алгоритм выбирает и устанавливает

Далее, выбирает , затем определяет , и для . Отметим что, как и в доказательстве леммы 2 в [19] , знает .

Ключевые запросы. Когда создает j-ый запрос секретного ключа, делает следующее.

[В случае ] Генерирует нормальный ключ, с помощью секретного мастер-ключа .

[В случае ] Создает полуфункциональный ключ, который можно сделать с помощью .

[В случае ] Определяет как для ,

которое обозначает, что , для .

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

также как и для .

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

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

Мы утверждаем, что является полуфункциональным шифротекстом с основными показателями and . Чтобы доказать это, заметим, что

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


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

которая имеет решение в всякий раз, когда .

В итоге, выводит бит и выводит 0, если . Как и в [19], мы видим, что играет , если и в противном случае.

TemplateLemmaIcon.svg Лемма «Lemma 3»
Если DBDH - трудная, и неотличимы.


Функциональное шифрование ненулевого внутреннего продукта

Инвертированное пространственное шифрование

Мы начнем этот раздел, предоставляя совместно-избирательно безопасную конструкцию инвертированного пространственного шифрования, которое мотивировано его ненулевым значением IPE. На высоком уровне наша схема может рассматриваться как "инвертированный" аналог пространственного шифрования Боне и Гамбурга [9], также, как и схема отзыва Левко-Сахаи-Уотерса [10] является инвертированным аналогом Boneh-Boyen IBE [24]. TИнтуиция следует именно с раздела 1, где мы должны использовать технику "n-equation technique". В пространственном шифровании мы должны иметь дело, в целом, с тем, как мы можем создать систему из n уравнений аналогично Eq.(1). Для этого, ограничим векторные подпространства, которые мы можем использовать следующим образом. Наша конструкция является FE для , где мы определяем множество векторных подпространств в как , где обозначаем как матрицу, полученную путем удаления первой строки .

Конструкция 4. (Совместно-избирательно безопасное инвертированное пространственное шифрование)
: cвыбирает билинейную группу простого порядка со случайным генератором . Он случайным образом выбирает . Пусть . Открытый ключ . Мастер ключ .
: предположим, что , из матрицы . Алгоритм выбирает и выводит , где

.

: выбирает и вычисляет как

.

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

.


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

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

TemplateTheoremIcon.svg Теорема Теорема 3
Конструкция 4 является совместно-избирательно безопасной при q-мерном Мульти-Экспонентальном Билинейном предположении Диффи-Хеллмана (q - число ключевых запросов).
Доказательство
Доказательство приведено в полной статье, где предположение [10] также упомянуто.


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

Ненулевой IPE под простыми предположениями

Докажем совместно-избирательную безопасность нашей инвертированной схемы пространственного шифрования при нестандартном предположении q-типа, представленного в [12]. Здесь мы показываем, что метод двойной системы [19] озволяет опираться на простые предположения, такие как DBDH и DLIN. Схема очень похожа на схему нулевого IPE в разделе 4.2, и мы лишь утверждаем отличия. Интуиция снова следует точно из раздела 1, и доказательство безопасности использует похожие методы, как в [10].

Конструкция 5. (Совместно-избирательная безопасность ненулевого IPE)
: выводит pk в точности, как в конструкции 3 за исключением того, что мы определяем в этой схеме, вместо .
: выводит , где такой же, как в конструкции 3 (with и .
: выводит , где как в конструкции 3 (with ) и
: вычисляет как в конструкции 3 и как . (См. приложение A.2).


TemplateTheoremIcon.svg Теорема Теорема 4
Конструкция 5 является совместно-избирательно безопасной при DLIN и DBDH предположениях.
Доказательство
Доказательство откладывается до полной версии статьи.


Обобщение схемы и ее применение

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

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

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


Применения. Мы можем получить схему отзыва на основе идентификации с параметром tradeoff из вышеупомянутого расширения. Конкретизация схемы отзыва на основе идентификации из нашей ненулевой системы внутреннего продукта приводит к конструкции с -размером шифротекстов и -размером закрытых ключей, где n обозначает максимальное число отозванных пользователей. Из нашей расширенной схемы мы можем получить хему отзыва на основе идентификации , без фиксированного максимального числа отозванных пользователей. Чтобы отозвать множество , где , поделим его на несвязное объединение , где для всех (предположим, что делит ). Затем построим вектор i из подмножества отзыва для каждого , таким же способом, как мы используем для создания экземпляра . Затем, наконец, шифруем, используя набор векторов . Свойства корректности и безопасности соблюдаются, поскольку . Конструкция имеет -размер шифротекстов и -размер закрытых ключей. Интересно отметить, что вторая схема, описанная Левко, Сахаи и Уотерсом [10] (которая, в действительности, вдохновила нашу) может быть рассмотрена как частный случай нашей схемы, где .


A Проверка корректности в расшифровании

A.1 Для ненулевой схемы IPE из раздела 4.2