📖 HE-TEST 문서

1. 동형암호란 무엇인가

Homomorphic Encryption (HE) 은 암호문 상태에서 연산이 가능한 암호 방식입니다. 일반 암호는 Dec(Enc(a) + Enc(b)) 와 같은 합산을 시도하면 의미 없는 비트가 나오지만, HE 에서는 정의된 연산 집합(+, ×, …) 안에서 Dec(Enc(a) ⊕ Enc(b)) = a + b 가 성립합니다.

본 데모는 SEAL 의 leveled HE를 그대로 사용합니다 — bootstrapping 없이 미리 정한 깊이까지만 안전.

2. SEAL 의 두 스킴: BFV vs CKKS

3. 키 4종 — 역할과 보호 레벨

본 데모의 SEAL 컨텍스트는 다음 4가지 직렬화 객체를 생성합니다. 각각 누가 가져야 하고 어디까지 노출 가능한지 구분이 필요합니다.

보호 레벨 요약

• PUBLIC — 누구에게 줘도 무방. 평문/비밀키 정보 없음.
• EVALUATION — 동형연산을 수행할 평가자(서버) 에게 전달. 익명/외부 노출은 권장 X.
• SECRET — 데이터 소유자만. 절대 외부 전송·평문 저장 금지.

4. 키 생성·배포 흐름

┌── EncryptionParameters ─────────┐
│  scheme, poly_modulus_degree,    │
│  coeff_modulus, plain_modulus    │
└────────────────┬─────────────────┘
                 ↓
        ┌────────────────┐
        │     Context    │  파라미터 검증 (parametersSet())
        └────────┬───────┘
                 ↓
        ┌────────────────┐
        │  KeyGenerator  │
        └────────┬───────┘
                 │
   ┌─────────────┼──────────────┬──────────────┐
   ↓             ↓              ↓              ↓
publicKey   secretKey      relinKeys    galoisKeys (선택)
 [PUBLIC]    [SECRET]      [EVAL]       [EVAL]
   ↓             ↓              ↓
 암호화     복호화         서버 동형연산 후
                          ct 크기 정상화

역할별 누가 무엇을 가지나

5. 동형연산 종류와 곱셈 깊이

6. 노이즈 예산 (Noise Budget)

BFV 의 모든 암호문은 약간의 노이즈를 동반합니다. 곱셈을 거듭할수록 노이즈가 증폭되고, budget ≤ 0 이 되면 복호화 결과가 임의의 정수가 됩니다 (= 데이터가 망가짐, 아님).

대략의 budget 변화

실제 budget 은 plain_modulus 비트 크기와 연산 종류에 따라 변동 — 위는 본 데모의 plain_modulus ≈ 2²⁰ 가정 시 대략값.

7. 패턴 매칭 트릭 — 다항식 zero-test

HE 는 비교(==, <) 를 직접 지원하지 않지만, 등치 검사는 차의 제곱 또는 다항식 zero-test 로 환원할 수 있습니다.

유한 집합 멤버십: x ∈ {a₁, …, aₙ}

p(x) = (x − a₁)(x − a₂) … (x − aₙ)
   = 0   ⇔   x ∈ {a₁, a₂, …, aₙ}

위 식은 다항식 곱셈만으로 평가 가능 → HE 친화적. RRN 의 성별자리(7번째 숫자) 가 {1,2,3,4} 중 하나인지 확인하는 데 정확히 이 트릭을 씁니다.

// 각 후보 ct 에 대해 (depth 2)
d1 = ct − Plain([1,1,...])
d2 = ct − Plain([2,2,...])
d3 = ct − Plain([3,3,...])
d4 = ct − Plain([4,4,...])
m12 = d1 × d2;  relinearize(m12)
m34 = d3 × d4;  relinearize(m34)
p   = m12 × m34;  relinearize(p)
// → 슬롯 6 의 평문 값이 0 ⇔ 성별자리 ∈ {1,2,3,4}

완전 일치 검사: x == t

diff = ct − Plain(t)
sq   = diff × diff   // 0 만 0, 다른 값은 양수
// → 모든 슬롯이 0 ⇔ 완전 일치

8. 키워드/와일드카드 검색 — 토큰 단위 HE 매칭

탭 4 의 "Keyword Search (HE)" 는 임의의 키워드를 동형암호 위에서 검색합니다. 핵심 아이디어는 문자 단위 비교를 SIMD 슬롯에 펼친 후 마스크를 곱해 와일드카드를 처리 하는 것:

패턴 P  = "p?ssword"  (? = '*'  와일드카드)
target = ['p', 0, 's', 's', 'w', 'o', 'r', 'd']
mask   = [ 1, 0,  1,   1,   1,   1,   1,   1 ]   (와일드카드 자리만 0)

token  = "password" (codepoint vector)
ct     = Enc(token)

서버:
  diff = ct − Plain(target)            // 슬롯별 차이
  sq   = diff × diff                   // 음수 영향 제거 (depth 1)
  out  = sq × Plain(mask)              // 와일드카드 자리는 0 유지 (depth 2)

클라이언트:
  out 복호화 → 슬롯 0..L-1 합 = 0  ⇒  MATCH

왜 길이가 같은 토큰만 후보가 되는가

슬롯 단위 SIMD 비교는 같은 길이의 벡터끼리만 의미가 있습니다. 그래서 클라이언트에서 공백 단위로 토큰화한 뒤 패턴 길이와 정확히 일치하는 토큰만 골라 암호화합니다. '*' 는 한 글자 와일드카드라는 점에 주의 — pa*sword 는 8자 토큰만, pa**word 는 8자 토큰 중 자리 2,3 이 임의인 것만.

일반 정규식이 HE 위에서 곤란한 이유

