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

Криптосистема Пэйе — вероятностная криптосистема с открытым ключом, изобретенная французским криптографом Паскалем Пэйе (англ. Pascal Paillier) в 1999 году. Аналогично криптосистемам RSA, Гольдвассер — Микали и Рабина, криптосистема Пэйе основана на сложности факторизации составного числа, являющегося произведением двух простых чисел.

Схема является аддитивной гомоморфной криптосистемой, то есть зная только открытый ключ и шифротексты, соответствующие открытым текстам [math]\displaystyle{ m_1 }[/math] и [math]\displaystyle{ m_2 }[/math], мы можем вычислить шифротекст открытого текста [math]\displaystyle{ m_1+m_2 }[/math].

История

Алгоритм был впервые предложен Паскалем Пэйе в его статье в 1999 году. В работе было описано предположение о сложности вычисления корня остатка от деления по модулю и предложен соответствующий механизм использования этой математической проблемы в криптографических целях. В оригинальной статье отмечается, что криптосистема может быть уязвима для атак на основе подобранного шифротекста, однако уже в 2001 году было показано, что при небольшом изменении оригинальной схемы криптосистема перестает быть уязвимой для такого рода атак. В 2006 году был предложен метод увеличения эффективности и безопасности криптосистемы Пэйе, основанный на верифицируемых перестановках.

Описание алгоритма

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

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

1. Выбираются два больших простых числа [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math], такие, что [math]\displaystyle{ \gcd(pq, (p-1)(q-1))=1 }[/math].
2. Вычисляется [math]\displaystyle{ n=pq }[/math] и [math]\displaystyle{ \lambda=\operatorname{lcm}(p-1,q-1) }[/math].
3. Выбирается случайное целое число [math]\displaystyle{ g }[/math], такое что [math]\displaystyle{ g\in \mathbb Z^{*}_{n^{2}} }[/math]
4. Вычисляется [math]\displaystyle{ \mu = (L(g^{\lambda}\mod n^{2}))^{-1} \bmod n }[/math], где [math]\displaystyle{ L(u) = div(\frac{u-1}{n}) }[/math].

• Открытым ключом является пара [math]\displaystyle{ (n, g) }[/math].
• Закрытым ключом является пара [math]\displaystyle{ (\lambda, \mu). }[/math]

Шифрование

1. Предположим, что необходимо зашифровать открытый текст [math]\displaystyle{ m }[/math], [math]\displaystyle{ m\in \mathbb Z_{n} }[/math]
2. Выбираем случайное число [math]\displaystyle{ r }[/math], [math]\displaystyle{ r\in \mathbb Z^{*}_{n} }[/math]
3. Вычисляем шифротекст [math]\displaystyle{ c=g^m \cdot r^n \bmod n^2 }[/math]

Расшифрование

1. Принимаем шифротекст [math]\displaystyle{ c\in \mathbb Z^{*}_{n^{2}} }[/math]
2. Вычисляем исходное сообщение [math]\displaystyle{ m = L(c^{\lambda} \bmod n^{2}) \cdot \mu \bmod n }[/math]

Электронная подпись

Для работы в режиме электронной подписи требуется наличие хеш-функции [math]\displaystyle{ h : \mathbb N \mapsto \{0,1\}^k \subset \mathbb Z^{*}_{n^{2}} }[/math].

• Подпись сообщения

Для того, чтобы подписать сообщение [math]\displaystyle{ m }[/math], необходимо вычислить

[math]\displaystyle{ s_1 = \frac{L(h(m)^\lambda \bmod n^2)} {L(g^\lambda \bmod n^2)} \bmod n }[/math]

[math]\displaystyle{ s_2 = (h(m)g^{-s_1})^{\frac{1}{n} \bmod \lambda} \bmod n }[/math]

Электронной подписью будет пара [math]\displaystyle{ (s_1,s_2) }[/math].

• Проверка подписи

Подпись считается верной, если выполнено следующее условие:

[math]\displaystyle{ h(m) = g^{s_1}s^n_2 \bmod n^2 }[/math].

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

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

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

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

