오류가 있는 링 러닝 키 교환

암호학에서 공개키 교환 알고리즘은 두 당사자가 서로 메시지를 암호화하는 데 사용할 수 있는 개인 키를 만들고 공유할 수 있는 암호화 알고리즘입니다.Ring Learning with Errors Key Exchange(RLWE-KEX; 오류 키 교환)는 퀀텀컴퓨터를 소유하고 있는 상대로부터 보호되도록 설계된 새로운 공개 키 교환 알고리즘의 1개입니다.현재 사용되고 있는 공개키 알고리즘 중 일부는 양자컴퓨터가 구현하면 쉽게 깨질 수 있기 때문에 이것은 중요합니다.RLWE-KEX는 격자와 관련된 특정 수학 문제를 해결하는 난이도에 기반을 둔 사후 양자 암호화 알고리즘의 집합 중 하나이다.이전의 격자 기반 암호화 알고리즘과는 달리, RLWE-KEX는 입증 가능한 방법으로 격자의 알려진 하드 문제로 환원할 수 있습니다.

배경

1980년대부터 인터넷을 통한 암호화 키 교환과 디지털 서명의 보안은 주로 소수의 공개 키 알고리즘에 기초하고 있습니다.이러한 알고리즘의 보안은 고전적인 컴퓨팅에서 마찬가지로 적은 수의 계산상 어려운 문제에 기초하고 있습니다.이러한 문제는 신중하게 선택된 두 소수의 곱을 인수분해하는 어려움, 신중하게 선택된 유한 필드에서의 이산 로그 계산의 어려움, 그리고 신중하게 선택된 타원 곡선 그룹에서의 이산 로그 계산의 어려움이다.이러한 문제들은 고전적인 컴퓨터(세계가 1940년대부터 오늘날까지 알고 있는 유형의 컴퓨터)로는 해결하기가 매우 어렵지만, 5에서 1만 비트의 메모리만 사용하는 비교적 작은 양자 컴퓨터로는 오히려 쉽게 해결할 수 있습니다.컴퓨터 업계에서는 2030년경 더 큰 규모의 양자컴퓨터가 출시될 것이라는 낙관론이 있다.만약 충분한 크기의 양자 컴퓨터가 만들어지면, 이 세 가지 고전적인 문제에 기초한 모든 공개 키 알고리즘은 안전하지 않을 것이다.이 공개 키 암호는 오늘날 인터넷 웹 사이트를 보호하고, 컴퓨터 로그인 정보를 보호하며, 컴퓨터가 악의적인 소프트웨어를 허용하지 않도록 하기 위해 사용됩니다.

양자 컴퓨터의 공격을 받지 않는 암호화를 양자 안전 또는 사후 양자 암호화라고 합니다.양자 저항성 암호화 알고리즘의 한 클래스는 ^[1]Oded Regev가 2005년에 도입한 "오류를 수반하는 학습"이라는 개념을 기반으로 합니다.오류가 있는 특수 형태의 학습은 유한 필드에 걸쳐 다항식의 링 내에서 작동합니다.이 전문화된 형식을 오류 포함 링 러닝 또는 RLWE라고 합니다.

RLWE 패러다임을 사용하여 작동하는 다양한 암호화 알고리즘이 있습니다.이 기사에 제시된 공개키, 키 교환 알고리즘 외에 공개키 암호화 알고리즘, 동형 암호화 알고리즘 및 RLWE 디지털 서명 알고리즘이 있습니다.

키 교환 알고리즘은, 통신 링크상의 2개의 통신사간에 공유 비밀 키를 확립하는 공개 키 알고리즘의 일종입니다.키 교환의 전형적인 예는 Diffie-입니다.Hellman 키 교환.교환은 회선의 한쪽 끝으로부터의 송신과 링크의 다른 쪽 끝으로부터의 송신으로 구성됩니다.디피Hellman과 타원 곡선 디피 -Hellman은 가장 인기 있는 키 교환 알고리즘입니다.

RLWE 키 교환은 널리 사용되는 Diffie를 "양자 안전" 대체하도록 설계되었다.헬만 및 타원 곡선 Diffie-신뢰할 수 없는 통신 채널 상의 비밀 키 확립을 보호하기 위해 사용되는 Hellman 키 교환.Diffie처럼-Hellman과 타원 곡선 디피 -Hellman, Ring-LWE 키 교환은 "전송 비밀"이라고 불리는 암호화 속성을 제공합니다.그 목적은 대량 보안 감시 프로그램의 효과를 줄이고 대량 복호화를 가능하게 하는 장기 비밀 키가 손상되지 않도록 하는 것입니다.

