Просмотр кода страницы Falcon (криптоалгоритм)

{{значения|Falcon}}
'''Falcon''' ({{lang-en|Fast-Fourier Lattice-Based Compact Signs over NTRU}}) — [[Постквантовая криптография|постквантовый]] алгоритм криптографической подписи поверх решёток {{iw|NTRU}}.

Представлен в {{iw|Проект NIST по стандартизации постквантовой криптографии|проекте постквантовой криптографии NIST||NIST Post-Quantum Cryptography Standardization}} 30 ноября 2017 года, авторы — Томас Прест, Пьер-Ален Фуке, Джеффри Хоффштейн, Полом Киршнер, Вадим Любашевский, Томас Порнин, Томас Рикоссе, Грегор Зайлер, Уильям Уайт, Чжэнфей Чжан. Использует преимущества нескольких инструментов для обеспечения компактности и эффективности с доказуемой безопасностью. Использование решётки NTRU позволяет сделать размер подписи и открытого ключа относительно небольшим, в то время как [[быстрое преобразование Фурье]] обеспечивает эффективное вычисление подписи. При этом с точки зрения безопасности NTRU обладает пониженной безопасностью по сравнению с [[Случайный оракул|моделью квантового случайного оракула]].

Эталонные реализации выполнены на [[Си (язык программирования)|Си]] и [[Python]].

== Свойства ==
Для обеспечения безопасности используется гауссов семплер, что гарантирует малую утечку информации о секретном ключе вплоть до практически бесконечного количества подписей (более 2<sup>64</sup>). Компактность обеспечивается благодаря использованию решёток NTRU — подписи существенно короче, чем в любой схеме подписи на основе решёток с теми же гарантиями безопасности, а открытые ключи имеют примерно такой же размер.

Алгоритм масштабируем — его [[Вычислительная сложность|асимптотическая сложность]] <math>O(n \log n)</math> позволяет использовать долговременные параметры безопасности при умеренных затратах. Усовершенствованный алгоритм генерации ключей Falcon использует менее 30 килобайт оперативной памяти, таким образом, Falcon совместим с небольшими встроенными устройствами с ограниченным объёмом памяти.

Кроме того, в версии Falcon-512 все операции выполняются с постоянным временем, в том числе операции с плавающей точкой. 

Применение быстрого преобразования Фурье позволяет реализовывать тысячи подписей в секунду на обычном компьютере, a проверка проходит в пять-десять раз быстрее. Версия Falcon-512 имеет уровень безопасности NIST 1 (безопасность, сравнимая со взломом битов [[AES (стандарт шифрования)|AES-128]]), а версия Falcon-1024 имеет уровень безопасности NIST 5 (сравнимый со взломом [[AES (стандарт шифрования)|AES-256]]). Используя эталонную реализацию на обычном настольном компьютере (Intel Core i5-8259U с тактовой частотой 2,3 ГГц, TurboBoost отключён), Falcon достигает следующей производительности:
{| class="wikitable"
|+
!Версия
!Время генерации ключа (мс)
!Пропускная способность (подписей/с)
!Пропускная способность(проверок/с)
!Размер сигнатуры (байт)
|-
|Falcon-512
|8,64
|5948,1
|27930
|666
|-
|Falcon-1024
|27,45
|2913,0
|13650
|1280
|}

== Основные элементы ==
Основными элементами в Falcon являются многочлены степени <math>n</math> с целыми коэффициентами. Степень <math>n</math> обычно является степенью двойки (обычно 512 или 1024). Вычисления производятся по модулю многочлена одной переменной степени <math>n</math>, обозначаемого <math>\phi</math> (который всегда имеет вид <math>\phi = x^{n} + 1 </math>). 

Математически в алгоритме некоторые многочлены интерпретируются как векторы, а другие – как матрицы. Полином <math>f</math> по модулю <math>\phi</math> обозначает квадратную матрицу <math>n \times n</math>, строками которой являются <math>x^{i}f \pmod \phi </math> для всех <math>i</math> от 0 до <math>n-1</math>. Сложение и умножение таких матриц сводится к сложению и умножению многочленов по модулю <math>\phi</math>. Поэтому Falcon реализован в терминах операций над многочленами, даже в операциях с матрицами, определяющими решётку.

== Генерация ключевой пары ==
Генерация ключевой пары включает в себя генерацию случайных многочленов <math>f</math> и <math>g</math> с простым распределением гаусса и решение уравнения NTRU для вычисления <math>F</math> и <math>G</math>. Генерация  <math>f</math> и <math>g</math>:

