Русская Википедия:Криптосистема Боне — Го — Ниссима

Криптосистема Боне — Го — Ниссима — частично гомоморфная криптосистема, являющаяся модификацией криптосистемы Пэйе^[1] и криптосистемы Окамото — Утиямы^[2]. Разработана Дэном Боне^[3] совместно с Ю Чжин Го и Коби Ниссимом^[4] в 2005 году^[5]. Основывается на конечных группах составного порядка и билинейных спариваний на эллиптических кривых; система позволяет оценить многовариантные квадратичные полиномы на шифротекстах (например, дизъюнктивная нормальная форма второго порядка (2-ДНФ)).

Система обладает аддитивным гомоморфизмом (поддерживает произвольные добавления и одно умножение (за которым следуют произвольные добавления) для зашифрованных данных).

Используемый в криптосистеме БГН алгоритм основан на задаче Бернсайда.^[6].

Алгоритм работы

Как и все системы гомоморфного шифрования, КБГН включает следующие процессы: Генерация ключа, шифрование и расшифрование.

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

<math>\mathbb{G}</math> и <math>\mathbb{G}_1</math>- две циклические группы конечного порядка <math>{n}</math>.
<math>{g}</math> — генератор <math>\mathbb{G}</math>.
<math>{f}</math> — билинейное отображение <math>{f}:\mathbb{G}\times\mathbb{\mathbb{G}}\rightarrow\mathbb{G}_1</math>. Другими словами, для всех <math>{u} , {v} \in\mathbb{G}</math> и <math>{a} , {b} \in\mathbb{Z}</math> мы имеем <math>{f}({u}^{a},{v}^{b}) = {f}({u},{v})^{{a}{b}}</math>. Мы также требуем выполнение условия : <math>{f}({g},{g})</math> является генератором <math>\mathbb{G}_1</math>

Мы говорим, что <math>\mathbb{G}</math> — билинейная группа, если существует группа <math>\mathbb{G}_1</math> и билинейное отображение, определённое выше.^[7]

Генерация ключа

Генерация_Ключа(<math>\tau</math>):

Подавая на вход параметр безопасности <math>\tau\in\mathbb{Z}^+</math>, вычисляем алгоритм <math>X(\tau)</math>, чтобы получить кортеж <math>({q}_1,{q}_2,\mathbb{G},\mathbb{G}_1,{f})</math>. Алгоритм работает следующим образом:
1. Сгенерируем два случайных <math>\tau</math> — битовых числа <math>{q}_1</math> и <math>{q}_2</math> и положим <math>{n}={q}_1{q}_2\in\mathbb{Z}</math>.
2. Создадим билинейную группу <math>\mathbb{G}</math> порядка <math>{n}</math>, где <math>{n}</math> > 3 — заданное число, которое не делится на 3:
  1. Найдём наименьшее натуральное число <math>\ell\in\mathbb{Z}</math> , такое что <math>{p}=\ell{n}-1</math> — простое число и <math>{p=3\bmod 4}</math>.
  2. Рассмотрим группу точек на эллиптической кривой <math>{y^2=x^3+x}</math> опреленную над <math>\mathbb{F}_{p}</math>. Поскольку <math>{p=3\bmod 4}</math> кривая имеет <math>{p}+1=\ell{n}</math> точек в <math>\mathbb{F}_{p}</math>. Поэтому группа точек на кривой имеет подруппу порядка <math>{n}</math>, которую обозначим через <math>\mathbb{G}</math>.
  3. Пусть <math>\mathbb{G}_1</math> подгруппа в <math>\mathbb{F}^*_{{p}^2}</math>порядка <math>{n}</math>. Модифицированный алгоритм спаривания Вейля (Спаривание Вейля является билинейным, кососимметричным, невырожденным отображением^[8]^[4]^[9]^[10]) на кривой выдаёт билинейное отображение <math>{f}:\mathbb{G}\times\mathbb{\mathbb{G}}\rightarrow\mathbb{G}_1</math>, удовлетворяющее заданным условиям
3. На выходе получим <math>({q}_1,{q}_2,\mathbb{G},\mathbb{G}_1,{f})</math>.
Пусть <math>{n}={q}_1\times{q}_2</math>. Выберем два случайных генератора <math>{g},{u}\xleftarrow{R}\mathbb{G}</math> и определим <math>{h}</math>, как <math>{h}={u}^{q_2}</math>. Тогда <math>{h}</math> это случайный генератор подгруппы <math>\mathbb{G}</math> порядка <math>{q_1}</math>. Открытый ключ : <math>{O}{K}=({n},\mathbb{G},\mathbb{G_1},{f},{g},{h})</math>. Закрытый ключ : <math>{S}{K}={q_1}</math>.^[11]^[7]

Шифрование

Шифр(<math>OK,M</math>):

Мы предполагаем, что пространство сообщений состоит из целых чисел в наборе <math>\{0,T\}</math>. Чтобы зашифровать сообщение <math>M</math> с помощью открытого ключа <math>OK</math> выбираем случайный параметр <math>{r}\xleftarrow{R}\{0,1,...,{n}-1\}</math> и вычисляем