서론

소수 q부터 시작하여 Ring-LWE 키 교환은 정수 mod q $R_{q}:=Z_{q}[x]/\Phi (x)$ , $R_{q}:=Z_{q}[x]/\Phi (x)$ : $=$ Z Q [ $R_{q}:=Z_{q}[x]/\Phi (x)$ x $R_{q}:=Z_{q}[x]/\Phi (x)$ / $R_{q}:=Z_{q}[x]/\Phi (x)$ $=$ { { $display style R_Q})$ 의 $계수$ 를 $\Phi (x)$ 가진 다항식 $x$ )의 링에서 작동합니다. {displaystyle \Phi $(x)}$ 에서 작동합니다.다항식의 곱셈과 덧셈은 일반적인 방식으로 작동하며, mod $\Phi (x)$ ( $\Phi (x)$ ) { $display$ style \ $Phi (x$ 의 곱셈 결과를 나타냅니다.

키 교환에 LWE와 Ring LWE를 사용하는 아이디어는 2011년 Jintai Ding에 의해 신시내티 대학에서 처음 제안되어 제출되었습니다.이 아이디어는 행렬 곱셈의 연관성에서 비롯되며, 오차는 보안을 제공하기 위해 사용됩니다.이^[2] 논문은 2012년 가특허 출원 이후 2012년 등장했다.프로토콜의 보안은 LWE 문제 해결의 경도에 기반하여 증명됩니다.

2014년 Peikert는 딩의 기본 아이디어를 따라 키 전송^[3] 방식을 제시했으며, 딩의 구축에서 반올림을 위해 추가 1비트 신호를 보내는 새로운 아이디어도 사용되었습니다.

구글의 양자화 후 ^[5]실험을 위해 선택된 "새로운 희망" 구현은^[4] 오차 분포에 변화가 있는 Peikert의 방식을 사용한다.

128비트 이상의 보안을 위해 Singh는 Peikert의 ^[6]스킴에 대해 6956비트 공개키를 가진 일련의 파라미터를 제시합니다.대응하는 개인 키는 약 14,000비트입니다.Diffie의 고전적인 MQV 바리안트의 RLWE 버전 -Hellman 키 교환은 이후 Zhang 등에 의해 2014년에 발행되었다.두 키 교환의 보안은 이상적인 격자에서 대략적인 짧은 벡터를 찾는 문제와 직접적으로 관련이 있다.이 문서는 "오류 문제에 근거한 간단한 입증 가능한 안전한 키 교환 체계"^[2]에 있는 Ding의 RLWE 작업을 밀접하게 따릅니다.이 프레젠테이션에서 일반적인 다항식은 다음과 같이 표현된다.

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

이 다항식의 계수 as는_i 정수 mod q입니다.다항식 $\Phi (x)$ ( $\Phi (x)$ ) { $displaystyle \Phi (x)}$ 는 $\Phi (x)$ 사이클로토믹 다항식이 됩니다.n이 2의 거듭제곱일 경우 $\Phi (x)=x^{n}+1.$ $\Phi (x)=x^{n}+1.$ $=$ $\Phi (x)=x^{n}+1.$ + $\Phi (x)=x^{n}+1.$ . $\Phi (x)=x^{n}+1.$ \ $displaystyle \Phi(x$ )= $x^{n}+1입니다.$ $}$ ^[6]^[7]

RLWE-KEX는 "무한 노름"이라고 불리는 척도에 대해 "작은" 것으로 간주되는 다항식을 사용한다.다항식의 무한 노름은 계수가 $($ 즉, 집합 {-(q - 1)/2, ..., (q - 1)/2})가 $아닌$ Z(\ $displaystyle Zq)$ 의 정수로 간주될 때 다항식의 가장 큰 계수의 값입니다.알고리즘의 보안은 무한 노름에 대해 작은 랜덤 다항식을 생성할 수 있는 능력에 따라 달라집니다.이는 보장되거나 작을 가능성이 매우 높은 다항식(s_n-1, ..., s₀)에 대한 계수를 랜덤하게 생성함으로써 수행됩니다.여기에는 다음 두 가지 일반적인 방법이 있습니다.

균등 표본 추출 사용 – 작은 다항식의 계수는 작은 계수 집합에서 균일하게 표본 추출됩니다.b를 q보다 훨씬 작은 정수라고 가정합니다. 집합에서 계수를 무작위로 선택하는 경우: { -b, -b + 1, -b + 2 . ...-2, -1, 0, 1, 2, ..., b - 2, b - 1, b} 다항식은 결합(b)에 비해 작습니다.Singh는 b = ^[6]5를 사용할 것을 제안한다.따라서 계수는 집합 {q - 5, q - 4, q - 3, q - 2, q - 1, 0, 1, 2, 3, 4, 5 } 중에서 선택됩니다.
이산 가우스 샘플링 사용 – q에 대한 홀수 값의 경우 계수는 평균 0과 분포 모수 θ가 포함된 이산 가우스 분포에 따라 세트 { -(q - 1)/2 ~ (q - 1)/2 }에서 무작위로 샘플링하여 선택합니다.참고 자료에는 이 작업을 수행하는 방법이 자세히 설명되어 있습니다.이것은 균일한 샘플링보다 복잡하지만 알고리즘의 보안을 증명할 수 있습니다.가우스 샘플링의 개요는 Peikert의 ^[8]프레젠테이션에서 찾을 수 있습니다.

이 문서의 나머지 부분에서는 D로 간단히 지정된 분포에 따라 랜덤 소다항식을 추출할 것이다.또한 q는 1 mod 4 및 1 mod 2 n과 일치하도록 홀수 소수가 됩니다.q와 n에 대한 다른 사례는 "Ring-LWE 암호화를 위한 툴킷"과 싱의 "래티스 ^[9]^[10]암호화를 사용한 인터넷을 위한 훨씬 더 실용적인 키 교환" 및 싱의 다른 논문에서 철저히 논의됩니다.네트워크의 모든 사용자가 공유하는 고정 퍼블릭 다항식 a(x)입니다.암호학적으로 안전한 소스로부터 확실하게 생성됩니다.

전술한 바와 같이 a(x)가 주어졌을 때, 우리는 공개 키 교환에서 "비밀 키"가 되도록 작은 다항식 s(x)와 e(x)를 무작위로 선택할 수 있다.해당 공용 키는 다항식 p(x) = a(x)s(x) + 2e(x)가 됩니다.

키 교환

키 교환은 2개의 디바이스 간에 이루어집니다.(I)로 지정된 키 교환의 개시자와 (R)로 지정된 응답자가 있습니다.I와 R은 모두 q, n, a(x)를 알고 있으며 $\alpha$ α(\ $displaystyle$ \alpha $\alpha$ 의 $\chi _{\alpha }$ 분포 $\chi _{\alpha }$ $(\$ displaystyle \ $chi$ _ ${\alpha$ $})$ 에 따라 작은 다항식을 생성할 수 있다. 분포 $\chi _{\alpha }$ (\ $displaystyle \chi$ _{\alpha $})$ 는 $\chi _{\alpha }$ 일반적으로 링 $R_{q}=Zq[x]/\Phi (x)$ $R_{q}=Zq[x]/\Phi (x)$ 의 이산 가우스 분포이다. $R_{q}=Zq[x]/\Phi (x)$ $R_{q}=Zq[x]/\Phi (x)$ $R_{q}=Zq[x]/\Phi (x)$ / $R_{q}=Zq[x]/\Phi (x)$ $R_{q}=Zq[x]/\Phi (x)$ ( x $R_{q}=Zq[x]/\Phi (x)$ ) { $displaystyle R$ _ {q } = $Zq$ [ x $R_{q}=Zq[x]/\Phi (x)$ ] / \ $Phi ($ x ) $R_{q}=Zq[x]/\Phi (x)$ } 。다음 설명에는 링크 양단에서 키 교환이 같은 키가 되는 이유에 대한 설명은 포함되어 있지 않습니다.오히려 취해야 할 단계를 간결하게 명시하고 있습니다.키 교환에 의해 발신측과 응답측의 키가 같은 이유를 충분히 이해하려면 , 독자는 Ding등의 참조된 작업을 참조할 필요가 있습니다.^[2]

키 교환은 이니시에이터(I)가 다음을 수행하는 것으로 시작됩니다.

개시:

$두$ 개의 $s_{I}$ $s_{I}$ 를 생성합니다. $e_{I}$ $}}$ 및 $s_{I}$ $e_{I}$ {\ $displaystyle e_{$ $I}}$ 분포 $e_{I}$ $\chi _{\alpha }$ {\ $displaystyle \chi$ _ ${\alpha$ 에서 추출하여 계수가 작은 값.
$p_{I}=as_{I}+2e_{I}.$ p I $p_{I}=as_{I}+2e_{I}.$ $p_{I}=as_{I}+2e_{I}.$ $p_{I}=as_{I}+2e_{I}.$ + $p_{I}=as_{I}+2e_{I}.$ $p_{I}=as_{I}+2e_{I}.$ I $p_{I}=as_{I}+2e_{I}.$ . { $display style$ p $p_{I}=as_{I}+2e_{I}.$ _ { $I} = as_{I}+$ $나.}$
이니시에이터가 $p_{I}$ $(\$ 를 전송합니다. $I$ 응답자에게.

응답:

분포 $\chi _{\alpha }$ 하여 계수가 작은 2개의 $s_{R}$ $(\$ 와 $s_{R}$ $(\$ $displaystyle$ $e_{R$ $\chi _{\alpha }$ 를 $e_{R}$ 생성합니다.
$p_{R}=as_{R}+2e_{R}$ p R $p_{R}=as_{R}+2e_{R}$ $p_{R}=as_{R}+2e_{R}$ + $p_{R}=as_{R}+2e_{R}$ e $p_{R}=as_{R}+2e_{R}$ { $displaystyle$ p $_$ { R } $=as$ _ { $R}$ + $2e$ _ { $R$
$\chi _{\alpha }$ 에서 $e'_{R}$ $e'_{R}$ R ${\$ { $display$ $style$ \ $chi$ _ { \ $alpha }$ computedisplaydisplay $e'_{R}$ { display style \ ci _ { \ alpha }} 를 생성합니다. $k_{R}=p_{I}s_{R}+2e'_{R}$ k $k_{R}=p_{I}s_{R}+2e'_{R}$ $k_{R}=p_{I}s_{R}+2e'_{R}$ $k_{R}=p_{I}s_{R}+2e'_{R}$ $k_{R}=p_{I}s_{R}+2e'_{R}$ $k_{R}=p_{I}s_{R}+2e'_{R}$ + $k_{R}=p_{I}s_{R}+2e'_{R}$ $k_{R}=p_{I}s_{R}+2e'_{R}$ R ${\$ { $display$ style $k$ _ { $R$ $e'_{R}$ } = $p$ _ { p _ { { r } } $I}s_{R}+2e'_$ ${R}}.$ $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ k $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ s $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ s $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ + $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ s $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ + $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ e $k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}$ ${\$ { $display$ style $k$ _ { R } = $as$ _ { $I}s_{R}+2e_{$ $I}s_{R}+2e'_$ ${R$
신호 $\operatorname {Sig}$ Sig $(\displaystyle \operatorname {Sig})$ 를 $\operatorname {Sig}$ 사용하여 w $=$ $w=\operatorname {Sig} (k_{R})$ $w=\operatorname {Sig} (k_{R})$ ） { $displaystyle$ w =\ $operatorname {Sig$ 를 $Sig$ 구합니다. 이는 K의 $k_{R}$ 계수에 $Sig(\displaystyle$ $k_{R}$ $})$ $함수$ 를 적용하여 $Sig$ 합니다 $.$
응답측 키 $sk_{R}=\operatorname {Mod} _{2}(k_{R},w)$ $sk_{R}=\operatorname {Mod} _{2}(k_{R},w)$ k $sk_{R}=\operatorname {Mod} _{2}(k_{R},w)$ $sk_{R}=\operatorname {Mod} _{2}(k_{R},w)$ $sk_{R}=\operatorname {Mod} _{2}(k_{R},w)$ 2 $sk_{R}=\operatorname {Mod} _{2}(k_{R},w)$ ( $sk_{R}=\operatorname {Mod} _{2}(k_{R},w)$ R , $sk_{R}=\operatorname {Mod} _{2}(k_{R},w)$ ) { $displaystyle sk$ _ { R } = \ $operatorname$ { $Mod$ } $_ {$ 2} ( k $_$ { $R$ , $w$ ) }는 $sk_{R}=\operatorname {Mod} _{2}(k_{R},w)$ $조정$ $정보$ w { $displaystyle$ $w$ $}$ 및 $w$ $k_{R}$ { r $k_{R}$ 에 기초하여 계산된다.
응답자는 p $(\$ }) $w$ w $\displaystyle$ w를 $w$ 이니시에이터로 $p_{R}$ 합니다.

종료:

Responder에서 p $(\$ 및 $p_{R}$ $\displaystyle$ w를 $w$ $p_{R}$ 합니다.
$e'_{I}$ $e'_{I}$ I $©$ { $displaystyle$ e $`$ { $(\$ _ ${\alpha$ }) 및 $\chi _{\alpha }$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ I $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ R $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ I + $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ I $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ + $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ R $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ + $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ I $k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}$ ′ $display$ { displaystyle $k_{$ $I}=p_{R}s_{$ $I}+2e'_{$ $I}=as_{I}s_{R}+2e_{$ $R}s_{I}+2e'_$ ${I$
이니시에이터 측의 키 $sk_{I}=\operatorname {Mod} _{2}(k_{I},w)$ 은 $sk_{I}=\operatorname {Mod} _{2}(k_{I},w)$ k $sk_{I}=\operatorname {Mod} _{2}(k_{I},w)$ $sk_{I}=\operatorname {Mod} _{2}(k_{I},w)$ $sk_{I}=\operatorname {Mod} _{2}(k_{I},w)$ 2 $sk_{I}=\operatorname {Mod} _{2}(k_{I},w)$ ( $sk_{I}=\operatorname {Mod} _{2}(k_{I},w)$ , $sk_{I}=\operatorname {Mod} _{2}(k_{I},w)$ ) { $display$ style $sk$ _ { $I}=\operatorname {Mod}_{2}(k_{I},w)$ _ $sk_{I}=\operatorname {Mod} _{2}(k_{I},w)$ { $displaystyle$ w $}$ 와 $w$ $k_{I}$ $(\displaystyle k_{I$ 의 조정 $w$ 입니다.

위의 키 교환에서 Sig $\displaystyle \operatorname {Sig}$ 는 $\operatorname {Sig}$ 과 $\operatorname {Sig}$ 같이 정의된 신호 함수입니다.

$Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}$ $\mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}$ E : $Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}$ $\mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}$ { - $\mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}$ 4 $\mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}$ , $\mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}$ , $\mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}$ 4 $}$ { $displaystyle$ \ $mathbf$ { $E$ } : = \ { - \ $lfloor$ , \ $ldots$ , \ $lfloor$ \ $frac {q }$ { $4$ $Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}$ $}$ \ $rceil$ \ $\mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}$ = $Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}$ { - $Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}$ } 를 정의합니다 $Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}$ $\lfloor .\rceil$ . $（$ \ $displaystyle$ \lfloor $.\rceil ）$ 는 $\lfloor .\rceil$ 바닥과 반올림을 각각 가장 가까운 정수로 나타냅니다 $\lfloor .\rceil$

$\operatorname {Sig}$ Sig(\ $displaystyle \operatorname {Sig})$ 는 $\operatorname {Sig}$ E의 보수의 특성 함수입니다.

$\operatorname {Sig} :Zq\rightarrow \{0,1\}$ : $\operatorname {Sig} :Zq\rightarrow \{0,1\}$ $\operatorname {Sig} :Zq\rightarrow \{0,1\}$ { $\operatorname {Sig} :Zq\rightarrow \{0,1\}$ , $\operatorname {Sig} :Zq\rightarrow \{0,1\}$ $}$ { $displaystyle \operatorname$ { $Sig$ } : $\operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}$ $\operatorname {Sig} :Zq\rightarrow \{0,1\}$ \ $rightarrow$ \ { 0 , $1$ \ $\operatorname {Sig} :Zq\rightarrow \{0,1\}$ } : Sig $\operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}$ （ $\operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}$ $\operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}$ $\operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}$ { $0 、$ $\operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}$ . \ $displaystyle$ \ $operatorname$ { $Sig$ } = { $texts$ } } $\end {case}}$

$\operatorname {Mod} _{2}$ 2 $({$ 는 $\operatorname {Mod} _{2}$ 다음과 같이 정의된 오류 용어를 제거하기 위한 mod 2 연산입니다. $\operatorname {Mod} _{2}(v,w)={\biggl (}v+w.{\frac {q-1}{2}}{\Biggr )}{\bmod {q}}{\bmod {2}}$ ${\frac {q-1} {2}} {\bmod {q} {\bmod {2}}$

$k_{I}$ 의 $k_{I}$ 은 k_{style $k_{$ 를 표시합니다. $I}$ 와 $k_I$ $({$ 는 거의 동일합니다 $k_{R}$ .이 대략적인 등가값을 사용하여 공유키를 추출하기 위해 신호함수라고도 불리는 조정함수가 사용된다.이 함수는 $R_{q}$ q {\ $displaystyle R_{q}$ 의 $R_{q}$ $다항식$ v {\ $displaystyle$ v $}$ 의 $v$ 각 계수가 있는 영역을 나타내며 k $k_{R}$ {\ $displaystyle k_{R}}$ 및 $k_{R}$ $k_{I}$ I {\ $displaystyle k_{$ R}}의 오차항을 확인하는 데 도움이 됩니다. $I$ 다른 modq 작업은 발생하지 않습니다.

조정 및 키 문자열 생성 방법은 해당 RLWE-KEX 방식에 따라 달라집니다.모듈식 산술에 기반한 방법과 고차원 ^[6]^[11]지오메트리에 기반한 방법이 있습니다.

키 교환이 정상적으로 동작했을 경우, 발신측의 문자열과 응답측의 문자열은 같습니다.

선택한 파라미터의 상세 내용에 따라서는 이 키 교환이 같은 키를 생성하지 못할 가능성이 매우 희박합니다.키 교환의 파라미터는 키 교환의 장애 확률을 검출할 수 없는 카블 또는 디바이스 장애 확률보다 훨씬 작게 하기 위해 선택할 수 있습니다.

파라미터 선택

위에 제시된 RLWE-KEX 교환은 다항식 $\Phi (x)$ ( $\Phi (x)$ $)\displaystyle \Phi (x$ 도 이하의 다항식 링에서 작동합니다.프레젠테이션에서는 n은 2의 거듭제곱이고 q는 1(mod 2n)에 해당하는 소수라고 가정했습니다.Peikert의 논문에서 제시된 지침에 따라 싱은 RLWE-KEX에 대한 두 가지 매개변수를 제안했다.

128비트의 보안의 경우 n = 512, q = 25601 $\Phi (x)=x^{512}+1$ (x ) $=$ $\Phi (x)=x^{512}+1$ + $\Phi (x)=x^{512}+1$ $(\displaystyle \Phi$ ( $\Phi (x)=x^{512}+1$ )= $x^{display}+1$ }

256비트 보안의 경우 n = 1024, q = 40961 및 $\Phi (x)=x^{1024}+1$ ( $\Phi (x)=x^{1024}+1$ $\Phi (x)=x^{1024}+1$ $\Phi (x)=x^{1024}+1$ $\Phi (x)=x^{1024}+1$ $\Phi (x)=x^{1024}+1$ + $\Phi (x)=x^{1024}+1$ { $displaystyle$ \ $Phi$ (x) = $x^$ { $phi }+1$ }

키 교환은 랜덤샘플링과 고정범위를 사용하기 때문에 키 교환이 발신측과 응답측의 같은 키를 생성하지 못할 가능성은 작습니다.가우스 파라미터 θ가 8 ${\textstyle {\frac {8}{\sqrt {2\pi }}}}$ {\ $textstyle {8}{\taxrt {2\pi$ }}}}이고 ${\textstyle {\frac {8}{\sqrt {2\pi }}}}$ 균일한 샘플링 바운드 (b)^[6] = 5(Singh 참조)라고 가정하면 키 어그리먼트 실패 확률은 128비트 시큐어 파라미터의 경우 2 미만⁻⁷¹, 256비트 시큐어 파라미터의 경우 2 미만입니다⁻⁹¹.

2015년 11월 논문에서 Alkim, Ducas, Pöppelmann 및 Schwabe는 다음 매개변수 n = 1024, q¹⁰²⁴ = 12289 및 $\Phi (x)$ ( $\Phi (x)$ ) { $displaystyle \Phi (x)}$ = $\Phi (x)$ x ^[11]+ 1을 권장합니다.이는 Singh의 n = 1024 매개 변수보다 공개 키 크기가 70% 감소된 것이며, NIST의 Nost-Quantum 암호 표준화 프로젝트에 NewHope라는 이름으로 제출되었다.

또한 2015년 11월 논문에서 Alkim, Ducas, Pöppelmann 및 Schwabe는 키 교환을 위한 기본 다항식(위의 a(x))을 각 교환에 대한 보안 난수 생성기에서 무작위로 생성하거나 "nothing up my sleeve"^[11] 또는 NUMS 기법을 사용하여 검증 가능한 방식으로 생성할 것을 권고한다.이와 같이 생성되는 파라미터의 예로는 소수의 ^[12]디지털 표현에 수학적 상수 pi의 자릿수를 포함하는 인터넷 키 교환기(RFC 2409)의 소수이다.첫 번째 방법은 NIST 타원 ^[13]곡선에 대해 Dan Bernstein이 설명한 것과 같은 숨겨진 공격의 가능성을 열어두고 많은 주요 교환에 걸쳐 공격 비용을 상각하는 것을 방지합니다.NUMS 접근방식은 상각할 수 있지만 일반적으로 pi와 e와 같은 일반적인 수학 상수만 사용한다면 번스타인 공격을 피할 수 있다.

키 교환 보안

이 키 교환의 보안은 이상적인 ^[1]^[2]격자에서 최단 벡터 문제(SVP)에 대한 최악의 경우 해결책만큼 어렵다는 것이 입증된 오류 문제가 있는 링 학습의 기본 경도에 기초합니다.특정 격자 파라미터 세트의 실제 보안을 측정하는 가장 좋은 방법은 BKZ 2.0 격자 ^[14]감소 알고리즘입니다.BKZ 2.0 알고리즘에 따르면 위의 키 교환 파라미터는 각각 128비트 또는 256비트 이상의 보안을 제공합니다.

실장

2014년 Douglas Stebila는 "오류 문제가 ^[15]있는 링 러닝에서 TLS 프로토콜을 위한 Post-quantum key exchange"에 게재된 자신의 작업 등을 바탕으로 OpenSSL 1.0.1f용 패치를 만들었습니다.Singh의 작업을 구현하는 소프트웨어는 ^[6]https://github.com/vscrypto/ringlwe의 GitHub에서 찾을 수 있습니다.

기타 접근법

위에서 설명한 접근법의 변형은 장, 장, 딩, 스누크 및 다그델렌의 논문 "이상적 ^[16]격자에서 양자 인증 키 교환 후"에서 인증된 버전입니다.디피(Diffie)라고 불리는 것을 창조하는 개념.조정 기능이 있는 격자를 사용하는 Hellman과 같은 키 교환은 프랑스 연구원 Aguilar, Gaborit, Lacharme, Schrek 및 Zemor에 의해 PQCrypto 2010에서 그들의 강연에서 처음 제시된 것으로 보인다. "Noisy Diffie –헬만 프로토콜"^[17]

2015년 11월, Alkim, Ducas, Pöppelmann 및 Schwabe는 Peikert의 이전 작업을 기반으로 구축되었으며,^[11] 보다 보수적인 격자 공격 비용을 사용하여 매개변수를 권장했다.Alkim, Ducas, Pöppelmann 및 Schwabe의 작업에 기반한 소프트웨어는 GitHub에 있습니다.https://github.com/tpoeppelmann^[11]/newhope

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Regev, Oded (2005). "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05. Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. STOC '05. New York, NY, USA: ACM. pp. 84–93. CiteSeerX 10.1.1.110.4776. doi:10.1145/1060590.1060603. ISBN 978-1-58113-960-0. S2CID 53223958.
^ ^a ^b ^c ^d Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012). A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem (PDF).
^ Peikert, Chris (2014-01-01). "Lattice Cryptography for the Internet". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)
^ Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01). "Post-quantum key exchange - a new hope". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)
^ "Experimenting with Post-Quantum Cryptography". Google Online Security Blog. Retrieved 2017-02-08.
^ ^a ^b ^c ^d ^e ^f Singh, Vikram (2015). "A Practical Key Exchange for the Internet using Lattice Cryptography". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)
^ "Cryptology ePrint Archive: Report 2015/1120". eprint.iacr.org. Retrieved 2015-12-23.
^ "An Efficient and Parallel Gaussian Sampler for Lattices" (PDF). www.cc.gatech.edu. Retrieved 2015-05-29.
^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2013). "A Toolkit for Ring-LWE Cryptography". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)
^ "Cryptology ePrint Archive: Report 2015/1120". eprint.iacr.org. Retrieved 2016-01-17.
^ ^a ^b ^c ^d ^e "Cryptology ePrint Archive: Report 2015/1092". eprint.iacr.org. Retrieved 2015-11-11.
^ D., Carrel; D., Harkins. "The Internet Key Exchange (IKE)". tools.ietf.org. Retrieved 2017-03-16.
^ "Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?". crypto.stackexchange.com. Retrieved 2017-03-16.
^ Chen, Yuanmi; Nguyen, Phong Q. (2011). Lee, Dong Hoon; Wang, Xiaoyun (eds.). BKZ 2.0: Better Lattice Security Estimates. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1–20. doi:10.1007/978-3-642-25385-0_1. ISBN 978-3-642-25384-3.
^ Bos, Joppe W.; Costello, Craig; Naehrig, Michael; Stebila, Douglas (2014-01-01). "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)
^ "Workshop on Cybersecurity in a Post-Quantum World". www.nist.gov. 2015-04-02. Retrieved 2015-06-06.
^ "Noisy Diffie–Hellman protocols" (PDF). pqc2010.cased.de. Retrieved 2015-06-06.

[:4-1] Regev, Oded (2005). "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05. Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. STOC '05. New York, NY, USA: ACM. pp. 84–93. CiteSeerX 10.1.1.110.4776. doi:10.1145/1060590.1060603. ISBN 978-1-58113-960-0. S2CID 53223958.

[:0-2] Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012). A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem (PDF).

[3] Peikert, Chris (2014-01-01). "Lattice Cryptography for the Internet". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)

[4] Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01). "Post-quantum key exchange - a new hope". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)

[5] "Experimenting with Post-Quantum Cryptography". Google Online Security Blog. Retrieved 2017-02-08.

[:1-6] ^ ^a ^b ^c ^d ^e ^f Singh, Vikram (2015). "A Practical Key Exchange for the Internet using Lattice Cryptography". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)

[7] "Cryptology ePrint Archive: Report 2015/1120". eprint.iacr.org. Retrieved 2015-12-23.

[8] "An Efficient and Parallel Gaussian Sampler for Lattices" (PDF). www.cc.gatech.edu. Retrieved 2015-05-29.

[:2-9] Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2013). "A Toolkit for Ring-LWE Cryptography". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)

[10] "Cryptology ePrint Archive: Report 2015/1120". eprint.iacr.org. Retrieved 2016-01-17.

[:3-11] "Cryptology ePrint Archive: Report 2015/1092". eprint.iacr.org. Retrieved 2015-11-11.

[12] D., Carrel; D., Harkins. "The Internet Key Exchange (IKE)". tools.ietf.org. Retrieved 2017-03-16.

[13] "Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?". crypto.stackexchange.com. Retrieved 2017-03-16.

[14] Chen, Yuanmi; Nguyen, Phong Q. (2011). Lee, Dong Hoon; Wang, Xiaoyun (eds.). BKZ 2.0: Better Lattice Security Estimates. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1–20. doi:10.1007/978-3-642-25385-0_1. ISBN 978-3-642-25384-3.

[15] Bos, Joppe W.; Costello, Craig; Naehrig, Michael; Stebila, Douglas (2014-01-01). "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem". {{cite journal}}:Cite저널을 요구한다 journal=( 도와 주)

[16] "Workshop on Cybersecurity in a Post-Quantum World". www.nist.gov. 2015-04-02. Retrieved 2015-06-06.

[17] "Noisy Diffie–Hellman protocols" (PDF). pqc2010.cased.de. Retrieved 2015-06-06.

[1]

[2]

[3]

[5]

[4]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Search

오류가 있는 링 러닝 키 교환

네임스페이스

더

목차

배경

서론

키 교환

파라미터 선택

키 교환 보안

실장

기타 접근법

「」를 참조해 주세요.

레퍼런스

Search

오류가 있는 링 러닝 키 교환

배경

서론

키 교환

파라미터 선택

키 교환 보안

실장

기타 접근법

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.