암호화 된 대용량 데이터에 동형 연산 적용
현재 PALISADE 라이브러리를 사용하여 동형 암호화를 실험하고 있습니다 .
큰 암호화 된 입력에 더하기 및 곱하기와 같은 간단한 작업을 적용하고 싶습니다. 예를 들어 int 값의 벡터 / 배열을 입력 A[3200]하고 입력 B[4096]하면 암호화됩니다. 그 두 개의 입력으로 Enc(A)하고 Enc(B)나는 곱셈을 적용 할 :
EvalMult(Enc(A[0]), Enc(B[42]))
*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed
위에서 설명한 요구 사항의 구현은 두 가지 다른 방법으로 해결할 수 있습니다.
입력을 단일 암호문 (SIMD와 같은)으로 압축하고 작업
EvalIndexAt()을 위해 암호화 된 입력에서 올바른 값을 가져 오는 데 사용할 수 있습니다 .A와 B의 각 값을 개별적으로 암호화합니다.
설명 된 솔루션 중 효율성 측면에서 어떤 것이 최선인지 잘 모르겠습니다 . 첫 번째 접근 방식은 전체 입력에 대해 하나의 암호화 프로세스 만 필요하다는 주요 이점이 있지만 항상 EvalAtIndex()메서드를 사용하여 올바른 요소에 액세스해야 하고 입력이 클수록 가져 오기 계산이 느려진다는 단점 EvalAtIndexKeyGen()이 있습니다. (적어도 내 컴퓨터에서)
두 번째 접근 방식은 EvalAtIndex()필요하지 않기 때문에 더 적합 해 보이지만 각 값을 개별적으로 암호화하는 데 상당한 시간이 소요됩니다.
어떤 생각 권장 사항이 있습니까?
답변
질문 해주셔서 감사합니다.
접근 방식 # 1 (SIMD)의 주요 이점은 단일 동형 더하기 또는 곱하기 (매우 효율적)를 사용하여 벡터 (4096 개 이상의 정수 / 실수)의 더하기 및 곱하기를 수행 할 수 있다는 것입니다. 회전 ( EvalAtIndexPALISADE에서 호출 됨)은 개별 인덱스에 액세스하거나 효율적인 합산 (내적에서와 같이), 행렬 곱셈 등을 수행 할 수있는 추가 작업입니다.이 접근 방식은 또한 암호문 확장 계수가 4096x 이상으로 훨씬 더 작습니다. 접근 # 2. 일반적으로 옵션 # 1이 실제로 선호됩니다 (그리고 옵션 # 2로 가고 싶은 실제 사용 사례를 생각할 수 없습니다).
곱셈 비용을 최소화하기 위해 한 블록에 대해 단일 회전이 필요하도록 연속 블록으로 벡터를 압축 할 수 있습니다. 예를 들면
EvalMult(Enc(A[0:5]),Enc(B[42:47))
사용할 수있는 또 다른 기술은 EvalFastRotation(PALISADE v1.10.x의 CKKS 및 BGVrns에만 사용 가능)입니다. 동일한 암호문을 여러 번 회전해야하는 경우 암호문에 대해 미리 계산 한 다음 더 저렴한 회전을 사용할 수 있습니다 (BV 키 전환에서 가장 많은 이점을 얻을 수 있음).https://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp 예를 들어.
또한 여러 회전이 필요한 경우 생성되는 키 수를 최소화하는 방법도 있습니다 (필요한 회전 수의 대략 제곱근 만 계산), 예를 들어에 설명 된 baby-step-giant-step 기술을 사용하여 https://eprint.iacr.org/2018/244 (이러한 기술은 PALISADE 기반 애플리케이션에서 구현할 수 있습니다.)
곱셈을 수행하기위한 패턴이 알려진 경우 벡터 패킹의 특별한 순서를 사용할 수도 있습니다 (이렇게하면 회전이 단일 회전 작업을 사용하여 벡터에 여러 블록을 준비합니다). # 일반 텍스트 슬롯 (배치 크기)이 ring dimension/ 2 와 같을 때 CKKS 및 BGVrn 모두에서 순환 (랩 어라운드)됩니다 . 이보다 작은 벡터가있는 경우 항상 필요한만큼 작은 벡터를 복제 / 복제 할 수 있습니다. 채우기 위해 ring dimension/ 2.
요약하면 SIMD와 같은 벡터 측면에서 문제를 생각하면 가장 큰 효율성 향상을 얻을 수 있습니다. 그런 다음 문제 / 모델을 재구성하여 HE가 제공하는 도구 세트를 최대한 활용할 수 있습니다. 어떤면에서 이것은 벡터화 된 명령어 (예 : AVX) 또는 행렬 지향 프로그래밍 (MATLAB과 같은)을 사용하는 프로그래밍과 유사합니다.