제한된 디코딩 문제 기반 MPCitH 서명

기본 정보

• 논문 ID: 2510.11224
• 제목: MPCitH-based Signatures from Restricted Decoding Problems
• 저자: Michele Battagliola (Marche 폴리테크닉 대학교), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (뮌헨 공과대학교)
• 분류: cs.CR (암호학 및 보안), cs.IT (정보 이론), math.IT (정보 이론)
• 발표 시간: 2025년 10월 13일 (arXiv 사전인쇄본)
• 논문 링크: https://arxiv.org/abs/2510.11224

초록

본 논문은 제한된 디코딩 문제(E-SDP)를 Threshold-Computation-in-the-Head (TCitH) 및 VOLE-in-the-Head (VOLEitH) 프레임워크에 내장하였으며, 이 두 프레임워크는 MPC-in-the-Head (MPCitH) 패러다임의 최신 발전으로서 디지털 서명 방식의 성능을 크게 개선합니다. 저자들은 구조가 간단한 모델링 방법을 제안하여 경쟁력 있는 서명 크기를 달성했습니다. CROSS와 동일한 어려움 가정을 사용하여 제한된 디코딩 문제를 인스턴스화함으로써, NIST 제출 버전 대비 서명 크기를 2배 이상 감소시켰습니다. 또한 저자들은 삼진 전체 가중치 디코딩이 WAVE의 기본 어려움 가정과 밀접한 관련이 있음을 발견하였으며, 이 방법으로 얻은 서명 크기는 NIST 경쟁에서 가장 작은 MPCitH 후보 방식과 필적할 수 있습니다.

연구 배경 및 동기

문제 배경

1. 양자 후 암호학 표준화 필요성: NIST는 CRYSTALS-Dilithium, FALCON 및 SPHINCS+를 표준화한 후, 2022년 9월에 추가 디지털 서명 방식 모집을 시작하여 양자 후 서명 표준 조합의 다양화를 목표로 합니다.
2. MPCitH 패러다임의 발전: 2007년 Ishai 등이 제안한 이래, MPCitH 기술은 양자 후 디지털 서명의 환경을 재편했습니다. TCitH 및 VOLEitH는 MPCitH의 최신 특화로서 이전 구성에 비해 현저한 성능 개선을 제공합니다.
3. 암호학에서의 부호 이론 응용: 부호 이론 기반의 어려움 문제(예: 해밍 거리 및 순위 거리 디코딩 문제)는 효율적인 양자 후 서명 구축을 위한 이론적 기초를 제공합니다.

연구 동기

1. 성능 최적화 필요성: 기존 CROSS 서명 방식은 제한된 디코딩 문제를 기반으로 하지만 상대적으로 단순한 CVE 프로토콜을 사용하여 서명 크기 측면에서 최적화 여지가 있습니다.
2. 프레임워크 통합: 제한된 디코딩 문제를 고급 TCitH/VOLEitH 프레임워크에 통합하여 이러한 프레임워크의 성능 이점을 충분히 활용합니다.
3. 경쟁력 향상: 보안성을 유지하면서 서명 크기를 크게 감소시켜 NIST 경쟁에서의 경쟁력을 높입니다.

핵심 기여

1. E-SDP의 다항식 모델링 방법 제안: 제한된 종합 디코딩 문제를 TCitH 및 VOLEitH 프레임워크에 내장하는 구조가 간단하지만 효과적인 다항식 관계를 설계했습니다.
2. CROSS 유형 서명 크기의 현저한 감소: 동일한 디코딩 문제에 대해 NIST 제출 CROSS 방식 대비 서명 크기를 50% 이상 감소(12.4kB에서 5.5kB로)시켰습니다.
3. 삼진 전체 가중치 디코딩의 응용 잠재력 발견: WAVE와 관련된 삼진 전체 가중치 디코딩이 제한된 디코딩 문제임을 증명하고 최소 MPCitH 후보 방식과 동등한 서명 크기(3.1kB)를 달성했습니다.
4. 완전한 매개변수화 방식 제공: NIST 보안 등급 1, 3, 5에 대한 구체적인 매개변수 선택 및 성능 분석을 제시했습니다.

