몇 분 안에 완전 동형 암호화 FHE 이해하기: 작동 모드 및 적용 시나리오

원제:완전 동형 암호화: 소개 및 사용 사례

원문 제목. 니콜라스 가마 및 산드라 구아쉬, SandBoxAQ 작성

편집: Faust, geekweb3

이 문서 블로그는 완전 동형 암호화(FHE)를 체계적으로 소개하지만, 여기서는 수학적 세부 사항을 다루기보다는 기본 메커니즘 설계 관점에서 기술을 설명하고, 독자가 FHE의 기본 작동 로직을 처음 이해할 수 있도록 하며, FHE의 주요 애플리케이션 모델 몇 가지를 소개합니다.

용어를 언급할 때 "암호화"라고 하면 가장 먼저 떠오르는 적용 시나리오는 일반적으로 미사용 암호화와 전송 중 암호화입니다. 전자는 데이터를 암호화하여 하드 드라이브, 모바일 장치 또는 클라우드 기반 서버와 같은 하드웨어 장치에 저장하며, 권한이 있는 사람만 해독된 일반 텍스트 콘텐츠를 보거나 다시 쓸 수 있습니다. 반면 전송 중 암호화는 인터넷을 통해 전송되는 데이터를 지정된 사람만 해석할 수 있도록 하는 것을 목표로 하며, 데이터가 공용 라우터나 채널을 통해 전송되더라도 중개자가 평문을 개인적으로 해독할 수 없습니다.

이 두 시나리오 모두 암호화 알고리즘에 의존하며, 데이터 무결성, 즉 전송 중에 중개자가 데이터를 변조하지 않았음을 추가로 보장하는 "인증된 암호화"라고 알려진 암호화 알고리즘을 사용합니다.데이터가 암호화되면 지정된 사람만 데이터를 읽을 수 있습니다. 이를 "인증된 암호화"라고 합니다: 데이터가 암호화되면 데이터 전송 과정의 참여자는 평문을 개인적으로 해독할 수 없으며(기밀성), 중개자는 원본 암호문(무결성/진본성)을 변조할 수 없습니다(무결성/진본성).

다자간 협업 시나리오의 경우, 개인정보 보호 기술 범주에 속하는 암호 텍스트의 복잡한 처리가 필요하며 완전동형암호(FHE)가 그 중 하나입니다. 온라인 투표의 경우를 예로 들어 보겠습니다. 대통령 선거에서 유권자가 자신의 투표를 암호화하여 중개 기관에 제출하면, 중개 기관은 모든 투표를 통합된 방식으로 수집하고 각 대통령 후보의 득표수를 계산하여 최종적으로 하나의 선거 결과만 공개한다고 가정해 보겠습니다.

유감스럽게도 앞서 언급한 '인증된 암호화' 방식을 사용하면 개표를 담당하는 중개 기관이 모든 사람의 투표 데이터의 평문을 해독하여 개표 작업을 수행해야 합니다. 하지만 이렇게 하면 모든 사람의 투표 결과가 노출되며 개인정보를 보호할 수 없습니다. 이론적으로는 모든 사람의 투표 데이터를 섞어서 섞을 수 있지만(일부 전자 투표 프로토콜에서는 그렇게 하고 있습니다), 종이 투표용지와 달리 기존의 암호화 메커니즘으로는 데이터의 무결성(변조되지 않음)을 보장하면서 암호화된 투표 데이터를 해당 유권자의 신원과 분리하기 어렵습니다.

온라인 투표 시나리오에서는 투표 개표를 담당하는 중개자 주변에 TEE(신뢰할 수 있는 실행 환경)와 같은 하드웨어 격리벽을 추가할 수 있습니다. 이 기술은 악의적인 공격자가 개표 프로그램과 상호작용하기 어렵게 만들지만, 하드웨어 수준의 취약점으로 인해 암호문을 해독하는 키가 TEE 밖으로 유출될 수 있으며 소프트웨어에 포함된 버그와 달리 하드웨어 설계의 취약점은 쉽게 수정할 수 없습니다.

