Homomorphic Encryption - HEaaN

To be continued …

To be continued …

1) Overview

Reference: Extended Euclidean Algorithm Tutorial

2) 모듈러 산술 (Modulo Arithmetic)

• Modulo Division (모듈러 나눗셈)
  • 모듈러 산술에서의 나눗셈은 일반적인 수학적 나눗셈과는 다르다. (엄밀히 말하면, 모듈러 나눗셈은 존재하지 않는다.) 왜냐하면 모듈러 연산 자체가 이미 나머지를 구하는 일종의 나눗셈이기 때문이다.

  • 하지만 어떤 수 $b$를 $a$로 “모듈러 나누기” 하고자 한다면, 이는 곧 $a$의 모듈러 역원 (modular inverse)을 이용한 곱셈으로 표현할 수 있다. \(b \div a \bmod q \; \equiv \; b \cdot a_{*}^{-1} \bmod q\)
    즉, 모듈러 나눗셈(modulo division)은 모듈러 곱셈 (modulo multiplication)으로 정의된다.

    📍 중요한 차이점:

    • 일반적인 나눗셈은 실수(real number)를 결과로 내지만,
      모듈러 나눗셈은 항상 정수(integer)를 결과로 낸다.
      (이는 $b$와 $a_{*}^{-1}$ 모두 정수이기 때문)
  • 마지막으로, 정수 $a$의 모듈러 역원은 확장 유클리드 알고리즘 (Extended Euclidean Algorithm)을 이용해 계산할 수 있다.
