💻 computer science

GPU Acceleration of Learning With Errors KEMs Using OpenACC for Post-Quantum Cryptography

이 논문은 OpenACC를 사용하여 LWE(Learning with Errors) 기반 키 캡슐화 메커니즘의 GPU 가속 구현을 제시하며, 기존 CPU 및 H100 기반 시스템과 비교하여 특히 NVIDIA Grace Hopper 슈퍼칩에서 최대 208배의 상당한 속도 향상과 개선된 에너지 효율성을 입증한다.

원저자: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

게시일 2026-06-02

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

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

당신이 미래의 초지능 로봇(양자 컴퓨터)조차 풀 수 없는 매우 복잡한 열쇠로 보물 상자를 잠그려 한다고 상상해 보세요. 이것이 바로 **양자 내성 암호(Post-Quantum Cryptography)**의 목표입니다. 이 논문이 집중하고 있는 특정 "자물쇠"는 **LWE(Learning With Errors)**라고 불립니다.

LWE를 이해하기 쉽게 설명하자면, 누군가 의도적으로 신호에 약간의 "정적" 또는 "노이즈"를 추가한 거대한 수학 퍼즐을 푸는 것과 같습니다. 노이즈를 만드는 것은 쉽지만, 비밀 키 없이는 그 노이즈를 걸러내고 원래의 메시지를 찾아내는 것은 매우 어렵습니다. 문제는, 일반적인 컴퓨터로 이 퍼즐을 푸는 것이 마치 산을 모래알 하나씩 옮기는 것처럼 엄청나게 오래 걸린다는 점입니다.

연구진이 이를 가속화하기 위해 수행한 작업을 알기 쉽게 설명하면 다음과 같습니다.

1. 문제점: CPU는 느린 트럭이다

저자들은 먼저 일반 컴퓨터 프로세서(CPU)에서 실행되는 버전의 암호화를 시작했습니다. 그 결과 CPU가 고전하고 있다는 것을 발견했습니다. 이는 마치 수천 개의 상자를 옮기려는 단 한 대의 배송 트럭과 같았습니다. 트럭이 창고(메모리)에서 트럭 적재함으로 데이터(상자 하나)를 옮길 때마다, 트럭은 멈춰서 짐을 싣고 다시 출발해야 했습니다. 트럭은 일하는 시간보다 기다리는 데 대부분의 시간을 허비하고 있었습니다.

2. 해결책: GPU는 드론 함대이다

이를 해결하기 위해 연구진은 무거운 작업을 **GPU(그래픽 처리 장치)**로 옮겼습니다. CPU가 한 번에 상자 하나를 운반하는 단 한 대의 배송 트럭이라면, GPU는 수천 대의 작고 매우 빠른 드론 함대와 같습니다.

비유: 한 번에 상자 하나를 실어 나르는 트럭 대신, GPU는 수천 개의 상자를 동시에 운반할 수 있습니다.
도구: 그들은 OpenACC라는 프로그래밍 언어를 사용했습니다. 이것은 일종의 범용 리모컨과 같습니다. 드론을 위한 전체 설명서를 새로 쓰는 대신(이는 어렵고 오류가 생기기 쉽습니다), 기존의 트럭 명령어를 향해 리모컨을 조준하고 "이 부분도 당신이 하세요, 하지만 더 빠르게!"라고 말하는 것과 같습니다. 이를 통해 기존 소프트웨어를 망가뜨리지 않고도 쉽게 업그레이드할 수 있었습니다.

3. 병목 현상: "노이즈" 생성기

이 암호화 방식에서는 퍼즐을 어렵게 만들기 위해 많은 양의 무작위 "노이즈"가 필요합니다.

