당신이 친구에게 비밀 메시지를 보내려고 하는데, 우체국을 믿을 수 없는 상황을 상상해 보세요. 당신은 편지를 상자에 넣고 잠갔지만, 우체국은 주소를 확인하기 위해 상자를 열어보거나 쌓거나 분류해야 합니다. 이때 상자 안의 내용물은 절대 보지 못한 채로 말이죠. 이것이 바로 **완전 동형 암호(Fully Homomorphic Encryption, FHE)**의 마법입니다. 이는 컴퓨터가 암호화된 상태 그대로인 데이터에 대해 계산을 수행할 수 있게 해줍니다. 이것은 마치 마법 같은 주방에서 재료들이 여전히 밀봉된 포장지에 담긴 채로 케이크를 굽는 것과 같습니다. 오븐은 작업을 수행하지만, 마지막에 상자를 열었을 때 신선한 케이크를 얻게 되며, 그동안 오븐은 재료가 무엇이었는지 전혀 알지 못합니다.

하지만 여기에는 문제가 하나 있습니다. 컴퓨터가 이 잠긴 데이터에 대해 수학 연산을 수행할 때마다, 렌즈에 먼지가 내려앉는 것처럼 아주 작은 "노이즈"나 정전기가 추가됩니다. 계산을 너무 많이 하면 노이즈가 너무 커져서 메시지가 엉망이 되고 읽을 수 없게 됩니다. 이를 해결하기 위해 과학자들은 **부트스트래핑(bootstrapping)**이라는 과정을 사용합니다. 이것은 일종의 마법 같은 리셋 버튼입니다. 컴퓨터는 노이즈가 섞인 잠긴 상자를 가져와서, 복잡한 기술을 사용하여 데이터의 먼지를 털어내고, 메시지를 다시 깨끗하고 새로운 상자에 담아 계산을 계속할 수 있도록 합니다. 문제는 이 청소 기술이 매우 느리고 무겁다는 점입니다. 마치 칫솔로 자동차를 세차하는 것과 같습니다. 이 작업은 엄청난 컴퓨팅 파워를 요구하며, 이로 인해 모든 과정이 느려지게 만듭니다. 실세계의 응용 사례들이 매우 답답하게 느껴지는 이유입니다.

여기서 Jean-Sébastien Coron과 Robin Köstler의 새로운 논문이 등장합니다. 그들은 이 "청소" 과정을 수행하는 영리하고 새로운 방법인 희소 단위근(Sparse Roots of Unity, SPRU) 부트스트래핑을 소개합니다. 데이터를 깨끗하게 만들기 위해 복잡한 곡선(예: 사인파)을 근사하려는 기존의 무거운 방식 대신, 그들은 데이터를 "단위근(roots of unity)"이라 불리는 숫자의 원형 위에 직접 매핑하는 방법을 찾아냈습니다. 이는 자동차를 칫솔로 문지르는 대신, 자동차를 거대한 회전 목마 위에 올려놓으면 회전하면서 자연스럽게 먼지가 닦여 나가는 것과 같습니다. 그들의 방법은 특히 적은 양의 데이터를 한 번에 처리할 때 훨씬 빠르고 가볍습니다. 그들은 이 새로운 접근 방식을 통해, 암호를 리셋하는 데 걸리는 시간을 표준 방식과 비교했을 때 최대 5배까지 단축할 수 있음을 보여주었으며, 이를 통해 비밀 컴퓨팅의 마법을 먼 미래의 꿈이 아닌 현실처럼 느끼게 만들었습니다.

옛날 방식: 무거운 짐을 든 사람

이 새로운 기술이 왜 특별한지 이해하려면, 기존의 방식이 어떻게 작동했는지 살펴봐야 합니다. 소수점 계산을 하는 데 가장 인기 있는 CKKS 암호 체계에서, 부트스트래핑 과정은 산의 모양을 추측하기 위해 그 위에 매끄러운 선을 그리는 것과 같았습니다. 컴퓨터는 "모듈러 감소(modular reduction)"를 근사하기 위해 복잡한 다항식(정교한 수학 공식)을 평가해야 했습니다. 모듈러 감소란 긴 숫자 선을 원형으로 말아 작은 상자에 맞게 만드는 과정을 의미합니다. 기존 방식은 이 말기 과정을 흉내 내기 위해 사인파(물결 모양의 선)를 그리려고 시도했습니다.

이 방식은 작동은 했지만, 매우 힘든 작업이었습니다. 이는 컴퓨터가 매우 큰 "링 차원(ring dimension, 수학적 놀이터의 크기)"을 사용해야 함을 의미했습니다. 이는 마치 무거운 배낭을 메고 마라톤을 하는 것과 같았습니다; 이는 모든 것을 느리게 만들었고, 리셋 후에 얼마나 많은 유용한 작업을 할 수 있는지를 제한했습니다. 저자들은 이 높은 "곱셈 깊이(multiplicative depth, 수학적 층의 수)"가 주요 병목 현상이었으며, 특히 한 번에 몇 개의 숫자만 처리해야 할 때 과정을 너무 느리게 만든다고 지적했습니다.

새로운 방식: 단위근의 회전 목마

저자들의 새로운 아이디어인 SPRU 부트스트래핑은 무거운 근사 과정을 통째로 건너뜀으로써 판도를 바꿉니다. 물결 모양의 선을 그려서 감싸는 과정을 흉내 내는 대신, 그들은 데이터를 직접 "단위근"에 **임베딩(embed)**할 수 있다는 사실을 깨달았습니다.