방법 상세 설명

작업 정의

연구 목표는 제한된 종합 디코딩 문제(E-SDP)를 다항식 관계로 표현하여 TCitH 및 VOLEitH 프레임워크에서 디지털 서명 방식을 구축할 수 있도록 하는 것입니다.

E-SDP 정의: 제한 집합 E ⊂ F, 검사 행렬 H ∈ F^(r×n) 및 종합 s ∈ F^r이 주어졌을 때, eH^T = s를 만족하는 e ∈ E^n을 찾습니다.

핵심 모델링 방법

1. 다항식 제약 구성

시스템 형태의 검사 행렬 H = (A, I_r)에 대해, 여기서 A ∈ F^(r×k), I_r은 단위 행렬입니다:

• 증명 벡터: w ∈ F^k (부분 오류 벡터)
• 확장 오류 벡터: e = (w, s - wA^T)
• 제한 다항식: f_E(x) = ∏_{e∈E}(x - e)

다항식 관계 시스템:

F(x) = (f_1, ..., f_n) ∈ F[x_1, ..., x_k]^n

여기서:

• f_i(x) = f_E(x_i) for i ∈ k
• f_{k+i}(x) = f_E(s_i - ⟨a_i, x⟩) for i ∈ r

2. 차수 분석

명제 1: 이 다항식 관계는 차수 z = |E|의 E-SDP 모델링을 제공하며, w ∈ F^k가 F(w) = 0을 만족하면 오류 벡터 e = (w, s - wA^T)는 E-SDP 인스턴스(H, s)를 해결합니다.

구체적 인스턴스화

CROSS-SDP

• 제한 집합: E = {2^i | i ∈ 7} ⊆ F_{127}
• 매개변수: |E| = 7, p = 127
• 보안성: 7,15의 상세 분석 기반

Ternary-SDP

• 제한 집합: E = {1, 2} ⊆ F_3
• 매개변수: |E| = 2, p = 3
• 복잡도: O(2^{0.247·n}) 연산 (다항식 인수 내)

실험 설정

매개변수 선택 전략

보안 요구사항 및 성능 최적화 목표에 따라 다음 핵심 매개변수를 선택합니다:

1. TCitH 프레임워크 매개변수:
   • τ: 병렬 반복 횟수
   • N: 평가 영역 크기
   • μ: 확장 영역 차수 K : F
   • η: 배치 처리 매개변수
2. VOLEitH 프레임워크 매개변수:
   • ρ: 확장 영역 매개변수
   • B: 일관성 검사 매개변수
   • T_open: VC 방식 매개변수

보안성 제약

다음 보안성 요구사항을 만족합니다:

• TCitH: N ≤ p^μ, p^{μ·η} ≥ 2^λ, (N/d)^τ ≥ 2^{λ-w}
• VOLEitH: N^τ/d ≥ 2^{λ-w}, p^ρ ≥ 2^λ

평가 지표

주로 서명 크기를 평가하며, 세 가지 구성 요소를 포함합니다:

• |σ_sym|: VC 방식 관련
• |σ_w|: 증명 관련
• |σ_F|: OWF 관련

실험 결과

주요 결과

TCitH 프레임워크 성능

VOLEitH 프레임워크 성능

NIST 후보 방식과의 비교

주요 발견

1. 현저한 크기 감소: CROSS-SDP는 원본 CROSS 대비 64.5%의 서명 크기 감소
2. 프레임워크 선택의 영향: 높은 차수 문제의 경우 VOLEitH가 TCitH보다 더 유리
3. 경쟁력: Ternary-SDP는 최고 성능의 MPCitH 후보 방식과 동등한 성능 달성

