Гомоморфные подписи для Полиномиальных функций

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:53, 27 сентября 2015.
Homomorphic Signatures for Polynomial Functions
Homomorphic Signatures for Polynomial Functions.png
Авторы Dan Boneh[@: 1] and
David Mandell Freeman[@: 2]
Опубликован 2011 г.
Сайт Cryptology ePrint Archive
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Содержание

Аннотация. Мы создаем первую схему гомоморфной подписи, которая способна дать оценку многомерным полиномам на подписанных данных. Учитывая открытый ключ и подписанный набор данных, существует эффективный алгоритм для получения подписи по среднему значению, стандартному отклонению и другим характеристикам подписанных данных. Предыдущие системы для вычислений на подписанных данных могли обрабатывать только линейные операции. Для полиномов постоянной степени длина полученной подписи зависит логарифмически от размера набора данных.
Наша система использует идеальные решетки таким образом, что является «подписывающим аналогом» гомоморфного шифрования Джентри. Безопасность основана на аппаратных задачах на идеальных решетках аналогично задачам в системе Джентри.
Ключевые слова: Гомоморфные подписи, идеалы, решетки.

Введение

Несмотря на то, что недавние новаторские работы показали, как вычислить произвольные функции на зашифрованных данных [1],[2],[3], намного меньше известно о вычислении функций на подписанных данных.

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

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

“классы”,

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

Обратим здесь внимание на функции, которые выполняют на наборе данных арифметические операции, такие как среднее, стандартное отклонение и другие операции анализа данных. Современные методы расчетов на подписанных данных могут использовать только линейные функции [4], [5], [6], [7], [8], [9]. В этих системах, учитывая независимо подписанных векторов , определенных над некоторым конечным полем , любой желающий может вычислить подпись на любом векторе в -линейно оболочке , но без секретно ключа никто не сможет получить достоверную подпись на векторе вне этой оболочки. Эти линейные схемы происходит от сетевого кодирования механизма маршрутизации [10].

Здесь мы представили первую систему подписи, которая поддерживает вычисление полиномиальных функций на подписанных данных. В частности, наша система поддерживает многомерные полиномы ограниченной степени. Для многочленов постоянной степени с ограниченными коэффициентами длина выработанной подписи зависит логарифмически только от размера набора данных. Так, например, задав в качестве входных данных подписанные данные, каждый может вычислить короткую подпись по среднему значению, стандартному отклонению, наименьшим квадратам и другим функциям произвольного подмножества данных. Заметим, что для вычисления стандартного отклонения требуется только квадратичный многомерный полином; другие приложения, обсуждаемые в Разделе 2.4., могут потребовать полиномы третьей и более степеней. Хотя наша система, по сути, совершает вычисления на данных, определенных над конечным полем , она может быть использована для вычисления на данных, определенных над множеством целых чисел посредством выбора достаточно большого поля .

Функциональность и безопасность нашей системы вытекают из свойств некоторых целочисленных решеток. В качестве «разогрева» для нашего основного результата, в Разделе 4 мы описываем линейную гомоморфную схему, построенную из случайных целочисленных решеток, которая использует те же базовые принципы, что и в нашей полиномиальной схеме. Интересно то, что эта конструкция дает гомоморфную систему над , которая допускает линейные функции с большим количеством входов, чем в предыдущих лучших таких системах [9]. В разделе 6 мы покажем как замена произвольных решеток в линейной схеме с идеальными решетками приводит к полиноминально-гомоморфной схеме – нашему основному результату.

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

Вспомогательная работа

Прежде, чем углубиться в детали нашей конструкции, упомянем связанную работу по интерактивному доказательству [11], [12], [13], где цель доказывающего получить сертификат, который убеждает верификатора, что некоторое утверждение верно. Вычислительно корректные доказательства Micali (Micali’s computationally sound (CS)) [11] могут решить описанную выше проблему следующим образом: Алиса подписывает пару , где это набор данных, а это короткий тег, используемый для задания имени . Она посылает на сервер и подпись . Позже, для некоторой функции сервер публикует , где - короткое доказательство того, что существует набор данных , такой, что , и что - действительная подпись Алисы на . Этот кортеж убеждает каждого, что он является результатом применения к исходному набору данных , помеченного Алисой. Безопасность обеспечивается использованием извлекателя удостоверителя Вэлианта (Valiant’s witness extractor) [12] для выделения 151 подлога Гомоморфных Подписей для Полиномиальных Функций от поддельного сервера. Конструирование в полной мере использует теорему PCP и надежность в случайной модели оракула. Заметим, что вычислительная устойчивость здесь достаточна с того момента, как сервер получает подписанные данные и следовательно уже считается вычислительно ограниченной.

