Открытый ключ RSA с нулевым разглашением

Предположим, что у Боба есть $к>1$ открытые ключи RSA $(e_i, n_i)$ без какого-либо знания их соответствующих закрытых ключей. Алиса также имеет все открытые ключи, но также имеет закрытый ключ только для одного из них, скажем, $(d_j, n_j)$. Может ли она доказать Бобу, что у нее есть хотя бы один из секретных ключей, не раскрывая $j$

РЕДАКТИРОВАТЬ: изменено обозначение в соответствии с предложениями fgrieu

Вот предложение (вылетело из головы). Большая фотография

• Боб вытягивает случайный $Х$, и отправляет его детерминистически зашифрованным под каждым открытым ключом
• Алиса расшифровывает $Х$ с открытым ключом, который она держит
• Алиса проверяет, что Боб сделал так, как ожидалось, учитывая, что $Х$
• Алиса показывает $Х$ Бобу

Точнее:

• Определите 8 миллиардов долларов-битный хэш (скажем, SHA-512), такой, что $\мин(n_i)>2^{16b}$
• Определите функцию генерации маски (например, MGF1 с этим хешем), так что для байтовой строки $Х$, $\operatorname{MGF}(X,\ell)$ является $\ell$-байтовый хэш $Х$
• Определите длину байтов $\ell_i=\слева\lfloor\log_2(n_i)/8\справа\rfloor$, которые таковы, что $2^{8\ell_i}<n_i<2^{8\ell_i+8}$ (во избежание тайминг-атак желательно, чтобы $n_i$ имеют одинаковую разрядность, поэтому $l_i$ равный)
• Боб вытягивает случайный $X\in\{0,1\}^{8b}$ (а $б$-байтовая байтовая строка)
• Для каждого $я$, Боб
  • вычисляет $M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$
  • вычисляет $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$ (ан $l_i$-байтовая байтовая строка)
  • вычисляет и выводит $C_i={X_i}^{e_i}\bmod n_i$
• Алиса получает $C_i$, в том числе $C_j$
• Алиса вычисляет $f={C_j}^{d_j}\bmod n_j$
• Алиса выражает $ф$ как строка байтов $M\mathbin\|G$ с $ млн $ из $l_i-b$ байты и $G$ из $б$ байт.
• Алиса выздоравливает $Х$ вычисляя $X=G\oplus H(M\mathbin\|J)$
• Для каждого $я$, Алиса
  • вычисляет $M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$, куда $I$ индекс $я$ как байтовая строка.
  • вычисляет $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$ (ан $l_i$-байтовая байтовая строка)
  • чеки ${X_i}^{e_i}\bmod n_i=C_i$ (когда $я=j$, это проверяет $M=\operatorname{MGF}\bigl(X\mathbin\|H(n_j),l_j-b\bigr)$ как побочный эффект)
• Только если все проверки пройдены, и без выявления (например, по времени), где произошла ошибка, если таковая имеется, или какая $X_i$ был использован для восстановления $Х$
  • Алиса показывает $Х$
• Боб проверяет, что Алиса раскрыла правду. $Х$

Обоснование:

• Алиса доказывает, что может расшифровать одну из криптограмм $C_i$, таким образом, она держит закрытый ключ
• Она не раскрывает какие, так как убедилась, что все криптограммы совпадают. $Х$. Нет риска, что смещение в старших битах в каком-то количестве в $[0,n_j)$ может дать преимущество в угадывании $j$ (как могло бы быть в случае наивной реализации тот другой ответ).
• Представители $X_i$ из $Х$ распространяются на $[0,n_i)$ как в РСАССА-ОАЭП, с независимыми функциями заполнения. Обратите внимание, что прямое шифрование $X_i=X$, или же $X_i=F(X)$ для некоторого фиксированного впрыска $F$, сделает систему уязвимой для Широковещательная атака Хостада; кроме того, может оказаться невозможным определить безопасную общую ширину для $X_i$, например если $n_0$ 2048-битный, $n_1$ 8192-бит, $e_1=3$; прокладка решает это.
• С $Х$ является вызовом, нарисованным Бобом, протокол невосприимчив к воспроизведению: Алиса не может уйти с данными, которые она предварительно вычислила до потери доступа к своему закрытому ключу, или данными, ранее вычисленными Амандой, у которой также есть закрытый ключ.

Возможные улучшения, чтобы еще больше уберечь Алису от превращения в оракула дешифрования, а Боба от настройки его $Х$, и, возможно, упростить доказательство:

• Алиса сначала рисует $б$-байт $Y$ и отправляет обязательство $H(Y\mathbin\|S_0)$
• Боб рисует свой $б$-байт $Х$ и отправляет обязательство $H(X\mathbin\|S_1)$
• Алиса показывает $Y$, Боб сверяет его с $H(Y\mathbin\|0)$
• вышеуказанный протокол изменен
  • это используется $M_i=\operatorname{MGF}\bigl(X\mathbin\|Y\mathbin\|H(n_i),l_i-b\bigr)$
  • это используется $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|Y\mathbin\|H(n_i)))$
  • Алиса далее проверяет $H(X\mathbin\|1)$ совпадения
  • Алиса показывает $H(X\mathbin\|S_2)$ скорее, чем $Х$
  • Боб проверяет это. (где $S_i$ являются различными произвольными короткими непустыми байтовыми строками)

Обновление: другой метод, описанный в этот другой ответ, заключается в использовании Кольцевая подпись на основе RSA, и заставьте Алису продемонстрировать Бобу свою способность подписывать сообщение с вызовом.