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

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

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

Алгоритм

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

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

1. Случайным образом и независимо друг от друга выбираем два больших простых числа p и q так , чтобы . Это свойство обеспечивается, если оба простых числа имеют одинаковую длину.${\ Displaystyle \ НОД (pq, (p-1) (q-1)) = 1}$
2. Вычислить и . lcm означает наименьшее общее кратное.${\ 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 \ му = (L (г ^ {\ лямбда} {\ bmod {п}} ^ {2})) ^ {- 1} {\ bmod {п}}}$

где функция определяется как . ${\ 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 (п, г)}$
• Секретный ключ (дешифрования) ${\ displaystyle (\ lambda, \ mu).}$

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

Шифрование

1. Пусть будет сообщение, которое нужно зашифровать, где${\ displaystyle m}$${\ Displaystyle 0 \ Leq м <п}$
2. Выберите случайное , где и (т.е. обеспечить )${\ displaystyle r}$${\ Displaystyle 0 <г <п}$${\ displaystyle r \ in \ mathbb {Z} _ {n} ^ {*}}$${\ Displaystyle НОД (г, п) = 1}$
3. Вычислить зашифрованный текст как: ${\ Displaystyle с = г ^ {м} \ CDOT г ^ {п} {\ bmod {п}} ^ {2}}$

Расшифровка

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

Как указывается в исходной статье , дешифрование - это «по существу одно возведение в степень по модулю ». ${\ Displaystyle п ^ {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 {старшие степени}} n}$

Это означает, что:

${\ Displaystyle (1 + п) ^ {х} \ эквив 1 + nx {\ pmod {п ^ {2}}}}$

Следовательно, если:

${\ Displaystyle у = (1 + п) ^ {х} {\ bmod {п}} ^ {2}}$

тогда

${\ Displaystyle х \ экв {\ гидроразрыва {у-1} {п}} {\ pmod {п ^ {2}}}}$.

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

${\ Displaystyle L ((1 + п) ^ {х} {\ bmod {n}} ^ {2}) \ Equiv x {\ pmod {n}}}$,

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

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

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

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

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

Приложения

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

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

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

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

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

• Наккаш Штерн криптосистемы и криптосистемы Окамото-Учияма являются историческими предшественниками Paillier.
• Криптосистема Damgård-Jurik является обобщением Paillier.

использованная литература