The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

이 논문은 레벨 구조를 활용하여 SQIsign 서명 방식을 일반화하는 프레임워크를 제시하고, 이를 1 차원 및 2 차원 등형성 (isogeny) 에 적용하여 레벨 구조를 가진 초특이 타원곡선에 대한 새로운 명시적인 듀어링 대응 (Deuring correspondence) 과 제약된 노름 방정식 해결 방법을 제공합니다.

핵심

SQInstructor: 초전도 마법 지도와 새로운 도장 만들기 가이드

이 논문은 양자 컴퓨터 시대에 대비한 **'새로운 디지털 도장 (서명) 기술'**을 소개합니다. 기존에 가장 유망했던 기술인 'SQIsign'을 더 유연하고 강력하게 업그레이드한 **'SQInstructor'**라는 새로운 시스템을 제안한 것이죠.

이 복잡한 수학 이야기를 이해하기 쉽게, **'미로 찾기'**와 **'지도'**에 비유해서 설명해 드릴게요.

---

1. 배경: 왜 새로운 도장이 필요할까요?

미래의 양자 컴퓨터는 현재의 암호를 뚫어버릴 수 있습니다. 그래서 과학자들은 **'양자 컴퓨터도 뚫기 힘든 암호'**를 찾고 있습니다. 그중 하나가 **'타원곡선 (Isogeny)'**을 이용한 암호입니다.

기존의 'SQIsign'은 아주 작고 효율적인 도장을 만들지만, 도장을 찍는 과정이 매우 복잡하고 느렸습니다. 마치 **미로 (Supersingular Curve)**를 빠져나가는 데, 정해진 길 (KLPT 알고리즘) 로만 가야 해서 시간이 오래 걸리는 상황이었죠.

2. SQInstructor 의 핵심 아이디어: "레벨 구조 (Level Structure)"

이 논문은 SQIsign 을 업그레이드하기 위해 **'레벨 구조 (Level Structure)'**라는 개념을 도입했습니다.

• 비유: 미로의 '특수한 표지판'
  • 기존 SQIsign 은 미로에서 "출구로 가는 길"을 찾는 것이었습니다.
  • SQInstructor 는 미로에 **'특정 모양의 표지판 (레벨 구조)'**을 붙여놓습니다. 예를 들어, "이 표지판을 A 지점에서 B 지점으로 옮겨야 한다"는 규칙을 추가하는 거죠.
  • 이제 도장을 찍는 사람 (Prover) 은 단순히 출구로 가는 것뿐만 아니라, 이 표지판을 정확히 옮겨야만 도장이 유효해집니다.

이렇게 규칙을 조금 더 구체적으로 정하면, 도장을 만드는 과정이 훨씬 자유로워지고, 보안성을 증명하기도 쉬워집니다.

3. 두 가지 방식: 1 차원 vs 2 차원 미로

논리는 같지만, 이 새로운 시스템을 구현하는 두 가지 방법이 있습니다.

① 1 차원 방식 (기존 스타일 유지)

• 비유: 좁은 골목길만 걷는 방식.
• 특징: 아주 오래전부터 쓰여온 전통적인 방법입니다.
• 장점: 복잡한 수학 (Quaternion 대수) 을 이용해 도장을 만들 수 있어, '링 서명 (여러 사람이 함께 도장 찍기)' 같은 고급 기능에 적합합니다.
• 단점: 계산이 조금 느리고 도장 크기가 좀 큽니다.

② 2 차원 방식 (최신 스타일)

• 비유: 넓은 고속도로를 달리는 방식.
• 특징: 최근 발견된 '고차원 (Higher-dimensional)' 기술을 사용합니다.
• 장점: 압도적으로 빠릅니다. 기존 SQIsign 과 거의 비슷한 속도를 내면서도, 새로운 '레벨 구조' 규칙을 따릅니다.
• 현실: 이 방식이 현재 NIST(미국 표준 기관) 에서 표준으로 채택하려는 최신 SQIsign 과 가장 비슷합니다.

