격자 기반 암호학: 포스트양자 보안의 수학

Source: Dev.to

NIST가 양자 컴퓨터에 대비해 인터넷을 보호하기 위한 알고리즘들을 선택했을 때, 승자들은 동일한 예상치 못한 장소에서 나왔습니다: 기하학입니다. 삼각형의 기하학이 아니라, 고차원 공간에 있는 무한히 많은 점들의 격자이며, 여기서 seemingly 무해해 보이는 질문 — “여기서 가장 가까운 격자점은 어디인가?” — 가 실제로는 끔찍하게 어렵다는 것이 밝혀집니다. 그 어려움은 안전한 통신의 새로운 기반이 됩니다.

오늘날 공개키 암호화는 두 문제에 기반합니다: 큰 수의 인수분해(RSA)와 이산 logaritm(타원 곡선 및 고전 디피‑헬만 시스템). 둘 다 일반적인 컴퓨터에게는 어렵고, 충분히 큰 양자 컴퓨터가 쇼어 알고리즘을 실행하면 쉬워집니다. 이것이 포스트양자 암호화가 존재하는 전체 이유이며, 격자는 해답을 제공하는 이유입니다.

먼저 간단히 시작합니다. 평면에 두 벡터를 취하고它们의 정수 배를 더해 도달할 수 있는 모든 점을 고려합니다: 첫 번째는 0, 두 번째는 3; 첫 번째는 -2, 두 번째는 1; 그리고 così sucesivamente. 이러한 점들의 집합은 격자 — 규칙적이고 무한히 반복되는 격자 — 로, 시작했을 때 사용한 두 벡터가 기준(basis)이 됩니다.

이제 그림을 확대합니다: 평면에 두 벡터 대신 수백 개 또는 수천 개의 벡터를 사용하고, 차원이 수백 개 또는 수천 개인 공간에 배치합니다. 격자는 여전히 “기준 벡터의 모든 정수 조합”이지만, 시각적 직관이 완전히 붕괴됩니다. 그리고 그 붕괴가 바로 암호화가 존재하는 위치입니다.

고차원 격자에 대한 두 질문은 2차원에서 보기에 사소해 보이지만 고차원으로 갈수록 불가능해집니다:

• Shortest Vector Problem (SVP): 격자 내 비영Vector(비영벡터) 중 가장 짧은 것을 찾기 — 원점과 가장 가까운 격자점.
• Closest Vector Problem (CVP): 공간의 임의의 점(격자에 반드시 포함될 필요는 없음)에 대해 가장 근접한 격자점을 찾기.

핵심적인 뉘앙스는 이겁니다: 어려움이 전적으로 당신이 받은 기준에 달려 있습니다. 동일한 격자는 “좋은” 기준으로 설명될 수 있으며(짧고 거의 직각인 벡터), 이는 문제를 쉽게 만들고, 또는 “나쁜” 기준으로 설명되어 어려움을 완전히 만들 수 있습니다 — 비록 둘 다 동일한 점들의 격자를 나타낸다 하더라도.

암호화는 좋은 기준을 개인키로 숨기고, 나쁜 기준으로 공개키를 발표합니다.

왜 양자 컴퓨터가 여기서 도움은 될 수 없는가: 쇼어 알고리즘은 숨겨진 주기 구조를 가진 문제를 위한 특수화된 도구이며, 인수분해와 이산 logaritm은 완벽히 그 모델에 맞습니다. 격자 문제는 그런 종류의 구조를 노출하지 않으며, 수십 년간의 노력에도 불구하고 양자 알고리즘이 modest(약간) 속도 향상만 제공할 뿐입니다. 이는 “양자 컴퓨터가 도울 수 없다”는 증명된 법칙이 아니라, “수년을 시도한 후 어떻게 될지 전혀 모르겠다”는 베팅입니다.

대부분의 현대 격자 기반 스키마는 직접 SVP를 사용하지 않습니다. 대신 Oded Regev이 2005년에 도입한 Learning With Errors(LWE)라는 문제를 사용하며, 이 문제는 최악의 경우 격자 문제와 동등한 어려움으로 입증됩니다.

