Система групповой цифровой подписи с использованием решеток

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:05, 26 октября 2015.


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


A Group Signature Scheme from Lattice Assumptions
Cover.PNG
Авторы S. Dov Gordon [@: 1],

Jonathan Katz [@: 2]and
Vinod Vaikuntanathan [@: 3]

Опубликован 2010 г.
Сайт оригинал
Перевели Alexander Sosenko
Год перевода 2015 г.
Скачать оригинал


Введение

Системы групповой цифровой подписи [1] позволяют пользователям подписывать сообщения от имени группы, администрируемой каким-то менеджером. Для создания группы менеджер должен сгенерировать групповой публичный и секретный мастер-ключи. При вступлении в группу, пользователь получает личный секретный ключ, который является производным от секретного мастер-ключа. Член группы может подписать сообщение, используя свою личный секретный ключ, что позволяет любому, кто знает публичный мастер-ключ убедиться, что некоторый член группы подписал сообщение. Грубо говоря, система групповой цифровой подписи обязана удовлетворять двум, казалось бы, противоречивым требованиям: зная валидную цифровую подпись σ, менеджер группы должен быть в состоянии определить, кому из членов группы принадлежит σ (возможность вычисления отправителя), но никто, кроме менеджера группы не должен быть в состоянии определить, какую-либо информацию о подписавшем (анонимность). Система групповой цифровой подписи оказалась популярным примитивом, к тому же было предложено несколько их конструкций: со случайным оракулом [2] [3] [4] [5] [6] [7] и без него [8] [9] [10] [11] [12] [13] .
В то время как существуют конструкции систем групповой цифровой подписи на основе односторонних перестановок [8][9] такие схемы служат лишь в качестве доказательств целесообразности концепции и далеки от практического применения. С другой стороны, схемы, пригодные на практике, основаны на сравнительно небольшом наборе гипотез, а именно: гипотеза о неразрешимости задачи взлома RSA [2][3][4] [7] и различные гипотезы, связанные с группами, имеющими ассоциативное билинейное отображение [5][6][10][11][12][13] .
В этой работе мы демонстрируем первую конструкцию системы групповой цифровой подписи на основе гипотез, связанных с решетками. Использование решеток в криптография популярно в последние годы. В частности, это связано с общим желанием расширить набор гипотез, на которых могут основываться криптосистемы (т.е. выйти за пределы стандартного набора гипотез, связанных с вычислительной сложностью факторизации и решения задачи дискретного логарифмирования). Опираясь на гипотезы о решетках можно получить несколько конкретных преимуществ: известные оценки для наихудшего/среднего случая решения решетчатых задач, а также стойкость решеток в настоящее момент к квантовым атаки. Даже ограничиваясь классическими атаками, наиболее известные алгоритмы для решения некоторых задач на решетках требуют экспоненциального времени (в отличие от суб-экспоненциальных алгоритмов известны, например, для факторизации). Наконец, опираясь на решетки можно прийти к эффективной конструкции, потому что основные операции на решетках оперируют с относительно небольшими цифрами и по своей сути хорошо распараллеливаются. В то время как полученная нами конструкция менее эффективна, чем существующие, основанные на теоретико-числовых предположениях, конструкции, она значительно более эффективна чем подходы [8][9] которые полагаются на NIZK-доказательства, основанные на редукции Карпа в каком-то NP-полном языке. (Peikert и Vaikuntanathan [14] произвели NIZK-доказательства для конкретных задач на решетках, однако их результаты не могут быть напрямую задействованы в нашей работе.)

Наши техники

