💻 computer science

Fresh Masking Makes NTT Pipelines Composable: Machine-Checked Proofs for Arithmetic Masking in PQC Hardware

이 논문은 Lean 4 를 활용하여 ML-KEM 및 ML-DSA 와 같은 양자내성 암호 가속기의 파이프라인 수준 보안을 보장하는 산술 마스킹의 구성 가능성을 수학적으로 증명하고, Adams Bridge 가속기 등의 설계 결함을 규명했습니다.

원저자: Ray Iskander, Khaled Kirah

게시일 2026-04-23

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Ray Iskander, Khaled Kirah

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

이 논문은 **"양자 컴퓨터 시대를 대비한 새로운 암호 기술 (PQC)"**을 만드는 하드웨어 설계자들이, 해커들의 공격을 막기 위해 사용하는 '가상 가면 (마스크)' 기술에 대해 이야기합니다.

특히, 이 기술이 여러 단계를 거쳐 연결될 때 (파이프라인) 정말로 안전한지, 수학적으로 100% 증명된 사실을 보여줍니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

🎭 1. 배경: 왜 '가상 가면'이 필요한가요?

미래의 양자 컴퓨터는 현재의 암호를 쉽게 뚫을 수 있습니다. 그래서 새로운 암호 (ML-KEM 등) 가 개발되었는데, 이를 하드웨어로 만들 때 전력 소비나 전자기파를 분석하면 비밀 키가 유출될 수 있습니다.

이를 막기 위해 설계자들은 **'마스크 (가상 가면)'**를 씌웁니다.

비유: 비밀 숫자 5를 처리할 때, 그대로 쓰지 않고 5 + 3 = 8과 3이라는 두 개의 조각으로 나누어 처리합니다. 해커가 한 조각만 훔쳐봐도 3만 알 수 있을 뿐, 원래 숫자 5는 알 수 없습니다.

이 논문은 이 '가면'을 여러 단계로 이어붙일 때 (NTT 파이프라인), **각 단계마다 새로운 가면 (Fresh Masking)**을 씌워야만 전체가 안전하다는 것을 수학적으로 증명했습니다.

🧩 2. 핵심 발견 1: "가면이 없어도 괜찮다?"라는 착각 (Butterfly Trap)

하드웨어 엔지니어들은 보통 "각 단계가 안전하면 전체도 안전할 거야"라고 생각합니다. 하지만 이 논문은 **"아니요, 그건 함정입니다!"**라고 경고합니다.

비유: 어떤 기계가 두 개의 조각을 섞어서 새로운 조각을 만듭니다. 엔지니어는 "각 조각이 섞여도 원래 숫자가 안 보이게 하려면, 섞이는 순간마다 새로운 가면을 씌워야 해"라고 생각했습니다.
실제 상황: 하지만 이 논문의 수학 증명에 따르면, 각 단계마다 새로운 가면을 씌우지 않으면 해커가 중간에 훔쳐본 조각을 통해 원래 숫자를 추측할 수 있게 됩니다. 마치 가면이 낡아서 구멍이 난 것과 같습니다.

🚨 중요한 경고 (Pointwise VI Trap):
엔지니어들이 흔히 "숫자가 변하지 않으면 안전하다"고 생각하는데, 이 논문에 따르면 **"숫자가 변하지 않아도 해커에게 정보가 새어 나갈 수 있다"**는 것을 증명했습니다. 마치 가면을 쓴 사람이 얼굴을 움직이지 않아도, 가면을 쓴 채로 움직이는 방식에 따라 해커가 얼굴을 유추할 수 있는 것과 같습니다.

🏗️ 3. 핵심 발견 2: "매번 새 가면"이 답이다 (Fresh Masking)

이 논문이 제시한 해결책은 매우 단순하지만 강력합니다.

비유: 공장이 여러 공정을 거칩니다.
- 틀린 방법: 첫 공정에서 가면을 씌우고, 그다음 공정에서는 그 가면을 그대로 쓰고, 세 번째 공정에서도 그대로 씁니다. (이건 가면이 낡아서 구멍이 나기 쉽습니다.)
- 올바른 방법 (이 논문의 주장): 매 공정마다 완전히 새로운 가면을 씌웁니다. 첫 공정에서 쓴 가면은 버리고, 두 번째 공정에서는 완전히 다른 새 가면을 씌웁니다.