* генерируется случайный бит <math>s</math>, а также случайная величина <math>v_0</math>; если <math>v_0</math> меньше заданной константы <math>c_0</math>, то коэффициент будет равен нулю;
* Генерируется случайное 63-битное значение <math>v_{1}</math>, и используется таблица констант: получается индекс <math>k</math> первого значения <math>c_{k}</math>, которое не больше <math>v_{1}</math> (элементы таблицы индексируются, начиная с 1, и идут по убыванию, последний равен 0, что гарантирует уникальность решения).
* если <math>v_0 < c_0</math>, то новый коэффициент многочлена равен 0; в противном случае его значение равно <math>(-1)^{s}k </math>; все операции выполняются систематически, то есть тест на <math>v_{0}</math> выполняется в постоянном времени, а поиск <math>v_{1}</math> в таблице выполняется всегда, независимо от результата теста на <math>v_{0}</math>; поиск в таблице выполняется путем чтения всех элементов таблицы;
* решении уравнения NTRU; при решении уравнения NTRU вычисляются многочлены различных степеней, коэффициенты которых являются большими целыми числами; используется [[Система остаточных классов|RNS]] (система остаточных чисел) для больших целых чисел, поэтому работа происходит с ожидаемой длиной целых чисел, а не с их истинной длиной.

В итоге, открытый ключ <math>pk </math>, соответствующий закрытому ключу <math>sk = (f, g, F, G)</math> – это многочлен <math>h \in Z_{q} [x]/(\phi)  </math> такой, что:

: <math>h = gf^{-1} \pmod {\phi,q} </math>.

После получения подходящих многочленов <math>f</math>, <math>g</math>, <math>F</math>, <math>G</math>, вторая часть генерации ключа заключается в их обработке в подходящий формат. Под подходящим форматом подразумевается, компактность и возможность быстро генерировать подписи. К такому формату можно прийти с помощью Falcon-дерева. Чтобы вычислить Falcon-дерево, нужно вычислить <math>LDL^*</math>-разложение <math>G=BB^*</math>, где:
: <math>B = \ \ \ \begin{vmatrix}g\ \ -f\\
G\ \ \ \ F\end{vmatrix} </math>. 
Это эквивалентно вычислению [[Процесс Грама ― Шмидта|ортогонализации Грамма — Шмидта]] для <math>B = L \times B</math>.

== Вычисление подписи ==
Принцип алгоритма создания подписи:

* вычисление хэш-значение <math>c \in Z_{q} [x]/(\phi)</math> из сообщения <math>m</math> и [[Соль (криптография)|модификатора входа хэш-функции]] <math>r</math>.
* вычисление двух коротких значений <math>s_1</math> и <math>s_2</math>, таких, что <math>s_1 + s_2 h = c  \pmod q</math>, используя знание секретного ключа <math>f, g, F, G</math>.

== Преимущества и недостатки ==
Главными преимуществами алгоритма являются компактность, быстрота и несколько режимов работы (классический, режим восстановления сообщения, режим восстановления ключа). Кроме того, Falcon можно превратить в схему [[ID-based encryption|IBE]] (шифрование на основе идентификации) и в схему кольцевой подписи. Falcon является самой компактной схемой из всех постквантовых схем подписи. Но существуют и недостатки, в первую очередь это сложность для понимания и реализации и плохая устойчивость побочного канала к перехвату.

