격자 문제

컴퓨터 과학에서 격자 문제는 격자라 불리는 수학적 물체와 관련된 최적화 문제의 한 종류다.그러한 문제들의 추측 난해성은 보안 격자 기반 암호 시스템의 구축에 핵심적이다: 격자 문제는 암호화 알고리즘의 보안을 위한 시험 사례를 제공하면서 평균 케이스 하드인 것으로 보여진 NP-하드 문제의 한 예다.또한, 최악의 경우 어려운 일부 격자 문제는 극히 안전한 암호 체계를 위한 기초로 사용될 수 있다.그러한 계획에서 최악의 경도를 사용하는 것은 양자 컴퓨터에도 안전할 가능성이 높은 극소수의 계획들 가운데 하나로 만든다.그러한 암호 시스템에 있는 애플리케이션의 경우 벡터 공간(종종 $\mathbb {Z} ^{n}$ ${\$ 또는 무료 모듈(종종 $\mathbb {Z} ^{n}$ n ${\$ 을 통한 격자가 고려된다.

아래의 모든 문제에 대해, 벡터 공간 V와 표준 N에 대한 기초가 주어진다고 가정한다.일반적으로 고려되는 규범은 유클리드 규범 L이다².그러나 다른 규범(L^p 등)도 고려되고 다양한 결과에서 나타난다.^[1] $\lambda (L)$ ( $\lambda (L)$ ) $\lambda (L)$ 은 $\lambda(L)$ 격자 L에서 가장 짧은 0이 아닌 벡터의 길이, 즉,

\lambda(L)=\min _{v\in L\smallsetminus \{\mathbf {0}\}\v\ _{N}}

최단 벡터 문제(SVP)

이것은 최단 벡터 문제(Basis 벡터: 파랑, 최단 벡터: 빨강)에 대한 그림이다.

SVP에서는 격자 L에 대해 벡터 공간 V와 표준 N(종종 L²)의 기초가 제공되며, N이 측정한 대로 V에서 가장 짧은 0이 아닌 벡터를 L에서 찾아야 한다.즉, 알고리즘은 $N(v)=\lambda (L)$ ( $N(v)=\lambda (L)$ ) $N(v)=\lambda (L)$ = $N(v)=\lambda (L)$ ( L $N(v)=\lambda (L)$ ) $N(v)=\lambda (L)$ 과 같은 0이 아닌 벡터 v를 출력해야 한다 $N(v)=\lambda (L)$

γ-대략 버전 SVP에서는_γ 주어진 $\gamma \geq 1$ $\gamma \geq 1$ ${\displaystyle$ $\cdot \lambda$ ( $L)}$ 에 대해 $\gamma \cdot \lambda (L)$ 최대 $\gamma \cdot \lambda (L)$ $\gamma \cdot \lambda (L)$ ( L ){\ $displaystyle$ $\gamba \$ lambda ( $L)}$ 에서 길이가 0이 아닌 격자 벡터를 찾아야 한다 $\gamma \geq 1$

경도 결과

문제의 정확한 버전은 무작위적인 감소를 위해 NP-hard로 알려져 있다.^[2]^[3]

이와는 대조적으로, 통일규범에 관한 해당 문제는 NP-hard로 알려져 있다.^[4]

유클리드 규범 알고리즘

유클리드 규범에 따라 SVP의 정확한 버전을 해결하기 위해 몇 가지 다른 접근법을 알 수 있는데, 이 접근법은 초특수 시간( $2^{\omega (n)}$ ( $2^{\omega (n)}$ ) ${\$ 과 $\operatorname {poly} (n)$ $\operatorname {poly} (n)$ ( $){\displaystystyle \operatorname {poly}(n)$ 메모리가 $\operatorname {poly} (n)$ 필요한 알고리즘의 두 종류로 나눌 수 있다.tial 시간과 공간(2 $2^{\Theta (n)}$ ( $2^{\Theta (n)}$ ${\$ 디스플레이 $스타일$ 2 $^{\$ 격자 치수의 $세타(n$ 이전의 알고리즘 등급은 격자 열거^[5]^[6]^[7] 및 무작위 샘플링 감소를 가장 두드러지게 포함하며,^[8]^[9] 후자는 격자 체이빙,^[10]^[11]^[12] 격자의 보로노이 셀 계산,^[13]^[14] 이산 가우스 샘플링을 포함한다.^[15]개방적인 문제는 정확한 SVP를 해결하기 위한 알고리즘이 단일 $2^{O(n)}$ 시간( $2^{O(n)}$ O $2^{O(n)}$ ( $2^{O(n)}$ ) ${\$ 에서 실행 중이고, 격자 차원에 다항적으로 메모리 스케일링이 필요한지 여부다.^[16]

유클리드 규범에 $\gamma >1$ $\gamma >1$ > 1 $\gamma >1$ 에 대한 γ 근사 버전 SVP를_γ 해결하기 위해, 가장 잘 알려진 접근법은 격자 기준 감소를 사용하는 것에 기초한다.큰 $\gamma =2^{\Omega (n)}$ = $\gamma =2^{\Omega (n)}$ ( $\gamma =2^{\Omega (n)}$ ){\displaystyle $\gamma =2^{\Oomega (n)}}}}$ 의 경우 $\gamma =2^{\Omega (n)}$ Lenstra-Lenstra-Lovász(LLL) 알고리즘은 격자차원에서 시간 다항식의 솔루션을 찾을 수 있다.더 적은 값 γ{\displaystyle \gamma}내용은 블록 Korkine-Zolotarev 알고리즘(BKZ)[17][18][19]일반적으로, 알고리즘(그blocksize β{\displaystyle \beta})에 입력하는 시간 복잡성과 출력 품질는지를 확인합니다. 큰 근사 요인에 대하여{\displaystyle \gamma}, 작은 블록 크기 γ 사용된다. β{\disp $laystyle \property }$ 이면 $\beta$ 충분하며 알고리즘은 빠르게 종료된다.소형 $\gamma$ $\gamma$ 의 경우 충분히 짧은 격자 벡터를 찾으려면 더 큰 $\beta$ $\beta$ 이 $\gamma$ 가) 필요하며 $\beta$ , 알고리즘이 솔루션을 찾는데 더 오랜 시간이 걸린다.BKZ 알고리즘은 내부적으로 서브루틴으로서 정확한 SVP 알고리즘을 사용하며(최대 $\beta$ $\beta$ 에서 치수 래티스로 실행됨) $\beta$ 전체적인 복잡성은 치수 $\beta$ $\beta$ 에서 이러한 SVP 호출 비용과 밀접하게 관련되어 있다 $\beta$

갭SVP

GapSVPβ 부사장의에서 가장 작은 벡터의 길이 대부분은 1{1\displaystyle}을 보거나 격자 n{n\displaystyle}의 차원의β{\beta\displaystyle}가 될 수 있어 고정된 기능 β{\beta\displaystyle},보다 크다 인스턴스를 구별하는 것을 구성된 문제이다.톤을 위한 기반 위he 격자, 알고리즘은 $\lambda (L)\leq 1$ $\lambda (L)\leq 1$ ( $\lambda (L)\leq 1$ ) $\lambda (L)\leq 1$ 1 $\lambda (L)\leq 1$ {\ $displaystyle \lambda (L)\leq$ 1} $\lambda (L)>\beta$ $\lambda (L)>\beta$ $\lambda (L)>\beta$ ) $\lambda (L)>\beta$ ${\displaystyle \lambda (L)\beta$ }}}의 여부를 결정해야 한다 $\lambda (L)>\beta$ 다른 약속 문제와 마찬가지로 알고리즘도 다른 모든 경우에 오류가 발생할 수 있다.

그러나 그 문제의 또 다른 버전은 GapSVPζ, 일부 기능에 γ,γ{\displaystyle \zeta ,\gamma}. ζ은 알고리즘에 입력 기본이고 B{B\displaystyle}하며, 숫자 d{\displaystyle d}. 그것은 Gram–Schmidt의 직교의 모든 벡터 길이 최소 1이며λ(L(B))≤된다. ζ( $\lambda (L(B))\leq \zeta (n)$ ) $\lambda (L(B)\leq \zeta (n)$ 및 $\lambda (L(B))\leq \zeta (n)$ 그 1 $1\leq d\leq \zeta (n)/\gamma (n)$ d $1\leq d\leq \zeta (n)/\gamma (n)$ $1\leq d\leq \zeta (n)/\gamma (n)$ ) / $1\leq d\leq \zeta (n)/\gamma (n)$ ( $1\leq d\leq \zeta (n)/\gamma (n)$ ) ${\$ $displaystyle$ $1\leq d\leq \zeta (n)/\damma (n)}.$ $n$ 서 $1 \leq d \leq \zeta(n)/\gamma(n)$ n $}$ 은 $차원$ 이다 $n$ .만약λ(L(B))≤ d{\displaystyle \lambda(L(B))\leq d}이 알고리즘, 그리고 만약λ(L(B))≥γ(n)을 거절하다 d{\displaystyle \lambda(L(B))\geq \gamma(n).d}. 대규모ζ{\zeta\displaystyle}(ζ(n)>;2n/2{\displaystyle \zeta(n)>, 2^{n/2}}), 그 문제 GapSVPγ bec에 해당합니다를 받아들여야 한다.한 ause[20]LLL 알고리즘을 사용하여 사전 처리를 수행하면 두 번째 조건(따라서, $\zeta$ $\zeta$ )이 중복된다.

가장 가까운 벡터 문제(CVP)

이것은 가장 가까운 벡터 문제(Basis 벡터: 파랑, 외부 벡터: 녹색, 가장 가까운 벡터: 빨강)에 대한 그림이다.

CVP에서는 격자 L에 대한 벡터 공간 V와 미터법 M(종종 L²)의 기초가 제공되며, V에는 벡터 V가 제공되지만 L에는 반드시 제공되지 않는다.v에 가장 가까운 L에서 벡터를 찾는 것이 바람직하다(M으로 측정). $\gamma$ $\gamma$ - 근사치 $\gamma$ 버전 CVP에서는_γ $\gamma$ $\gamma$ 의 거리에서 격자 벡터를 찾아야 한다 $\gamma$

SVP와의 관계

가장 가까운 벡터 문제는 최단 벡터 문제의 일반화다.CVP용_γ Oracle(아래 정의)을 지정하면 Oracle에 몇 가지 조회를 함으로써 SVP를_γ 해결할 수 있다는 것을 쉽게 보여줄 수 있다.^[21]0은 그 자체가 격자 벡터이고 알고리즘이 잠재적으로 0을 출력할 수 있기 때문에 CVP_γ 오라클을 호출하여 최단 벡터를 찾는 순진한 방법은 효과가 없다.

SVP에서_γ CVP로의_γ 감소는 다음과 같다.Suppose that the input to the SVP_γ is the basis for lattice $B=[b_{1},b_{2},\ldots ,b_{n}]$ . Consider the basis $B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]$ and let $x_{i}$ be the vect또는 CVP_γ(Bⁱ, b_i)에 의해 반환된다.그 주장은 $\{x_{i}-b_{i}\}$ { $\{x_{i}-b_{i}\}$ - $\{x_{i}-b_{i}\}$ i $}$ {\ $displaystyle \{x_{i}-b_{$ i}\}}}의 최단 벡터가 주어진 격자에서 최단 벡터라는 $\{x_{i}-b_{i}\}$ 것이다.

경도 결과

Goldreich 외 연구진은 SVP의 경도는 CVP에 대해 동일한 경도를 내포한다는 것을 보여주었다.^[22]PCP기구를 사용하여, Arora(알. 중심정 맥압과 가까워지려고 인자 2로그 1−ϵ⁡(n){\displaystyle 2^{\log ^{1-\epsilon}(n)내에}은 어렵}{\displaystyle \operatorname{문제 없어}\subseteq\operatorname{DTIME}(2^{\operatorname{폴리에스테르}(\log n)})}.[23]Dinur(알.을 강화하지 않는 한 문제 없어)DTIME ⁡(2폴리 ⁡(통나무⁡ n)⊆을 보여 주었다.교육 $c<1/2$ < $c<1/2$ / 2 ${\displaystyle c<1/2$ ^[24]에 대해 $\epsilon =(\log \log n)^{c}$ = $\epsilon =(\log \log n)^{c}$ (log $\log$ n $)^{c}}$ 를 사용하여 NP 경도 결과를 제공함으로써.

구 디코딩

CVP 알고리즘,^[6] 특히 핀케와 포스트 변종은 다중 입력 다중 출력(MIMO) 무선 통신 시스템(코딩되지 않은 신호 및 코드화되지 않은 신호용)에서 데이터 검출에 사용되어 왔다.^[25]^[13]이러한 맥락에서 그것은 많은 CVP 용액의 내부에서 사용되는 반지름 때문에 구체 디코딩이라고 불린다.^[26]

반송파상 GNSS(Garrier-phase GNSS)의 정수 모호성 분해능 분야에 적용되었다.^[27]그 분야에서는 램다(LAMBDA) 방식이라고 한다.동일한 필드에서 일반적인 CVP 문제를 정수 최소 제곱이라고 한다.

GapCVP

이 문제는 GapSVP 문제와 비슷하다.GapSVP의 경우 입력은 격자 기반과 $벡터$ v $v$ 로 구성되며 $v$ 알고리즘은 다음 중 하나가 고정되는지 여부를 답해야 한다._β

격자 벡터와 $v$ $v$ 사이의 거리가 최대 $v$ 1인 격자 벡터가 있다.
모든 격자 벡터는 $v$ ${\displaystyle$ \displaystyle v}에서 $\beta$ $\beta$ ${\$ displaystyle \ $disp$ }보다 큰 거리에 있다 $v$

반대 조건으로는 가장 가까운 격자 벡터가 $1<\lambda (L)\leq \beta$ 1 < $1<\lambda (L)\leq \beta$ ( $1<\lambda (L)\leq \beta$ ) $1<\lambda (L)\leq \beta$ β $1<\lambda (L)\leq \beta$ ${\displaystyle 1<\lambda (L)\leq \beta$ $1<\lambda (L)\leq \beta$ 에 있으므로 이름이 GapCVP이다.

알려진 결과

문제는 근사 인자에 대해 NP에 사소한 것으로 포함되어 있다.

Schnorr, 1987년, 결정론적 다항 시간 알고리즘)β를 위해서는 2O(n(통나무 ⁡ 로그⁡ n)를 해결할 수 있다는 것을 2/로그⁡ nx{\displaystyle\beta =2^{O(n(\log\log n)^{2}/\log nx}}.[28]Ajtai(알을 보여 주었다.는 확률적 알고리즘 수 있기 약간 더 좋은 근사 요인의 β x2O(n로그 ⁡ lo.g⁡ $\beta =2^{O(n\log \log n/\log n)}$ / $\beta =2^{O(n\log \log n/\log n)}$ $){\$ n $/\log n$ ^[10]

In 1993, Banaszczyk showed that GapCVP_n is in ${\mathsf {NP\cap coNP}}$ .^[29] In 2000, Goldreich and Goldwasser showed that $\beta ={\sqrt {n/\log n}}$ puts the problem in both NP and coAM.^[30]2005년에 Aharonov와 Regev는 일부 상수 $c$ ${\displaystyle$ c $}$ 에 대해 $c$ $\beta =c{\sqrt {n}}$ = $\beta =c{\sqrt {n}}$ ${\$ 의 문제가 $\beta =c{\sqrt {n}}$ ${\mathsf {NP\cap coNP}}$ ${\mathsf {NP\cap coNP}}$ ${\mathsf {NP\cap coNP}}$ N P ${\$ 에 있다는 것을 보여주었다 ${\mathsf {NP\cap coNP}}$ ^[31]

하한에 대해서는 1998년 디누르 외 연구진이 $\beta =n^{o(1/\log {\log {n}})}$ = n $\beta =n^{o(1/\log {\log {n}})}$ ( $\beta =n^{o(1/\log {\log {n}})}$ / log $\beta =n^{o(1/\log {\log {n}})}$ log $\beta =n^{o(1/\log {\log {n}})}$ ){\ $displaystyle \beta$ =n $^{o($ 1/\ $log {\n$ ^[32]에 대해 NP-hard가 문제라는 것을 보여주었다.

최단 독립 벡터 문제(SIVP)

Given a lattice L of dimension n, the algorithm must output n linearly independent $v_{1},v_{2},\ldots ,v_{n}$ so that $\max \ v_{i}\ \leq \max _{B}\ b_{i}\$ where the right hand side considers all bases $B=\{b_{1},\ldots ,b_{n}\}$ $B=\{b_{1},\ldots ,b_{n}\}$ ${\displaystyle B=\{b_{1},\ldots ,b_$

In the $\gamma$ -approximate version, given a lattice L with dimension n, find n linearly independent vectors $v_{1},v_{2},\ldots ,v_{n}$ of length $\max \ v_{i}\ \leq \gamma \lambda _{n}(L)$ , where $\lambda _{n}(L)$ ${\displaystyle \lambda _{n}(L)$ 은 $n$ ${\displaystyle$ n $}$ 의 $n$ ' $th번째$ 연속 최소 $L$ $L$ 이다 $\lambda_n(L)$ $L$

경계 거리 디코딩

이 문제는 CVP와 비슷하다.격자로부터의 거리가 최대 $\lambda (L)/2$ ( $\lambda (L)/2$ ) $\lambda (L)/2$ / 2 $\lambda (L)/2$ 인 벡터를 사용할 경우 알고리즘은 가장 가까운 격자 벡터를 출력해야 한다 $\lambda (L)/2$

커버 반지름 문제

격자 기초가 주어진 알고리즘은 어떤 벡터로부터 격자까지의 가장 큰 거리(또는 일부 버전에서는 근사치)를 찾아야 한다.

최단기 문제

입력 기준이 짧은 벡터로 구성되면 많은 문제가 쉬워진다.최단 기본 문제(SBP)를 해결하는 알고리즘은 격자 기준 $B$ $B$ 을 $B$ 를) 주어진 경우 $B$ $'$ ${\$ 에서 가장 긴 벡터의 길이가 가능한 짧게 되도록 $B'$ $B'$ 동등한 기준 $B$ $'$ ${\$ B $'}$ 을(를) 출력해야 한다.

근사 버전 SBP_γ 문제는 가장 긴 벡터가 최단 기준의 가장 긴 벡터보다 $\gamma$ $\gamma$ 배 $\gamma$ 긴 기초를 찾는 것으로 구성된다.

암호화에 사용

문제의 평균 사례 경도는 대부분의 암호 체계에서 보안 증명(proof-of-security)의 기초를 형성한다.그러나 실험적인 증거는 대부분의 NP-하드 문제에는 이러한 특성이 결여되어 있다는 것을 시사한다: 그들은 아마도 최악의 경우일 것이다.많은 격자문제는 평균 케이스가 어려운 것으로 추측되거나 입증되어 암호 체계를 기반으로 하는 매력적인 문제 등급이 되었다.더욱이 일부 격자문제의 최악의 경도는 안전한 암호 체계를 만드는 데 사용되었다.그러한 계획에서 최악의 경도를 사용하는 것은 양자 컴퓨터에도 안전할 가능성이 높은 극소수의 계획들 가운데 하나로 만든다.

위의 격자 문제는 알고리즘이 "좋은" 기초를 제공한다면 해결하기가 쉽다.격자 감소 알고리즘은 격자의 기초가 주어진 경우 비교적 짧고 거의 직교 벡터로 구성된 새로운 기준을 출력하는 것을 목표로 한다.Lenstra-Lenstra-Lovasz 격자 기반 감소 알고리즘(LLL)은 다항식 시간에 거의 감소된 격자 기초를 출력할 수 있는 이 문제에 대한 초기 효율적인 알고리즘이었다.^[33]이 알고리즘과 그 추가적 정비는 여러 암호 체계를 깨기 위해 사용되어 암호 분석에서 매우 중요한 도구로서의 지위를 확립했다.실험 데이터에 대한 LLL의 성공은 격자 감소가 실제로 쉬운 문제일 수 있다는 믿음으로 이어졌다.그러나 이러한 믿음은 1990년대 후반 아제타이의 결과를 시작으로 격자 문제의 경도에 관한 몇 가지 새로운 결과를 얻었을 때 도전을 받았다.^[2]

아제이는 그의 논문에서 SVP 문제가 NP-hard임을 보여주었고 최악의 경우 복잡성과 일부 격자 문제의 평균 사례 복잡성 사이의 연관성을 발견했다.^[2]^[3]이러한 결과를 토대로 아제이와 드워크는 특정 버전의 SVP의 최악의 경도만을 사용하여 보안성을 증명할 수 있는 공개키 암호체계를 만들었고,^[34] 따라서 보안 시스템을 만들기 위해 최악의 경도를 사용한 최초의 결과가 되었다.^[35]

참고 항목

참조

^ Khot, Subhash (2005). "Hardness of approximating the shortest vector problem in lattices". J. ACM. 52 (5): 789–808. doi:10.1145/1089023.1089027. S2CID 13438130.
^ ^a ^b ^c Ajtai, M. (1996). "Generating hard instances of lattice problems". Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. Philadelphia, Pennsylvania, United States: ACM. pp. 99–108.
^ ^a ^b Ajtai, Miklós (1998). "The shortest vector problem in L₂ is NP-hard for randomized reductions". Proceedings of the thirtieth annual ACM symposium on Theory of computing. Dallas, Texas, United States: ACM. pp. 10–19.
^ van Emde Boas, Peter (1981). "Another NP-complete problem and the complexity of computing short vectors in a lattice". Technical Report 8104. University of Amsterdam, Department of Mathematics, Netherlands.
^ Kannan, Ravi (1983). "Improved Algorithms for Integer Programming and Related Lattice Problems". Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83. Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC '83. New York, NY, USA: ACM. pp. 193–206. doi:10.1145/800061.808749. ISBN 978-0897910996. S2CID 18181112.
^ ^a ^b Fincke, U.; Pohst, M. (1985). "Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis". Math. Comp. 44 (170): 463–471. doi:10.1090/S0025-5718-1985-0777278-8.
^ Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded (2010-05-30). Lattice Enumeration Using Extreme Pruning. Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. Springer, Berlin, Heidelberg. pp. 257–278. doi:10.1007/978-3-642-13190-5_13. ISBN 978-3-642-13189-9.
^ Schnorr, Claus Peter (2003-02-27). "Lattice Reduction by Random Sampling and Birthday Methods". Stacs 2003. Lecture Notes in Computer Science. Vol. 2607. Springer, Berlin, Heidelberg. pp. 145–156. CiteSeerX 10.1.1.137.4293. doi:10.1007/3-540-36494-3_14. ISBN 978-3540364948. {{cite book}}:누락 또는 비어 있음 title=(도움말)
^ Aono, Yoshinori; Nguyen, Phong Q. (2017-04-30). Random Sampling Revisited: Lattice Enumeration with Discrete Pruning (PDF). Advances in Cryptology – EUROCRYPT 2017. Lecture Notes in Computer Science. Vol. 10211. Springer, Cham. pp. 65–102. doi:10.1007/978-3-319-56614-6_3. ISBN 978-3-319-56613-9.
^ ^a ^b Ajtai, Miklós; Kumar, Ravi; Sivakumar, D. (2001). "A sieve algorithm for the shortest lattice vector problem". Proceedings of the thirty-third annual ACM symposium on Theory of computing. Hersonissos, Greece: ACM. pp. 601–610.
^ Micciancio, Daniele; Voulgaris, Panagiotis (2010). Faster Exponential Time Algorithms for the Shortest Vector Problem. Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '10. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. 1468–1480. doi:10.1137/1.9781611973075.119. ISBN 9780898716986. S2CID 90084.
^ Becker, A.; Ducas, L.; Gama, N.; Laarhoven, T. (2015-12-21). "New directions in nearest neighbor searching with applications to lattice sieving". Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings. Society for Industrial and Applied Mathematics. pp. 10–24. doi:10.1137/1.9781611974331.ch2. ISBN 978-1-61197-433-1.
^ ^a ^b Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "Closest Point Search in Lattices". IEEE Trans. Inf. Theory. 48 (8): 2201–2214. doi:10.1109/TIT.2002.800499.
^ Micciancio, Daniele; Voulgaris, Panagiotis (2010). A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations. Proceedings of the Forty-second ACM Symposium on Theory of Computing. STOC '10. New York, NY, USA: ACM. pp. 351–358. CiteSeerX 10.1.1.705.3304. doi:10.1145/1806689.1806739. ISBN 9781450300506. S2CID 2449948.
^ Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah (2015). Solving the Shortest Vector Problem in 2N Time Using Discrete Gaussian Sampling: Extended Abstract. Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing. STOC '15. New York, NY, USA: ACM. pp. 733–742. doi:10.1145/2746539.2746606. ISBN 9781450335362. S2CID 10214330.
^ Micciancio, Daniele (2017-07-01). "Lattice Cryptography – Shortest Vector Problem".
^ Schnorr, C. P. (1987-01-01). "A hierarchy of polynomial time lattice basis reduction algorithms". Theoretical Computer Science. 53 (2): 201–224. doi:10.1016/0304-3975(87)90064-8.
^ Schnorr, C. P.; Euchner, M. (1994-08-01). "Lattice basis reduction: Improved practical algorithms and solving subset sum problems" (PDF). Mathematical Programming. 66 (1–3): 181–199. doi:10.1007/bf01581144. ISSN 0025-5610. S2CID 15386054.
^ Chen, Yuanmi; Nguyen, Phong Q. (2011-12-04). BKZ 2.0: Better Lattice Security Estimates. Advances in Cryptology – ASIACRYPT 2011. Lecture Notes in Computer Science. Vol. 7073. Springer, Berlin, Heidelberg. pp. 1–20. doi:10.1007/978-3-642-25385-0_1. ISBN 978-3-642-25384-3.
^ Peikert, Chris (2009). "Public-key cryptosystems from the worst-case shortest vector problem: extended abstract". Proceedings of the 41st annual ACM symposium on Theory of Computing. Bethesda, MD, USA: ACM. pp. 333–342.
^ Micciancio, Daniele; Goldwasser, Shafi (2002). Complexity of Lattice Problems. Springer.
^ Goldreich, O.; et al. (1999). "Approximating shortest lattice vectors is not harder than approximating closest lattice vectors". Inf. Process. Lett. 71 (2): 55–61. doi:10.1016/S0020-0190(99)00083-6.
^ Arora, Sanjeev; et al. (1997). "The hardness of approximate optima in lattices, codes, and systems of linear equations". Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. J. Comput. Syst. Sci. Vol. 54. pp. 317–331. doi:10.1109/SFCS.1993.366815. ISBN 978-0-8186-4370-5. S2CID 44988406.
^ Dinur, I.; et al. (2003). "Approximating CVP to Within Almost-Polynomial Factors is NP-Hard". Combinatorica. 23 (2): 205–243. doi:10.1007/s00493-003-0019-y. S2CID 45754954.
^ Biglieri, E.; Calderbank, R.; Constantinides, Anthony G.; Goldsmith, A.; Paulraj, A.; Poor, H. V. (2007). MIMO Wireless Communications. Cambridge: Cambridge U. P.
^ Wang, Ping; Le-Ngoc, Tho (2011). "A List Sphere Decoding Algorithm with Improved Radius Setting Strategies". Wireless Personal Communications. 61 (1): 189–200. doi:10.1007/s11277-010-0018-4. S2CID 30919872.
^ Hassibi, A.; Boyd, S. (1998). "Integer Parameter Estimation in Linear Models with Applications to GPS". IEEE Trans. Sig. Proc. 46 (11): 2938–2952. Bibcode:1998ITSP...46.2938H. CiteSeerX 10.1.1.114.7246. doi:10.1109/78.726808.
^ Schnorr, C. P. "Factoring integers and computing discrete logarithms via diophantine approximation". Advances in Cryptology: Proceedings of Eurocrypt '91.
^ Banaszczyk, W. (1993). "New bounds in some transference theorems in the geometry of numbers". Math. Ann. 296 (1): 625–635. doi:10.1007/BF01445125. S2CID 13921988.
^ Goldreich, Oded; Goldwasser, Shafi (1998). "On the limits of non-approximability of lattice problems". Proceedings of the thirtieth annual ACM symposium on Theory of computing. Dallas, Texas, United States: ACM. pp. 1–9.
^ Aharonov, Dorit; Oded Regev (2005). "Lattice problems in NP $\cap$ coNP". J. ACM. 52 (5): 749–765. CiteSeerX 10.1.1.205.3730. doi:10.1145/1089023.1089025. S2CID 1669286.
^ Dinur, I.; Kindler, G.; Safra, S. (1998). "Approximating-CVP to within Almost-Polynomial Factors is NP-Hard". Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society. p. 99. ISBN 978-0-8186-9172-0.
^ Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. (1982). "Factoring polynomials with rational coefficients" (PDF). Math. Ann. 261 (4): 515–534. doi:10.1007/BF01457454. S2CID 5701340. Archived from the original (PDF) on 2011-07-17.
^ Ajtai, Miklós; Dwork, Cynthia (1997). "A public-key cryptosystem with worst-case/average-case equivalence". Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. El Paso, Texas, United States: ACM. pp. 284–293.
^ Cai, Jin-Yi (2000). "The Complexity of Some Lattice Problems". Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 1838. pp. 1–32. doi:10.1007/10722028_1. ISBN 978-3-540-67695-9.

추가 읽기

Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "Closest Point Search in Lattices". IEEE Trans. Inf. Theory. 48 (8): 2201–2214. doi:10.1109/TIT.2002.800499.
Micciancio, Daniele (2001). "The Shortest Vector Problem is {NP}-hard to approximate to within some constant". SIAM Journal on Computing. 30 (6): 2008–2035. CiteSeerX 10.1.1.93.6646. doi:10.1137/S0097539700373039.
Nguyen, Phong Q.; Stern, Jacques (2000). "Lattice Reduction in Cryptology: An Update". Proceedings of the 4th International Symposium on Algorithmic Number Theory. Springer-Verlag. pp. 85–112. ISBN 978-3-540-67695-9.

[1] Khot, Subhash (2005). "Hardness of approximating the shortest vector problem in lattices". J. ACM. 52 (5): 789–808. doi:10.1145/1089023.1089027. S2CID 13438130.

[ajtai-2] Ajtai, M. (1996). "Generating hard instances of lattice problems". Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. Philadelphia, Pennsylvania, United States: ACM. pp. 99–108.

[Ajtai_1998_10–19-3] Ajtai, Miklós (1998). "The shortest vector problem in L₂ is NP-hard for randomized reductions". Proceedings of the thirtieth annual ACM symposium on Theory of computing. Dallas, Texas, United States: ACM. pp. 10–19.

[vEB-4] van Emde Boas, Peter (1981). "Another NP-complete problem and the complexity of computing short vectors in a lattice". Technical Report 8104. University of Amsterdam, Department of Mathematics, Netherlands.

[5] Kannan, Ravi (1983). "Improved Algorithms for Integer Programming and Related Lattice Problems". Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83. Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC '83. New York, NY, USA: ACM. pp. 193–206. doi:10.1145/800061.808749. ISBN 978-0897910996. S2CID 18181112.

[:0-6] Fincke, U.; Pohst, M. (1985). "Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis". Math. Comp. 44 (170): 463–471. doi:10.1090/S0025-5718-1985-0777278-8.

[7] Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded (2010-05-30). Lattice Enumeration Using Extreme Pruning. Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. Springer, Berlin, Heidelberg. pp. 257–278. doi:10.1007/978-3-642-13190-5_13. ISBN 978-3-642-13189-9.

[8] Schnorr, Claus Peter (2003-02-27). "Lattice Reduction by Random Sampling and Birthday Methods". Stacs 2003. Lecture Notes in Computer Science. Vol. 2607. Springer, Berlin, Heidelberg. pp. 145–156. CiteSeerX 10.1.1.137.4293. doi:10.1007/3-540-36494-3_14. ISBN 978-3540364948. {{cite book}}:누락 또는 비어 있음 title=(도움말)

[9] Aono, Yoshinori; Nguyen, Phong Q. (2017-04-30). Random Sampling Revisited: Lattice Enumeration with Discrete Pruning (PDF). Advances in Cryptology – EUROCRYPT 2017. Lecture Notes in Computer Science. Vol. 10211. Springer, Cham. pp. 65–102. doi:10.1007/978-3-319-56614-6_3. ISBN 978-3-319-56613-9.

[:1-10] Ajtai, Miklós; Kumar, Ravi; Sivakumar, D. (2001). "A sieve algorithm for the shortest lattice vector problem". Proceedings of the thirty-third annual ACM symposium on Theory of computing. Hersonissos, Greece: ACM. pp. 601–610.

[11] Micciancio, Daniele; Voulgaris, Panagiotis (2010). Faster Exponential Time Algorithms for the Shortest Vector Problem. Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '10. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. 1468–1480. doi:10.1137/1.9781611973075.119. ISBN 9780898716986. S2CID 90084.

[12] Becker, A.; Ducas, L.; Gama, N.; Laarhoven, T. (2015-12-21). "New directions in nearest neighbor searching with applications to lattice sieving". Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings. Society for Industrial and Applied Mathematics. pp. 10–24. doi:10.1137/1.9781611974331.ch2. ISBN 978-1-61197-433-1.

[:2-13] Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "Closest Point Search in Lattices". IEEE Trans. Inf. Theory. 48 (8): 2201–2214. doi:10.1109/TIT.2002.800499.

[14] Micciancio, Daniele; Voulgaris, Panagiotis (2010). A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations. Proceedings of the Forty-second ACM Symposium on Theory of Computing. STOC '10. New York, NY, USA: ACM. pp. 351–358. CiteSeerX 10.1.1.705.3304. doi:10.1145/1806689.1806739. ISBN 9781450300506. S2CID 2449948.

[15] Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah (2015). Solving the Shortest Vector Problem in 2N Time Using Discrete Gaussian Sampling: Extended Abstract. Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing. STOC '15. New York, NY, USA: ACM. pp. 733–742. doi:10.1145/2746539.2746606. ISBN 9781450335362. S2CID 10214330.

[16] Micciancio, Daniele (2017-07-01). "Lattice Cryptography – Shortest Vector Problem".

[17] Schnorr, C. P. (1987-01-01). "A hierarchy of polynomial time lattice basis reduction algorithms". Theoretical Computer Science. 53 (2): 201–224. doi:10.1016/0304-3975(87)90064-8.

[18] Schnorr, C. P.; Euchner, M. (1994-08-01). "Lattice basis reduction: Improved practical algorithms and solving subset sum problems" (PDF). Mathematical Programming. 66 (1–3): 181–199. doi:10.1007/bf01581144. ISSN 0025-5610. S2CID 15386054.

[19] Chen, Yuanmi; Nguyen, Phong Q. (2011-12-04). BKZ 2.0: Better Lattice Security Estimates. Advances in Cryptology – ASIACRYPT 2011. Lecture Notes in Computer Science. Vol. 7073. Springer, Berlin, Heidelberg. pp. 1–20. doi:10.1007/978-3-642-25385-0_1. ISBN 978-3-642-25384-3.

[20] Peikert, Chris (2009). "Public-key cryptosystems from the worst-case shortest vector problem: extended abstract". Proceedings of the 41st annual ACM symposium on Theory of Computing. Bethesda, MD, USA: ACM. pp. 333–342.

[21] Micciancio, Daniele; Goldwasser, Shafi (2002). Complexity of Lattice Problems. Springer.

[22] Goldreich, O.; et al. (1999). "Approximating shortest lattice vectors is not harder than approximating closest lattice vectors". Inf. Process. Lett. 71 (2): 55–61. doi:10.1016/S0020-0190(99)00083-6.

[23] Arora, Sanjeev; et al. (1997). "The hardness of approximate optima in lattices, codes, and systems of linear equations". Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. J. Comput. Syst. Sci. Vol. 54. pp. 317–331. doi:10.1109/SFCS.1993.366815. ISBN 978-0-8186-4370-5. S2CID 44988406.

[24] Dinur, I.; et al. (2003). "Approximating CVP to Within Almost-Polynomial Factors is NP-Hard". Combinatorica. 23 (2): 205–243. doi:10.1007/s00493-003-0019-y. S2CID 45754954.

[25] Biglieri, E.; Calderbank, R.; Constantinides, Anthony G.; Goldsmith, A.; Paulraj, A.; Poor, H. V. (2007). MIMO Wireless Communications. Cambridge: Cambridge U. P.

[26] Wang, Ping; Le-Ngoc, Tho (2011). "A List Sphere Decoding Algorithm with Improved Radius Setting Strategies". Wireless Personal Communications. 61 (1): 189–200. doi:10.1007/s11277-010-0018-4. S2CID 30919872.

[27] Hassibi, A.; Boyd, S. (1998). "Integer Parameter Estimation in Linear Models with Applications to GPS". IEEE Trans. Sig. Proc. 46 (11): 2938–2952. Bibcode:1998ITSP...46.2938H. CiteSeerX 10.1.1.114.7246. doi:10.1109/78.726808.

[28] Schnorr, C. P. "Factoring integers and computing discrete logarithms via diophantine approximation". Advances in Cryptology: Proceedings of Eurocrypt '91.

[29] Banaszczyk, W. (1993). "New bounds in some transference theorems in the geometry of numbers". Math. Ann. 296 (1): 625–635. doi:10.1007/BF01445125. S2CID 13921988.

[30] Goldreich, Oded; Goldwasser, Shafi (1998). "On the limits of non-approximability of lattice problems". Proceedings of the thirtieth annual ACM symposium on Theory of computing. Dallas, Texas, United States: ACM. pp. 1–9.

[31] Aharonov, Dorit; Oded Regev (2005). "Lattice problems in NP $\cap$ coNP". J. ACM. 52 (5): 749–765. CiteSeerX 10.1.1.205.3730. doi:10.1145/1089023.1089025. S2CID 1669286.

[32] Dinur, I.; Kindler, G.; Safra, S. (1998). "Approximating-CVP to within Almost-Polynomial Factors is NP-Hard". Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society. p. 99. ISBN 978-0-8186-9172-0.

[33] Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. (1982). "Factoring polynomials with rational coefficients" (PDF). Math. Ann. 261 (4): 515–534. doi:10.1007/BF01457454. S2CID 5701340. Archived from the original (PDF) on 2011-07-17.

[34] Ajtai, Miklós; Dwork, Cynthia (1997). "A public-key cryptosystem with worst-case/average-case equivalence". Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. El Paso, Texas, United States: ACM. pp. 284–293.

[35] Cai, Jin-Yi (2000). "The Complexity of Some Lattice Problems". Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 1838. pp. 1–32. doi:10.1007/10722028_1. ISBN 978-3-540-67695-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[21]

[22]

[24]

[25]

[26]

[27]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

v t 계산 경도 가정
수 이론	정수 인자화 피히딩 RSA 문제 강력한 RSA 이차잔류도 결정합성잔여도 잔존도가 더 높음
집단의 이론	이산 로그 디피-헬먼 결정 디피-헬먼 연산 디피-헬먼
페어링	외부 디피-헬먼 하위 그룹 숨기기 의사 결정 선형
선반	최단 벡터 문제(갭) 가장 가까운 벡터 문제(갭) 오류와 함께 학습 오류가 있는 링 학습 짧은 정수용액
비결정학	지수 시간 가설 유니크 게임 추측 심어진 클라이크 추측

Search

격자 문제

네임스페이스

더

목차

최단 벡터 문제(SVP)

경도 결과

유클리드 규범 알고리즘

갭SVP

가장 가까운 벡터 문제(CVP)

SVP와의 관계

경도 결과

구 디코딩

GapCVP

알려진 결과

최단 독립 벡터 문제(SIVP)

경계 거리 디코딩

커버 반지름 문제

최단기 문제

암호화에 사용

참고 항목

참조

추가 읽기