Решение Линейное предположение - Decision Linear assumption

В Допущение линейного решения (DLIN) это предположение о вычислительной сложности используется в криптография на основе эллиптических кривых. В частности, допущение DLIN полезно в условиях, когда решающее предположение Диффи – Хеллмана не выполняется (как это часто бывает в криптография на основе пар ). Предположение о линейном решении было введено Boneh, Бойен и Шахам.[1]

Неформально предположение DLIN утверждает, что данное , с случайные элементы группы и случайные показатели, трудно различить из независимого элемента случайной группы .

Мотивация

В симметричном криптография на основе пар группа оснащен сопряжением который билинейный. Эта карта дает эффективный алгоритм для решения решающий Диффи-Хеллмана проблема. [2] Данный ввод , легко проверить, если равно . Это следует с помощью спаривания: обратите внимание, что

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

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

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

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

Позволять быть еще одним равномерно случайным элементом . Определите другое распределение

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

Приложения

Линейное шифрование

Бонех, Бойен и Шахам определяют шифрование с открытым ключом Схема по аналогии с шифрованием ЭльГамаля.[1] В этой схеме открытый ключ - это генераторы . Закрытый ключ - это два показателя степени, такие что . Шифрование объединяет сообщение с открытым ключом для создания зашифрованного текста

.

Чтобы расшифровать зашифрованный текст, закрытый ключ может использоваться для вычисления

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

Затем, используя тот факт, что дает

Далее эта схема IND-CPA безопасный предполагая, что предположение DLIN выполнено.

Короткие групповые подписи

Бонех, Бойен и Шахам также используют DLIN в схеме для групповые подписи. [1] Подписи называются «короткими групповыми подписями», потому что со стандартным уровень безопасности, их можно представить всего в 250 байты.

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

Их доказательство опирается не только на предположение DLIN, но и на другое предположение, называемое -сильное предположение Диффи-Хеллмана. Это доказано в случайная модель оракула.

Другие приложения

С момента своего определения в 2004 г. допущение линейного принятия решений нашло множество других применений. К ним относятся строительство псевдослучайная функция это обобщает Конструкция Наора-Рейнгольда, [3] ан шифрование на основе атрибутов схема, [4] и особый класс неинтерактивные доказательства с нулевым разглашением. [5]

Рекомендации

  1. ^ а б c Дэн Бонех, Ксавье Бойен, Ховав Шахам: Короткие групповые подписи. КРИПТО 2004: 41–55
  2. ^ Джон Бетенкур: Введение в билинейные карты
  3. ^ Эллисон Бишоп Левко, Брент Уотерс: Эффективные псевдослучайные функции из линейного решения и более слабые варианты. CCS 2009: 112-120
  4. ^ Лукас Ковальчик, Епископ Эллисон Левко: Билинейное разложение энтропии из решающего линейного предположения. КРИПТО 2015: 524-541
  5. ^ Бенуа Либер, Томас Петерс, Марк Джой, Моти Юнг: Компактное скрытие линейных пролетов. ASIACRYPT 2015: 681-707