기존 방식: CPU가 노이즈를 생성하여 기록한 다음, 이를 GPU로 운반했습니다. 이는 트럭 운전사가 쇼핑 목록을 적고, 가게로 운전해서 가서, 물건을 사고, 다시 돌아오는 과정과 같았습니다. 이는 많은 시간을 낭비했습니다.
해결책: 연구진은 GPU의 창고 안에 직접 "노이즈 생성기"를 설치했습니다. 이제 드론은 현장에서 직접 무작위 노이즈를 생성할 수 있습니다. 더 이상 트럭이 물건을 가져다주기를 기다릴 필요가 없습니다. 이로 인해 대기 시간이 극적으로 줄어들었습니다.

4. "배칭(Batching)" 기술

암호화 과정은 한 번에 256개의 작은 퍼즐(메시지의 각 비트당 하나)을 푸는 과정을 포함합니다.

기존 방식: GPU가 하나의 퍼즐을 풀고, 멈추고, 명령을 기다리고, 다음 퍼즐을 풀고, 또 멈추는 식의 과정을 반복했습니다. 이는 마치 요리사가 한 번에 달걀 하나를 요리하고, 다음 요리를 하기 전에 가스레인지가 식기를 기다리는 것과 같습니다.
해결책: 그들은 **연산 내 배칭(Intra-Operation Batching)**이라는 전략을 사용했습니다. 이는 요리사가 256개의 달걀을 커다란 팬에 한꺼번에 넣고 동시에 요리하는 것과 같습니다. GPU는 256개의 퍼즐을 동시에 해결하기 위해 한 번의 큰 "실행(launch)"을 수행하며, 이를 통해 엄청난 시간을 절약합니다.

5. 결과: 속도와 에너지

연구진은 다양한 종류의 초고속 컴퓨터(GPU)에서 이 방식을 테스트하고 기존의 CPU 방식과 비교했습니다.

속도: 그들이 테스트한 가장 최신의 강력한 컴퓨터(Grace Hopper 슈퍼칩)에서, 새로운 방식은 기존 CPU 방식보다 208배 더 빨랐습니다.
- 비유: 기존 트럭이 패키지를 배달하는 데 3시간이 걸렸다면, 새로운 드론 함대는 1분도 안 되어 일을 끝냅니다.
- 또한, 기존 CPU라면 메모리가 부족해 충돌(crash)이 발생했을 만큼 거대한 크기의 퍼즐들도 풀어낼 수 있었습니다.
에너지: 새로운 방식은 에너지도 덜 사용했습니다. Grace Hopper 컴퓨터는 다른 종류의 빠른 GPU를 갖춘 표준 컴퓨터에 비해 동일한 작업을 수행하는 데 약 절반의 에너지만을 사용했습니다.
- 비가: 이는 가솔린을 많이 쓰는 트럭 대신 하이브리드 자동차를 사용하여 동일한 배달을 마치는 것과 같습니다.

6. 왜 중요한가

이 논문은 GPU(드론)와 스마트한 관리 기술(OpenACC, 배칭, 온디바이스 노이즈)을 사용함으로써, 이 초강력 보안 기술인 양자 내성 암호를 실제로 사용할 수 있게 만들 수 있음을 보여줍니다. 이러한 속도 향상이 없다면, 이 수학적 계산은 너무 느려서 실생활에서 유용하게 쓰일 수 없습니다. 이 기술을 통해 우리는 단 하나의 자물쇠가 채워지기를 며칠씩 기다릴 필요 없이, 미래의 양자 컴퓨터로부터 우리의 데이터를 안전하게 보호할 수 있습니다.

요약하자면: 연구진은 느리고 무거운 암호화 방식을 가져와서, 수천 명의 작은 일꾼(GPU)들이 함께 협력하고, 스스로 물자를 생성하며, 명령을 기다리며 멈추지 않도록 하여 엄청난 속도 향상을 이루어냈습니다. 그 결과, 수백 배 더 빠르고 에너지 효율적인 시스템을 만들어냈습니다.

기술 요약: OpenACC를 이용한 LWE 기반 KEM의 GPU 가속화