• 중심 잔여 표현 (Centered Residue Representation)

  • Canonical은 0부터 시작하는 잔여계, Centered는 0을 기준으로 대칭인 잔여계다

    지금까지 잔여(나머지, Residue)를 양의 정수(positive integer)라고 가정했다.

    • 모듈러 $q$에서 가능한 나머지 집합은 다음과 같다.
      \({0, 1, 2, \dots q-1}\)

      → 이 표현 방식을 표준 잔여계(canonical residue system) 또는 비부호형 잔여 표현 (unsigned residue representation) 이라고 부른다.

      🔸 하지만 또 다른 표현 방식도 존재한다.
      바로 부호형 잔여계 (signed or centered residue system) 로, 잔여들이 0을 중심으로 대칭되게 분포한다. \({-\frac{q}{2}, -frac{q}{2}+1, \dots, 0, \dots, frac{q}{2}-2, \frac{q}{2}-1}\)

      → 비부호형 잔여계나 부호형 잔여계 모두 잔여의 개수는 동일하게 $q$개이다. 차이는 단지 잔여 범위의 기준점(upper/lower bound)에 있다.

      표현 방식	잔여 집합	하한(lower bound)	상한(upper bound)
      Canonical (Unsigned)	$\{0, 1, 2, \dots, q-1\}$	0	$q-1$
      Centered (Signed)	$\{-\frac{q}{2}, \dots, 0, \dots, \frac{q}{2}-1\}$	$-\frac{q}{2}$	$\frac{q}{2}-1$

      💡 모듈러 연산의 역할
      모듈러 연산은 주어진 값을 위 두 시스템 중 하나의 잔여 범위로 변환한다.

      • 값이 상한보다 크면 → 모듈러스 $q$를 빼준다
      • 값이 하한보다 작으면 → 모듈러스 $q$를 더해준다

      → 따라서 두 시스템의 차이는 단지 잔여의 “표현 방식”일 뿐, 모두 동일한 모듈러 집합 $\mathbb{Z}_q$를 나타낸다.

      \[\mathbb{Z}_q = \{0, 1, 2, \dots, q - 1\}\]

  • Canonical과 Centered 잔여계는 모든 연산 성질이 동일하게 유지된다.

    표준 잔여계(canonical system)와 중심 잔여계(centered system)는 덧셈 $\cdot$ 뺄셈 $\cdot$ 곱셈 $\cdot$ 나눗셈의 모든 모듈러 성질은 동일하게 성립한다.

    \[(a \pm b) \bmod q, \quad (a \times b) \bmod q, \quad (a \div b) \bmod q\]

    → 이들이 어떤 잔여계에서 계산되든 결과의 동치 관계는 변하지 않는다.

    💡 이유:
    두 시스템 모두 같은 모듈러스 $q$를 사용하기 때문에,
    어떤 두 동치 잔여(congruent residues)라도 서로 $kq$의 차이를 가진다.
    즉,
    \(a \equiv b \pmod q \quad \Rightarrow \quad a - b = kq \quad (k \in \mathbb{Z})\)

    → 따라서 canonical 표현이든 centered 표현이든, 각 연산의 결과는 항상 같은 동치류(congruence class)에 속하게 된다.

  • Canonical과 Centered 잔여계의 연산 성질 중 역원도 동일하게 유지된다.

    모듈러 $q$에서 $a$의 역원은 다음을 만족한다.

    \[a \cdot a^{-1} \equiv 1 \pmod q\]

    🔹 부호형(signed) 잔여 표현을 사용하는 이유는 특정 상황에서 모듈러 연산을 생략할 수 있을 정도로 계산을 단순화할 수 있기 때문이다.

  ---

  #### 🧩 예제 1. Canonical (Unsigned) Representation 표준 잔여계에서는
  \((a + b) \bmod q\) 의 형태를 가정하자.
  만약 어떤 애플리케이션에서 항상 $0 \le a + b \le q - 1$ 이라는 조건이 보장된다면,

  \[(a + b) \bmod q = a + b\]

  따라서 모듈러 연산을 생략할 수 있다.
  (즉, 값이 잔여 범위 $[0, q-1]$를 벗어나지 않기 때문)

  ---

  #### 🧩 예제 2. Centered (Signed) Representation 이번에는 중심 잔여계에서
  \((a - b) \bmod q\) 를 생각하자.
  만약 $a - b$가 항상 $[-\frac{q}{2}, \frac{q}{2} - 1]$ 범위 안에 있다면,

  \[(a - b) \bmod q = a - b\]

  이때도 모듈러 연산을 생략할 수 있다.

  ---

  #### ⚠️ 주의: Canonical 표현에서의 뺄셈 만약 위와 같은 $(a - b) \bmod q$ 연산을 canonical 표현으로 계산한다면,
  $a - b$가 음수일 경우 그 값은 하한(0)보다 작아진다.
  이 경우 모듈러스 $q$를 하나 이상 더해주는(modulo reduction) 보정이 필요하다.

  예를 들어,
  \(a = 3, \quad b = 7, \quad q = 11\)
  이면
  \((a - b) \bmod 11 = (3 - 7) \bmod 11 = (-4) \bmod 11 = 7\)

  ✅ 정리:

  • canonical 표현: 음수가 되면 반드시 모듈러 보정 필요
  • centered 표현: ±범위 안이면 모듈러 보정 없이 연산 가능

  즉, 부호형(centered) 잔여 표현은 덧셈보다 뺄셈 연산에서 더 직관적이며 효율적이다.

  • §D-5.8 절에서는 centered residue representation의 유리한 성질을 활용하여 FastBConvEx 연산(Fast Balanced Convolution Extension) 을 설계한다.

    • 이 알고리즘에서는 다음과 같은 관계가 성립한다.
    \[(\mu + u) \bmod b^{\alpha}\]

    일반적으로는 모듈러 연산이 필요하지만,
    이때 $\mu + u$가 항상 centered residue 범위 내에 존재함이 보장된다.

    \[-\frac{b^{\alpha}}{2} \leq \mu + u < \frac{b^{\alpha}}{2}\]

    따라서, \((\mu + u) \bmod b^{\alpha} = \mu + u\)

    즉, 모듈러 연산을 생략하고 단순 덧셈으로 표현할 수 있다.
    이는 연산을 간소화하고 계산 효율을 높이는 핵심 아이디어이다.

    💡 핵심 포인트:

    • centered residue 표현을 사용하면,
      값이 잔여 범위를 벗어나지 않는 한 모듈러 처리가 불필요하다.
    • 이 특성은 고속 암호 연산(예: FastBConvEx) 설계 시
      불필요한 나머지 계산을 제거하여 성능을 최적화하는 데 사용된다.

  </div>

</details>

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$
    • 암호화 (Encryption) : $Enc(m) = m + p q \pmod{n}$
    • 복호화 (Decryption) : $Enc(m) \bmod p = m$

    • 덧셈 연산
      \(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)\)

    • ✅ 결과:
      평문 덧셈이 암호문 덧셈으로 보존되므로 부분동형(ADD-homomorphic) 속성을 가진다.
      그러나 INSECURE — 잡음(noise) 누적과 키 복원 공격에 취약하다.
  • DGHV HE scheme (on $\mathbb{Z}_{2}$)
    • 암호화 : $Enc(m) = m + 2e + p q$
      • $m \in {0,1}$: 메시지 비트
      • $e$: 작은 노이즈 (error term)
      • $p, q$: 큰 정수
    • 특징
      • 양자 컴퓨팅에 대해 안전 (Post-Quantum Secure)
      • 정수 기반 대신 다항식 링 구조를 사용하는 고도화된 확장 버전 존재:
        $R_q = \mathbb{Z}_q[x] / (x^n + 1)$
    • ✅ 의의:
      DGHV는 Craig Gentry의 Fully Homomorphic Encryption (FHE)의
      초기 형태로, “잡음을 제어하며 연산을 확장하는” 아이디어의 기반이 되었다.

  </div>

</details>