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

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

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

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

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

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

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

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

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

Пусть будет другим равномерно случайным элементом . Определим другое распределение${\displaystyle \эта}$${\displaystyle G}$

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

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

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

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

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

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

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

${\displaystyle 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}.}$

Тогда, используя тот факт, что дает${\displaystyle u^{x}=v^{y}=h}$

${\displaystyle 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 в схеме для групповых подписей . ^[1] Подписи называются «короткими групповыми подписями», поскольку при стандартном уровне безопасности они могут быть представлены всего в 250 байтах .

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

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

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