위 시나리오에 대응하기 위해 전체 동형 암호화(FHE) 기술을 도입할 수 있습니다. FHE는 암호문을 해독하지 않고 암호문에서 직접 함수를 계산하여 해당 함수의 출력값을 암호화된 결과로 얻을 수 있는 특수한 형태의 암호화 체계로, 개인정보를 보호할 수 있습니다.

FHE 시나리오에서 함수 ? 의 수학적 구조는 공개적으로 사용 가능하므로 입력 암호문 ? 는 결과 ? (?) 의 처리 흐름은 공개 정보이므로 개인 정보를 침해하지 않고 클라우드에서 실행할 수 있습니다. 여기서 중요한 점은 ? 와 ? (?) 는 모두 키로 해독해야 하는 암호화된 암호 텍스트이며, 대부분의 경우 둘 다 동일한 복호화 키에 해당합니다.

위 그림은 온라인 투표를 위한 세 가지 암호화/복호화 체계를 보여주며, 여기서 E( )는 암호화 작업을, D( )는 복호화 작업을 나타냅니다.

왼쪽 그림에서 신뢰할 수 있는 중개자가 투표 결과를 발표하기 전에 개별 투표 데이터를 난독화 및 복호화합니다. 이 중개자가 개인정보를 침해하지 않으며 투표 집계가 정확하다고 가정해야 합니다.

가운데 다이어그램에서는 데이터 무결성과 개인정보 보호를 보장하는 TEE가 사용됩니다.

가운데 다이어그램에서는 데이터 무결성과 개인정보 보호를 보장하는 TEE가 사용됩니다.

가운데 그림에서는 결과를 게시하기 전에 신뢰받는 중개자가 개별 투표 데이터를 난독화하고 암호를 해독하는 방식을 취합니다. 왼쪽;">그리고 가장 오른쪽 그래프에서는 동형 암호화가 사용됩니다. 암호화된 투표 데이터를 공개적으로 합산한 다음 복호화하여 최종 득표수를 계산하는 결과를 얻을 수 있습니다

FHE(완전 동형 암호화)는 압축적인 암호화 체계입니다. 출력 결과는? (?) 암호 텍스트 데이터의 크기와 그 결과를 해독하는 데 필요한 작업량은 원래 평문 데이터에 해당하는 입력 데이터 ? 에 해당하는 입력 데이터에만 의존하며, 사용된 계산 프로세스에 의존하지 않으며, 이는 종종 단순히 ? 함수와 ? 함수를 소스 코드에 결합한 다음 수신자에게 맡겨 ? 에 입력해 계산 작업을 완료하는 ? 에 입력하여 계산 작업을 완료합니다.

실제로 FHE 아웃소싱 모델은 종종 TEE와 같은 보안 실행 환경의 대안으로 간주되는데, FHE 보안은 암호화 알고리즘에 기반하며 하드웨어와 같은 물리적 장치에 의존하지 않습니다. 따라서 FHE는 패시브 사이드 채널 공격이나 클라우드 서버에 대한 공격에 완전히 면역이 됩니다. 컴퓨팅 작업을 아웃소싱해야 하지만 데이터가 매우 민감한 경우, 클라우드 기반 서버 뒤에 고급 컨트롤러가 있는 경우가 많기 때문에 AWS에 구축된 가상 머신(VM)을 사용하는 것을 꺼릴 수 있다고 상상해 보십시오. 또한 TEE를 실행하는 호스트가 해당 컴퓨팅 작업이 실행될 때 발생하는 전력 소비량이나 런타임 등을 모니터링하고 해당 데이터에서 일부 정보를 유추할 수 있기 때문에 SGX나 TEE 같은 것을 사용하는 것을 주저할 수도 있습니다.

그러나 FHE를 사용하면 컴퓨팅 작업을 아웃소싱하는 사람들이 안심할 수 있습니다. 왜냐하면 FHE 시스템에서 개인 정보를 해독하려면 사용하는 암호화 알고리즘을 해독해야 하는데 현재로서는 사실상 불가능하기 때문입니다.

