Альфапедия

Задача решения для коротких целых чисел

редактировать

Решение для коротких целых чисел (SIS) и Ring-SIS - это две задачи среднего случая проблемы, которые используются в конструкциях криптографии на основе решеток. Криптография на основе решеток началась в 1996 году с плодотворной работы Айтая, который представил семейство односторонних функций, основанных на проблеме SIS. Он показал, что это безопасно в среднем случае, если самая короткая векторная задача SVP γ {\ displaystyle \ mathrm {SVP} _ {\ gamma}}{\ displaystyle \ mathrm {SVP} _ {\ gamma}} (где γ = nc {\ displaystyle \ gamma = n ^ {c}}{\ displaystyle \ gamma = n ^ {c}} для некоторой константы c>0 {\ displaystyle c>0}c>0 ) в худшем случае сложно.

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

Содержание
  • 1 Решетки
  • 2 Идеальная решетка
    • 2.1 Циклические решетки
    • 2.2 Идеальные решетки
  • 3 Краткое целочисленное решение задачи
    • 3.1 SIS n, m, q, β
    • 3.2 Ring-SIS
    • 3.3 R-SIS m, q, β
  • 4 См. Также
  • 5 Ссылки
Решетки

Полный ранг решетка L ⊂ R n {\ displaystyle {\ mathfrak {L}} \ subset \ mathbb {R} ^ {n}}{\ displaystyle {\ mathfrak {L}} \ subset \ mathbb {R} ^ {n}} представляет собой набор целочисленных линейных комбинаций n {\ displaystyle n}n линейно независимые векторы {b 1,…, bn} {\ displaystyle \ {b_ {1}, \ ldots, b_ {n} \}}{\ displaystyle \ {b_ {1}, \ ldots, b_ {n} \}} , именованный базис:

L (b 1,…, bn) = {∑ i = 1 nzibi: zi ∈ Z} = {B z: z ∈ Z n} {\ displaystyle {\ mathfrak {L }} (b_ {1}, \ ldots, b_ {n}) = \ left \ {\ sum _ {i = 1} ^ {n} z_ {i} b_ {i}: z_ {i} \ in \ mathbb {Z} \ right \} = \ {B {\ boldsymbol {z}}: {\ boldsymbol {z}} \ in \ mathbb {Z} ^ {n} \}}{\ displaystyle {\ mathfrak {L}} (b_ {1}, \ ldots, b_ {n}) = \ left \ {\ sum _ {i = 1} ^ {n} z_ {i} b_ {i}: z_ {i} \ in \ mathbb {Z} \ right \} = \ {B {\ boldsymbol {z}}: {\ boldsymbol {z}} \ in \ mathbb {Z} ^ {n} \}}

где B ∈ R n × n {\ displaystyle B \ in \ mathbb {R} ^ {n \ times n}}{\ displaystyle B \ in \ mathbb {R} ^ {n \ times n}} - матрица, имеющая базисные векторы в своих столбцах.

Примечание: Дано B 1, B 2 {\ displaystyle B_ {1}, B_ {2}}{\ displaystyle B_ {1}, B_ {2}} два основания для решетки L {\ displaystyle {\ mathfrak {L}}}{\ displaystyle {\ mathfrak {L}}} , существуют унимодулярные матрицы U 1 {\ displaystyle U_ {1}}{\ displaystyle U_ {1}} такие, что B 1 = B 2 U 1 - 1, B 2 = B 1 U 1 {\ displaystyle B_ {1} = B_ {2} U_ {1} ^ {- 1}, B_ {2} = B_ {1} U_ {1}}{\ displaystyle B_ {1} = B_ {2} U_ {1} ^ {- 1}, B_ {2} = B_ {1} U_ {1}} .

Идеальная решетка

Определение: Оператор ротационного сдвига на R n (n ≥ 2) {\ displaystyle \ mathbb {R} ^ {n} (n \ geq 2)}{\ displaystyle \ mathbb {R} ^ {n} (п \ geq 2)} обозначается rot {\ displaystyle \ operatorname {rot}}{\ displaystyle \ operatorname {rot}} и определяется как:

∀ x = (x 1,…, xn - 1, xn) ∈ R n: rot ⁡ (x 1,…, Xn - 1, xn) = (xn, x 1,…, xn - 1) {\ displaystyle \ forall {\ boldsymbol {x}} = (x_ {1}, \ ldots, x_ {n-1}, x_ {n}) \ in \ mathbb {R} ^ {n}: \ operatorname {rot} (x_ {1}, \ ldots, x_ {n-1}, x_ {n}) = (x_ {n}, x_ {1}, \ ldots, x_ {n-1})}{\ displaystyle \ forall {\ boldsymbol {x}} = (x_ {1}, \ ldots, x_ {n-1}, x_ {n}) \ in \ mathbb {R} ^ {n}: \ operatorname {rot} (x_ {1}, \ ldots, x_ {n-1}, x_ {n}) = (x_ {n}, x_ {1}, \ ldots, x_ {n- 1})}

