Модель родовой группы [1] [2] является идеализированной криптографической моделью, где противник только получают доступ к случайно выбранной кодировке в группе , а не эффективное кодирование, такие , как те , которые используются в конечной области или эллиптических группами кривых используются на практике.
Модель включает оракула, который выполняет групповую операцию . Этот оракул принимает на вход две кодировки элементов группы и выводит кодировку третьего элемента. Если группа должна разрешить операцию сопряжения, эта операция будет моделироваться как дополнительный оракул.
Одно из основных применений общей групповой модели - анализ предположений о вычислительной сложности . Анализ в общей групповой модели может ответить на вопрос: «Каков самый быстрый универсальный алгоритм для нарушения предположения о криптографической стойкости». Общий алгоритм - это алгоритм, который использует только групповую операцию и не учитывает кодирование группы. Ответ на этот вопрос для задачи дискретного логарифмирования был дан Виктором Шоупом с использованием общей групповой модели. [1] Например, другие результаты в модели общей группы. [3] Модель также может быть расширена на другие алгебраические структуры, такие как кольца . [4]
Общая групповая модель страдает некоторыми из тех же проблем, что и модель случайного оракула . В частности, было показано [5] с использованием аналогичного аргумента [6], что существуют криптографические схемы, которые доказуемо безопасны в модели общей группы, но которые тривиально становятся небезопасными после того, как случайное групповое кодирование заменено эффективно вычисляемым экземпляром функция кодирования.
Рекомендации
- ^ a b Виктор Шуп (1997). «Нижние оценки дискретных логарифмов и смежных задач» (PDF) . Конспект лекций по информатике . Достижения в криптологии - Eurocrypt '97. 1233 . Springer-Verlag. С. 256–266 . Проверено 9 апреля 2010 .
- ^ Ули Маурер (2005). «Абстрактные модели вычислений в криптографии» (PDF) . Конспект лекций по информатике . 10-я конференция IMA по криптографии и кодированию. 2796 . Springer-Verlag. С. 1–12 . Проверено 1 ноября 2007 .
- ^ Ули М. Маурер, Стефан Вольф: нижние границы общих алгоритмов в группах. ЕВРОКРИПТ 1998: 72-84
- ^ Дивеш Аггарвал, Ули Маурер: Взлом RSA в целом эквивалентен факторингу. EUROCRYPT 2009: 36-53
- ^ Александр В. Дент: Адаптация слабых сторон модели случайного оракула к модели общей группы. ASIACRYPT 2002: 100-109
- ↑ Ран Канетти, Одед Голдрайх и Шай Халеви, Повторение методологии случайного оракула, STOC 1998, стр. 209–218 (PS и PDF) .