그러나 암호화 알고리즘을 통해 공격자가 키를 알지 못한 채 ? 반면에 일반 확장성을 사용하면 공격자는 해당 일반 텍스트에 대한 지식이 없어도 ? (?) 공격자는 암호화 알고리즘을 실행하는 하드웨어를 공격하여 출력에 영향을 줄 수 있는 활성 부채널 공격에 해당합니다. 이는 무섭게 들릴 수 있지만 FHE의 설계상 이러한 유형의 악의적인 공격은 계산 흐름에 중복성을 생성하여 우회할 수 있습니다.

요약하면, FHE는 일반적으로 다음을 포함한 여러 키 세트를 사용합니다.

암호 해독 키:

Decryption. 키): 전체 FHE 암호화 시스템에서 마스터 키이며, 다른 모든 유형의 키는 마스터 키에서 파생될 수 있습니다. 복호화 키는 일반적으로 사용자가 로컬에서 생성하며 외부로 전송되지 않으며, 소유자만 FHE 암호 텍스트를 해독하는 데 사용할 수 있습니다. 즉, 다른 사람이 전송 중에 암호 텍스트를 가로채더라도 암호 해독 키를 가지고 있지 않으면 암호를 해독할 수 없습니다.

암호화 키: FHE의 공개 키 모드에서 암호화 키는 평문 텍스트를 암호 텍스트로 변환하는 데 사용되는 키입니다. 암호화 키는 초기 암호 텍스트를 생성한 사람이 암호 해독 키/마스터 키의 소유자가 아닐 때 암호화에 사용됩니다. 이 키는 일반적으로 중간 크기이며 여러 개의 임의의 0 암호화로 구성됩니다. FHE는 아핀 함수를 지원하므로 모든 메시지를 암호화하는 데 충분합니다.

공개 키 암호화 모드에서 암호화 키는 일반적으로 공개되며 누구나 데이터를 암호화하는 데 사용할 수 있지만 복호화 키 소유자만 지정된 방식으로만 복호화할 수 있습니다.

평가 키: 계산 키는 암호문에서 동형 연산을 수행하는 데 사용되는 특수 키입니다. 암호문에서 동형 연산을 수행하는 데 사용되는 특수 키로, FHE 시스템이 암호문을 복호화하지 않고도 암호문에서 동형 연산을 수행할 수 있게 해줍니다. 암호 텍스트를 복호화하지 않고도 ? 계산키를 공개키처럼 공개할 수 있어 다른 사람이 계산키를 알고 있어도 암호문을 복호화할 수 없고 ? 암호문에서 동형 연산만 수행하여 출력을 얻을 수 있습니다.

또한, 계산 키를 사용하여 계산할 때 암호문의 구조는 변경되지 않으며 암호문에 대한 동형 연산 ? 동형 연산을 통해 얻은 결과를 새로운 암호문으로 재암호화하여 계산 과정의 프라이버시를 보장하고, 계산 과정이 공개되어 있어도 기밀 데이터가 유출되지 않도록 합니다.

위 키 홀더 중 복호화 키/마스터 키 홀더는 가장 민감한 키 홀더로, 동형 연산의 전체 체인/실행 과정이 효율적이고 오류가 없는지, 최종 암호 텍스트가 안전한지 확인한 후 이를 복호화하여 결과를 일반 텍스트로 가져오는 역할을 합니다. . 악의적인 연산이 FHE 연산 체인에 도입되면 복호화 중에 복호화 키가 손상될 수 있습니다. 하지만 다행히 동형 연산을 공개적으로 수행하여 누구나 검증할 수 있습니다.

FHE의 특정 시나리오/패턴

이 섹션에서는 FHE의 몇 가지 일반적인 시나리오/패턴을 설명하고 각각의 장단점에 대해 논의합니다.

아웃소싱 모드

이 다이어그램에서 왼쪽의 주황색 키 기호는 암호 해독 키(및 그 소유자 앨리스)를 상징합니다. FHE 암호 텍스트는 암호 해독 키와 같은 색의 자물쇠로 표현됩니다. 개인 데이터를 제공하는 쪽은 원통으로 표시됩니다.

