Самый дешевый способ доказать, что два разных закрытых ключа известны одному и тому же человеку?

Предположим, что есть две несвязанные пары ключей ECC ($Pub_1$, $Priv_1$) и ($Pub_2$, $Priv_2$). Алиса утверждает, что знает обоих $Priv_1$ и $Priv_2$, но Боб ей не доверяет и думает, что $Priv_2$ известно только Еве, подруге Алисы.

Боб просит Алису доказать, что она владеет обоими закрытыми ключами. Теперь Боб знает, что если Ева действительно контролирует $Priv_2$, она согласилась бы вступить в сговор с Алисой, чтобы получить доказательство того, что Алиса контролирует их обоих. Но он также знает, что доверие Евы ограничено — Ева на самом деле не захотела бы сообщить Алисе секретный ключ. $Priv_2$.

Какое доказательство Алиса могла бы предоставить Бобу, что она (или, по крайней мере, один и тот же человек) знает и то, и другое? $Priv_1$ и $Priv_2$? Обратите внимание, что напр. вложенная подпись, например, например. $Sig_1(Sig_2(сообщение))$ недостаточно, потому что Ева могла бы просто сгенерировать $Sig_2(сообщение)$ и дайте Алисе завернуть $Sig_1$ никогда не раскрывая $Priv_2$.

Еще одна сложность: доказательство должно эффективно работать на кривой secp256k1. (Я рассматривал возможность использования для этого zkSNARK, но библиотеки SNARK, которые я видел, не работают эффективно на этой кривой.)

Это кажется теоретически невозможным. Насколько я могу судить, нет никакой разницы между знанием $priv_2$ и в сговоре с кем-то, кто знает $priv_2$.

Предположим, что какой-то протокол доказательства $\Пи$ существует между доказывающим (A) и верификатором (B), который удовлетворяет описанным требованиям. Всегда есть способ $A(priv_1)$ и $E(priv_2)$ вступить в сговор для казни $\Пи$ таким образом, что $А$ ничего не узнает о $priv_2$. $А$ и $Е$ просто запустите какой-нибудь протокол MPC, чтобы вычислить следующий ответ на $В$.

Безопасность протокола MPC гарантирует, что $А$ не узнает ничего, кроме своего собственного ввода $priv_1$ и результаты, которые являются ответами на $В$, который и так все видят. И если $\Пи$ является нулевым разглашением $В$ (обычно желательно), затем $А$ ничего не узнает из ответов.

Отказ от ответственности: у меня нет доказательств безопасности для этой схемы. Критика приветствуется.

Чтобы упростить запись, я называю две пары ключей (закрытый и открытый) $(а, А = а\cdot G)$ и $(b, B = b\cdot G)$ на базовой точке $G$. Строчные буквы — скаляры, прописные буквы — точки ЕС. $H_s()$ означает хэш и сокращение (мод порядок $G$) в скаляр. Все операции между скалярами (такие как вычитание и умножение) выполняются по модулю порядка $G$.

Во-первых, объявить $D = а\cdot b\cdot G$.

позволять $m = H_s(\text{"сообщение подписывается"})$ как одноразовое сообщение, которое предотвратит повторное использование этой подписи в разных контекстах.

Чтобы доказать $Д$ действительно построен правильно, используйте расширенную подпись Шнорра:

Подпись $(D, с, г)$ куда $к$ является случайным скаляром, $c = H_s(m \mathbin\| k\cdot G \mathbin\| k\cdot B)$ и $r = k - c\cdot a$.

Подпись проверяется проверкой $c \overset{?}{=} H_s(m \mathbin\| r\cdot G + c\cdot A \mathbin\| r\cdot B + c\cdot D)$ и проверив $Д$ является действительной точкой, а не точкой в ​​бесконечности.

Это доказывает и то, и другое $а$ известно, и что $а$ является закрытым ключом точки $А$ на генераторной точке $G$, а также приватный ключ точки $Д$ на генераторной точке $В$. Следовательно $Д$ доказано, что $а\cточка б\cточка G$.

Наконец, нам нужно создать вторую подпись, доказывающую, что кто-то знает и то, и другое. $а$ и $b$. Мы можем сделать это, доказав знание закрытого ключа точки $Д$ на базовой точке $G$ (таким образом подтверждая знание $а\cточка б$).

Подпись $(с', г')$ куда $к'$ является случайным скаляром, $c' = H_s(m \mathbin\| k'\cdot G)$ и $r' = k' - c'\cdot a\cdot b$.

Подпись проверяется проверкой $c' \overset{?}{=} H_s(m \mathbin\| r'\cdot G + c'\cdot D)$.

Если бы Алиса вступила в сговор с Евой, а Ева не раскрыла бы $b$, Алиса должна будет раскрыть свой закрытый ключ $а$ к Еве. Знание $к'$ одним из участников сговора позволит этому участнику сговора вычислить закрытый ключ другого участника сговора. Безопасность этой схемы зависит от того, что Алиса математически не может каким-либо образом сговориться с Евой, чтобы построить $г'$ так что либо Алиса, либо Ева могли математически определить закрытый ключ другого.

Таким образом, общая подпись $(D, с, г, с', г')$ и является $5\cdot 32 = 160$ байт.