완전동형암호와 진정한 프라이빗 인터넷의 시작

• 완전동형암호(FHE) 는 데이터를 복호화하지 않고도 암호문 상태로 연산을 수행할 수 있는 기술
• 현재 FHE는 여전히 저조한 실용성과 1,000배~10,000배의 연산 속도 저하, 40배~1,000배의 저장공간 증가 등 한계를 지님
• 하지만 최근 FHE 알고리듬은 매년 8배씩 속도 향상을 이루고 있으며, 곧 클라우드 컴퓨팅, LLM 추론, 블록체인 스마트컨트랙트 등에서 실용영역에 진입할 가능성 있음
• FHE가 보편화된다면, 컴퓨팅 환경 전반에서 데이터 프라이버시가 기본값이 되는 산업적 변화를 촉진할 것임
• 격자 기반 암호, LWE, 부트스트래핑 등 핵심 개념들과 FHE 알고리듬 발전사, 실제 구현 예시 및 성능 개선 추이 등을 종합적으로 다룸

---

서론: 완전동형암호란 무엇인가

• 완전동형암호(Fully Homomorphic Encryption, FHE)는 복호화 없이 암호문 상태에서 임의의 연산을 가능하게 해, 실제로 암호화된 데이터에 그대로 연산을 수행할 수 있는 방식
• 즉 서버가 평문을 모른 채로도 질문과 결과를 계산하여 전달할 수 있음
• 이 기술은 오늘날의 여러 실세계 시스템에 실제 도입되고 있음

FHE의 잠재력과 한계: "FHE의 무어의 법칙"

• FHE는 네트워크 상에서 데이터를 지속적으로 암호화된 상태로 유지할 수 있어, 데이터 유출 위험을 원천적으로 차단하는 완전한 프라이버시를 실현할 수 있음
• 그럼에도 불구하고 현재 실용화에 제약이 많은 이유는, 암호문 연산이 평문 연산에 비해 1,000~10,000배 느리고, 저장공간도 대략 40~1,000배 증가하는 등의 현격한 성능 저하가 있기 때문
• 이는 1990년대 인터넷 초창기와 유사함
• 그러나 최근 FHE는 매년 8배씩 빨라지고 있어, 곧 여러 실용 영역에 진입할 것으로 전망됨

임계점: 곧 다가오는 FHE 실용화

• 이와 같은 속도의 비약적 발전이 지속된다면, 앞으로는 다음과 같은 분야에서 FHE가 실용화될 수 있음
  • 암호화된 클라우드 컴퓨팅
  • 암호화된 LLM 추론
  • 비밀보장이 가능한 블록체인 스마트컨트랙트
• 이런 변화는 사용자 데이터 수집 기반 인터넷 비즈니스 모델을 근본적으로 뒤흔들 수 있음
• FHE로 인해 "감시가 기본"인 인터넷에서 "프라이버시가 기본"인 인터넷으로의 본질적 전환이 기대됨

데이터 보안의 아킬레스건과 FHE의 해결책

• 데이터는 3가지 상태(저장, 전송, 사용) 중 '사용 중' 상태에서 복호화가 되어 보안 취약점이 되곤 함
• 클라우드, 내부자, 해커, 취약한 CPU 등 누구나 메모리 내 평문 데이터에 접근 가능
• 대형 데이터 유출 사고 역시 대부분 '사용 중' 또는 '저장 중'에 발생
• FHE는 데이터를 전체 라이프사이클 동안 암호화 상태로 유지해 이러한 취약점을 근본적으로 해소

완전한 프라이버시 컴퓨팅 정의

• 이상적 환경은 데이터가 저장 시, 전송 시, 사용(연산) 시 모두 암호화를 유지함
• 예를 들어, 서버는 평문 질문을 전혀 보지 못하며, 암호화된 질문을 입력받아 암호화된 결과만 반환
• 오로지 사용자만이 그 결과를 복호화 할 수 있음

FHE의 동작 방식: 수학적 구조와 개념

