Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

본 논문은 Babbush 등이 제안한 영지식 증명 기반 결과와 비교하여 secp256k1에 대해 토폴리 게이트 수를 6.5%에서 10%까지 감소시키는 동시에 큐비트 사용량은 단 1.5%의 미미한 증가만을 초래함으로써, 소수체 위 타원 곡선에서의 최적화된 점 덧셈을 위한 상세한 양자 논리 회로 아키텍처를 제시한다.

핵심

당신이 매우 복잡한 자물쇠를 깨려고 노력하고 있다고 상상해 보세요. 수십 년 동안 수학자들은 특수한 종류의 "슈퍼 키"(양자 컴퓨터)가 이 자물락을 거의 즉시 열어 대부분의 인터넷 암호 체계를 무너뜨릴 수 있다는 사실을 알고 있었습니다. 이것이 바로 **쇼어 알고리 알고리즘(Shor's Algorithm)**입니다.

하지만 이 슈퍼 키를 만드는 것은 믿기 힘들 정도로 비용이 많이 들고 어렵습니다. 이를 위해서는 엄청난 양의 "마법 에너지"(양자 자원)가 필요합니다. 이 논문의 목표는 그보다 더 작고 효율적인 버전의 키를 만드는 방법을 알아내는 것입니다.

다음은 저자인 안드레 슈로텐로러(André Schrottenloher)가 달성한 성과를 일상적인 비유를 통해 설명한 내용입니다.

1. 거대한 문제: 무거운 배낭

쇼어 알고리즘을 실행하는 것을 산을 오르는 것에 비유해 보세요. 정상에 도달하기 위해(암호를 풀기 위해), 당신은 무거운 배낭(양자 비트 또는 "큐비트")을 메고 가야 합니다.

• 이전의 시도들: 다른 연구자들은 최근 그 어느 때보다 가벼운 매우 효율적인 배낭을 만들었습니다. 하지만 그들은 설계도를 비밀로 부쳤으며, 배낭이 가볍다는 것을 증명하기 위해 "마법의 기술"(영지식 증명)을 사용하여 직접 만드는 법을 보여주지 않았습니다.
• 이 논문의 목표: 저자는 비밀스러운 배낭만큼이나 가벼우면서도, 누구나 그 작업 내용을 확인할 수 있도록 설계도가 완전히 공개된 배낭을 만들고자 했습니다.

2. 핵심 과제: 곡선 위에 점 추가하기

이 알고리즘의 주요 작업은 타원 곡선(elliptic curve)에서 "점 덧셈(point addition)"이라는 특정 수학 연산을 수행하는 것입니다.

• 비유: 당신이 거대하고 구부러진 트램펄린 위를 걷고 있다고 상상해 보세요. 당신은 정해진 규칙에 따라 한 지점에서 다른 지점으로 점프해야 합니다. 이 점프를 완벽하게 수행하는 것은 어렵습니다.
• 병목 현상: 점프에서 가장 어려운 부분은 "제자리 곱셈(in-place multiplication)"이라고 불리는 특정 동작입니다. 이는 마치 여분의 연습장을 쓸 공간 없이, 오직 현재 서 있는 공간만을 사용하여 두 숫자를 곱해야 하는 것과 같습니다.

3. 해결책: "두 단계의 춤"

"연습장이 없는 문제"를 해결하기 위해, 저자는 영리한 두 단계 전략(확장 유클리드 알고리즘이라 불리는 방법에 기반함)을 사용했습니다.

• 1단계: 메모 테이프 (움직임 기록하기)
  수학 연산을 직접 수행하고 결과를 유지하는 대신, 컴퓨터는 먼저 자신이 수행했을 "움직임"을 긴 비트 테이프에 기록합니다. 아직 본격적인 힘든 작업을 하는 것이 아니라, 단지 지침을 적어두는 것입니다. 이 테이프는 놀라울 정도로 짧습니다.
• 2단계: 재구성 (움직임 재생하기)
  테이프가 작성되면, 컴퓨터는 이를 역순으로 재생합니다. 컴퓨터는 테이프에 적힌 지침을 사용하여 숫자들에 대해 실제 수학 연산을 수행합니다.
• 이것이 도움이 되는 이유: "계획하기"와 "실행하기"를 분리함으로써 컴퓨터는 엄청난 양의 공간을 절약합니다. 이는 요리를 시작하기 전에 재료를 한꺼움에 다 들고 있는 대신, 포스트잇에 레시피를 미리 적어두는 것과 같습니다.

4. 지름길: "의사 메르센(Pseudo-Mersenne)" 소수

이 논문은 secp256k1(비트코인에서 사용됨)이라는 특정 유형의 자물쇠에 집중합니다. 이 자물쇠는 특별한 모양을 가지고 있습니다.

• 비유: 일반적인 자물쇠가 완벽한 정사각형이라면, 비트코인 자물쇠는 한 모서리가 살짝 잘려 나간 정사각형과 같습니다.
• 최적화: 모서리가 잘려 있기 때문에, 이 자물쇠를 여는 데 필요한 수학 연산이 약간 더 쉬워집니다. 저자는 이 "잘려 나간 모서리"를 활용하여 불필요한 단계를 건너뛰는 특수한 도구들을 설계했습니다.
  • 일반적인 자물쇠(모든 소수)의 경우, 도구는 표준적이며 약간 더 무겁습니다.
  • 비트코인 자물쇠(secp256k1)의 경우, 도구는 모서리가 어디가 잘려 있는지 정확히 알고 있기 때문에 훨씬 더 간결하고 가볍습니다.

5. 결과: 약간 더 가벼운 배낭

저자는 이 새로운 배낭의 전체 "설계도"를 구축하고 테스트했습니다.

• 공간 (큐비트): 새로운 배낭은 이전의 비밀스러운 배낭보다 약 1.5% 더 무겁습니다. 이는 아주 작은 절충안입니다.
• 에너지 (게이트): 하지만 새로운 배낭은 실행하는 데 필요한 에너지(토폴리 게이트, Toffoli gates) 측면에서 6.5%에서 10% 더 효율적입니다.
• 신뢰성: 저자는 이 배낭이 이전의 비밀스러운 버전만큼 신뢰할 수 있다는 것을 증명했습니다. 무작위 입력을 넣었을 때, 이 배낭은 비밀 버전과 마찬가지로 거의 매번 성공적으로 작동합니다.

요약

단순히 말하자면, 이 논문은 다음과 같이 말합니다: "우리는 현대 암호를 해독하는 데 필요한 양자 컴퓨터를 만드는 방법을 알아냈습니다. 우리는 단순히 추측한 것이 아니라, 정확한 지침을 작성했습니다. 우리의 버전은 크기는 약간 더 크지만, 이전의 '비밀스러운' 버전보다 실행하는 데 에너지가 덜 들며, 일반적인 자물쇠와 비트코인에서 사용하는 특정 자물쇠 모두에 작동한다는 것을 증명했습니다."

저자는 이것이 논리적인 설계(이론적 청사진)라는 점을 강조합니다. 이것이 오늘 당장 만들 수 있다는 뜻은 아니지만, 양자 컴퓨터가 마침내 시도할 수 있을 만큼 강력해졌을 때 우리가 정확히 어느 정도의 "마법 에너지"가 필요할지를 알려줍니다.

기술 요약

문제 정의
본 논문은 현재의 공개키 암호 체계에 주요한 위협이 되는 타원 곡선 이산 로그(ECDL)를 계산하기 위한 쇼어 알고리즘(Shor's algorithm)의 자원 추정을 다룬다. 최근 Babbush 등의 연구(arXiv 2026)는 secp256k1 곡선에 대해 게이트 및 큐비트 수를 크게 줄이는 성과를 보여주었으나, 이들은 기저의 논리적 양자 회로를 공개하지 않고 결과를 검증하기 위해 영지식 증명(zero-knowledge proof)에 의존했다. 이러한 투명성의 결여는 재현성과 독립적인 검증을 저해한다. 본 논문의 목적은 Babbush 등의 효율성에 필적하는 효율성을 달면서도, 설계 원칙과 구현 세부 사항을 명시적으로 드러내는, 완전히 상세하고 재현 가능한 논리적 양자 회로 아키텍처를 제공하는 것이다.

방법론
저자들은 쇼어 알고리즘의 상위 수준 구조에서 시작하여 산술 구성 요소를 정교화하는 하향식(top-down) 접근 방식을 채택한다. 최적화의 핵심은 소수체(prime field) 상의 타원 곡선에 대한 윈도우 점 덧셈(windowed point addition) 구현에 있다.

1. 상위 수준 구조: 알고의는 큐비트 재사용(qubit recycling)을 포함한 준클래식컬 푸리에 변환(semiclassical Fourier transform)을 사용하여 점 곱셈 $|u, v\rangle|0\rangle \to |u, v\rangle|[u]P + [v]Q\rangle$을 일련의 윈도우 점 덧셈으로 축소한다. 점들은 아핀 좌표(affine coordinates)로 표현된다.
2. 모듈러 인플레이스 곱셈(Modular In-Place Multiplication): 점 덧셈에서 가장 비용이 많이 드는 연산은 인플레이스 모듈러 곱셈 $|x, y\rangle \to |x, yx \pmod q|$이다. 저자들은 확장 유클리드 알고리즘(EEA)을 두 개의 별도 단계로 분리하는 [14]의 기법을 응용하였다.
   • 유클리드 알고리즘 (순방향): 베주 항등식(Bézout coefficients)을 직접 계산하는 대신, 이 단계는 입력값 $(q, x)$를 처리하고 연산 시퀀스(스왑, 뺄셈, 2로 나누기)를 인코딩하는 "가비지(garbage)" 비트 벡터를 출력한다. 이는 공간 복잡도를 줄인다.
   • 베주 재구성 (역방향): 이 단계는 가비지 비트 벡터를 가져와 기록된 연산을 $(y, 0)$ 쌍에 적용하여 $|y, yx^{-1} \pmod q\rangle$를 계산한다. 이를 역순으로 실행하거나 특정 입력을 사용함으로써, 저자들은 인플레이스 곱셈과 역원을 동시에 달성한다.
3. 산술 최적화:
   • 공간 대 게이트 트레이드오프: 저자들은 알고리즘의 서로 다른 단계에서 사용 가능한 보조 큐비트(ancilla qubits)의 가용성에 따라 CDKM 가산기(낮은 공간 사용)와 Gidney 가산기(낮은 게이트 수, 높은 공간 사용) 사이를 전략적으로 전환한다.
   • 근사 산술(Approximate Arithmetic): 게이트 수를 줄이기 위해 저자들은 근사 산술 회로를 도입한다. 비교 연산은 전체 너비 비교 대신 최상위 비트(MSB)만을 사용하여 수행된다. 이는 실패 확률을 도입하지만, 무작위 입력에 대해 높은 확률로 성공하도록(구체적으로 실패 확률 $\le 2^{-13.3}$) 상수를 최적화하여 이를 관리한다.
   • 인스턴스 특화 최적화: 의사 메르센 소수($q = 2^{256} - 4294968273$)를 사용하는 secp256k1 곡선의 경우, 모듈러 감소 회로가 더욱 단순화된다. 저자들은 $2^u - f$ 형태의 작은 차이 $f$를 활용하여, 비용이 많이 드는 모듈러 뺄셈을 간단한 비트 조작 및 $f$의 덧셈으로 대체한다.

주요 기여

• 재현 가능한 회로 아키텍처: 본 논문은 불투명한 Babbish 등의 연구의 효율성 주장에 부합하는, secp256k1에 대한 최초의 완전히 명시된 논리적 양자 회로를 상세히 기술한다. 코드는 구현되어 있으며 Qarton 라이브러리를 통해 이용 가능하다.
• 최적화된 자원 수: 저자들은 두 가지 변형의 회로를 제시한다.
  • 공간 최적화 변형: 약 $4.36n + O(\sqrt{n})$ 큐비트를 사용한다.
  • 게이트 최적화 변형: 약 $4.36n + O(\sqrt{n})$ 큐비트를 사용하지만, 토폴리(Toffoli) 게이트 수를 줄인다.
• 일반 변형: secp256k1에 국한되지 않고 임의의 소수체에 유효한 버전의 회로도 제공되나, 의사 메르센 최적화의 부재로 인해 약간 더 높은 게이트 비용이 발생한다.
• 상세 비용 분석: 본 논문은 GCD 구성, 베주 재구성, 모듈러 산술 구성 요소를 구분하여 토폴리 게이트 비용에 대한 세밀한 분석을 제공한다.

결과
저자들은 secp256k1(여기서 $n=256$)에 대한 다음과 같은 자원 추정치를 보고한다.

• 큐비트 수:
  • 공간 최적화 변형: 1,192 큐비트 (Babbush 등의 1,175 큐비트와 비교).
  • 게이트 최적화 변형: 1,446 큐비트 (Babbush 등의 1,425 큐비트와 비교).
  • 이는 큐비트 수에서 약 1.5%의 미세한 증가를 나타낸다.
• 게이트 수 (Toffolis):
  • 공간 최적화 변형: $2^{21.19}$ (약 $2.3 \times 10^6$).
  • 게이트 최적화 변형: $2^{20.83}$ (약 $1.8 \times 10^6$).
  • 이는 Babbush 등의 연구와 비교하여 토폴리 게이트 수를 6.5%에서 10%까지 감소시킨 결과이다.
• 전체 알고리즘 비용: secp256k1에 대한 완전한 쇼어 알고리즘의 경우, 게이트 최적화 변형은 약 $2^{25.78}$ 개의 토폴리 게이트와 1,462개의 큐비트를 요구한다. 이는 약 $2^{27.57}$ 개의 토폴리 게이트와 두 배의 큐비트를 요구했던 Litinski(arXiv 2023)의 이전 연구보다 상당한 개선이다.

의의
본 논문은 주로 재현성과 투명성 측면에서 의의를 갖는다. 명시적인 논리적 회로 아키텍처를 제공함으로써, 저자들은 이전에는 영지식 증명 뒤에 숨겨져 있던 타원 곡선 암호를 해독하기 위한 자원 추정치를 암호학계가 검증할 수 있도록 한다. 이 연구는 EEA를 기록 단계와 재구성 단계로 분리하는 것과 근사 산술을 결 조합하는 구체적인 설계 선택을 통해, 유사하거나 혹은 더 개선된 효율성을 달성할 수 있음을 입증한다. 저자들은 자신들의 회로가 정확하지 않으며 무작위 입력에 대해 높은 성공 확률에 의존한다는 점을 언급하며, 이는 그들이 복제하고자 하는 연구와 공유되는 특성이다. 이 결과는 secp256k1을 깨뜨리는 비용이 이전의 일부 논리적 회로 모델에서 추정된 것보다 낮음을 확인시켜 주며, 양자 내성 암호로의 전환의 시급성을 강화한다.