Параллельные доказательства с нулевым разглашением конфиденциальной информации
Параллельные доказательства с нулевым разглашением конфиденциальной информации
Обычный протокол доказательства с нулевым разглашением конфиденциальной информации требует, чтобы Антон и Борис последовательно повторили его шаги n раз. Можно попробовать выполнять действия, предусмотренные этим протоколом, одновременно:
1. Антон использует имеющуюся у него информацию и n
сгенерированных случайных чисел, чтобы свести труднорешаемую задачу к n другим труднорешаемым задачам, изоморфным исходной задаче. Затем Антон решает эти n новых задач.
2. Антон задействует протокол предсказания бита для найденных на шаге
1 n решений, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этими решениями, Борис мог бы достоверно убедиться, что предъявленные Антоном решения действительно были получены им на шаге 1.
3. Антон показывает n новых труднорешаемых задач Борису.
4. Для каждой из n новых труднорешаемых задач Борис просит Антона
или доказать, что она изоморфна исходной труднорешаемой задаче или предоставить решение этой задачи, которое Антон должен был найти на шаге 1, и доказать, что оно действительно является ее решением.
5. Антон выполняет все просьбы Бориса.
На первый взгляд параллельный протокол обладает тем же свойством нулевого разглашения конфиденциальной информации, что и обычный. Однако строгого доказательства этого факта еще не найдено. А пока с полной определенностью можно сказать лишь одно: некоторые интерактивные протоколы доказательства с нулевым разглашением в некоторых ситуациях можно выполнять параллельно, и от этого они не утрачивают свойство нулевого разглашения конфиденциальной информации.
Обсуждение Защита компьютерной информации
Комментарии, рецензии и отзывы