Introduction to Homomorphic Encryption

1) 동형암호란?

• 미래 컴퓨팅 환경: 완벽한 하인!
  • 우리가 하려는 일의 비밀을 알지 못한 채, 빠르고 정확하게 대신 수행하는 컴퓨터
  📘 사례 모음집

  • 사례 1: 개인 클라우드 - 데이터를 맡기되, 비밀은 지키기 (대칭키 동형암호)
    • 스토리지 클라우드: Dropbox, Google email/calendar, NAS
      • 사용자는 데이터를 암호화하여 저장하지만, 클라우드는 복호화 키를 모름
        → 그래도 사용자는 평문처럼 검색하거나 접근 가능함
      • 단순한 대칭키 암호는 서버가 데이터를 전혀 활용할 수 없지만, 대칭키 동형암호를 사용하면 암호문 상태에서도 검색·분석이 가능
        → 예: 스팸 필터링, 파일 이름 검색 등
    • 계산 클라우드: DNA 계산, 헬스케어, 개인성향분석을 통한 추천
      • 개인의 민감한 데이터를 암호화한 채 클라우드에 맡겨 계산 가능
      • 복호화 키는 오직 데이터 소유자가 보유
        → 이러한 형태의 계산을 대칭키 동형암호라고 함
  • 사례 2: 다수 사용자 통계분석 - 데이터를 공유하되, 통제는 유지하기
    • 개인정보기반 마케팅 (구글, 페이스북, 네이버 등)
      • 사용자의 데이터가 허용된 범위 내에서만 활용되도록 제한 가능
        → 예: 내가 ‘광고에 사용’ 옵션을 허용한 경우에만 마케팅 분석 수행
      • 동형암호를 통해 ‘데이터는 사용하되, 직접 보지는 못하게’ 할 수 있음*
    • 정부 데이터베이스: 교육, 의료, 납세
      • 기관 간 민감 데이터 교류시, 동형암호 기반 연산으로 프라이버시 보장 가능
• 동형암호 (Homomorphic Encryption, HE)
  • 복호화 없이도 연산이 가능한 암호화 기술, 즉 데이터를 보지 않고도 계산할 수 있는 암호
  📘 참고. 영지식 증명 (Zero-Knowledge Proof, ZKP)

  • 2017년, 영지식 (Zero-Knowledge) SNARG 계산 증명 기술 등장
    • 연산 결과를 직접 공개하지 않고도 “올바르게 계산되었음”을 증명할 수 있음
    • 즉, 비밀은 보호하면서도 신뢰를 확보하는 기술
      → 대표 활용: 블록체인 개인정보 보호, 신원 인증, 거래 검증

• 동형암호의 장·단점
  • 장점: 튜링완전성 (Turing-Complete)
    • 암호화된 상태에서 AND, OR, NOT 연산이 모두 가능하다. 즉, 컴퓨터가 수행할 수 있는 모든 연산 (검색·통계처리·머신러닝)을 암호화된 데이터 위에서 수행할 수 있다.
      → 따라서 데이터 유출 위험을 원천 차단할 수 있다.
  • 단점
    • 암호문 크기 확장: 평문 대비 약 $10$ ~ $100K$배 (대칭키 방식은 약 $0.1$ ~ $1K$ 배 수준)
    • 암·복호화 속도 저하: AES ≈ $1 us$, RSA ≈ $1 ms$, HE ≈ 수십 $ms$
    • 암호문 연산 속도 저하: 특히 곱셈 연산은 평문 계산 대비 수백 배 이상 느림
    • 응용별 성능 편차: 연산의 종류 (덧셈·곱셈·비교)에 따라 속도 차이가 크며, 효율을 높이기 위해 개별 최적화 알고리즘 및 구현 기술이 필요함
      📘 예시 (복잡도 관점의 단순 모델)

      - 128-bit 보안을 만족하기 위해 키 크기를 50배 늘린다고 가정하면, 계산량은 일반적으로 O(n^2) 복잡도를 가지므로 $50^2x = 2,500x$ 배 증가하게 된다.

      - 그러나 빠른 곱셈 알고리즘 (Fast Multiplication)을 적용하면 복잡도는 O(nlog n) 수준으로 개선되어 $(50 \log 50)x ≈ 2,000x$ 배 정도로 줄어든다.

      👉 따라서, 키 길이를 $50$배 늘려도 계산량은 약 $2,000$배 증가하게 된다. 즉, 보안 강도를 높이는 것은 필연적으로 연산 비용 증가를 수반한다.

      - 물론 위 계산은 최적화가 잘 이루어진 경우를 가정한 것이다. 실제로는 알고리즘과 구현 수준에 따라 성능 편차가 크며, 이러한 최적화(optimization)는 인공지능이 아니라 사람이 직접 설계해야 한다. 다시 말해, 알고리즘적·구현적 튜닝이 부족한 경우에는 여전히 수천 배에서 수만 배까지 느린 사례도 존재한다.

2) 동형암호의 종류

