필기 원본
이 글에서 다룬 원본 PDF 44–45쪽이다. 두 단과 여백 필기를 포함한 페이지 전체를 실었다. 이미지를 누르면 확대해서 볼 수 있다.
들어가며
앞 글[1]에서는 공개된 커널을 암호화된 입력과 곱했다. 이번에는 두 입력 행렬이 모두 암호화된 경우다. 행렬곱의 한 출력에는 한 행과 한 열의 내적이 필요하다. 데이터를 먼저 재배치하면, 같은 슬롯에 그 내적의 두 피연산자를 놓고 모든 출력 위치를 동시에 계산할 수 있다.
정리 범위는 원본 PDF 44~45쪽의 Homomorphic Matrix Multiplication 단원 전체다. 슬라이드 25–35와 두 쪽의 관련 필기를 포함한다. 행·열 순환이동, 네 재배치 연산, 평문 마스크를 이용한 구현, BSGS와 전체 회전 횟수를 옮긴다. 원문의 표기 오류는 올바른 식과 구별해 11절에 기록한다.
1. 같은 슬롯끼리 곱하면 행렬곱이 되는가
1.1 필요한 것은 한 행과 한 열의 내적이다
의 행렬곱을 라 하자. 원하는 출력은
반면 같은 슬롯의 값을 바로 곱하면
이다. 는 성분별 곱, 즉 Hadamard product다. 원문 도식의 곱 기호도 이 계산 내용에 맞춰 로 통일한다.
행렬곱을 만들려면 서로 다른 위치에 있는 값들을 같은 출력 슬롯으로 가져온 뒤, 필요한 곱을 더해야 한다.
1.2 원문이 attention을 예로 드는 이유
원문의 동기는 Transformer의 attention이다.
는 query와 key의 차원이다. 이 식은 원 논문의 scaled dot-product attention과 같다. Vaswani et al., §3.2.1[2]
를 암호화해 평가하는 설정에서는 같은 계산에 두 암호문의 곱이 필요하다. 여기서는 그 행렬곱의 구성을 다룬다. softmax까지 이 단원의 선형 재배치만으로 계산한다는 뜻은 아니다.
1.3 원문 필기의 숫자를 고정한다
필기에 등장하는 부터 까지의 행렬과, 그 배 값을 쓰는 행렬을 사용하자.
좌표는 부터 센다. 왼쪽 위 출력은
마지막 항에 필요한 값은 첫 열의 이다. 오른쪽 아래 값 을 넣지 않는다. 이 네 곱을 한 출력 슬롯에서 차례로 만들 수 있도록 배치를 정하는 것이 목표다.
2. 슬롯 전체의 회전과 행·열 회전을 구별한다
2.1 행 우선으로 넣고 회전 방향을 정한다
행렬을 행 순서로 펼친 벡터를
로 둔다. 벡터의 왼쪽 회전은
이다. 암호문 회전 는 이 슬롯 변환을 근사적으로 수행한다.
우선 행렬이 전체 슬롯을 채우는
설정으로 설명한다. 예제는 , , 의 작은 계산 모형이다. 이 CKKS 설정에서 은 의 거듭제곱이다. 실제 슬롯이 더 많을 때와 행렬 크기가 맞지 않을 때는 10절에서 따로 다룬다.
2.2 전체를 한 칸 돌리면 행 끝에서 다른 값이 온다
예제의 펼친 입력은
이를 전체적으로 한 칸 돌리면
첫 행에 대응하는 네 슬롯은 다. 각 행 안에서 한 칸 순환시키려면 이어야 한다. 원문 필기의 전역 회전 그림과 행별 회전을 혼동하지 않는다.
2.3 RowRot와 ColRot의 의미
이 글에서 행별 왼쪽 회전과 열별 위쪽 회전은
로 정의한다. 원문의 연산 방향과 같다. 행별 회전은 각 행 안에서 순환하고, 열별 회전은 각 열 안에서 순환한다.
원본 에 한 칸씩 적용하면
뒤에서 행별 회전은 마스크와 두 슬롯 회전으로, 열별 회전은 한 슬롯 회전으로 구현한다.
3. 모든 출력 위치에 맞게 두 행렬을 재배치한다
3.1 먼저 출력 (0,0) 하나만 생각한다
원문 26번 슬라이드는 의 첫 행과 의 첫 열을 먼저 정하고 나머지는 회색으로 비워 둔다. 회색은 배치를 아직 정하지 않았다는 표시다. 실제 입력의 나머지 값을 으로 지운다는 뜻은 아니다.
위쪽 행을 왼쪽으로, 왼쪽 열을 위로 같은 횟수만큼 돌리면 위치의 곱은
를 차례로 읽는다. 이들을 더하면 첫 출력이 된다.
3.2 출력 (0,1)에는 B의 두 번째 열을 다르게 놓는다
의 첫 행은 이미 원래 순서다. 에는 이 있으므로, 처음 짝지을 값은 이어야 한다.
따라서 의 두 번째 열을 위로 한 칸 순환시켜
순서로 놓는다. 같은 회전·곱·합은 에서
를 만든다. 항의 순서가 순환했지만 필요한 내적은 같다.
3.3 모든 열을 채운다
같은 논리로 의 번째 열을 위로 칸 이동한다. 원문 28번 슬라이드의 배열이다.
이면 기호로는
3.4 A의 나머지 행도 채운다
출력의 번째 행을 맞추려면 의 번째 행을 왼쪽으로 칸 이동한다. 원문 29번 슬라이드는 두 번째 행을, 30번은 전체 행을 채운다.
일 때는
이제 같은 좌표 의 두 값은 공통 내부 인덱스 를 사용한다. 이후 는 행별로, 는 열별로 같은 횟수만큼 더 돌리면 된다.
4. 네 연산으로 행렬곱 항등식을 쓴다
4.1 원문의 σ·τ·φ·ψ
행렬 인덱스를 로 나눈 나머지로 읽는다는 조건 아래, 네 연산은 다음과 같다.
| 연산 | 성분 정의 | 하는 일 |
|---|---|---|
| 각 행을 그 행 번호만큼 왼쪽 이동 | ||
| 각 열을 그 열 번호만큼 위로 이동 | ||
| 모든 행을 각각 한 칸 왼쪽 이동 | ||
| 모든 열을 각각 한 칸 위로 이동 |
두 번째 열의 식은 각 연산의 성분이다. 와 는 각각 칸 이동을 뜻하고, 이면 항등 연산이다. 이 거듭제곱은 행렬 자체의 곱을 뜻하지 않는다.
4.2 같은 k끼리 곱해 더한다
원문의 핵심 식은
재배치 를 사용하면
첫 행렬을 한 칸씩, 두 번째 행렬도 같은 횟수만큼 이동해 곱한다. 필요한 곱은 개다. 이때 각각의 성분별 곱 한 번으로 개 출력 위치의 항을 동시에 만든다.
4.3 모든 출력 성분에서 맞는 이유
출력 에서 번째 항은
두 항의 내부 인덱스가 정확히 같다. 가 부터 까지 변하면
도 을 한 번씩 지난다. 따라서
원문의 네 순열과 이 항등식은 같은 방법을 제시한 논문의 §3.1과도 대조했다. Jiang–Kim–Lauter–Song, Secure Outsourced Matrix Computation[3]
5. 4×4 필기 예제를 끝까지 계산한다
5.1 두 재배치 결과
1절의 숫자를 넣으면
원문 필기의 두 재배치 배열과 같은 결과다.
5.2 네 번의 곱이 만드는 값
각 출력 위치에서 생기는 곱을 확인하자. 표의 네 항은 순서다.
| 출력 위치 | 내부 인덱스 순서 | 네 항의 값 | 합 |
|---|---|---|---|
예를 들어 에서는
이는 원래 순서의
와 같다. 한 위치의 계산을 맞추기 위해 다른 위치를 차례로 덮어쓰는 과정이 아니라, 모든 출력 위치에서 이 관계가 동시에 성립한다.
필기의 다른 내적도 원래 행·열 순서로 확인하면
이다. 항등식으로 계산한 같은 위치의 값과 일치한다.
회전의 입력도 구별한다. 의 두 번째 행은 지만, 이미 재배치한 를 회전한 의 두 번째 행은 이다. 원본 행렬의 한 칸 이동 예시를 그대로 의 값으로 쓰지 않는다.
5.3 전체 16개 출력
직접 행렬곱과 재배치·회전·성분별 곱의 합은 모두
을 준다. 펼친 벡터의 실제 슬롯 회전과 다음 절의 마스크를 사용한 계산에서도 모든 출력이 같았다. 이는 정수 벡터 계산의 검산이며, CKKS 암호 라이브러리의 잡음 실험은 아니다.
6. σ와 τ를 평문 마스크·슬롯 회전으로 구현한다
6.1 σ에서 한 행은 두 조각으로 나뉜다
번째 행을 왼쪽으로 칸 옮기려면, 출력 열 에 따라
이다. 펼친 벡터에서 필요한 회전량은 각각 , 다.
원문처럼 마스크 이름을 로 두자. 에 대해
이다. 즉 번째 행의 앞부분을 고른다.
음수 회전은 에 대해
로 정의한다. 이 마스크는 해당 행의 뒤쪽 순환 부분을 고른다. 두 종류를 합치면
마스크는 총 개이며, 은 회전 없이 원본을 쓴다.
6.2 필기의 두 번째 행을 마스크로 분리한다
의 두 번째 행은 원래 이고, 재배치 목표는 다.
두 결과를 더하면 목표 행이 된다. 원문 필기의 여러 조각을 더하는 그림과 배열은 이렇게 필요한 위치만 남기는 평문 마스크다.
| 출력 행 | 앞부분 회전 | 앞부분 값 | 뒤쪽 회전 | 뒤쪽 값 |
|---|---|---|---|---|
| 없음 | 없음 | |||
6.3 τ는 열마다 다른 전체 회전을 고른다
원문의 는 번째 열만 인 마스크다.
행 우선 배치에서 슬롯 회전은 각 열을 위로 칸 옮긴다. 그 결과 중 번째 열만 남기면
의 열별 회전량은 다. 원문 필기에 적힌 네 숫자는 이 간격이다. 모든 열에 같은 네 칸 회전을 적용한 것이 아니라, 열마다 해당 회전의 결과를 골라 합친다.
6.4 마스크가 공개된 평문이어도 되는 이유
는 행렬 크기와 슬롯 위치로 정해지는 배열이다. 비밀인 의 원소를 담지 않는다. 따라서 평가자가 이 마스크를 공개된 평문으로 준비해도 입력 행렬을 복호화할 필요가 없다.
이 점이 필기의 “마스크가 plaintext인가?”라는 질문에 대한 답이다. 암호화된 두 입력과, 위치를 선택하기 위한 공개 마스크는 역할이 다르다.
7. φ는 두 회전, ψ는 한 회전이다
7.1 한 행 안의 순환은 끝 열을 따로 가져온다
마지막 열을 제외한 위치가 인 , 마지막 열만 인 을 정의한다. 이면
라 하면
첫 회전은 각 행의 앞 개 출력에 필요한 값을 가져온다. 두 번째 회전은 각 행의 마지막 출력에 그 행의 첫 값을 가져온다. 마스크가 두 결과를 올바르게 이어 붙인다.
7.2 열별 한 칸 이동은 d슬롯 이동이다
전체 슬롯이 행렬 한 개를 채우는 조건에서
한 행의 길이가 이므로 위로 한 행을 가져오면 된다. 마지막 행은 전체 슬롯의 순환으로 첫 행을 읽는다. 원문 34번 슬라이드의 두 연산은 각각 슬롯 회전 두 번과 한 번을 요구한다.
7.3 k칸 이동도 원래 입력에서 직접 만든다
에 대해 앞 개 열이 인 마스크 , 나머지 개 열이 인 마스크 을 쓰면
따라서 각 의 결과를 같은 재배치 입력에서 독립적으로 만들 수 있다. 를 번 연속 실행하며 평문 곱의 단계를 계속 쌓아야 한다는 뜻이 아니다. 항등인 은 재배치 결과를 재사용한다.
8. BSGS로 준비 단계의 회전을 줄인다
8.1 먼저 직접 계산하는 횟수
항등 회전을 제외하고 필요한 직접 회전키가 있다고 가정한다. 기본 구현의 회전 횟수는
| 단계 | 회전 횟수 |
|---|---|
| 준비 | |
| 준비 | |
| , | |
| , | |
| 전체 |
원문은 앞의 두 준비 단계를 09번 글의 BSGS[4]로 최적화한다. 준비 후의 행·열 이동은 각 항당 회전 두 번·한 번인 구조를 유지한다.
8.2 음수 오프셋과 d 간격도 같은 방식으로 묶는다
보충으로, 다음 형태의 선형변환을 생각하자. 는 공개된 평문 슬롯 벡터다.
두 재배치에 적용할 값은
| 변환 | 항 수 | 슬롯 간격 | |
|---|---|---|---|
블록 크기를 , 블록 수를 로 두고
라 하자. 원래 범위 밖의 마스크는 으로 두면
바깥 회전이 평문 벡터의 사전 회전과 상쇄되고, 입력에는 총
만큼의 회전이 남는다. 평문 마스크의 사전 회전은 공개 데이터의 준비 계산이다. 암호문의 회전 횟수에 넣지 않는다.
안쪽 회전은 번이고, 바깥 회전은 많아야 번이다. 바깥 오프셋이 인 블록은 그 회전도 생략한다. 특히 인 에서는 첫 블록의 바깥 회전이 항등이므로
번이면 된다. 이 식은 마지막 블록이 덜 차는 경우에도 적용된다.
8.3 4×4에서 실제 그룹을 확인한다
의 항 수는 개다. 으로 묶으면
의 세 블록이다. 안쪽 입력 회전은 , 바깥 회전은 이다. 항등을 빼면 총 번이다. 각 블록의 마스크를 반대 방향으로 사전 회전하는 단계도 포함해야 같은 변환이 된다.
는 로 묶는다. 안쪽 입력 회전은 , 바깥 회전은 이다. 항등을 빼면 총 번이다.
8.4 원문의 근사 회전 수와 전체 비용
균형 있게 로 잡으면 원문에 적힌 준비 단계의 근사 횟수
를 얻는다. 여기에 나머지 번을 더하면
원문 35번 슬라이드는 상수항과 정수 블록의 차이를 생략해
로 적는다. 정확한 작은 크기의 횟수는 블록 선택과 항등 생략을 따로 계산해야 한다.
다음은 위 구성에서 확인한 선택 예다. 최적 하한이나 실측 시간이 아니다.
| 블록 | 블록 | 직접 구현 | BSGS 사용 | |
|---|---|---|---|---|
대조 논문의 §3.3.3은 다른 블록 구분으로 준비 단계의 를 제시한다. 본문의 는 이번 강의 원문의 구분에 맞춰 유도한 값이다. 두 계수를 같은 숫자라고 옮기지 않는다.
9. 암호문 행렬곱으로 연결한다
9.1 일반 배치의 두 암호문에서 시작한다
같은 비밀키로 암호화한 입력 가 있고, 각 입력 행렬을 행 우선으로 담았다고 하자. 필요한 회전키와 재선형화키가 준비됐다고 가정한다.
평문 마스크를 인코딩한 것을 라 하면 선형 재배치의 계산 구조는
이다. 이때 는 평문·암호문 곱이다. BSGS를 쓰면 같은 선형변환을 8.2절의 순서로 평가한다.
여기서는 소유자가 미리 재배치한 입력을 보내 주는 비용을 무료로 가정하지 않는다. 서버가 일반 배치의 암호문에서 를 계산하는 준비 비용까지 포함했다.
9.2 서로 대응하는 두 암호문을 곱한다
재배치와 필요한 스케일 처리를 마친 암호문을 라 하자. 각 에 대해
를 만든다. 왼쪽은 암호문, 오른쪽은 이상적인 슬롯 값의 대응이며, 실제 디코딩에는 근사 오차가 있다.
최종 계산은
이 곱은 앞의 마스크 곱과 달리 암호문·암호문 곱이다. 합산 직전의 피연산자들을 같은 법·레벨과 대응 스케일로 맞춘다.
재배치 이후의 성분별 암호문 곱은 번, 그 결과의 덧셈은 번이다. 각 곱은 개 슬롯 위치를 한꺼번에 처리한다. 평문 마스크 곱과 재배치 안의 덧셈 횟수는 이 마지막 단계의 숫자에 포함하지 않았다.
9.3 스케일·재선형화·rescaling
마스크를 스케일 으로 인코딩했다면 입력 스케일 는 그 평문 곱에서
이 된다. 준비와 의 마스크 곱이 추가하는 스케일·레벨을 처리해야 한다. 의 재사용 입력과 다른 의 결과도 맞춰야 한다. 스케일 숫자를 임의로 바꾸어 같다고 선언하는 것으로 이 과정을 대신하지 않는다.
모든 와 를 유효한 공통 레벨에 맞추고, 스케일을 각각 로 준비했다면 raw 곱과 그 합의 스케일은
보통의 두 성분 암호문을 곱한 raw 결과는 비밀키 에 대해
로 복호화되는 세 성분을 가진다. 06번 글의 재선형화[5]는 이를 두 성분 표현으로 돌려놓는다. 원문 필기의 key switching 비용과 연결되는 부분이다. 슬롯 회전에도 08번 글의 키 전환[6]이 들어간다.
곱마다 재선형화하거나, 같은 형태의 raw 곱들을 먼저 더한 뒤 재선형화하는 구성을 사용할 수 있다. rescaling도 합의 표현 범위·오차 조건을 확인해 배치한다. 로 rescale하면
최종 암호문 의 목표 관계는
이다. 이는 2.1절의 한 행렬·전체 슬롯 조건에서 쓴 식이다.
9.4 d개의 곱과 곱셈 깊이는 다르다
마지막 단계의 개 암호문 곱은 서로 독립적으로 계산해 더한다. 따라서 이 단계의 암호문·암호문 곱 깊이는 1이다. 곱을 개 수행한다고 깊이가 가 되는 것은 아니다.
다만 앞의 선형 재배치에도 인코딩된 마스크 곱과 스케일 처리가 있다. 전체 CKKS 계산이 항상 법 체인 한 단계만 소비한다고 해석하지 않는다. 원문의 회전 수도 암호문 곱·재선형화·평문 곱·메모리·실제 시간을 모두 포함한 비용 단위는 아니다.
행렬 크기와 함께 필요한 슬롯 수도 커지므로, 회전 한 번의 비용도 고정된 상수로 볼 수 없다.
10. 실제 슬롯 수가 행렬 크기와 다르면
10.1 남는 슬롯을 0으로 채우기만 하면 원문 식이 깨질 수 있다
행렬을 슬롯의 앞 개에 넣고 나머지는 으로 두었다고 하자. 전체를 슬롯 회전하면 첫 행이 마지막 행으로 순환해 오지 않는다. 원본 에서 마지막 출력 행은
이지만, 원하는 의 마지막 행은
이다. 따라서 단순히 라는 조건만 붙여 원문의 한 번짜리 열 회전을 그대로 사용하지 않는다.
10.2 같은 행렬 블록을 반복하면 논리적 순환을 유지할 수 있다
보충으로 가 을 나누고, 같은 행렬의 벡터를 전체 슬롯에 반복해서 넣으면
이다. 와 평문 마스크도 같은 블록 주기로 반복한다. 그러면 슬롯 회전은 각 출력에서 원래 주기의 값과 동일하게 읽히고, 결과도 의 반복 블록이 된다.
이것은 동일한 행렬을 반복하는 배치다. 서로 다른 행렬을 연속 블록에 넣고, 경계 처리 없이 같은 공식이 독립적으로 적용된다고 주장하지 않는다.
예제는 슬롯에서 이 반복 배치를 검산했고, 모든 결과 블록이 5.3절과 같았다. 실제 CKKS 라이브러리의 실행이나 보안 매개변수 검증을 한 것은 아니다.
10.3 행렬 차원을 맞추는 패딩도 슬롯 뒤에 0을 붙이는 것과 다르다
행렬 두 개를 로 확장하려면 행과 열을 각각 으로 채운다.
이 경우 회전식·마스크·비용 계산의 행렬 차원은 이고, 개 슬롯에 확장 행렬을 행 우선으로 넣는다. 원래 아홉 값을 연속으로 놓고 뒤에만 일곱 개의 을 붙이는 배치와는 다르다.
11. 원문의 표기와 필기를 옮기며 점검한 부분
-
31번 슬라이드 위쪽 합. 상한 와 첫 회전 인자 이 아래 항등식과 맞지 않는다. 합의 범위는 로, 두 회전의 인자는 모두 로 바로잡았다.
-
33번 슬라이드 음수 마스크. 끝 좌표가 로 인쇄돼 마지막 열을 지정하지 못한다. 올바른 범위는 이다.
-
44쪽 전역 회전 필기. 전체 한 칸 회전과 행별 한 칸 회전의 경계가 다르다. 2.2절의 반례와 7.1절의 두 마스크로 구별했다.
-
숫자 필기의 입력 구별. 를 회전한 값과 를 회전한 값은 다르다. 2.3절과 5.2절에서 각각 계산했다.
특히 행렬곱 항등식의 합은 개 항이다. 상한을 로 두면 항이 하나 더 생기고, 첫 회전 인자를 상수 로 두면 같은 입력 원소만 반복해서 곱하게 된다. 음수 마스크의 끝 열도 실제 슬롯 인덱스에서 유도해 바로잡았다.
원문의 는 평문 위치 선택 마스크이며, 는 암호화된 데이터다. 그림의 배열, 공개 마스크, 암호문 평가를 구별해 읽는다. 이상적인 마스크의 항등식과 실제 CKKS 인코딩·키 전환·재선형화·rescaling 오차도 구별한다.
원문에 있는 네 연산의 정의와 구현, BSGS 준비, 최종 회전 구성을 여기까지 옮겼다. 다음 범위는 46쪽 Activation Functions와 Polynomial Approximation부터다.
참고 링크
- https://noir1458.github.io/posts/ai-security-homomorphic-convolution-rotations-masks-and-channels/
- https://arxiv.org/pdf/1706.03762
- https://yongsoosong.github.io/files/papers/matrix.pdf
- https://noir1458.github.io/posts/ai-security-ckks-matrix-vector-multiplication-and-bsgs/
- https://noir1458.github.io/posts/ai-security-ciphertext-multiplication-key-switching-and-rescaling/
- https://noir1458.github.io/posts/ai-security-slot-rotation-and-homomorphic-conjugation/
Comments