Циклические решетки

Микчанчо ввел циклические решетки в своей работе, обобщая компактную задачу о ранце на произвольные кольца. Циклическая решетка - это решетка, которая замкнута относительно оператора вращательного сдвига. Формально циклические решетки определяются следующим образом:

Определение: Решетка L ⊆ Z n {\ displaystyle {\ mathfrak {L}} \ substeq \ mathbb {Z} ^ {n}}{\ displaystyle {\ mathfrak {L}} \ substeq \ mathbb {Z} ^ {n}} является циклическим, если ∀ x ∈ L: rot ⁡ (x) ∈ L {\ displaystyle \ forall {\ boldsymbol {x}} \ in {\ mathfrak {L}}: \ operatorname {rot} ( {\ boldsymbol {x}}) \ in {\ mathfrak {L}}}{ \ displaystyle \ forall {\ boldsymbol {x}} \ in {\ mathfrak {L}}: \ operatorname {rot} ({\ boldsymbol {x}}) \ in {\ mathfrak {L}}} .

Примеры:

  1. Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ displaystyle \ mathbb {Z} ^ {n}} сам по себе циклическая решетка.
  2. Решетки, соответствующие любому идеалу в кольце частных полиномов R = Z [x] / (xn - 1) {\ displaystyle R = \ mathbb {Z} [x] / (x ^ {n} -1)}{\ displaystyle R = \ mathbb {Z} [x] / (x ^ {n} -1)} являются циклическими:

рассмотрим кольцо частных полиномов R = Z [x] / (xn - 1) {\ displaystyle R = \ mathbb {Z} [x] / (x ^ {n} -1)}{\ displaystyle R = \ mathbb {Z} [x] / (x ^ {n} -1)} , и пусть p (x) {\ displaystyle p (x)}{\ displaystyle p (x)} будет некоторым полиномом от R {\ displaystyle R}R , т.е. p (x) = ∑ i = 0 n - 1 aixi {\ displaystyle p (x) = \ sum _ {i = 0} ^ {n -1} a_ {i} x ^ {i}}{\ displaystyle p (x) = \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i}} где ai ∈ Z {\ displaystyle a_ {i} \ in \ mathbb {Z}}{\ displaystyle a_ {i} \ in \ mathbb {Z}} для i = 0,…, n - 1 {\ displaystyle i = 0, \ ldots, n-1}{\ displaystyle i = 0, \ ldots, n-1} .

Определите коэффициент внедрения Z {\ displaystyle \ mathbb {Z}}\ Z -модульный изоморфизм ρ {\ displaystyle \ rho}\ rho как:

ρ: R → Z n ρ (x) = ∑ i = 0 n - 1 aixi ↦ ( a 0,…, an - 1) {\ displaystyle {\ begin {align} \ quad \ rho: R \ rightarrow \ mathbb {Z} ^ {n} \\ [4pt] \ rho (x) = \ sum _ { i = 0} ^ {n-1} a_ {i} x ^ {i} \ mapsto (a_ {0}, \ ldots, a_ {n-1}) \ end {align}}}{\ displaystyle {\ begin {выровнено} \ quad \ rho: R \ rightarrow \ mathbb {Z} ^ {n} \\ [4pt] \ rho (x) = \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ mapsto (a_ {0}, \ ldot s, a_ {n-1}) \ end {align}}}

Пусть I ⊂ R {\ displaystyle I \ subset R}{\ displaystyle I \ subset R} быть идеалом. Решетка, соответствующая идеалу I ⊂ R {\ displaystyle I \ subset R}{\ displaystyle I \ subset R} , обозначается LI {\ displaystyle {\ mathfrak {L}} _ {I}}{\ displaystyle { \ mathfrak {L}} _ {I}} , является подрешеткой Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ displaystyle \ mathbb {Z} ^ {n}} и определяется как

LI: = ρ (I) = {( a 0,…, an - 1) ∣ ∑ i = 0 n - 1 aixi ∈ I} ⊂ Z n. {\ Displaystyle {\ mathfrak {L}} _ {I}: = \ rho (I) = \ left \ {(a_ {0}, \ ldots, a_ {n-1}) \ mid \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ in I \ right \} \ subset \ mathbb {Z} ^ {n}.}{\ displaystyle {\ mathfrak {L}} _ {I}: = \ rho (I) = \ left \ {(a_ {0}, \ ldots, a_ {n-1) }) \ mid \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ in I \ right \} \ subset \ mathbb {Z} ^ {n}.}

Теорема :L ⊂ Z n {\ displaystyle {\ mathfrak {L}} \ subset \ mathbb {Z} ^ {n}}{\ displaystyle {\ mathfrak {L}} \ subset \ mathbb {Z} ^ {n}} является циклическим тогда и только тогда, когда L {\ displaystyle {\ mathfrak {L}} }{\ displaystyle {\ mathfrak {L}}} соответствует некоторому идеалу I {\ displaystyle I}I в кольце частных многочленов R = Z [x] / (xn - 1) {\ displaystyle R = \ mathbb {Z} [x] / (x ^ {n} -1)}{\ displaystyle R = \ mathbb {Z} [x] / (x ^ {n} -1)} .