Наш подход исключает доказательства .Сервер только публикует , где получена из и аутентифицирует как так и . Построение просто и имеет примерно такую же сложность, как вычисление . Более того, любой может дополнительно вычислить для некоторой функции и использовать для получения подписи на и вычисления функции . Хотя дальнейшее вычисление может быть сделано при помощи вычислительно корректных доказательств (CS) [12], намного проще использовать гомоморфные подписи.

Совсем недавно Гольдвассер, Калай и Ротблум (Goldwasser, Kalai, Rothblum)[13] и Дженнаро, Джентри, и Парно (Gennaro, Gentry, Parno) [14] показали, как безопасно передавать вычисления. В обоих случаях: [14] и [13] (в не интерактивной установке) взаимодействие между сервером и клиентом инициируется со стороны клиента и клиент использует секретный ключ для проверки результатов. В наших настройках сервера генерирует публично заверяемую подпись на результат, и каждый может убедиться, что подпись сделана с помощью открытого ключа Алисы.

Отметим также еще одну линию прилегающей работы, которая изучает "изменяемые" подписи [15],[16],[17],[18],[19],[20],[21],[22],[23],[24],[25]. Эти схемы обладают тем свойством, что при подписании ими сообщение, любой желающий может получить подписи на подмножествах этого сообщения. В нашем случае в центре внимания здесь совсем другое – мы смотрим на вычисление арифметических функций на независимо удостоверенных данных, а не вычисление на подмножестве одного сообщения. Нам также необходимо, чтобы сгенерированная подпись явно аутентифицировала вычисленную функцию .

Обзор наших методов

Метод пересечения

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

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

Точнее говоря, пусть будет тегом, - сообщением, и -кодированием функции . Подпись на тройке это короткий вектор в , удовлетворяющий и . Здесь - хэш-функция, определяющая тег , который отображает (кодирует) функции в вектора из . Эта должна не только сохранять гомоморфные свойства системы, но и должна давать возможность имитации против выбранного сообщения противника. Обратим внимание, что компонент подписи по существу такой же, как и подпись Джентри-Пэйкерт-Вайкунтанатана (Gentry-Peikert-Vaikuntanathan) [26] на (нехешированном) сообщении .

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

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

это подпись на и
это подпись на .

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

Наше использование идеальных решеток это подпись, аналогичная "в какой-то степени гомоморфной" системе шифрования Джентри (Gentry’s “somewhat homomorphic” encryption system) [1]. Идеальные решетки также появляются в схемах шифрования с открытым ключом, основанных на решетках Стэла, Стэйнфелда, Танака, Ксагавы (Stehle, Steinfeld, Tanaka, Xagawa) [27], Любашевского, Пейкерта и Регева (Lyubashevsky, Peikert, Regev) [28] и в хэш-функциях Любашевского и Миссиансио (Lyubashevsky, Micciancio) [29].

Неподдельность

Грубо говоря, атака подлогом под выбранным сообщением это допустимая подпись на тройке , такая, что , где есть набор данных, подписанный с использованием тега . Мы покажем, что успешная фальсификация может быть использована для решения Задачи Поиска Вектора по Норме (SIS, Small Integer Solution) в решетке , что для случайных -ичных решеток и подходящих параметров так же сложно, как и решение стандартных наихудших проблем решеток [30]. Когда - идеальная решетка, мы можем использовать идеальную структуру для получения решения задачи Приближенного Поиска Кратчайших Линейно Независимых Векторов (SIVP, Shortest Independent Vectors Problem) для (в среднем случае) распределения решеток, производимых нашим алгоритмом генерации ключей. Как и в случае с существующими линейно гомоморфными схемами подписи, наши доказательства безопасности устанавливаются в случайной модели оракула, где случайный оракул используется для симулирования подписей для атакующего по выбранному сообщению.

Конфиденциальность

В некоторых случаях желательно, чтобы сгенерированные подписи были закрытими. То есть, если это подпись на сообщении , полученная из подписей на сообщениях , то не должны раскрывать никакой информации о , получаемой из и . Используя аналогичные методы, как и в работе [9], не трудно показать, что наши линейно гомоморфные подписи удовлетворяющие свойствам конфиденциальности (также определены в работе [9]), называемым слабым сокрытием в контексте. Демонстрация этих свойств является доказательством того, что распределение, полученное путем суммирования независимых дискретных Гауссиан, зависящих только от смежного класса сумм.

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