<math>{C}={g}^{M}{h}^{r}\in\mathbb{G}</math> .

Полученный результат и есть шифротекст.^[11]^[7]

Расшифрование

Расшифр(<math>SK,C</math>):

Чтобы расшифровать шифротекст используя закрытый ключ <math>SK=q_1</math>, рассмотрим следующее выражение

<math>{C}^{q_1}=({g}^{M}{h}^{r})^{q_1}=({g}^{q_1})^{M}</math> .

Пусть <math>\hatШаблон:G={g}^{q_1}</math> . Чтобы восстановить <math>{M}</math> достаточно вычислить дискретный логарифм <math>{C}^{q_1}</math> по основанию <math>\hatШаблон:G</math>.

Следует отметить, что дешифрование в этой системе занимает полиномиальное время в размере пространства сообщений.^[11]^[7]

Примеры

Пример работы алгоритма

Сначала мы выбираем два различных простых числа

<math>{{q}_1=7}</math> <math>{{q}_2=11}</math>.

Вычислим произведение

<math>{{n}={q}_1{q}_2=7\times11=77}</math>.

Далее мы строим группу эллиптических кривых с порядком <math>{n}</math>, которая имеет билинейное отображение. Уравнение для эллиптической кривой

которое определяется над полем <math>\mathbb{F}_{p}</math> для некоторого простого числа <math>{p=3\bmod 4}</math>. В этом примере мы устанавливаем

<math>{p=307}</math>.

Следовательно, кривая суперсингулярна с #<math>{(E(p))=p+1=308}</math> рациональными точками, которая содержит подгруппу <math>\mathbb{G}</math> с порядком <math>{{n}=77(=308/4)}</math> . В группе <math>\mathbb{G}</math> мы выбираем два случайных генератора

где эти два генератора имеют порядок <math>{n}</math> и вычислим

где <math>{h}</math> порядка <math>{q_1=7}</math>. Мы вычисляем зашифрованный текст сообщения

<math>{M}{=2}</math> .

Возьмём <math>{r=5}</math> и вычислим

<math>{C={g}^{M}{h}^{r}=[182,240]^2\oplus[99,120]^5=[256,265]}</math>.

Для расшифровки мы сначала вычислим

<math>\hatШаблон:G={g^{q_1}=[182,240]^7=[146,60]}</math>

и

<math>{C}^{q_1}=({g}^{M}{h}^{r})^{q_1}=({g}^{q_1})^{M}={[256,265]^7=[299,44]}</math>.

Теперь найдём дискретный логарифм, перебирая все степени <math>\hatШаблон:G={g}^{q_1}</math> следующим образом

<math>\hatШаблон:G^{1}={[146,60]}</math>

<math>\hatШаблон:G^{2}={[299,44]}</math>

<math>\hatШаблон:G^{3}={[272,206]}</math>

<math>\hatШаблон:G^{4}={[191,151]}</math>

<math>\hatШаблон:G^{5}={[79,171]}</math>

<math>\hatШаблон:G^{6}={[79,136]}</math>

<math>\hatШаблон:G^{7}={[191,156]}</math>

<math>\hatШаблон:G^{8}={[272,101]}</math>

<math>\hatШаблон:G^{9}={[299,263]}</math>

<math>\hatШаблон:G^{10}={[146,247]}</math>

<math>\hatШаблон:G^{11}={\infty}</math>.

Обратите внимание, что <math>\hatШаблон:G^{2}={C^{q_1}}</math>. Следовательно, расшифровка зашифрованного текста равна <math>{2}</math>, что соответствует исходному сообщению.^[12]

Оценка 2-ДНФ

Частично гомоморфная система позволяет оценить 2-ДНФ.

На входе: У Алисы есть 2-ДНФ формула <math>\phi(x_1,...,x_n)=\lor_{i=1}^k(l_{i,1}\land l_{i,2})</math>, а у Боба есть набор переменных <math>{a=a_1,...,a_n\in\{0,1\}^n}</math> . Обе стороны на входе содержат параметр безопасности <math>\tau</math>.

Боб выполняет следующие действия:
1. Он исполняет алгоритм Генерация_Ключа(<math>\tau</math>), чтобы вычислить <math>{O}{K},{SK}</math> и отправляет <math>{O}{K}</math> Алисе.
2. Он вычисляет и отправляет Шифр(<math>{O}{K},{a_j}</math>) для <math>{j=1,...,n}</math>.
Алиса выполняет следующие действия:
1. Она выполняет арифметизацию <math>\Phi(\phi)</math> заменяя «<math>\lor</math>» на «<math>+</math>», «<math>\land</math>» на «<math>\times</math>» и «<math>\bar{x_j}</math>» на «<math>(1-x_j)</math>».Отметим, что <math>\Phi</math> это полином степени 2.
2. Алиса вычисляет шифрование <math>{r}\times\Phi({a})</math> для случайно выбранного <math>{r}</math> используя гомоморфные свойства системы шифрования. Результат отправляется Бобу.
Если Боб получает шифрование «<math>0</math>», он выводит «<math>0</math>»; в противном случае, он выводит «<math>1</math>».^[13]