proof:⇐) {\ displaystyle \ Leftarrow)}{\ displaystyle \ Leftarrow)} Мы имеем:

L = LI: = ρ (I) = {(a 0,…, an - 1) ∣ ∑ i = 0 n - 1 aixi ∈ I} {\ displaystyle {\ mathfrak {L}} = {\ mathfrak { L}} _ {I}: = \ rho (I) = \ left \ {(a_ {0}, \ ldots, a_ {n-1}) \ mid \ sum _ {i = 0} ^ {n-1 } a_ {i} x ^ {i} \ in I \ right \}}{\ Displaystyle {\ mathfrak {L}} = {\ mathfrak {L}} _ {I}: = \ rho (I) = \ left \ {(a_ {0}, \ ldots, a_ {n-1}) \ mid \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ in I \ right \}}

Пусть (a 0,…, an - 1) {\ displaystyle (a_ {0}, \ ldots, a_ {n -1})}{\ displaystyle (a_ {0}, \ ldots, a_ {n-1) })} быть произвольным элементом в L {\ displaystyle {\ mathfrak {L}}}{\ displaystyle {\ mathfrak {L}}} . Затем определите p (x) = ∑ i = 0 n - 1 aixi ∈ I {\ displaystyle p (x) = \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ { i} \ in I}{\ displaystyle p (x) = \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ in I} . Но поскольку I {\ displaystyle I}I является идеалом, мы имеем x p (x) ∈ I {\ displaystyle xp (x) \ in I}{\ displaystyle xp (x) \ in I} . Тогда ρ (x p (x)) ∈ L I {\ displaystyle \ rho (xp (x)) \ in {\ mathfrak {L}} _ {I}}{\ displaystyle \ rho (xp (x)) \ in {\ mathfrak {L} } _ {I}} . Но ρ (xp (x)) = rot ⁡ (a 0,…, an - 1) ∈ LI {\ displaystyle \ rho (xp (x)) = \ operatorname {rot} (a_ {0}, \ ldots, a_ {n-1}) \ in {\ mathfrak {L}} _ {I}}{\ displaystyle \ rho (xp (x)) = \ operatorname {rot} (a_ {0}, \ ldots, a_ {n-1}) \ in {\ mathfrak {L}} _ {I}} . Следовательно, L {\ displaystyle {\ mathfrak {L}}}{\ displaystyle {\ mathfrak {L}}} является циклическим.

⇒) {\ displaystyle \ Rightarrow)}{\ displaystyl е \ Rightarrow)}

Пусть L ⊂ Z n {\ displaystyle {\ mathfrak {L}} \ subset \ mathbb {Z} ^ {n}}{\ displaystyle {\ mathfrak {L}} \ subset \ mathbb {Z} ^ {n}} - циклическая решетка. Следовательно, ∀ (a 0,…, an - 1) ∈ L: rot ⁡ (a 0,…, an - 1) ∈ L {\ displaystyle \ forall (a_ {0}, \ ldots, a_ {n- 1}) \ in {\ mathfrak {L}}: \ operatorname {rot} (a_ {0}, \ ldots, a_ {n-1}) \ in {\ mathfrak {L}}}{\ displaystyle \ forall (a_ {0}, \ ldots, a_ {n-1}) \ in {\ mathfrak {L}}: \ operatorname {rot} (a_ {0}, \ ldots, a_ {n-1}) \ in {\ mathfrak {L}}} .

Определить набор многочленов I: = {∑ i = 0 n - 1 aixi ∣ (a 0,…, an - 1) ∈ L} {\ displaystyle I: = \ left \ {\ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ mid (a_ {0}, \ ldots, a_ {n-1}) \ in {\ mathfrak {L}} \ right \}}{\ displaystyle I: = \ left \ {\ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ mid (a_ {0}, \ ldots, a_ {n-1}) \ in {\ mathfrak {L}} \ right \}} :

  1. Поскольку L {\ displaystyle {\ mathfrak {L}}}{\ displaystyle {\ mathfrak {L}}} решетка и, следовательно, аддитивная подгруппа Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ displaystyle \ mathbb {Z} ^ {n}} , I ⊂ R {\ displaystyle I \ subset R}{\ displaystyle I \ subset R} является аддитивной подгруппой R {\ displaystyle R}R .
  2. начиная с L {\ displaystyle {\ mathfrak {L}}}{\ displaystyle {\ mathfrak {L}}} циклично, ∀ p (x) ∈ I: xp (x) ∈ I {\ displaystyle \ forall p (x) \ in I: xp (x) \ in I}{\ displaystyle \ forall p (x) \ in I: xp (x) \ in I} .