이 논문의 수학 증명 (Lean 4 라는 컴퓨터 프로그램으로 검증됨) 은 **"각 단계마다 새로운 가면을 씌우면, 해커는 어떤 단계에서 훔쳐봐도 절대 원래 숫자를 알 수 없다"**는 것을 100% 증명했습니다.

🚫 4. 실제 사례: '애덤스 브릿지'의 실패

이 논문은 실제 존재하는 하드웨어 설계인 **'애덤스 브릿지 (Adams Bridge)'**를 분석했습니다.

상황: 이 설계는 첫 단계에서만 가면을 씌우고, 그다음 단계들은 가면 없이 진행했습니다.
결과: 이 논문은 "왜 이 설계가 해커에게 취약한지" 그 근본 원인을 찾아냈습니다. "매 단계마다 새로운 가면을 씌우는 규칙 (Fresh Masking Design Principle)"을 어겼기 때문에, 수학적으로 보장이 안 된다는 것입니다.
비유: 금고 문은 첫 번째 잠금장치만 걸고, 두 번째와 세 번째 문은 열려 있는 것과 같습니다. 비록 첫 문이 튼튼해도, 그다음 문이 열려 있으면 금고는 안전하지 않습니다.

🛡️ 5. 왜 이 논문이 중요한가요? (컴퓨터가 증명한 사실)

이 논문은 단순히 "우리가 이렇게 생각해요"가 아니라, 컴퓨터 (Lean 4) 가 모든 경우의 수를 계산해서 "절대 틀릴 수 없다"고 증명했습니다.

수학적 증명: "어떤 숫자 (q) 를 쓰든, 어떤 단계 (k) 를 거치든, 매번 새 가면을 씌우면 해커는 100% 실패한다"는 것을 증명했습니다.
실용성: 이제 하드웨어 설계자들은 이 논문을 참고하여, "우리는 이 증명된 규칙을 따랐으니 안전합니다"라고 인증 기관 (FIPS) 에 제출할 수 있습니다.

💡 요약

문제: 양자 암호 하드웨어를 만들 때, 해커가 정보를 훔쳐보지 못하게 '가면'을 씌우는데, 여러 단계를 거치면 안전성이 깨질 수 있습니다.
오해: "한 번 가면 씌우면 끝"이라고 생각하면 안 됩니다.
해결: 각 단계마다 완전히 새로운 가면을 씌워야 합니다.
증명: 이 논문은 컴퓨터로 이를 수학적으로 100% 증명했고, 기존에 잘못된 설계 (애덤스 브릿지) 가 왜 실패했는지 그 이유를 밝혀냈습니다.

이 논문은 **"안전한 암호 하드웨어를 만들기 위한 가장 기초적이지만 가장 중요한 규칙"**을 수학적으로 확립한 것입니다.

이 논문은 양자내성암호 (PQC) 하드웨어, 특히 ML-KEM(FIPS 203) 과 ML-DSA(FIPS 204) 가속기에 사용되는 수정 정수 변환 (NTT, Number Theoretic Transform) 파이프라인의 산술 마스킹 (Arithmetic Masking) 보안성을 검증하기 위해 작성된 연구입니다. 저자들은 Lean 4 와 Mathlib 라이브러리를 사용하여 파이프라인 수준의 보안을 보장하는 세 가지 기계 검증 (Machine-Checked) 결과를 제시하며, 기존 프레임워크의 한계를 극복하고 하드웨어 설계자에게 명확한 설계 원칙을 제공합니다.

다음은 이 논문의 상세한 기술 요약입니다.

1. 문제 정의 (Problem)

