Схема Гольдвассер — Микали

Схема Гольдвассер — Микали — это криптографическая система с открытым ключом, обладающая свойством семантической стойкости, то есть невозможности для противника, имеющего только шифротекст, получить какую-либо информацию об открытом тексте (кроме его длины). Разработана в 1982 году Шафи Гольдвассер и Сильвио Микали. Является одной из первых схем, для которых была строго доказана стойкость в рамках теоретико-сложностного подхода, основанная на вычислительной трудности задачи квадратичного вычета по модулю составного числа.

История

Схема была предложена в 1982 году в совместной работе Шафи Гольдвассер и Сильвио Микали «Probabilistic Encryption» (вероятностное шифрование). До этого момента большинство криптосистем с открытым ключом (например, RSA) были детерминированными: один и тот же открытый текст при шифровании одним и тем же ключом всегда давал один и тот же шифротекст. Это позволяло противнику проверять гипотезы об открытом тексте, сравнивая шифротексты, что нарушало семантическую стойкость.

Гольдвассер и Микали ввели понятие вероятностного шифрования, в котором процесс шифрования включает случайность, а также формально определили семантическую стойкость. Они доказали, что их схема семантически стойка при условии, что задача различения квадратичных вычетов по модулю составного числа (Quadratic Residuosity Problem, QRP) является вычислительно сложной. За эту работу в 2012 году Гольдвассер и Микали получили премию Тьюринга (совместно с Лесли Валиантом).

Математические основы

Стойкость схемы опирается на задачу квадратичного вычета (QRP). Пусть \( N = p \cdot q \), где \( p \) и \( q \) — два больших различных простых числа. Число \( a \), взаимно простое с \( N \), называется квадратичным вычетом по модулю \( N \), если существует такое целое \( x \), что \( x^2 \equiv a \pmod{N} \). В противном случае \( a \) называется квадратичным невычетом.

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

Схема использует свойство, что квадратичные вычеты по модулю \( N \) образуют мультипликативную группу, а произведение двух невычетов может быть вычетом. В частности, если \( y \) — фиксированный квадратичный невычет, то для любого вычета \( r \) произведение \( y \cdot r \) будет невычетом.

Описание схемы

Схема состоит из трёх алгоритмов: генерации ключей, шифрования и дешифрования.

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

1. Выбираются два больших различных простых числа \( p \) и \( q \) (например, длиной 512–1024 бита каждое).
2. Вычисляется модуль \( N = p \cdot q \).
3. Выбирается такое число \( y \in \mathbb{Z}_N^* \), что символ Якоби \( \left(\frac{y}{N}\right) = 1 \), но \( y \) является квадратичным невычетом по модулю \( N \). То есть \( y \) — псевдоквадрат.
4. Открытый ключ: \( (N, y) \).
5. Секретный ключ: \( (p, q) \).

Шифрование

Для шифрования одного бита \( b \in \{0, 1\} \):

1. Выбирается случайное число \( r \in \mathbb{Z}_N^* \) (равномерно).
2. Вычисляется шифротекст \( c \):

• Если \( b = 0 \), то \( c = r^2 \mod N \).
• Если \( b = 1 \), то \( c = y \cdot r^2 \mod N \).

1. Шифротекст \( c \) передаётся получателю.

Дешифрование

Для дешифрования одного бита из шифротекста \( c \):

1. Вычисляется, является ли \( c \) квадратичным вычетом по модулю \( N \). Для этого используется секретный ключ \( (p, q) \):

• Вычисляется символ Лежандра \( \left(\frac{c}{p}\right) \). Если \( \left(\frac{c}{p}\right) = 1 \), то \( c \) — вычет по модулю \( p \), иначе — невычет.
• Аналогично для \( q \). Если \( c \) — вычет по модулю \( p \) и по модулю \( q \), то \( c \) — квадратичный вычет по модулю \( N \).

1. Если \( c \) — квадратичный вычет, то \( b = 0 \). Если \( c \) — невычет, то \( b = 1 \).

Свойства

Семантическая стойкость

Схема является семантически стойкой (стойкой к атаке на основе выбранного открытого текста, IND-CPA) при условии, что задача QRP является вычислительно сложной. Противник, не знающий факторизации \( N \), не может отличить шифротекст, соответствующий биту 0, от шифротекста, соответствующего биту 1, с вероятностью, существенно большей 1/2.