Наша конструкция сочетает идеи нескольких работ,связывая их вместе, используя новый метод, описанный ниже. В крупную клетку, наша система подобна (но не полностью) на то, что описал Bellare et al. [8]. Публичный мастер-ключ включает в себя публичный ключ для криптосистемы с открытым ключом, на ряду с ключами для подтверждения подписи . Личный секретный ключ, выданный -тому члену это , он отвечает открытому ключу . Чтобы подписать сообщение , член группы подписывает используя ; шифруя полученную подпись, используя ; а потом предоставляет NIZK-доказательство о целостности (что пересланный шифротекст - это зашифрованная одним из секретных ключей цифровая подпись сообщения). Это обеспечивает анонимность (никто кроме менеджера группы не знает закрытого ключа отвечающего ), но обеспечивает возможность вычислить субъекта, подписавшего сообщение, т.к. менеджер группы может дешифровать шифротекст, который является частью каждой вылидной групповой цифровой подписи.
Чтобы создать конкретную систему а основе решеток, использующую этот подход, мы должны определить систему цифровой подписи и шифрования с подходящими характеристиками. В то время как нынешние конструкции, основанные на решетках, не имеют конструкции NIZK-доказательств для всего NP, основанные на гипотезах, связанных с решетками , и мы должны адаптировать нашу схему так что она сможет рассчитывать на эффективные NIZK-доказательства для некоторых конкретных языков. Это будет объяснено более подробно в дальнейшем.
В качестве системы цифровой подписи мы решили использовать систему GPV [15]. Открытый ключ - это базис для случайной решетки. Чтобы подписать сообщение , используется односторонняя функция чтобы найти кратчайший вектор и (где это hash-функция, моделируемая случайным оракулом).Соответственно, найти этот вектор без односторонней функции очень сложно.
Полученную подпись мы шифруем используя нестандартный вариант криптосистемы Regev [16]. Имея матрицу (открытый ключ), мы шифруем выбирая случайный вектор и получая шифротекст . Фактически, используется в качестве шума в соответствии с проблемой обучения с ошибками [16]. Before going further, we stress that this “encryption scheme” is not semantically secure. However, it turns out that we need something much weaker than semantic security in order to prove anonymity of our scheme; roughly, all we need is that the encryption of a uniformly random Прежде чем идти дальше, мы подчеркиваем, что эта "схема шифрования" является семантически опасной. Тем не менее, оказывается, что нам нужно что-то гораздо более слабое, чем семантическая безопасность для того, чтобы доказать анонимность нашей схемы; грубо говоря, все, что нам нужно - это то, что шифрование ведется с равномерно случайным вычислительно неопределимо исходя из шифротекстов. Мы перенесем дальнейшее обсуждение этого на часть 3.
Как было описано ранее открытый мастер-ключ состоит из личных открытых ключей наряду с ключом для шифрования ;подпись будет включать в себя , где такой что для любого , а также NIZK-доказательство о валидности . Построение NIZK-доказательства поворачивает нас к самой сложной части нашей работы, будет полезным немного модифицировать нашу схему чтобы было легче строить NIZK-доказательства. (Делая так мы полагаемся на некоторые специфические особенности GPV.) Мы изменили нашу систему так: Теперь открытый мастер-ключ содержит подтверждающих ключей (как раньше) и еще шифрующих ключей . Чтобы подписать сообщение , пользователь вычисляет подпись (используя одностороннюю функцию, соответствующую ) и “псевдо-подписи” для всех . Каждая “псевдо-подпись” имеет свойство, что , однако не короткие (и поэтому не подходят для цифровой подписи). Все зашифрованы как раньше, т.е. каждый зашифрован, используя чтобы получить . Далее пользователь должен предоставить доказательство , что каждый шифрует валидную подпись в соответствии с , и хотя бы одна их псевдо-подписей короткая (является валидной). Подробгее будет рассказано далее.
Чтобы доказать, что каждый шифротекст шифрует псевдо-подпись, мы разработали новый метод: способ выбрать базис для ортогональной решетки, связанной с односторонней функцией. А именно, показал метод который по данной матрице , дает такой что и - “хорошая односторонняя функция” (подходящая для GPV) для A. Если мы используем матрицы в качестве подтверждающих ключей, тогда оказывется возможным подтвердить, что данный шифротекст шифрует "псевдо-подпись", соответствующую проверяя . Это работает, т.к.


по построению.
Последнее, что мы должны сделать - доказать, что хотя бы один шифрует короткий вектор. Это эквивалентно доказательству того, что хотя бы один из векторов близок к решетке, построенной по колонкам . Это можно проделать, используя статистический протокол с нулевым знанием, продемонстрированный Micciancio и Vadhan [17] , вместе со стандартными техниками [18] [19].
По сути, мы получаем повышение эффективности за счет сочетания вместе шифрования и подписи так, что NIZK-доказательства, могут быть получены очень просто.

Обобщение

Мы введем немного обозначений и рассмотрим необходимы понятия о решетках в части 2. Для читателя, который знаком с решетками интереснее всего будет прочесть:

  • В части 2.2 (см. Лемма 1) и далее, мы рассматриваем проблему обучения с ошибками с нестандартным распределением ошибок. К счастью , недавний результат Peikert [20] показал сложность этой проблемы.
  • В части 2.4 мы описываем технику выбора базиса в ортогональной решетке с односторонней функцией.


