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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

Шаг 1.

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

Шаг 2.

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

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

Шаг 3.

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

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

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

$2212=0100010100100$ $5928=1011100101000$

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

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

Шаг 4.

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

$y_{2}=0110011111100=1660.$

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

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

Шаг 5.

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

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

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

$s_{2}=471=000111010111$ $g^{-1}(y_{2})=1988=011111000100$ $s_{2}\oplus g^{-1}(y_{2})=011000010011={\boldsymbol {1555}}$

Шаг 6.

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

$x'_{7}=2212=100010100100$ $342=000101010110$ $x'_{7}\oplus 342)=100111110010={\boldsymbol {2546}}$

.

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

$x_{2}=1988=11111000100$ $1555=11000010011$ $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 года.