Атака по шифртекстам на одну линейную полностью гомоморфную криптосистему

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

захстана, Сингапура, Украины. Более 280 участников — студенты, около 120 — школьники, остальные участники — любители криптографии и профессионалы.
Участникам олимпиады было предложено 15 задач. Математические задачи олимпиады посвящены вопросам исследования дифференциальных характеристик S-бло-ков- взаимосвязи простейших операций, использующихся для построения шифра: циклического сдвига и сложения по модулю 2k- построению специальных линейных подпространств в F^- поиску числа решений уравнения F (x) + F (x + a) = b над конечным полем F2n и APN-функциям. Были и игровые задачи, такие, как крипто-квест, дешифрование секретных сообщений, анализ музыкального шифра. Детально задачи и их решения обсуждаются в [1, 2]. При этом работа [2] содержит не только разбор всех задач, но и комментарии к решениям участников, организационные моменты олимпиады, списки призёров.
Победителями олимпиады стали участники из Новосибирска, Омска, Москвы, Санкт-Петербурга, Саратова, Минска (Беларусь) и Лёвена (Бельгия): 15 участников в первом туре и 11 команд-победительниц во втором туре. Награждение призёров состоялось в Новосибирском государственном университете в декабре.
NSUCRYPTO задумана как ежегодное мероприятие. В следующий раз она пройдёт в ноябре 2015 г. (см. www. nsucrypto. nsu. ru). Приглашаем всех желающих принять в ней участие! Например, участники конференции Sibecrypt могут выбрать категорию «любитель/профессионал».
ЛИТЕРАТУРА
1. Agievich S., Gorodilova A., Kolomeec N., Nikova S., et al. Mathematical problems of the First international student'-s Olympiad in cryptography NSUCRYPTO //IV Симпозиум «Современные тенденции в криптографии» CTCrypt'-15, Казань, 3−5 июня 2015 г.
2. Agievich S., Gorodilova A., Kolomeec N., Nikova S., et al. Problems, solutions and experience of the first international student'-s Olympiad in cryptography // Прикладная дискретная математика. 2015. № 3(29).
УДК 519. 95 DOI 10. 17 223/2226308X/8/28
АТАКА ПО ШИФРТЕКСТАМ НА ОДНУ ЛИНЕЙНУЮ ПОЛНОСТЬЮ ГОМОМОРФНУЮ КРИПТОСИСТЕМУ1
А. В. Трепачева
Описывается новая стратегия атаки по шифртекстам на одну линейную полностью гомоморфную криптосистему, чья защищённость обосновывается с привлечением сложности задачи факторизации больших чисел. Приводятся теоретические и практические оценки вероятности раскрытия секретного ключа с использованием данной атаки. Проводится анализ связи трудности факторизации чисел и защищённости криптосистемы против атаки по шифртекстам, на основе которого предлагается более эффективная модификация криптосистемы.
Ключевые слова: полностью гомоморфное шифрование, задача факторизации чисел, атака по шифртекстам.
Введение
В связи с распространением облачных сервисов задача построения полностью гомоморфных криптосистем (ПГК), позволяющих проводить произвольные вычисления
1 Работа поддержана грантом РФФИ № 15−07−597-a.
над данными в зашифрованном виде, приобрела большую актуальность. Основным направлением в данной области является построение ПГК, основанных на теории решёток и методике Джентри [1]. Однако существующие на данный момент ПГК этого типа обладают низкой вычислительной эффективностью и являются непригодными для практики [1]. Поэтому не прекращаются поиски альтернативного варианта ПГК, не использующей метод Джентри и являющейся эффективной и криптостойкой. В частности, активно предлагаются ПГК, основанные на задаче факторизации чисел. В данной работе анализируется одна недавно предложенная ПГК этого вида из [2]. Описывается атака по шифртекстам (АШ) на ПГК [2], основанная на решении системы линейных уравнений и не рассмотренная ранее в литературе. Приводятся оценки вероятности её успеха в зависимости от различных параметров.
1. Полностью гомоморфная криптосистема из [2] и её основные свойства
Опишем ПГК, предложенную в [2]. Для зашифрования открытого текста т Е Ъп составляется матрица Б = diag (m, г) €Пх2, где п = рд, р, д — простые числа, ^(р) = ^(д) ^ 512 (т.е. п трудно факторизовать), г € Ъп выбран по равномерному распределению, diag (m, г) -диагональная матрица с т, г на главной диагонали. Шифртекст вычисляется как С = К-1БК €Пх2, где К Е %ПХ2 — секретный ключ. Ясно, что т — собственное число С, имеющее собственный вектор = К-1 е1 Е где е1 = (1, 0). Для расшифрования вычисляется в = С1, а затем т = 51/^1,1. Описанная криптосистема — ПГК, так как в ней произведению и сумме шифртекстов соответствуют произведение и сумма открытых текстов. При этом операции над шифртекстами вычислительно эффективны (умножение и сложение матриц). Это делает данную ПГК очень интересной с практической точки зрения. Однако ПГК [2] совершенно нестойка к атаке по известным открытым текстам. По перехваченной паре (т, С) можно составить систему линейных уравнений (С — т/)х = 0, множество решений которой имеет базис с вероятностью ~ 1, и поэтому наличие даже одной пары (т, С) компрометирует [2]. Больше информации об атаке по известным открытым текстам на ПГК [2] можно найти в [3].
2. Атака по шифртекстам на ПГК [2]
Предположим, противник перехватил последовательность С ЕПх2, г = 1,… ,?, шифрующих mi Е г = 1,…, ?, на ключе К. Ясно, что т^ - корень характеристического полинома сЬагДж) Е 2п[х], составленного для С^ Так как п трудно факторизовать, нахождение корней сЬагДж) в общем случае трудно. Этим свойством в [2] и обосновывается защищённость ПГК. Однако на самом деле это работает, только если вероятностное распределение О, заданное на пространстве открытых текстов Р = Zn, является близким к равномерному. Если же, к примеру, О таково, что P{mi & gt- л/П} = 0, то, согласно [3], т^ можно найти из сЬагДж).
Рассмотрим другую стратегию АШ на ПГК [2]. Противнику предлагается решить систему линейных уравнений
(С — С) Х = о (1)
для г = 1,…, ?, ] = 1,…, ?, г = ]. Ясно, что если существуют г,], такие, что т, 1 = т^, то соответствующая система уравнений (1) имеет решение г^ = К-1е1 Е Т? п. Оценим вероятность того, что существует хотя бы одна пара г,^, такая, что т, 1 = т^. Для этого понадобится следующая лемма.
Лемма 1. Вероятность появления т Е Ъп хотя бы дважды в последовательности {тк: к = 1,…, и& gt-}, где тк Е Zn сгенерированы по вероятностному распределению Т& gt-,
равна PrD, w (m) = 1 — (1 — pm) w — w (1 — pm) w 1pm, где pm — вероятность появления m в соответствии с D.
Распределение D здесь считается таким, что все m^ независимы друг от друга. Лег-
n-1 _ n-1
ко видеть тогда, что Prt =1 — П (1 — P Tv, t (a)) = 1 — П ((1 — Ра)4 + t (1 — Pa) t-1Pa),
а=0 а=0
где ра -вероятность появления, а G Zn согласно D. Другие ненулевые решения, кроме v1, у системы (1) появляются, только если г — Tj G Z*n. Последнее может произойти с вероятностью Pr =1 — ф (п)/п, так как г — Tj — равномерно распределённая на Zn величина. В силу выбора п можно считать, что Pr ^ 0, поэтому вероятность успеха описанной атаки равна Prt.
Для любого D справедливо lim Prt = 1. Однако атака оказывается практичной не
t-у^о
для любого D из-за большого размера P = Zn. Наилучшим образом она работает для дискретного гауссова распределения D = Dzn,?, a2, где ^ - математическое ожидание- а2 -дисперсия и а2 ^ п. В таблице приведены значения Prt для разных t при п с 1с^(п) = 1024 и а2 ^ п- указаны также практические оценки вероятности Prt найти v1 с помощью описанной стратегии, полученные при тестировании реализации атаки. Для получения каждой P rt проводилось 104 независимых испытаний.
t Prt Prt
50 0,88 0,85
70 0,955 0,945
90 0,998 0,99
120 1 0,99 999
3. Связь трудности факторизации больших чисел и защищённости криптосистемы
В [2] доказано, что умение правильно расшифровывать C G Z^x2 позволяет фак-торизовать n. Однако для того чтобы строго связать криптостойкость с задачей факторизации, необходимо и обратное утверждение. Но оно не выполняется, так как если известны p, q, то из этого не следует корректное расшифрование C. Действительно, по китайской теореме об остатках char (x) для C имеет четыре корня, и чтобы выбрать из
них открытый текст, придётся привлечь D. Исходя из этого, можно модифицировать
i
ПГК [2]. Пусть n задается как n = П p^, где pk — простые числа, pi = pj. Решить
k=l
уравнение char (x) = 0 теперь нетрудно, так как n можно факторизовать. Однако количество решений равно 2l. При знании D для выбора открытого текста среди этих решений необходимо ^ 2l операций. Если положить l = 120, то перебор окажется настолько велик, что атака на char (x) будет нереализуемой. Причём вычислительная сложность этого перебора эквивалентна сложности факторизации 1024-битного RSA модуля (с использованием метода решета числового поля), т. е. сложность атаки на char (x) остаётся такой же. При этом размер n можно уменьшить, подобрав нужным образом pk, k = 1,…, l- в результате ПГК [2] становится более эффективной.
Заключение
Предложена атака по шифртекстам на ПГК [2], основанная на решении системы линейных уравнений. Её практичность обусловлена распределением D на пространстве открытых текстов. Если D сильно отлично от равномерного, например D — гауссово распределение с небольшой дисперсией, то атака работает успешно. Для практики
это представляет интерес, так как в реальных приложениях D часто является именно таким. Обнаружено, что отсутствие строгой сводимости криптостойкости ПГК [2] к задаче факторизации позволяет использовать модуль n более скромных размеров без ухудшения защищённости. Это делает ПГК [2] более быстродействующей.
ЛИТЕРАТУРА
1. Guellier A. Can Homomorphic Cryptography ensure Privacy? PhD thesis, Inria- IRISA- Supelec Rennes, equipe Cidre- Universite de Rennes 1, 2014.
2. Kipnis A. and Hibshoosh E. Efficient methods for practical fully homomorphic symmetric-key encrypton, randomization and verification // IACR Cryptology ePrint Archive. 2012. No. 637.
3. Vizar D. and Vaudenay S. Analysis of chosen symmetric homomorphic schemes // Central European Crypto Conference, Budapest, Hungary, 2014, EPFL-CONF-198 992.

ПоказатьСвернуть
Заполнить форму текущей работой