자릿수별 char class (예: \d = [0-9]) 는 그 자리의 코드포인트 c 가 집합 안에 있는지를 다항식 zero-test로 풀어야 합니다. 즉 자리마다 (c − v₁)(c − v₂)…(c − vₙ) 곱셈 트리를 평가해야 하고, 자리마다 다항식 차수가 달라 SIMD 한 번에 처리하기 어렵습니다. 결과적으로

• 자리마다 별도 동형 곱셈 → 곱셈 깊이가 폭증 (예: [0-9] 만으로 깊이 ≈ log₂10 ≈ 4)
• 각 자리 결과를 슬롯 합으로 모으려면 Galois rotations(회전 키) 가 추가 필요
• 큰 poly_modulus_degree (16384+) 와 그에 따른 키·암호문 크기 증가

본 데모는 와일드카드(*) 만 지원해 깊이 2 회로(8192) 에서 빠르게 동작하도록 했습니다. 필요하면 같은 패턴 매칭 트릭을 여러 자리에 일반화해 char class 까지 확장 가능 (위 한계를 감수하면).

9. 가명화/익명화 프레임워크 — KR·JP·US·EU

탭 5 의 "가명화/익명화" 는 PII Scanner 의 검출 결과를 ISO/IEC 20889(기법 분류) 에 따라 변환하고 ISO/IEC 27559(절차 프레임워크) 의 흐름에 맞춰 4개 관할의 법령에 대한 준수 여부를 평가합니다. 용어는 W3C DPV 2.0 의 dpv-pd:* compact IRI 를 사용합니다.

처리 흐름 (시각화)

처리 7단계 (ISO 27559 정렬)

1. 입력 — 파일(.txt .csv .json .pdf .docx .hwp) 또는 인라인 텍스트
2. PII 검출 — Presidio (또는 lite) 의 정규식·키워드·NER 결합
3. DPV 매핑 — 각 entity_type → dpv-pd:NationalIdentificationNumber 등
4. 관할별 분류 — direct identifier / quasi-identifier / sensitive / secret
5. 기법 선택 — ISO 20889 §7~§8 카탈로그에서 entity 별 기법 자동 매핑
6. 변환 적용 — 위치 역순으로 in-place 치환 (인덱스 유지)
7. 준수 평가 — 관할별 verdict (compliant / partial / insufficient) + 근거 + 잔여 요구사항

관할별 핵심 기준 (요지)

구현된 기법 (ISO 20889 인용)

익명화 모드의 강화점

탭 UI 에서 "익명화" 를 선택하면 pseudonym_consistent 와 tokenize_random 에서 동일성 매핑(같은 입력에 같은 토큰) 을 끕니다. 같은 사람이 두 번 등장해도 다른 토큰을 부여 — 연결성(linkability) 차단. 단 진정한 익명화는 통계적 검증(k-익명성·l-다양성·t-근접성) 과 매핑 테이블 폐기 가 함께 필요하다는 점을 판정 카드의 "잔여 요구사항" 에 명시합니다.

10. 본 데모의 프라이버시 모델

┌─────────── CLIENT (data owner) ───────────┐
│ 보유: EncParms, publicKey, secretKey,       │
│       relinKeys, 평문 데이터                 │
│                                            │
│ 1. 데이터 → publicKey 로 암호화              │
│ 2. 결과 ct 를 비밀키로 복호화                  │
└────────────┬────────────────┬──────────────┘
             │ ct 만 전송       │ result ct 만 수신
             ↓                ↑
┌───────────────────────────────────────────┐
│ SERVER (evaluator)                         │
│ 보유: EncParms, publicKey, relinKeys        │
│       (secretKey 없음 → 평문 복원 절대 불가) │
│                                            │
│ ct 에 대해 add/multiply/square 등           │
│ 동형연산만 수행                              │
└───────────────────────────────────────────┘

• 서버는 평문을 단 한 순간도 보지 않음
• 서버는 비밀키가 없으므로 ct 의 의미를 알 수 없음 (의미적 보안)
• 탭 2(SEAL)·탭 3(RRN Search) 모두 같은 모델 — 다만 본 브라우저 데모에서는 클라이언트와 서버 역할이 같은 페이지에서 시뮬레이션되어 있을 뿐

11. 실제 운영 시 고려사항

• 비밀키 분리 — 데모는 편의상 brower 메모리에 두고 화면에도 보여주지만, 실제 시스템은 KMS/HSM/TPM 또는 보안 엔클레이브에서만 사용해야 함
• 매개변수 선택 — security level (HE Standard 권장 128bit), poly_modulus_degree, plain_modulus 는 위협 모델·연산 깊이·성능 요구 균형으로 결정
• 키 크기와 대역폭 — galois keys 는 수십 MB 까지 커질 수 있음. 압축·필요 회전만 생성 등 최적화 필요
• 부채널·악의적 클라이언트 — HE 자체는 IND-CPA. 능동적 공격(예: 변조된 ct 주입)은 별도 무결성/인증 메커니즘 필요
• Bootstrapping 미사용 — leveled scheme 의 깊이 한계. 깊은 회로(예: 신경망 추론) 가 필요하면 bootstrapping 가능 라이브러리(OpenFHE 등) 또는 회로 분할 전략을 검토
• RRN 검색의 부정확성 — 정규식 추출에 의존하므로 띄어쓰기·특수문자가 끼어든 변형은 보강 필요. 진짜 양방향 PSI 가 필요하면 OPRF + HE 조합 또는 PIR 사용

12. 참고 자료

• Microsoft SEAL — C++ 본체 라이브러리
• node-seal — JS/WASM 래퍼 (본 데모가 사용)
• BFV 논문 · CKKS 논문
• HE Standard — 권장 매개변수
• ← 데모로 돌아가기