Мы переходим к групповой цифровой подписи в части 3. Мы рассматриваем стандартные определения безопасности для групповой цифровой подписи в части 3.1, описывая нашу конструкцию в части 3.2, и доказывая ее анонимность и возможность вычисления отправителя в частях 3.3 и 3.4.

Предварительно о решетках

Поскольку, мы берем как параметр, отвечающий за безопасность, остальные параметры должны быть функциями от . Когда мы говорим, "статистически близко" мы подразумеваем "разница незначительно по сравнению с .”
Мы рассмотрим некоторые основные свойства решеток, используемые далее. В этот раздел входит в основном объяснения обозначений и основных идей, также и мы даем в этом разделе ссылки на работы понимание которых важно для дальнейшего изложения.
Мы используем маленькие буквы (например, ) для обозначения векторов, и большие буквы (например, ) для обозначения матриц. (Вектора в нашей работе - это всегда вектора-столбцы.) Пусть обозначает Евклидову (например, ℓ2) норму вектора , и пусть обозначает максимальную Евклидову норму по столбцам ; например, если тогда . Если , тогда обозначает округление до ближайшего целого.
Для целого, обозначает группу вычетов по модулю . Мы расширим модульное исчисление на действительные числа очевидным способом: например, для и используем для представления уникального действительного числа такого что целое кратное. Наконец, мы определим понятие расстояния между элементами в естественным способом: даны , расстояние между ними определено отображением в множество целых чисел и затем остается лишь взять результат по модулю.
Зафиксируем при данной матрице , определим m-размерную решетку как для . Определим ортогональную решетку как . (Отметим, что понятие ортогональной решетки было определено немного иначе в предыдущих работах.) Наконец, для вектора определим

.

Другими словами, это расстояние до от решетки, натянутой на столбы.

Гауссовы функции ошибок

Одномерное (непрерывное) распределение Гаусса над , с параметрами определено плотностью распределения

.


В этой работе мы всегда используем обрезанное распределение Гаусса, то есть распределение Гаусса которое ограничено такими, что . Обрезанное и полное распределения Гаусса статистически близки, и мы выбросим слово "обрезанное" из описаний далее. M-размерное непрерывное распределение Гаусса определено похожим способом, через плотность распределения . Наконец, обозначим m-размерное непрерывное распределение Гаусса центрованное в точке , например, .
Пусть - решетка. Дискретное распределение Гаусса это m-размерное распределение Гаусса, центрованное в , но ограниченное решеткой. (Мы пишем как сокращение для .) Формально, плотность распределения дискретного распределения Гаусса определена как

.

Gentry et al. [15] показал, что при заданном базисе для , это распределение может быть упрощено (в рамках незначительных статистических отклонений) для .

Проблема обучение с ошибками

Проблема “Обучения с ошибками” () была впервые рассмотрена Regev [16] как обобщение проблемы “обучения с шумом”. Мы объясняем эту проблему в форме, применимой в нашей статье.
Зафиксируем положительное целое , целые числа и , вектор , и вероятностное распределение на интервале . Определим два следующих распределения над :

  • это распределение, полученное выбором равномерной матрицы , выбирая , получая .
  • это распределение, полученное выбором равномерной матрицы и равномерного вектора , получая .


Проблема принятия решений в условиях (относительно распределения ) может быть определена как проблема различения и для равномерного . Формально, для , и </math>\chi</math>, которые могут зависеть от (рассматриваемое теперь как параметр безопасности) мы говорим, что проблема сложна, если следующее утверждение является незначительным для любого полиномиального вероятностного алгоритма :

.


Обычно для подразумевается распределение ошибок над опрделенное как: Выборка чиссел , пусть , и получим . Мы пишем как сокращение для .
Понимание сложности приходит из результата Regev [16], который предложил квантовое сокращение для приближения некоторых проблем над решетками в пределах над n-размерными решетками в худшем случае для решения , при условии, что that. Недавно Peikert [21] проделал классическое сокращение с такими же параметрами. Для наших целей отметим, что считается сложной — учитывая состояние современных алгоритмов над решетками — для любого и (с учетом вышесказанного).
Второе распределение ошибок для — и одно из тех, что будут использоваться в этой работе — дискретное Гауссово распределение . Хотя это распределение может показаться похожим на дискретизированное (округленное) , это распределение статистически далеко от него и поэтому мы можем немедленно сделать заключение относительно сложности с использованием первого распределения исходя из сложности с использованием второго. К счастью, недавний результат Peikert [20] может быть использован чтобы показать, что сложность с распределением ошибок обуславливается сложностью с распределением ошибок . Мы пишем как сокращение для .