문제 정의
대규모 양자 컴퓨터의 등장은 쇼어(Shor) 알고리즘을 통해 현재의 비대칭 암호 프로토콜(예: RSA, ECC)을 위협하고 있습니다. 격자 기반 암호, 특히 학습 오류(Learning With Errors, LWE) 문제에 의존하는 키 캡슐화 메커니즘(Key Encapsulation Mechanisms, KEM)을 중심으로 한 양자 내성 암호(Post-Quantum Cryptography, PQC)가 해결책으로 부상했습니다. 그러나 LWE 기반 방식은 대규모 행렬 연산과 난수 생성으로 인해 상당한 계산 오버헤드를 발생시키며, 이는 표준 CPU 아키텍처 기반의 고처리량 서버 측 애플리케이션에서 실용성을 떨어뜨리는 경우가 많습니다. GPU 가속화가 PQC를 위해 탐구되어 왔으나, 대부분의 기존 구현체는 CUDA 특정 최적화에 의존하여 이식성과 개발 생산성을 제한합니다. 또한, 단순한 포팅은 호스트-디바이스 간 메모리 전송 지연 및 난수 생성의 직렬화와 같은 병목 현상을 해결하지 못해 실패하는 경우가 빈번합니다.

방법론
저자들은 "순수(plain)" LWE(Ring-LWE와 같은 추가적인 대수적 구조를 피함)에 기반한 KEM을 제안하며, OpenACC 디렉티브 기반 프로그래밍 모델을 사용하여 GPU 지향적 구현을 개발합니다. 본 연구는 다음과 같은 방법론적 단계를 거칩니다:

베이스라인 구현: LWE-KEM의 C++ 구현체를 멀티코어 CPU를 위한 OpenMP를 사용하여 병렬화했습니다. 이 스킴은 KeyGen, Encaps, Decaps 단계를 포함하며, IND-CCA2 보안을 달기 위해 후지사키-오카모토(Fujisaki-Okamoto, FO) 변환을 활용합니다.
OpenACC 포팅 및 최적화: CPU 코드를 OpenACC를 사용하여 GPU로 포팅했습니다. 성능 병목 현상을 극복하기 위해 저자들은 세 가지 주요 전략을 구현했습니다:
- 연산 내 배치(Intra-Operation Batching): 256개의 독립적인 메시지 비트를 순차적으로 처리(별도의 커널 호출 및 메모리 전송 유발)하는 대신, 구현체는 256개의 모든 암호화를 단일 GPU 커널 호출로 융합합니다. 이를 통해 미세한 병렬성( $256 \times n$ 워크 아이템)을 노출하고 호출 오버헤드를 분산시킵니다.
- 디바이스 상주 난수 생성(Device-Resident Random Number Generation, RNG): 난수 노이즈 벡터를 PCIe를 통해 전송하는 것이 심각한 병목 현상을 만든다는 점을 인식하여, 저자들은 RNGonGPU 라이브러리를 통합했습니다. 이 라이브러리는 AES-256 결정론적 비트 생성기(DRBG)를 GPU에서 직접 구현합니다. 호스트에서 디바이스로 64비트 시드만 전송함으로써, 사전 생성된 노이즈 벡터를 전송할 때보다 데이터 전송량을 약 6배(10^6) 줄였습니다.
- 명시적 데이터 관리: 저자들은 결정론적인 호스트-디바이스 전송을 제어하기 위해 CUDA Unified Memory 대신 명시적인 enter data 및 exit data 디렉티브를 사용하여 불필요한 통신을 최소화하고, 특정 동기화 지점(예: 해싱 전)에서만 데이터 일관성을 보장했습니다.
커널 병렬화: 주요 계산 비용인 행렬-벡터 곱셈을 계층적으로 병렬화했습니다. 암호화/복호화의 경우, 독립적인 메시지 암호화 작업은 OpenACC gang에 할당되었고, 암호문 구성 요소는 벡터 레인(vector lanes) 전체에서 동시에 계산되었습니다.

주요 기여

