помогите найти вариант авторизации с нулевым разглашением
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)
комментариев: 1 документов: 1 редакций: 0
комментариев: 9796 документов: 488 редакций: 5664
На шифрование Рабина похоже и протокол Фейге-Фиата-Шамира.
А теперь появилась «Simple quantum password checking», которую ещё пока ни в один журнал не приняли, но написана вроде солидно. Стр. 1:
Не знаю, как по сути, но по постановке задачи это больше случай «zero-knowledge proof» (доказательство с нулевым разглашением), чем «password». Видимо, они хотят сказать, что задача аутентификации — частный случай zero-knowledge(?).