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. (англ.) // Springer Lecture Notes in Computer Science 263(1987). 4 марта 2016 года.
• A.Salomaa and L.Santean. (англ.) // EATCS Bulletin 42(1990)). 4 марта 2016 года.

В статье есть список источников , но не хватает сносок . Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники , подтверждающие информацию. Сведения без сносок могут быть удалены . ( 30 октября 2014 )

Для улучшения этой статьи желательно : Оформить статью по правилам . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.