Криптосистема Пайе

Алгоритм криптографии с открытым ключом

Криптосистема Пайе , изобретенная и названная в честь Паскаля Пайе в 1999 году, является вероятностным асимметричным алгоритмом для криптографии с открытым ключом . Считается, что проблема вычисления n -ных классов остатков является вычислительно сложной. Предположение о составной остаточности принятия решений является гипотезой неразрешимости , на которой основана эта криптосистема.

Схема представляет собой аддитивную гомоморфную криптосистему ; это означает, что, имея только открытый ключ и шифрование и , можно вычислить шифрование . ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle m_{1}+m_{2}}$

Алгоритм

Схема работает следующим образом:

Генерация ключей

1. Выбираем два больших простых числа и случайно и независимо друг от друга так, что . Это свойство обеспечивается, если оба простых числа имеют одинаковую длину. ^[1] ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \gcd(pq,(p-1)(q-1))=1}$
2. Вычислите и . НОК означает наименьшее общее кратное . ${\displaystyle n=pq}$ ${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)}$
3. Выберите случайное целое число , где ${\displaystyle g}$ ${\displaystyle g\in \mathbb {Z} _{n^{2}}^{*}}$
4. Убедитесь, что порядок делится путем проверки существования следующего модульного мультипликативного обратного числа : , ${\displaystyle n}$ ${\displaystyle g}$ ${\displaystyle \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}}$

где функция определяется как . ${\displaystyle L}$ ${\displaystyle L(x)={\frac {x-1}{n}}}$

Обратите внимание, что эта запись обозначает не модульное умножение на модульное мультипликативное обратное число , а скорее частное от деления на , т. е. наибольшее целое значение, удовлетворяющее соотношению . ${\displaystyle {\frac {a}{b}}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle v\geq 0}$ ${\displaystyle a\geq vb}$

• Открытый (шифровальный) ключ — . ${\displaystyle (n,g)}$
• Закрытый (расшифровочный) ключ — это ${\displaystyle (\lambda ,\mu ).}$

При использовании p,q эквивалентной длины более простым вариантом вышеприведенных шагов генерации ключа будет установка и , где . ^[1] Более простой вариант рекомендуется для целей реализации, поскольку в общем виде время вычисления может быть очень большим при достаточно больших простых числах p,q. ${\displaystyle g=n+1,\lambda =\varphi (n),}$ ${\displaystyle \mu =\varphi (n)^{-1}{\bmod {n}}}$ ${\displaystyle \varphi (n)=(p-1)(q-1)}$ ${\displaystyle \mu }$

Шифрование

1. Пусть будет сообщение, которое нужно зашифровать, где ${\displaystyle m}$ ${\displaystyle 0\leq m<n}$
2. Выберите случайным образом , где и . (Примечание: если вы найдете значение, которое имеет , вы можете использовать его для вычисления закрытого ключа: это вряд ли можно проигнорировать.) ${\displaystyle r}$ ${\displaystyle 0<r<n}$ ${\displaystyle \gcd(r,n)=1}$
   ${\displaystyle \gcd(r,n)\neq 1}$
3. Вычислить шифротекст как: ${\displaystyle c=g^{m}\cdot r^{n}{\bmod {n}}^{2}}$

Расшифровка

1. Пусть будет зашифрованным текстом для расшифровки, где ${\displaystyle c}$ ${\displaystyle c\in \mathbb {Z} _{n^{2}}^{*}}$
2. Вычислите текстовое сообщение следующим образом: ${\displaystyle m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}}$

Как отмечается в оригинальной статье ^[2] , расшифровка — это «по сути одно возведение в степень по модулю ». ${\displaystyle n^{2}}$

Гомоморфные свойства

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

• Гомоморфное сложение открытых текстов

Произведение двух шифртекстов расшифруется в сумму соответствующих им открытых текстов,

${\displaystyle D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,}$

Произведение зашифрованного текста с открытым текстом расшифровывается как сумма соответствующих открытых текстов, ${\displaystyle g}$

