오류가 있는 링 학습

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2015년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

퀀텀 후 암호학에서 오류가 있는 링러닝(RLWE)은 양자컴퓨터에 의한 암호해석으로부터 보호하고 동형 암호화의 기초를 제공하기 위해 고안된 뉴호프(NewHope)와 같은 새로운 암호 알고리즘의 근간 역할을 하는 연산 문제다.공개키 암호화는 추가 정보가 없으면 풀기 어렵다고 판단되는 수학 문제 구축에 의존하지만 문제 구축에 사용된 일부 정보가 알려지면 풀기 쉽다.현재 암호화에 사용되고 있는 이런 종류의 몇몇 문제들은 만약 충분히 큰 양자 컴퓨터가 만들어질 수 있다면 공격의 위험에 처하기 때문에 저항적인 문제들이 추구된다.동형 암호화는 암호화된 데이터베이스에 저장된 숫자 값의 산술과 같이 암호문 상에서 연산할 수 있는 암호화의 한 형태다.

RLWE는 링 위에 오류가 있는 학습이라고 더 적절하게 불리며, 단순히 유한한 분야에 걸쳐 다항식 링에 특화된 오류(LWE) 문제가 있는 더 큰 학습이다.^[1]양자 컴퓨터에서도 RLWE 문제를 해결하는 것이 어려울 것으로 추정되기 때문에, 1980년대 초부터 정수 인수화와 이산 로그 문제가 공개키 암호화의 기반으로서 작용해 왔듯이, RLWE 기반 암호화는 향후 공개키 암호화의 근본적인 기반을 형성할 수 있을 것이다.^[2]오류 문제가 있는 링 학습을 기반으로 암호화를 하는 중요한 특징은 RLWE 문제에 대한 해결책을 격자(SVP 문제에서 RLWE 문제로 다항 시간 단축이 제시됨^[1])에서 NP-하드 최단 벡터 문제(SVP 문제에서 RLWE 문제로의 다항 시간 단축이 제시됨)를 해결할 수 있다는 점이다.

배경

현대 암호학의 보안, 특히 공개키 암호학의 보안은 문제의 크기가 충분히 크고 해결할 문제의 예를 무작위로 선택하는 경우 특정 계산 문제를 해결하는 가정된 난해성에 기초한다.1970년대 이후 사용된 대표적인 예가 정수인자화 문제다.만약 그러한 소수들이 충분히 크고 무작위로 선택된다면, 두 소수들의 산출물을 계산적으로 다루기 어렵다고 여겨진다.^[3]2015년 현재 연구 결과 384비트 프리타임 2개 제품이지만 512비트 프리타임 2개 제품은 해당되지 않는 것으로 나타났다.정수 인자화는 널리 사용되는 RSA 암호 알고리즘의 기초를 형성한다.

오류가 있는 링 학습(RLWE) 문제는 유한한 분야의 계수를 갖는 다항식 산술에 기초한다.^[1]$\mathrm{일반적}$인 다항식 $a$( x$$) ${\textstyle a(x)}$은(는) 다음과 같이 표현된다.

${\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}x^{2}+\ldots +a_{n-2}x^{n-2}x^{n-2}+a_{n-1}x^{n-1}$

