HEAAN

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. CKKS 평문 공간
- 2.1. 인코딩 방법
- 2.2. 디코딩 방법
3. 알고리즘
4. 보안
5. 라이브러리
참조

1. 개요

HEAAN은 복소수(또는 실수)에 대한 근사 산술 연산을 지원하는 CKKS(Cheon-Kim-Kim-Song) 방식의 동형 암호화 방식이다. 이 방식은 평문 벡터를 다항식으로 인코딩하고, 암호화된 상태에서 덧셈, 곱셈 등의 연산을 수행하며, 재조정을 통해 오차를 관리한다. HEAAN은 링 오류를 겪는 학습 문제(RLWE)의 어려움에 기반한 IND-CPA 안전성을 가지며, 여러 버전의 라이브러리로 구현되어 사용된다.

더 읽어볼만한 페이지

공개 키 암호 - 공개 키 기반 구조
공개 키 기반 구조(PKI)는 공개 키 암호화를 기반으로 안전한 통신과 개체 식별을 가능하게 하는 기술로서, 디지털 인증서를 통해 공개 키를 특정 개체에 연결하고 인증서를 관리하며, 인증 기관(CA), 등록 기관(RA) 등 다양한 구성 요소로 이루어져 인증서 발급, 관리, 배포, 사용 및 폐기와 관련된 역할, 정책, 하드웨어, 소프트웨어 및 절차의 집합을 포함한다.
공개 키 암호 - DNSSEC
DNSSEC는 DNS의 보안 취약점을 개선하기 위해 도메인 정보에 디지털 서명을 추가하여 응답 레코드의 무결성을 보장하고 DNS 위장 공격을 막는 기술로, RRSIG, DNSKEY 등 다양한 리소스 레코드 유형을 사용하여 인증 체인을 구성하며 공개 키 암호 방식을 활용한다.
암호학 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
암호학 - 암호화
암호화는 정보를 보호하기 위해 사용되는 기술로서, 단순한 문자 치환 방식에서 시작하여 현대에는 강력한 암호화 표준과 다양한 종류로 발전했으며, IT 시스템 전반에 적용되지만, 사이버 공격과 양자 컴퓨팅의 발전에 대한 대응이 필요한 기술이다.

HEAAN - [IT 관련 정보]에 관한 문서
기본 정보
종류	동형 암호
개발자	서울대학교 암호학 연구실
발표일	2016년 5월 15일
프로그래밍 언어	C++
라이선스	CC BY-NC 3.0

2. CKKS 평문 공간

CKKS (Cheon-Kim-Kim-Song) 방식은 다른 동형 암호화 방식과 달리 복소수(및 실수)에 대한 근사 산술 연산을 지원한다.

CKKS 방식의 평문 공간은 어떤 2의 거듭제곱 정수 $n$ 에 대해 $\mathbb{C}^{n/2}$ 이다. 복소수 평문 벡터를 효율적으로 처리하기 위해, 환 동형 사상 $\phi: \mathbb{R}[X]/(X^n+1) \rightarrow \mathbb{C}^{n/2}$ 를 활용하는 평문 인코딩/디코딩 방법을 사용한다. 인코딩 및 디코딩 방법에 대한 자세한 내용은 하위 섹션을 참고하면 된다.

2. 1. 인코딩 방법

평문 벡터

\vec z = (z_1, z_2, \dots, z_{n/2}) \in \mathbb{C}^{n/2}

와 스케일링 팩터

\Delta > 1

이 주어졌을 때, 평문 벡터는

m(X) \in R := \mathbb{Z}[X]/(X^n + 1)

형태의 다항식으로 인코딩된다. 이는

m(X) = \lfloor \Delta \cdot \phi^{-1}(\vec z) \rceil \in R

를 계산하여 얻으며, 여기서

\lfloor \cdot \rceil

는 계수별 반올림 함수를 나타낸다.

2. 2. 디코딩 방법

메시지 다항식

m(X) \in R

과 스케일링 팩터

\Delta > 1

이 주어지면, 이 다항식을 사용하여 복소 벡터

\vec z \in \mathbb{C}^{n/2}

를 계산한다. 이 과정은

\vec z = \Delta^{-1}\cdot \phi(m(X)) \in \mathbb{C}^{n/2}

