помогите найти вариант авторизации с нулевым разглашением




1. Боб знает пару простых чисел, а и b
2. Алиса знает пару простых чисел, c и d
3. Как Бобу проверить истинность выражения f(a,c) mod 53 == f(b,d) mod 53 с заданной вероятностью v при том, что никто из них
не должен узнать пары чисел друг друга, а также результат f(a,c) mod 53 и f(b,d) mod 53
т.е. подобрать функцию f, а также протокол проверки
под "не должен узнать" подразумевается невозможность узнать за приемлемое время, сложность >= O(N^2), при этом сложность алгоритма
проверки должна быть <= O(N * log N)

Комментарии
Гость (20/09/2013 00:13)   
Напоминает Diffie-Hellman. С википедийными статьями про zero-knowledge proof ознакомились, там не то?
— samson11 (20/09/2013 00:20)   
Есть протокол Шнорра. Но он может проверить только пару чисел, причем так, что один знает а, другой знает б. Нам же требуется сравнить две совокупности пар. Нам не нужно понимать равно ли а == с или б == д.
Гость (20/09/2013 06:13)   
Протокол миллионера-социалиста больше не в моде?
— unknown (20/09/2013 21:08, исправлен 20/09/2013 21:09)   

На шифрование Рабина[link1] похоже и протокол Фейге-Фиата-Шамира[link2].

Гость (17/01/2015 21:09)   
Была когда-то работа «Quantum passwords»[link3], которая

Paper withdrawn to address a security loophole

А теперь появилась «Simple quantum password checking»[link4], которую ещё пока ни в один журнал не приняли, но написана вроде солидно. Стр. 1:

We consider two parties, Alice and Bob, who share an m-bit string p (the password). There can also be an eavesdropper, Eve, trying to either learn the password or to impersonate Alice or Bob. For simplicity, we describe the case where Alice tries to provу her identity to Bob. Everything is symmetric for the converse case.

In this paper, we propose an alternative password checking protocol where security is derived from the laws of quantum mechanics. The protocol can resist replay attacks and is robust against dictionary attacks, even for poorly chosen passwords.

Не знаю, как по сути, но по постановке задачи это больше случай «zero-knowledge proof» (доказательство с нулевым разглашением), чем «password». Видимо, они хотят сказать, что задача аутентификации — частный случай zero-knowledge(?).

Ссылки
[link1] https://en.wikipedia.org/wiki/Rabin_encryption

[link2] https://en.wikipedia.org/wiki/Feige–Fiat–Shamir_identification_scheme

[link3] http://arxiv.org/abs/quant-ph/0506255

[link4] http://arxiv.org/abs/1501.02622