여기서는 앨리스만 개인 데이터를 제공합니다. Bob 측에서는 동형 계산 함수와 계산 키가 공개되어 있으며, 녹색 상자로 표시된 계산 체계는 결정론적 방식으로 수행되어 누구나 로컬에서 계산 과정을 다시 실행하고 Bob이 제공한 출력에 오류가 있는지 테스트할 수 있습니다

위 아웃소싱 모델도 마찬가지입니다. 은 일반 클라우드 컴퓨팅을 SGX 및 TEE와 유사한 프라이빗 컴퓨팅으로 전환하기 위해 설계된 FHE의 첫 번째 역사적 사용 사례이지만, 위 FHE 알고리즘의 보안은 하드웨어 수준의 보안 조치가 아닌 암호화 알고리즘을 기반으로 합니다. 이 설정에서 앨리스는 일부 개인 데이터를 가지고 있지만 연산 능력이 제한되어 있고, 밥은 강력한 연산 능력을 갖춘 클라우드 서버를 가지고 있으며, 밥은 추가적인 개인 데이터를 제공하지 않습니다.

Alice는 계산 작업을 암호화할 수 있습니까? ()의 입력 매개변수를 암호화하여 암호문 ? 동형 암호화를 통해 밥에게 전송하고, 이후 계산을 하는 밥은 동형 암호화를 통해 ? (?) 를 계산하고 암호화된 결과를 다시 앨리스에게 전송합니다.

현재 하드웨어 장치의 성능을 고려할 때 수행해야 할 계산 작업의 복잡성이 ? ()의 복잡성이 비선형 복잡성을 갖는 경우, FHE 연산을 수행하는 ? () 연산을 수행하는 데 걸리는 시간은 원래 계산보다 최대 100만 배 더 오래 걸리고 메모리 오버헤드는 약 1000배 더 높아집니다. 현재 많은 조직에서 계산 비용을 줄이기 위해 FHE 전용 하드웨어를 개발하고 있으며, 그 예로 Darpa DPRIVE 프로젝트나 CryptoLight 등이 있습니다.

현재 FHE 아웃소싱 모델은 실질적으로 주로 PIR(개인 정보 검색) 시나리오에서 주로 사용되는데, 퍼블릭 서버 컨트롤러인 Bob이 대규모 퍼블릭 데이터베이스를 소유하고 있고 클라이언트인 Alice가 데이터 읽기 요청을 시작하지만 데이터를 조회하려는 사람에 대해 Bob이 알기를 원하지 않는 경우입니다. 이러한 유형의 PIR 시나리오는 동형 암호화 연산의 선형성과 간결함의 이점을 활용하면서 계산 비용을 적정 수준으로 유지할 수 있습니다.

다음 표에는 FHE 아웃소싱 모델의 장점과 단점이 요약되어 있습니다.

두 당사자 컴퓨팅 모드

그래프는 이전과 동일한 색상 설정을 사용합니다. 이번에는 Bob이 계산 프로세스에 일부 개인 데이터를 제공합니다. 그리고 Bob 측의 계산 흐름은 더 이상 공개적으로 검증할 수 없으며, 빨간색 상자로 표시되며, 이는 두 통신 당사자가 정직하지만 궁금해하는 시나리오로 제한되어야 하는 패턴입니다.

즉, 프로토콜이 실행되는 동안 참여자(예: Bob)는 엄격하게 주어진 단계만 주어진 단계를 따르며 의도적으로 잘못된 결과를 출력하거나 프로토콜 실행을 방해하지 않습니다. 그러나 Bob은 "호기심"이 많기 때문에 암호문이나 기타 중간 데이터에서 가능한 한 많은 민감한 정보를 추론하려고 하지만 프로토콜 실행을 방해하지는 않습니다

FHE의 2자 계산 모델에서 유일한 차이점은 계산을 해야 하는 사람이 Bob뿐이라는 점입니다. 모델과 유일한 차이점은 Bob이 계산 프로세스에 일부 개인 데이터를 제공한다는 점, 즉 자신의 개인 데이터를 FHE 계산 프로세스에 추가한다는 점입니다. 이 경우 FHE는 통신 복잡성을 최소화하는 우수한 양 당사자 계산 솔루션이며, 메커니즘 설계를 통해 Bob은 Alice의 개인 데이터를 스누핑하지 않고, Alice는 Bob의 개인 데이터를 스누핑하지 않는다는 강력한 보증을 제공할 수 있습니다.