관련 연구

MPCitH 패러다임 발전

1. 원본 MPCitH 23: 2007년 제안, 안전 다자간 계산과 Fiat-Shamir 변환 결합
2. TCitH 프레임워크 21: ℓ-out-of-n 임계값 비밀 공유의 인스턴스화 사용
3. VOLEitH 프레임워크 13: VOLE 기반 영지식 프로토콜을 공개 검증 가능 프로토콜로 컴파일

부호 이론 응용

1. 해밍 거리 디코딩: SDitH 등 방식의 기초
2. 순위 거리 디코딩: RYDE, Mirath 등 방식
3. 치환 핵 문제: PERK 방식의 어려움 가정

제한된 디코딩 문제

1. CROSS 방식 6: 단순 CVE 프로토콜을 사용하는 제한된 디코딩
2. WAVE 방식 10,19: 삼진 고가중치 종합 디코딩 기반
3. 이론 분석 8,9: E-SDP의 NP 완전성 및 구체적 어려움

결론 및 논의

주요 결론

1. 성공적인 프레임워크 통합: 제한된 디코딩 문제가 고급 MPCitH 프레임워크에 효과적으로 통합될 수 있음을 증명
2. 현저한 성능 향상: 단순 CVE 프로토콜을 TCitH/VOLEitH로 대체하여 서명 크기를 대폭 감소
3. 광범위한 적용성: 이 방법은 다양한 유형의 제한된 디코딩 문제에 적용 가능

제한사항

1. 복잡성 증가: 원본 CROSS의 단순 CVE 프로토콜에 비해 TCitH/VOLEitH 구성이 현저히 더 복잡
2. 계산 오버헤드: 서명 크기 감소에도 불구하고 서명 생성 및 검증의 계산 복잡도 증가 가능
3. 매개변수 의존성: 성능은 구체적인 매개변수 선택 및 최적화 전략에 크게 의존

향후 방향

1. 추가 최적화: 더 효율적인 다항식 모델링 방법 탐색
2. 기타 제한 문제: 이 방법을 다른 유형의 제한된 디코딩 문제로 확장
3. 구현 최적화: 계산 오버헤드를 줄이기 위한 효율적인 구현 개발

심층 평가

장점

1. 기술 혁신: 간결하면서도 효과적인 제한된 디코딩 문제의 다항식 모델링 방법 제안
2. 현저한 개선: 동일한 보안성을 유지하면서 서명 크기를 대폭 감소
3. 이론적 기여: 제한된 디코딩 문제와 고급 MPCitH 프레임워크 간의 다리 구축
4. 실용적 가치: 양자 후 서명 방식 설계에 새로운 설계 사상 제공

부족한 점

1. 복잡성 트레이드오프: 구성 복잡성을 대가로 서명 크기 감소 달성
2. 제한된 새로움: 주로 기존 기술의 영리한 조합으로 이론적 혁신이 상대적으로 제한적
3. 구현 세부사항 부족: 상세한 성능 분석 및 실제 구현 비교 부재

영향력

1. 학술적 가치: MPCitH 프레임워크 응용에 새로운 사례 연구 제공
2. 실용적 의미: 향후 NIST 표준화 과정에서 방식 선택에 영향 가능
3. 방법론 기여: 다른 어려움 문제의 유사한 모델링을 위한 참고 제공

적용 시나리오

1. 자원 제약 환경: 서명 크기에 민감한 응용 시나리오
2. 양자 후 암호 배포: 다양한 보안 가정이 필요한 시스템
3. 연구 프로토타입: 추가 최적화 및 개선의 기초

참고문헌

논문은 24개의 중요한 참고문헌을 인용하였으며, MPCitH 프레임워크 발전, 부호 이론 응용 및 관련 NIST 후보 방식을 포함하여 연구에 견고한 이론적 기초를 제공합니다.