[math]\displaystyle{ D(E(m_1, r_1)\cdot E(m_2, r_2)\bmod n^2) = m_1 + m_2 \bmod n. }[/math]

Умножив шифротекст на [math]\displaystyle{ g^{m_2} }[/math] мы получим сумму соответствующих открытых текстов,

[math]\displaystyle{ D(E(m_1, r_1)\cdot g^{m_2} \bmod n^2) = m_1 + m_2 \bmod n. }[/math]

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

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

[math]\displaystyle{ D(E(m_1, r_1)^{m_2}\bmod n^2) = m_1 m_2 \bmod n, }[/math]

[math]\displaystyle{ D(E(m_2, r_2)^{m_1}\bmod n^2) = m_1 m_2 \bmod n. }[/math]

В общем случае, возведение шифротекста в степень [math]\displaystyle{ k }[/math], будет расшифровано как произведение исходного текста на [math]\displaystyle{ k }[/math],

[math]\displaystyle{ D(E(m_1, r_1)^k\bmod n^2) = k m_1 \bmod n. }[/math]

Обобщение

В 2001 году Иван Дамгард и Мадс Юрик предложили обобщение криптосистемы Пэйе. Для этого предлагается вести вычисления по модулю [math]\displaystyle{ n^{s+1} }[/math], где [math]\displaystyle{ n = p * q }[/math], [math]\displaystyle{ s }[/math] - натуральное число. Измененный алгоритм выглядит следующим образом:

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

1. Случайно и независимо друг от друга выбираются два больших простых числа [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math].
2. Вычисляется [math]\displaystyle{ n=pq }[/math] и [math]\displaystyle{ \lambda=\operatorname{lcm}(p-1,q-1) }[/math].
3. Выбирается число [math]\displaystyle{ g \in \mathbb{Z}^*_{n^{s+1}} }[/math] , такое, что [math]\displaystyle{ g=(1+n)^j x \bmod n^{s+1} }[/math], где [math]\displaystyle{ j }[/math] известное взаимно простое число с [math]\displaystyle{ n }[/math] и [math]\displaystyle{ x \in H }[/math].
4. Используя китайскую теорему об остатках, выбирается [math]\displaystyle{ d }[/math] такое, что [math]\displaystyle{ d \bmod n \in \mathbb{Z}^*_n }[/math] и [math]\displaystyle{ d= 0 \bmod \lambda }[/math]. Например, [math]\displaystyle{ d }[/math] может быть равен [math]\displaystyle{ \lambda }[/math] из оригинальной криптосистемы Пэйе.

• Открытым ключом является пара [math]\displaystyle{ (n, g) }[/math].
• Закрытым ключом является [math]\displaystyle{ d }[/math].

Шифрование

1. Допустим мы хотим зашифровать сообщение [math]\displaystyle{ m }[/math], где [math]\displaystyle{ m\in \mathbb Z_{n^s} }[/math].
2. Выбираем случайное число [math]\displaystyle{ r }[/math] такое, что [math]\displaystyle{ r\in \mathbb Z^{*}_{n^{s+1}} }[/math].
3. Вычисляем шифротекст [math]\displaystyle{ c=g^m \cdot r^{n^s} \bmod n^{s+1} }[/math].

Расшифрование

1. Пусть у нас есть шифротекст [math]\displaystyle{ c\in \mathbb Z^{*}_{n^{s+1}} }[/math] и мы хотим его расшифровать.
2. Вычисляем [math]\displaystyle{ c^d \;mod\;n^{s+1} }[/math]. Если [math]\displaystyle{ c }[/math] действительно является шифротекстом, то выполнены равенства: [math]\displaystyle{ c^d = (g^m r^{n^s})^d = ((1+n)^{jm}x^m r^{n^s})^d = (1+n)^{jmd \;bmod\; n^s} (x^m r^{n^s})^{d \;bmod\; \lambda} = (1+n)^{jmd \;bmod\; n^s} }[/math].
3. Применяем рекурсивную версию механизма расшифрования криптосистемы Пэйе для получения [math]\displaystyle{ jmd }[/math]. Так как произведение [math]\displaystyle{ jd }[/math] известно, мы можем вычислить [math]\displaystyle{ m=(jmd)\cdot (jd)^{-1} \;bmod\;n^s }[/math].