${\displaystyle D(E(m_{1},r_{1})\cdot g^{m_{2}}{\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,}$

• Гомоморфное умножение открытых текстов

Зашифрованный текст, возведенный в степень открытого текста, будет расшифрован в произведение двух открытых текстов,

${\displaystyle D(E(m_{1},r_{1})^{m_{2}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}},\,}$

${\displaystyle D(E(m_{2},r_{2})^{m_{1}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}}.\,}$

В более общем случае, зашифрованный текст, увеличенный до константы k, будет расшифрован в произведение открытого текста и константы,

${\displaystyle D(E(m_{1},r_{1})^{k}{\bmod {n}}^{2})=km_{1}{\bmod {n}}.\,}$

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

Фон

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

Например, по биномиальной теореме ,

${\displaystyle (1+n)^{x}=\sum _{k=0}^{x}{x \choose k}n^{k}=1+nx+{x \choose 2}n^{2}+{\text{higher powers of }}n}$

Это указывает на то, что:

${\displaystyle (1+n)^{x}\equiv 1+nx{\pmod {n^{2}}}}$

Поэтому, если:

${\displaystyle y=(1+n)^{x}{\bmod {n}}^{2}}$

затем

${\displaystyle x\equiv {\frac {y-1}{n}}{\pmod {n}}}$.

Таким образом:

${\displaystyle L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}}$,

где функция определяется как (частное от целочисленного деления) и . ${\displaystyle L}$ ${\displaystyle L(u)={\frac {u-1}{n}}}$ ${\displaystyle x\in \mathbb {Z} _{n}}$

Семантическая безопасность

Исходная криптосистема, показанная выше, обеспечивает семантическую безопасность от атак с выбранным открытым текстом ( IND-CPA ). Способность успешно различать шифртекст вызова по сути сводится к способности определять составную остаточность. Так называемое предположение о решающей составной остаточности (DCRA) считается неразрешимым.

Однако из-за вышеупомянутых гомоморфных свойств система является пластичной и, следовательно, не обладает наивысшим уровнем семантической безопасности, защитой от адаптивных атак с выбранным шифротекстом ( IND-CCA2 ). Обычно в криптографии понятие пластичности не рассматривается как «преимущество», но в некоторых приложениях, таких как безопасное электронное голосование и пороговые криптосистемы , это свойство действительно может быть необходимым.

Однако Пайе и Пуаншеваль предложили усовершенствованную криптосистему, которая включает в себя комбинированное хеширование сообщения m со случайным r . Подобное по своему назначению криптосистеме Крамера-Шоупа , хеширование не позволяет злоумышленнику, которому дано только c, изменить m осмысленным образом. Благодаря этой адаптации можно показать, что усовершенствованная схема является безопасной по стандарту IND-CCA2 в модели случайного оракула .

Приложения

Электронное голосование

Семантическая безопасность — не единственное соображение. Существуют ситуации, в которых пластичность может быть желательной. Защищенные электронные системы голосования могут использовать указанные выше гомоморфные свойства. Рассмотрим простой двоичный голос («за» или «против»). Пусть m избирателей отдают голоса либо 1 (за), либо 0 (против). Каждый избиратель шифрует свой выбор перед тем, как отдать свой голос. Сотрудник избирательной комиссии берет произведение m зашифрованных голосов, а затем расшифровывает результат и получает значение n , которое является суммой всех голосов. Затем сотрудник избирательной комиссии знает, что n человек проголосовали за и mn человек проголосовали против . Роль случайного r гарантирует, что два эквивалентных голоса будут зашифрованы в одно и то же значение только с незначительной вероятностью, тем самым обеспечивая конфиденциальность избирателей.

Электронные деньги

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

Электронный аукцион

Криптосистема Paillier играет решающую роль в повышении безопасности электронных аукционов . Она предотвращает мошеннические действия, такие как нечестные аукционисты и сговор между участниками торгов и аукционистами, которые манипулируют ставками. Обеспечивая конфиденциальность фактических значений ставок и раскрывая результаты аукционов, криптосистема Pailler успешно продвигает честную практику. ^[3]

Пороговая криптосистема

Гомоморфное свойство криптосистемы Пайе иногда используется для построения пороговой подписи ECDSA. ^[4]

Смотрите также

• Криптосистема Наккаш -Стерна и криптосистема Окамото-Утиямы являются историческими предшественниками Пайе.
• Криптосистема Дамгарда –Юрика является обобщением криптосистемы Пайе.

Ссылки

• Пайе, Паскаль (1999). "Криптосистемы с открытым ключом на основе классов остаточной криптографии составной степени" (PDF) . Достижения в криптологии – EUROCRYPT '99. EUROCRYPT . Springer. doi :10.1007/3-540-48910-X_16.
• Пайе, Паскаль; Пуаншеваль, Дэвид (1999). «Эффективные криптосистемы с открытым ключом, доказуемо защищенные от активных злоумышленников». ASIACRYPT . Springer. стр. 165–179. doi : 10.1007/978-3-540-48000-6_14 .
• Пайе, Паскаль (1999). Криптосистемы на основе составной невязкости (кандидатская диссертация). Высшая национальная школа телекоммуникаций.
• Пайе, Паскаль (2002). "Криптография на основе композитных остатков: обзор" (PDF) . CryptoBytes . 5 (1). Архивировано из оригинала (PDF) 20 октября 2006 г.

Примечания

1. Джонатан Кац, Иегуда Линделл, «Введение в современную криптографию: принципы и протоколы», Chapman & Hall/CRC, 2007
2. Paillier, Pascal (1999). "Криптосистемы с открытым ключом, основанные на классах остаточной криптографии составной степени". Advances in Cryptology — EUROCRYPT '99 . Lecture Notes in Computer Science. Vol. 1592. Springer. pp. 223–238. doi : 10.1007/3-540-48910-X_16 . ISBN 978-3-540-65889-4.
3. Pan, M., Sun, J., & Fang, Y. (2011). Очищение закулисных сделок: безопасный аукцион спектра с использованием криптосистемы Paillier. Журнал IEEE по избранным областям в коммуникациях, 29(4), 866–876. https://doi.org/10.1109/JSAC.2011.110417
4. Канетти, Ран; Дженнаро, Росарио; Голдфедер, Стивен; Макрияннис, Николаос; Пелед, Уди (30 октября 2020 г.). «UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts». Труды конференции ACM SIGSAC 2020 года по безопасности компьютеров и коммуникаций . Ассоциация вычислительной техники. стр. 1769–1787. doi :10.1145/3372297.3423367. ISBN 9781450370899. S2CID  226228099.

Внешние ссылки

• Проект гомоморфного шифрования реализует криптосистему Пайе вместе с ее гомоморфными операциями.
• Encounter: библиотека с открытым исходным кодом, обеспечивающая реализацию криптосистемы Пайе и конструкцию криптографических счетчиков на ее основе.
• python-paillier — библиотека для частично гомоморфного шифрования на Python, включающая полную поддержку чисел с плавающей точкой.
• Интерактивный симулятор криптосистемы Пайе. Архивировано 18 февраля 2012 г. на Wayback Machine. Демонстрирует приложение для голосования.
• Интерактивная демонстрация криптосистемы Пайе.
• Реализация концепции криптосистемы Пайе на Javascript с интерактивной демонстрацией.
• Видеоролик GoogleTechTalk о голосовании с использованием криптографических методов.
• Реализация гомоморфного сложения Пайе и протокола доказательства с нулевым разглашением на Ruby (документация)