왜 동형암호와 PQC는 모두 격자를 택했을까: 양자 알고리즘이 아직 없기 때문일까

By PLURA 2026-04-05

동형암호와 양자내성암호(PQC)를 보다 보면
묘한 공통점이 하나 눈에 들어옵니다.

둘 다 결국
격자 문제(lattice problem) 라는 수학 난제 위에 서 있다는 점입니다.

여기서 자연스럽게 질문이 생깁니다.

왜 하필 격자인가?
혹시 “양자 알고리즘이 아직 없으니 당분간 안전하겠지”라는 기대 때문인가?

이 질문은 매우 좋습니다.

결론부터 말하면,
그것만이 이유는 아닙니다.

물론 현재로서는
격자 문제를 Shor 알고리즘처럼 단번에 무너뜨리는
효율적인 양자 알고리즘이 알려져 있지 않습니다.

하지만 동형암호와 PQC가
모두 격자를 선택한 더 본질적인 이유는 따로 있습니다.

격자는 “아직 안 깨졌다”는 소극적 이유만이 아니라,
효율성과 확장성, 그리고 다양한 암호 기능을 구현하기 좋은 구조를
동시에 제공하기 때문입니다.

즉, 격자는
단순한 임시 피난처가 아니라
현재까지 알려진 후보들 중
가장 균형이 좋은 수학적 기반에 가깝습니다.

왜 이 질문이 중요한가

많은 글은 이렇게 설명합니다.

RSA와 ECC는 양자컴퓨터에 취약하다
그래서 PQC가 필요하다
PQC는 격자를 많이 쓴다

여기까지만 들으면
격자는 마치 “양자 알고리즘이 아직 없는 임시 후보”처럼 보일 수 있습니다.

하지만 그렇게 이해하면
동형암호까지 왜 격자를 쓰는지 설명이 잘 되지 않습니다.

동형암호는 단순한 키 교환이나 서명이 아니라
암호문 상태의 계산을 해야 합니다.
그런데도 격자가 중심입니다.

이 말은 곧
격자의 가치는 단순히 “양자에 아직 안 깨졌다”가 아니라,
암호 기능을 만들기 좋은 구조 자체에 있다는 뜻입니다.

즉, 이 질문은
양자 시대 보안을 이해하는 문제일 뿐 아니라
왜 현재 암호학이 특정 수학 위에 무게를 두는지를 이해하는 문제이기도 합니다.

먼저 정리할 것: “양자 알고리즘이 아직 없다”는 말은 맞지만, 그것만으로는 부족하다

현재 공개적으로 알려진 범위에서
RSA를 무너뜨린 Shor 알고리즘에 해당하는
격자 전용의 결정적 양자 알고리즘은 없습니다.

하지만 이것을
“그냥 양자 알고리즘이 아직 안 나와서 쓴다”로 요약하면
절반만 맞습니다.

왜냐하면 암호는
단순히 “안 깨지는 수학”만으로 채택되지 않기 때문입니다.

실제로 표준이 되려면
다음 조건이 함께 필요합니다.

충분한 보안 근거
실제 구현 가능성
키와 서명 크기
속도와 메모리 사용량
다양한 프로토콜에 넣을 수 있는 유연성
수년간의 공개 분석을 견딜 수 있는 성숙도

즉, 격자가 선택된 이유는
“대안이 없어서”가 아니라
여러 현실 조건을 동시에 만족시키는 드문 후보였기 때문입니다.

왜 격자인가 1: 보안성만이 아니라 효율성이 좋다

격자 계열은 현재까지 알려진 후보 중
일반 목적 공개키 암호로서 효율성이 매우 좋다는 강점을 보여 주었습니다.

좀 더 직설적으로 말하면 이렇습니다.

보안성만 높은데 너무 느리면 표준이 되기 어렵고
효율성만 좋은데 분석이 약하면 더 어렵습니다

격자 기반은
바로 이 균형에서 강점을 보였습니다.

예를 들어 PQC에서 자주 말하는 LWE, Ring-LWE, Module-LWE는
서로 구조화 정도가 다르지만
공통적으로 “격자 기반 보안”과 “구현 효율”의 균형을 노린 설계입니다.

LWE: 가장 일반적인 형태에 가깝고 설명의 출발점이 됨
Ring-LWE: 다항식 환 구조를 써서 계산 효율을 높임
Module-LWE: 일반성과 효율성 사이에서 더 좋은 균형을 노림