Следовательно, I ⊂ R {\ displaystyle I \ subset R}{\ displaystyle I \ subset R} является идеалом, и, следовательно, L = LI {\ displaystyle {\ mathfrak {L}} = {\ mathfrak { L}} _ {I}}{ \ Displaystyle {\ mathfrak {L}} = {\ mathfrak {L}} _ {I}} .

Идеальные решетки

Пусть f (x) ∈ Z [x] {\ displaystyle f (x) \ in \ mathbb {Z} [x]}{\ displaystyle f (x) \ in \ mathbb {Z} [x]} быть моническим полиномом степени n {\ displaystyle n}n . Для криптографических приложений f (x) {\ displaystyle f (x)}f (x) обычно выбирается несократимым. Идеал, порожденный f (x) {\ displaystyle f (x)}f (x) , равен:

(f (x)): = f (x) ⋅ Z [x] = {f (x) g (x): ∀ g (x) ∈ Z [x]}. {\ Displaystyle (е (х)): = е (х) \ cdot \ mathbb {Z} [x] = \ {f (x) g (x): \ forall g (x) \ in \ mathbb {Z} [x] \}.}{\ displaystyle (f (x)): = f (x) \ cdot \ mathbb {Z} [x] = \ {f (x) g (x): \ forall g (x) \ in \ mathbb {Z} [x] \}.}

Кольцо частных многочленов R = Z [x] / (f (x)) {\ displaystyle R = \ mathbb {Z} [x] / (f (x)) }{\ displaystyle R = \ mathbb {Z} [x] / ( е (х))} разбивает Z [x] {\ displaystyle \ mathbb {Z} [x]}{\ displaystyle \ mathbb {Z} [x]} на классы эквивалентности многочленов степени не выше n - 1 {\ displaystyle n-1}n-1 :

R = Z [x] / (f (x)) = {∑ i = 0 n - 1 aixi: ai ∈ Z} {\ displaystyle R = \ mathbb {Z} [x] / (f (x)) = \ left \ {\ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i}: a_ {i} \ in \ mathbb {Z} \ right \} }{\ displaystyle R = \ mathbb {Z} [x] / (f ( x)) = \ left \ {\ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i}: a_ {i} \ in \ mathbb {Z} \ right \}}

где сложение и умножение сокращаются по модулю f (x) {\ displaystyle f (x)}f (x) .

Рассмотрим коэффициент вложения Z {\ displaystyle \ mathbb {Z}}\ mathbb {Z} -модульный изоморфизм ρ {\ displaystyle \ rho}\ rho . Затем каждый идеал в R {\ displaystyle R}R определяет подрешетку Z n {\ displaystyle \ mathbb {Z} ^ {n}}\ mathbb {Z} ^ {n} с именем идеальная решетка.

Определение: LI {\ displaystyle {\ mathfrak {L}} _ {I}}{\ displaystyle { \ mathfrak {L}} _ {I}} , решетка, соответствующая идеалу I {\ displaystyle I}I , называется идеальной решеткой. Более точно, рассмотрим кольцо частных полиномов R = Z [x] / (p (x)) {\ displaystyle R = \ mathbb {Z} [x] / (p (x))}{\ displaystyle R = \ mathbb {Z} [x] / (p (x))} , где (p (x)) {\ displaystyle (p (x))}{\ displaystyle (p (x))} - идеал, порожденный степенью n {\ displaystyle n}n многочлен p (x) ∈ Z [x] {\ displaystyle p (x) \ in \ mathbb {Z} [x]}{\ displaystyle п (х) \ in \ mathbb {Z} [x]} . LI {\ displaystyle {\ mathfrak {L}} _ {I}}{\ displaystyle { \ mathfrak {L}} _ {I}} , является подрешеткой Z n {\ displaystyle \ mathbb {Z} ^ {n}}\ mathbb {Z} ^ {n} и определяется как:

LI: = ρ (I) = {(a 0,…, an - 1) ∣ ∑ i = 0 n - 1 aixi ∈ I} ⊂ Z n. {\ Displaystyle {\ mathfrak {L}} _ {I}: = \ rho (I) = \ left \ {(a_ {0}, \ ldots, a_ {n-1}) \ mid \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ in I \ right \} \ subset \ mathbb {Z} ^ {n}.}{\ displaystyle {\ mathfrak {L}} _ {I}: = \ rho (I) = \ left \ {(a_ {0}, \ ldots, a_ {n-1) }) \ mid \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ in I \ right \} \ subset \ mathbb {Z} ^ {n}.}

