Numerical and Algebraic Evaluation of Chebyshev Polynomial Representations for Ring-LWE-Related Polynomial Arithmetic

오늘날의 기계로는 해결할 수 없는 문제들을 해결할 수 있는 컴퓨터를 만들기 위한 경쟁 속에서, 과학자들은 격자 기반 암호(lattice-based cryptography)라고 불리는 수학의 한 분야로 눈을 돌리고 있습니다. 마치 무한히 뻗어 나가는 결정 구조와 같은, 다차원의 거대한 점들의 격자를 상상해 보십시오. 현대 디지털 통신의 보안은 이 격자의 점들이 약간 흐릿하거나 "노이즈(noise)"가 섞여 있을 때 특정 경로를 찾는 것의 어려움에 의존합니다. 이 노이즈는 실수가 아니라, 비밀을 보호하는 바로 그 핵심 요소입니다. 공격자가 경로를 추측하려고 시도할 때, 이 흐릿함은 어느 방향이 옳은지 알 수 없게 만듭니다. 이 방법은 매우 유망하여, 현재의 암호 체계를 깨뜨릴 수 있을 만큼 강력한 미래의 양자 컴퓨터로부터 데이터를 보호하기 위한 표준이 될 것으로 기대됩니다. 하지만 이러한 시스템이 현실 세계에서 작동하려면, 이 노이즈를 생성하고 읽어내는 수학적 연산이 믿을 수 없을 정도로 빠르고 정밀해야 합니다.

인도의 파룰 대학교(Parul University) 연구팀은 이러한 계산을 더 효율적으로 만들기 위한 구체적인 아이디어를 테스트하기 위해 연구에 착수했습니다. 그들은 수학적 형상을 기술하는 다른 방식, 구체적으로 체비쇼프 다항식(Chebyshev polynomials)이라 알려진 일련의 곡선을 사용하는 것이 시스템을 더 빠르거나 더 안전하게 만들 수 있는지 조사했습니다. 이 곡선들은 복잡한 형상을 단순한 숫자로 근사하는 데 탁월하기 때문에 공학 및 물리학 분야에서 오랜 역사를 가지고 있습니다. 연구진은 이 익숙한 언어로 전환하는 것이 시스템의 "노이즈"를 줄여, 잠재적으로 암호를 더 강력하게 만들거나 계산을 더 관리하기 쉽게 만들 수 있을지 궁금해했습니다. 답을 찾기 위해 그들은 단순히 추측하는 대신, 숫자가 한 언어에서 다른 언어로 번역될 때 정확히 어떻게 행동하는지 확인하기 위해 수백 번의 테스트를 수행하는 엄격하고 단계적인 디지털 실험실을 구축했습니다.

연구진은 먼저 명확한 규칙을 세우는 것으로 시작했습니다. 즉, 그들이 연구하는 기초적인 수학적 세계는 변하지 않을 것이라는 점입니다. 그들은 암호화 링(encryption ring)의 핵심 구조는 그대로 유지한 채, 그 안의 숫자들을 기술하는 좌표계만을 변경했습니다. 이것은 도시의 위치를 위도와 경도로 설명하는 것과 격자 형태의 거리와 도로를 사용하여 설명하는 것의 차이와 같습니다. 도시는 움직이지 않지만, 그 위치를 찾기 위해 적는 숫자는 매우 다르게 보일 수 있습니다. 초기 테스트에서 작은 차원(dimension)을 사용했을 때, 이 전환은 유망해 보였습니다. 숫자를 체비쇼프 체계로 변환했을 때, 원시 값들이 기존 체계보다 훨씬 작고 다루기 쉬워 보였습니다. 마치 노이즈가 길들여진 것처럼 보였으며, 이는 이 분야에서 큰 승리가 될 수 있는 결과였습니다.

하지만 연구진은 표면적인 모습에만 머무르는 실수를 범하지 않았습니다. 그들은 숫자를 쓰는 방식이 바뀐다고 해서 반드시 근본적인 보안이 변하는 것은 아니라는 점을 알고 있었습니다. 이를 테스트하기 위해, 그들은 체비쇼프 체계의 결과값을 다시 표준 체계로 번역하여 실제 암호학적 노이즈가 정말로 달라졌는지 확인했습니다. 번역을 수행했을 때, 환상은 사라졌습니다. 노이즈 수준은 정확히 동일했습니다. 겉으로 보이는 크기의 감소는 새로운 좌표계에 의한 부산물, 즉 보안의 실질적인 개선이 아닌 관점의 트릭일 뿐이었습니다. 이 발견은 매우 중요했습니다. 체비쇼프 표현 방식이 암호를 깨기 더 어렵게 만들거나 노이즈를 더 작게 만드는 마법 같은 효과를 내지 못한다는 것을 증명했기 때문입니다.