로 표현된다.

여기서 스케일링 팩터

\Delta > 1

은 반올림 과정에서 생기는 인코딩 및 디코딩 오류를 제어한다.

\Delta

값을 조절하면,

\text{Dcd}(\text{Ecd}(\vec z; \Delta); \Delta) \approx \vec z

와 같은 근사 방정식을 얻을 수 있다. 여기서

\text{Ecd}

와

\text{Dcd}

는 각각 인코딩 및 디코딩 알고리즘을 의미한다.

매핑

\phi: \mathbb{R}[X]/(X^n+1) \rightarrow \mathbb{C}^{n/2}

는 링 동형 성질을 가지므로,

m_1 = \text{Ecd}(\vec z_1;\Delta)

와

m_2 = \text{Ecd}(\vec z_2;\Delta)

에 대해 다음이 성립한다:

$\text{Dcd}(m_1 + m_2;\Delta) \approx \vec z_1 + \vec z_2$
$\text{Dcd}(m_1\cdot m_2;\Delta) \approx \vec z_1 \circ \vec z_2$

여기서

\circ

기호는 동일한 길이를 가진 벡터 간의 아다마르 곱을 나타낸다. 이러한 특성 덕분에 스케일링 팩터

\Delta

를 적절하게 선택하면, 인코딩된 상태에서도 계산의 근사적 정확성을 확보할 수 있다.

3. 알고리즘

CKKS 암호화 방식은 키 생성, 암호화, 복호화, 동형 덧셈 및 곱셈, 재조정 알고리즘으로 구성된다.^[6] 양의 정수 $q$ 에 대해, $R_q := R/qR$ 를 $R$ 을 $q$ 로 나눈 몫환(Quotient Ring)이라고 정의한다. $\chi_s$ , $\chi_r$ , $\chi_e$ 는 작은 계수를 가진 다항식을 출력하는 $R$ 에 대한 분포를 나타낸다. 이러한 분포, 초기 모듈러스 $Q$ , 링 차원 $n$ 은 키 생성 단계 이전에 미리 결정된다.

3. 1. 키 생성

비밀 다항식 $s$ 를 $\chi_s$ 에서 샘플링한다.
$a$ 와 $a'$ 를 각각 $R_Q$ 와 $R_{PQ}$ 에서 균일하게 무작위로 샘플링하고, $e$ 와 $e'$ 를 $\chi_e$ 에서 샘플링한다.
비밀 키 $sk \leftarrow (1, s)\in R_Q^2$ , 공개 키 $pk \leftarrow (b = -a \cdot s + e, a) \in R_Q^2$ , 평가 키 $evk \leftarrow (b' = -a' \cdot s + e' + P\cdot s^2, a') \in R_{PQ}^2$ 를 출력한다.

3. 2. 암호화

임시 비밀 다항식

r \leftarrow \chi_r

을 샘플링한다. 주어진 메시지 다항식

m \in R

에 대해, 암호문

ct \leftarrow (c_0 = r \cdot b + e_0 + m, c_1 = r \cdot a + e_1) \in R_Q^2

를 출력한다.

3. 3. 복호화

주어진 암호문

ct \in R_q^2

에 대해, 메시지

m' \leftarrow \langle ct, sk \rangle

(\text{mod } q)

를 출력한다.

복호화는 원래 메시지의 근사값을 출력한다. 즉,

\text{Dec}(sk, \text{Enc}(pk, m)) \approx m

이며, 근사 오차는 분포

\chi_s, \chi_e, \chi_r

의 선택에 의해 결정된다. 동형 연산을 고려할 때, 평가 오차 또한 근사 오차에 포함된다.

3. 4. 동형 덧셈

두 암호문 ${\displaystyle ct}$와 ${\displaystyle ct'}$가 ${\displaystyle R_{q}^{2}}$에 주어지면, ${\displaystyle ct_{\text{add}}\leftarrow ct+ct'\in R_{q}^{2}}$를 출력한다.