Эффективность длины

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

Гомоморфные Подписи: Определения и Применения

Неформально, схема гомоморфной подписи состоит из обычных алгоритмов Генерация Ключа, Подписывание, Верификация (KeyGen, Sign, Verify), а также дополнительный алгоритм Оценка (Evaluate), который “переводит” функции на сообщениях в функции на подписях. Если является допустимым набором подписей на сообщениях , то должна быть действительной подписью для .

Для предотвращения смешивания данных из различных наборов при оценке функций, во входные данные алгоритмов Sign, Verify и Evaluate добавляется дополнительный короткий "тег". Тег служит для объединения сообщений из одного и того же набора данных. Можно было бы избежать использования тега, если бы новый открытый ключ генерировался для каждого набора данных, но простое создание нового тега для каждого набора данных более удобно.

Формально схема гомоморфной подписи заключается в следующем:

TemplateDifinitionIcon.svg Определение «Определение 2.1»

Схема гомоморфной подписи – это вероятностный кортеж полиномиальных (по времени) алгоритмов (Setup, Sign, Verify, Evaluate), таких, что:

  • . В качестве входных данных используются значение параметра безопасности и размер максимальный набор данных размера . На выходе получаем открытый ключ и секретный ключ . Отрытый ключ определяет пространство сообщений , пространство подписей и множество “допустимых” функции .
  • . На входе секретный ключ , тег , сообщение и индекс . На выходе подпись .
  • . На входе открытый ключ , тег , сообщение , подпись и функция . На выходе подпись .
  • . Вход: открытый ключ , тег , функция . Выход: подпись .

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

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

  1. Для всех тегов , всех и всех : если , то с огромной вероятностью .
  2. Для всех , всех кортежей , и для всех функций : если для , то с очень большой вероятностью

Будем говорить, что схема подписи, показанная выше, -гомоморфна.

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

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

Неподдельность

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

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

TemplateDifinitionIcon.svg Определение «Определение 2.2»

Схема гомоморфной подписи неподдельна, если для всех преимущество любого вероятностного, полиномиального по времени в следующей игре пренебрежимо мала по параметру безопасности :

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

Запросы: Действуя адаптивно, определяет последовательность наборов данных . Для каждого , кандидат равномерно выбирает и дает тег и подписи для .

Выход: выводит тег , сообщение , функцию , и подпись .

Противник побеждает, если и либо

(1) (подделка 1-го типа), либо
(2) для какого-либо , но (подделка 2-го типа).

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

Конфиденциальность

Как и в работе [9], определим понятие конфиденциальности для гомоморфных подписей, используя вариацию определения из Бруска и соавторы (Brzuska et al.) [22].Определение использует следующую идею: учитывая подписи на некотором числе сообщений, происходящих от двух различных наборов данных, злоумышленник не сможет сказать, от какого набора данных была произведена та или иная подпись и, кроме того, это свойство сохраняется, даже если произошла утечка секретного ключа. Подписи с такими свойствами конфиденциальности будем называть слабым сокрытием в контексте . Причиной для этой «слабости» является то, что мы предполагаем, что подлинные подписи на множестве данных не являются открытыми. Концепция такая же, как и у удостоверителя неразличимости [31], где в нашей настройке мы обращаемся к оригинальным набором данных как удостоверители.

В работе Ahn и соавт. (Ahn et al.) [24] определяется более сильное понятие конфиденциальности, называемое сильным сокрытием в контексте, которое требует от сгенерированных подписей распространения в качестве независимых свежих подписи на том же самом сообщении; это требование гарантирует конфиденциальность, даже если оригинальными подписи уязвимы.

TemplateDifinitionIcon.svg Определение «Определение 2.3»

Схема гомоморфной подписи называется слабым сокрытием в контексте, если для всех , преимущество любого вероятностного, полиномиального по времени в следующей игре пренебрежимо мала по параметру безопасности :

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

Задача: выводит , где . Функции и удовлетворяют

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

Далее, для претендент вычисляет подпись на . посылаются тег и подписи . Заметим, что функции могут быть выведены адаптивно после того, как будут выведены .

Выход: выдает бит .

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

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

Эффективность длины

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

TemplateDifinitionIcon.svg Определение «Определение 2.4»

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