이 아이디어는 간단하면서도 구체적입니다. 비밀 벡터 s를 가지고 많은 방정식의 시스템을 생각해 보세요: 정확한 형태라면, 1학년 선형대수 학생은 가우스 소거를 이용해 몇 분 안에 해결할 수 있습니다. 전체적인 트릭은 “approximate”(근사)라는 단어에 있습니다. 각 방정식에는 작은 무작위 오차가 추가됩니다. 이 노이즈는 충분히 크어Eliminate(제거)이 폭발하게 만들고, 방정식을 결합할수록 오류가 catastrophically 누적되지만, 비밀을 가진 사람에게는 여전히 깨끗하게 복호화될 수 있을 만큼 작습니다. “키를 가지고 디코딩 가능”과 “노이즈로 잠겨서 디코딩 불가능” 사이의 간극이 보안입니다.

평범한 LWE는 안전하지만 부피가 큽니다 — 키와 암호문은 큰 행렬을 차지합니다. 이를 사용하기 쉽게 만들기 위해 연구자들은 대수 구조를 추가했습니다. Ring-LWE는 벡터를 다항식으로 표현하여 전체 행렬 대신 하나의 다항식이 stand in(대신)할 수 있게 하고, 키 크기를 크게 줄입니다. Module-LWE는 중간 지점 — 몇 개의 다항식을 작은 행렬에 배치하는 형태 — 로 효율성보다 더 보수적인 보안 마진을 제공합니다. 이는 표준화된 대부분의 스키마가 선택한 변형입니다.

별도로, 1996년을 거슬러 올라가는 NTRU 가족은 다른 다항식 구성을 통해 유사한 격자 기반 보안을 얻었고, 실용적인 격자 암호체 중 가장 초기이기도 했습니다.

2024년 NIST는 첫 포스트양자 표준을 확정했으며, 격자가 라인업을 주도했습니다:

해시 기반 SLH-DSA의 포함은 의도적인 다양화 — 미래에 격자 가정에서 깨질 가능성이 있다면, 세계는 해시 기반 서명과 완전히 다른 수학을 바탕으로 한 서명 스킴을 여전히 가질 것입니다 (즉, 우리가 해시 기반 서명을 다루는 동일한 가족). Falcon에서 파생된 격자 기반 서명 스킴도 세트를 마무리할 것으로 기대됩니다.

격자 암호화는 무료가 아닙니다. 그 키와 암호문은 ECC를 대체하는 데 사용되는 타원 곡선 대비 상당히 더 큽니다 — 수천 바이트에서 수십 바이트까지. 이는 제한된 프로토콜, TLS 핸드쉐이크, 대역폭 민감한 시스템에 중요합니다. 계산 자체는 빠르며, RSA보다 빠른 경우가 많지만, 크기 팽창은 실제적이고 배포는 클래식 알고리즘과 포스트양자 알고리즘을 동시에 실행하는 하이브리드 스키마로 이루어져, 어느 한쪽이 유효한 한 안전합니다.

하이브리드의 이유는 양자 위협에 대한 의심이 아니라, 젊은 가정에 대한 겸손에서 비롯됩니다. 격자의 어려움은 잘 유지되어 왔지만, 인수분해가 겪어온 수십 년간의 공격만큼의 시험을 겪지는 못했습니다. 두 가지를 동시에 실행한다는 것은 어느 한 기반이 surprise(위협)받더라도 연결이 무너지지 않음을 의미합니다.

위협은 미래에만 있는 것이 아닙니다. “지금 기록하고 나중에 복호화”는 현재 진행 중인 전략입니다: 적대자는 오늘 기록한 암호문_traffic_를 훔치고, 강력한 양자 컴퓨터가 존재할 때 이를 복호화합니다. 의료 기록, 국가 비밀, 소스 코드, 장기 신원 등 수십 년간 기밀이 필요한 것이 classical cryptography만으로 보호된다면 이미 노출되어 있습니다. 이것이 양자 컴퓨터가 등장하기 전에 이 migration(전이)이 시작된 이유입니다.

격자는 우아함 때문에 이 라운드에서 승리한 것이 아니라 — 고차원 기하학은 드물게 아름답지 않다 — 하지만 그들은 수십 년 동안 클래식과 양자 공격 모두에 저항해 온 문제를 기반으로 한 효율적인 암호화라는 희귀한 것을 제공하기 때문입니다. 인터넷의 다음 신뢰 계층은 보이지 않는 격자를 탐색하는 단순한 고집스러운 어려움 위에 구축되고 있습니다.

원문은 havenmessenger.com에서 출판되었습니다.