Homomorphic Encryption / Ring-LWE

2025. 9. 18. 20:10ㆍ개발/인공지능 보안

반응형

 

1. Homomorphism (동형사상)

  • 정의: 두 대수 구조(예: 군, 환, 체) 사이에서 연산을 보존하는 함수.
  • 예시
    • f(x)=2x,f:(Z,+)→(Z,+)→ 동형성 성립.
    • f(x)=2x,f:(Z,×)→(Z,×)→ 동형성 불성립.
    • g(x)=ex,g:(R,+)→(R+,×)→ 동형성 성립.

2. Homomorphic Encryption (동형암호)

  • 아이디어: 평문에서의 연산(+, ×) 결과를 암호문에서도 동일하게 수행할 수 있도록 보장.
    • Dec(Enc(m1) ⊛ Enc(m2)) = m1 ∗ m2
  • 비공식 정의: 암호화된 데이터 상태에서 사칙연산, 논리연산을 수행할 수 있는 암호화 기법.
  • 공식 정의
    • E=(KeyGen,Enc,Eval,Dec)
    • KeyGen: 키 생성
    • Enc: 평문 → 암호문
    • Eval: 암호문 연산
    • Dec: 암호문 → 평문

3. Correctness & Security

  • 정확성 (Correctness)
    • 복호화했을 때 원래 연산 결과와 다를 확률은 무시할 수 있을 만큼 작아야 함.
  • 보안성 (Security):
    • 최소한 IND-CPA (선택평문공격에 대한 안전성)을 만족해야 함.
    • 즉, 공격자가 두 평문 중 어느 것이 암호화되었는지 추측할 확률은 거의 50%를 넘지 않아야함.

IND-CPA(암호문 선택적합 공격 하의 구분불능성) 

공개키 암호(또는 대칭키의 경우에도 유사한 정의) 에서 자주 쓰이는 IND-CPA(암호문 선택적합 공격 하의 구분불능성) 보안의 수학적 표현입니다. 한국어로 한 줄 요약하면:

임의의 PPT(다항시간) 공격자 (A)에 대해, 공격자가 암호문으로부터 원문을 구분해낼 확률은 단순 무작위 추측(1/2) 보다 유의미하게 크지 않다 — 오차는 보안파라미터 ( λ )에 대한 무시가능 함수뿐이다.

여기서 각 기호 의미는 다음과 같습니다.

  • Pr⁡[⋅] : 확률
  • PubKA,ECPA(λ)=1:
    IND-CPA 게임(공개키 스킴 E, 보안파라미터 λ)에서 공격자 가 “승리”(즉 비트 를 정확히 맞춤)했음을 나타냄.
  • 1/2: 공격자가 아무 정보 없이 무작위로 맞출 확률(기저선).
  • negl(λ) : 무시가능 함수 — λ\lambda가 커지면 0에 급감하는 아주 작은 값.

IND-CPA 게임(흐름)

  1. 키 생성: (pk,sk)←KeyGen(1λ). 공개키 는 공격자에게 주어짐.
  2. 공격자 A는 두 동등 길이의 메시지 (m0,m1)를 출력.
  3. 챌린저는 무작위 비트 b∈{0,1}를 골라 c←Encpk(mb)를 생성해 공격자에게 줌.
  4. 공격자 A는 추가 연산(다항시간) 후 를 출력.
  5. 공격자가 b′=b이면 승리.
    보안 요구: 모든 PPT 에 대해 승률 ≤1/2+negl(λ).

직관

  • 공격자는 암호문만 보고 어느 메시지가 암호화되었는지 (즉 (m_0)인지 (m_1)인지) 유의미하게 알아냄으로써 이득을 얻을 수 없어야 한다.
  • 1/2은 ‘모르면 동전 던지기’와 같다는 뜻이고, negl(λ)는 그보다 조금 더 잘 맞출 수 있는 여유(허용 오차)가 아주 작다는 뜻입니다.

추가 메모

  • 공개키 암호의 IND-CPA는 semantic security(의미론적 보안)과 동치입니다.
  • 강한 보안 모델(예: IND-CCA)은 더 강한 게임 규칙(복호화 오라클 허용 등)을 요구합니다.

4. LWE (Learning With Errors) 기반 암호

  • LWE 문제: 선형 방정식에 작은 오차(error)를 섞어 비밀 값을 숨기는 문제.
  • LPR 암호화 (Lyubashevsky–Peikert–Regev): LWE 기반 대표적인 공개키 암호화 방식.
  • 한계: 공개키와 암호문 크기가 너무 큼 → 비효율적.

📌 LWE 기반 PKE (LPR Scheme)

KeyGen (1λ)

 

  • 파라미터 설정:
    • n=n(λ), q=q(λ), χ=χ(λ) (분포)
  • 비밀키: , sk=s
  • 공개키:
    • yT=sTA+eT(mod q)
    • pk=(A,yT)

Enc(pk, m ∈ {0,1})

  • 무작위 샘플: r, x←χn, x′←χ
  • 암호문: c=(a,b)=(Ar+x, yTr+x′+m⋅[q/2]​)(modq)

Dec(sk, c = (a, b))

  • 계산: v=b−sTa(mod q)
  • 복호화:
    • 그렇지 않으면 m=1