,

тогда для всех , полученная подпись имеет битовую длину не более, чем с огромной вероятностью.

Применения

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

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

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

Где - матрица Вандермонда для , в которой -ый столбец это вектор и это вектор-столбец . Степень обычно мала, например, для метода наименьших квадратов с линией.

Используя гомоморфные подписи, серверу можно задать набор индивидуально подписанных точек данных и извлечь из него подпись на подборе наименьшими квадратами (или, точнее, подпись на векторе коэффициентов ). Если подпись эффективна по длине, то для фиксированного длина полученной подписи зависит логарифмически только от числа точек данных . Если подписи закрытые, то полученная на подпись не раскрывает никакой информации об исходном наборе данных после раскрытия через f.

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

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

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

Более продвинутый интеллектуальный анализ данных

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

Предварительные замечания

Обозначения. Для любого целого , обозначим как кольцо целых чисел по модулю . Если - простое, является полем и обозначается . Положим - множество матриц с коэффициентами в . Будем говорить, что функция несущественная, если она равна для всех , и обозначим ее как - несущественная функция от переменных. Будем также говорить, что полиномиальная, если она равна для некоторого , и обозначим ее как - полиномиальная функция от переменных. Событие происходит с подавляющей вероятностью, если его вероятность равна . Функция - логарифм с основанием 2.

Решетки. -мерная решетка - это полноранговая дискретная подгруппа в . Стандартные результаты на решетках, которые мы используем появляются в полной версии этой работы [32]. Здесь же кратко отметим, что наши схемы будут использовать алгоритм SamplePre [[26], теорема 5.9], которая принимает на вход базис -мерной решетки , параметр и вектор , и дает на выходе вектор в смежном классе из распределения Гаусса. Сам алгоритм SamplePre построен из алгоритма SampleGaussian [[26], теорема 4.1], который выводит вектор в решетке выборкой из распределения Гаусса.

Наши линейно гомоморфные схемы будут использовать «-мерные» решетки, определяемые следующим образом: для любое целого и любого , мы определяем . Наши схемы будут использовать алгоритм TrapGen [[34], теорема 3.2], который делает выборку (почти) равномерно случайной матрицы вместе с «коротким» базисом для .

Сложность предположения. Определим обобщение нестандартного решения Задачи Поиска Вектора по Норме (SIS), которая заключается в нахождении короткого ненулевого вектора в некотором классе решеток.

TemplateDifinitionIcon.svg Определение «Определение 3.1»

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

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

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


Когда состоит из для равновероятных случайных задача является стандартной задачей определенной Миссиансио и Регевом (Micciancio, Regev)[30]. Для этого распределения решеток, алгоритм, который решает задачу может быть использован для решения наихудших проблем на произвольных решетках [[30], § 5].

Гомоморфные подписей для линейных функций над небольшими полями

В качестве "разминки" для нашей полиномиально гомоморфной схемы, опишем схему, которая может аутентифицировать любую линейную функцию подписанных векторов, определенных на небольшом поле . Предыдущие конструкции достигают данной функциональности только на больших полях [5], [7] или для небольшого числа векторов [9]. В частности, наша схема легко оперирует с двоичными данными (). Пример примитива, который можно построить над решетками - это линейно гомоморфные подписи над , но в настоящее время построение их из дискретных протоколов или предположений RSA-типа невозможно. В полной версии этой работы [32] мы описали вариант схемы, в которых данные могут принимать значения на больших полях .

Безопасность основана на задаче на -ичных решетках для некоторого простого ; Миссиансио и Регев (Micciancio, Regev) [30], опираясь на работу Айтая (Ajtai) [35], показывают, что решение этой задачи имеет такую же сложность, как и задача стандартных наихудших проблемы произвольных решеток размерности примерно . Системы в данном разделе безопасны лишь для малых , в частности, , где для наборов данных размера .

Обзор схемы

Так как наша система основана на подписях типа"хэширование-и-подпись" (“hash-and-sign”) Джентри, Пэйкерта и Вайкунтанатана (Gentry, Peikert, Vaikuntanathan) [26], давайте вспомним, как GPV подписи работают в абстрактном смысле. Открытый ключ - это решетка , а секретный ключ это короткий базис . Чтобы подписать сообщение , владелец секретного ключа хэширует в элемент и представляет собой образец короткого вектора из смежного класса , определенного . Для верификации , проверяется, что короткая и что .

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

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