Применение

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

Используя криптосистему Пэйе можно организовать выборы между несколькими кандидатами, используя следующую схему:

1. Пусть [math]\displaystyle{ N }[/math] — число избирателей и [math]\displaystyle{ k \in \mathbb N }[/math] такое, что [math]\displaystyle{ N \lt 2^k }[/math].
2. Если избиратель хочет проголосовать за кандидата номер [math]\displaystyle{ i }[/math], то он шифрует число [math]\displaystyle{ 2^{k(i-1)} }[/math] и передает полученный шифротекст координатору выборов.
3. При подведении итогов выборов координатор дешифрует произведение всех шифротекстов, полученных от избирателей. Несложно заметить, что первые [math]\displaystyle{ k }[/math] бит результата будут давать число голосов, отданных за первого кандидата, вторые [math]\displaystyle{ k }[/math] бит будут давать число голосов, отданных за второго кандидата, и так далее.

Электронная лотерея

При помощи криптосистемы Пэйе можно организовать проведение электронной лотереи следующим образом:

1. Пусть [math]\displaystyle{ N }[/math] игроков хотят поучаствовать в лотерее, каждый имеет свой лотерейный билет с уникальным номером [math]\displaystyle{ n \in \{ 0, \dots ,N-1 \} }[/math].
2. Каждый игрок выбирает случайное число, шифрует и передает организатору лотереи.
3. Для того чтобы вычислить «счастливый» билет, организатор дешифрует произведение всех полученных шифротекстов, получая при этом сумму [math]\displaystyle{ s }[/math] случайных чисел, сгенерированных игроками. Организатор лотереи объявляет победителем билет с номером [math]\displaystyle{ s\bmod n }[/math].

Несложно заметить, что у всех участников вероятности выигрыша будут равны даже если [math]\displaystyle{ n-1 }[/math] игроков попытаются сфальсифицировать итог лотереи, отправив организатору заранее подготовленные числа.

Электронная валюта

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

Литература

• Paillier P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes (англ.) // Advances in cryptology, EUROCRYPT'99. — 1999. — P. 223-238. — ISBN 978-3-540-48910-8. — doi:10.1007/3-540-48910-X_16. Архивировано 17 декабря 2014 года.

• Fouque P.-A., Poupard G., Stern J. Sharing Decryption in the Context of Voting or Lotteries (англ.) // Financial Cryptography, Proceedings of 4th International Conference. — 2001. — P. 90-104. — ISBN 978-3-540-45472-4. — doi:10.1007/3-540-45472-1_7.

• Jurik M. J. Extensions to the paillier cryptosystem with applications to cryptological protocols (англ.) // Public Key Cryptography. — 2003. — P. 119-136.

• Jurik M., Damgård I. A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System (англ.) // Proceedings of 4th International Workshop on Practice and Theory in Public Key Cryptosystems. — 2001. — P. 119-136.

• Варновский Н. П., Шокуров А. В. Гомоморфное шифрование (рус.) // Труды ИСП РАН. — 2007. — С. 27-36.

• Katz J., Lindell Y. Introduction to Modern Cryptography: Principles and Protocols. — Chapman & Hall/CRC, 2007. — С. 385-395. — ISBN 978-1584885511.

Ссылки

• The Homomorphic Encryption Project: реализация криптосистемы Пэйе с гомоморфными свойствами.
• Encounter: библиотека с открытым исходным кодом, реализующая криптосистему Пэйе и криптографические счетчики, основанные на ней.
• Интерактивная демонстрация криптосистемы Пэйе.
• Интерактивный симулятор криптосистемы Пэйе, показывающий её применение в системах электронного голосования.
• Видео, посвященное применению криптографических методов при голосовании.
• Интерактивный симулятор обобщенной криптосистемы Пэйе, показывающий её применение в системах электронного голосования.