즉, 격자 계열은
그냥 안전해 보여서가 아니라
현실적인 키 크기, 계산량, 구현성까지 함께 고려했을 때 경쟁력이 있었기 때문에 채택되었습니다.

왜 격자인가 2: 수학적 확장성이 크다

격자의 더 큰 강점은
단순한 키 교환이나 서명만 되는 것이 아니라는 점입니다.

RSA나 ECC는
공개키 암호 primitive로는 강력했지만,
동형암호처럼 암호문 계산까지 자연스럽게 확장되지는 않습니다.

반면 격자는
다음과 같은 방향으로 뻗어 나갑니다.

KEM
전자서명
동형암호
threshold 구조
일부 다자 연산 구조와의 결합

즉, 격자는
“양자 시대 공개키 대체”라는 문제뿐 아니라
고급 암호 기능을 만드는 공통 바닥재 역할을 합니다.

이것이 동형암호와 PQC가
둘 다 격자로 수렴하는 가장 중요한 이유 중 하나입니다.

왜 격자인가 3: 동형암호는 아예 격자 없이는 설명이 어렵다

이 지점에서
동형암호를 따로 봐야 합니다.

PQC는
기존 공개키 암호를 바꾸는 문제입니다.

하지만 동형암호는
그보다 훨씬 더 어려운 문제를 풉니다.

암호문 상태로 덧셈과 곱셈을 반복해야 합니다.

이 기능을 가능하게 하려면
단순한 “어려운 문제”만으로는 부족합니다.
연산 구조 자체가 암호문 위에서 자연스럽게 닫혀 있어야 하고,
잡음 관리와 파라미터 설계도 가능해야 합니다.

바로 여기서 격자가 강합니다.

동형암호에서 자주 언급되는 대표 스킴만 봐도 그렇습니다.

BFV: 정수 기반의 정확 계산에 적합
BGV: 정수 연산과 잡음 관리 측면에서 중요한 고전 계열
CKKS: 실수·벡터 기반 근사 계산에 적합해 AI/통계에 자주 연결됨
TFHE: 부트스트래핑을 매우 짧은 회로 연산 단위에서 빠르게 처리하는 방향으로 발전

이 스킴들은 서로 쓰임새가 다르지만,
공통적으로 격자 기반 구조 위에서 잡음을 관리하고 암호문 연산을 설계한다는 점에서 만납니다.

즉, 동형암호가 격자를 고른 것은
단지 PQC와 비슷한 이유가 아니라,
암호문 연산을 설계하기 가장 유리한 수학적 구조 중 하나였기 때문입니다.

이 점에서 동형암호의 격자 선택은
소극적 안전성보다
기능 구현상의 필연성에 더 가깝습니다.

그럼 정말 이유는 “양자 알고리즘이 오래 걸릴 것 같아서”인가

부분적으로는 맞습니다.

암호학은 언제나
현재 알려진 최선의 공격을 기준으로 설계합니다.

즉,
“지금 알려진 범위에서는 격자가 가장 믿을 만하다”는 판단은 분명 들어 있습니다.

하지만 그 말은
“오래 걸릴 것 같으니 일단 쓰자”와는 다릅니다.

더 정확한 표현은 이렇습니다.

격자는 현재 알려진 공격 모델에서 가장 넓게 버티면서,
동시에 실제 제품에 넣을 수 있을 만큼 효율적인 기반으로 평가받고 있다.

즉,
시간 벌기용 임시 선택이라기보다
현재까지는 가장 현실적인 장기 후보에 가깝습니다.

그래도 불안 요소는 있다

여기서 너무 낙관하면 안 됩니다.

격자가 강력한 후보인 것은 맞지만,
암호학은 본질적으로 “안전이 영원히 증명된 기술”이 아닙니다.

이 점에서 중요한 것은
격자 집중이 장점이자 위험이라는 사실입니다.

장점

공통 수학 기반 덕분에 연구와 구현 경험이 축적됩니다
하드웨어 가속, 파라미터 분석, 보안 평가가 서로 도움을 줄 수 있습니다
양자 시대 고급 암호 생태계를 하나의 축으로 묶기 쉽습니다

부담

만약 격자에 대해 예상 밖의 큰 돌파가 나오면
여러 기술이 동시에 흔들릴 수 있습니다
그래서 backup 알고리즘과 다변화가 필요합니다
특정 분야는 lattice 외 계열 후보도 계속 유지해야 합니다