• "동형"은 동일 구조를 보존하는 수학적 변환(예: 푸리에 변환과 유사)에 기반함
• FHE는 평문 공간과 암호문 공간을 쌍방향으로 변환해, 암호문 연산 결과의 복호화가 곧 평문 연산 결과와 같음
• 이런 변환에는 주로 격자 기반 암호와 LWE(오차 학습 문제) 가 사용됨
  • 격자 기반 암호는 매우 높은 차원에서의 벡터 문제로, 양자컴퓨터마저 풀기 어렵다고 알려져 있음(양자 내성)
  • LWE는 노이즈가 섞인 선형 시스템을 역산하는 문제로, 현실적으로 해독이 불가함

노이즈 관리와 부트스트래핑

• FHE에서 연산을 거듭할수록 암호문 내 노이즈(잡음) 가 증가함
• 덧셈 연산에서는 선형적으로, 곱셈에서는 기하급수적으로 커져, 결국 복호화 불능이 되는 문제가 있음
• 이를 해결하는 핵심 기술이 부트스트래핑이며, 이는 암호문을 '새 공용키'로 재암호화하며 노이즈를 일정 수준으로 리셋하는 기법
• 이 과정이 FHE 시스템의 성능 병목이지만, 매년 빠르게 개선되고 있음

FHE의 추가 핵심 구성 요소

• 재선형화(relinearization): 곱셈 후 키 차수가 2차로 증가하는 문제를 해결해 다시 1차로 만드는 과정
• 모듈러스 스위칭(modulus switching): 노이즈 관리를 위해 암호문 모듈러를 축소하는 기법

이외에도 알고리듬 발전에 따라 다양한 테크닉들이 지속적으로 제시되고 있음

동형암호(HE) 체계의 분류와 파이썬 예제

• 부분동형암호(Partial HE): 하나의 연산만 지원(e.g. 파이에 암호는 덧셈만 지원)
• 일부동형암호(Somewhat HE): 덧셈, 곱셈 모두 지원. 단, 곱셈 반복 횟수 제한
• 완전동형암호(FHE): 덧셈, 곱셈 모두 무제한 지원. Turing 완전성 보장

파이썬으로 구현된 Paillier 암호 예제를 통해 부분 동형을 직관적으로 체험할 수 있음

FHE 발전 역사와 "FHE의 무어의 법칙"

• 1978년: 최초로 "프라이버시 동형사상" 개념 등장
• 2009년: Craig Gentry의 FHE 첫 실현(박사논문)
• 2011년: 최초 구현, 비트당 30분 소요(매우 느림)
• 2013년 이후: 부트스트래핑 수 ms 수준까지 단축
• 2017년: CKKS 등 부동소수점 근사 지원, ML/AI에 본격 도입

FHE 알고리듬은 2011년부터 매년 8배씩 개선되어, 초기 10¹⁰배 오버헤드에서 최근 10³~10⁴배 수준까지 도달함
최신 논문은 FHE 곱셈 처리량 1,000배, 지연시간 10배까지 감소시켰고, 하드웨어 가속화 결합시 추가로 1,000배 이상 속도 개선 여지 있음

암호화가 기본값이 되는 미래

• 대형 데이터 유출사고는 피할 수 없는 현실임
• FHE를 이용해 서버가 복호화 키 없이도 암호화된 데이터에 연산만 가능하다면, 프라이버시 보호의 새로운 기준이 될 것
• 아직 모든 영역에서 완전히 실용적이지는 않지만, 매해 놀라운 속도로 개선되고 있음
• 사용자의 프라이버시 요구와 관련 규제 강화가 맞물려, 결국 FHE가 대부분의 클라우드 컴퓨팅에 표준이 될 것으로 전망됨
• 미래의 인터넷 컴퓨팅은 언제나 암호화 상태로 진화할 것

2010년대: HTTPS가 기본값
앞으로: FHE가 기본값이 되는 시대가 도래할 것으로 예상

참고문헌 및 추가자료

• FHE Reference Library: 학술 자료 포괄적 정리
• Craig Gentry 2009 박사논문: FHE의 출발점
• Vitalik Buterin: FHE 심층 분석
• 커뮤니티: FHE.org (개발자 중심 허브)
• GitHub: awesome-he: 동형암호 관련 프로젝트 모음