이 시나리오의 한 가지 잠재적 사용 사례는 암호화에서 "백만장자의 문제"로, 앨리스와 밥은 누가 더 부자인지 알고 싶지만 상대방이 정확히 얼마나 부자인지 알고 싶지 않은 두 명의 백만장자입니다. 그들은 누가 더 부자인지 알고 싶지만 상대방이 정확히 얼마나 가지고 있는지 알기를 원하지 않습니다. 이 문제에 대한 해결책은 일반적으로 실제 이커머스 시나리오에서 사용됩니다.

집계 모드

집계 패턴은 아웃소싱 패턴을 개선한 것으로, 여러 참여자의 데이터를 간결하고(입력 매개변수의 수에 따라 출력이 증가하지 않음) 공개적으로 검증 가능한 방식으로 집계합니다. 일반적인 사용 사례로는 연합 학습 및 온라인 투표 시스템이 있습니다.

클라이언트-. 서버 모드

이 모델은 앞서 언급한 양 당사자 계산 모델을 개선한 것으로, 서버가 독립 키를 가진 여러 클라이언트에 FHE 계산 서비스를 제공합니다. (예: 개인 데이터를 보유한 클라이언트와 서버 측의 개인 AI 모델 또는 서비스 등) 프라이빗 AI 모델 컴퓨팅 서비스에도 FHE를 사용할 수 있습니다(프라이빗 AI 모델 컴퓨팅 서비스). 서버가 소유한 프라이빗 AI 모델은 평문으로 로컬에 저장되며, 각 클라이언트는 계산을 위해 AI 모델에 넣으려는 자체 프라이빗 데이터를 보유하게 됩니다. 궁극적으로 각 클라이언트는 자체 키를 사용하여 자신이 제출한 데이터에 대한 연산 결과를 구문 분석할 수 있습니다.

동형 암호화에 대한 정보 기타 세부 정보

동형 암호화는 외부 계산이 유효하도록 어떻게 보장하나요?

다자간 협업 시나리오에서 FHE를 사용하면 각 참여자가 프로토콜 규정을 정직하게 따를 인센티브가 있기 때문에 더 쉽게 사용할 수 있습니다. 예를 들어, FHE는 서로 다른 국가에 있지만 같은 회사/조직에 속한 두 법인 간에 암호화된 계산을 수행하고 일부 데이터를 집계할 수 있습니다. GDPR과 같은 규정은 특정 통계를 외부에 게시하는 것을 허용하지만 모든 개인 데이터를 동일한 물리적 위치에 중앙 집중적으로 저장하는 것은 금지합니다.

이 경우 FHE를 사용하는 것이 가능하며 모든 참여자가 프로토콜 요건을 정직하게 따를 인센티브가 있습니다. 참가자들이 서로 협력하지 않는 시나리오에서는 계산 작업이 올바르게 실행되었는지 확인하는 가장 쉬운 방법은 중복성을 도입하는 것입니다(다중 서명/합의와 유사). 예를 들어, 앞서 언급한 아웃소싱 및 집계 시나리오에서 동형 계산에 사용되는 함수 공식은 완전히 공개되어 있고 결정론적일 수 있으므로 두 개 이상의 독립 개체가 정확히 동일한 출력 암호 텍스트에 도달하기만 하면 전체 계산 프로세스가 정확하고 결과를 신뢰할 수 있습니다. 중복성 수준이 높을수록 최종 결과의 신뢰성이 높아지지만 효율성 측면에서 상충되는 부분이 있습니다.

또한 계산 작업을 계약한 컴퓨팅 당사자가 입력 및 출력 암호 텍스트에 디지털 서명을 함으로써 FHE 결과의 유효성을 보증하면 누구나 동일한 FHE 계산 과정을 다시 실행하여 컴퓨팅 당사자가 제공한 증명이 유효한지 확인할 수 있습니다. 모든 컴퓨팅 당사자의 스푸핑을 감지하고 처벌할 수 있으며 스푸핑 행위와 스푸퍼를 노출하는 공개적으로 검증 가능한 인증서와 연결할 수 있으며, 이 모델을 강력하게 은폐된 보안이라고 부릅니다.

