🔢 mathematics

Spinel: A Post-Quantum Signature Scheme Based on $\mathrm{SL}_n(\mathbb{F}_p)$ Hashing

이 논문은 $\mathrm{SL}_n(\mathbb{F}_p)$ 확장 그래프 탐색의 난해함에 기반한 새로운 대수적 해시 함수를 SPHINCS+ 프레임워크에 결합하여, 양자 컴퓨터 공격에 내성을 가진 새로운 양자 내성 디지털 서명 방식인 'Spinel'을 제안하고 그 보안성과 실용성을 입증합니다.

원저자: Asmaa Cherkaoui, Faraz Heravi, Delaram Kahrobaei, Siamak F. Shahandashti

게시일 2026-02-12

📖 2 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Asmaa Cherkaoui, Faraz Heravi, Delaram Kahrobaei, Siamak F. Shahandashti

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

1. 배경: "기존의 자물쇠가 위험해지고 있어요!"

지금 우리가 인터넷에서 사용하는 디지털 서명(전자 서명)은 아주 복잡한 수학 문제라는 '자물쇠'로 잠겨 있습니다. 그런데 곧 등장할 양자 컴퓨터는 이 자물쇠를 순식간에 따버릴 수 있는 '만능 열쇠'를 가진 괴물과 같습니다.

그래서 과학자들은 양자 컴퓨터도 절대 풀 수 없는, 훨씬 더 복잡하고 새로운 방식의 자물쇠를 만들려고 노력 중입니다.

2. 핵심 아이디어: "미로 속의 술래잡기" (해시 함수)

이 논문에서 제안하는 Spinel의 핵심은 **'해시 함수'**라는 기술을 바꾸는 것입니다. 해시 함수는 어떤 데이터를 넣으면 아주 복잡한 결과물(지문 같은 것)을 내놓는 장치입니다.

기존의 방식이 "숫자를 아주 복잡하게 섞는 것"이었다면, Spinel은 **"거대한 미로 속에서 술래잡기를 하는 것"**과 같습니다.

미로(SLn(Fp) 그룹): 아주 거대하고 복잡한 미로가 있습니다. 이 미로는 수학적으로 설계되어 있어서, 한 번 들어가면 길을 찾기가 거의 불가능합니다.
술래잡기(Random Walk): 우리가 전달하려는 데이터(메시지)는 술래가 미로 안에서 움직이는 **'이동 경로'**가 됩니다. "왼쪽으로 한 칸, 오른쪽으로 두 칸..." 이런 식으로 움직이다가 최종적으로 도착한 위치가 바로 '디지털 지문(해시값)'이 됩니다.
왜 안전한가요? 양자 컴퓨터가 아무리 똑똑해도, 미로의 끝에 도착한 술래가 어떤 경로로 움직였는지 거꾸로 추적해서 알아내는 것은 불가능에 가깝기 때문입니다.

3. Spinel의 구조: "겹겹이 쌓은 성벽" (SPHINCS+ 결합)

Spinel은 단순히 미로만 만든 것이 아니라, 이 미로 기술을 **'SPHINCS+'**라는 아주 튼튼한 성벽 구조 안에 집어넣었습니다.

이 성벽은 **'계층형 구조'**로 되어 있습니다.

가장 안쪽에는 작은 성문(WOTS+)이 있고,
그 위에는 중간 성벽(FORS)이 있으며,
가장 바깥에는 거대한 성채(Hypertree)가 이 모든 것을 감싸고 있습니다.

마치 **"최첨단 미로 기술이 적용된 특수 인감도장을, 여러 겹의 금고 속에 넣어둔 것"**과 같습니다. 도장 하나가 노출되더라도 성벽이 워낙 두꺼워서 전체 시스템이 무너지지 않도록 설계되었습니다.

4. 연구 결과: "실제로 써보니 꽤 쓸만합니다!"

연구팀은 이 새로운 기술이 이론으로만 존재하는 게 아니라, 실제로도 잘 작동하는지 테스트했습니다.

무작위성 테스트: 술래가 미로를 돌아다닌 결과가 정말 예측 불가능한지(진짜 무작위인지) 검사했는데, 통과했습니다! (NIST 통계 테스트 통과)
성능 테스트: 새로운 방식이라 조금 느릴 수는 있지만, 컴퓨터로 계산해 보니 실제 서비스(예: 디지털 인증서 발급)에 충분히 사용할 수 있는 수준의 속도가 나왔습니다.

요약하자면!

Spinel은 **"양자 컴퓨터라는 만능 열쇠를 가진 도둑이 와도, 거대한 수학적 미로 속에서 길을 잃게 만들어 우리의 디지털 서명을 안전하게 지켜주는 차세대 보안 기술"**이라고 할 수 있습니다.

[기술 요약] Spinel: $SL_n(\mathbb{F}_p)$ 해싱 기반의 양자 내성 디지털 서명 스킴

1. 문제 배경 (Problem)