[GN⁺]

Hacker News 의견

• FHE와 Cryptography를 굉장히 좋아하는 입장을 전제로 말하겠음. FHE가 점점 빨라지고는 있지만, 부트스트래핑에 의존하는 한 평문의 연산 속도를 따라잡을 수 없음을 이야기함. 부트스트래핑으로 인한 약 1000배 이상의 오버헤드는 근본적으로 피할 수 없으며, 더 빠르게 만드는 게 불가능하다고 깨닫자 하드웨어 가속 이야기가 나오기 시작했음. 하지만 LLM에 컴퓨팅 파워가 모조리 들어가는 요즘 시기엔 쉽지 않은 일임. FHE로 컴퓨팅할 때 단위 토큰당 비용이 몇 배로 뛸지 생각해보면, 1000배 이상이 아닌 이상 현실적으로 가능성이 거의 없음. 개인정보 보호 목적이라면 confidential computing 방식이 현재로선 유일하게 실용적인 대안임. 하드웨어를 신뢰해야 하는 점이 마음에 들진 않지만, 그게 우리가 가진 최선임

  • FHE를 임의의 연산에 쓰기 힘든 진짜 더 근본적인 이유가 있음. 바로 어떤 종류의 연산들은 평문보다 암호문에서 비정상적으로 복잡도가 커짐. 데이터베이스 검색의 경우, 평문에서는 O(log n)이지만, 암호화된 키로 검색하면 O(n)이 됨. 그래서 완전동형 Google 검색은 기본적으로 실현 불가능함. 하지만 완전동형 DNN 추론은 상황이 다를 수 있음

  • 부트스트래핑이 없어도 FHE는 평문 연산만큼 빠를 수 없음. 암호문이 평문보다 1000배 정도 더 큼. 즉, 메모리 대역폭과 연산량이 훨씬 더 많이 필요함. 이 격차를 좁힐 수 없음

  • 계산 비용이 1000배로 뛰더라도, 인증 가능한 프라이버시를 진짜 원하는 특정 수요층이 있지 않을지 생각해봄. Dropbox만큼 크진 않겠지만 어느 정도의 시장은 있다고 상상함

  • 예전에 모든 게 PCIE 확장 카드 시절이었음을 되짚어봄. GPU도 그랬고, 수학 코프로세서 같은 특수 가속기도 따로 있었음. 지금은 범용 하드웨어에 통합돼서 더 싸고 편하지만, 특정 기능에 최적화된 실리콘 칩만큼 잘할 순 없음. 그래서 AI/ML용 전용 카드를 GPU 기반 대신 따로 쓰자고 주장함. 아키텍처가 일부 중첩되지만 GPU에 기반한 AI 카드는 많은 부분에서 손해를 감수하는 셈임. 진짜 AI 가속기는 최신 SXM 소켓에 들어가는 전용 하드웨어라고 생각함. 하지만 SXM 소켓은 서버에만 있고 가격도 만만치 않음

  • LLM 열풍은 인정하지만, FHE를 쓸 만한 다른 용도가 정말 없을지 궁금함. 예를 들어, 고속이 필요 없는 트레이딩 알고리즘을 FHE로 서버에 호스팅해서 보안을 보장하는 방식도 생각해볼 수 있을 것 같음

• FHE가 중요한 이유는, 현재 기업들이 정부의 압박에 의해 특정 타겟의 암호화를 강제로 깨야 하는 경우가 있기 때문임. FHE는 기업이 "우리는 평문을 절대 못 본다"고 떳떳하게 말할 수 있게 해줌. 네트워크 캐리어 역할에선 E2E encryption 등으로 일부 가능하지만, 평문 상태에서 데이터 처리 시엔 아직 불가능함. 개인정보 보호는 기본 인권이라는 생각임. 정부의 권한은 민주주의적 활동(투표, 예술, 언론, 표현 등)에 대해 아주 제한적으로만 작동해야 함

