Ciphertexts-only attack on a linear fully ho-momorphic cryptosystem.pdf Введение В связи с распространением облачных сервисов задача построения полностью гомоморфных криптосистем (ПГК), позволяющих проводить произвольные вычисления над данными в зашифрованном виде, приобрела большую актуальность. Основным направлением в данной области является построение ПГК, основанных на теории решёток и методике Джентри [1]. Однако существующие на данный момент ПГК этого типа обладают низкой вычислительной эффективностью и являются непригодными для практики [1]. Поэтому не прекращаются поиски альтернативного варианта ПГК, не использующей метод Джентри и являющейся эффективной и криптостойкой. В частности, активно предлагаются ПГК, основанные на задаче факторизации чисел. В данной работе анализируется одна недавно предложенная ПГК этого вида из [2]. Описывается атака по шифртекстам (АШ) на ПГК [2], основанная на решении системы линейных уравнений и не рассмотренная ранее в литературе. Приводятся оценки вероятности её успеха в зависимости от различных параметров. 1. Полностью гомоморфная криптосистема из [2] и её основные свойства Опишем ПГК, предложенную в [2]. Для зашифрования открытого текста m G Zn составляется матрица D = diag(m, r) G Z;;x2, где n = pq, p, q - простые числа, log(p) = log(q) ^ 512 (т.е. n трудно факторизовать), r G Zn выбран по равномерному распределению, diag(m, r) -диагональная матрица с m, r на главной диагонали. Шифртекст вычисляется как C = K-1DK G Z^2, где K G Z^2 - секретный ключ. Ясно, что m - собственное число C, имеющее собственный вектор v1 = K-1 e1 G Z^ где e1 = (1, 0). Для расшифрования вычисляется s = Cv1, а затем m = s1/v1,1. Описанная криптосистема - ПГК, так как в ней произведению и сумме шифртекстов соответствуют произведение и сумма открытых текстов. При этом операции над шифртекстами вычислительно эффективны (умножение и сложение матриц). Это делает данную ПГК очень интересной с практической точки зрения. Однако ПГК [2] совершенно нестойка к атаке по известным открытым текстам. По перехваченной паре (m, C) можно составить систему линейных уравнений (C - mI)x = 0, множество решений которой имеет базис {v1} с вероятностью ~ 1, и поэтому наличие даже одной пары (m, C) компрометирует [2]. Больше информации об атаке по известным открытым текстам на ПГК [2] можно найти в [3]. 2. Атака по шифртекстам на ПГК [2] Предположим, противник перехватил последовательность Cj G Znx2, i = 1,...,t, шифрующих m^ G Zn, i = 1,... , t, на ключе K. Ясно, что m^ - корень характеристического полинома chari(x) G Zn[x], составленного для Cj. Так как n трудно факторизовать, нахождение корней charj(x) в общем случае трудно. Этим свойством в [2] и обосновывается защищённость ПГК. Однако на самом деле это работает, только если вероятностное распределение D, заданное на пространстве открытых текстов P = Zn, является близким к равномерному. Если же, к примеру, D таково, что P{mj > ^Jn} = 0, то, согласно [3], mj можно найти из charj(x). Рассмотрим другую стратегию АШ на ПГК [2]. Противнику предлагается решить систему линейных уравнений (Cj - Cj )x = 0 (1) для i = 1,... , t, j = 1,... , t, i = j. Ясно, что если существуют i, j, такие, что mj = mj, то соответствующая система уравнений (1) имеет решение v1 = K-1e1 G Z^ Оценим вероятность Prt того, что существует хотя бы одна пара i,j, такая, что mj = mj. Для этого понадобится следующая лемма. Лемма 1. Вероятность появления m G Zn хотя бы дважды в последовательности {mk : k = 1,... , w}, где fnk G Zn сгенерированы по вероятностному распределению D, равна PrD,w(ш) = 1 - (1 - )w - w(1 - )w , где - вероятность появления ш в соответствии с D. Распределение D здесь считается таким, что все m^ независимы друг от друга. Легn-1 n-1 ко видеть тогда, что Prt =1 - П (1 - Prx>,t(a)) = 1 - П ((1 - Ра)* + t(1 - p«)t-1p«), а=0 а=0 где ра -вероятность появления а Е Zn согласно D. Другие ненулевые решения, кроме v1, у системы (1) появляются, только если r - rj Е Z^ Последнее может произойти с вероятностью Pr =1 - 0(n)/n, так как r - rj - равномерно распределённая на Zn величина. В силу выбора n можно считать, что Pr ^ 0, поэтому вероятность успеха описанной атаки равна Prt. Для любого D справедливо lim Prt = 1. Однако атака оказывается практичной не t-^^о для любого D из-за большого размера P = Zn. Наилучшим образом она работает для дискретного гауссова распределения D = Dzn,M,CT2, где ^ - математическое ожидание; а2 -дисперсия и а2 ^ n. В таблице приведены значения Prt для разных t при n с log(n) = 1024 и а2 ^ n; указаны также практические оценки вероятности Prt найти v1 с помощью описанной стратегии, полученные при тестировании реализации атаки. Для получения каждой Prt проводилось 105 независимых испытаний. t Prt Prt 50 0,88 0,85 70 0,955 0,945 90 0,998 0,99 120 1 0,99999 это представляет интерес, так как в реальных приложениях D часто является именно таким. Обнаружено, что отсутствие строгой сводимости криптостойкости ПГК [2] к задаче факторизации позволяет использовать модуль n более скромных размеров без ухудшения защищённости. Это делает ПГК [2] более быстродействующей.

Скачать электронную версию публикации