ANDOS (криптография)

ANDOS (англ. All or Nothing Disclosure Of Secrets) — криптографический протокол «секретной продажи секретов». Пусть продавец S секретов имеет некий список вопросов и выставляет на продажу ответы к любому из них. Предположим, покупатель B хочет купить секрет, но не хочет раскрывать какой именно. Протокол гарантирует, что B получит нужный ему секрет и ничего более, в то время как S не будет знать какой именно секрет получил B.

Пусть ${\displaystyle s_{1},...,s_{k}}$ секреты, которым обладает S, каждый из них содержит ${\displaystyle n}$ бит. Для каждого ${\displaystyle s_{j}}$ S публикует описание секрета. Предположим, что покупатели B и C хотят купить секреты ${\displaystyle s_{j}}$ и ${\displaystyle s_{j'}}$, соответственно. Идея в том, что покупатели имеют индивидуальные односторонние функции и каждый из них оперирует над числами, полученными другим.

Шаг 1. S даёт B и C индивидуальные односторонние функции f и g, но сохраняет обратные к ним для себя.

Шаг 2. B сообщает C (соответственно C — B) ${\displaystyle k}$ случайных ${\displaystyle n}$-битных чисел ${\displaystyle x_{1},...,x_{k}}$ (соответственно ${\displaystyle x_{1'},...,x_{k'}}$).

Для ${\displaystyle f}$, отображающего ${\displaystyle n}$-разрядные числа в ${\displaystyle n}$-разрядные числа, и ${\displaystyle n}$-разрядного числа ${\displaystyle x}$, скажем, что индекс ${\displaystyle i,1\leqslant i\leqslant n}$ — это Индекс Фиксированного Бита (ИФБ) соответствующего паре ${\displaystyle (x,f)}$, если ${\displaystyle i}$-й бит в ${\displaystyle x}$ равен ${\displaystyle i}$-му биту в ${\displaystyle f(x)}$. Ясно, что ${\displaystyle i}$ есть ИФБ соответствующий паре ${\displaystyle (x,f)}$, если он является ИФБ, соответствующим паре ${\displaystyle (f(x),f^{-1})}$. Если ${\displaystyle f}$ ведёт себя достаточно произвольно при изменении битов в ${\displaystyle x}$ (как хорошие криптографические функции), то, для случайного ${\displaystyle x}$, можно грубо оценить, что примерно ${\displaystyle {\frac {n}{2}}}$ индексов являются ИФБ, соответствующими ${\displaystyle (x,f).}$

Шаг 3. B сообщает C (соответственно C — B) набор ИФБ${\displaystyle _{B}}$ индексов, соответствующих ${\displaystyle (x'_{j},f)(}$ соответственно набор ИФБ${\displaystyle _{C}}$ индексов, соответствующих ${\displaystyle (x_{j'},g)).}$

