Аккумулятор (криптография)

В криптографии аккумулятор — это односторонняя хэш-функция членства . Она позволяет пользователям удостоверять, что потенциальные кандидаты являются членами определенного набора, не раскрывая отдельных членов набора. Эта концепция была официально введена Джошем Беналохом и Майклом де Маре в 1993 году. ^{[1] [2]}

В литературе предложено несколько формальных определений. В этом разделе они перечислены по авторам, примерно в хронологическом порядке. ^[2]

Бенало и де Маре определяют одностороннюю хеш-функцию как семейство функций, которые удовлетворяют следующим трем свойствам: ^{[1] [2]}${\displaystyle h_{\ell }:X_{\ell }\times Y_{\ell }\to Z_{\ell }}$

1. Для всех можно вычислить за время . (Здесь символ «поли» относится к неопределенному, но фиксированному полиному.)${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y\in Y_{\ell }}$${\displaystyle h_{\ell }(x,y)}$${\displaystyle {\text{поли}}(\ell ,|x|,|y|)}$
2. Ни один вероятностный алгоритм с полиномиальным временем не сможет при достаточно большом отобразить входные данные и найти значение , такое, что с вероятностью, большей, чем пренебрежимо мала.${\displaystyle \ell }$${\displaystyle \ell \in \mathbb {Z} ,(x,y)\in X_{\ell }\times Y_{\ell },y'\in Y_{\ell }}$${\displaystyle x'\in X_{\ell }}$${\displaystyle h_{\ell }(x,y)=h_{\ell }(x',y')}$
3. Для всех имеем . (Функция, удовлетворяющая этому свойству, называется квазикоммутативной .)${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y_{1},y_{2}\in Y_{\ell }}$${\displaystyle h(h(x,y_{1}),y_{2})=h(h(x,y_{2}),y_{1})}$

(С помощью первых двух свойств можно восстановить обычное определение криптографической хеш-функции.)

Из такой функции определяется «накопленный хэш» набора и начальное значение относительно значения . Результат не зависит от порядка элементов, поскольку является квазикоммутативным. ^{[1] [2]}${\displaystyle \{y_{1},\dots,y_{m}\}}$${\displaystyle x}$${\displaystyle z}$${\displaystyle h(h(\cdots h(h(x,y_{1}),y_{2}),\dots ,y_{m-1}),y_{m})}$${\displaystyle y_{1},y_{2},...,y_{n}}$${\displaystyle ч}$

Если принадлежат некоторым пользователям криптосистемы, то каждый может вычислить накопленное значение Также пользователь может вычислить частичное накопленное значение . Затем, Таким образом , пользователь может предоставить пару любой другой части, чтобы аутентифицировать .${\displaystyle y_{1},y_{2},...,y_{n}}$${\displaystyle з.}$${\displaystyle y_{i}}$${\displaystyle z_{i}}$${\displaystyle (y_{1},...,y_{i-1},y_{i+1},...,y_{n})}$${\ displaystyle h (z_ {i}, y_ {i}) = z.}$${\displaystyle i-}$${\displaystyle (z_{i},y_{i})}$${\displaystyle y_{i}}$

Базовая функциональность квазикоммутативной хэш-функции не следует непосредственно из определения. Чтобы исправить это, Барич и Пфицманн дали немного более общее определение, которое представляет собой понятие схемы аккумулятора , состоящей из следующих компонентов: ^{[2] [3]}