Эта двойная подпись вычисляется через так называемый «метод пересечения», который работает следующим образом. Пусть и - -мерные целочисленные решетки, . Положим - сообщение и это хэш-функция (зависящая от тега ), которая отображает кодирование функций в элементы из . Так как сообщение определяет класс смежности в и хэш-функция определяет класс смежности в , по Китайской теореме об остатках пара определяет уникальный смежный класс в . Таким образом, можно использовать короткий базис для расчета коротких вектор в этом классе; т.е. короткий вектор со свойством и . Вектор - это подпись на .

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

Гомоморфная конфиденциальность теперь получается следующим образом. Для аутентификации линейной комбинации для целых , вычисляем подпись . Если и достаточно малы, то - короткий вектор. Кроме того, имеем:

.

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

Линейная гомоморфная схема

Опишем схему.

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

  1. Выбираются два простых числа , где . Определяем ;
  2. Зададим ;
  3. Используем для генерации матрицы наряду с коротким базисом в . Определим и ;
  4. Пусть - хэш-функция (сгенерированная как случайный оракул).
  5. На выходе открытый ключ и секретный ключ .

Открытый ключ определяет следующие параметры системы:

  • - пространство сообщений, а подписи – это короткие вектора в .
  • Множество допустимых функций - это все -линейные функции от -кортежей сообщений из .
  • Для функции , определенной как , мы кодируем , интерпретируя как целые числа из , и .
  • Для оценки хэш-функции на закодированной функции делается следующе:
(a) Для вычисляется в .
(b) Определить .

. На входе секретный ключ , тег , сообщение и индекс . Выполняется следующее:

  1. Вычисляется . Затем, по определению, .
  2. Вычисляется так, что и .
  3. На выходе

. На входе открытый ключ , тег , сообщение , подпись и функция . Выполняется:

  1. Если все из следующих условий выполняются, то на выходе (принято); иначе

На выходе (изъято):

(a) .
(b) .
(c) .

. На входе открытый ключ , тег , функция , закодированная в виде и кортеж подписей . На выходе .

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

Неподдельность

Мы покажем, что противник, который подделывает подпись для линейно гомоморфной схемы может использовать для вычислений короткий вектор в решетке , выбраной в Шаге 3 из Setup. В силу Теоремы 3.2 [34], распределение матриц , используемых для определения статистически близко к равномерному распределению на . Таким образом, распределение решеток выводящееся алгоритмом Setup, статистически близка к распределению испытаний для задачи (для любого ). Наша теорема безопасности заключается в следующем.

TemplateTheoremIcon.svg Теорема Теорема 4.1

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

Доказательство

Набросок доказательства Пусть - противник, который учавствует в игре по безопасности по Определению 2.1. Зададим решетку для , мы моделируем алгоритм Sign со входом для случайного выбирая короткий вектор из распределения Гаусса на и определяя . Затем - действительная подпись на . Другие запросы к получают ответ аналогичным способом, но со случайным сообщением . Параметр Гаусса достаточно большой, чтобы был статистически близок к равномерному распределению в


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

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

Соединения в наихудшем случае

В силу предположения 5.7 [26], если , то решение задачи имеет такую же сложность, как и аппроксимация задачи SIVP в худшем случае в пределах множителей. Для алгоритма Setup мы требуем, чтобы , что гарантирует, что является достаточно большим в этой теореме для применения. Хотя фактор наихудшего случая аппроксимации будет зависеть от параметров и .

Сравнение с предыдущей работой

Боне и Фримен (Boneh, Freeman) [9] в своей работе описывают, что линейно гомоморфная схема подписи, может аутентифицировать вектора над при малых , с неподдельностью, в зависимости от задачи SIS. Тем не менее, чтобы надежно подписать сообщений в их системе, задача должна быть сложна для , и поэтому их система предназначена только для подписывания постоянное число векторов на набор данных , сохраняя при этом полиномиальную связь к проблемам решеток в наихудшем случае. С другой стороны, для тех же самых значений наша система остается безопасной при подписывании векторов на набор данных.

Конфиденциальность

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

