Задача
1. Боб знает пару простых чисел,
2. Алиса знает пару простых чисел,
3. Как Бобу проверить истинность выражения
с вероятностью
при том, что никто из них не должен узнать пары чисел друг друга, а также значение выражений
. Т.е. подобрать функцию
, а также протокол проверки.
Примечание:
Под "не должен узнать" подразумевается невозможность узнать за приемлемое время при том, что проверка истинности выражения должна выполняться за приемлемое время. Иными словами сложность алгоритма "узнавания" должна быть экспоненциальная, а сложность алгоритма сравнения - полиноминальная.
Идеи:
В качестве гипотетической надежды на возможность такой схемы послужило наличие схемы Шнорра (
http://ru.wikipedia.org/wiki/%D0%A1%D1% ... 1%80%D0%B0). Т.е. направление, куда следует копать, это свойства простых чисел, а также сложность задачи факторизации произведения двух больших простых чисел, сложность вычисления дискретного логарифма при меньшей сложности задачи вычисления
skype: easy88easy88