WikiDer > Криптосистема Бенало

Benaloh cryptosystem

В Криптосистема Бенало является продолжением Криптосистема Голдвассера-Микали (GM) создана в 1985 году Джошем (Коэном) Бенало. Основное улучшение криптосистемы Benaloh по сравнению с GM заключается в том, что более длинные блоки данных могут быть зашифрованы одновременно, тогда как в GM каждый бит шифруется индивидуально.[1][2][3]

Определение схемы

Как и многие криптосистемы с открытым ключом, эта схема работает в группе куда п это продукт двух больших простые числа. Эта схема гомоморфный и поэтому податливый.

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

Данный размер блока р, пара открытый / закрытый ключ создается следующим образом:

  1. Выберите большие простые числа п и q такой, что и
  2. Набор
  3. выбирать такой, что .
Примечание: Если р является составным, как указали Fousse et al. в 2011[4] что вышеуказанные условия (то есть те, которые указаны в исходной статье) недостаточны, чтобы гарантировать правильное дешифрование, то есть гарантировать, что во всех случаях (как и должно быть). Чтобы решить эту проблему, авторы предлагают следующую проверку: пусть быть простым разложением р. выбирать так что для каждого фактора , это тот случай, когда .
  1. Набор

Тогда открытый ключ , а закрытый ключ .

Шифрование сообщений

Чтобы зашифровать сообщение :

  1. Выберите случайный
  2. Набор

Расшифровка сообщения

Расшифровать зашифрованный текст :

  1. Вычислить
  2. Выход , т.е. найти м такой, что

Чтобы понять расшифровку, сначала обратите внимание, что для любого и у нас есть:

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

Безопасность

Безопасность этой схемы основана на Проблема более высокой остаточности, в частности, учитывая z,р и п где факторизация п неизвестно, вычислить невозможно, чтобы определить, z является рмод остатка п, т.е. если существует Икс такой, что .

Рекомендации

  1. ^ Коэн, Джош; Фишер, Майкл (1985). Надежная и проверяемая криптографически безопасная схема выборов (PDF). Материалы 26-го симпозиума IEEE по основам компьютерных наук. С. 372–382.
  2. ^ Бенало, Джош (1987). Поддающиеся проверке выборы тайным голосованием (кандидатская диссертация) (PDF).
  3. ^ Бенало, Джош (1994). Плотное вероятностное шифрование (PDF). Семинар по избранным направлениям криптографии. С. 120–128.
  4. ^ Фусс, Лоран; Лафуркад, Паскаль; Альнуайми, Мохамед (2011). «Возвращение к плотному вероятностному шифрованию Бенало». arXiv:1008.2991 [cs.CR].