{{Определение|Теорема 4.2| Предположим, что , определенная в алгоритме Setup, удовлетворяет . Тогда схема линейно гомоморфной подписи, описанная выше, -слабо скрывающая в контексте для наборов данных размера .

Справочная информация об Идеальных Решетках

Числовое поле – это алгебраическое расширения рациональных чисел конечной степени. Любое числовое поле может быть представлено в виде для некоторого унитарного, неприводимого многочлена с целыми коэффициентами (и для каждого есть бесконечно много таких ). Степенью числового поля является его размер, как векторное пространство над , а также степень любого многочлена , определяющего . Для любого заданного , множество является Q-базис для , и поэтому мы можем определить с путем сопоставления полинома степени меньше к ее вектором коэффициентов. Определив с используя это "вложение коэффициентов", мы можем определить функцию длины на элементах из просто используя какую-либо норму на . Эта функция длины неканоническая - она явно зависит от выбора используемых для представления (здесь все нормы будут обозначаться , если не указано иначе).

Наше определение с порождает мультипликативную структуру на в дополнение к обычной добавочной структуре. Мы определяем параметр . Этот параметр ограничивает насколько умножение может увеличить длину произведения, по отношению к произведению длины множителей. Для наших применений мы должны иметь . Если является степенью двойки, то функция имеет (см. [[1], лемма 7.4.3]). Мы будем думать об , как о нашем предпочтительном выборе для применения.

Числовые кольца и идеалы

Числовое кольцо это кольцо, чье поле дробей является числовым полем . Обзор арифметики в числовых кольцах можно найти в работе [36]; здесь мы суммируем ключевые моменты.

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

Идеал (интеграл) это аддитивная подгруппа , замкнутое относительно умножения на элементы из . По нашему определению с , идеал является подрешеткой и, следовательно, также называется идеальной решеткой. Отметим, что термин «идеальная решетка» используется для обозначения ранга одного -модульного отличия [27],[29], которое использует терминологию -модуля для обозначения произвольного ранга.

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

Если -простой идеал в , то по теореме Куммера и Дедекинда [[36], теорема 8.2], мы можем написать для некоторого многочлена , изменение которого по является неприводимым множителем . Запись в этом «двух-элементном представлении» позволяет легко вычислить соответствующее фактор-отображение ; мы просто уменьшаем многочлен по модулю и и . В частности, если - простое первой степени, то для некоторого целого и фактор-отображение дается через .

Получение идеалов с коротким базисом

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

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

TemplateDifinitionIcon.svg Определение «Теорема 5.1 ([[2], § 3.1])»

Существует алгоритм PrincGen, который принимает на вход единичный неприводимый многочлен степени и параметр , и дает на выходе главный простой идеал степени один в , наряду с образующей от , удовлетворяющих

Алгоритм работает, выбирая случайное с низкой нормой, и проверяя порождает ли оно простой идеал в . Смарт и Веркотерен не дают строгого анализа для времени работы алгоритма, но эвристически мы ожидаем, что по аналогу числового поля из теоремы о простых числах [[37], теорема 8.9], мы найдем простой идеал, испробуя значении .

Гомоморфные Подписи для Полиномиальных Функций

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

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

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

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

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

Хэш-функция определяется так же, как в нашей линейной схеме: для функции в , кодировка которой , определим полиномиальную функцию , которая уменьшается до . Затем определим , где определяются как для некоторой хэш-функции .

Мы используем тот же увеличение с до для оценки многочленов на подписях; в частности, данный многочлен и подписи на сообщениях , подпись на имеет вид .

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

Полиномиально гомоморфная схема

Теперь опишем схему формально.

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

  1. Выбираем единичный неприводимый многочлен степени с . Пусть вложено в с помощью коэффициента вложения. Пусть - решетка, соответствующая .
  2. Дважды запускаем алгоритм PrincGen со входами и для получения различных главных простых идеалов степени единица и с образующими соответственно.
  3. Пусть - базисы в .
  4. Определяем . Выбераем целых чисел и .
  5. Пусть - хэш-функция (смоделированная как случайный оракул).
  6. На выходе открытый ключ и секретный ключ .

Открытый ключ определяет следующие параметры системы:

  • Пространство сообщений - и подписи – короткие вектора в .
  • Набор допустимых функций это все многочлены в с коэффициентами из , степени не больше и постоянным нулевым членом. Величина используется только в алгоритме Verify.
  • Пусть . И пусть - набор не постоянных одночленов степени в лексикографическом порядке. Тогда любая полиномиальная функция определяется как для .Мы интерпретируем как целые числа в , и кодируем как .
  • Для оценки хэш-функции на закодированной функции <f>=(c_1,\ldots,c_l)\in Z^l,

выполняется следующее:

(a) Для вычисляется .
(b) Определяется .

Sign(sk,\tau,m,i). На входе секретный ключ , тег , сообщение и индекс