Интерактивное доказательство (interactive proof)- понятие теории сложности вычислений, составляющее основу понятия доказательства с нулевым разглашением,. И. д. — доказательство путем выполнения протокола с двумя участниками, доказывающим и проверяющим, в процессе работы которых участники обмениваются сообщениями (запросы и ответы), обычно зависящими от случайных чисел, которые могут содержаться в секрете. Цель доказывающего - убедить проверяющего в истинности некоторого утверждения. Проверяющий либо принимает, либо отвергает доказательство. В отличие от обычного математического понятия доказательства в данном случае доказательство носит не абсолютный, а вероятностный характер и характеризуется двумя вероятностями. Если доказываемое утверждение верно, то доказательство должно быть верным с вероятностью, стремящейся к единице при увеличении числа циклов протокола. Если же доказываемое утверждение ложно, то при увеличении числа циклов протокола вероятность правильности доказательства должна стремиться к нулю. Криптографическое качество протокола и. д. характеризуется свойствами полноты, корректности и нулевого разглашения. |
|