오픈 소스 구현: 저자들은 CPU(OpenMP) 및 GPU(OpenACC) 모두를 위한 순수 LWE 기반 KEM의 오픈 소스 구현을 제공하여 재현 가능한 벤치마크를 가능하게 합니다.
디렉티브 기반 최적화: 광범위한 LWE 스킴에 적용 가능한 GPU 지향적 최적화 세트를 제시하며, 디렉티브 기반 모델(OpenACC)이 깊은 CUDA 전문 지식 없이도 높은 성능을 달고 달성할 수 있음을 입증합니다.
포괄적 평가: 여러 세대의 NVIDIA GPU(Volta, Ampere, Hopper) 및 아키텍처(x86 + Hopper vs. ARM 기반 Grace Hopper Superchip)에 대한 성능, 에너지 효율성 및 확장성에 대한 상세한 연구를 수행합니다.

결과
평가는 NVIDIA GH200 Grace Hopper Superchip, A100, V100S를 포함한 다양한 플랫폼에서 수행되었습니다.

가속도(Speedup): 최적화된 OpenACC 구현체는 멀티스레드 CPU 베이스라인 대비 상당한 속도 향상을 달성했습니다. GH200 플랫폼에서 큰 문제 크기( $n=4096$ )에 대해 최대 208배의 속도 향상을 기록했습니다. GPU 구현체는 $n \ge 256$ 에서 CPU 베이스라인을 능가하기 시작했습니다.
확장성: GPU 구현체는 문제 크기가 증가함에 따라 CPU 버전보다 우수한 확장성을 보여주었으며, 메모리 경합 및 동기화 오버헤드로 인해 CPU에서 처리가 불가능했던 파라미터 세트(예: $n=32768$ )를 효과적으로 처리했습니다.
에너지 효율성: GH200 Superchip에서 이 구현체는 x86 + H100 시스템에 비해 **1.78배 낮은 에너지-투-솔루션(energy-to-solution)**을 달却했습니다. 이는 주로 ARM 기반 Grace CPU의 낮은 전력 소비에 기인합니다. GH200 대 x86+Hopper의 시간-투-솔루션(time-to-solution) 개선은 1.19배로 다소 완만했습니다.
아키텍처 스케일링: 세대 간 분석(V100S $\to$ A100 $\to$ GH200) 결과, 성능 스케일링은 주로 고대역폭 메모리(HBM) 대역폭에 의해 주도됨을 밝혔습니다. 그러나 대역폭이 증가함에 따라, 온디맨드 행렬 요소 생성(연산 비용) 및 고정된 CPU 측 FO 변환 비용이 스케일링을 제한하기 시작하여, 병목 현상이 순수 메모리 제한에서 계산 및 동기화 제약이 혼합된 형태로 변화함을 확인했습니다.
최적화 영향: 프로파일링 결과, 초기 구현은 호스트 측 계산과 PCIe 전송에 의해 지배되었습니다(GPU 스타베이션). 최적화된 구현은 병목을 동기화로 이동시켰으며, GPU 활동은 반복 시간의 약 98% 동안 유지되었습니다.

의의
본 논문은 계산 집약적인 LWE 기반 암호 워크로드에 대한 GPU 가속의 효과를 강조합니다. 저자들은 OpenACC를 활용함으로써, 저수준 CUDA 코딩 없이도 프로그래밍 가능성과 성능 사이의 균형을 맞춘 고성능 PQC로 가는 경로를 제시합니다. 이 연구는 적절한 최적화(특히 연산 내 배치 및 디바이스 상주 RNG)를 통해, 보수적인 보안 가정을 제공하지만 높은 계산 비용을 수반하는 "순수" LWE 스킴이 현대적인 이기종 플랫폼에서 실용화될 수 있음을 시사합니다. 또한, 차세대 아키텍처에서는 CPU 측 연산과 인터커넥트가 확장성을 제약하게 됨에 따라, 전체 이기종 파이프라인을 공동 최적화하는 것이 중요하다는 점을 강조합니다. 향후 연구로는 이 접근 방식을 멀티 GPU 환경 및 기타 가속기 아키텍처(AMD, Intel)로 확장하는 것이 제안되었습니다.