GL 스킴 깊이 알기: 행렬을 위해 처음부터 다시 설계한 동형암호
PR 팀 · 디사일로테크앤인사이트 — 동형암호와 Private AI 시리즈 (전 4편)
- ① 완전동형암호(FHE) 깊이 알기: 데이터를 열어보지 않고 계산하는 기술
- ② THOR 깊이 알기: 암호문 위에서 LLM을 추론하는 기술
- ③ GL 스킴 깊이 알기: 행렬을 위해 처음부터 다시 설계한 동형암호 — 지금 읽고 있는 글
- ④ Private AI 깊이 알기: 데이터를 내주지 않고 AI를 쓰는 기술 — 공개 예정
한눈에 보기 (TL;DR)
- GL(Gentry-Lee) 스킴은 행렬 연산을 스킴 설계 단계부터 지원하는 새로운 완전동형암호다. FHE의 창시자 크레이그 젠트리(Craig Gentry)와 디사일로 이용우 수석과학자(현 인하대학교 전기전자공학부 교수)가 공동 발명했고, 논문은 암호학 분야 최고 권위 학회인 CRYPTO 2026에 채택됐다.
- 기존 동형암호는 암호문을 '긴 벡터'로만 다루기 때문에 행렬 곱을 수십~수백 번의 회전 연산으로 우회해서 구현해야 했다. GL은 암호문이 처음부터 행렬을 담도록 인코딩을 재설계해, 암호화된 행렬 곱을 평문 행렬 곱 4번으로 환원한다.
- 행렬 곱에 드는 키 스위칭 비용은 원소별 곱셈 대비 최대 4배 이내(실측 약 2.8배)로 증명됐다. 256×256 복소 행렬 16장의 암호문 간 곱을 CPU 한 스레드로 약 7초에 처리했고, 그 시간의 대부분은 동형암호의 오버헤드가 아니라 평문 행렬 곱 그 자체였다.
- AI 연산의 대부분이 행렬 곱이라는 점에서, GL은 THOR가 증명한 '암호화된 AI 추론'을 다음 단계로 끌어올릴 5세대 동형암호다. 디사일로가 세계 최초로 상용 소프트웨어로 구현했다.
목차
- 왜 '행렬을 위한 동형암호'인가
- 무엇이 문제였나: 벡터로 행렬을 구현해오던 15년
- 핵심 아이디어 ① 암호문이 행렬을 담는다
- 핵심 아이디어 ② 행렬 곱이 평문 행렬 곱 4번으로
- 행렬을 위한 도구 상자: 전치, 회전, 부트스트래핑
- 결과: 숫자로 보는 GL
- 보안: 새 스킴은 왜 안전한가
- GL이 여는 것: 5세대 동형암호와 Private AI
- 자주 묻는 질문(FAQ)
- 참고 자료
1. 왜 '행렬을 위한 동형암호'인가
동형암호를 실제 서비스에 적용하려고 하면 결국 같은 벽에 부딪히게 된다. 행렬 곱셈이다. AI 추론 연산량의 대부분은 행렬 곱이고, 통계 분석과 추천 시스템까지 데이터가 커질수록 계산의 중심에는 행렬이 있다. 「THOR 깊이 알기」에서 보았듯, 암호화된 트랜스포머 추론의 성패도 결국 행렬 곱을 얼마나 빠르게 처리하느냐에 달려 있었다.
그런데 정작 동형암호 스킴에는 '행렬'이라는 자료형이 없었다. 2세대 BGV·BFV부터 4세대 CKKS까지, 지난 15년의 표준 스킴들은 암호문을 수천~수만 개의 숫자를 담은 긴 벡터(슬롯)로 다룬다. 벡터끼리의 덧셈과 원소별 곱셈에는 자연스럽지만, 행과 열이 얽히는 행렬 곱에는 태생적으로 부자연스러운 구조다.
GL(Gentry-Lee) 스킴은 이 문제를 뒤집어 푼다. 행렬을 벡터에 욱여넣는 대신, 처음부터 행렬을 담도록 암호문 자체를 다시 설계한 것이다. 2009년 완전동형암호를 처음 실현한 크레이그 젠트리(Craig Gentry, 현 Cornami 수석과학자)와 디사일로 이용우 수석과학자(현 인하대학교 전기전자공학부 교수)가 공동 발명했고, 논문은 암호학 분야 최고 권위 학회인 국제암호학회(IACR)의 CRYPTO 2026에 채택됐다(IACR ePrint Paper 2025/1935).
동형암호 기술 전반과 세대 구분은 「완전동형암호(FHE) 깊이 알기」에서 다룬다.
2. 무엇이 문제였나: 벡터로 행렬을 구현해오던 15년
암호문이 벡터뿐이라면, 행렬 곱은 어떻게든 벡터 연산으로 조립해야 한다. 기존 연구는 크게 두 갈래로 이 문제와 씨름해 왔다.
회전으로 조립하기. 행렬을 행·열·대각선 형태로 벡터에 펼쳐 담은 뒤, 회전(rotation)과 원소별 곱을 반복해 행렬 곱을 재구성하는 접근이다. Halevi-Shoup의 베이비스텝-자이언트스텝 기법부터 THOR의 대각선 인코딩까지 알고리즘은 계속 정교해졌지만, 회전과 그에 따르는 키 스위칭이라는 비용 구조 자체는 사라지지 않는다.
평문 행렬 곱으로 환원하기. 최근에는 암호문의 계수를 직접 다뤄, 암호화된 행렬 곱을 몇 번의 평문 행렬 곱으로 바꾸는 접근이 등장했다(Bae 외 CRYPTO 2024, Park EUROCRYPT 2025). 고도로 최적화된 행렬 곱 라이브러리를 그대로 쓸 수 있어 빠르지만, 대가가 있다. 행렬 크기가 링 차원(보통 4,096~131,072)에 고정되어 실용적인 크기의 행렬을 다루기 어렵고, 계수 인코딩을 쓰기 때문에 일반 SIMD 연산과 섞으려면 슬롯↔계수 변환 — 부트스트래핑에서도 주요 병목으로 꼽히는 무거운 동형 선형변환 — 을 반복해야 하며, 곱셈이 낮은 레벨에서만 가능해 회로 설계가 제약된다.
| 접근 | 대표 연구 | 강점 | 한계 |
|---|---|---|---|
| 회전 기반 (슬롯 인코딩) | Halevi-Shoup, Jiang 외, THOR | 기존 스킴을 그대로 활용 | 회전·키 스위칭 비용이 본질적으로 남음 |
| 평문 행렬 곱 환원 (계수 인코딩) | Bae 외(CRYPTO 2024), Park(EUROCRYPT 2025) | 평문 행렬 곱 라이브러리 활용 | 행렬 크기가 링 차원에 고정, 슬롯↔계수 변환 필요, 낮은 레벨 제약 |
GL의 목표는 두 갈래의 장점만 취하는 것이다. 슬롯 인코딩 위에서 곧바로, 크기를 자유롭게 고른 행렬을, 평문 행렬 곱의 속도로 곱한다.
3. 핵심 아이디어 ① 암호문이 행렬을 담는다
GL의 첫 번째 재료는 다변수 링(multivariate ring)이다. 기존 스킴의 암호문이 변수 하나짜리 다항식, 즉 한 줄짜리 벡터라면, GL의 암호문은 세 개의 축을 가진 다항식이다. X축이 행렬의 행을, Y축이 열을, W축이 여러 장의 행렬을 담는다. 한 줄짜리 표가 아니라 처음부터 가로×세로×깊이를 가진 텐서(tensor)이고, 다항식의 평가값 하나하나가 "ℓ번째 행렬의 (j, k) 원소"에 정확히 대응한다.
이 구조의 실용적 이점은 두 가지다. 첫째, 행렬 크기가 링 차원에 묶이지 않는 자유 파라미터가 된다. 실험에서는 256×256 행렬을 썼는데, 필요에 따라 더 작게도 크게도 잡을 수 있다. 둘째, 여러 행렬이 한 암호문에 배치(batch)되므로 곱셈 한 번으로 여러 쌍의 행렬 곱이 동시에 처리된다. 실험 파라미터에서는 한 암호문에 16장이 담긴다.
두 번째 재료는 가우스 정수(Gaussian integer) 관점이다. 동형암호가 쓰는 표준 링을 복소 정수 계수의 링으로 다시 바라보면 행렬 인코딩에 꼭 맞는 대칭 구조가 드러나고, 축의 확장이 자연스러워진다. 논문에 따르면 FHE의 행렬 인코딩에 가우스 정수 구조를 활용한 것은 이번이 처음이다.
4. 핵심 아이디어 ② 행렬 곱이 평문 행렬 곱 4번으로
인코딩을 바꿨으니 남은 문제는 곱셈이다. GL의 답은 대수학의 고전 도구인 자취(trace)다. 두 암호문 다항식을 곱한 뒤 보조 변수의 0차 성분만 골라내면, 그 결과가 정확히 '인코딩된 행렬들의 곱'이 된다는 것을 논문은 증명한다. 비밀키가 보조 변수에 의존하지 않도록 설계되어 있어, 이 자취 연산을 암호문 상태 그대로 수행할 수 있다.
결정적인 것은 이 자취가 계산되는 방식이다. 복잡해 보이는 연산이 실제로는 암호문 계수들의 평문 행렬 곱으로 정확히 환산된다. 복소수 행렬의 암호화된 곱 한 번은 가우스 정수 행렬 곱 4번(일반 정수 행렬 곱으로는 8번)으로 끝난다. 슬롯↔계수 변환도, 링 스위칭도, 수백 번의 회전도 없다. 남는 부대비용은 키 스위칭뿐인데, 그 비용이 원소별 곱셈(아다마르 곱) 대비 최대 4배 이내로 묶인다는 것까지 증명됐다.
이 구조가 게임의 성격을 바꾼다. 지금까지 동형암호의 행렬 곱은 "회전을 몇 번으로 줄이느냐"의 싸움이었다. GL에서는 "평문 행렬 곱을 얼마나 빨리 하느냐"의 싸움이 된다. 그리고 평문 행렬 곱은 BLAS·FLINT 같은 수십 년간 최적화된 라이브러리와 GPU가 세상에서 가장 잘하는 일이다.
5. 행렬을 위한 도구 상자: 전치, 회전, 부트스트래핑
행렬 대수는 곱셈만으로 이루어지지 않는다. GL은 스킴 수준에서 행렬 연산 일습을 지원한다.
- 전치(transpose): 두 변수를 맞바꾸는 자기동형 (X, Y)→(Y, X) 하나로 끝난다. 기존 스킴에서 전치는 그 자체로 무거운 동형 선형변환이었다.
- 켤레·켤레전치: 복소 행렬의 기본 변환을 같은 방식으로 지원한다.
- 행 회전·행렬 간 회전: 링 자기동형과 키 스위칭 한 번으로 처리된다.
- 열 회전: 키 스위칭이 아예 필요 없다. 비밀키가 열 방향 성분을 갖지 않도록 설계된 덕분에 계수 재배열만으로 끝난다. 실측 0.005초.
- 덧셈·아다마르 곱: 기존 스킴과 동일하게 지원되며, 아다마르 곱의 키 스위칭 비용은 기존 스킴과 사실상 같은 수준이다.
정수 행렬로의 일반화도 자연스럽다. BGV형 인코딩을 쓰면 같은 크기의 암호문에 두 배의 정수 행렬을 담을 수 있다. 또 실무적으로 중요한 점 한 가지는, GL의 후속 연구가 기존 CKKS 부트스트래핑의 병목을 해소하여, 보다 빠르고 효율적인 부트스트래핑이 가능하며(해당 후속 연구 논문은 GL 스킴 논문과 함께 CRYPTO 2026에 동시 채택됨), 이로 인해 신경망 전체 같은 깊은 회로도 끊김 없이 이어 계산할 수 있게 되었다는 점이다.
6. 결과: 숫자로 보는 GL
논문의 구현 결과다. 모든 수치는 GPU 없이 CPU 한 스레드에서 측정됐다.
| 항목 | 내용 |
|---|---|
| 대상 | 256×256 복소 행렬 16장을 한 암호문에 배치 |
| 보안 수준 | 128비트 (커뮤니티 표준 파라미터 가이드라인 준수) |
| 구현 | 정수론 라이브러리 FLINT의 행렬 곱 활용 |
| 환경 | Intel i9-11900K CPU, 단일 스레드 |
| 연산 (행렬 16장 동시 처리) | 실행 시간 |
|---|---|
| 암호문×암호문 행렬 곱 | 7.24초 (키 스위칭 3.32초 포함) |
| 평문×암호문 행렬 곱 | 2.06초 |
| 아다마르 곱 (원소별 곱셈) | 2.78초 |
| 전치 | 1.71초 |
| 행 회전 | 1.06초 |
| 열 회전 | 0.005초 |
| 덧셈 | 0.018초 |
읽는 법이 중요하다. 암호문 간 행렬 곱 7.24초는 16장 동시 처리이므로 행렬 한 장당 약 0.45초 꼴이고, 그중 순수한 정수 행렬 곱이 3.04초를 차지한다. 전체 시간의 상당 부분이 동형암호라서 붙는 웃돈이 아니라 어차피 해야 하는 평문 행렬 곱 그 자체라는 뜻이다. 키 스위칭을 슬롯당 비용으로 환산하면 아다마르 곱은 약 1.1µs로 같은 모듈러스 조건에서 측정한 OpenFHE의 CKKS 슬롯 회전 0.8µs와 같은 급이고, 행렬 곱 전체로도 약 3.2µs 수준이다. 행렬이 커질수록 행렬 곱 대비 키 스위칭의 비중은 더 작아지므로, 큰 행렬일수록 GL의 구조적 이점은 커진다.
7. 보안: 새 스킴은 왜 안전한가
새 스킴이라고 새로운 보안 가정을 세운 것은 아니다. GL의 암호문은 표준적인 링 위의 RLWE 암호문 여러 개와 수학적으로 동치이며, 따라서 보안은 기존 BGV·BFV·CKKS와 같은 근거, 곧 격자 문제(Ring-LWE)의 난해성 위에 선다. 실험 파라미터는 커뮤니티의 표준 보안 가이드라인에 따라 128비트 보안 수준으로 설정됐다. 격자 기반이므로 양자 컴퓨터에 대한 내성 역시 기존 FHE와 같은 수준으로 기대된다.
8. GL이 여는 것: 5세대 동형암호와 Private AI
동형암호의 역사는 다룰 수 있는 데이터의 확장사였다. 젠트리의 첫 구성(1세대)이 가능성을 열었고, BGV·BFV(2세대)가 정수 벡터를, TFHE(3세대)가 빠른 논리 연산을, 한국에서 나온 CKKS(4세대)가 실수를 다루게 했다. GL(5세대)은 여기에 '행렬'이라는 자료형과 '행렬 곱'이라는 연산을 스킴의 기본기로 추가한다. AI 시대의 계산이 행렬로 수렴한다는 점에서, 이는 단순한 기능 추가가 아니라 동형암호가 AI 연산을 정면으로 겨냥하게 됐다는 선언에 가깝다.
THOR와의 관계도 이 지점에서 분명해진다. THOR는 기존 4세대 스킴(CKKS) 위에서 인코딩과 알고리즘을 혁신해 암호화된 BERT 추론을 기존 논문 기준 10분으로, 이후 최적화를 통해 2분 수준까지 끌어내렸다. 이번 논문 역시 THOR를 포함한 기존 접근들을 검토하며, 벡터 기반 스킴 위의 최적화가 갖는 구조적 한계를 짚는다. GL은 그 한계를 스킴 교체로 걷어낸다. 알고리즘의 층위에서 스킴의 층위로, 최적화의 무대가 한 단계 내려간 것이다.
반향도 빠르다. 공개 직후 구글의 동형암호 컴파일러 프로젝트(HEIR)가 GL 스킴 검토에 착수했고, GL 전용 부트스트래핑 최적화를 다룬 후속 논문도 나오는 등 'GL'이라는 이름이 커뮤니티에 자리 잡고 있다. 디사일로는 GL 스킴을 국제 동형암호 콘퍼런스 FHE.org 2026(대만)에서 공개하고 세계 최초로 상용 소프트웨어로 구현했으며, 디사일로의 DESILO FHE 라이브러리는 국제 표준화 컨소시엄 HomomorphicEncryption.org의 공식 소개 페이지에 CKKS와 GL 스킴을 지원하는 라이브러리로 등재되어 있다. 논문이 제시하는 다음 단계 — 역행렬·행렬 분해 같은 고급 행렬 대수와 GPU·전용 프로세서 가속 — 는 평문 행렬 곱이 빨라질수록 GL도 함께 빨라진다는 구조 덕분에 더욱 기대되는 방향이다.
9. 자주 묻는 질문 (FAQ)
Q1. 기존 CKKS나 BFV를 대체하는가?
층위가 다르다. 기존 스킴이 '숫자 벡터'를 위한 범용 도구라면, GL은 행렬 연산이 중심인 워크로드를 위한 스킴이다. 덧셈·아다마르 곱·부트스트래핑 같은 기본기를 모두 갖추고 있어 단독으로도 쓸 수 있고, 기존 부트스트래핑과 호환되므로 대체라기보다 확장에 가깝다.
Q2. 왜 5세대라고 부르는가?
동형암호의 세대 구분은 '다룰 수 있는 데이터와 연산'의 확장을 기준으로 한다. 2세대가 정수 벡터를, 3세대가 빠른 논리 연산을, 4세대가 실수를 열었다면, GL은 행렬이라는 자료형과 행렬 곱이라는 연산을 스킴 수준에서 지원하는 다음 단계다. 세대별 흐름은 「완전동형암호(FHE) 깊이 알기」 3장에서 다룬다.
Q3. 실제로 얼마나 빠른가?
단일 CPU 스레드에서 256×256 복소 행렬 16장의 암호문 간 곱이 7.24초, 행렬 한 장당 약 0.45초다. 절대 수치보다 중요한 것은 비용 구조다. 시간의 대부분이 평문 행렬 곱이어서, GPU와 전용 하드웨어 가속의 이득을 구조적으로 그대로 흡수한다.
Q4. THOR와는 어떤 관계인가?
문제의식은 같고 해법의 층위가 다르다. THOR는 기존 CKKS 위에서 알고리즘을 혁신했고, GL은 스킴 자체를 재설계했다. GL은 THOR가 증명한 암호화 AI 추론의 기반 연산을 통째로 바꿀 수 있는 다음 카드다.
Q5. 새 스킴인데 보안을 믿을 수 있는가?
새로운 보안 가정은 없다. GL 암호문은 표준 RLWE 암호문 여러 개와 동치라서 기존 스킴과 같은 격자 난해성에 기반하며, 실험 파라미터도 표준 가이드라인에 따른 128비트 보안 수준으로 설정됐다.
10. 참고 자료
- Craig Gentry, Yongwoo Lee, "Fully Homomorphic Encryption for Matrix Arithmetic," CRYPTO 2026 (IACR Cryptology ePrint Archive, Paper 2025/1935): https://eprint.iacr.org/2025/1935
- Eric Crockett, Craig Gentry, Hyojun Kim, Yeongmin Lee, Yongwoo Lee, "Efficient Bootstrapping in Fully Homomorphic Encryption for Matrix Arithmetic," CRYPTO 2026 (IACR Cryptology ePrint Archive, Paper 2026/956): https://eprint.iacr.org/2026/956
- 구글 HEIR 프로젝트의 GL 스킴 검토 이슈 (google/heir #2408): https://github.com/google/heir/issues/2408
- Jai Hyun Park, "Ciphertext-ciphertext Matrix Multiplication: Fast for Large Matrices," EUROCRYPT 2025
- Youngjin Bae 외, "Plaintext-ciphertext Matrix Multiplication and FHE Bootstrapping: Fast and Fused," CRYPTO 2024
- Jungho Moon 외, "THOR: Secure Transformer Inference with Homomorphic Encryption," ACM CCS 2025
- DESILO FHE 라이브러리: https://fhe.desilo.dev/latest/
테크앤인사이트 — 동형암호와 Private AI 시리즈 (전 4편)
- ① 완전동형암호(FHE) 깊이 알기: 데이터를 열어보지 않고 계산하는 기술
- ② THOR 깊이 알기: 암호문 위에서 LLM을 추론하는 기술
- ③ GL 스킴 깊이 알기: 행렬을 위해 처음부터 다시 설계한 동형암호 — 지금 읽고 있는 글
- ④ Private AI 깊이 알기: 데이터를 내주지 않고 AI를 쓰는 기술 — 공개 예정
다음 편 예고
다음 편에서는 시리즈의 마지막으로 Private AI 자체를 다룬다. 데이터를 내주지 않고 AI를 쓴다는 것이 무엇인지, 동형암호·신뢰실행환경·연합학습이 각각 어느 자리를 맡는지, 그리고 THOR와 GL이 증명한 암호화 추론이 실제 제품의 어디에 들어가는지 짚는다. 다음 주 이 게시판에서 공개한다.