격자 기반 암호에 대해 설명드릴게요.
격자 기반 암호는 다차원 공간에서 격자점들 사이의 최단거리를 찾는 문제를 활용한 건데요
이게 차원이 높아질수록 계산량이 기하급수적으로 늘어나서 양자컴퓨터도 힘들어한답니다
쉽게 설명하면 3차원 이상의 공간에서 가장 가까운 두 점을 찾는 문제인데
차원이 수백 수천개로 늘어나면 양자컴퓨터로도 현실적인 시간 안에 풀기 어려워요
기존 RSA 암호는 큰 수의 소인수분해를 기반으로 하는데 이건 양자컴퓨터가 쉽게 풀 수 있구요
그래서 요즘은 격자 문제를 활용한 새로운 암호들이 개발되고 있는거죠
수학적으로는 SVP나 CVP같은 문제들이 사용되는데
이런 문제들은 NP-hard 문제군에 속해서 양자컴퓨터로도 쉽게 해결하기 어렵답니다..