정확성은 ${\displaystyle \operatorname {Dec} (sk,ct_{\text{add}})\approx \operatorname {Dec} (sk,ct)+\operatorname {Dec} (sk,ct')}$로 성립한다.

3. 5. 동형 곱셈

두 암호문

ct = (c_0, c_1)

와

ct' = (c_0', c_1')

이

R_q^2

에 주어졌을 때,

(d_0, d_1, d_2) = (c_0c_0', c_0c_1'+c_1c_0', c_1c_1')

(\text{mod } q)

를 계산한다.

ct_\text{mult} \leftarrow (d_0, d_1) + \lfloor P^{-1}\cdot d_2 \cdot evk \rceil \in R_q^2

를 출력한다.

정확성은

\text{Dec}(sk, ct_\text{mult}) \approx \text{Dec}(sk, ct) \cdot \text{Dec}(sk, ct')

로 성립한다.

근사 오차(메시지에 대한)는 동형 곱셈의 횟수에 따라 지수적으로 증가한다. 이러한 문제를 극복하기 위해 대부분의 동형 암호(HE) 방식은 Brakerski, Gentry 및 Vaikuntanathan에 의해 도입된 모듈러스 전환 기술을 사용한다.^[6] HEAAN의 경우, 모듈러스 전환 절차를 스케일 조정이라고 한다. 스케일 조정 알고리즘은 Brakerski-Gentry-Vaikuntanathan의 원본 알고리즘에 비해 매우 간단하다. 동형 곱셈 후에 스케일 조정 알고리즘을 적용하면 근사 오차가 지수적으로 증가하는 것이 아니라 선형적으로 증가한다.

3. 6. 재조정

암호문 $ ct \in R_q^2 $와 새로운 모듈 $ q' < q $가 주어졌을 때, 재조정된 암호문 $ ct_{\text{rs}}\leftarrow \lfloor (q'/q)\cdot ct\rceil \in R_{q'}^2 $를 출력한다.

4. 보안

CKKS 암호 방식의 IND-CPA 안전성은 격자 기반 난제인 링 오류를 겪는 학습 문제(RLWE)의 난해성 가정을 기반으로 한다.^[7] RLWE는 오류를 겪는 학습 문제(LWE)의 링 변형이다. 현재 거듭제곱 2를 밑으로 하는 순환 링에 대한 RLWE에 알려진 최상의 공격은 이중 공격 및 주 공격과 같은 일반적인 LWE 공격이다.^[7] 알려진 공격을 기반으로 하는 CKKS 암호 방식의 비트 보안은 Albrecht의 LWE 추정기에 의해 추정되었다.^[7]

5. 라이브러리

현재까지 버전 1.0, 1.1 및 2.1이 출시되었다. 버전 1.0은 부트스트래핑이 없는 CKKS 방식의 첫 번째 구현이다.

두 번째 버전에서는 사용자가 대규모 동형 암호 연산을 수행할 수 있도록 부트스트래핑 알고리즘이 추가되었다.

현재 최신 버전인 버전 2.1에서는 고속 푸리에 변환(FFT) 최적화된 수론 변환(NTT) 구현을 활용하여 $R_q$ 에서 링 요소의 곱셈 속도가 향상되었다.^[1]

참조

_[1] 간행물 Homomorphic encryption for arithmetic of approximate numbers Springer, Cham 2017
_[2] 웹사이트 An approximate HE library HEAAN https://github.com/s[...] 2016-05-15
_[3] 논문 Bootstrapping for Approximate Homomorphic Encryption https://eprint.iacr.[...] EUROCRYPT 2018(springer)
_[4] 웹사이트 Release HEAAN with BOOTSTRAPPING · snucrypto/HEAAN https://github.com/s[...] 2024-12-10
_[5] 간행물 Release HEAAN with Faster Multiplication · snucrypto/HEAAN https://github.com/s[...] Cryptography LAB in Seoul National University 2024-12-10
_[6] 논문 Fully Homomorphic Encryption without Bootstrapping http://eprint.iacr.o[...] ITCS 2012
_[7] 문서 Security Estimates for the Learning with Errors Problem https://bitbucket.or[...]
_[8] 간행물 Homomorphic encryption for arithmetic of approximate numbers Springer, Cham 2017
_[9] 웹인용 An approximate HE library HEAAN https://github.com/s[...] 2016-05-15
_[10] 논문 Bootstrapping for Approximate Homomorphic Encryption https://eprint.iacr.[...] EUROCRYPT 2018(springer)

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com