Сравнение размера открытого ключа с другими алгоритмами подписи на уровне NIST 5 (размеры в байтах): <graph>{
	"version": 2,
	"width": 1100,
	"height": 200,
	"data": [
		{
			"name": "table",
			"values": [
				{
					"x": "RSA-4096",
					"y": 800
				},
				{
					"x": "ECDSA-256",
					"y": 900
				},
				{
					"x": "DILITHIUM",
					"y": 1200
				},
				{
					"x": "Dual ModeMS",
					"y": 1200
				},
				{
					"x": "Falcon",
					"y": 1100
				},
				{
					"x": "MQDSS",
					"y": 100
				},
				{
					"x": "pqNTRUSign",
					"y": 3000
				},
				{
					"x": "Picnic",
					"y": 90
				},
				{
					"x": "qTESLA",
					"y": 9500
				},
				{
					"x": "SPHINCS+",
					"y": 90
				}
			]
		}
	],
	"scales": [
		{
			"name": "x",
			"type": "ordinal",
			"range": "width",
			"zero": false,
			"domain": {
				"data": "table",
				"field": "x"
			}
		},
		{
			"name": "y",
			"type": "linear",
			"range": "height",
			"nice": true,
			"domain": {
				"data": "table",
				"field": "y"
			}
		}
	],
	"axes": [
		{
			"type": "x",
			"scale": "x"
		},
		{
			"type": "y",
			"scale": "y"
		}
	],
	"marks": [
		{
			"type": "rect",
			"from": {
				"data": "table"
			},
			"properties": {
				"enter": {
					"x": {
						"scale": "x",
						"field": "x"
					},
					"y": {
						"scale": "y",
						"field": "y"
					},
					"y2": {
						"scale": "y",
						"value": 0
					},
					"fill": {
						"value": "steelblue"
					},
					"width": {
						"scale": "x",
						"band": "true",
						"offset": -1
					}
				}
			}
		}
	]
}</graph>Сравнение размера подписи с другими алгоритмами подписи на уровне NIST 5 (размеры в байтах):  <graph>{
	"version": 2,
	"width": 1100,
	"height": 200,
	"data": [
		{
			"name": "table",
			"values": [
				{
					"x": "RSA-4096",
					"y": 800
				},
				{
					"x": "ECDSA-256",
					"y": 900
				},
				{
					"x": "DILITHIUM",
					"y": 1200
				},
				{
					"x": "Dual ModeMS",
					"y": 1400
				},
				{
					"x": "Falcon",
					"y": 1050
				},
				{
					"x": "MQDSS",
					"y": 100
				},
				{
					"x": "pqNTRUSign",
					"y": 80000
				},
				{
					"x": "Picnic",
					"y": 100000
				},
				{
					"x": "qTESLA",
					"y": 9000
				},
				{
					"x": "SPHINCS+",
					"y": 80000
				}
			]
		}
	],
	"scales": [
		{
			"name": "x",
			"type": "ordinal",
			"range": "width",
			"zero": false,
			"domain": {
				"data": "table",
				"field": "x"
			}
		},
		{
			"name": "y",
			"type": "linear",
			"range": "height",
			"nice": true,
			"domain": {
				"data": "table",
				"field": "y"
			}
		}
	],
	"axes": [
		{
			"type": "x",
			"scale": "x"
		},
		{
			"type": "y",
			"scale": "y"
		}
	],
	"marks": [
		{
			"type": "rect",
			"from": {
				"data": "table"
			},
			"properties": {
				"enter": {
					"x": {
						"scale": "x",
						"field": "x"
					},
					"y": {
						"scale": "y",
						"field": "y"
					},
					"y2": {
						"scale": "y",
						"value": 0
					},
					"fill": {
						"value": "steelblue"
					},
					"width": {
						"scale": "x",
						"band": "true",
						"offset": -1
					}
				}
			}
		}
	]
}</graph>

== Литература ==
* {{Citation|author1=Thomas Prest|author2=Pierre-Alain Fouque|author3=Jeffrey Hoffstein|author4=Paul Kirchner|title=Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU|url=https://falcon-sign.info/falcon.pdf}}
* {{cite conference|author1=Craig Gentry|author2=Chris Peikert|author3=Vinod Vaikuntanathan|title=Trapdoors for Hard Lattices and New Cryptographic Constructions|url=https://eprint.iacr.org/2007/432|conference=STOC|date=2008 | conference-url = https://eprint.iacr.org/2007/432 }}
* {{cite conference|title=Random Oracles in a Quantum World|author1=Dan Boneh|author2=Özgür Dagdelen|author3=Marc Fischlin|author4=Anja Lehmann|author5=Christian Schaffner|author6=Mark Zhandry|conference=Asiacrypt|year=2011|url=https://eprint.iacr.org/2010/428}}
* Phong Q. Nguyen and Oded Regev. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 271–288. Springer, Heidelberg, May / June 2006.
* Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, and William Whyte. NTRUSIGN: Digital signatures using the NTRU lattice. In Marc Joye, editor, CT-RSA 2003, volume 2612 of LNCS, pages 122–140. Springer, Heidelberg, April 2003.
* Nick Howgrave-Graham. A hybrid lattce-reduction and meet-in-the-middle attack against NTRU. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 150–169. Springer, Heidelberg, August 2007.
* Jean-Sébastien Coron and Jesper Buus Nielsen, editors. EUROCRYPT 2017, Part I, volume 10210 of LNCS. Springer, Heidelberg, April / May 2017.

== Ссылки ==
* {{URL|https://falcon-sign.info/|Falcon official website}}
* {{URL|https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022|List of NIST PQC selected candidates}}
* {{URL|https://falcon-sign.info/impl/falcon.h.html|Reference implementation of Falcon in C}}
* {{URL|https://github.com/tprest/falcon.py|Implementation of Falcon in Python}}
* {{URL|https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/Call-for-Proposals|NIST Post-Quantum Cryptography Call for Proposals}}

{{rq|isbn|refless}}

[[Категория:Криптография на решётках]]
[[Категория:Криптография]]