1. Gen: вероятностный алгоритм, который принимает два параметра (параметр безопасности и количество значений, которые могут быть безопасно накоплены, соответственно) и возвращает соответствующий ключ .${\displaystyle \лямбда ,N}$${\displaystyle к}$
2. Eval: вероятностный алгоритм, который принимает ключ и набор накопления , где , и возвращает накопленное значение и вспомогательную информацию . Мы настаиваем на том, что Eval должен быть детерминированным для .${\displaystyle к}$${\displaystyle Y:=\{y_{1},\dots,y_{N'}\}}$${\displaystyle N'\leq N}$${\displaystyle z}$${\displaystyle aux}$${\displaystyle z}$
3. Wit: вероятностный алгоритм, который принимает ключ , значение , накопленное значение некоторого набора и некоторую вспомогательную информацию и возвращает либо свидетельство , либо специальный символ . Мы настаиваем, что если , то Wit возвращает свидетельство, а в противном случае Wit возвращает .${\displaystyle к}$${\displaystyle у}$${\displaystyle z}$${\displaystyle Y}$${\displaystyle aux}$${\displaystyle w}$${\displaystyle \bot}$${\displaystyle y\in L}$${\displaystyle \bot}$
4. Ver: детерминированный алгоритм, который принимает key , value , witness и collected value и возвращает значение Yes/No. Мы настаиваем на том, что если был сгенерирован из запуска Wit на кортеже , где был сгенерирован из запуска Eval на некотором , и где был выбран произвольно и был выбран из запуска Gen, то Ver всегда возвращает Yes.${\displaystyle к}$${\displaystyle у}$${\displaystyle w}$${\displaystyle z}$${\displaystyle w}$${\displaystyle (k,y,z,aux)}$${\displaystyle z,вспомогательный}$${\displaystyle к,Л}$${\displaystyle L}$${\displaystyle к}$

Сравнительно легко увидеть, что можно определить схему накопителя из любой квазикоммутативной хэш-функции, используя технику, показанную выше. ^[2]

Можно заметить, что для многих приложений набор накопленных значений будет меняться много раз. Наивно, можно было бы полностью переделывать расчет аккумулятора каждый раз; однако это может быть неэффективно, особенно если наш набор очень большой, а изменение очень мало. Чтобы формализовать эту интуицию, Камениш и Лисянская определили динамическую схему аккумулятора , состоящую из 4 компонентов обычной схемы аккумулятора, плюс еще три: ^{[2] [4]}

1. Add: (возможно, вероятностный) алгоритм, который принимает ключ , накопленное значение и другое значение для накопления , и возвращает новое накопленное значение и вспомогательную информацию . Мы настаиваем на том, что если было сгенерировано путем накопления некоторого набора , то должно быть так, как если бы оно было сгенерировано путем накопления набора .${\displaystyle к}$${\displaystyle z}$${\displaystyle у}$${\displaystyle z'}$${\displaystyle aux}$${\displaystyle z}$${\displaystyle L}$${\displaystyle z'}$${\displaystyle L\чашка \{y\}}$
2. Del: (возможно, вероятностный) алгоритм, который принимает ключ , накопленное значение и другое значение для накопления , и возвращает новое накопленное значение и вспомогательную информацию . Мы настаиваем на том, что если было сгенерировано путем накопления некоторого набора , то должно быть так, как если бы оно было сгенерировано путем накопления набора .${\displaystyle к}$${\displaystyle z}$${\displaystyle у}$${\displaystyle z'}$${\displaystyle aux}$${\displaystyle z}$${\displaystyle L}$${\displaystyle z'}$${\displaystyle L\обратная косая черта \{y\}}$
3. Upd: детерминированный алгоритм, который принимает ключ , значение , свидетельство , накопленное значение и вспомогательную информацию и возвращает нового свидетеля . Мы настаиваем на том, что если был сгенерирован Gen, является частью набора , является свидетелем для членства в и является накопленным значением для и был сгенерирован запуском Add или Del, то будет свидетелем для членства в новом наборе.${\displaystyle к}$${\displaystyle у}$${\displaystyle w}$${\displaystyle z}$${\displaystyle aux}$${\displaystyle w'}$${\displaystyle к}$${\displaystyle у}$${\displaystyle L}$${\displaystyle w}$${\displaystyle у}$${\displaystyle L}$${\displaystyle z}$${\displaystyle L}$${\displaystyle aux}$${\displaystyle w'}$${\displaystyle у}$

Фацио и Николоси отмечают, что поскольку Add, Del и Upd можно смоделировать путем повторного запуска Eval и Wit, это определение не добавляет никакой принципиально новой функциональности. ^[2]

Одним из примеров является умножение больших простых чисел . Это криптографический аккумулятор, поскольку требуется суперполиномиальное время для факторизации составного числа (по крайней мере, согласно гипотезе), но требуется лишь небольшое количество времени (полиномиальное по размеру), чтобы разделить простое число на целое число, проверить, является ли оно одним из множителей, и/или вынести его за скобки. Новые члены могут быть добавлены или вычтены из набора множителей путем умножения или вынесения за скобки числа соответственно. В этой системе два аккумулятора, накопившие одно общее простое число, могут тривиально обнаружить его, вычислив свой НОД, даже без предварительного знания простого числа (что в противном случае потребовало бы разложения аккумулятора на простые множители для его обнаружения). ^{[ необходима цитата ]}

Более практичные накопители используют квазикоммутативную хэш-функцию, так что размер накопителя не растет с числом членов. Например, Бенало и де Мар предлагают криптографический накопитель, вдохновленный RSA : квазикоммутативная функция для некоторого составного числа . Они рекомендуют выбирать жесткое целое число (т. е. произведение двух безопасных простых чисел ). ^[1] Барич и Пфицманн предложили вариант, где было ограничено быть простым числом и не более (эта константа очень близка к , но не дает утечки информации о разложении на простые множители ). ^{[2] [3]}${\displaystyle h(x,y):=x^{y}{\pmod {n}}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle у}$${\displaystyle n/4}$${\displaystyle \фи (н)}$${\displaystyle n}$

Дэвид Наккаш заметил в 1993 году, что является квазикоммутативным для всех констант , обобщая предыдущий криптографический аккумулятор, вдохновленный RSA. Наккаш также отметил, что полиномы Диксона являются квазикоммутативными в степени, но неизвестно, является ли это семейство функций односторонним. ^[1]${\displaystyle e_{n,c}(x,y):=x^{y}c^{y-1}{\pmod {n}}}$${\displaystyle с,н}$

В 1996 году Ниберг построил аккумулятор, который является доказуемо информационно-теоретически безопасным в модели случайного оракула . ​​Выбрав некоторый верхний предел для количества элементов, которые могут быть безопасно накоплены, и параметр безопасности, определите константу как целое число, кратное (так, чтобы можно было записать ), и пусть будет некоторой криптографически безопасной хэш-функцией . Выберите ключ как случайную -битовую битовую строку. Затем, чтобы накопить с помощью схемы Ниберга, используйте квазикоммутативную хэш-функцию , где - побитовая и операция , а - функция, которая интерпретирует свой вход как последовательность -битовых битовых строк длины , заменяет каждую битовую строку, состоящую из всех нулей, на один 0, а каждую другую битовую строку - на 1, и выводит результат. ^{[2] [5]}${\displaystyle N=2^{d}}$${\displaystyle \лямбда}$${\displaystyle \ell :\approx {\frac {e}{\log _{2}(e)}}\lambda N\log _{2}(N)}$${\displaystyle д}$${\displaystyle \ell =rd}$${\displaystyle H:\{0,1\}^{*}\to \{0,1\}^{\ell }}$${\displaystyle к}$${\displaystyle r}$${\displaystyle h(x,y):=x\odot \alpha _{r}(H(y))}$${\displaystyle \odot}$${\displaystyle \alpha _{r}:\{0,1\}^{\ell }\to \{0,1\}^{r}}$${\displaystyle д}$${\displaystyle r}$

Этот раздел нуждается в расширении . Вы можете помочь, дополнив его. ( Май 2021 )

Хабер и Сторнетта показали в 1990 году, что аккумуляторы могут использоваться для временной отметки документов посредством криптографической цепочки. (Эта концепция предвосхищает современное понятие криптографического блокчейна .) ^{[1] [2] [6]} Беналох и де Маре предложили альтернативную схему в 1991 году, основанную на дискретизации времени в раунды. ^{[1] [7]}

Бенало и де Маре показали, что накопители могут использоваться для того, чтобы большая группа людей могла узнавать друг друга в более позднее время (что Фацио и Николоси называют ситуацией «депонирования идентификаторов»). Каждый человек выбирает представляющий его личность, и группа коллективно выбирает публичный накопитель и секрет . Затем группа публикует или сохраняет хэш-функцию и накопленный хэш всех идентификаторов группы относительно секретного и публичного накопителя; одновременно каждый член группы сохраняет как свое значение идентичности , так и накопленный хэш всех идентификаторов группы, за исключением члена . (Если большая группа людей не доверяет друг другу или если накопитель имеет криптографический лазейку, как в случае накопителя, вдохновленного RSA, то они могут вычислить накопленные хеши с помощью безопасного многостороннего вычисления .) Чтобы позже убедиться, что заявленный член действительно принадлежал к группе, они представляют свою личность и личный накопленный хэш (или доказательство с нулевым разглашением этого); Накапливая идентификационные данные заявленного участника и проверяя их по накопленному хешу всей группы, любой может проверить участника группы. ^{[1] [2]} Благодаря схеме динамического аккумулятора впоследствии становится еще проще добавлять или удалять участников. ^{[2] [4]}${\displaystyle у}$${\displaystyle ч}$${\displaystyle x}$${\displaystyle x}$${\displaystyle у}$

Криптографические накопители также могут использоваться для построения других криптографически безопасных структур данных :

• Барич и Пфицманн показывают, что можно построить отказоустойчивые сигнатуры с постоянным пространством, используя свойство сжатия. ^{[2] [3]}
• Гудрич и др. создали эффективный, динамический аутентифицированный словарь, не учитывающий размер (который позволяет ненадежным каталогам давать криптографически проверяемые ответы на запросы о членстве). ^{[2] [8]}
• Папамантхоу и др. построили криптографически безопасную хеш-таблицу , функциональность которой может быть аутентифицирована при удаленном хранении. ^[9]

Концепция вновь получила интерес из-за дополнения Zerocoin к биткойну , которое использует криптографические накопители для устранения отслеживаемой связи в блокчейне биткойна, что сделало бы транзакции анонимными и более приватными. ^{[10] [11] [12]} Более конкретно, чтобы отчеканить (создать) Zerocoin, нужно опубликовать монету и криптографическое обязательство по серийному номеру с секретным случайным значением (которое примут все пользователи, если оно будет правильно отформатировано); чтобы потратить (вернуть) Zerocoin, нужно опубликовать серийный номер Zerocoin вместе с неинтерактивным доказательством с нулевым разглашением , что вам известно о каком-то опубликованном обязательстве, которое относится к заявленному серийному номеру, а затем потребовать монету (которую примут все пользователи, если NIZKP действителен, а серийный номер ранее не появлялся). ^{[10] [11]} После первоначального предложения Zerocoin, на смену ему пришел протокол Zerocash , и в настоящее время он разрабатывается в Zcash , цифровую валюту, основанную на кодовой базе Bitcoin. ^{[13] [14]}

• Криптография
• Доказательство с нулевым разглашением