필기 원본
이 글에서 다룬 원본 PDF 24–27쪽이다. 두 단과 여백 필기를 포함한 페이지 전체를 실었다. 이미지를 누르면 확대해서 볼 수 있다.
들어가며
앞 글[1]에서는 동형암호의 정의와 IND-CPA 안전성을 정리했다. 이번에는 실수 값을 정수 계수 다항식으로 표현하고, 암호화한 상태의 연산에서 스케일과 오차가 어떻게 변하는지 살펴본다.
정리 범위는 원본 PDF의 24–27쪽이다. 실수 연산의 필요성, 스케일링·반올림·법 연산, 실수 계수 다항식의 Ring-LWE 암호화와 근사 복호화, 동형 덧셈과 공개 평문 곱셈을 다룬다.
원문의 수치 예제와 알고리즘을 옮기고, 생략된 반올림 항과 복호화 범위 조건을 보충한다. 추가 검산 예제는 별도로 표시한다. 여기서 다루는 것은 실수 계수 다항식을 정수화하는 과정이며, CKKS의 슬롯 인코딩 전체는 이후 범위다.
1. 실수의 산술적 의미를 유지해야 한다
1.1 비트 암호화에서 실수 연산으로
앞에서 본 Ring-LWE 공개키 암호는
에서 계산했고, 메시지의 각 계수는 또는 이었다.
원문은 예를 들어
같은 다항식의 각 비트에 를 곱하는 방식을 떠올린다. 작은 잡음이 있어도 두 중심을 구별해 각 계수를 또는 로 복원하는 구조다.
하지만 신경망의 가중치에는 , , 같은 소수가 등장한다. 활성화 함수의 출력과 중간 계산도 실수 값을 다룬다.
실수의 표현을 비트열로 만들어 암호화하는 것에 더해, 원하는 실수 덧셈·곱셈에 대응하는 계산이 필요하다. 원문의 예제는
에 대해
을 계산하는 것이다. 이런 근사 실수 산술로 이어지는 대표적인 구성이 CKKS다.
1.2 Floating-point 표현에서 fixed-point 스케일링으로
원문은
를 예로 든다. 유효 숫자와 지수를 나누어 표현할 수 있지만, 의 계수 자리에 실수 를 직접 넣을 수는 없다.
여기서는 fixed-point 방식처럼 공개된 스케일을 사용한다. 이 글에서는 양의 정수 로 설명한다. 값을 배 하고 정수로 반올림한 뒤 암호화한다. 계산 결과를 해석할 때는 그 결과의 스케일로 나눈다.
이 글의 는 실수 표현을 위해 선택하는 스케일이다. 세 번째 글에서 비트 사이의 간격으로 사용한 와 용도를 구별한다.
1.3 추적해야 할 세 종류의 오차
원문은 다음 세 가지를 함께 고려하라고 강조한다.
- 실수를 정수화할 때 생기는 인코딩 반올림 오차.
- Ring-LWE 암호화·복호화 과정에서 남는 암호화 잡음.
- 동형 연산이 기존 오차를 더하거나 증폭하면서 생기는 결과 오차.
아래에서는 이 항들을 기호로 분리한다. 계산 후의 총오차를 처음의 작은 잡음 분포와 동일하게 취급하지 않는다.
2. 실수 계수 다항식을 정수 계수로 옮기기
2.1 계산할 공간
앞 글처럼 은 의 거듭제곱으로 두자. 정수 계수 다항식의 환과 그 법 버전을
로 쓰자. 실수 값의 유한 정밀도 표현은 유리수로 나타낼 수 있으므로, 원문처럼
의 메시지 을 생각한다. 각 다항식은 차수가 보다 작은 대표 다항식으로 쓴다.
모든 실수를 유한한 비트 수로 정확히 저장한다는 뜻은 아니다. 주어진 수치 근삿값을 다항식 계수에 넣고, 그다음 정수화 오차를 분석하는 단계다.
2.2 원문 예제: 스케일링
라 하고 원문의 다항식을 보자.
을 곱하면
표시한 계수들은 이 스케일에서 정수가 된다. 일반적인 메시지에서는 를 곱해도 정수가 되지 않을 수 있으므로 반올림 단계가 필요하다.
2.3 계수별 반올림과 오차
는 가장 가까운 정수로의 반올림을 뜻한다. 처럼 항상 아래로 내리는 연산과 구별한다. 수치 예제에서 정확히 중간이면 에서 먼 정수를 선택한다.
다항식에는 계수별로 적용한다. 반올림 오차를
로 정의하면
각 계수의 오차는 절댓값 이하다. 이후 사용할 노름도 계수의 최대 절댓값으로 고정한다.
따라서
이는 이 글의 계수 표현에 대한 상한이다. 이후 CKKS 슬롯 값의 오차로 바꾸려면 슬롯 변환이 오차에 미치는 영향도 반영해야 한다.
2.4 법 로 보내기
마지막으로 각 정수 계수를 법 로 줄인다.
전체 과정은 다음과 같다.
이제 정수 계수 환에서 계산할 수 있다. 다만 법 연산으로 합쳐진 여러 정수 중 어떤 값을 의도했는지 복원하려면 표현 범위에 관한 조건이 필요하다.
3. 스케일은 정밀도와 표현 범위를 함께 바꾼다
3.1 원문 예제: 작은 스케일과 큰 스케일
원문은 을 , 으로 비교한다. 암호화 잡음을 제외하고 인코딩만 계산하면 다음과 같다.
| 스케일 | 절대오차 | |||
|---|---|---|---|---|
반올림만 있을 때 계수별 오차 상한은
큰 스케일은 이 상한을 줄인다. 정밀도를 위해 원문에서 라고 쓰는 이유다.
3.2 중심 대표값과 wrap-around
법 의 값에는 부호 있는 정수 표현이 여러 개 대응한다. 음수 계수를 복원하려면 각 계수의 중심 대표값을 선택해야 한다.
에 대해
다항식에는 계수별로 적용한다. 선택한 정수 계수는 에 놓인다.
원문은 다음 wrap-around 예제를 든다.
법 의 값 만으로 원래 정수가 이었다고 복원할 수는 없다. 추가로 , 을 대입하면
가 되어 의도한 값 를 잃는다. 라는 비교만으로 충분하지 않으며, 스케일을 곱한 메시지 자체의 크기를 봐야 한다.
원문 25쪽의 인코딩 흐름에 추가 수치 예제를 넣었다. , , 이며 암호화 잡음은 생략했다. 법 연산으로 을 으로 저장해도, 중심 대표값이 임을 복원하면 으로 해석할 수 있다.
3.3 메시지와 잡음에 필요한 공간
복호화 후 남는 암호화 잡음을 라 하자. 중심 대표값으로 의도한 정수 다항식을 복원하는 충분조건은
인 경우, 다음 조건으로도 충분하다.
이 조건 아래에서 계수의 크기가 이하인 메시지들을 표현하려면
처럼 메시지·반올림·잡음의 여유를 함께 확보한다.
원문의 는 이 관계를 직관적으로 요약한다. 정확한 조건은 메시지 크기와 계산 중 증가하는 오차까지 포함한다. 같은 에서 를 키우면 정밀도에 유리하지만 사용할 수 있는 메시지 범위가 줄어든다.
4. 실수 다항식용 Ring-LWE 키 생성
4.1 앞 글과 달라진 부호·성분 순서
원문은 여기서 공개키와 복호화의 표기를 바꾼다.
| 구분 | 공개키의 관계와 순서 | 암호문 의 복호화 조합 |
|---|---|---|
| 세 번째 글 | , | |
| 이번 글 | , |
각 표기에서 큰 항이 소거되도록 암호문 성분을 맞추는 구조다. 아래에서는 원문 25–27쪽의 부호 규약에 맞춰 , 를 일관되게 사용한다.
4.2 KeyGen
입력은 보안 매개변수의 단항 표현 이고, 출력은 다.
보안 매개변수에 따라
를 정한다. 는 작은 정수 계수를 위한 분포이며, 에서 뽑은 계수들을 차수 미만의 작은 다항식으로 본다.
비밀키와 공개키를 다음처럼 만든다.
작은 다항식은 의 값으로 생각하고, 암호문의 계산에서는 법 로 보낸다. 인코딩 스케일 는 메시지의 수치 표현에 사용하는 공개정보로 별도 추적한다.
5. 암호화와 근사 복호화
5.1 암호화
메시지 를 인코딩해 를 만든다. 암호화할 때마다 작은 다항식을 서로 독립적으로 새로 뽑는다.
암호문은
성분별로 쓰면
스케일 로 정수화한 메시지는 첫 성분에 더해진다.
5.2 비밀키와 결합하면 큰 항이 소거된다
먼저 안의 선형 결합을
로 정의하자. 원문의 내적 표기는
와 같다.
암호문 성분을 대입하면 에서
마지막 줄은 , 즉 를 사용했다. 균등한 큰 다항식 가 들어간 두 항은
으로 소거된다.
복호화에 남는 잡음을
로 두면
각 작은 다항식이 곱해지고 더해진 결과이므로, 의 분포를 원래의 와 같다고 둘 수는 없다.
5.3 반올림 오차까지 포함한 근사 복호화
3.3절의 범위 조건이 성립하면
이를 실제 수치로 해석하는 결과를 이라 하자.
이제 을 대입하면
원문의 와 가 각각 여기의 , 에 해당한다. 따라서
으로 이해한다. 여기서 다. 이 글에서는 환 안의 결합 와, 중심 대표값을 선택해 스케일로 나누는 수치 디코딩을 구분했다.
잡음 상한이 이면
같은 잡음 상한을 유지할 수 있고 wrap-around가 없다는 조건에서, 스케일을 키우면 이 오차 상한이 줄어든다. 실제 잡음 분포에 대한 분석에서는 이 상한을 넘는 꼬리 확률도 별도로 고려해야 한다.
5.4 보충: 스케일로 나누기는 모듈러 역원 곱셈이 아니다
위 복원 순서는 다음과 같다.
- 를 에서 계산한다.
- 각 계수를 중심 대표 정수로 옮긴다.
- 그 정수 계수를 유리수·실수의 의미로 로 나눈다.
원문의 scale down에서 등장하는 는 마지막 수치 나눗셈을 뜻한다. 에서 모듈러 역원을 곱하는 것과 구별해야 한다.
추가 예제: , , 복원된 정수 계수가 이면
한편 이므로 모듈러 역원을 곱하면
이는 실수 을 복원하는 나눗셈과 다른 연산이다.
6. 추가 검산: 작은 다항식으로 암호화부터 확인하기
이 절은 원문에 없는 계산 예제다. 작은 차수와 고정한 표본을 사용해 식의 부호·반올림·오차를 검산하며, 실제 보안 수준을 정하는 예제는 아니다.
6.1 매개변수와 메시지
인 환에서 다음 작은 다항식을 선택하자.
계수 벡터를 로 쓰고
으로 정한다. 메시지는
계수별 반올림 결과는
세 번째 계수는 를 이 글의 중간값 규칙에 따라 으로 반올림했다.
6.2 공개키와 암호문
다항식 곱셈을 로 정리하고 중심 대표 계수로 표시하면
각각 , , 을 계산한 값이다.
6.3 잔여 잡음과 수치 오차
잡음은 직접 전개할 수 있다.
실제로 암호문을 복호화 조합에 넣으면
계수 크기가 모두 보다 작으므로 범위를 벗어나지 않는다. 으로 나누면
원래 메시지와의 차이는
이 예제에서 이므로
반올림 오차와 암호화 잡음을 합친 상한과 실제 계산이 맞는다.
7. 동형 덧셈: 스케일은 유지되고 오차는 더해진다
7.1 연산을 위한 총오차 표기
같은 비밀키·환·법 와 같은 스케일 를 사용하는 두 암호문을 보자.
원문 27쪽의 암호문 성분 를 여기서는 로 적는다. 공개키 성분과 구별하기 위한 표기 변경이다.
인코딩 오차와 암호화 잡음을 합친 총오차를
로 두면
여기서 는 정수 계수 다항식이다. 는 원래의 잡음 분포 에서 새로 뽑은 값이 아니라 이미 인코딩·암호화 과정을 거친 총오차다.
7.2 암호문 성분을 더한다
동형 덧셈을
로 정의한다. 에서
원문의 핵심은 의 암호문 성분에 대한 선형성이다. 이는 에서 성립하는 관계다. 중심 대표값을 고르는 연산이 모든 경우에 선형인 것은 아니다.
결과가 중심 대표 범위 안에 있으면
따라서 결과 스케일은 , 총오차는
다. 계수별 오차 상한도 삼각부등식에 따라 합할 수 있다. 입력 각각이 복호화 범위 안에 있어도 합이 범위를 넘을 수 있으므로
같은 출력 조건을 다시 확인한다.
7.3 추가 예제: 원문의 두 실수에 오차를 넣으면
이 절과 8.4절의 스칼라 검산에서는 별도로 , 을 사용한다. 상수 다항식으로 생각하면 된다.
두 값은 이 스케일에서 반올림 오차가 없다. 복호화 조합의 중심 대표값에 각각 , 의 잡음이 남았다고 하자.
합의 복호화·디코딩 결과는
평문 합 에 합산된 오차 이 남는다.
7.4 보충: 서로 다른 스케일은 먼저 맞춘다
오차가 없는 경우에도, 같은 값 가 스케일 에서는 , 스케일 에서는 으로 표현된다. 이 정수들을 그대로 더한 을 어느 한 스케일로 나눠도 원하는 합 가 되지 않는다.
첫 암호문의 각 성분을 배 하여 스케일 에 맞추면
실제 오차가 있다면 첫 암호문의 오차도 배 된다. 스케일 정렬은 암호문의 값과 오차에 영향을 주므로, 스케일을 적어 둔 숫자만 임의로 바꾸는 것과 구별한다.
8. 동형 평문 곱셈: 두 입력의 스케일을 곱한다
8.1 한쪽 입력은 공개 평문이다
이번에는 암호화된 에 공개된 평문 다항식 를 곱한다. 는 암호문으로 주어지는 비밀 입력이 아니다.
같은 스케일 로 평문을 인코딩하자.
에서 를 암호문의 두 성분에 각각 곱한다.
암호문 성분은 여전히 두 개다. 비밀키도 를 유지한다.
8.2 원문의 근사식과 반올림을 포함한 정확한 전개
곱셈 전 암호문이
를 만족한다고 하자. 에서
원문은 를 사용해
로 설명한다. 여기서 결과의 스케일이 가 되는 것을 볼 수 있다.
평문의 반올림 항도 남겨 두면 이므로, 법으로 줄이기 전의 정확한 다항식 전개는
원문 마지막 줄의 가 여기의 다. 메시지 쪽의 반올림 오차도 안에 포함했다.
따라서 스케일을 적용한 메시지 외의 총오차를
로 추적할 수 있다. 기존 잡음에 가 곱해지고, 공개 평문의 반올림 오차에서 두 항이 더 생긴다.
8.3 결과는 바뀐 스케일로 디코딩한다
새 복호화 결과도 범위 안에 있어야 한다.
이 조건 아래 결과를 로 나누면
곱셈에서는 암호화 잡음뿐 아니라 메시지·평문 반올림 항의 교차 곱도 나타난다. 결과 오차를 처음의 에서 뽑은 새 오차 하나로 대체하지 않는다.
8.4 추가 예제: 스케일을 그대로 두면 값이 달라진다
7.3절과 같은 , 을 사용하고
로 두자. 잡음이 없으면 스케일을 적용한 곱은
이번에는 암호문 쪽에 이 남아 정수 복호화 값이 라고 하자. 공개 평문은 정확히 인코딩되므로 이다.
새 스케일 으로 해석하면
이 오차는 정확히
다. 이므로 이 예제에는 wrap-around가 없다.
원래 스케일 으로 나누면 가 된다. 새 스케일이 이라는 정보를 유지해야 올바른 수치 근삿값을 얻는다.
8.5 보충: 모든 평문 곱셈이 스케일을 제곱하지는 않는다
위의 는 두 입력을 모두 스케일 로 표현했기 때문이다. 일반적으로 암호문 메시지의 스케일이 , 인코딩한 평문의 스케일이 라면
이미 정수인 공개 상수 를 스케일링 없이 그대로 곱하면
이때 메시지 에 대한 스케일은 다. 자체에 스케일 를 붙여 를 곱하는 경우와 구별한다.
스케일의 곱을 추적하고 덧셈 전에 스케일·계산 매개변수를 맞추는 관계는 Microsoft SEAL의 CKKS 공식 예제[2]에서도 확인할 수 있다.
9. 연산 뒤에 남는 정보를 추적하기
9.1 같은 스케일에서의 연산 비교
아래 표의 복호화 조합은 법 안의 식이다. 실제 수치 결과는 범위 조건을 확인한 뒤 중심 대표값을 선택하고 출력 스케일로 나눠 해석한다.
| 연산 | 암호문 성분 | 복호화 조합의 내용 | 출력 스케일 |
|---|---|---|---|
| 덧셈 | |||
| 스케일링하지 않은 정수 곱셈 | |||
| 스케일 의 공개 평문 곱셈 |
세 경우 모두 암호문은 다항식 두 개로 남는다. 스케일은 연산에 따라 달라지며, 표현 범위와 총오차도 결과마다 다시 추적해야 한다.
9.2 보충: 계수 인코딩과 CKKS 슬롯 인코딩
지금까지는 실수 계수 다항식 가 이미 주어졌다고 생각했다. 그 계수를 정수화하는 과정과, 데이터 벡터를 성분별 연산이 가능한 슬롯으로 배치하는 과정은 구별해야 한다.
계수에 데이터를 그대로 나열하면 다항식 덧셈은 계수별 덧셈이지만, 곱셈은 계수들의 합성곱이다. 예를 들어 일 때
계수 벡터 와 의 성분별 곱 을 뜻하지 않는다. 높은 차수 항은 추가로 에 따라 정리한다.
CKKS의 슬롯 표현에서는 cyclotomic 다항식의 복소수 근에서 평가하는 구조를 이용한다. 이때의 인코딩과 디코딩은 저자들의 ASIACRYPT 2017 발표 자료, Packing Method[3]에 설명되어 있다. 이 글의 계수 반올림 오차 상한을 슬롯 오차 상한으로 그대로 옮겨 쓰지는 않는다.
원문 28쪽부터는 암호문 두 개를 곱할 때의 항, relinearization과 key switching, 증가한 스케일을 조정하는 rescaling으로 이어진다. 이 과정은 결과를 읽을 때 스케일로 나누는 디코딩과도 구별해서 다음 글에서 다룬다.
참고 자료
- 원본 필기 PDF 24–27쪽: 실수 연산 예제, 스케일링·반올림·법 연산, Ring-LWE 알고리즘, 근사 복호화, 덧셈과 공개 평문 곱셈 전개의 기준 자료.
- Jung Hee Cheon, Andrey Kim, Miran Kim, Yongsoo Song, Homomorphic Encryption for Arithmetic of Approximate Numbers, ASIACRYPT 2017 발표 자료[3]: 암호화 잡음을 수치 오차로 다루는 복호화 구조와 슬롯 packing의 구별.
- Microsoft SEAL, CKKS Basics[2]: 곱셈의 스케일 변화, 덧셈의 스케일·매개변수 정렬.
참고 링크
Comments