Шаг 4. B (соответственно C) сообщает S числа ${\displaystyle y_{1},...,y_{k}}$ (соответственно ${\displaystyle y_{k'},...,y_{k'}}$, где ${\displaystyle y_{i}}$ — результат, полученный заменой каждого бита в ${\displaystyle x_{i}}$, чей индекс не является ИФБ${\displaystyle _{C}}$, ему противоположным (соответственно ${\displaystyle y'_{i}}$ получаются из ${\displaystyle x'_{i}}$ аналогичным образом).

Шаг 5. S сообщает B (соответственно C) числа

${\displaystyle s_{i}\oplus f^{-1}(y'_{i})(}$ соответственно ${\displaystyle s_{i}\oplus g^{-1}(y_{i}))}$ , ${\displaystyle i=1,...,k}$.

Шаг 6. B (соответственно C) может вычислить ${\displaystyle s_{j}}$ (соответственно ${\displaystyle s'_{j}}$), поскольку известны ${\displaystyle x'_{j}=f^{-1}(y'_{j})(}$ соответственно ${\displaystyle x_{j'}=g^{-1}(y_{j'})).}$

B и C узнали нужные им секреты. S не узнал ничего об их выборе. Кроме того, ни B, ни C не узнали более одного секрета или выбора друг друга. Сговор между B и C приводит к тому, что они могут узнать все секреты. Сговор между S и кем-либо из покупателей может вскрыть какой секрет хочет другой покупатель.

Итак, основная проблема заключается в сговорах. Однако в случае, если покупателей не меньше трёх, то одного честного покупателя достаточно для того, чтобы сделать невозможным жульничество остальных, благодаря использованию криптографический функций, так как каждый бит последовательности, отправленный покупателям от S сильно зависит от бит предоставленных честным покупателем.

В случае, ели число покупателей ${\displaystyle t\geqslant 3}$ протокол действует абсолютно так же, но каждый покупатель получает ${\displaystyle t-1}$ функцию от продавца наравне с наборами чисел от других покупателей.

• За основу односторонних функций ${\displaystyle f}$ и ${\displaystyle g}$ возьмём RSA.

Выберем ${\displaystyle k=8,n=12}$. Считаем, что S имеет 8 следующих 12-битных секретов на продажу:

${\displaystyle s_{1}=1990,}$ ${\displaystyle s_{2}=471,}$ ${\displaystyle s_{3}=3860,}$ ${\displaystyle s_{4}=1487,}$ ${\displaystyle s_{5}=2235,}$ ${\displaystyle s_{6}=3751,}$ ${\displaystyle s_{7}=2546,}$ ${\displaystyle s_{8}=4043.}$

Шаг 1.

S даёт B и C индивидуальные односторонние функции f и g, основанные на простых числах ${\displaystyle p_{1}=83,q_{1}=89}$ (соответственно ${\displaystyle p_{2}=67,q_{2}=41}$), модуль ${\displaystyle n_{1}=7387}$ (соответственно ${\displaystyle n_{2}=2747}$). Открытая и закрытая экспоненты равны ${\displaystyle e_{1}=5145,d_{1}=777}$ (соответственно ${\displaystyle e_{2}=1421,d_{2}=2261}$).

Шаг 2.

B сообщает C восемь 12-битных чисел ${\displaystyle x_{i},1\leqslant i\leqslant 8}$: ${\displaystyle x_{1}=743,}$ ${\displaystyle x_{2}=1988,}$ ${\displaystyle x_{3}=4001,}$ ${\displaystyle x_{4}=2942,}$ ${\displaystyle x_{5}=3421,}$ ${\displaystyle x_{6}=2210,}$ ${\displaystyle x_{7}=2306,}$ ${\displaystyle x_{8}=912.}$

C сообщает B восемь 12-битных чисел ${\displaystyle x'_{i},1\leqslant i\leqslant 8}$: ${\displaystyle x'_{1}=1708,}$ ${\displaystyle x'_{2}=711,}$ ${\displaystyle x'_{3}=1969,}$ ${\displaystyle x'_{4}=3112,}$ ${\displaystyle x'_{5}=4014,}$ ${\displaystyle x'_{6}=2308,}$ ${\displaystyle x'_{7}=2212,}$ ${\displaystyle x'_{8}=222.}$

Шаг 3.

Пусть B хочет купить секрет ${\displaystyle s_{7}}$. Он вычисляет

${\displaystyle f(x'_{7})=(x'_{7})^{e_{1}}{\pmod {n_{1}}}=2212^{5145}{\pmod {7387}}=5928.}$

Сравнивая бинарное представление ${\displaystyle x'_{7}}$ и ${\displaystyle f(x'_{7}),}$

${\displaystyle 2212=0100010100100}$

${\displaystyle 5928=1011100101000}$

B сообщает C набор ИФБ${\displaystyle _{B}=\{0,1,4,5,6\}}$ соответствующих ${\displaystyle (x'_{7},f).}$

Пусть C хочет купить секрет ${\displaystyle s_{2}}$. После вычислений, C сообщает B набор ИФБ${\displaystyle _{C}=\{0,1,2,6,9,10\}}$ соответствующих ${\displaystyle (x_{2},g).}$

Шаг 4.

B сообщает S числа ${\displaystyle y_{i},1\leqslant i\leqslant 8}$, где ${\displaystyle y_{i}}$ — результат, полученный заменой каждого бита в ${\displaystyle x_{i}}$, чей индекс не принадлежит ${\displaystyle \{0,1,2,6,9,10\}}$, на противоположный, например:

${\displaystyle y_{2}=0110011111100=1660.}$

C сообщает S числа ${\displaystyle y'_{i},1\leqslant i\leqslant 8}$, где ${\displaystyle y'_{i}}$ — результат, полученный заменой каждого бита в ${\displaystyle x'_{i}}$, чей индекс не принадлежит ${\displaystyle \{0,1,4,5,6\}}$, на противоположный, например:

${\displaystyle y'_{7}=1011100101000=5928.}$

Шаг 5.

S сообщает B числа ${\displaystyle s_{i}\oplus f^{-1}(y'_{i}),1\leqslant i\leqslant 8(}$обратная функция ${\displaystyle f^{-1}(y')=y'^{d_{1}}{\pmod {n_{1}}}=y'^{777}{\pmod {7387}})}$, например:

${\displaystyle s_{7}=2546=0100111110010}$

${\displaystyle f^{-1}(y'_{7})=2212=0100010100100}$

${\displaystyle s_{7}\oplus f^{-1}(y'_{7})=0000101010110={\boldsymbol {342}}}$

S сообщает C числа ${\displaystyle s_{i}\oplus g^{-1}(y_{i}),1\leqslant i\leqslant 8(}$обратная функция ${\displaystyle g^{-1}(y)=y^{d_{2}}{\pmod {n_{2}}}=y^{2261}{\pmod {2747}})}$, например.

${\displaystyle s_{2}=471=000111010111}$

${\displaystyle g^{-1}(y_{2})=1988=011111000100}$

${\displaystyle s_{2}\oplus g^{-1}(y_{2})=011000010011={\boldsymbol {1555}}}$

Шаг 6.

B узнаёт секрет ${\displaystyle s_{7}}$, побитовым сложение ${\displaystyle x'_{7}}$ и 7-го числа, полученного от S, а именно:

${\displaystyle x'_{7}=2212=100010100100}$

${\displaystyle 342=000101010110}$

${\displaystyle x'_{7}\oplus 342)=100111110010={\boldsymbol {2546}}}$

.

Если C хочет купить секрет ${\displaystyle s_{2}}$, то он вычисляет побитовое сложение ${\displaystyle x_{2}}$ и 2-го числа, полученного от S, а именно:

${\displaystyle x_{2}=1988=11111000100}$

${\displaystyle 1555=11000010011}$

${\displaystyle x_{2}\oplus 1555)=00111010111={\boldsymbol {471}}}$

.

• G.Brassard, C.Crepeau and J.-M. Robert. All-or-nothing disclosure of secrets (англ.) // Springer Lecture Notes in Computer Science 263(1987). Архивировано 4 марта 2016 года.
• A.Salomaa and L.Santean. Secret selling of secrets with many buyers (англ.) // EATCS Bulletin 42(1990)). Архивировано 4 марта 2016 года.