Моделирующая машина

Моделирующая машина

  1. Запоминает состояние машины V, то есть содержимое всех ее лент, внутреннее состояние и позиции головок на лентах. Затем получает от V значение δ и после этого снова запоминает состояние машины V.
  2. Выбирает ηRZq и вычисляет h`1gη(modp) и h`2`rη(modp).
  3. Получает от V значения a и b. Если δ ragb(modp), то MV` останавливается.
  4. Машина MV` "отматывает" V на состояние, которое было запомнено в конце шага 1. Выбирает tRZq и вычисляет h1ragb+1(modp) и h2γawb+1(modp).
  5. Машина MV` передает V h1, h2 и получает ответ (a`, b`). Возможны два варианта:
      5.1. a=a`, b=b`. В этом случае моделирование закончено и MV` записывает на выходную ленту тройку (h1, h2, t) и останавливается.
      52 aa` или bb` . Отсюда следует, что δ ragbra`gb`(modp). Предположим, что bb`. Из этого следует, что aa`. Следовательно, MV` может вычислить rg(bb`)/(aa`)(modp). Отсюда (b`b)/(aa`)=l дискретный логарифм r по основанию g.
  6. Машина MV` "отматывает" V на состояние, которое было заполнено в начале шага 1. Получает от V значение δ.
  7. Выбирает ηRZq вычисляет h1gη(modp) и h2wη(modp) и передает их V.
  8. Получает от V значения a и b. Если δ ragb(modp), то MV` останавливается. В противном случае вычисляет t=[η alb](mod q), выдает (h1, h2, t) на выходную ленту и останавливается.

К пп. 7 и 8 необходимо сделать следующее пояснение. Поскольку logg(p)wlogr(p)γ, из этого следует, что logw(p)γ logg(p)r. Отсюда

h2wηwb+1walwb+1γa(modp)

Из описания моделирующей машины MV` очевидно, что она работает за полиномиальное время. Величины (h1, h2, t) на шаге 5.1 выбираются в точности как в протоколе и поэтому имеют такое же распределение вероятностей. Кроме того, значения (h1, h2), выбираемые на шаге 7, имеют такое же распределение, как и в протоколе. Чтобы показать что и t имеет одинаковое распределение, достаточно заметить, что машина V не может по h1 и h2 определить, с кем она имеет дело с S или MV`. Поэтому, даже если бы V могла какимлибо "хитрым" образом строить a и b с учетом (h1, h2), распределение вероятностей величин a и b в обоих случаях одинаковы. Но значение t определяется однозначно четверкой величин a, b, h1, h2, при условии выполнения проверки на шаге 5 протокола.


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

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


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

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