TemplateTheoremIcon.svg Теорема Лемма 1
Для любого , сложность определяется сложностью .
Доказательство

Мы покажем эффективную трансформацию которая берет на вход </math>(A, y) \in \Z^{n\times m}_q \times [0, q)^m и имеет следующие свойства:

  • Если равномерен над тогда получим равномерен над .
  • Если распределен в соответствии с тогда распределен в соответствии с .


Лемма следует сразу же из этих двух свойств.
Трансформация работает так как следует. По данному , она выбирает вектор и выдает пару .
Во-первых, распределен равномерно над . Заметим, что всегда целое, и распределение зависит только от дробной части каждого элемента вектора . Из этого следует, что распределен равномерно над .
С другой стороны, где . Пока мы имеем , выбор эквивалентен выбору. Недавняя теорема (Теорема 3.1) Peikert [20] показывает, что два следующих процесса дают статистически близкие распределения:

  • Выбор и затем установка ;
  • Выбор .
Мы получили, что распределен также как и .


Односторонние функции и система цифровой подписи GPV

Ajtai [22] и Alwen and Peikert [23] показали алгоритмы, которые генерируют почти равномерные матрицы с матрицей односторонней функции удовлетворяющей следующим условиям:

TemplateTheoremIcon.svg Теорема Лемма 2 ([3])
Есть вероятностный полиномиальный алгоритм TrapSamp, который по входу с и , получим матрицу и такие что:
  • Распределение , как следует из применения TrapSamp, статистически близкое к равномерному над ,
  • столбцы из базиса решетки , подразумевая ,
  • .
Доказательство
Без доказательства

Дан “объект LWE” для “короткого” вектора , знание может быть использовано для восстановления . Особенно, если (что гарантировано Леммой 2) и получен из для , тогда может быть легко восстановлен. Это делается путем вычисления

.

Т.к. и содержат только “маленькие” элементы, каждый элемент вектора меньше чем и поэтому равна (в целых числах). Умножение дает , после чего очень просто восстановить .

TemplateDifinitionIcon.svg Определение «Система цифровой подписи GPV.»
Gentry, Peikert, и Vaikuntanathan [15] показали как использовать процедуру отбора односторонних функций, описанную выше, чтобы построить

одностороннюю перво-выборочную функцию. Это может быть применено в системе цифровой подписи с помощью "FDH-подобных" конструкций [24]. (См. [15] для формального определения перво-выборочной функции и для построения системы цифровой подписи.) Здесь мы перво-выборочная функция работает.
Возьмем , , и . Односторонняя перво-выборочная функция определена следующими алгоритмами:

  • исполняет чтобы получить . Матрица определяет функцию , с областью значений и областью определения. Сложность обращения с учетом области значений есть над областью значений.
  • Алгоритм обращения односторонних функций выбирает из следующим образом: во-первых, вычисляется (используя стандартную линейную алгебру) приблизительный такой что (за исключением незначительной дробной части , такой что всегда существует). Тогда выбирается и получим .

Gentry et al. показал, что сказанное выше является односторонним алгоритмом если сложен для полиномиальной аппроксимации с фактором .

Выбор базиса ортогональной решетки с односторонней функцией

Мы показали вариант выбора односторонней функции в Лемме 2. В нашем варианте алгоритму на вход дополнительно подается матрица и на выход он должен выдавать матрицу с ассоциированной односторонней функцией с дополнительным требованием, что строки ортогональны (над ) строкам . Другими словами, мы требуем чтобы .
Описание конструкции. Здесь изложена основная идея нашей работы. Запишем как

,

где квадратная, обратимая матрица размерности . Затем с генерируем ортогональную матрицу за два шага. Мы с генерируем первый компонент Используя TrapSamp. Напомним, он возвращает матрицу, которая статистически близка к нормально распределенной, вместе с ассоциированной односторонней функцией . Как только мы выбрали вторая компонента ограничена условием, что ; поэтому мы генерируем решая указанное линейное уравнение.
Осталось только найти одностороннюю функцию такую что столбцы короткие и . Здесь мы опираемся на последние методы Cash et al. [25] , которые позволяют расширить базис до большего базиса для как объяснялось ранее. Детали следуют далее.

TemplateTheoremIcon.svg Теорема Лемма 3.
Существует вероятностный полиномиальный алгоритм который по входу и ) и матрице чьи столбцы охватывают , выдает матрицы и такие что:
  • . Более того, распределение статистически близко к нормальному над ,
  • столбцы образуют базис решетки , подразумевая ,
  • .
