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

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


Алгоритм[ | ]

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

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

Для , отображающего -разрядные числа в -разрядные числа, и -разрядного числа , скажем, что индекс  — это Индекс Фиксированного Бита (ИФБ) соответствующего паре , если -й бит в равен -му биту в . Ясно, что есть ИФБ соответствующий паре , если он является ИФБ, соответствующим паре . Если ведёт себя достаточно произвольно при изменении битов в (как хорошие криптографические функции), то, для случайного , можно грубо оценить, что примерно индексов являются ИФБ, соответствующими

Шаг 3. B сообщает C (соответственно C — B) набор ИФБ индексов, соответствующих соответственно набор ИФБ индексов, соответствующих
Шаг 4. B (соответственно C) сообщает S числа (соответственно , где  — результат, полученный заменой каждого бита в , чей индекс не является ИФБ, ему противоположным (соответственно получаются из аналогичным образом).
Шаг 5. S сообщает B (соответственно C) числа
соответственно , .
Шаг 6. B (соответственно C) может вычислить (соответственно ), поскольку известны соответственно

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

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

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

Примеры[ | ]

  • За основу односторонних функций и возьмём RSA.
Выберем . Считаем, что S имеет 8 следующих 12-битных секретов на продажу:
Шаг 1.
S даёт B и C индивидуальные односторонние функции f и g, основанные на простых числах (соответственно ), модуль (соответственно ). Открытая и закрытая экспоненты равны (соответственно ).
Шаг 2.
B сообщает C восемь 12-битных чисел :
C сообщает B восемь 12-битных чисел :
Шаг 3.
Пусть B хочет купить секрет . Он вычисляет
Сравнивая бинарное представление и
B сообщает C набор ИФБ соответствующих
Пусть C хочет купить секрет . После вычислений, C сообщает B набор ИФБ соответствующих
Шаг 4.
B сообщает S числа , где  — результат, полученный заменой каждого бита в , чей индекс не принадлежит , на противоположный, например:
C сообщает S числа , где  — результат, полученный заменой каждого бита в , чей индекс не принадлежит , на противоположный, например:
Шаг 5.
S сообщает B числа обратная функция , например:
S сообщает C числа обратная функция , например.
Шаг 6.
B узнаёт секрет , побитовым сложение и 7-го числа, полученного от S, а именно:

.

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

.

Литература[ | ]