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

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

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

Содержание

Введение

Системы групповой цифровой подписи [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-доказательства для конкретных задач на решетках, однако их результаты не могут быть напрямую задействованы в нашей работе.)

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

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

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