배경: PQC 가속기는 $Z_q$ (유한체) 상에서 Cooley-Tukey 버터플라이 (Butterfly) 스테이지로 구성된 파이프라인 형태의 NTT 를 사용합니다. 각 스테이지는 1 차 산술 마스킹으로 보호되어야 합니다.
간극 (Gap): 기존 보안 프레임워크 (ISW, t-SNI, PINI, DOM 등) 는 주로 $GF(2) $(부울 회로) 에 대한 마스킹에 초점을 맞추어 기계 검증되었습니다.$ Z_q$ 상의 산술 마스킹, 특히 NTT 버터플라이 구조에 대한 파이프라인 수준의 구성 (Composition) 보안성에 대한 기계 검증된 증명은 존재하지 않았습니다.
설계자의 오해: 설계자들은 각 스테이지가 개별적으로 안전하면 파이프라인 전체도 안전하다고 직관적으로 생각하지만, 이는 증명되지 않았습니다. 또한, "점별 값 독립성 (Pointwise Value-Independence)"을 보안 속성으로 잘못 판단하여 안전하지 않은 설계를 "불안전"하다고 오해하거나, 반대로 실제 취약점을 놓치는 함정이 존재합니다.
실제 사례: Adams Bridge (CHIPS Alliance Caliptra 의 ML-DSA/ML-KEM 구현체) 는 스테이지 간에 새로운 마스킹 (Fresh Masking) 을 적용하지 않아 구조적으로 불안전한 것으로 알려져 있었으나, 그 수학적/아키텍처적 근본 원인에 대한 공식적 증명은 부족했습니다.

2. 방법론 (Methodology)

형식 검증 도구: Lean 4 증명 보조기 (Proof Assistant) 와 Mathlib 라이브러리를 사용했습니다. 모든 증명은 zero sorry (미해결 부분 없음), zero admit, zero unverified axioms 조건으로 작성되어 수학적으로 엄밀합니다.
모델링:
- NTT 버터플라이: $a' = a + tw \cdot b$ , $b' = a - tw \cdot b$ 연산을 수행하며, 각 출력에 새로운 무작위 마스크 $m$ 을 적용합니다.
- 프로빙 모델 (Probing Model): ISW 1 차 프로빙 모델을 가정합니다 (전체 회로에서 클록 사이클당 1 개의 와이어만 관찰 가능).
- 새로운 마스킹 (Fresh Masking): 각 NTT 스테이지마다 독립적으로 새로운 무작위 마스크를 생성하여 적용하는 방식을 가정합니다.
접근 방식:
1. 기존 연구 (Paper 3) 의 제한사항을 해결하기 위해 '새로운 무작위성 (Fresh Randomness)'을 포함한 증명을 확장합니다.
2. 버터플라이의 선형성 (Affine structure) 을 활용하여 마스크에 대한 균일성 (Uniformity) 을 증명합니다.
3. 다단계 파이프라인에 대해 이러한 속성이 어떻게 전파되는지 구성 정리를 증명합니다.

3. 주요 기여 (Key Contributions)

이 논문은 Lean 4 로 증명된 세 가지 핵심 결과를 제시합니다.

1) r-베어링 브리지 (The r-Bearing Bridge)

내용: 이전 연구 (Paper 3) 에서 증명된 '값 독립성 (Value-Independence)'이 새로운 무작위성 (Fresh Randomness, $r$ ) 을 포함하는 경우에도 '상수 주변 분포 (Constant Marginal Distribution)'를 함의함을 증명했습니다.
의미: 대수적 상호 정보 (MutualInfoZero) 를 0 으로 만드는 조건을 엄밀하게 연결하여, 무작위성이 포함된 실제 하드웨어 환경에서의 보안성을 이론적으로 뒷받침합니다.

2) 버터플라이 컨텍스트별 균일성 (Butterfly Per-Context Uniformity)