• FHE로 임의 연산이 가능해도, 대부분의 서비스는 특정 데이터를 제공하기 때문에 쓰는 것임. 구글이 내 쿼리에 대해 보안을 보장하려면 전체 검색 인덱스를 암호화해야 하는데, 현실적으로 불가능함. 비즈니스적으로도 극소수의 고신뢰·고위험 분야 외에는 FHE 방식 서비스를 채택할 인센티브가 거의 없다고 봄

  • 내가 알기로 민감한 데이터만 암호화해도 됨(예: 내 은행 거래 데이터). 계산하려는 함수 자체는 암호화할 필요 없이, 공개 데이터와 결합해 사용할 수 있음

  • 결국 대형 기업 입장에선 사용자의 데이터나 쿼리를 직접 들여다봐야 수익원이 되기 때문에, FHE를 습관적으로 채택할 동기가 없음. 은행 등 금융 분야에선 쿨할 수 있지만, 그 외에선 언제 채택될지 미지수임

  • 인센티브 이야기는 맞음. 하지만 첫 부분은 다름. 평문 데이터베이스에 대한 프라이빗 조회(lookup)는 이미 몇 년 전부터 가능함. 다만, 평문 DB를 사전에 꽤 복잡하게 전처리하거나, 최악의 경우엔 전체 DB를 선형 스캔해야 함

  • 완전 비공개 검색엔진 FHE 구현체 예시로 spiralwiki.com을 소개함. 서버가 사용자가 어떤 위키피디아 문서를 읽는지 전혀 알 수 없는 방식임 spiralwiki.com

• "클라이언트 입장"에서 FHE처럼 데이터를 완벽히 보호할 서비스를 돈 주고 쓰려는 사람은 있겠지만, 실제로는 엄청나게 비쌀 거고 가입자는 극소수일 것임. 현재 대비 수십 배의 컴퓨팅 비용이 든다는 전제하에 계산해보면, 프라이버시 중심 구글 대체 서비스가 연 $100에 가능하다 쳐도 많은 가입자를 유치하긴 어려움. 비용이 올라갈수록 가입자는 더 줄어듦. Tor처럼 완벽하지 않아도 꽤 많은 보호를 무료로 제공하는 대안이 있음. HE(동형암호)가 쓸모가 없는 게 아니라, 아주 소수만이 비용을 감수하고 쓸 거라는 사실임

  • 지금 FHE 구글을 만든다고 치면 너무 느리고 비싸서 아무도 안 쓸 것임. 관건은 앞으로 컴퓨팅 속도가 어떻게 발전할까임. 만약 FHE가 평문 대비 1000배 느려도 하드웨어가 1000배 더 빨라진다면 비슷한 레벨이 될 수 있음. 미래 예측은 어렵지만, FHE가 유일하게 줄 수 있는 프라이버시라는 가치를 생각하면, 장기적으로는 디폴트가 될 수도 있음(10년 안엔 아니겠지만 50년 후엔 가능할지도). 과거 50년간 하드웨어 성능이 엄청나게 올라왔듯이. 물론 암호문 크기, 모델 전체 재암호화 필요 등 문제도 있음. 아직은 실용적인 적용 범위가 좁지만 앞으로 점차 넓어질 거라 믿음. 언젠가는 검색엔진과 LLM 분야도 포괄하게 될 것임

• 인터넷이 "기본이 감시"에서 "기본이 프라이버시"로 바뀔 수 있다는 생각이 언급됨. 나도 오래 전부터 디지털 서명을 만드는 등 프라이버시 기술을 확산시켜 왔음. 하지만 Hacker News나 Facebook이 모두의 아이덴티티를 쥐고 있는 현실을 봐야 함. 그게 너무 쉽고 돈이 되기 때문임. FHE 역시 "사람들이 원하지만 실질적으로 빠르게 널리 쓰이진 않는 기술"임. 운영 오버헤드와 복잡성 부담 때문에 대부분의 경우 기존 방식이 충분히 잘 동작한다고 보는 현상임

  • 이메일 말미에 디지털 서명 같은 걸 달면 "저게 뭐여?"라는 반응밖에 못 얻었음. 일반 사용자들이 클라이언트 암호화에 동참하도록 설득한 경험 있는지 궁금함

  • FHE와 AI가 결합될 때 복잡성 부담을 AI가 일부 떠안으면서, 진짜 널리 쓰일만한 킬러 조합이 될 수 있을지도 모른다는 의견임