Доказательство
Пусть и . Запишем
,

где и . Где алгоритм Работает так:

  • Если строки не охватывают , выводит . Это происходит с незначительной вероятностью [26] [16]
  • Вычислим . Пусть нормальная случайно распределенная матрица, удовлетворяющая тому, что


(такая матрица существует, исходя из предположения, что строки охватывают ). Если столбцы не охватывают , выдается . Это происходит с незначительной вероятностью.

  • Расширим базис до базиса для используя методы Cash et al. [25]. Мы предоставляем их методы для полноты картины.


Пусть матрица вида

где произвольная матрица, удовлетворяющая , и единичная матрица. (Отметим, что существует исходя из предположения того, что столбцы охватывают .) Выдаем и .
Теперь проверим, что этот алгоритм удовлетворяет затребованным свойствам. Сначала заметим, что

.

Утверждение в отношении распределения непосредственно следует из построения. Мы также имеем

,
где последнее равенство выполнятся т.к. по свойствам , и по построению. Наконец, мы отсылаем читателя к работе Cash et al. [25] за доказательством того, что


Приведенное следствие получается из доказанного выше, и будет использовано для доказательства безопасности нашей системы.

TemplateDifinitionIcon.svg Определение « Следствие 1.»
Распределения

и

статистически близки.

NIWI доказательства необходимых фактов о решетках

Пусть и . В этом разделе мы кратко опишем, как можно построить NIWI доказательство (в модели случайного оракула) для языка определенного как:

Здесь, это набор точек, среди которых хотя бы одна близка к соответствующей решетке, и это набор точек, лежащих далеко от соответствующих решеток.
Наша отправная точка это система NIWI доказательств для для варианта задачи определения ближайшего вектора, т.е. для языка [27] [17]:

.
.

Наш язык может быт описан как OR нескольких ; т.е.,

.
.

Мы можем использовать метод Cramer, Damgard, и Schoenmakers [18] чтобы получить WI доказательство для с незначительными отклонениями. Используя преобразование Fiat-Shamir [28] , результирующий протокол может быть сделан неинтерактивным в модели случайного оракула.
Заметим, что для наших целей требуется только устойчивость (и не требуются чтобы система доказательств, была доказательством знаний) и свидетельство неразличимость (нулевое знание). Суть этого раздела отражена в следующей лемме.

TemplateTheoremIcon.svg Теорема Лемма 4.
. Существует система NIWI-доказательств для языка в модели случайного оракула, где длина доказательства есть bits.
Доказательство
Без доказательства


Система групповой цифровой подписи, основанная на решетках

Определения

Мы принимаем определение системы групповой цифровой подписи из работы Bellare, Micciancio, и Warinschi [8], с ослаблением, предложенным Boneh, Boyen, и Shacham [5] (рассматриваемую также в, e.g., [11]). Формально, система групповой цифровой подписи это набор из четырех полиномиальных алгоритмов, определенных следующим образом.

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

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

и ,

за исключением пренебрежимо малого количества случаев.
Система групповой цифровой подписи также должна, удовлетворять двум основным свойствам безопасности: анонимность и прослеживаемость. Анонимность означает, что без отслеживающего ключа должно быть невозможно, определить, какой из ленов группы подписал сообщение (даже учитывая что известны все персональные ключи членов группы). Bellare et al. [8] определил “CCAversion” этого понятия, где противнику предоставляется доступ к отслеживающему оракулу. После [5] мы используем “CPA-version” анонимности, где доступ к такому оракулу не дается.

TemplateDifinitionIcon.svg Определение «Определение 1.»
Система групповой цифровой подписи

анонимна, если для всех полиномиальных и всех вероятностных полиномиальных противников , преимущество в следующем эксперименте незначительно по сравнению с :

  • Вычислим и дадим противнику .
  • выдает две личности , вместе с сообщением . Случайный бит выбирается, и получает . Наконец, выдает бит .