Вероятностное шифрование

Одно и то же сообщение (один бит) при каждом шифровании даёт разные шифротексты из-за случайного выбора \( r \). Это предотвращает атаки по словарю.

Размер шифротекста

Шифротекст представляет собой число по модулю \( N \), то есть имеет размер порядка \( \log_2 N \) бит. Для шифрования одного бита открытого текста требуется \( O(\log N) \) бит шифротекста. Это приводит к значительному расширению данных (примерно в 1024 раз для 1024-битного модуля).

Скорость

Шифрование требует одного возведения в квадрат (или умножения на \( y \)) по модулю \( N \), что относительно быстро. Дешифрование требует вычисления символа Лежандра, что также эффективно при известной факторизации. Однако генерация ключа требует нахождения \( y \), что может быть вычислительно затратно.

Применение

Из-за большого расширения данных схема Гольдвассер — Микали редко используется для шифрования больших объёмов информации. Её основное применение — в теоретических криптографических конструкциях и протоколах, где требуется семантическая стойкость и возможность гомоморфных операций.

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

Схема обладает свойством гомоморфизма по XOR (сложение по модулю 2). Если \( c_1 \) — шифротекст бита \( b_1 \), а \( c_2 \) — шифротекст бита \( b_2 \), то произведение \( c_1 \cdot c_2 \mod N \) является шифротекстом бита \( b_1 \oplus b_2 \). Это свойство используется в протоколах голосования, электронных деньгах и других системах, где требуется вычисление на зашифрованных данных.

Криптографические протоколы

Схема используется в качестве строительного блока для:

• Протоколов передачи бита с забыванием (Oblivious Transfer).
• Доказательств с нулевым разглашением.
• Многосторонних вычислений.

Критика и ограничения

• Расширение данных: Как уже упоминалось, шифротекст в \( O(\log N) \) раз длиннее открытого текста. Для практического использования это неприемлемо.
• Вычислительная сложность: Хотя шифрование и дешифрование одного бита относительно быстры, для шифрования длинных сообщений (например, файла размером 1 МБ) потребуется выполнить миллионы операций, что делает схему неэффективной.
• Зависимость от QRP: Стойкость схемы напрямую зависит от сложности задачи QRP. Хотя эта задача считается сложной, её стойкость не доказана безусловно. В случае появления эффективного алгоритма решения QRP (например, с помощью квантового компьютера) схема станет небезопасной.
• Отсутствие аутентичности: Схема не обеспечивает аутентификацию сообщения или целостность шифротекста. Противник может модифицировать шифротекст, что приведёт к изменению расшифрованного бита.

Сравнение с другими схемами

• RSA: Детерминированная, не семантически стойкая без дополнительных модификаций (например, OAEP). Меньшее расширение данных.
• Эль-Гамаль: Вероятностная, семантически стойкая. Расширение данных в 2 раза (для одного элемента группы). Более эффективна для шифрования сообщений.
• Paillier: Гомоморфна по сложению, имеет меньшее расширение данных, чем Гольдвассер — Микали, и более эффективна.

Интересные факты

• Схема Гольдвассер — Микали стала первой криптосистемой, для которой была строго доказана семантическая стойкость в рамках теоретико-сложностной модели.
• В 1984 году Мануэль Блюм и Шафи Гольдвассер предложили улучшенную версию схемы, основанную на задаче факторизации, которая также является вероятностной.
• Схема используется в учебных целях для иллюстрации концепций вероятностного шифрования и гомоморфного шифрования.

Источники

1. Goldwasser, S., Micali, S. (1982). Probabilistic Encryption & How to Play Mental Poker Keeping Secret All Partial Information. Proceedings of the 14th Annual ACM Symposium on Theory of Computing.
2. Goldwasser, S., Micali, S. (1984). Probabilistic encryption. Journal of Computer and System Sciences, 28(2), 270–299.
3. Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
4. Katz, J., Lindell, Y. (2014). Introduction to Modern Cryptography (2nd ed.). CRC Press.
5. Стинсон, Д. Р. (2005). Криптография: теория и практика (2-е изд.).