• 실제로는 기업들이 FHE 서비스처럼 컴퓨팅 100만 배 더 쓰고, 디버깅도 어려우며, 사용 패턴 분석도 못하는 솔루션을 채택할 이유가 없을 거라고 봄

• 구글 사례로 이야기를 시작하는 건 오해를 부를 수 있음. 보통 "Google"하면 "웹검색"을 떠올리는데, 문서에서 설명하는 FHE는 입력값 전체가 하나의 키로 암호화돼야 한다는 점에서 검색 서비스와 맥락이 안 맞을 수 있음. 구글의 검색 인덱스는 수 TB에 달하는데, 이걸 전부 특정 키로 암호화하는 건 불가능하다고 봄. 즉, 사용자가 입력 전체를 통제할 때만 FHE가 쓸모 있음. 구글 레퍼런스는 혼란을 줌

  • Apple의 CallerID 같은 사례에서는 데이터베이스 전체를 사용자별로 암호화하는 게 꼭 필요한 것 같진 않음 Apple의 동형암호 연구 / Apple의 개인정보 보호 검색

  • 동형암호형 서비스는 애초에 암호화 키를 미리 알 필요가 없음. 그게 핵심임. 아주 단순한 암호화 예시로, 키 미지정 상태에서 암호문끼리 덧셈 결과를 낼 수 있는 구조를 소개함. 더 강력한 암호에 더 복잡한 연산까지 지원하면, 굉장히 다양한 기능을 구현할 수 있음

  • 구글하면 검색만 떠오르는 게 아니라 Gmail, Google docs 등 개인정보 관련 서비스도 많이 있음. 검색만 떠올리는 사람은 아마 관련 기사 자체를 안 읽을 것 같음

• FHE가 범용 컴퓨팅이나 인터넷 서비스에 곧바로 도입되긴 쉽지 않을 거라고 생각함. 적어도 무어의 법칙이 아주 여러 세대 더 지나야 가능해질 듯함. 하지만 이미 FHE가 빛을 내기 시작한 분야는 복잡성은 낮지만 보안과 신뢰 수준이 매우 중요한 스마트컨트랙트, 금융, 의료 쪽일 수 있음. 최근 Moore's law, 소프트웨어 최적화 덕에 곡선이 실용성 쪽으로 굽히기 시작했다고 판단됨. Zama의 하드웨어/Devtools 작업을 예시로 언급함

• E2EE git이 이미 개발되었음. 내가 만든 사람이 서버에서 protected 브랜치나 force push 방지 같은 요구를 해결 가능한지 물어봤지만, 클라이언트가 악의적이면 마땅한 대책이 없었음. 이게 언젠가 E2EE Github으로 발전할지도 궁금함 관련 Hacker News 링크

• FHE의 속도 향상이 계속될 것이란 담론을 듣다 보면, 평균속도에 관한 오래된 수학 문제가 떠오름. 예를 들어, 오르막 1마일 구간을 시속 15마일로 달린 다음, 내리막 1마일을 얼마나 빨리 가야 전체 2마일 평균속도가 30마일이 될까? 과거의 개선 속도가 미래 가능성을 보장하지 않음. 이건 물리적 한계가 아니라 알고리즘 한계임

  • 내리막이 절벽이라면 어쩔까? 자동차의 터미널 속도가 200-300mph 정도라 계산하면 1마일을 자유낙하로 15초 만에 주파하는 것도 계산상 가능할 수 있음. 전체 2마일을 평균 30mph로 가려면 4분이 걸리므로, 남은 시간에 맞춰 오르막 속도도 적절히 조정되겠지만, 실제론 여러 변수로 실현 불가능함

  • 엄밀히 계산하면 내리막에서 41mph만 내면 전체 평균이 30mph가 됨. 질문 자체에 수치 반올림이나 측정 오차가 개입됐다고 가정하면 이렇게 나옴