Гомоморфные свойства

Система является аддитивно гомоморфной. Пусть <math>({n},\mathbb{G},\mathbb{G_1},{f},{g},{h})</math> — открытый ключ. Пусть <math>{C_1} , {C_2} \in\mathbb{G}_1</math> — шифротексты сообщений <math>{m_1} , {m_2} \in\{0,1\}</math> соответственно. Любой может создать равномерно распределённое шифрование <math>{m_1}+{m_2}\bmod {n}</math> вычисляя произведение <math>{C}={C_1}{C_2}{h}^{r}</math> для случайного чила <math>{r}</math> в диапазоне <math>\{0,1,...,{n}-1\}</math>.

Более важно то, что любой может умножить два зашифрованных сообщения один раз, используя билинейное отображение. Определим <math>{g_1}={f}({g},{g})</math> и <math>{h_1}={f}({g},{h})</math> . Тогда <math>{g_1}</math> порядка <math>{n}</math>, а <math>{h_1}</math> порядка <math>{q_1}</math>. Кроме того, для некоторого (неизвестного) параметра <math>\alpha\in\mathbb{Z}</math>, напишем <math>{h}={g}^{\alpha{q_2}}</math> . Предположим, что нам известны два шифротекста <math>{C_1}={g}^{m_1}{h}^{r_1}\in\mathbb{G}</math>, <math>{C_2}={g}^{m_2}{h}^{r_2}\in\mathbb{G}</math>. Чтобы построить шифрование произведения <math>{m_1}\times{m_2}\bmod {n}</math>, выберем случайное число <math>{r}\in\mathbb{Z_n}</math> и положим <math>{C}={f}({C_1},{C_2}){h_1^r}\in\mathbb{G}_1</math>. Получаем <math>{C=f(C_1,C_2)h_1^r=f(g^{m_1}h^{r_1},g^{m_2}h^{r_2})h_1^r=g^{m_1m_2}h^{m_1r_2+r_2m_1+\alpha q_2r_1r_2+r}=g_1^{m_1m_2}h_1^{\tilde{r}}}\in\mathbb{G}_1</math>, где<math>{\tilde{r}=m_1r_2+r_2m_1+\alpha q_2r_1r_2+r}</math> — распределено равномерно в <math>\mathbb{Z_n}</math>, как и необходимо.

Таким образом, <math>{C}</math> является равномерно распределённым шифрованием <math>{m_1}\times{m_2}\bmod {n}</math>, но только в группе <math>\mathbb{G}_1</math>, а не в <math>\mathbb{G}</math> (поэтому допускается только одно умножение).^[11]

Стойкость системы

Стойкость данной схемы основана на задаче Бернсайда: зная элемент группы составного порядка <math>{n}={q}_1{q}_2</math>, невозможно определить его приналежность к подгруппе порядка <math>{q_1}</math>.

Пусть <math>\tau\in\mathbb{Z}^+</math>, а <math>({q}_1,{q}_2,\mathbb{G},\mathbb{G}_1,{f})</math> — кортеж, созданный <math>X</math>, где <math>{n}={q}_1{q}_2</math>. Рассмотрим следующую задачу. Для заданного <math>({n},\mathbb{G},\mathbb{G}_1,{f})</math> и элемента <math>{x}\in\mathbb{G}</math>, выведем «<math>1</math>», если порядок <math>{x}</math> равен <math>{q_1}</math>, в противном случае, выведем «<math>0</math>». Другими словами, без знания факторизации группы порядка <math>{n}</math>, необходимо узнать, находится ли элемент <math>{x}</math> в подгруппе группы <math>\mathbb{G}</math>. Данная задача называется задачей Бёрнсайда^[7].

Понятно, что если мы можем учесть групповой порядок <math>{n}</math> в криптосистеме, то мы знаем закрытый ключ <math>{q_1}</math>, и в результате система взломана. Кроме того, если мы можем вычислить дискретные логарифмы в группе <math>\mathbb{G}</math>, то мы можем вычислить <math>{q_2}</math> и <math>{q_1=n/q_2}</math>. Таким образом, необходимые условия для безопасности: сложность факторинга <math>{n}</math> и сложность вычисления дискретных логарифмов в <math>\mathbb{G}</math>.^[14]

Примечания

Шаблон:Примечания

Литература

Шаблон:Книга

Ссылки

Шаблон:Статья

Шаблон:Криптосистемы с открытым ключом

[1] Шаблон:Статья

[2] Шаблон:Статья

[3] Шаблон:Статья

[:0-4] 4,0 ^4,1 Шаблон:Статья

[5] Шаблон:Cite web

[6] Шаблон:Книга

[:2-7] 7,0 ^7,1 ^7,2 ^7,3 ^7,4 Шаблон:Статья

[8] Шаблон:Книга

[9] Шаблон:Статья

[10] Шаблон:Статья

[:1-11] 11,0 ^11,1 ^11,2 ^11,3 Шаблон:Книга

[12] Шаблон:Книга

[13] Шаблон:Книга

[14] Шаблон:Книга

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.