즉,
격자 집중은 효율적이지만
동시에 단일 기반 위험을 키울 수도 있습니다.

그래서 실무적으로도
“격자가 주류다”와
“격자만 있으면 된다”는 전혀 다른 말입니다.

비교하면 더 분명하다

질문	짧은 답	더 정확한 답
왜 PQC가 격자를 많이 쓰는가	양자 알고리즘이 아직 없어서	보안성, 효율성, 구현성, 분석 축적이 모두 좋기 때문
왜 동형암호도 격자를 쓰는가	PQC와 비슷해서	암호문 연산 구조를 만들기 가장 유리한 수학적 기반 중 하나이기 때문
그럼 격자는 영원히 안전한가	아니다	현재까지는 가장 강한 후보지만, backup과 다변화는 계속 필요하다
이 선택은 임시방편인가	아니다	현재 기준으로는 가장 현실적인 장기 후보에 가깝다

격자를 이해하면 왜 PQC와 FHE를 함께 이해하게 되는가

이 시리즈에서 중요한 포인트는
동형암호와 PQC가 단지 “같은 수학을 쓴다”는 수준에서 끝나지 않는다는 점입니다.

격자를 이해하면
다음 두 흐름이 함께 보입니다.

1) PQC의 관점

왜 RSA/ECC 이후 후보가 필요한가
왜 KEM과 서명이 lattice 쪽으로 많이 기울었는가
왜 efficiency가 표준화에서 결정적이었는가

2) FHE의 관점

왜 암호문 연산이 가능한 구조가 중요한가
왜 잡음 관리가 핵심인가
왜 CKKS, BFV, TFHE 같은 스킴이 서로 다른 목적을 가지는가

즉,
격자는 양자 시대 공개키 대체와 고급 암호 기능 구현을 함께 잇는 공통 문법에 가깝습니다.

이 점에서 격자는
단순한 한 문제의 답이 아니라
양자 시대 암호학의 중심 언어처럼 작동합니다.

실무자가 기억해야 할 포인트

이 질문을 실무적으로 정리하면 다음과 같습니다.

격자는 단지 “양자 알고리즘이 아직 없어서” 쓰이는 것이 아니다
PQC에서는 보안성과 성능의 균형 때문에 격자가 강하다
동형암호에서는 기능 구현 자체 때문에 격자가 거의 필수 축에 가깝다
Ring-LWE, Module-LWE 같은 구조화된 격자는 효율성을 끌어올리는 핵심 아이디어다
다만 lattice 집중은 장점과 함께 단일 기반 위험도 만든다
그래서 backup 알고리즘과 암호 민첩성은 계속 중요하다

결론

동형암호도 PQC도
왜 모두 격자를 택했는가.

가장 짧은 대답은
“양자 알고리즘이 아직 없기 때문”일 수 있습니다.

하지만 그 대답은 충분하지 않습니다.

더 정확한 답은 이렇습니다.

격자는 아직 안 깨진 수학이기만 한 것이 아니라,
현재까지 알려진 후보들 가운데
보안성, 효율성, 구현성, 확장성을 가장 잘 함께 만족시키는 기반이기 때문입니다.

즉,
동형암호와 PQC가 격자로 만나는 것은
우연도 아니고, 단순한 임시방편도 아닙니다.

그만큼 격자가
양자 시대 암호학의 중심 바닥재 역할을 하고 있다는 뜻입니다.

그리고 이 점은
실무자에게도 분명한 시사점을 줍니다.

실무 시사점

격자를 공부하면 PQC와 FHE를 함께 이해할 수 있다
두 분야가 서로 다른 시장에 있어도, 수학적 공통 기반은 깊게 연결돼 있습니다.
격자는 현재 최선의 공통 기반이지만, 유일한 미래는 아니다
표준과 제품은 계속 lattice 중심으로 움직이겠지만, backup과 다변화도 함께 봐야 합니다.
‘아직 안 깨졌다’보다 ‘왜 이렇게 많이 쓰이는가’를 이해하는 것이 더 중요하다
그래야 PQC의 표준화, FHE의 확장, NIST의 행보를 한 흐름으로 볼 수 있습니다.

그래서 지금의 결론은
낙관도, 비관도 아닌 이것이어야 합니다.

격자는 현재 최선의 선택이지만,
암호학은 언제나 “현재 최선” 위에 서 있는 분야다.

그리고 2026년 현재,
그 “현재 최선”의 가장 중요한 공통 기반이
바로 격자입니다.