4. 이 기술이 가져오는 변화 (기여)

이 논문은 단순히 "새로운 도장"을 제안한 것을 넘어, 다음과 같은 중요한 일을 했습니다.

1. 수학적 연결고리 확장:

   • 기존에는 '타원곡선'과 '쿼터니온 (4 차원 수)' 사이의 연결고리 (Deuring 대응) 가 명확하지 않았습니다.
   • 연구진은 '레벨 구조'가 있는 곡선과 '레벨 구조'가 있는 수를 완벽하게 연결하는 새로운 수학적 지도를 그렸습니다. 마치 새로운 언어의 사전을 만든 것과 같습니다.

2. 실제 구현 (Proof of Concept):

   • 이론만 있는 게 아니라, 실제로 컴퓨터 코드로 구현해 보았습니다.
   • 특히 1 차원 방식에서는 기존에 없던 복잡한 수학 문제 (제약 조건이 있는 노름 방정식) 를 푸는 새로운 알고리즘을 개발했습니다.

3. 보안성 증명:

   • "이 도장은 위조할 수 없다"는 것을 수학적으로 엄격하게 증명했습니다. 기존 SQIsign 과 동등하거나 더 나은 보안 수준을 가집니다.

5. 성능 비교: 얼마나 빨라졌나요?

연구진은 SQIsign(기존) 과 SQInstructor(새로운) 를 비교했습니다.

• 속도: 2 차원 방식을 쓴 SQInstructor 는 기존 SQIsign 과 거의 똑같은 속도로 작동합니다. (약간 더 느리지만 무시할 수준)
• 크기: 도장 (서명) 크기는 아주 약간 커졌지만, 여전히 매우 작습니다.
• 의미: "새로운 규칙 (레벨 구조) 을 추가했음에도 불구하고, 기존 기술의 장점 (빠른 속도) 을 잃지 않았다"는 것이 큰 성과입니다.

6. 결론: 왜 이 논문이 중요할까요?

이 논문은 **"양자 컴퓨터 시대의 디지털 신분증 (서명)"**을 만드는 데 있어, 더 유연하고 더 안전한 새로운 설계도를 제시했습니다.

• SQIsign이 이미 유망한 후보라면, SQInstructor는 그 후보를 더 튼튼하게 다듬고, 다양한 응용 (링 서명 등) 에 쓸 수 있도록 확장한 **'프로 버전'**이라고 볼 수 있습니다.
• 특히, 복잡한 수학적 개념인 '레벨 구조'를 실제 암호 시스템에 어떻게 적용할지 구체적인 방법 (알고리즘) 까지 제시했다는 점이 가장 큰 의의입니다.

한 줄 요약:

"양자 컴퓨터 시대에도 뚫리지 않는 디지털 도장을 만들기 위해, 기존 기술에 '새로운 규칙 (레벨 구조)'을 추가해 더 유연하고 강력한 시스템을 만들었습니다."

기술 요약

SQInstructor: SQIsign 및 레벨 구조를 활용한 Deuring 대응성 가이드에 대한 기술적 요약

이 논문은 SQInstructor라는 새로운 디지털 서명 프레임워크를 제안하며, 이는 기존 양자 내성 암호화 표준화 후보인 SQIsign을 일반화한 것입니다. 저자들은 타원 곡선의 **레벨 구조 (Level Structures)**를 활용하여 Deuring 대응성 (Supersingular 타원 곡선과 Quaternions 대수 간의 대응) 을 확장하고, 이를 기반으로 1 차원 및 2 차원 등형사상 (isogeny) 을 사용하는 구체적인 프로토콜을 구현했습니다.

1. 문제 정의 (Problem)