Примечание:

  1. Получается, что GapSVP γ {\ displaystyle {\ text {GapSVP}} _ {\ gamma}}{\ displaystyle {\ text {GapSVP}} _ {\ gamma}} даже для маленьких γ = poly (n) {\ displaystyle \ gamma = \ operatorname {poly (n)}}{\ displaystyle \ gamma = \ operatorname {poly (n)}} обычно прост на идеальных решетках. Интуиция заключается в том, что алгебраические симметрии приводят к тому, что минимальное расстояние от идеала находится в узком, легко вычисляемом диапазоне.
  2. Используя предоставленные алгебраические симметрии в идеальных решетках, можно преобразовать короткий ненулевой вектор в n {\ displaystyle n}n линейно независимые (почти) одинаковой длины. Следовательно, на идеальных решетках SVP γ {\ displaystyle \ mathrm {SVP} _ {\ gamma}}{\ displaystyle \ mathrm {SVP} _ {\ gamma}} и SIVP γ {\ displaystyle \ mathrm {SIVP} _ { \ gamma}}{\ displaystyle \ mathrm {SIVP} _ {\ gamma} } эквивалентны с небольшой потерей. Более того, даже для квантовых алгоритмов SVP γ {\ displaystyle \ mathrm {SVP} _ {\ gamma}}{\ displaystyle \ mathrm {SVP} _ {\ gamma}} и SIVP γ {\ displaystyle \ mathrm {SIVP} _ {\ gamma}}{\ displaystyle \ mathrm {SIVP} _ {\ gamma} } очень сложны в наихудшем сценарии.
Задача решения для коротких целых чисел

SIS и Ring-SIS - это две задачи среднего случая, которые используются в конструкциях криптографии на основе решеток. Криптография на основе решеток началась в 1996 году с основополагающей работы Айтаи, который представил семейство односторонних функций, основанных на проблеме SIS. Он показал, что это безопасно в среднем случае, если старший вице-президент γ {\ displaystyle \ mathrm {SVP} _ {\ gamma}}{\ displaystyle \ mathrm {SVP} _ {\ gamma}} (где γ = nc {\ displaystyle \ gamma = n ^ {c}}{\ displaystyle \ gamma = n ^ {c}} для некоторой константы c>0 {\ displaystyle c>0}c>0 ) в худшем случае сложно.

SIS n, m, q, β

Пусть A ∈ Z qn × m {\ displaystyle A \ in \ mathbb {Z} _ {q} ^ {n \ times m}}{\ displaystyle A \ in \ mathbb {Z} _ {q} ^ {n \ times m}} будет n × m {\ displaystyle n \ times m}п \ раз м матрица с элементами в Z q {\ displaystyle \ mathbb {Z} _ {q}}{\ displaystyle \ mathbb {Z} _ {q}} , состоящая из из m {\ displaystyle m}m равномерно случайных векторов ai ∈ Z qn {\ displaystyle {\ boldsymbol {a_ {i}}} \ in \ mathbb {Z} _ {q} ^ {n}}{\ displaystyle {\ boldsymbol { a_ {i}}} \ in \ mathbb {Z} _ {q} ^ {n}} : A = [a 1 | ⋯ | am] {\ displaystyle A = [{\ boldsymbol {a_ {1}}} | \ cdots | {\ boldsymbol {a_ {m}}}]}{\ displaystyle A = [{\ boldsymbol {a_ {1}}} | \ cdots | {\ boldsymbol {a_ {m}}}]} . Найдите ненулевой вектор x ∈ Z m {\ displaystyle {\ boldsymbol {x}} \ in \ m athbb {Z} ^ {m}}{\ displaystyle {\ boldsymbol {x}} \ in \ mathbb {Z} ^ {m}} такой, что:

  • ‖ x ‖ ≤ β {\ displaystyle \ | {\ boldsymbol {x}} \ | \ leq \ beta}{\ displaystyle \ | {\ boldsymbol {x}} \ | \ leq \ beta}
  • f A (Икс): = А Икс = 0 ∈ Z qn {\ Displaystyle f_ {A} ({\ boldsymbol {x}}): = А {\ boldsymbol {x}} = {\ boldsymbol {0}} \ in \ mathbb {Z} _ {q} ^ {n}}{\ displaystyle f_ {A} ({\ boldsymbol {x}}): = A {\ boldsymbol {x}} = {\ boldsymbol {0}} \ in \ mathbb {Z} _ {q} ^ {n}}