다항식들은 일반적인 방법으로 첨가되고 증식될 수 있다.In the RLWE context the coefficients of the polynomials and all operations involving those coefficients will be done in a finite field, typically the field ${\textstyle \mathbf {Z} /q\mathbf {Z} =\mathbf {F} _{q}}$ for a prime integer ${\textstyle q}$. The set of polynomials over a finite field with the op덧셈과 곱셈의 어법은 무한 다항식 링(${}_{}$[ $x$ $]$ ${\textstyle \mathbf {F} _{q}[x]})$을 형성한다.$$RLWE 컨텍스트는 이 무한반지의 유한 지수 링과 함께 작동한다.The quotient ring is typically the finite quotient (factor) ring formed by reducing all of the polynomials in ${\textstyle \mathbf {F} _{q}[x]}$ modulo an irreducible polynomial ${\textstyle \Phi (x)}$. This finite quotient ring can be written as ${\displaystyle \mathbf {F} _{q$$}[x]/\Phi (x)}$ 많은$$ 저자가 $Z{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$[ ${\displaystyle x}$ ${\displaystyle ]}$/ ${\displaystyle \phi \mathrm{}}$( ${\displaystyle x}$) ${\displaystyle \mathbf {Z} _{q}[x]/\Phi (x)}$ $$^[1].

다항식 $\phi {\displaystyle \mathrm{}(x}$) ${\displaystyle \Phi(x)}$의 정도가 $n$ ${\textstyle n}$인 경우$,$ 지수 링은 $F{\displaystyle {}_{}}$ ${\displaystyle q_{}}$ ${\$$q}$의 계수를 갖는$$ n ${\$$displaysty$ n$}$$모듈$로 o$$$(x)$보다 작은 다항식의 링이 된다.다항식 $\phi {\displaystyle \mathrm{}(x}$) ${\displaystyle \Phi(x)}$과$($$와$) $n$ ${\textstyle q}$ 값은 RLWE 문제에 대한 수학적 컨텍스트를 부분적으로$$ 정의한다.

RLWE 문제에 필요한 또 다른 개념은 어떤 규범에 관한 "작은" 다항식 개념이다.RLWE 문제에 사용되는 대표적인 규범을 무한규범(일률규범이라고도 한다)이라고 한다.다항식의 무한정 규범은 단순히 이러한 계수를 정수로 볼 때 다항식의 가장 큰 계수다.${\displaystyle \mathrm{따라서}}$ ${\displaystyle a}$( x${\displaystyle }$) ${\displaystyle \infty {}_{\mathrm{}}}$= b ${\displaystyle a($${\displaystyle x}$$) _{\infit }=b}$에 다항식 $a{\displaystyle }$( x${\displaystyle }$) ${\displaystyle a(x)}$의 무한정 규범이 b ${\displaystyle b}$을 명시한다$.$따라서 $b{\displaystyle }$ ${\displaystyle b}$은 $a{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle a(x$의 가장 큰 계수다.

The final concept necessary to understand the RLWE problem is the generation of random polynomials in ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$ and the generation of "small" polynomials . A random polynomial is easily generated by simply randomly sampling the ${\displaystyle n}$ coefficients of the polynomial from ${\displaystyle \mathbf {F} _{q}}$, where ${\displaystyle \mathbf {F} _{q}}$ is typically represented as the set ${\displaystyle \{-(q-1)/2,...,-1,0,1,...,(q-1)/2\}}$.

$임의$로 "작은" 다항식을 생성하는 것은 F ${\displaystyle {}_{}}$ ${\$에서 다항식의 계수를 생성하여 매우$$ 작은 계수를 보장하거나 만드는 방식으로 이루어진다.$q{\displaystyle }$ ${\displaystyle q}$이(가) 기본 정수인 경우 이를 수행하는 두 가지 일반적인 방법이 있다.

1. 균일 표본 추출 사용 – 작은 다항식의 계수는 작은 계수 집합에서 균일하게 표본 추출된다.Let ${\textstyle b}$ be an integer that is much less than ${\textstyle q}$. If we randomly choose coefficients from the set: ${\textstyle \{-b,-b+1,-b+2,\ldots ,-2,-1,0,1,2,\ldots ,b-2,b-1,b\}}$ the polynomial will be small with respect to the bound ($$ $[\textstyle b}$ $$)
2. Using discrete Gaussian sampling – For an odd value for ${\textstyle q}$, the coefficients of the polynomial are randomly chosen by sampling from the set ${\textstyle \{-(q-1)/2,\ldots ,(q-1)/2\}}$ according to a discrete Gaussian distribution with mean ${\displaystyle 0}$ and distri부티온 매개 변수 $\sigma$ ${\textstyle \sigma$ $\}.$ 참조는 이 작업을 수행할 수 있는 방법을 자세히 설명한다.그것은 균일한 샘플링보다 더 복잡하지만 알고리즘의 보안성을 증명할 수 있다.드워마카나스와 갈브레이스의 논문 "제약된 장치에 대한 Lattice 기반 암호화를 위한 이산 가우시안으로부터의 샘플링"은 이 문제에 대한 개요를 제공한다.^[4]

RLWE 문제

RLWE 문제는 "검색" 버전과 "결정" 버전의 두 가지 다른 방식으로 진술될 수 있다.둘 다 같은 공사로 시작한다.내버려두다

• ${\displaystyle a_{}}$ (${\displaystyle {}_{}x}$) ${\$$displaystyle$ $a_{$${\displaystyle i}$$}(x)}$은(는) $F{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ [ ${\displaystyle {}_{}}$ ${\displaystyle ]}$/ ${\displaystyle \phi }$( x${\displaystyle }$) ${\displaystyle$ $\mathbf$${F$$} _{q}[$x]/\$Phi (x)$의 랜덤하지만 알려진 다항식의 집합이다$.$
• ${\displaystyle e_{}}$ ${\displaystyle i_{}}$( ${\displaystyle x}$) ${\displaystyle e_{i}(x)}$은(는) $링{\displaystyle {\mathbf{}}_{}}$ F ${\displaystyle {}_{}}$[ ${\displaystyle x]}$ / ${\displaystyle (}$ (${\displaystyle x}$ )$${\$displaystyle \mathbf {F} _{q}[x]/\Phi (x$의 $바인딩{\displaystyle }$ b$${\$displaystystyledata.$
• ${\displaystyle s}$( ${\displaystyle x}$) ${\displaystyle s(x)}$은(는) 링 $F{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$[ ${\displaystyle x}$]${\displaystyle }$/ ${\displaystyle \phi \mathrm{}}$(${\displaystyle x}$ ) ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x$의 $바인딩{\displaystyle }$ b ${\displaystystyle b}$에 대한 작은 알 수 없는 다항식이다.
• ${\displaystyle b_{}}$ ${\displaystyle i_{}}$( ${\displaystyle x}$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle a}$ (${\displaystyle {}_{}x}$)${\displaystyle }$⋅ ${\displaystyle s}$( x${\displaystyle }$)${\displaystyle }$+ ${\displaystyle e{}_{}}$( ${\displaystyle {}_{}}$ )${\displaystyle b_{i}(x)=(a_{i}(x)\cdot$ s$(x)+e_{i}(x$

Search 버전에는 다항식 쌍 목록$({\displaystyle i}$ ${\displaystyle {}_{}}$ x${\displaystyle }$)$${\$displaystyle$${\displaystyle }$$s(x$${\displaystyle )\}}$이(가) 주어진$$ 알 수 없는 $다항식{\displaystyle }$ s${\displaystyle }$( x ) ${\displaystyle (a_{i})(x), b_{i}(x$ .

문제의 결정 버전은 다음과 같이 명시될 수 있다.Given a list of polynomial pairs ${\displaystyle (a_{i}(x),b_{i}(x))}$, determine whether the ${\displaystyle b_{i}(x)}$ polynomials were constructed as ${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$ or were gene$F{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ [${\displaystyle {}_{}x}$ ${\displaystyle ]}$ /${\displaystyle \phi \mathrm{}}$ ${\displaystyle (x}$) ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$에서 임의로 F q ${\$의 계수를 갖는$$ 정격.

이 문제의 난이도는 지수 다항식( ${\displaystyle \phi }$( x${\displaystyle }$) ${\displaystyle \Phi (x)})$의 선택,$$ 그 정도(${\displaystyle }$ ${\\displaystyle$n}),$$ 필드(${\displaystyle {}_{}}$ $\$ $$및 소항(${\displaystyle }$ ${\displaystytytytytype b})$의 선택에 의해 매개변수가 지정된다.$$많은 RLWE 기반 공개 키 알고리즘에서 개인 키는 작은 $다항식{\displaystyle }$ s (${\displaystyle x}$) ${\displaystyle$ s$(x)}$ $및{\displaystyle }$ e$$${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle e(x)}$ 쌍이 될 것이다$.$The corresponding public key will be a pair of polynomials ${\displaystyle a(x)}$, selected randomly from ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$, and the polynomial ${\displaystyle t(x)=(a(x)\cdot s(x))+e(x)}$. Given ${\displaysty$$a(x)}$ 및 t${\displaystyle (\mathrm{x<img\; alt="a(x)"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/5d685172ca5d7f10d1e9dfd16cffc5a54bf1301a"\; style="vertical-align:\; -0.838ex;\; width:4.369ex;\; height:2.843ex;"\; papago-attr-id="204">}}$) ${\displaystyle t(x$ 다항식 s$($ ) $displaystyle s(x)}$을(를) 복구하는 것은 계산상 불가능해야 한다$.$

보안 감소

In cases where the polynomial ${\displaystyle \Phi (x)}$ is a cyclotomic polynomial, the difficulty of solving the search version of RLWE problem is equivalent to finding a short vector (but not necessarily the shortest vector) in an ideal lattice formed from elements of ${\displaystyle \mathbf {Z} [x]/\Phi$$(x)}$은(는) 정수 벡터로 표시됨$$.^[1]이 문제는 일반적으로 근사 최단 벡터 문제(α-SVP)로 알려져 있으며, 최단 벡터의 α배보다 짧은 벡터를 찾는 문제다.이 동등성에 대한 증명의 작성자는 다음과 같이 쓴다.

"... we give a quantum reduction from approximate SVP (in the worst case) on ideal lattices in ${\displaystyle \mathbf {R} }$ to the search version of ring-LWE, where the goal is to recover the secret ${\displaystyle s\in \mathbf {R} _{q}}$ (with high probability, for any ${\displaystyle s}$) from arbitrarily m시끄러운 제품이라면 어디든지."^[1]

In that quote, The ring ${\displaystyle \mathbf {R} }$ is ${\displaystyle \mathbf {Z} [x]/\Phi (x)}$ and the ring ${\displaystyle \mathbf {R} _{q}}$ is ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$.

일반 격자 내 α-SVP는 오류 문제가 있는 일반 학습의 감소에 필요한 α 값은 아니지만, 2001년 Daniele Micciancio의 작업으로 인해 NP-hard인 것으로 알려져 있다.^[5]그러나 이상적인 격자에 대한 α-SVP의 난이도가 평균 α-SVP와 동등하다는 것을 보여주는 증거는 아직 없다.오히려 이상적인 격자에서 해결하기 어려운 α-SVP 인스턴스가 있다면 RLWE 문제는 무작위적으로 어려워질 것이라는 증거를 가지고 있다.^[1]

마이클 슈나이더 연구원은 이상 래티스의 최단 벡터 문제 난이도에 대해 "현재까지 이상 래티스의 특수 구조를 이용하는 SVP 알고리즘은 없다"고 쓰고 있다. 이상적인 격자(및 다른 모든 격자 문제)에서 SVP(및 모든 격자 문제)를 해결하는 것이 일반 격자처럼 어렵다는 것이 널리 알려져 있다."^[6]정기적인 격납고에서 이러한 문제들의 어려움은 분명히 NP-hard이다.^[5]그러나 이상적인 격자가 일반 격자와 동일한 보안 속성을 공유한다고 믿지 않는 소수의 연구자가 있다.^[7]

Peikert는 이러한 보안 동등성 때문에 RLWE 문제가 향후 암호화를 위한 좋은 근거가 될 것이라고 믿는다.그는 다음과 같이 쓰고 있다: "임의의 경우에서 (일부 형식 공격 모델 내에서) 암호 시스템을 깨는 유일한 방법은 최악의 경우 근본적인 격자 문제를 해결할 수 있는 것이라는 수학적 증거가 있다."(원문에서는 강조).^[8]

RLWE 암호학

RLWE 기반 암호화가 오류(LWE) 기반 암호학보다 원본 학습에 비해 갖는 주요 이점은 공용 및 개인 키 크기에서 찾을 수 있다.RLWE 키는 대략 LWE에서 키의 제곱근이다.^[1]128비트 보안의 경우 RLWE 암호 알고리즘은 약 7000비트 길이의 공용 키를 사용할 것이다.^[9]해당 LWE 체계는 동일한 수준의 보안을 위해 4900만 비트의 공개 키가 필요할 것이다.^{[1][failed verification]}반면 RLWE 키는 RSA, Elliic Curve Diffie-Hellman과 같이 현재 사용되고 있는 공개키 알고리즘의 키 크기보다 크며, 공개키 크기는 각각 3072비트, 256비트여야 128비트 수준의 보안을 달성할 수 있다.그러나 계산적 관점에서 볼 때 RLWE 알고리즘은 기존의 공개 키 시스템과 동일하거나 더 나은 것으로 나타났다.^[10]

RLWE 암호 알고리즘의 세 가지 그룹이 존재한다.

오류 발생 시 링 학습(RLWE-KEX)

키 교환에 LWE와 링 LWE를 이용하자는 근본적인 발상이 진타이딩에 의해 2011년 신시내티 대학에 제안되어 접수되었다.기본적인 아이디어는 매트릭스 승수의 연관성에서 나왔고, 오류는 보안을 제공하기 위해 사용된다.논문은^[11] 2012년 잠정 특허출원이 접수된 뒤 2012년 나왔다.

2014년 파이커트는^[12] 딩스(Ding's)와 같은 기본 아이디어에 따라 핵심 교통수단을 제시했는데, 딩스(Ding) 건설에서 라운딩을 위해 1비트 신호를 추가로 보내는 새로운 아이디어도 활용된다.Diffie-Hellman 키 교환의 고전적인 MQV 변종의 RLWE 버전은 장 외 연구진에 의해 나중에 출판되었다.^[13]두 핵심 교환기의 보안은 이상적인 격자에서 대략적인 짧은 벡터를 찾는 문제와 직접적으로 관련이 있다.

오류 서명이 있는 링 학습(RLWE-SIG)

고전적인 Feige-Fiat-Shamir Identification 프로토콜의 RLWE 버전은 류바셰프스키에 의해 2011년에 디지털 서명으로 만들어졌다.^[14]이 서명의 세부사항은 2012년 구네슈, 류바셰프스키, 포플만에 의해 확장되었으며, 논문 "실용 격자 기반 암호 체계 - 임베디드 시스템을 위한 서명 체계"^[15]에 발표되었다.이 논문들은 오류 문제가 있는 링 학습과 동일한 하드 RLWE 문제와 연관되지 않은 몇몇에 직접적으로 기반을 둔 최근의 다양한 시그니처 알고리즘을 위한 토대를 마련했다.^[16]

오류가 있는 링 학습(RLWE-HOM)

동형 암호화의 목적은 중요한 데이터에 대한 연산이 데이터에 대해 신뢰되어서는 안 되는 컴퓨팅 장치에서 이루어지도록 하는 것이다.이 컴퓨터 장치들은 동형 암호화에서 출력되는 암호문을 처리할 수 있다.2011년, Brakersky와 Vaikuntanathan은 RLWE 문제에 직접 동형 암호화 체계를 구축하는 "링-LWE로부터의 완전 동형 암호화 및 키 종속 메시지 보안"을 출판했다.^[17]

참조