현재 널리 사용되는 디지털 서명 알고리즘(RSA, ECDSA 등)은 양자 컴퓨터의 등장으로 인해 보안이 무너질 위기에 처해 있습니다. 이에 대한 대안으로 해시 기반 서명(Hash-based Signature) 방식이 주목받고 있으며, 그중 **SPHINCS+**는 NIST의 양자 내성 암호 표준화 과정에서 선정된 대표적인 무상태(Stateless) 서명 스킴입니다.

그러나 SPHINCS+의 보안은 SHA-256이나 SHAKE-256과 같은 기존 해시 함수에 의존하고 있는데, 이들의 보안성은 수학적 증명보다는 **경험적/휴리스틱(Heuristic)**한 근거에 기반하고 있습니다. 본 논문은 "해시 함수의 보안성을 수학적으로 더 견고한 대수적 구조(Algebraic structure)로 대체하여 SPHINCS+의 이론적 토대를 강화할 수 있는가?"라는 질문에서 시작되었습니다.

2. 연구 방법론 (Methodology)

저자들은 SPHINCS+의 구조적 프레임워크(WOTS+, FORS, Hypertree)는 그대로 유지하되, 내부의 해시 함수만을 대수적 그룹 기반 해시 함수로 교체하는 'Spinel' 스킴을 제안합니다.

대수적 해시 함수 설계: Tillich–Zémor 패러다임을 기반으로, 특수 선형군 $SL_n(\mathbb{F}_p)$ $S L_{n} (F_{p})$ 상의 Cayley 그래프에서 발생하는 **비역행(Non-backtracking) 랜덤 워크(Random Walk)**를 이용합니다.
- 차원 설정: $SL_2$ 그룹에 대한 공격 사례를 피하기 위해 차원을 $n=4$ 로 고정했습니다.
- 파라미터: 소수 $p = 2^{31}-1$ 을 사용하며, 행렬의 각 요소를 32비트 정수로 직렬화하여 총 **512비트(64바이트)**의 고정된 출력 길이를 갖도록 설계했습니다.
입력 인코딩: 입력 바이트를 3진법(Ternary)으로 변환한 뒤, 이를 행렬 생성자( $A, B$ 및 그 역행렬)를 선택하는 지표로 사용하여 그룹 원소들을 곱해 나가는 방식입니다.
보안 모델링: 서명이 반복될수록 FORS(Few-time signature) 구성 요소의 비밀 정보가 일부 노출되는 '서명 노출(Signature exposure)' 현상을 Poisson 분포 모델을 통해 수학적으로 분석했습니다.

3. 주요 기여 (Key Contributions)

Spinel 스킴 제안: SPHINCS+의 검증된 구조에 $SL_n(\mathbb{F}_p)$ 기반의 대수적 해시를 통합한 새로운 양자 내성 서명 스킴을 설계했습니다.
해시 함수의 경험적 검증: 제안된 해시 함수가 NIST의 통계적 테스트 스위트(STS)의 15개 카테고리를 모두 통과함을 보여줌으로써, 출력값의 무작위성(Randomness)을 입증했습니다.
보안 저하 분석: 서명 횟수 증가에 따른 FORS 기반의 보안성 감소(Security degradation)를 모델링하여, 실무적인 파라미터 선택 가이드를 제공했습니다.
구현 및 벤치마크: C 언어로 직접 구현하여 연산 효율성, 서명 크기, 키 크기에 대한 상세한 성능 데이터를 제시했습니다.

4. 연구 결과 (Results)

통계적 무작위성: NIST STS 테스트 결과, Spinel 해시 함수는 통계적으로 매우 우수한 무작위성을 보였습니다.
성능 특성:
- 연산 비용: 서명(Signing) 작업이 검증(Verification) 작업보다 약 3자릿수(1,000배) 정도 더 많은 사이클을 소모합니다. 이는 인증서 발급과 같이 서명은 가끔 일어나고 검증은 빈번한 환경에 적합함을 의미합니다.
- 트레이드오프: 서명 크기를 줄이려는 설정(Small signature size)은 서명 생성 속도가 느려지고, 서명 속도를 높이려는 설정(High signing speed)은 서명 크기가 커지는 전형적인 암호학적 트레이드오프를 보여주었습니다.
- 비교: 기존 SPHINCS+(SHAKE-256)와 비교했을 때, 더 강력한 수학적 가정과 512비트 출력 사용으로 인해 서명 크기와 검증 시간은 다소 증가했습니다.

5. 의의 및 결론 (Significance)

본 논문은 단순히 기존 암호를 개선하는 것을 넘어, **"대수적 구조를 가진 해시 함수를 사용하여 해시 기반 서명 스킴의 보안 근거를 강화할 수 있다"**는 새로운 설계 방향을 제시했습니다.

Spinel은 비록 기존 방식보다 연산 비용은 높지만, 휴리스틱한 보안에 의존하는 대신 그룹 이론(Group Theory)의 난해함에 기반한 보안을 제공함으로써, 극도로 높은 보안 수준이 요구되는 양자 내성 암호 환경(예: 공공 인증서 체계)에서 실용적인 대안이 될 수 있음을 입증했습니다.