Слепые подписи, основанные на решетке

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:40, 29 ноября 2015.
Lattice-Based Blind Signatures
LBBS.png
Авторы Markus Ruckert
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал
Аннотация. Слепые подписи (СП), введенные Chaum, стали краеугольным камнем в криптографии, ориентированной на секретность. Использование вопросов жесткой решетки, таких как вопрос кратчайшего вектора, в качестве основы безопасности имеют преимущества по сравнению с использованием факторизации или задач дискретного логарифмирования. Например, решеточные операции более эффективны, чем модульное возведение в степень и задачи решетки остаются трудными для квантовых и субэкспоненциально-временных противников. Вообще говоря, слепая подпись позволяет подписывающему лицу подписывать сообщение не видя его, при сохранении управления над процессом. В частности, подписавшийся может контролировать количество выданных подписей. Для получателя подписи, этот процесс обеспечивает идеальную анонимность, например, его расходы остаются анонимными при использовании слепой подписи для электронных денег.
Мы даем положительный ответ на вопрос того, возможно ли реализовать слепую подпись, основанную на задачах решетки. Более того, мы показываем, как превратить схему идентификации Lyubashevsky в схему слепой подписи, которая имеет почти ту же самую эффективность и безопасность в модели случайного оракула. В частности, это предлагает квазилинейную сложность, статистическую слепоту(отсутствие видимости), и невозможность подделки, основанные на твердости задач решетки худшего случая с фактором приближения в размерности . Кроме того, первые схемы слепой подписи, которые поддерживают стойкость к утечке, терпя утечку чести секретного ключа к модели, которая создана Katz и Vaikuntanathan.


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


Введение

