Доказательство интерактивное [ Interactive proof ]

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