Решение Линейное предположение

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

Неформально предположение DLIN гласит, что с учетом $(u,\,v,\,h,\,u^{x},\,v^{y})$, с $u,\,v,\,h$ элементы случайной группы и $x,\,y$ случайные показатели, трудно отличить $h^{x+y}$ из независимого случайного элемента группы $\eta$.

Мотивация

В криптографии на основе симметричных пар группа $G$ оснащен сопряжением $e:G\times G\to T$ что является билинейным . Эта карта дает эффективный алгоритм для решения решающей проблемы Диффи-Хеллмана . Учитывая ввод $(g,\,g^{a},\,g^{b},\,h)$, легко проверить, если $h$ равно $g^{ab}$. Это следует с помощью спаривания: обратите внимание, что

$e(g^{a},g^{b})=e(g,g)^{ab}=e(g,g^{ab}).$

Таким образом, если $h=g^{ab}$, то значения $e(g^{a},g^{b})$ и $e(g,h)$ будет равен.

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

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

Позволять $G$ — группа простого порядка циклическая $p$. Позволять $u$, $v$, и $h$ быть равномерно генераторами случайными $G$. Позволять $a,b$ быть равномерно случайными элементами $\{1,\,2,\,\dots ,\,p-1\}$. Определить распределение

$D_{1}=(u,\,v,\,h,\,u^{a},\,v^{b},\,h^{a+b}).$

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

$D_{2}=(u,\,v,\,h,\,u^{a},\,v^{b},\,\eta ).$

Предположение линейного решения утверждает, что $D_{1}$ и $D_{2}$ неотличимы вычислительно .

Приложения

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

Бонех, Бойен и Шахам определяют схему шифрования с открытым ключом по аналогии с шифрованием Эль-Гамаля. В этой схеме открытым ключом являются генераторы $u,v,h$. Закрытый ключ имеет две степени, такие что $u^{x}=v^{y}=h$. Шифрование объединяет сообщение $m\in G$ с открытым ключом для создания зашифрованного текста

$c:=(c_{1},\,c_{2},\,c_{3})=(u^{a},\,v^{b},\,m\cdot h^{a+b})$.

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

$m':=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}.$

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

$m'=c_{3}\cdot (c_{1}^{x}\cdot c_{2}^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{a})^{x}\cdot (v^{b})^{y})^{-1}=m\cdot h^{a+b}\cdot ((u^{x})^{a}\cdot (v^{y})^{b})^{-1}.$

Затем, используя тот факт, что $u^{x}=v^{y}=h$ урожайность

$m'=m\cdot h^{a+b}\cdot (h^{a}\cdot h^{b})^{-1}=m\cdot (h^{a+b}\cdot h^{-a-b})=m.$

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

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

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

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

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

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

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