여기 간단한 비유가 있습니다. 기존 방식이 비밀 코드를 번역하기 위해 모든 글자마다 길고 복잡한 사전 항목을 쓰는 것과 같았다면, 새로운 방식은 비밀 코드가 특정 자물쇠에 딱 맞는 열쇠 세트라는 것을 깨닫는 것과 같습니다. 번역하는 대신, 그냥 열쇠를 돌리기만 하면 됩니다.

기술적으로 말하면, 그들은 가법군(additive group, 숫자가 더해지는 방식)을 복소수 체계의 원형에 있는 점들인 복소 단위근으로 직접 매핑합니다. CKKS 암호 체계는 기본적으로 이러한 복소수를 이해하기 때문에, 컴퓨터는 사인파를 근사할 필요 없이 직접 "청소" 작업을 수행할 수 있습니다. 이는 벽돌을 하나씩 쌓아 다리를 만드는 대신, 완벽하게 들어맞는 조립식 아치를 사용하는 것과 같습니다.

핵심 비결: 희소성과 패킹

논문은 단순히 새로운 맵을 제시하는 데 그치지 않고, 특히 적은 수의 데이터 슬롯(숫자 리스트의 일부)을 다룰 때 더 빠르게 만들기 위한 두 가지 영리한 최적화를 도입했습니다.

1. 비트 패킹(Packing the Bits): 과거에는 비밀 키에 1,000비트가 있다면 컴퓨터가 각 비트를 하나씩 처리해야 했습니다. 저자들은 이 비트들을 암호의 슬롯 안에 "패킹"하여, 마치 1,00러 개의 편지를 하나의 초효율적인 우편함에 담는 것처럼 처리할 수 있다는 것을 깨달았습니다. 이를 통해 필요한 무거운 계산 횟수를 방대한 양에서 로그(logarithmic) 수준의 적은 양으로 줄였습니다.
2. 희소 블록 트릭(The Sparse Block Trick): 그들은 또한 비밀 키가 특별한 구조를 가진다고 가정했습니다. 즉, 키가 무작위 비트가 아니라, 각 블록 내에서 단 하나의 비트만 "1"이고 나머지는 "0"인 블록으로 나뉘어 있다는 것입니다. 이는 마치 10개 그룹마다 단 하나의 스위치만 켜져 있는 전등 스위치 행과 같습니다. 이 "희소(sparse)" 구조를 사용함으로써, 그들은 많은 어려운 곱셈 단계를 단순한 덧셈 단계로 대체할 수 있었습니다. 이는 긴 숫자의 목록을 곱하는 것에서 몇 개의 숫자를 더하는 것으로 바꾸는 것과 같습니다. 이로 인해 계산의 "깊이"는 깊은 탑에서 낮은 계단 수준으로 더욱 낮아졌습니다.

결과: 마법의 속도를 높이다

저자들은 인기 있는 암호 소프트웨어 구축 도구인 OpenFHE 라이브러리를 사용하여 새로운 방법을 테스트했습니다. 그들은 SPRU 부트스트래핑을 기존의 무거운 방식과 비교했습니다.

결과는 특정 시나리오에서 매우 놀라웠습니다. 적은 수의 슬롯을 가진 사이퍼텍스트(ciphertext)를 부트스트래핑할 때, 그들의 새로운 방식은 최대 5배 더 빨랐습니다(지연 시간 5배 감소). 이는 매우 중요한데, "리셋 버튼"을 누른 후 컴퓨터가 유용한 작업을 다시 시작하기 위해 기다려야 하는 시간이 훨씬 짧아졌음을 의미하기 때문입니다.

하지만 논문은 이 방식이 모든 상황에 대한 마법의 해결책은 아니라는 점을 주의 깊게 언급합니다. 만약 엄청나게 많은 수의 슬롯(거대한 데이터 리스트)을 처리하려고 한다면, 기존 방식이 여전히 더 효율적일 수 있습니다. 그러나 우리가 다루는 데이터의 묶음이 작은 경우가 많은 실제 적용 사례에서, 이 새로운 접근 방식은 상당한 속도 향상을 제공합니다.

이것이 중요한 이유

이 연구의 아름다움은 단순히 숫자를 조금 조정하는 것이 아니라, 부트스트래핑 과정을 생각하는 방식 자체를 근본적으로 바꿨다는 데 있습니다. 무거운 다항식 근사를 버리고 암호 체계의 고유한 능력을 활용함으로써, 저자들은 우리가 완전 동형 암호를 훨씬 더 실용적으로 만들 수 있음을 보여주었습니다.

그들은 이러한 "단위근"과 스마트한 패킹 기술을 사용함으로써, 암호화된 데이터를 계속 사용할 수 있게 유지하는 데 필요한 시간과 컴퓨팅 파워를 크게 줄일 수 있음을 증명했습니다. 논문은 내부의 기술적 세부 사항과 수학적 원리에 집중하고 있지만, 핵심 메시지는 명확합니다. 복잡한 계산을 수행하면서도 속도가 느려지지 않게 하려는 꿈이 현실에 한 걸음 더 다가왔다는 것입니다. 저자들은 마법을 지속시키기 위한 더 가볍고 빠른 방법을 제공했으며, 이를 통해 당신의 개인 정보가 클라우드에서 처리되면서도 결코 노출되지 않고, 결과가 나올 때까지 영원히 기다릴 필요도 없는 미래를 상상할 수 있게 만들었습니다.