완전 동형 서명의 경우, 타사 검증자 없이 계산 정확성을 검증하는 또 다른 방법이지만 일반적으로 더 많은 하드웨어 및 소프트웨어 리소스가 필요합니다.

FHE는 최종 수신자가 중간 변수가 아닌 최종 결과만 해독하도록 어떻게 보장하나요?

가장 간단한 방법은 복호화 키 보유자가 FHE 계산 프로세스 중에 생성되는 중간 암호 텍스트에 액세스할 수 없도록 하는 것입니다. 양 당사자 계산 시나리오 또는 클라이언트-서버 시나리오에서 앨리스는 입력 결과를 암호화하고 밥은 암호 텍스트를 계산하여 암호화된 출력을 앨리스에게 다시 전송하는데, 앨리스는 최종 결과만 해독할 수 있고 중간 변수에 액세스할 수 없습니다.

온라인 투표 시스템과 같이 많은 참가자가 AWS와 같은 공용 클라우드 서버에서 암호화된 투표 데이터를 전송하는 클라우드 기반 서버 시나리오에서는 일반적으로 한 명의 수신자에게 암호 해독 키를 제공하지 않고 비밀 공유 방식으로 배포하는 수단이 사용됩니다. 다른 사람이나 조직에 비밀 공유 방식으로 배포됩니다(MPC와 유사). 이 경우 특정 암호문은 다자간 연산을 수행하고 복호화 키를 보유한 구성원 간의 온라인 통신을 허용해야만 해독할 수 있습니다. 구성원 중 일부가 다른 구성원과의 협력을 거부하면 복호화를 수행할 수 없습니다. 이렇게 적절한 임계값을 설정하면 시스템의 전반적인 보안이 향상됩니다.

동형 암호화를 위한 블록 구축

동형 암호화는 부분 동형 암호화(PHE), 등급 동형 암호화(LHE), 완전 동형 암호화(FHE) 등 세 가지 종류가 있습니다. 완전 동형 암호화(FHE). 부분 동형 암호화는 특정 연산 작업(예: 합산, 선형 함수, 이선 함수)만 동형 암호화할 수 있는 반면, 등급 동형 암호화와 완전 동형 암호화는 임의의 연산 작업도 지원할 수 있습니다.

LHE의 경우, 시스템에서 사용/생성하는 매개변수는 수행하려는 함수 계산에 따라 ? ()에 따라 달라지며, 해당 함수의 계산 복잡성이 증가함에 따라 커지고, 결과적으로 암호문과 키의 크기가 증가하여 더 많은 저장 및 통신 리소스를 소비하게 됩니다. 반면에 FHE 방식은 주어진 매개변수 집합(즉, 주어진 키와 암호문 크기)에 대해 이진 논리 게이트 회로로 표현할 수 있는 모든 함수를 계산할 수 있습니다. 즉, LHE와 달리 FHE 체계에 포함된 매개변수(키와 암호문)는 계산해야 할 작업이 점점 더 복잡해지더라도 더 커지지 않습니다.

그 결과, 동형 계산의 메모리 사용량과 런타임이 원본 일반 텍스트/작업에 비례한다는 것을 보장하는 유일한 모델이 바로 FHE입니다. 하지만 FHE에는 계산이 계속될수록 암호 텍스트에 점점 더 많은 노이즈(쓰레기 데이터)가 포함된다는 기술적 문제가 있습니다. 너무 많은 노이즈가 잘못된 복호화 결과를 초래하는 것을 방지하기 위해 FHE 체계는 주기적으로 부트스트래핑이라는 비용이 많이 드는 작업을 수행하여 노이즈를 관리 가능한 수준으로 줄입니다. 앞으로 이에 대해 더 자세히 설명할 예정이니 기대해 주세요!

원본 링크: https://cryptographycaffe.sandboxaq.com/posts/fhe-01/