FHE에 대하여

Homomorphic Encryption

수학에서 ‘homomorphic’하다는 것은 두 algebraic structure가 보존됨을 의미합니다. 예를 들어, 함수 $F:X\rightarrow Y$가 operation $\times$에 대해 homomorphic하다면 이는 $F(a\times b)=F(a)\times F(b)$임을 의미합니다. 일반적으로 operation $\times$는 addition, multiplication $2$개로써 유용하게 쓰이는 것 같습니다.

이는 encrypted data에 대해 secret key를 알아 이를 decrypt하지 않고도 여러 operation을 취할 수 있음을 의미합니다. 이는 상당히 유용한데, 예를 들어 서버의 입장에서는 encrypted data를 직접 복호화하지 않으면서도 data를 변형해 필요한 query들을 수행하는 작업을 취할 수 있습니다.

하지만 위의 정의로는 부족함을 알 수 있습니다. 왜일까요? 일반적으로 encryption은 난수를 사용하기 때문에 probablistic algorithm이지 function이라고 하기 힘듭니다. 그래서 약간 다른 느낌의 정의가 더 적절한데, decryption이 function의 성질을 가진다는 데서 아이디어를 가져올 수 있습니다. addition, multiplication에서 수정된 homomorphic encryption의 정의는 다음과 같이 내릴 수 있습니다.

\[Dec(Enc(x)+Enc(y))=x+y,\quad Dec(Enc(x)\cdot Enc(y))=x\cdot y.\]

이 때, 주의할 점으로 message space와 ciphertext space 내에서의 연산($+, \cdot$)이 꼭 같을 필요는 없다는 것이 있습니다. 서로 다른 space 내에서의 연산이기 때문입니다.

Types of HE

• (Partial) HE
  • encrypted data에 대해 특정 연산의 operation만을 지원합니다.
  • 일반적으로 알려진 RSA / ElGamal System이 여기 해당합니다. RSA는 multiplication이 가능하고, ElGamal은 addition이 가능합니다.
• Somewhat HE (SHE)
  • 일반적으로 덧셈과 곱셈 모두를 지원하는 HE입니다.
  • 하지만, operation을 제한된 횟수만 할 수 있습니다.
• Fully HE (FHE)
  • encrypted data에 대해 어떤 function이든 evaluate할 수 있습니다.
  • SHE를 “bootstrapping”의 과정을 통해 FHE로 만들 수 있습니다.

History of HE

• 첫 번째 FHE는 2009년 Gentry에 의해 만들어졌습니다. Gentry는 Bootstrapping이란 기술을 사용하였는데, 문제는 한 operation에 30분이나 걸린다는 치명적인 단점이 있었다고 합니다.
• 이후 Integer-based HE를 거쳐 (DGHV) Lattice-based HE가 현재 활발히 연구되고 있고 사용되고 있다고 합니다. 여러 오픈소스 라이브러리(IBM Helib, Microsoft SEAL, TFHE, HEAAN, Lattigo, Palisade 등등)가 존재합니다.
• 최신 Lattice-based HE scheme을 정리하면 다음과 같습니다.

Scheme	Message Space	Operation	Bootstrapping
BGV, B/FV	Finite Field $\mathbb{Z}_p$	Modular arithmetic	Optional
TFHE	Single bit {0, 1}	Boolean {XOR, AND}	Default
CKKS	Real/Complex numbers	Approximate(fixed-point) arithmetic	Optional