успешен(обозначается если , и преимущество есть .

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

TemplateDifinitionIcon.svg Определение « Определение 2.»
Система групповой цифровой подписи

прослеживаема, если для всех полиномиальных и вероятностно полиномиальных противников , вероятность успешности в следующем эксперименте незначительна по сравнению с :

  • Вычислим и дадим и противнику .
  • может запрашивать следующих оракулов как захочет:
    • оракул, который по выдает .
    • оракул, которых по выдает .
Пусть это набор личностей запрошенных у .
  • В какой-то момент выдает сообщение и подпись .

успешен, если (1) и (2) никогда не запрашивались для

и еще (3) .

Описание системы

Пусть - параметр безопасности, , и - параметры системы. Пусть - hash-функция, моделируемая случайным оракулом.

: Сначала вычислим потом, для , вычислим .
Выдадим как открытый ключ, как отслеживающий ключ, и закрытые ключи пользователей.


: Чтобы подписать сообщение используя секретный ключ , выберем случайное , установим , и вычислим для . Потом:
  • Вычислим .
  • Для <for i \neq j</math>, выберем равномерное при условии, что .
Для всех , выберем и вычислим . Наконец построим NIWI-доказательство для языкаfor the языка как обсуждалось в Разделе 2.5 (и используя свидетеля ). Выдадим подпись .


: Разберем подпись как и установим . Выдадим если доказательство верно, и для каждого .


: Разберем подпись как . Используя , выдадим наименьший индекс для которого .

Сначала проверим корректность. Пусть - подпись, сгенерированная честным пользователем. Ясно, что - валидное доказательство. К тому же, для любого мы имеем

,

таким образом, подтверждение завершено. Корректность вскрывающего алгоритма следует просто.

TemplateTheoremIcon.svg Теорема Теорема 1.
Пусть , , и такие, как описано выше. Если сложна для , и система доказательств неотличима по свидетелям, тогда система групповой цифровой подписи, описанная выше анонимна. Если сложна для , тогда система групповой цифровой подписи, описанная выше прослеживаемая.
Доказательство
Без доказательства.

Отметим, что для значений , как описано выше, сложность обуловлена сложностью поиска квантового алгоритма для приближения для [16], таким образом, наша система может быть основана на сложности поиска квантового алгоритма для .
Мы докажем анонимность в Разделе 3.3 и прослеживаемость в Разделе 3.4.

Анонимность

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

TemplateTheoremIcon.svg Теорема Утверждение
Если проблема сложна, тогда и вычислительно неразличимы.
Доказательство

Напомним (см. Лемма 1), что сложность обуславливает сложность . Используем чтобы построить алгоритм для . дается в качестве входа , где равномерен и также равномерен или равен для .
выбирает случайный индекс и устанавливает . Для всех , выбирается равномерно случайным образом. Потом для алгоритм вычисляет . Дается и противнику . На все H-запросы отвечают случайными элементами с допустимыми значениями.
В итоге выдает две личности наряду с сообщением . Если тогда выводит случайный бит и прерывается. В противном случае, создает подпись, выбирая случайным образом и фиксируя (Значение для выбирается равномерно.) Тогда вычисляет и, для , выбирается равномерно при условии, что . ( явно не вычисляет все значения .) Для , шифротекст вычисляется как в и . Однако, устанавливает .
Пусть обозначает предыдущий эксперимент, когда выходные данные - - распределены равномерно. Мы утверждаем, что вид в статистически близок к его виду в .
Действительно:

  • В мы имеем выбранный равномерно в ; тогда выбран равномерно в соответствии с ; и наконец .
  • В мы имеем для , выбранного равномерно в ; тогда .

Чтобы увидеть, что эти два объекта статистически близки, мы покажем, что выбор в статистически близок к равномерному над . Мы видим как функцию из , и заметим, что эта функция регулярна. Кроме того, поскольку столбцы охватывают все за исключением незначительного числа случаев (в зависимости от выбора), наш случайно выбранный равномерен над образом . Для регулярной функции, выбор элемент из образа, идущего перед элементом из прообраза, эквивалентно выбору элемента из области значений, как это сделано в.
С другой стороны, пусть обозначает предыдущий эксперимент, когда входные данные - - распределены в соответствии с для . Мы утверждаем, что вид в статистически близок к его виду в .
Действительно:

  • В эксперименте мы имеем , выбранный равномерно в . Затем мы вычисляем ; и наконец .
  • В мы имеем для ; тогда .


Сказанное выше, как легко видеть, статистически близко для наших параметров, снова с учетом результатов [15]. Поскольку вероятность, что не прервется есть , и его решение прерваться не зависит от успеха , доказательство завершено.


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

Возможность вычисления отправителя

Зафиксируем и пусть это противник, атакующий систему групповой цифровой подписи в соответствии с Определением 2. Построим лжеца для системы цифровой подписи GPV [15](в модели случайного оракула) вероятность успеха которого полиномиально зависит от . Поскольку система цифровой подписи GPV безопасна, предполагая сложность , это завершает доказательство.
Заметим сначала, что мы можем, без потери общности, предположить, что никогда не захватит всех пользователей т.к. может преупеть только лишь с незначительной вероятностью в этом случае. (Имея валидную подпись , обоснованность доказательства подразумевает, что выдаст несколько за исключением незначительного количества случаев.) Будем учитывать, это в дальнейшем.
получает открытый ключ для системы GPV, и начинает с выбора случайного индекса и установки . Затем, вычисляются значения . Для оставшихся индексов , лжец вычисляет значения и также как и в легитимном алгоритме. После этого дает и противнику . Отметим, что в соответствии со Следствием 1, распределение ключей является статистически близким к распределению, которое ожидается противником.
отвечает на запросы к случайному оракулу со стороны просто передавая эти запросы своему собственному случайному оракулу. отвечает на другие запросы следующим образом:

  • : если тогда дает противнику , как только прерывается.
  • : если тогда вычисляет подпись, используя и честный алгоритм подписи. Если , тогда:
  • выбирает случайный и запрашивает своего собственного оракула для подписи сообщения . В ответ он получает подпись .
  • Остальная часть подписи вычисляется с использованием честного алгоритма подписи. (Отметим, что вычисление единственный аспект подписания, который опирается на закрытый ключ пользователя.)

Пусть обозначает множество личностей запрошенных у . (Напомним, что если не прервался, тогда .) В какой-то момент выдаст сообщение и подпись . Предполагая, что , и что никогда не запрашивал . Поскольку имеет отслеживающий ключ , можно вычислить . Если тогда прерывается. Иначе, делает так:

  • Используем чтобы восстановить такой что:
  • , и
  • .
  • Выдаем лжеца .

Пусть обозначает вероятность, с которой преуспел в эксперименте по Определению 2. Легко увидеть, что прерывает с вероятностью не более и, условие непрерываемости это вид когда он выполняется как подпрограмма статистически близко к виду эксперимента, описанного в Определении 2. Поэтому вероятность как минимум для того, что выдаст с и , где никогда не запрашивался . Мы покажем, что когда бы это не произошло, тогда выдаст лжеца (скорее всего).
Зафиксируем такое что выполняется вышесказанное, и пусть . Поскольку , это обозначает, что будет действительно иметь возможность восстановить такой, что (1) и (2) . Более того, т.к. мы имеем ; т.к. это означает . Поэтому - валидное, отправленное при помощи системы GPV сообщение . Т.к. никогда не запрашивался , мы знаем, что никогда не запрашивал своего собственного подписывающего оракула для подписи . Из этого следует, что выход это действительный лжец.

Благодарности

Мы благодарим Chris Peikert за то что он указал нам, что результат из работы [20] может быть использован чтобы доказать Лемму 1.

Контакты авторов материала

  1. Dept. of Computer Science, University of Maryland, E-mail: gordon@cs.umd.edu
  2. Dept. of Computer Science, University of Maryland, E-mail: jkatz@cs.umd.edu
  3. Microsoft Research, Redmond, E-mail: vinod@microsoft.com

Литература

  1. David Chaum and Eug`ene van Heyst. Group signatures. In Advances in Cryptology — Eurocrypt ’91, volume 547 of LNCS, pages 257–265. Springer, 1991.
  2. 2,0 2,1 Giuseppe Ateniese, Jan Camenisch, Marc Joye, and Gene Tsudik. A practical and provably secure coalition-resistant group signature scheme. In Advances in Cryptology — Crypto 2000, volume 1880 of LNCS, pages 255–270. Springer, 2000.
  3. 3,0 3,1 Giuseppe Ateniese, Dawn Xiaodong Song, and Gene Tsudik. Quasi-efficient revocation in group signatures. In Financial Cryptography 2002, volume 2357 of LNCS, pages 183–197. Springer, 2002.
  4. 4,0 4,1 Jan Camenisch and Anna Lysyanskaya. Dynamic accumulators and application to efficient revocation of anonymous credentials. In Advances in Cryptology — Crypto 2002, volume 2442 of LNCS, pages 61–76. Springer, 2002.
  5. 5,0 5,1 5,2 5,3 Dan Boneh, Xavier Boyen, and Hovav Shacham. Short group signatures. In Advances in Cryptology — Crypto 2004, volume 3152 of LNCS, pages 41–55. Springer, 2004.
  6. 6,0 6,1 Jan Camenisch and Anna Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In Advances in Cryptology — Crypto 2004, volume 3152 of LNCS, pages 56–72. Springer, 2004.
  7. 7,0 7,1 Aggelos Kiayias and Moti Yung. Group signatures with efficient concurrent join. In Advances in Cryptology — Eurocrypt 2005, volume 3494 of LNCS, pages 198–214. Springer, 2005.
  8. 8,0 8,1 8,2 8,3 8,4 8,5 Mihir Bellare, Daniele Micciancio, and Bogdan Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In Advances in Cryptology — Eurocrypt 2003, volume 2656 of LNCS, pages 614–629. Springer, 2003.
  9. 9,0 9,1 9,2 Mihir Bellare, Haixia Shi, and Chong Zhang. Foundations of group signatures: The case of dynamic groups. In Cryptographers’ Track — RSA 2005, volume 3376 of LNCS, pages 136–153. Springer, 2005.
  10. 10,0 10,1 Giuseppe Ateniese, Jan Camenisch, Susan Hohenberger, and Breno de Medeiros. Practical group signatures without random oracles, 2005. Cryptology ePrint Archive, report 2005/385.
  11. 11,0 11,1 11,2 Xavier Boyen and Brent Waters. Compact group signatures without random oracles. In Advances in Cryptology — Eurocrypt 2006, volume 4004 of LNCS, pages 427–444. Springer, 2006.
  12. 12,0 12,1 Xavier Boyen and Brent Waters. Full-domain subgroup hiding and constant-size group signatures. In 10th Intl. Conference on Theory and Practice of Public Key Cryptography (PKC), volume 4450 of LNCS, pages 1–15. Springer, 2007.
  13. 13,0 13,1 Jens Groth. Fully anonymous group signatures without random oracles. In Advances in Cryptology – ASIACRYPT 2007, volume 4833 of LNCS, pages 164–180. Springer, 2007.
  14. Chris Peikert and Vinod Vaikuntanathan. Noninteractive statistical zeroknowledge proofs for lattice problems. In Advances in Cryptology — Crypto 2008, volume 5157 of LNCS, pages 536–553. Springer, 2008.
  15. 15,0 15,1 15,2 15,3 15,4 15,5 Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In 40th Annual ACM Symposium on Theory of Computing (STOC), pages 197–206. ACM Press, 2008.
  16. 16,0 16,1 16,2 16,3 16,4 16,5 Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In 37th Annual ACM Symposium on Theory of Computing (STOC), pages 84–93. ACM Press, 2005.
  17. 17,0 17,1 Daniele Micciancio and Salil Vadhan. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In Advances in Cryptology — Crypto 2003, volume 2729 of LNCS, pages 282–298. Springer, 2003.
  18. 18,0 18,1 Ronald Cramer, Ivan Damg°ard, and Berry Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology — Crypto ’94, volume 839 of LNCS, pages 174–187. Springer, 1994.
  19. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology — Crypto ’86, volume 263 of LNCS, pages 186–194. Springer, 1987.
  20. 20,0 20,1 20,2 20,3 Chris Peikert. An efficient and parallel gaussian sampler for lattices. In Advancesin Cryptology — Crypto 2010, volume 6223 of LNCS, pages 80–97. Springer, 2010.
  21. Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In 41st Annual ACM Symposium on Theory of Computing (STOC), pages 333–342. ACM Press, 2009.
  22. Mikl´os Ajtai. Generating hard instances of the short basis problem. In 26th International Colloquium on Automata, Languages and Programming (ICALP), volume 1644 of LNCS, pages 1–9. Springer, 1999.
  23. Jo¨el Alwen and Chris Peikert. Generating shorter bases for hard random lattices. In STACS, volume 09001 of Dagstuhl Seminar Proceedings, pages 75–86. Schloss Dagstuhl, 2009. Available at http://drops.dagstuhl.de/portals/STACS09/.
  24. Mihir Bellare and Phil Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In 1st ACM Conference on Computer and Communications Security, pages 62–73. ACM Press, 1993.
  25. 25,0 25,1 25,2 David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a lattice basis. In Advances in Cryptology — Eurocrypt 2010, volume 6110 of LNCS, pages 523–552. Springer, 2010.
  26. Mikl´os Ajtai. Generating hard instances of lattice problems. In 28th Annual ACM Symp. on Theory of Computing (STOC), pages 99–108. ACM Press, May 1996.
  27. Oded Goldreich and Shafi Goldwasser. On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences, 60(3):540–563, 2000.
  28. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology — Crypto ’86, volume 263 of LNCS, pages 186–194. Springer, 1987.