помогите найти вариант авторизации с нулевым разглашением
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)
Напоминает Diffie-Hellman. С википедийными статьями про zero-knowledge proof ознакомились, там не то?
Есть протокол Шнорра. Но он может проверить только пару чисел, причем так, что один знает а, другой знает б. Нам же требуется сравнить две совокупности пар. Нам не нужно понимать равно ли а == с или б == д.
Протокол миллионера-социалиста больше не в моде?
На шифрование Рабина[link1] похоже и протокол Фейге-Фиата-Шамира[link2].
Была когда-то работа «Quantum passwords»[link3], которая
А теперь появилась «Simple quantum password checking»[link4], которую ещё пока ни в один журнал не приняли, но написана вроде солидно. Стр. 1:
Не знаю, как по сути, но по постановке задачи это больше случай «zero-knowledge proof» (доказательство с нулевым разглашением), чем «password». Видимо, они хотят сказать, что задача аутентификации — частный случай zero-knowledge(?).