연구팀이 더 크고 복잡한 차원으로 실험을 확장하자, 보안보다는 계산의 안정성에 초점을 맞춘 다른 이야기가 나타났습니다. 그들은 시스템이 연속적인 많은 계산을 수행해야 하는 상황, 즉 실제 응용 분야에서 흔히 요구되는 상황을 테스트했습니다. 전통적인 체계에서는 숫자가 커지긴 하지만 예측 가능한 상태를 유지했습니다. 반면 체비쇼로 체계에서는 문제의 크기가 커짐에 따라 상황이 점점 더 불안정해졌습니다. 두 체계 사이를 전환하는 데 필요한 수학적 도구들이 미세한 반올림 오차에 너무 민감해져서 결과값이 표류하기 시작했습니다. 차원이 32일 때는 이미 민감도가 높았으나, 차원이 64에 도달하자 시스템은 완전히 불안정해졌습니다.

연구진은 완벽한 표준 역할을 하는 고정밀 참조값과 결과를 비교함으로써 이 불안정성을 측정했습니다. 차원이 64인 상태에서 8번의 곱셈 시퀀스를 실행했을 때, 서로 다른 계산 방식들은 판이하게 다른 결과를 냈습니다. 사전 계산된 곱셈 규칙(구조 상수)을 사용하는 방식은 약 739,000이라는 거대한 평균 상대 오차를 발생시켰습니다. 두 체계 간의 변환을 포함하는 방식은 10에 가까운 오차를 냈습니다. 이와 대조적으로, 단계별 평가 및 보간법(interpolation)을 사용하는 방식은 약 0.65의 평균 상대 오차를 기록했습니다. 이 최종 오차는 다른 방식들에 비하면 훨씬 작았지만, 여전히 수치적으로는 컸습니다. 즉, 컴퓨터가 충돌하거나 오류를 보고하지는 않았지만, 최종 숫자가 심하게 왜곡되었다는 것을 의미합니다. 이는 체비쇼프 숫자를 곱하는 데 사용되는 수학적 상수들이 엄청나게 커지면서, 계산 과정에서의 작은 오차들이 거대한 실수로 증폭되었기 때문에 발생했습니다.

연구는 또한 체비쇼프 체계 내에서 계산을 수행하는 다양한 방법들을 조사했습니다. 그들은 복잡한 곱셈 규칙을 미리 계산하는 방식을 포함한 한 방법이 높은 차원에서 처참하게 실패한다는 것을 발견했습니다. 반면, 단계별 평가 과정을 사용하는 다른 방법은 훨씬 더 잘 작동하며 오차를 비교적 작게 유지했습니다. 이는 만약 누 사람이 미래에 이 시스템을 사용하고자 한다면, 불안정성을 초래하는 직접적인 곱셈 규칙을 피하면서 계산 방법을 매우 신중하게 선택해야 함을 시사합니다.

결론적으로, 본 논문은 체비쇼프 다항식이 전통적인 체계와 동일한 수학적 대상들을 성공적으로 표현할 수는 있지만, 더 나은 보안이나 감소된 노이즈로 가는 지름길을 제공하지는 않는다고 결론짓습니다. 이 체계로 전환하는 것이 자동으로 암호를 더 강력하게 만들 것이라는 생각은 데이터에 의해 부정되었습니다. 대신, 이 연구는 중요한 수치적 과제를 강조합니다. 즉, 문제의 규모가 커질수록 이 체계로 전환하고 다시 돌아오는 과정이 위험할 정도로 불안정해진다는 것입니다. 이 연구 결과는 미래의 엔지니어들에게 주의 깊은 가이드 역할을 합니다. 수학적 표현 방식이 서류상으로는 우아해 보일 수 있지만, 특히 시스템을 확장할 때 실제 적용 단계에서는 심각한 오류의 원인이 될 수 있음을 보여줍니다. 이 연구는 새로운 암호 표준을 제안하는 것이 아니라, 미래의 체비쇼프 활용 시도가 희망적인 가정보다는 현실적인 기대치 위에 세워질 수 있도록, 어디에 함정이 있는지를 보여주는 명확하고 재현 가능한 지도를 제공합니다.