• SQIsign 의 한계: SQIsign 은 매우 컴팩트한 서명을 제공하지만, 서명 생성 과정이 복잡하고 느리며, KLPT 알고리즘의 한계로 인해 EUF-CMA (선택 메시지 공격 하의 존재적 위조 방지) 보안 증명이 어렵다는 문제가 있었습니다.
• 레벨 구조의 활용 부재: 기존 프로토콜들 (SIKE, FESTA 등) 은 암묵적으로 레벨 구조 (torsion 부분군의 기저) 를 사용하지만, 이를 명시적으로 서명 프로토콜의 핵심 메커니즘으로 활용하여 Deuring 대응성을 일반화한 연구는 부족했습니다.
• 제약된 등형사상 문제: 기존 SQIsign 은 공개키와 도전 (challenge) 곡선 사이의 등형사상을 찾는 데 그쳤다면, 새로운 접근법은 특정 레벨 구조를 다른 레벨 구조로 매핑하는 등형사상을 찾는 문제로 확장해야 합니다.

2. 방법론 (Methodology)

저자들은 다음과 같은 단계로 새로운 프레임워크를 구축했습니다:

2.1 Deuring 대응성의 일반화

• 레벨 구조 정의: $N$-torsion 부분군의 기저를 특정 부분군 $\Gamma \subset GL_2(\mathbb{Z}/N)$에 의해 동치인 것으로 간주하는 $\Gamma$-레벨 구조를 정의했습니다. (예: Borel, Split Cartan, Scalar 구조)
• 확장된 대응성: 기존 Deuring 대응성을 "레벨 구조를 가진 초특이 (supersingular) 타원 곡선"과 "Quaternion 대수 내의 부분 순서 (suborder)" 사이의 대응으로 확장했습니다.
  • 곡선 $E$와 레벨 구조 $S$의 쌍 $(E, S)$는 Quaternion 대수 $B_{p,\infty}$의 부분 순서 $\mathcal{O}(E, S)$에 대응됩니다.
  • 등형사상 $\phi: (E, S) \to (E', S')$는 $\phi(S) \subseteq \langle S' \rangle$를 만족하는 조건으로 정의되며, 이는 Quaternion 대수에서의 특정 아이디얼 (ideal) 로 매핑됩니다.

2.2 SQInstructor 프로토콜

• 개요: SQIsign 의 시그마 프로토콜 (Sigma-protocol) 구조를 유지하되, 응답 (response) 이 특정 레벨 구조를 다른 레벨 구조로 매핑하도록 요구합니다.
• 구현 방식:
  1. 키 생성: 비밀 키는 $\mathcal{O}(E_0)$의 왼쪽 아이디얼, 공개키는 해당 아이디얼로 생성된 곡선과 레벨 구조의 쌍입니다.
  2. 도전 (Challenge): 검증자는 무작위 레벨 구조를 선택하여 증명자에게 보냅니다.
  3. 응답 (Response): 증명자는 공개키 곡선의 레벨 구조를 도전 곡선의 레벨 구조로 매핑하는 등형사상을 계산하여 제출합니다.
• 구현 옵션:
  • 1 차원 등형사상: KLPT 알고리즘을 일반화하여 제약된 노름 방정식 (constrained norm equations) 을 풂. (고급 원시자 구현에 유리)
  • 2 차원 등형사상: 고차원 등형사상 기법을 사용하여 효율성을 극대화함. (NIST 표준화 후보와 유사한 성능)

2.3 알고리즘적 기여

• 제약된 노름 방정식 해결: Quaternion 대수 $B_{p,\infty}$에서 레벨 구조 제약 조건을 만족하는 아이디얼을 찾는 ScalarSigningKLPT 및 BorelSigningKLPT 알고리즘을 제안했습니다.
• Explicit Deuring 대응: 큰 비-smooth 레벨 (large non-smooth levels) 에 대해서도 명시적인 대응성을 구성하는 방법을 제시했습니다.

3. 주요 기여 (Key Contributions)

