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

Чтобы узнать о других значениях, см. Аккумулятор (значения) .

В криптографии аккумулятор представляет собой одностороннюю членства хеш-функцию . Это позволяет пользователям подтверждать, что потенциальные кандидаты являются членами определенной группы, не раскрывая отдельных членов группы. Эта концепция была официально представлена ​​Джошем Бенало и Майклом де Маре в 1993 году.

Формальные определения

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

Бенало и де Маре (1993)

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

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

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

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

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

Барич и Пфицманн (1997)

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

1. Gen: вероятностный алгоритм, принимающий два параметра. $\lambda ,N$ (параметр безопасности и количество значений, которые можно безопасно накапливать соответственно) и возвращает соответствующий ключ $k$.
2. Eval: вероятностный алгоритм, принимающий ключ. $k$ и накопительный набор $Y:=\{y_{1},\dots ,y_{N'}\}$, где $N'\leq N$и возвращая накопленное значение $z$ и вспомогательная информация $aux$. Мы настаиваем на том, что Eval должен быть детерминированным для $z$.
3. Острословие: вероятностный алгоритм, принимающий ключ. $k$, значение $y$, накопленное значение $z$ из какого-то набора $Y$и некоторая вспомогательная информация $aux$и возвращает либо свидетель $w$ или специальный символ $\bot$. Мы настаиваем на том, что если $y\in L$, что Вит возвращает свидетеля, и что Вит в противном случае возвращает $\bot$.
4. Версия: детерминированный алгоритм, принимающий ключ. $k$, значение $y$, свидетель $w$, и накопленное значение $z$и возвращает значение Да/Нет. Мы настаиваем на том, что если $w$ был сгенерирован в результате запуска Wit в кортеже $(k,y,z,aux)$, где $z,aux$ были созданы в результате запуска Eval на некоторых $k,L$, и где $L$ был выбран произвольно и $k$ был выбран из числа работающих Gen, поэтому Вер всегда возвращал Yes.

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

Камениш и Лысянская (2002)

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

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

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

Примеры

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

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

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

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

Приложения

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

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

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

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

Эта концепция получила новый интерес благодаря Zerocoin дополнению к биткойнам , которое использует криптографические аккумуляторы для устранения отслеживаемых связей в блокчейне биткойнов, что сделает транзакции анонимными и более конфиденциальными. Более конкретно, чтобы отчеканить (создать) Zerocoin, необходимо опубликовать монету и криптографическое обязательство по серийному номеру с секретным случайным значением (которое примут все пользователи, если оно правильно отформатировано); Чтобы потратить (вернуть) Zerocoin, нужно опубликовать серийный номер Zerocoin вместе с неинтерактивным доказательством с нулевым разглашением того, что им известно о каком-то опубликованном обязательстве, которое относится к заявленному серийному номеру, а затем заявить о своей монете (которую все пользователи примут как до тех пор, пока НИЗКП действителен и серийный номер не появился ранее). С момента первоначального предложения Zerocoin на смену ему пришел протокол Zerocash , и в настоящее время он развивается в Zcash , полноценный протокол. цифровая валюта.

См. также

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