핵심 발견:
- 오류 경고: "점별 값 독립성 (Pointwise Value-Independence)"은 버터플라이 출력에서 거짓입니다. (마스크가 고정된 상태에서 비밀값이 변하면 출력값도 변합니다. 이는 설계자가 SMT 솔버 등을 사용할 때 "불안전"이라고 잘못 판단하게 만드는 함정입니다.)
- 정확한 속성: 올바른 보안 속성은 **마스크에 대한 주변 균일성 (Marginal Uniformity)**입니다. 즉, 모든 비밀값과 입력 마스크에 대해, 특정 출력 값 $v$ 를 생성하는 정확히 하나의 마스크 값만이 존재한다는 것입니다.
보편성: 이 증명은 $q > 0$ 인 모든 모듈로 (소수뿐만 아니라 합성수 포함), 모든 트위들 팩터, 모든 입력에 대해 성립합니다.

3) 파이프라인 구성 (Pipeline Composition)

주장: $k$ 단계의 NTT 파이프라인에서 각 스테이지마다 새로운 (Fresh) 마스킹을 적용하면, ISW 1 차 프로빙 모델 하에서 모든 스테이지의 각 출력 와이어가 '컨텍스트별 균일성 (Per-Context Uniformity)'을 만족함을 증명했습니다.
의미: 이는 파이프라인 전체의 1 차 프로빙 보안을 보장하는 핵심 대수적 불변량 (Algebraic Invariant) 입니다.

4. 결과 및 검증 (Results)

검증 규모: 총 9 개의 정리가 Lean 4 로 증명되었으며, 1,738 개의 빌드 작업을 수행하여 0 에러, 0 경고를 기록했습니다.
Adams Bridge 분석:
- Adams Bridge 가속기는 INTT 0 라운드에서만 마스킹을 적용하고 이후 라운드에서는 새로운 마스킹을 적용하지 않습니다.
- 이 논문은 Theorem 6.2 (파이프라인 구성 정리) 의 가정이 위반되었기 때문에 Adams Bridge 에 대한 보안 보장이 적용되지 않는다는 것을 아키텍처적 관점에서 설명합니다. 즉, 스테이지 간 새로운 마스킹이 부재하여 정보가 누출될 수 있음을 수학적으로 규명했습니다.
비선형 소자 (Nonlinear Gadgets): 버터플라이는 선형 (Affine) 연산이므로 증명이 비교적 단순하지만, Barrett 축소 (Barrett Reduction) 나 곱셈과 같은 비선형 소자에 대한 구성은 별도의 논문 [3] 에서 PF-PINI 프레임워크를 통해 다루어지고 있음을 언급합니다.

5. 의의 및 중요성 (Significance)

FIPS 인증 지원: PQC 하드웨어 가속기 (FIPS 203/204) 의 FIPS 140-3 인증 과정에서, 하드웨어 설계자가 Lean 4 로 기계 검증된 증명을 직접 인용하여 1 차 프로빙 보안을 입증할 수 있는 근거를 제공합니다.
설계 원칙 정립: "Fresh Masking Design Principle"을 제시합니다. 즉, NTT 파이프라인의 각 스테이지 경계마다 독립적인 새로운 마스크를 주입해야만 파이프라인 수준의 보안이 보장된다는 것을 명확히 합니다.
오해 해소: 설계자들이 흔히 저지르는 '점별 값 독립성' 오류에 대한 경고 (Named Warning) 를 제공하여, 잘못된 보안 평가나 불필요한 설계 거부를 방지합니다.
범용성: 모듈로 $q$ 가 소수인 경우뿐만 아니라 모든 $q > 0$ 에 대해 성립하므로, 향후 다른 PQC 표준이나 모듈로가 적용되더라도 증명 결과가 유효합니다.

요약

이 논문은 Lean 4 를 이용한 기계 검증을 통해, NTT 파이프라인이 **각 스테이지마다 새로운 마스킹 (Fresh Masking)**을 적용할 때 1 차 프로빙 모델 하에서 보안이 보장됨을 수학적으로 증명했습니다. 이는 기존에 부울 회로에 국한되었던 검증 프레임워크를 **산술 회로 ( $Z_q$ )**로 확장한 첫 번째 사례이며, Adams Bridge 와 같은 기존 설계의 취약점을 이론적으로 규명하고, 향후 FIPS 인증을 받는 PQC 하드웨어 설계에 필수적인 기준을 제시했다는 점에서 큰 의의를 가집니다.