1. Deuring 대응성의 일반화: 초특이 타원 곡선에 레벨 구조를 도입하여 Deuring 대응성을 확장하고, 이를 명시적으로 구성 가능한 알고리즘으로 제시했습니다.
2. SQInstructor 프레임워크: 레벨 구조의 종류와 등형사상 표현 방식 (1 차원 또는 고차원) 을 자유롭게 선택할 수 있는 범용 서명 프레임워크를 설계했습니다.
3. 알고리즘 개선:
   • 1 차원 구현을 위해 KLPT 알고리즘을 레벨 구조 제약 하에 수정하여 효율적으로 제약된 노름 방정식을 해결하는 방법을 개발했습니다.
   • 2 차원 구현을 위해 최신 고차원 등형사상 기법을 적용하여 최적화된 구현을 제공했습니다.
4. 보안 증명:
   • 2-특수 사운드니스 (2-special soundness): 레벨 구조를 기반으로 한 새로운 관계 ($R_{\Gamma}$-OneEnd) 에 대해 프로토콜의 사운드니스를 증명했습니다. 이는 Endomorphism Ring 문제와 동치입니다.
   • Zero-Knowledge: 1 차원 구현은 계산적 Zero-Knowledge를 가정하고, 2 차원 구현은 Isogeny Oracle 또는 Hint-assisted 모델을 사용하여 Zero-Knowledge 성질을 증명했습니다.
   • EUF-CMA 보안: Fiat-Shamir 변환을 적용하여 SQInstructor 서명 scheme 의 EUF-CMA 보안을 입증했습니다.

4. 결과 (Results)

• 성능 비교 (Table 3):
  • NIST I, III, V 보안 수준에서 SQInstructor (2 차원 구현) 와 기존 SQIsign 을 비교했습니다.
  • 키 생성 (KeyGen): 거의 유사한 성능을 보였습니다.
  • 서명 (Sign): SQInstructor 가 약간의 오버헤드 (약 10% 내외) 를 보였으나, 여전히 매우 효율적이었습니다.
  • 검증 (Verify): SQInstructor 가 2 차원 등형사상 체인 (2, 2-isogeny chain) 을 사용하므로 검증 시간이 약간 더 길었습니다 (예: NIST I 기준 6.0 vs 4.3 Mcycles).
  • 서명 크기: 레벨 구조 정보와 추가적인 매개변수로 인해 SQIsign 보다 약간 더 큰 서명 크기를 가졌습니다 (예: NIST I 기준 174 bytes vs 148 bytes).
• 구현: SageMath 기반의 Proof-of-Concept 구현을 통해 1 차원 및 Borel 레벨 구조에 대한 알고리즘의 유효성을 검증했습니다.

5. 의의 및 중요성 (Significance)

• 양자 내성 암호의 유연성 증대: SQInstructor 는 레벨 구조라는 새로운 수학적 도구를 활용하여 SQIsign 의 한계를 극복하고, 다양한 응용 분야 (링 서명, 카멜레온 해시 등) 에 적합한 변형을 가능하게 합니다.
• 고급 원시자 (Advanced Primitives) 지원: 1 차원 등형사상 기반 구현은 링 서명 (Ring Signatures) 및 카멜레온 해시 (Chameleon Hashes) 와 같은 고급 암호학적 원시자를 구현하는 데 필수적인 "시뮬레이션 가능성 (Simulatability)"을 제공합니다. 이는 고차원 기법만으로는 달성하기 어려운 부분입니다.
• 이론적 확장: Deuring 대응성을 단순히 곡선과 순서 간의 대응을 넘어, 구조화된 레벨 구조를 가진 곡선으로 확장함으로써, 등형사상 기반 암호학의 이론적 기반을 더욱 공고히 했습니다.
• 실용성: NIST 표준화 후보인 SQIsign 과 유사한 성능을 유지하면서, 더 넓은 범위의 암호학적 문제를 해결할 수 있는 프레임워크를 제공했습니다.

요약하자면, 이 논문은 레벨 구조를 핵심 도구로 사용하여 SQIsign을 일반화한 SQInstructor를 제안함으로써, 등형사상 기반 암호학의 이론적 깊이와 실용적 유연성을 동시에 향상시켰습니다.