왜 동작하는가?

  • (b) 전개
    • b=yTr+x′+m*2/q​ = (sTA+eT)r+x′+m*2/q​ = sT(Ar)+eTr+x′+m*q/2
  • a=Ar+x이므로
    • sTa=sTAr+sTx
  • 따라서 차이는
    • b−sTa=m2q​+(eTr+x′−sTx)
  • 뒤쪽 항은 잡음(noise), 크기가 작아서 m*q/2를 구별할 수 있음.

보안성

  • LPR 스킴은 IND-CPA secure
  • 근거
    • yT=sTA+eT 구조는 LWE 샘플과 동일
    • 작은 secret s를 사용하는 small-secret LWE 가 어렵다는 가정 하에서 안전성 증명

✅ 정리하면, 이 스킴은

  • 공개키는 pk=(A,yT)
  • 암호문은 (a,b)
  • 복호화는 b−sTa 값이 근처냐 q/2 근처냐를 보고 판별합니다.
  • 보안성은 LWE 문제의 난이도에 기반합니다.

5. Ring-LWE (환 기반 LWE)

  • 아이디어: 다항식 환(Quotient Ring) 구조를 이용해 LWE를 최적화.
  • 장점:
    • 공개키 크기 감소 (LWE 대비 훨씬 작음).
    • 암호문 크기 감소, 더 많은 비트 저장 가능.
  • 보안성: Ring-LWE 문제의 난이도는 격자 문제(SIVP)와 연결되어, 양자컴퓨터 시대에도 안전하다고 여겨짐.

다항식환 Zq[X]

  • 는 계수가 유한체 에 속하는 모든 다항식 집합
    • a(x)=a0​+a1​x+a2​x2+⋯,ai​∈Zq​

몫환 정의

  • 어떤 양의 정수 (N) (여기서는 2의 거듭제곱)을 잡고,
    • ⟨XN+1⟩ 로 생성된 이상(ideal)을 고려합니다.
  • 두 다항식 a(x),b(x)가 있을 때,a(x)≡b(x)(modXN+1)라고 정의하는데, 이는 XN+1이 a(x)−b(x)를 나눈다는 뜻입니다

몫환

  • 이때 몫환을 Rq=Zq[X]/(XN+1)라고 정의합니다.
    • 대표원(Representative) 는 항상 차수가 인 다항식으로 고를 수 있습니다:
    • a(x)=a0+a1x+⋯+aN−1xN−1, ai∈Zq
  • 즉, 다항식환을 XN+1으로 나눈 나머지 형태만 고려하는 거예요.

왜 필요한가?

  • 이렇게 정의하면, 다항식의 곱셈/덧셈을 할 때 항상 차수가 이상으로 커질 수 있는데, 몫환에서는 XN≡−1로 치환해서 다시 차수 <N로 줄일 수 있습니다.
  • 이 구조는 Ring-LWE (RLWE) 문제 정의와 준동형 암호에 핵심적으로 쓰입니다.
    예:xN≡−1(modXN+1)이므로, 계산이 순환(cyclic)처럼 동작합니다.

직관

  • 의 원소는 사실상 Zq 계수의 길이 벡터와 같아요
    • a(x)↔(a0,a1,…,aN−1)
  • 연산은 벡터 덧셈/곱셈이지만, 곱셈할 때는 XN=−1 규칙을 적용합니다.

✅ 요약

  • 는 Zq[X]의 모든 다항식을 XN+1로 나눈 나머지로 묶어 만든 몫환이며, RLWE 기반 암호의 수학적 기반입니다.
  • Therefore, ℤ𝑞 𝑥 /(𝑋𝑛 + 1) = { 𝑎0 + 𝑎1𝑋 + ⋯ 𝑎𝑛−1𝑋𝑛−1 ∶ 𝑎𝑖 ∈ ℤ𝑞 }

6. 발전 흐름

  1. LWE 기반 공개키 암호 (LPR)
  2. Ring-LWE 기반 공개키 암호 (효율성 ↑)
  3. Leveled Homomorphic Encryption (레벨 제한 HE)
  4. Fully Homomorphic Encryption (완전 동형암호, Bootstrapping 포함)
  5. 응용: 프라이버시 보호 머신러닝, CKKS(근사 연산 지원 HE)

핵심 포인트

  • 동형사상 → 동형암호로 확장: 암호문 상태에서도 안전하게 연산 가능.
  • 보안성은 최소 IND-CPA 필요.
  • Ring-LWE는 기존 LWE보다 효율적이고, lattice 기반 보안성을 유지.
  • 최신 연구는 머신러닝, 데이터 프라이버시 보호에 활발히 적용 중.

👉 이 요약을 시험 대비용 ‘정의 + 성질 + 예시’ 정리표 형태로 다시 만들어 드릴까요, 아니면 시각화 다이어그램(예: 흐름도, 구조도)으로 정리해드릴까요?

반응형

'개발 > 인공지능 보안' 카테고리의 다른 글

Homomorphic Multiplication and Encoding  (0) 2025.09.30
Homomorphic Encryption  (0) 2025.09.17
LWE (Learning With Errors)  (0) 2025.09.17
LWE, Lattice, Reduction 이해하기  (0) 2025.09.09
보안 예비 지식 (Preliminaries)  (0) 2025.09.09

관련글

티스토리툴바