Решение SIS без необходимого ограничения на длину решения (‖ x ‖ ≤ β {\ displaystyle \ | {\ boldsymbol {x}} \ | \ leq \ beta}{\ displaystyle \ | {\ boldsymbol {x}} \ | \ leq \ beta} ) легко вычислить, используя метод исключения Гаусса. Нам также требуется β < q {\displaystyle \beta {\ displaystyle \ beta <q}, иначе x = (q, 0,…, 0) ∈ Z m {\ displaystyle {\ boldsymbol {x}} = (q, 0, \ ldots, 0) \ in \ mathbb {Z} ^ {m}}{ \ displaystyle {\ boldsymbol {x}} = (q, 0, \ ldots, 0) \ in \ mathbb {Z} ^ {m}} - тривиальное решение.

Чтобы гарантировать, что f A (x) {\ displaystyle f_ {A} ({\ boldsymbol {x}})}{\ displaystyle f_ {A} ({\ boldsymbol {x}})} имеет нетривиальное и короткое решение, мы требуется:

  • β ≥ n журнал ⁡ q {\ displaystyle \ beta \ geq {\ sqrt {n \ log q}}}{\ displaystyle \ beta \ geq {\ sqrt {n \ log q}}} и
  • m ≥ n журнал ⁡ q {\ displaystyle m \ geq n \ log q}{\ displaystyle m \ geq n \ log q}

Теорема: Для любого m = poly ⁡ (n) {\ displaystyle m = \ operatorname {poly} (n)}{\ displaystyle m = \ operatorname {poly} (n)} , любого β>0 {\ displaystyle \ beta>0}\beta>0 и любые достаточно большие q ≥ β nc {\ displaystyle q \ geq \ beta n ^ {c}}{\ displaystyle q \ geq \ beta n ^ {c}} (для любой константы c>0 {\ displaystyle c>0}{\displaystyle c>0} ), решение SIS n, m, q, β {\ displaystyle \ operatorname {SIS} _ {n, m, q, \ beta}}{\ displaystyle \ operatorname {SIS} _ {n, m, q, \ beta}} с немалая вероятность не менее так же сложно, как решить GapSVP γ {\ displaystyle \ operatorname {GapSVP} _ {\ gamma}}{\ displaystyle \ operatorname {GapSVP} _ {\ gamma}} и SIVP γ {\ displaystyle \ operatorname {SIVP} _ {\ gamma}}{\ displ aystyle \ operatorname {SIVP} _ {\ gamma}} для некоторых γ = β ⋅ O (n) {\ displaystyle \ gamma = \ beta \ cdot O ({\ sqrt {n}})}{\ displaystyle \ gamma = \ beta \ cdot O ({\ sqrt {n}})} с высокой вероятностью в худшем случае.

Ring-SIS

Проблема Ring-SIS, компактный аналог проблемы SIS на основе колец, изучалась в. Они рассматривают кольцо факторных полиномов R = Z [x] / ( е (х)) {\ displaystyle R = \ mathbb {Z} [x] / (f (x))}{\ displaystyle R = \ mathbb {Z} [x] / ( е (х))} с f (x) = xn - 1 {\ displaystyle f (x) = x ^ {n} -1}{\ displaystyle f (x) = x ^ {n} -1} и x 2 k + 1 {\ displaystyle x ^ {2 ^ {k}} + 1}{\ displaystyle x ^ {2 ^ {k}} + 1} соответственно, и расширить определение нормы векторов в R n {\ displaystyle \ mathbb {R} ^ {n}}\ mathbb {R} ^ {n} до векторов в R m {\ displaystyle R ^ {m}}R ^ m следующим образом:

Дан вектор z → = (p 1,…, pm) ∈ R m {\ displaystyle {\ vec {\ boldsymbol {z}}} = ( p_ {1}, \ ldots, p_ {m}) \ in R ^ {m}}{\ displaystyle {\ vec {\ boldsymbol { z}}} = (p_ {1}, \ ldots, p_ {m}) \ in R ^ {m}} где pi (x) {\ displaystyle p_ {i} (x)}p_ {i} (x) - это некоторый многочлен от R {\ displaystyle R}R . Рассмотрим коэффициент вложения Z {\ displaystyle \ mathbb {Z}}\ mathbb {Z} -модульный изоморфизм ρ {\ displaystyle \ rho}\ rho :

ρ: R → Z n ρ (x) = ∑ я знак равно 0 N - 1 aixi ↦ (a 0,…, an - 1) {\ displaystyle {\ begin {align} \ rho: R \ rightarrow \ mathbb {Z} ^ {n} \\ [3pt] \ rho (x) = \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ mapsto (a_ {0}, \ ldots, a_ {n-1}) \ end { выровнено}}}{\ displaystyle {\ begin {align} \ rho: R \ rightarrow \ mathbb { Z} ^ {n} \\ [3pt] \ rho (x) = \ sum _ {i = 0} ^ {n-1} a_ {i} x ^ {i} \ mapsto (a_ {0}, \ ldots, a_ {n-1}) \ end {align}}}

Пусть zi = ρ (pi (x)) ∈ Z n {\ displaystyle {\ boldsymbol {z_ {i}}} = \ rho (p_ {i} (x)) \ in Z ^ {n}}{\ displaystyle {\ boldsymbol {z_ {i}}} = \ rho (p_ {i} (x)) \ in Z ^ {n}} . Определите норму z → {\ displaystyle {\ vec {\ boldsymbol {z}}}}{\ displaystyle { \ vec {\ boldsymbol {z}}}} как:

‖ z → ‖: = ∑ i = 1 m ‖ zi ‖ 2 {\ displaystyle \ | {\ vec {\ boldsymbol {z}}} \ |: = {\ sqrt {\ sum _ {i = 1} ^ {m} \ | {\ boldsymbol {z_ {i}}} \ | ^ { 2}}}}{\ displaystyle \ | {\ vec {\ b oldsymbol {z}}} \ |: = {\ sqrt {\ sum _ {i = 1} ^ {m} \ | {\ boldsymbol {z_ {i}}} \ | ^ {2}}}}

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

σ: R = Z / (f (x)) → C np (x) ↦ (p (α 1),…, p (α n) {\ displaystyle {\ begin { выровнено} \ sigma: R = \ mathbb {Z} / (f (x)) \ rightarrow \ mathbb {C} ^ {n} \\ p (x) \ mapsto (p (\ alpha _ {1}), \ ldots, p (\ alpha _ {n}) \ end {align}}}{\ displaystyle {\ begin {align} \ sigma: R = \ mathbb {Z} / (f (x)) \ rightarrow \ mathbb {C } ^ {n} \\ p (x) \ mapsto (p (\ alpha _ {1}), \ ldots, p (\ alpha _ {n}) \ end {align}}}

где α i {\ displaystyle \ alpha _ {i}}\ alpha _ {i} - это ith {\ displaystyle i ^ {th}}i ^ {th} комплексный корень из f (x) {\ displaystyle f (x)}f (x) для i = 1,…, n {\ displaystyle i = 1, \ ldots, n}я = 1, \ ldots, n .

R-SISm,q,β

Учитывая кольцо частных многочленов R = Z [x] / (f (x)) {\ displaystyle R = \ mathbb {Z} [x] / (f (x))}{\ displaystyle R = \ mathbb {Z} [x] / ( е (х))} , определите

R q: = R / q R = Z q [x] / (f (x)) {\ displaystyle R_ {q}: = R / qR = \ mathbb {Z} _ {q} [x] / (f (x))}{\ displaystyle R_ {q}: = R / qR = \ mathbb {Z} _ {q} [x] / (f (x))} . Выберите m {\ displaystyle m}m независимых равномерно случайных элементов ai ∈ R q {\ displaystyle a_ {i} \ in R_ {q}}{\ displaystyle a_ {i} \ in R_ {q}} . Определите вектор a →: = (a 1,…, am) ∈ R qm {\ displaystyle {\ vec {\ boldsymbol {a}}}: = (a_ {1}, \ ldots, a_ {m}) \ in R_ {q} ^ {m}}{\ displaystyle {\ vec {\ boldsymbol {a}}}: = (a_ {1}, \ ldots, a_ {m}) \ in R_ {q} ^ {m}} . Найдите ненулевой вектор z →: = (p 1,…, pm) ∈ R m {\ displaystyle {\ vec {\ boldsymbol {z}}}: = (p_ {1}, \ ldots, p_ {m }) \ in R ^ {m}}{\ displaystyle {\ vec {\ boldsymbol {z}}}: = (p_ {1}, \ ldots, p_ {m}) \ in R ^ {m}} такой, что:

  • ‖ z → ‖ ≤ β {\ displaystyle \ | {\ vec {\ boldsymbol {z}}} \ | \ leq \ beta }{\ displaystyle \ | {\ vec {\ boldsymbol {z}}} \ | \ leq \ beta}
  • fa → (z →): = a → t. z → = ∑ я = 1 м а я. пи = 0 ∈ р q {\ displaystyle f _ {\ vec {\ boldsymbol {a}}} ({\ vec {\ boldsymbol {z}}}): = {\ vec {\ boldsymbol {a}}} ^ {\, t}. {\ vec {\ boldsymbol {z}}} = \ sum _ {i = 1} ^ {m} a_ {i}.p_ {i} = 0 \ in R_ {q}}{\ displaystyle f _ {\ vec {\ boldsymbol {a}}} ({\ vec {\ boldsymbol {z}}}) : = {\ vec {\ boldsymbol {a}}} ^ {\, t}. {\ vec {\ boldsymbol {z}}} = \ sum _ {i = 1} ^ {m} a_ {i}.p_ {i} = 0 \ in R_ {q}}

Напомнить что для гарантии существования решения проблемы SIS нам требуется m ≈ n log ⁡ q {\ displaystyle m \ приблизительно n \ log q}{\ displaystyle m \ приблизительно n \ log q} . Однако проблема Ring-SIS обеспечивает нам большую компактность и эффективность: чтобы гарантировать существование решения проблемы Ring-SIS, нам требуется m ≈ log ⁡ q {\ displaystyle m \ приблизительно \ log q}{\ displaystyle m \ приблизительно \ log q} .

Определение : Отрицательная матрица b {\ displaystyle b}bопределяется как:

для b = ∑ i = 0 n - 1 bixi ∈ R, rot ⁡ (b): = [b 0 - bn - 1… - b 1 b 1 b 0… - b 2 ⋮ ⋮ ⋱ ⋮ bn - 1 bn - 2… b 0] {\ displaystyle {\ text {for}} \ quad b = \ sum _ {i = 0} ^ {n-1} b_ {i} x ^ {i} \ in R, \ quad \ operatorname {rot} (b): = {\ begin {bmatrix} b_ {0} -b_ {n-1} \ ldots -b_ {1} \\ [0.3em] b_ {1} b_ {0} \ ldots -b_ {2} \\ [0.3em] \ vdots \ vdots \ ddots \ vdots \\ [0.3em] b_ {n-1} b_ {n-2} \ ldots b_ {0} \ end {bmatrix}}}{\ displaystyle {\ text {для }} \ quad b = \ sum _ {i = 0} ^ {n-1} b_ {i} x ^ {i} \ in R, \ quad \ operatorname {rot} (b): = {\ begin {bmatrix } b_ {0} - b_ {n-1} \ ldots -b_ {1} \\ [0.3em] b_ {1} b_ {0} \ ldots -b_ {2} \\ [0.3em ] \ vdots \ vdots \ ddots \ vdots \\ [0.3em] b_ {n-1} b_ {n-2} \ ldots b_ {0} \ end {bmatrix}}}

Когда частное кольцо многочленов равно R = Z / (xn + 1) {\ displaystyle R = \ mathbb {Z} / (x ^ {n} +1)}{\ displaystyle R = \ mathbb {Z} / (x ^ {n} +1)} для n = 2 k {\ displaystyle n = 2 ^ {k}}n = 2 ^ k , кольцевое умножение ai. pi {\ displaystyle a_ {i}.p_ {i}}{\ displaystyle a_ {i}.p_ {i}} можно эффективно вычислить, сначала сформировав rot ⁡ (ai) {\ displaystyle \ operatorname {rot} (a_ {i})}{\ displaystyle \ operatorname {rot} (a_ {i})} , отрицательно-циркулянтная матрица ai {\ displaystyle a_ {i}}a_ {i} , а затем умножение rot ⁡ (ai) {\ displaystyle \ operatorname {rot } (a_ {i})}{\ displaystyle \ operatorname {rot} (a_ {i})} с ρ (pi (x)) ∈ Z n {\ displaystyle \ rho (p_ {i} (x)) \ in Z ^ {n}}{\ displaystyle \ rho (p_ {i} (x)) \ in Z ^ {n}} , вектор коэффициентов вложения pi {\ displaystyle p_ {i}}p_ {i} (или, альтернативно, с σ (pi (x)) ∈ Z n {\ displaystyle \ sigma (p_ {i} (x)) \ in Z ^ {n}}{\ displaystyle \ sigma (p_ {i} ( x)) \ in Z ^ {n}} , вектор канонических коэффициентов).

Более того, проблема R-SIS - это частный случай проблемы SIS, где матрица A {\ displaystyle A}A в задаче SIS ограничена негабаритными блоками: A = [rot ⁡ (a 1) | ⋯ | rot ⁡ (am)] {\ displaystyle A = [\ operatorname {rot} (a_ {1}) | \ cdots | \ operatorname {rot} (a_ {m})]}{\ displaystyle A = [\ operatorname {rot} (a_ {1}) | \ cdots | \ operatorname {rot} (a_ {m})]} .

См. также
Ссылки
  1. ^ Ajtai, Miklós. [Создание сложных экземпляров задач решетки.] Труды двадцать восьмого ежегодного симпозиума ACM по теории вычислений. ACM, 1996.
  2. ^ Micciancio, Daniele. [Обобщенные компактные рюкзаки, циклические решетки и эффективные односторонние функции из предположений о сложности наихудшего случая.] Основы компьютерных наук, 2002. Труды. 43-й ежегодный симпозиум IEEE по. IEEE, 2002.
  3. ^Фукшанский, Ленни и Сюнь Сунь. [О геометрии циклических решеток.] Дискретная и вычислительная геометрия 52.2 (2014): 240–259.
  4. ^Крейг Джентри. Полностью гомоморфное шифрование с использованием идеальных решеток. На 41-м симпозиуме ACM по теории вычислений (STOC), 2009 г.
  5. ^http://web.cse.ohio-state.edu/~lai/5359-aut13/05.Gentry-FHE-concrete-scheme.pdf
  6. ^Пайкерт, Крис. [Десятилетие решетчатой ​​криптографии.] Cryptology ePrint Archive, Report 2015/939, 2015.
  7. ^Пайкерт, Крис и Алон Розен. [Эффективное устойчивое к коллизиям хеширование из наихудших предположений о циклических решетках.] Теория криптографии. Springer Berlin Heidelberg, 2006. 145–166.
  8. ^Любашевский, Вадим и др. [SWIFFT: скромное предложение по хешированию FFT.] Быстрое программное шифрование. Springer Berlin Heidelberg, 2008.
  9. ^Ланглуа, Аделина и Дэмьен Стеле. [Редукции от худшего случая к среднему для решеток модулей.] Проекты, коды и криптография 75.3 (2015): 565–599.

Последняя правка сделана 2021-06-08 06:42:30
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте