1994년 컴퓨터 과학자 Peter Shor는 발견 양자 컴퓨터가 발명되면 온라인에서 공유되는 정보를 보호하는 데 사용되는 인프라의 상당 부분이 파괴될 것입니다. 그 무서운 가능성 때문에 연구자들은 양자 해커의 손에 넘어가지 않도록 가능한 한 많은 정보를 저장하기 위해 새로운 "양자 이후" 암호화 체계를 만들기 위해 분주하게 움직였습니다.

올해 초 국립표준기술원(National Institute of Standards and Technology)은 공개 포스트 양자 암호화 표준을 찾기 위해 XNUMX명의 최종 후보에 올랐습니다. 그 중 XNUMX개는 "격자 암호화"를 사용합니다. 이는 격자에서 영감을 받은 방식으로, 공간에서 점의 규칙적인 배열입니다.

격자 암호화 및 기타 포스트 퀀텀 가능성은 중요한 면에서 현재 표준과 다릅니다. 그러나 그들은 모두 수학적 비대칭에 의존합니다. 많은 현재 암호화 시스템의 보안은 곱셈과 인수분해를 기반으로 합니다. 모든 컴퓨터는 두 숫자를 빠르게 곱할 수 있지만 암호학적으로 많은 수를 주요 구성 요소로 인수분해하는 데 수세기가 걸릴 수 있습니다. 이러한 비대칭성은 비밀을 인코딩하기는 쉽지만 디코딩하기 어렵게 만듭니다.

쇼어가 1994년 알고리즘에서 밝힌 것은 인수분해의 기이함이 양자 컴퓨터의 공격에 취약하다는 것이었습니다. "양자 컴퓨터가 할 수 있는 매우 구체적이고 특별한 일"이라고 말했습니다. 캐서린 스탠지, 콜로라도 대학 볼더의 수학자. 그래서 쇼어 이후 암호학자들은 새로운 직업을 갖게 되었습니다. 하기는 쉽지만 실행 취소가 거의 불가능한 새로운 수학 연산 세트를 찾는 것입니다.

격자 암호화는 지금까지 가장 성공적인 시도 중 하나입니다. 원래 1990년대에 개발되었으며 역 엔지니어링 포인트 합계의 어려움에 의존합니다.

격자 암호화를 설명하는 한 가지 방법은 다음과 같습니다. 친구에게 격자가 있다고 상상해 보십시오. 격자는 평면 전체에 걸쳐 규칙적이고 반복되는 패턴의 점 묶음일 뿐입니다. 당신의 친구는 당신이 이 점들 중 10개를 말해주기를 원합니다. 하지만 그는 어려워서 전체 격자를 그리지 않을 것입니다. 대신 그는 두 가지 점만 나열합니다. 첫 번째는 x-값 101 및 a y-값은 19이고 다른 하나는 좌표가 [235, 44]입니다.

다행히도 격자에서 새 점을 찾는 것은 쉽습니다. 격자에서 두 점을 더하거나 빼면 동일한 격자에서 세 번째 점을 얻을 수 있기 때문입니다. 따라서 친구가 제공한 점수를 더하거나 정수로 곱한 다음 더하거나 두 가지를 조합하기만 하면 됩니다. 이를 XNUMX가지 다른 방법으로 수행하면 친구의 질문에 답할 수 있습니다.

그러나 당신의 친구는 여전히 만족하지 않습니다. 그는 당신에게 같은 두 개의 시작점을 준 다음 같은 격자에서 [0, 0] 근처의 점을 찾을 수 있는지 묻습니다. 이 질문에 올바르게 답하려면 [101, 19]에 가까운 [235, 44]와 [0, 0]의 조합을 찾아야 합니다. 이 문제는 첫 번째 문제보다 훨씬 어렵습니다. 아마도 답을 찾기 위해 추측하고 확인하는 것으로 끝날 것입니다. 그 비대칭이 격자 암호화의 기초가 됩니다.

실제로 격자 암호화를 사용하여 정보를 공유하려면 다음을 수행합니다. 친구(더 좋은 친구)가 보안 메시지를 보내길 원한다고 상상해 보십시오. 숫자의 정사각형 그리드로 시작합니다. 두 개의 행과 두 개의 열이 있고 다음과 같이 보입니다.

이제 당신만 아는 개인 "키"가 떠오릅니다. 이 예에서 개인 키가 3과 −2라는 두 개의 비밀 번호라고 가정해 보겠습니다. 첫 번째 열의 숫자에 3을 곱하고 두 번째 열의 숫자에 -2를 곱합니다. 각 행의 결과를 더하여 두 개의 항목이 있는 세 번째 열을 얻습니다.

그리드 끝에 새 기둥을 붙입니다. 이 새로운 XNUMX열 그리드가 공개 키입니다. 자유롭게 공유하세요!

(실제 시나리오는 조금 더 복잡합니다. 해커가 개인 키를 해독하지 못하도록 하려면 최종 열에 약간의 임의 노이즈를 추가해야 합니다. 그러나 여기서는 단순성을 위해 해당 단계를 무시하겠습니다. )

이제 친구가 공개 키를 사용하여 메시지를 보냅니다. 그녀는 자신의 두 가지 비밀 번호인 2와 0을 생각합니다. 첫 번째 행의 숫자에 2를 곱하고 두 번째 행의 숫자에 0을 곱한 다음 각 열의 결과를 더하여 세 번째 행을 얻습니다.

이제 그녀는 새 행을 그리드 맨 아래에 연결하고 다시 사용자에게 보냅니다. (다시 말하지만 실제 시스템에서는 행에 약간의 노이즈를 추가해야 합니다.)

이제 메시지를 읽게 됩니다. 이렇게 하려면 친구의 마지막 행이 올바른지 확인합니다. 그녀의 행의 처음 두 항목에 자신의 개인 키를 적용합니다. 결과는 마지막 항목과 일치해야 합니다.

친구가 마지막 열에 잘못된 번호가 있는 행을 보내도록 선택할 수도 있습니다. 그녀는 이 숫자가 당신의 계산과 일치하지 않는다는 것을 알고 있습니다.

친구가 마지막 숫자가 정확한 행을 보내면 이를 0으로 해석합니다. 친구가 숫자가 잘못된 행을 보내면 1로 해석합니다. 따라서 행은 단일 비트: 0 또는 1.

외부 공격자는 귀하의 개인 키나 친구의 개인 키에 액세스할 수 없습니다. 이것이 없으면 공격자는 최종 숫자가 정확한지 여부를 알 수 없습니다.

실제로는 100비트보다 긴 메시지를 보내고 싶습니다. 따라서 예를 들어 100비트 메시지를 수신하려는 사람들은 하나가 아닌 100개의 새 열을 생성합니다. 그런 다음 메시지 발신자는 각 항목에 대해 0 또는 1을 인코딩하도록 마지막 XNUMX개 항목을 수정하여 단일 새 행을 생성합니다.

격자 암호화가 실제로 구현된다면 이 시나리오에서 다루지 않는 무수한 뉘앙스가 있을 것입니다. 예를 들어, 메시지를 엿보는 눈으로부터 진정으로 안전하게 하려면 매트릭스에 생각할 수 없는 수의 항목이 있어야 하므로 전체를 너무 다루기 어려워 사용할 가치가 없습니다. 이 문제를 해결하기 위해 연구원들은 매개변수의 수를 줄일 수 있는 유용한 대칭이 있는 행렬을 사용합니다. 그 외에도 문제 자체, 오류가 통합되는 방식 등에 적용할 수 있는 전체 조정 모음이 있습니다.

물론 Shor가 인수분해에 대해 했던 것처럼 누군가가 격자 암호화에서 치명적인 결함을 발견할 가능성은 항상 있습니다. 특정 암호화 체계가 가능한 공격에 직면하여 작동할 것이라는 보장은 없습니다. 암호화는 해독될 때까지 작동합니다. 사실 올 여름 초 하나의 유망한 양자 후 암호화 체계가 깨졌습니다. 양자 컴퓨터가 아닌 일반 노트북을 사용합니다. Stang에게 전체 프로젝트는 불편한 역설을 낳습니다. "암호화에 대해 놀라운 사실은 우리가 인간으로서 우리의 능력이 제한적이라는 확고한 믿음에 따라 인류를 위해 이 인프라를 구축했다는 것입니다."라고 그녀는 말했습니다. “너무 후진적이야.”

보정: 2022 년 11 월 9 일
이 기사의 원래 버전에서는 격자 암호에서 풀기 어려운 문제가 원점 근처의 격자에서 주어진 점을 찾는 것이라고 말했습니다. 사실 특정 지점을 찾는 것은 비교적 간단합니다. 어려운 문제는 원점 근처에 있는 미지의 점을 찾는 것입니다. 이 사실을 반영하여 기사를 변경했습니다.