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

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

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

Алгоритм

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

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

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

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

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

• Открытый ключ (шифрования) — это $(n,g)$.
• Закрытый ключ (дешифрования) $(\lambda ,\mu ).$

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

Шифрование

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

Расшифровка

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

Как оригинальная бумага указывает, что расшифровка — это «по существу одно возведение в степень по модулю $n^{2}$."

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фон

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

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

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

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

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

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

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

затем

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

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

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

где функция $L$ определяется как $L(u)={\frac {u-1}{n}}$ (частное целочисленного деления) и $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 успешно способствует честной практике.

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

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

См. также

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

Ссылки

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

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

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