С тех пор, как Chaum идею слепых подписей [1], это стало важным примитивом для анонимного Интернет-банкинга, электронного голосования (например [2], а так же для передачи с забыванием [3]. Эти приложения будут сохранять свою важность и в ближайшем, и в далеком будущем. Что касается ближайшего будущего, мы убеждены, что современная факторизация и дискретный логарифм являются основой эффективности и безопасности. Но как долго? Сегодня при создании криптографических схем с гарантированной защитой, необходимо также ожидать новейших технологий, которые могут привести к новым атакам. Именно поэтому мы обычно пытаемся использовать самые умеренные предположения. Давайте рассматривать, например, квантовые компьютеры как сравнение для этих будущих разработок. В квантовой эре, криптографические предположения изменяются скачками вычислительной мощности, которые обеспечат квантовые компьютеры. Есть только несколько криптографических предположений, которые предугаданы, чтобы быть постквантом, то есть, они способны противостоять атакам квантового компьютера. Одно из этих предположений – трудность нахождения коротких векторов в решетке. Даже на сегодняшний день, существуют положительные результаты, когда создавая криптографию, основанную на задачах жесткой решетки, в отличие от факторизации, они выдерживают субэкспоненциальные атаки и самые лучшие алгоритмы, например [4], имеют экспоненциальную сложность в размерности решетки. Кроме того, задачи решетки обычно позволяют сократить наихудший случай к среднему случаю, который возвращается к Ajtai [5]. Утверждают, что задача случайно выбранного варианта определенной решетки по крайней мере такая же сложная, как наихудший вариант связанной с этой задачей решетки. Таким образом, выбрать секретный ключ просто. Это сведение было позднее адаптировано для работы с идеальными решетками Lyubashevsky и Micciancio [6],потому что идеальные решетки предоставляют компактное представление открытого ключа и являются очень эффективными операциями в счет несколько более сильного предположения. Модель обеспечения безопасности, главным образом под влиянием Juels, Luby, и Ostrovsky [7],так же как Pointcheval и Stern [8], требует схем слепой цифровой подписи для удовлетворения отсутствия видимости и невозможности подделки. Отсутствие видимости предполагает, что подписывающее лицо не должно получать какую либо информацию о подписанных сообщениях и еще одно, что невозможность подделки означает, что противник не может получить больше подписей, чем было связано с подписывающим лицом.


Наш вклад

Мы создали первую схему слепой подписи, основанной на решетке. В ее основе лежит ID-схема Lyubashevsky [9] в сочетании с парадигмой Fiat-Shami [10]. Это безусловно вслепую и избирательно с отказами [3] и невозможность подделки в модели случайного оракула [11], если стандартные задачи решетки в идеальной решетке [6] труднее в худшем случае. С ее четырьмя шагами это довольно эффективно. Все действия имеют квазилинейную сложность и все ключи и подписи требуют квазилинейного количества битов для хранения с отношением к основному параметру . Кроме того, устойчивость к утечке в соответствии с моделью, предложенной Katz и Vaikuntanathan [12]. Пусть - длина секретного ключа в битах. Наша схема остается безопасной, даже если противник получает бит секретного ключа через сторонние каналы противника. Это делает модель обеспечения безопасности ближе к реальности, где противник может получить информацию о секретном ключе, например, через (удаленные) временные атаки или при наличии физического доступа к подписывающему устройству. При использовании электронного голосования или схем оплаты электронными деньгами такая устойчивость помогает при внутренних атаках и может улучшить надежность, мы готовы предоставить это в схемах. Другое применение нашей конструкции это слепые подписи, основанные на идентификации, в сочетании с [13]. Наша схема является также первой схемой слепой подписи устойчивой к утечкам, наши результаты в этом отношении применимы к ID Lyubashevsky и схемам подписи[9][14]. Это может быть возможно при использовании аналогичного подхода Pointcheval и Stern[8] для создания устойчивости в утечкам вида [12][15] из схемы подписи Okamoto-Schnorr [16][17]в схемах слепой подписи. Сравнение RSA, Okamoto-Schnorr, и нашей схемы слепой подписи.

Таблица 1.
Схема Безопасность Модуль (биты) Шаги Генерация ключей Сигнал Верификация
АRSA-1229 2012 Действующий (76) 2 95 мс 16 мс 5 мс
RSA-3313 2050 Средний(102) 2 1250 мс 46 мс 6 мс
RSA- 15424 2282 Перспективный(256) 2 251849 мс 2134 мс 20 мс
OS-1229 2012 Действующий (76) 3 16 мс 64 мс 24 мс
OS-3313 2050 Средний (102) 3 46 мс 184 мс 69 мс
OS-15424 2282 Перспективный (256) 3 2134 мс 8536 мс 3201 мс
Раздел 3

2012 Действующий (76) 4 37 мс 220 мс 33 мс
Раздел 3

2050 Средний (102) 4 52 мс 283 мс 57 мс
Раздел 3

2282 Перспективный (256) 4 305 мс 1175 мс 320 мс

В таблице сравнивается наша схема с RSA и Okamoto-Schnorr, для различных модулей согласно [18] в схемах слепой подписи. Сравнение RSA, Okamoto-Schnorr, и нашей схемы слепой подписи. (текущий, средний) и [19] (перспективный). Длину в битах можно вычислить на сайте www.keylength.com. Для нашей схемы слепой подписи мы предлагаем три оптимизированных набора параметров для тех же уровней безопасности, основанных на [20], что обеспечивает основу для выбора безопасных параметров для криптографии, основанной на решетке. Обратите внимание, что параметры RSA и ОS не берут потенциальных атак квантовых компьютеров в расчет. Весь расчет времени усредняются более чем 1000 случайных экземпляров. Однако, неясно, будет ли она действительно работающей и будет ли она эффективной. Таблица 1 сравнивает слепые подписи RSA и Okamoto-Schnorr (ОS) с нашей схемой с точки зрения вычислительных затрат. Для всех схем мы предлагаем наборы параметров для текущего, среднего и перспективного уровня безопасности. Мы считаем, что RSA является хорошей основой для сравнения, потому что она проста для понимания и очень эффективна, поскольку подписание включает только два модульных потенцирования, и проверка может быть сделана единожды (маленькая экспонента). Мы не считаем умножение. Как наблюдалось в работе [21], безопасность схемы слепой подписи RSA, основанной на специально сделанном интерактивном предположении, что сильнее, чем оригинал предположения RSA [22]. Принимая все это во внимание, расчет времени для RSA обеспечивает оптимальную нижнюю границу для текущих практических и безопасных схем. Расчет времени для OS предполагает расчет времени, в зависимости от количества модульных потенцирований, не считая умножения. Мы включаем OS, потому что она является типичной структурой с 3 перемещениями и основана на стандартном предположении. Поэтому ближе к нашему протоколу. Расчет времени был получен AMD Opteron CPU, достигая 2.3 ГГц. Для RSA и OS, мы использовали OpenSSL 0.9.8g, который предполагаемо должен быть очень эффективным. Для наших схем слепой подписи, мы сделали простую реализацию, что, безусловно, оставляет место для улучшений. Здесь, расчет времени отражается в общую схему. Из Таблицы 1, мы ясно видим, что наша схема имеет преимущества благодаря квазилинейной сложности, особенно в более высоких уровнях безопасности. Кроме того, для нашей схемы, мы имеем различную взаимосвязь между размером подписи и скоростью. Для получения дополнительной информации, смотрите полную версию [23]. Там, мы также показываем, как оптимизировать ключ и размеры подписи, которые являются обычно большими в конструкциях, основанных на решетке. Мы считаем, что наша работа является важным вкладом, так же как предыдущие эффективные конструкции, такие как [1][24][8][25][21][26][27], имеют одну общую черту: они построены на предположениях классической теории чисел, таких как стойкость факторизации больших целых чисел или дискретных логарифмов. Более новые подходы, например, Boldyreva [28] или Okamoto [27], намерены использовать соединения, которые приводят к очень изящным конструкциям. Они, однако, снова основаны на задаче дискретного логарифма в этой определенной установке. Ни одна из вышеупомянутых схем не остается безопасной в присутствии довольно больших квантовых компьютеров, где и факторизация и вычисления дискретных логарифмов стало легким из-за основополагающей работы Shor [29].


Основные препятствия

Для каждой схемы слепой подписи, нужно преодолеть три основных препятствия. Схема должна быть слепой, еще должна исключать возможность подделки, и вместе с этим полной. Отсутствие видимости и невозможность подделки всегда являются противоположными, поскольку предоставление пользователю слишком больших прав для обеспечения отсутствия видимости вредит возможностью подделки и наоборот. При работе с решетками у нас нет доступа к структуре циклической группы, как в схемах, которые основаны на DDH или предположениях DL. Там, отсутствие видимости обычно легче достигнуть, умножая сообщение на элемент случайной группы. Результат - снова элемент случайной группы. В решетках мы должны эмулировать это на бесконечной структуре с помощью метода фильтрации, которому способствовал [9]. Однако этот метод приводит к дефекту завершенности, который влияет даже на взаимодействие подлинного пользователя с подлинным подписывающим лицом. Таким образом, протокол, возможно, должны быть перезапущен. Мы показываем, как этот метод может быть усовершенствован, чтобы учитывать соотношение память - время, сокращая количество ожидаемых перезагрузок за счет только немного больших подписей. При решении этого дефекта, нам нужны дополнительные средства для обеспечения отсутствия видимости при повторении протокола. Наше решение включает статистически скрывающееся обязательство. Аналогичным образом, у дефекта полноты есть последствия относительно невозможности подделки, поскольку пользователь может утверждать, что протокол перестал работать, когда он на самом деле работал. Здесь, мы расширяем типичную структуру с тремя перемещениями до структуры с четырьмя перемещениями, где пользователь должен демонстрировать, что он или она не могли получить корректную подпись. Такое последнее перемещение, от пользователя к подписывающему лицу, очень необычно для схемы слепой подписи. Мы решаем эту проблему путем разработки специального доказательства отказа и используя в вычислительном отношении схему обязательной связи обстоятельств. Все эти вопросы, и дополнительная устойчивость к утечке информации, необходимо решать одновременно, так как они взаимосвязаны. Это приводит к сложному процессу правильно установить многочисленные параметры и наборы для нашей схемы в Таблице 2.


Слепые подписи RSA

Можно было бы думать, что RSA (хэш слепой инвертирование неслепой) слепые подписи, основанные на решетке, могут быть реализованы с использованием прообраза, способного к выборке, функции с секретом из [30]. Если определенные вопросы решетки трудны, то трудны выбранные прообразы из (маленькая норма), если каждому неизвестны короткие векторы , такие что . Если пользователь хешировал сообщение , используя хэш полной области и обеспечил отсутствие видимости, используя для . Подписывающий будет выбран из и результат возвращен в . Функция сжимается, поэтому нет уникальных прообразов. Используя и тот факт, что является линейной, пользователь может вычислить , который проходит проверку: . Для доказательства можно было бы положиться на интерактивном "еще одном" предположении инверсии пути обхода системы защиты, сродни [21]. Однако, противник никогда не должен получать ненулевой так, что , потому что это подразумевало бы изучение части секретного ключа. К сожалению, такие атаки просты: принять и отправить для подписывающего, которое возвращается в . Теперь, является маленьким и . Кроме того, с высокой вероятностью, поскольку есть много прообразов .


Организация

После краткого раздела предварительных выборов мы представляем нашу схему слепой подписи в Разделе 3. Там мы также предоставляем детальный анализ, в том числе полноты, отсутствия видимости, еще одно невозможность подделки и устойчивости к утечкам. Полная версия в документе [23]. Там мы обсудим, как выбрать практические параметры и докажем все вспомогательные леммы для теорем в Разделе 3.


Предварительные действия

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


Слепые подписи

Схема слепой подписи состоит из трех алгоритмов , где - интерактивный протокол между подписывающим лицом и пользователем . Спецификация состоит в следующем. Генерация ключей. выводит секретный ключ подписи , и открытый ключ верификации . Протокол подписи. описывает объединенное выполнение и . Секретный выход - представление , и секретный выход – подпись на сообщении , пространства сообщений в . Таким образом, мы пишем . Верификация подписи. Алгоритм выдает , если является допустимой подписью на в и в противном случае. Полнота определяется как с ЭЦП, т. е. каждая правдиво созданная подпись для правдиво созданных ключей и для любого сообщения действуют в этом разделе. Представления интерпретируются как случайные переменные, их выход порождает последующие выполнения соответствующего протокола. Два представления и считают равными, если они не отличаются в любом вычислительно неограниченном алгоритме со значимой вероятностью. Что касается безопасности, слепые подписи должны удовлетворять двум свойствам: отсутствие видимости (слепота) и еще одна невозможность подделки [7][8]. Понятие отсутствия видимости (слепоты) определено в эксперименте , где противник , который подписывает сообщение, работает в трех режимах. В режиме «поиска», он выбирает два сообщения и взаимодействует с двумя пользователями в режиме «вопроса». В зависимости от подбрасывания монеты , первый (второй) пользователь получает слепую подпись для .После наблюдения неослепленных подписей в первоначальном порядке, с вниманием к , подписывающее лицо должно предположить бит в режиме «предположения». Если в любом из пользовательских алгоритмов произошел сбой на выходе при получении корректной подписи, подписывающее лицо просто уведомляется об отказе и не получает подписи. Ниже, мы имеем дело с аварийными прекращениями работы, такими как расширение. Также отметим, что мы позволяем противнику сохранять состояние, которое возвращает обратно в последующие вызовы. Схема слепой подписи - слепа, если нет никакого противника выполненная в период времени не больше , которое выигрывает вышеупомянутый эксперимент с преимуществом, по крайней мере , где преимущество определяется как . Схема является статистически слепой, если - слепа для незначительного . Второе свойство безопасности, еще одна невозможность подделки, гарантирует, что каждое завершенное взаимодействие между подписывающим лицом и пользователем дает самое большое одну подпись. Это формализовано в эксперименте , где соперник, подписывающий сообщение, пытается вывести допустимое в подписи для завершает взаимодействие с честным подписывающим лицом. семейство случайных оракулов. Схему слепой подписи - невозможно подделать, если нет никого противника , работающего во времени не больше , делающего не более запросов подписи и не более запросов оракула хэша, который выигрывает вышеупомянутый эксперимент с вероятностью по крайней мере, .


Расширения

Мы рассматриваем три расширения вышеупомянутой модели обеспечения безопасности для слепых подписей: первое - мы имеем дело с пользовательскими аварийными прекращениями работы, второе – с нечестно выбранными ключами, третье – с устойчивостью к утечке. Безопасность до аварийного прекращения работы. Слепота (отсутствие видимости) в предыдущем подразделе не распространяется на случай, когда протокол прерван преждевременно. Есть утвердившееся понятие слепоты выборочного отказа [3], где злоумышленник, подписывающий сообщение, может выбрать или согласно некоторому секретному распределению, которое вызывает сбой протокола. Предотвратить такую возможность в общем легко, это было показано Fischlin и Schröder в [31]. В ходе обсуждения нашей конструкции, мы утверждаем, что она уже слепа в этом смысле. Ключи, выбранные противником. Рассмотрим эксперимент слепоты в [32]. Вместо выбранных в эксперименте , мы можем позволить подписывающему лицу выводить . Слепоту труднее достичь в этом случае. Однако, наша конструкция остается слепой в этой более сильной модели, поскольку доказательство не использует специфических особенностей о ключе. Устойчивость к утечке. Устойчивость к утечке ключей - способ обеспечения безопасности от атак по побочным каналам. В работе [12], Katz и Vaikuntanathan дают хороший обзор последних событий и эволюции устойчивости к утечкам для подлинности и конфиденциальности. Очевидно, что мы заинтересованы в подлинности в специальном случае слепых подписей. Мы моделируем утечку ключей в эксперименте невозможности подделки, добавляя утечку оракула в . Противник может адаптивно запросить утечку с серией функций , и получить . Единственным ограничением является то, что , где функция определяет количество утечки, которую мы готовы терпеть. Заметьте, что ключ подписывающего лица не должен изменяться в течение долгого времени, и его секретное состояние состоит только из секретного ключа. Кроме того заметьте, что это расширение разумно только пока , где обозначает длину в битах, и - подпись. Иначе, противник может легко получить весь секретный ключ или подпись на его выбор. Смотрите полную версию [23] для эксперимента. Чтобы продемонстрировать устойчивость к утечке нужно показать, что условная минимальная энтропия секретного ключа все еще достаточна велика, чтобы доказать безопасность.


Обязательства

Обязательства обычно работают в два этапа. Во-первых, одна сторона публикует обязательство , к сообщению не раскрывая никакой информации об этом. Это - "скрывающееся" свойство схемы обязательств. На втором этапе, сторона может доказать, что фактически соответствует , показывая . Важно, чтобы никакой алгоритм не мог найти второе сообщение и случайность , такие что , то есть, повредит свойству связи. Как обычно, эти свойства определены для таких семейств функции связи. Схема - сокрытия(-связи), если не существует алгоритма, работающего во времени не больше , который может повредить свойству сокрытия (связи) с вероятностью, по крайней мере, . Оба свойства могут быть удовлетворены вычислительно или безусловно, но нет схемы, которая безусловно скрывается и безусловно связывается [33]. Для нашей схемы мы принимаем статистически -сокрытия и в вычислительно -связи в схеме обязательств. Поскольку мы заинтересованы в схемах полностью основанных на решетках, мы хотим отметить, что такие схемы обязательств могут быть созданы на вопросах жестких решеток [34], но на практике, скорее используются криптографические хеш-функции, чем код аутентификации сообщений. Например, использование основанной на решетке хеш-функции [35].

Решетки

Решетки в являеюся дискретным множеством , где линейно независимы над . Матрица является основанием решетки , и мы пишем . Размерность решетки - . Основная вычислительная задача в решетках – это задача кратчайшего вектора (SVP), где алгоритму описание, основание решетки и предполагается нахождение короткого вектора , по отношению к определенной норме (до фактора приближения). Более точно, нужно найти вектор , такой что для всех с фиксированным фактором приближения . В этой работе мы интересуемся специальным семейством решеток, связанных с идеалами в кольце , где является главным и . Мы сосредотачиваемся на и степени двойки по соображениям эффективности, но может быть заменен на любой неприводимый многочлен над . Тогда, наша схема и анализ становятся только немного более сложными. Мы отождествляем с вектором коэффициентов . Кроме того, мы обозначим элементы - модуля с или непосредственно с . Следовательно, мы определяем . Нормой является небольшое злоупотребление обозначением, но оно будет использоваться , только если имеет малые коэффициенты над . Решетка соответствует идеалу , тогда и только тогда, когда каждый вектор решетки является вектором коэффициентов многочлена в . Задача кратчайшего вектора решетки (SVP) легко переводится в идеальные решетки, тогда это называется проблема кратчайшего вектора идеальной решетки (ISVP). Предположение о случае средней твердости для нашей конструкции зависит от задачи нахождения кратчайших векторов в ядре семейства гомоморфизмов модуля при ограничении области , то есть, ограничивая коэффициенты при вводе . Эта проблема может быть сформулирована как следующая проблема коллизии [LM06].

TemplateDifinitionIcon.svg Определение «Определение 1»
Проблема коллизии. Проблема коллизии говорит о нахождении отличной пары такой, что для .

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


TemplateTheoremIcon.svg Теорема Теорема 1
(от наихудшего случая к нормальному случаю, Теорема 2 в [6]) Пусть и . Противник , который решает задачу т. е. находит различные прообразы , такие , могут использоваться, чтобы решить задачу с факторами приближения в худшем случае.
Доказательство
Не приводится


Слепые подписи на идеальных решетках

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


Параметр Значение Асимптотика Использование
Степень двойки - Основной параметр безопасности

целая положительная константа

Размер секретного ключа, невозможность подделки

Множество секретных ключей

Показатель неразличимости, устойчивость к утечек
Преобразование от наихудшего случая к нормальному случаю
Размер выходного хэша
Целая положительная константа

Полнота, скорость
Слепота

(отсутствие видимости)

Слепота

(отсутствие видимости)

Показатель неразличимости
Показатель неразличимости, Дефект полноты
Слепота

(отсутствие видимости)

Слепота

(отсутствие видимости), Дефект полноты

Коллизии над
Преобразование от наихудшего случая к нормальному случаю

В таблице определяются все параметры и наборы для нашей схемы. Наборы определены через нормы связи, для которых мы также утверждаем асимптотический рост относительно параметра безопасности . В последнем столбце указывается основное использование параметра или набора. Некоторые наборы представляют ошибку полноты схемы, которая может быть уменьшена увеличением . Сокращение этого дефекта также значительно повышает производительность. Все наборы подмножества кольца . В ходе обсуждения мы показываем, что не подрывать безопасность не эффективно. Впоследствии, мы доказываем, что схема статистически слепа и что невозможность подделки, если задача коллизии легка. В результате, невозможность подделки может быть основана на наихудшем случае твердости схемы слепой подписи основанной на идеальных решетках. После основного анализа мы доказываем, что наша схема также поддерживает стойкость к утечке. Заметим, что схема требует большого количества параметров, которые должны быть тщательно разработаны. Их определение в Таблице 2 будет оправдано в конце анализа.Мы решили не «расслаблять» параметры и т.д. поскольку мы должны знать их относительный размер в различных леммах, делая доказательства легкими для понимания. Асимптотики в третьей колонке должны помочь в оценке их величины. Параметр является костантой 1 здесь, но он может быть увеличен, если необходимо подписаться значения хэш-функции длина в битах которой . Колонка «использование» в таблице указывает на раздел, в котором они больше всего влияют. Что касается выбора практических параметров, мы направляем читателя к полной версии [23]. Там, мы предлагаем набор параметров безопасности, основанный на анализе в [20].. Полная версия включает также обсуждение возможных компромиссов для повышения эффективности.

Наша конструкция

Мы создаем нашу схему слепой подписи следующим образом.

SINGER USER U(S,M)

Вход: Y






Начать с новой

Вход:



Переключаем рестарт

Вход:





Вход: result







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

Верификация. выход 1, если и .

Анализ и безопасность

В этом разделе мы анализирует нашу схему слепой подписи на полноту, слепоту (отсутствие видимости), невозможность подделки и стойкости к утечке. Для каждого аспекта мы доказываем основную теорему. Вспомогательные леммы указаны перед теоремами и доказаны в полной версии [23]. Полнота. Полнота слепых подписей является нетривиальным вопросом из-за возможности перезапуска и наличия многих параметров. Следующая лемма гарантирует, что число перепусков мало, эффективно постоянная.

TemplateLemmaIcon.svg Лемма «Лемма 1»
Пусть с произвольным и случайным . Учитывая для мы имеем .


{{Теорема|Теорема 2| Полнота. | Пусть . Схема слепой подписи полна после не белее чем (или ожидаемое число ) повторений. Смотрите полную версию доказательства в [23]. Там также утверждается, что , это хороший выбор чтобы сделать протокол более эффективным на практике. Отметим также, что все действия (включая возможные перезапуски) в слепой подписи имеют сложность и что секретные ключи, открытые ключи и подпись имеют размер . Слепота (отсутствие видимости). Мы доказали, что слепая подпись является статически слепой (невидимой), это основано на наблюдении, что подписывающее лицо видит только значения, которые не зависят от подписываемого сообщения. Точнее говоря, представления двух различных сообщений неразличимы. Для этого аргумента работы, мы требуем статически скрывать схему обязательств и тщательно выбирать наборы и . Следующая лемма о вероятности крайне важна, поскольку она гарантирует, что сообщение пользователя после шага 2 и конечный результат не зависят от сообщения. В контексте устанавливает форму неразличимости свидетеля относительно сообщения, которое выбрано злоумышленником для подписи.

TemplateLemmaIcon.svg Лемма «Лемма 2»
Пусть с произвольными и случайным для . Мы определяем случайные переменные и , если , иначе мы повторно производим выборку . Затем .


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

TemplateTheoremIcon.svg Теорема Теорема 3 (слепота)
. Слепая подпись - слепа, если - скрыта.
Доказательство
С соответствии с экспериментом , злоумышленник, подписывающий сообщение, получает на выходе 2 сообщения и взаимодействует с двумя пользователями , после секретного подбрасывания монеты . Мы показали, что эти пользователи не имеют утечки информации о соответствующих сообщениях.

Технически, мы устанавливаем все сообщения протокола и выход, так чтобы интерпретировать как случайные переменные, распределенные независимо от сообщения, которое будет подписываться. Это включает анализ и, в конечном итоге, перезапуски. Относительно и , мы не должны волноваться. Они выбраны равномерно случайно. Распределение . Пусть будут первыми сообщениями протокола , соответственно. Они находятся в и оба имеют вид с и . Статическое расстояние равно 0 по Лемме 2 , потому что коэффициенты в ограничены . Распределение . Пусть будут частью конечного выхода соответственно. Оба имеют вид для и . Кроме того, и находятся в , имея коэффициенты, ограниченные . Следовательно статическое расстояние равно 0 по Лемме 2 . Перезапуски. Заметим, что каждый запуск протокола статически не зависит от предыдущих запусков по статическим скрытым свойствам обязательств и потому что пользователь выбирает новые после каждого перезапуска. Эта причина, по которой мы наследуем статически - скрытую получая - слепую вместо совершенной слепоты. Наконец, мы должны обсудить перезапуск после шага 4. Пользователь посылает подписывающему. Эта информация позволяет проверить подпись по отношению к . Сообщения по прежнему статически скрыты свойствами , потому что пользователь никогда не показывает decommitment . Таким образом протокол скрывает сообщение, которое будет подписано, и последующие шаги протокола для аналогичного сообщения будут статически независимы. Кроме того, наша схема поддерживает слепоту селективных неудач, как показано в [31], потому что мы подписываем обязательства, вместо сообщений, которые выбрал злоумышленник. Даже четвертый шаг не раскрывает любую информацию о сообщении, благодаря обязательному свойству скрытости. Невозможность подделки. В этом разделе мы покажем, что слепые подписи невозможно подделать, что обеспечивается тем, что задача коллизии трудна и схема обязательств связана. Основным инструментом снижения является Forking Лемма [8][36]. Моделируя окружающую среду, особенно запросы на слепую подпись, для злоумышленника в эксперименте о невозможности подделки, мы требуем, чтобы было, по крайней мере, два возможных секретных ключа для каждого открытого ключа (Лемма 3). Кроме того, нам нужен протокол подписи, который будет неразличим свидетелями, чтобы предотвратить злоумышленника, изучающего секретный ключ (Лемма 4). Свойство обязательности , в том, чтобы предотвратить попытки злоумышленника получить одну подпись, которая работает для двух сообщений, изменяя обязательства над сообщениями. Все остальные злоумышленники на выходе получают, по крайней мере, одну подпись, которая не соответствует завершению взаимодействия. Здесь мы применяем Forking Лемму для получения знаний о секретном ключе, который был использован для вычисления подделки. Используя эти знания, мы можем решить задачу коллизии. Наконец, мы должны иметь дело с шагом 5 в протоколе. Злоумышленник доказывает, что не может получить корректную подпись. Докажем, что это обоснованно, если трудна. Если семейство функций сокращает область , легко показать, что все секретные ключи накладываются, по крайней мере, на один секретный ключ.

TemplateLemmaIcon.svg Лемма «Лемма 3»
Пусть . Для каждого секретного ключа есть второй с (с подавляющей вероятностью).


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

TemplateLemmaIcon.svg Лемма «Лемма 4»
Пусть и . Для любого сообщения и любых двух секретных ключей с в результате протокол имеет вид и неразличны.


С помощью Лемм 3 и 4, мы можем использовать неразличимость свидетелей, чтобы моделировать все запросы слепой подписи оракула с секретным ключом и в тоже время ожидать противника на выходе с подделкой, которая соответствует различным секретным ключам с немалой вероятностью или повредить связующее свойство в схеме связи. Мы применяем Forking Лемму для получения решения .

TemplateTheoremIcon.svg Теорема Теорема 4 (еще одна невозможность подделки).
Пусть будет оракулом подписи. Пусть и значения функций для моделирования оракулом и , и пусть будет вероятностью для перезапуска в протоколе. Слепую подпись невозможно подделать, если - обязательна и с и не малой , если не мала.

Вероятность зависит от количества выпущенных подписей. Она будет найдена в конце доказательства.

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

Установка. бросает монету . Для выбираем . Для получаем писание как входное. инициализирует список хэш- запроса пар . Выбираем и получаем . кроме того, случайно выбираем ответы оракула и случайную последовательность . Это работает моделируя «черный ящик». Запросы случайного оракула. На входе получаем в . Если находим соответствующие значения хэш, то возвращаем. Иначе выбирает первое из последовательности , хранящие в и возвращает . Запросы слепой подписи. действует в соответствии с протоколом на Рисунке 1. Выходы. В конечном счете, остановки и выходы для отличных сообщений. Если , сокращение выглядит, как и выходы останавливают связующую способность . Если нет такой коллизии, прерывается. Если , моделируем запросы с индексом , такие что для . Тогда запускается, работая с ответами случайного оракула для нового набора . и работают с такой же случайной лентой, как и в первом случае. Среди других значений, на выходе и возвращает , если пытается решить . Если , сокращение повторяется не более раз с различной случайной лентой и случайным оракулом. Анализ. Среда отлично моделируется. Особенно то, что перезапуски происходят с такой же вероятностью, как и в оригинальном протоколе. При - раскрытие связующей способности , если раскрывает связующую способность повредит невозможности подделки. Для мы предполагаем, что повреждение еще одной невозможности подделки без атаки . Так, по крайней мере, одна из выходных подписей не получена через взаимодействие. Вероятность, что предполагает индекс к этой подписи верна, по крайней мере, для . Заметьте, что является ответом случайного оракула, но с вероятностью . Кроме того, обратите внимание, что с вероятностью , по крайней мере, один из повторных запусков дает тот же результат , что и при первом запуске . Таким образом, мы полагаем, что показатели в обоих «интересных» воспроизведениях являются постоянными. Применяя Forking Лемму, мы знаем, что с вероятностью , снова успешна в эксперименте невозможности подделки и выходы с использованием тех же запросов случайного оракула, что и в первом запуске. Дополнительный фактор имеет потенциал прервать работу во время второго запуска, берем во внимание то, что это будет успешно при вероятности не более . Поэтому, мы знаем, что . Теперь мы возвращается к решению задач коллизии. Мы должны показать, что и . Второе требование следует непосредственно из предыдущего абзаца. Первое имеет более активное участие. Здесь важно то, что в протоколе неотличимости свидетелей (Лемма 4), то есть противник не распознает использовали ли мы один из двух возможных ключей (Лемма 3), с вероятностью больше чем . Таким образом, с вероятностью выход соответствует . Мы показываем, что или или . Предполагая, что оба равны, мы вычитаем уравнения и получаем . Мы знаем, что . Теперь, , потому что и . Таким образом, над , которая является областью целостности. Так, у нас есть противоречие и коллизия . Вероятность успеха, по крайней мере, , которая не мала, если не мала. Что касается перезапусков, мы утверждаем, что пользователь не может получить корректную подпись, после прерывания без решения задачи коллизии. Для того, чтобы вызвать прерывание после Шага 4, выводит результат равный , который вместе с удовлетворяет всем критериям аварийного прекращения работы:

(1)
(2)
(3)

Предположим, что он также получает корректную подпись в результате взаимодействия. Если , тогда из (2). Если параметры под равны, мы имеем - противоречие с (3). Если параметры отличны, у нас есть коллизия в , потому что и . Противник может добиться успеха, скрыв в .Но тогда мы обязательно имеем из (1) для и мы знаем, что .Так, противник должен был быть в состоянии предсказать вывод , чтобы вычислить . Таким образом, вероятность того, что мы может извлечь коллизию из мошенничества пользователя, во время прерывания работы, по крайней мере, , которая не мала, если не мала. Таким образом, полная вероятность успеха сокращения , если предположение было корректно. Следовательно, мы требуем, чтобы , чтобы иметь возможность полагаться на субэкспоненциальную твердость задачи решетки. Это ограничение - артефакт метода доказательства, который обсужден в [8] и это нисколько не необычно для эффективной схемы слепой подписи. Там, даже требовалось чтобы , потому что им необхадимо полиномиальное время сокращения. В последствии, в нашем сокращении, у нас значительное преимущество благодаря субэкспоненциальной твердости основной задачи решетки. Альтернативно, мы полагаем, что время выполнения сокращения может быть уменьшено для того, чтобы быть полиномиальным в , используя технологию Pointcheval [37]. В силу Теоремы 1, мы получаем следующие сильные гарантии безопасности худшего случая. Следствие 1. Слепую подпись еще раз невозможно подделать если решение трудна в худшем случае для факторов приближения в решетках, которые соответствуют идеалу в . Стойкость к утечке информации. Используя дополнительное ограничение для одного из параметров, мы можем создать утечку чести секретного ключа в эксперименте невозможности подделки, согласно полной версии [23]. Напомним, что для некоторого . Таким образом, можно выбрать , зная , не теряя квазиоптимальную эффективность схемы. Следующая теорема утверждает, что такой выбор является достаточным для обеспечения устойчивости к сильной утечке. Доказательство найдете в полной версии [23].

TemplateTheoremIcon.svg Теорема Теорема 5(Устойчивость к утечке).
Пусть и пусть будет длина секретного ключа. Условная минимальная энтропия для , условленного для . И полная утечка секретного ключа для бит, положительна с подавляющей вероятностью.
Доказательство
Без доказательства


Заключение

Мы показали, как создать эффективную и доказуемо безопасную схему слепой подписи, основанной на твердости задач решетки в худшем случае. Наша схема имеет четыре шага, квазиоптимальную производительность, и устойчивую к утечкам почти в оптимальном смысле. Поэтому, мы ожидаем, что наша конструкция будет противостоять даже субэкспотенциальным атакам и атакам квантовых компьютеров, а так же ограниченным атакам по сторонним каналам для получения секретного ключа. Благодарность Автор благодарит Özgür Dagdelen, Marc Fischlin, Tibor Jager, Vadim Lyubashevsky, Chris Peikert, Michael Schneider, and Dominique SchrЁoder за рассмотрение части этой работы и за очень полезные и стимулирующие обсуждения. Он также благодарит анонимных рецензентов ASIACRYPT 2010 за их ценный вклад.


Ссылки

  1. 1,0 1,1 Chaum, D.: Blind signatures for untraceable payments. In: CRYPTO, pp. 199–203 (1982)
  2. Rodrıguez-Henrıquez, F., Ortiz-Arroyo, D., Garcґıa-Zamora, C.: Yet another improvement over the mu-varadharajan e-voting protocol. Comput. Stand. Interfaces 29(4), 471–480 (2007)
  3. 3,0 3,1 3,2 Camenisch, J., Neven, G., Shelat, A.: Simulatable adaptive oblivious transfer. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 573–590. Springer, Heidelberg (2007)
  4. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: STOC, pp. 601–610. ACM, New York (2001)
  5. Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC, pp. 99–108. ACM, New York (1996)
  6. 6,0 6,1 6,2 Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V.,Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006)
  7. 7,0 7,1 Juels, A., Luby, M., Ostrovsky, R.: Security of blind digital signatures (extended abstract). In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 150–164. Springer, Heidelberg (1997)
  8. 8,0 8,1 8,2 8,3 8,4 8,5 Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptology 13(3), 361–396 (2000)
  9. 9,0 9,1 9,2 Lyubashevsky, V.: Lattice-based identification schemes secure under active attacks. In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp.162–179. Springer, Heidelberg (2008)
  10. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
  11. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: CCS. ACM, New York (1993)
  12. 12,0 12,1 12,2 Katz, J., Vaikuntanathan, V.: Signature schemes with bounded leakage resilience. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 703–720. Springer, Heidelberg (2009)
  13. Rückert, M.: Lattice-based blind signatures. Cryptology ePrint Archive, Report 2008/322 (2008), http://eprint.iacr.org/
  14. Lyubashevsky, V.: Fiat-shamir with aborts: Applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg (2009)
  15. Alwen, J., Dodis, Y., Wichs, D.: Leakage-resilient public-key cryptography in the bounded-retrieval model. In: Halevi, S. (ed.) Advances in Cryptology - CRYPTO 2009. LNCS, vol. 5677, pp. 36–54. Springer, Heidelberg (2009)
  16. Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptology 4, 161–174 (1991)
  17. Okamoto, T.: Provably secure and practical identification schemes and corresponding signature schemes. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 31–53. Springer, Heidelberg (1993)
  18. Lenstra, A.: The Handbook of Information Security. Key Lengths, ch. 14. Wiley, Chichester (2005), http://www.keylength.com/biblio/Handbook_of_Information_Security_-_Keylength.pdf
  19. ECRYPT2. Yearly report on algorithms and keysizes — report D.SPA.13 (2010), http://www.ecrypt.eu.org/documents/D.SPA.13.pdf
  20. 20,0 20,1 Rückert, M., Schneider, M.: Selecting secure parameters for lattice-based cryptography. Cryptology ePrint Archive, Report 2010/137 (2010), http://eprint.iacr.org/
  21. 21,0 21,1 21,2 Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The onemore-rsa-inversion problems and the security of chaum’s blind signature scheme. J. Cryptology 16(3), 185–215 (2003)
  22. Bresson, E., Monnerat, J., Vergnaud, D.: Separation results on the ”one-more” computational problems. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 71–87. Springer, Heidelberg (2008)
  23. 23,0 23,1 23,2 23,3 23,4 23,5 23,6 23,7 Rückert, M.: Lattice-based blind signatures. Cryptology ePrint Archive, Report 2008/322 (2008), http://eprint.iacr.org/
  24. Pointcheval, D., Stern, J.: New blind signatures equivalent to factorization (extended abstract). In: ACM Conference on Computer and Communications Security, pp. 92–99 (1997)
  25. Abe, M.: A secure three-move blind signature scheme for polynomially many signatures. vol. 2045, pp. 136–151. Springer, Heidelberg (2001)
  26. Camenisch, J., Koprowski, M., Warinschi, B.: Efficient blind signatures without random oracles. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 134–148. Springer, Heidelberg (2005)
  27. 27,0 27,1 Okamoto, T.: Efficient blind and partially blind signatures without random oracles. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 80–99. Springer, Heidelberg (2006)
  28. Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme. In: Desmedt, Y. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2002)
  29. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
  30. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) STOC, pp. 197–206. ACM, New York (2008)
  31. 31,0 31,1 Fischlin, M., SchrЁoder, D.: Security of blind signatures under aborts. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 297–316. Springer, Heidelberg (2009)
  32. Abdalla, M., Namprempre, C., Neven, G.: On the (im)possibility of blind message authentication codes. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 262–279. Springer, Heidelberg (2006)
  33. Goldreich, O.: The Foundations of Cryptography, vol. 1. Cambridge University Press, Cambridge (2004)
  34. Kawachi, A., Tanaka, K., Xagawa, K.: Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 372–389. Springer, Heidelberg (2008)
  35. Arbitman, Y., Dogon, G., Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFTX: A proposal for the SHA-3 standard. In: The First SHA-3 Candidate Conference (2008)
  36. Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Juels, A., Wright, R.N., De Capitani di Vimercati, S. (eds.) ACM Conference on Computer and Communications Security, pp. 390–399. ACM, New York (2006)
  37. Pointcheval, D.: Strengthened security for blind signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 391–405. Springer, Heidelberg (1998)