Доказательство составности с нулевым разглашением

Доказательство с нулевым разглашением (ZKP) отвечает на вопрос, не раскрывая ничего, кроме ответа. Например, цифровая подпись доказывает наличие у вас закрытого ключа, не раскрывая этот ключ.

Вот еще один пример, более конкретный, чем цифровая подпись. Предположим, у вас есть колода из 52 карт, по 13 пик, червей, бубн и треф. Если я вытяну из колоды пику, я смогу доказать, что я вытащил пику, не показывая, какую карту я вытянул. Если я покажу вам, что все червы, бубны и трефы все еще находятся в колоде, вы поймете, что недостающая карта должна быть пикой.

Составные числа

Вы можете думать о тесте на простоту Ферма как о доказательстве с нулевым разглашением. Например, я могу убедить вас, что следующее число является составным, не сообщая вам, каковы его делители.

н = 2449489742783178172392186841051790996978412532327498771485549520308735153256789144986927658044852334 35199358326742674280590888061039570247306980857239550402418179621896817000856571932268313970451989041

Маленькая теорема Ферма гласит, что если н является простым и б не кратно нзатем

б^н−1 = 1 (мод. н).

Число б такой, что б^н−1 ≠ 1 (мод. н) является доказательством того, что н не является простым, т.е. н является составным. Так, например, б = 2 является доказательством того, что н выше является составным. Это можно очень быстро проверить с помощью Python:

    >>> pow(2, n-1, n)
    10282 ... 4299

Я попробовал самую маленькую возможную базу [1] и это сработало. В общем, возможно, вам придется попробовать несколько баз. А для некоторых редких чисел (числа Кармайкла) базу найти не удастся. Но если вы найдете базу б такой, что б^н−1 не соответствует 1 модулю нты знаешь, с уверенность что б является составным.

Простые числа

Обращение малой теоремы Ферма неверно. С его помощью можно доказать, что число нет простое число, но оно не может доказать, что число является основной. Но его можно использовать, чтобы показать, что число вероятно основной. (Есть некоторая тонкость относительно того, что означает, что число, вероятно, является простым. См. здесь.)

Маленькая теорема Ферма может дать вам доказательство с нулевым разглашением того, что число является составным. Может ли он дать вам доказательство с нулевым разглашением того, что число простое? В этом вопросе есть пара странностей.

Во-первых, что бы значило иметь доказательство с нулевым разглашением того, что число простое? Какие знания вы держите в секрете? Когда вы доказываете, что число составное, простые множители остаются секретными (или даже неизвестными), но в чем секрет, когда вы говорите, что число простое? Строго говоря, ЗКП не обязан ничего хранить в секрете, но на практике он всегда это делает.

Во-вторых, как насчет вероятности ошибки? Доказательства с нулевым разглашением не обязательно должны быть непогрешимыми. ZKP может иметь незначительную вероятность ошибки, и обычно так и есть.

Доказывая другие вещи

Неконструктивные доказательства можно рассматривать как ZKP. Например, вы можете думать о теореме о промежуточном значении как о ZKP: она доказывает, что функция имеет нуль в интервале, не давая вам никакой информации о том, где может находиться этот ноль.

Что делает ZKP интересными в применении, так это то, что они могут доказывать вещи более общего характера, чем математические утверждения. [2]. Например, криптовалюты могут предоставлять ZKP, которые соответствуют ограничениям бухгалтерского учета, не раскрывая входные или выходные данные транзакции. Вы можете доказать, что никто не пытался потратить отрицательную сумму и что сумма входов равна сумме выходов.

Похожие сообщения

[1] Вы могли бы попробовать б = 1, но тогда б^н−1 всегда равен 1. Этот пример показывает, что существование базы, для которой б^н−1 = 1 (мод. н) ничего не доказывает.

[2] Вы можете возразить, что правила бухгалтерского учета являются математическими утверждениями, и, конечно, так оно и есть. Но они мало интересуют математиков и представляют большой интерес для сторон сделки.