Псевдокод алгоритма AxmoduloN

Псевдокод алгоритма AxmoduloN

Program Exp(x,N,A,R); {вход x,N,A, выход R}
	 begin
	 B:=1;
	 for i:=1 to n do
	 begin
	 B:=(B*B)modN;
	 if [i]=1 then B:=(A*B)modN;
	 end;
	 R:=B;
	 end.
Из описания алгоритма видно, что число обращений к операции вида (A*B)moduloN будет logx+ β(x), где β(x) число единиц в двоичном представлении операнда x или вес Хэмминга x.

Построение самотестирующейся/самокорректирующейся программной пары для функции дискретного экспоненцирования.

Сначала рассмотрим следующие 4 алгоритма. Для доказательства полноты и безопасности указанной пары доказывается следующая теорема.

Теорема 2.2. Пара программ S_K_exp(x,M,q,g,β) и S_T_exp(x,M,q,g,β) является (1/288,1/8,1/8)самокорректирующейся/ самотестирующейся программной парой для функции gxmoduloM, с входными значениями, выбранными случайно и равновероятно из множества In.

Для доказательства теоремы необходимо доказать следующие две леммы.

Лемма 2.1. Программа S_K_exp(M,q,g,β) является (1/8)самокорректирующейся программой для вычисления функции gxmoduloM в отношении равномерного распределения Dn.

Доказательство. Полнота программы S_K(') означает, что если оракульная программа P(x), обозначаемая как Exp(') выполняется корректно, то и самокорректирующаяся программа S_K(') будет выполняться корректно. В данном случае полнота программы очевидна. Если P(x) корректно вычислима, то из следует, что

Program L_T(n,R); {вход g,M,q, выход Rl}
begin
x1:=random(q);
x2:=random(q);
x:=(x1+x2)modq;
Exp(g,x1,M,R1);
Exp(g,x2,M,R2);
Exp(g,x,M,R);
if R1 R2=R then Rl:=1
else Rl:=0;
end.

Program N_T(n,R); {вход g,M,q, выход Re}
begin
x1:=random(q);
x2:=(x1+1)modq;
Exp(g,x1,M,R1);
Exp(g,x2,M,R2);
if R1 g=R2 then Re:=1
else Re:=0;
end.

Для доказательства безопасности сначала необходимо отметить, что так как x1 RZq, то и x2 имеет равномерное распределение вероятностей над Zq. Так как вероятность ошибки ε 1/8, то в одном цикле вероятность Prob[Rk=fM,g(x)] 3/4. Чтобы вероятность корректного ответа была не менее чем 1 β, исходя из оценки Чернова [62], необходимо выполнить не менее 12ln(1/β ) циклов


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок