💻 computer science

PIP-NTT: Towards a Scalable Memory-Parallelized Accelerator for Iterative NTT in PQC

본 논문은 4개의 더 작은 메모리 블록과 곱셈이 없는 리스케일링 아키텍처를 활용하여 기존 설계 대비 현저히 높은 면적-시간 효율성을 달성하는, 양자 내성 암호의 반복적 수론 변환을 위한 확장 가능하고 메모리 병렬화된 하드웨어 가속기인 PIP-NTT를 제안한다.

원저자: Malik Imran, Ayesha Khalid, Ciara Rafferty, Safiullah Khan, Muhammad Rashid, Maire O'Neill

게시일 2026-07-22

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Malik Imran, Ayesha Khalid, Ciara Rafferty, Safiullah Khan, Muhammad Rashid, Maire O'Neill

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

당신의 은행 계좌, 개인적인 메시지, 심지어 국가 기밀을 보호하는 자물쇠가 종이로 만들어진 세상을 상상해 보십시오. 수십 년 동안 우리는 거대한 숫자를 인수분해하는 것과 같은 수학적 퍼즐에 의존하여 이 자물쇠들을 안전하게 지켜왔습니다. 하지만 과학자들은 미래의 "양자" 컴퓨터가 양자 물리학의 기묘한 법칙에 따라 작동하며, '쇼어 알고리즘(Shor's algorithm)'이라는 기술을 사용해 이 종이 자물쇠들을 단 몇 초 만에 찢어버릴 수 있다는 사실을 발견했습니다. 이를 막기 위해 암호학자들은 "격자(lattice)"—즉, 숫자로 이루어진 복잡하고 다차원적인 격자 구조—를 기반으로 한 새롭고 매우 강력한 자물쇠를 만들고 있습니다. 이 새로운 자라들은 "양자 내성 암호(Post-Quantum Cryptography, PQC)"의 영웅들입니다. 하지만 여기에는 함정이 있습니다. 이 새로운 자물쇠들은 엄청난 양의 수치 계산을 필요로 하기 때문에 매우 무겁고 사용하기 느리다는 점입니다. 이를 당신의 스마트폰이나 스마트 온도 조절기에서 실용적으로 사용하려면, 배터리를 소모하거나 공간을 너무 많이 차지하지 않으면서도 이러한 계산을 효율적으로 수행할 수 있는 특별하고 번개처럼 빠른 하드웨어 엔진을 구축해야 합니다. 이것이 바로 이 새로운 디지털 자물쇠를 현실 세계에서 충분히 빠르게 만들기 위해 노력하는 연구팀이 직면한 과제입니다.

당신이 읽게 될 이 논문은 '수론 변환(Number Theoretic Transform, NTT)'이라고 불리는 특정하고 결정적인 수학 연산을 가속화하기 위해 설계된 PIP-NTT라는 새로운 하드웨어 엔진을 소개합니다. NTT를 숫자 더미를 즉시 곱할 수 있도록 재배열하는 마법의 컨베이어 벨트라고 생각해 보십시오. 격자 기반 암호(최근 NIST에서 표준화한 ML-KEM 스킴과 같은)의 세계에서 이 연산은 시스템의 심장 박동과 같습니다. 만약 NTT가 느려지면, 전체 보안 시스템이 멈춰버립니다. 연구진은 이 작업을 수행하는 기존 엔진들이 종종 두 개의 커다란 저장 공간 사이에서 데이터가 앞뒤로 왔다 갔다 해야 하는 "핑퐁" 메모리 시스템을 사용하느라, 데이터 정체가 발생하여 속도가 느려진다는 점을 발견했습니다. 또한 그들은 프로세스의 마지막 단계에서 숫자를 정리하기 위해 무겁고 에너지를 많이 소비하는 방법을 사용하고 있다는 점도 주목했습니다.

이를 해결하기 위해 저자들은 더 똑똑하고 능률적인 엔진을 구축했습니다. 두 개의 거대한 저장 공간 대신, 네 개의 더 작고 빠른 저장 공간을 병렬로 사용하여 데이터가 줄을 서서 기다리지 않고 시스템을 통해 흐를 수 있도록 했습니다. 또한 무거운 정리 단계를 단순한 덧셈과 배수를 사용하는 영리한 '곱셈 없는 기술'로 대체하여 공간과 전력을 대폭 절감했습니다. 이러한 메모리 기술을 고도로 최적화된 "버터플라이(butterfly)" 유닛(실제 수학 계산을 수행하는 작은 계산기)과 결에도 결합함으로써, 그들은 매우 빠르면서도 놀라울 정도로 작은 설계를 만들어냈습니다. 연구진이 이들의 창조물을 프로그래밍 가능한 게이트 어레이(FPGA)—칩을 맞춤형 하드웨어처럼 재프로그래밍할 수 있는 유형의 칩—에서 테스트했을 때, 기존 문헌의 그 어떤 것보다 훨씬 더 효율적이라는 것을 발견했습니다. 구체적으로, 그들의 설계는 가장 공간을 적게 차지하는 설계보다 2.67배 더 나은 '면적-시간 곱(Area-Time Product, 칩이 작업을 수행하는 데 필요한 공간과 시간의 척도)'을 달고 있었으며, 가장 빠른 고속 설계보다 1.48배 더 나은 성능을 보여주었습니다. 그 결과, 이 엔진은 비용이나 배터리 문제를 일으키지 않으면서도 양자 위협으로부터 우리의 디지털 미래를 보호할 수 있는 다재다능하고 확장 가능한 엔진이 되었습니다.

기술 요약: PIP-NTT: PQC를 위한 반복적 NTT의 확장 가능한 메모리 병렬화 가속기를 향하여

문제 정의
NIST에 의해 표준화된 ML-KEM (Kyber) 및 ML-DSA (Dilithium)와 같은 격자 기반 양자 내성 암호(PQC)는 효율적인 다항식 곱셈을 위해 수론적 변환(NTT)에 크게 의존한다. 기존의 반복적 NTT 하드웨어 가속기는 처리량과 자원 활용도 사이의 트레이드오프에 직면해 있다. 고처리량 설계는 심층 파이프라이닝과 대규모 메모리 배열 또는 다수의 버터플라이 유닛을 사용하여 상당한 면적 오버헤드를 초래하며, 이는 자원이 제한된 플랫폼에 부적합하다. 반대로, 면적 최적화 설계는 "핑퐁(ping-pong)" 메모리 방식과 단일 버터플라이 유닛에 의존하는 경우가 많다. 이러한 방식은 하드웨어 풋프린트를 줄여주지만, 본질적으로 확장성, 병렬성 및 주파수 최적화를 제한하여 성능 병목 현상을 일으킨다. 또한, 역 NTT(INTT) 후에 필요한 리스케일링(rescaling) 단계는 종종 비용이 많이 드는 모듈러 곱셈이나 나눗셈을 포함하며, 이는 임계 경로 지연(critical path delay)을 가중시킨다.

방법론
저자들은 면적 효율성과 계산 처리량의 균형을 맞추기 위해 설계된 통합된 파이프라인 및 메모리 병렬화 NTT 가속기인 "PIP-NTT"를 제안한다. 이 방법론은 세 가지 핵심 혁신을 기반으로 한다:

통합 파이프라인 버터플라이 유닛 (DSE): 저자들은 Cooley–Tukey (CT) 및 Gentleman–Sande (GS) 버터플라이 유닛에 대한 포괄적인 설계 공간 탐색(DSE)을 수행하였다. 비파이프라인 베이스라인부터 거친 입도(coarse-grained) 및 미세 입도(fine-grained) 파이프라이닝을 모두 활용하는 설계에 이르기까지 8가지 아키텍처 변형을 평가하였다. 최적의 설계인 8단계 파이프라인 버터플라이 유타(8SP-BU)는 Barrett 방식을 사용한 모듈러 리덕션과 산술 연산을 통합하고, 면적 오버헤드를 최소화하면서 동작 주파수를 극대화하기 위해 데이터 패스 내에 전략적으로 레지스터를 배치한다.
곱셈 없는 리스케일링 (Multiplication-Free Rescaling): INTT 리스케일링 단계( $a \cdot n^{-1} \mod q$ )를 위해, 저자들은 Kyber 모듈러스( $q=3329$ )의 특정 합동성( $n^{-1} \equiv -13 \pmod{3329}$ )을 활용한다. 복잡한 시프트-애드(shift-add) 회로나 나눗셈 대신, 모듈러 배수와 덧셈을 사용하여 $13a$ 를 계산한 후 조건부 부호 반전을 수행하는 경량 아키텍처를 구현한다. 이를 통해 이 단계에서 범용 곱셈기의 필요성을 제거한다.
메모리 병렬화 전략: 총 메모리 풋프린트를 늘리지 않고도 전통적인 핑퐁 메모리 방식의 한계를 극복하기 위해, 저자들은 두 개의 큰 블록 대신 네 개의 작은 메모리 블록(각 크기 $n/4$ )을 사용하는 기술을 도입한다. 계수들은 인접한 쌍으로 저장된다. 멀티플렉서 기반의 스왑 네트워크는 현재 단계의 오프셋( $\delta$ )에 따라 출력을 재정렬한다. 이를 통해 두 개의 버터플라이 유닛이 동시에 작동할 수 있다. 오프셋이 클 때( $\delta \ge n/4$ ), 네 개의 메모리 블록과 두 개의 버터플라이 유닛이 모두 활용된다. 오프셋이 작을 때( $\delta < n/4$ ), 시스템은 두 개의 활성 블록을 통해 부분 병렬성을 달성한다. 이 전략은 동일한 총 메모리 용량을 유지하면서 단일 유닛 반복 설계보다 클록 사이클을 절반으로 줄인다.

주요 기여

최적화된 버터플라이 아키텍처: 미세 입도 파이프라이닝을 통해 주파수를 46 MHz(베이스라인)에서 298 MHz로 증가시키면서 면적 오버헤드는 1.32배에 불과한 통합 CT/GS 버터플라이 유닛을 구현하였다.
효율적인 리스케일링: 표준 7-항 시프트-애드 구현과 비교하여 Slice 사용량을 1.67배, LUT 사용량을 1.84배 감소시키는 곱셈 없는 리스케일링 아키텍처를 제공한다.
확장 가능한 메모리 병렬성: 반복적 NTT에서 부분 병렬성을 가능하게 하는 네 개의 $n/4$ 크기 블록과 스왑 네트워크를 사용하는 새로운 메모리 구조를 통해, 총 메모리 비용을 늘리지 않고 클록 사이클을 50% 감소시켰다.
통합 가속기 (PIP-NTT): Kyber 파라미터( $n=256, q=3329$ )에 대해 순방향(FNTT) 및 역방향(INTT) 변환을 모두 지원하며, 두 개의 최적화된 버터플라이 유닛과 메모리 병렬화 기법이 통합된 완전한 FPGA 구현체를 제공한다.

실험 결과
PIP-NTT 설계는 Xilinx Virtex-7 및 Artix-7 FPGA 플랫폼에서 구현되었다.

성능: 이 가속기는 200 MHz에서 동작하며, 단일 FNTT 또는 INTT를 2.60 µs (520 클록 사이클) 내에 계산한다.
효율성: 면적-시간 곱(ATP) 측면에서 PIP-NTT는 다음을 달성한다:
- 문헌상의 가장 면적 최적화된 NTT 가속기 대비 2.67배 높은 효율.
- 가장 고속인 NTT 가속기 대비 1.48배 높은 효율.
자원 사용량: 설계는 Virtex-7에서 156개의 Slice, 426개의 LUT, 379개의 Flip-Flop을 사용하여, 그 처리량 대비 매우 컴팩트한 풋프린트를 보여준다.

의의 및 주장
본 논문은 PIP-NTT가 반복적 NTT 설계에 내재된 확장성 및 효율성 트레이드오프를 효과적으로 해결함으로써 미래의 암호화 하드웨어를 위한 다각적인 솔루션을 제공한다고 주장한다. 제안된 메모리 병렬화 전략을 통해 병렬성을 총 메모리 비용으로부터 분리함으로써, 설계는 엄격한 면적 제약 하에서도 높은 처리량을 가능하게 한다. 저자들은 이 아키텍처가 Kyber에 국한되지 않으며, 메모리 전략의 기수(radix) 및 스킴 불가지론적 특성과 버터플라이 유닛의 모듈형 설계를 통해 최소한의 수정만으로 다른 PQC 스킴(예: Dilithium) 및 다양한 링 크기에 적응할 수 있음을 강조한다. 이 연구는 PIP-NTT를 임베디드 시스템에서 데이터 센터에 이르기까지 다양한 배포 시나리오에 적합한 균형 잡히고 자원 효율적인 접근 방식으로 자리매김한다.

유사한 논문