• 정수 기반 동형암호 (Integer-based HE scheme) - 대칭키 방식
  동형암호의 초기 형태는 정수 연산 기반으로 설계되었습니다. 대표적으로 RAD PH와 DGHV 스킴이 있습니다.

  • RAD PH Scheme
    • 키 생성
      • Secret Key: large prime $p$
      • Public Key: $n = p q_0$, $q$는 임의의 자연수
    • 암호화 (Encryption) : $Enc(m) = m + p q \pmod{n}$
    • 복호화 (Decryption) : $Enc(m) \pmod p = m$
      👉 Quadratic Complexity - O(λ²) in the bit-length of modulus n
    • 덧셈 연산
      \(Enc(m_1) + Enc(m_2) = (m_1 + p q_1) + (m_2 + p q_2) = (m_1 + m_2) + p(q_1 + q_2) = Enc(m_1 + m_2)\) 👉 (m_1 + p의 배수) + (m_2 + p의 배수)로 생각하기!
    • 곱셈 연산
      \(Enc(m_1) * Enc(m_2) = (m_1 + p q_1) * (m_2 + p q_2) = (m_1 * m_2) + p(q_1 + q_2) = Enc(m_1 * m_2)\)
    📘 결과: RAD PH의 장·단점

    RAD PH는 구조가 단순하고 연산이 빠르며, 암호문 상태에서 덧셈·곱셈을 수행할 수 있다는 장점이 있다. 그러나 실전에서는 평문-암호문 쌍 공격과 곱셈 반복에 따른 잡음 누적 문제로 인해 그대로 사용하기엔 취약하다.

    핵심 취약점

    • 평문-암호문 쌍에 취약: 암호문이 m + p·q 형태라 몇 개 쌍만 알면 p를 추정할 수 있다.
    • 추측(guessing) 공격: 사람 문장은 패턴이 있어 일부만으로도 공격 실마리가 된다.
    • 곱셈 반복 시 잡음 급증: 교차항과 p^2 항이 생겨 복호 실패 위험이 커진다.

    결론: 효율 ↔ 안전성의 절충이 필요하다. Gentry의 부트스트래핑은 잡음을 관리해 반복 연산을 가능하게 했지만, 설계·파라미터·비용 문제가 남는다. 따라서 RAD PH 수준의 단순 정수 스킴은 "개념적으로는 멋지지만, 실제 보안 요구를 만족시키기엔 추가 보강이 필수"다.

  • DGHV HE scheme (on $\mathbb{Z}_{2}$)
    • 암호화 : $Enc(m) = m + 2e + p q$
      • $m \in {0,1}$: 메시지 비트
      • $e$: 작은 노이즈 (error term)
      • $p, q$: 큰 정수
      • 핵심 아이디어
        DGHV는 RAD PH와 달리 암호문에 작은 노이즈 $e$를 추가한다.
        따라서 공격자가 평문을 어느 정도 추측하더라도, 노이즈까지 함께 복원하지 못하면 암호문 구조를 직접 이용한 공격이 어려워진다.

    • 동형성
      DGHV 역시 암호문 상태에서 덧셈과 곱셈을 지원한다.
      따라서 복호화 결과는 각각 평문의 덧셈 및 곱셈에 대응한다.

    • 한계
      문제는 연산, 특히 곱셈을 반복할수록 노이즈가 증가한다는 점이다.
      노이즈가 일정 수준을 넘으면 복호화가 실패하므로, 초기 스킴은 계산 가능한 깊이(multiplicative depth)가 제한된다.

    • 암호문 크기가 커지는 이유
      여러 번의 곱셈을 지원하려면 중간 계산 과정에서 증가하는 노이즈와 비트 길이를 감당할 여유 공간이 필요하다.
      이 때문에 동형암호는 일반 암호보다 훨씬 큰 암호문 크기를 갖게 된다.

    • 특징
      • 양자 컴퓨팅에 대해 안전 (Post-Quantum Secure)
      • 정수 기반 대신 다항식 링 구조를 사용하는 고도화된 확장 버전 존재:
        $R_q = \mathbb{Z}_q[x] / (x^n + 1)$
    • ✅ 의의:
      DGHV는 Craig Gentry의 Fully Homomorphic Encryption (FHE)의 초기 형태로, “잡음을 제어하며 연산을 확장하는” 아이디어의 기반이 되었다.
    📘 왜 DGHV가 RAD PH보다 더 안전한가?

    DGHV에서는 암호문이 $m + 2e + pq$ 형태이므로, 공격자는 평문 $m$뿐 아니라 작은 노이즈 $e$까지 함께 고려해야 한다. 따라서 RAD PH처럼 단순한 평문-암호문 대응만으로 secret structure를 추정하기가 훨씬 어려워진다.

    이 계열의 안전성은 Approximate GCD 문제와 관련되며, 이후 격자 기반 난제와의 연결성도 연구되었다.

    📘 noise와 bootstrapping의 의미

    DGHV에서 가장 큰 제약은 곱셈이 반복될수록 노이즈가 커진다는 점이다.
    따라서 암호문은 처음부터 어느 정도의 계산 여유를 갖도록 크게 설계되어야 한다.

    하지만 계산 깊이가 계속 증가하면 결국 복호화가 불가능해진다.
    Gentry의 핵심 아이디어는 이 한계를 넘기 위해, 복호화 회로 자체를 암호문 위에서 다시 평가하여 노이즈를 줄이는 bootstrapping을 수행하는 것이었다.

    즉, bootstrapping은 암호화된 상태를 “다시 사용 가능한 상태”로 정리해 주는 과정이라고 볼 수 있다.