동형 암호화란 무엇인가요?

동형 암호화(HE)를 사용하면 암호화된 데이터에서 직접 계산을 수행할 수 있습니다. 그 결과로 암호화된 결과가 생성되며, 이를 복호화하면 평문에서 같은 연산을 수행한 결과와 같아집니다. "복호화하지 않고 암호문에서 계산합니다."

측면에 특수 장갑이 달린 잠긴 상자 안에 숫자를 넣는다고 상상해 보십시오. 상자를 전혀 열지 않고도 장갑을 통해 숫자를 조작할 수 있습니다(더하기, 곱하기). 열쇠 소유자만 상자의 잠금을 풀었을 때 결과를 볼 수 있습니다.

부분 동형 암호화는 한 종류의 연산을 제한 없이 지원합니다. RSA(교과서 버전)는 곱셈 동형입니다. Enc(m1)*Enc(m2) = Enc(m1*m2)입니다. Paillier는 덧셈 동형입니다. Enc(m1)*Enc(m2) = Enc(m1+m2)입니다. 전자 투표와 비공개 정보 검색에 사용됩니다.

준동형 암호화는 덧셈과 곱셈을 모두 지원하지만, 제한된 횟수의 곱셈(회로 깊이)에만 사용할 수 있습니다. 곱셈을 수행할 때마다 잡음이 커지고, 임계값을 넘으면 복호화에 실패합니다. Gentry가 2009년에 처음 구성했습니다.

완전 동형 암호화는 암호화된 데이터에서 임의의 계산(모든 불리언/산술 회로)을 지원합니다. Gentry는 2009년에 "부트스트래핑"을 통해 FHE가 가능하다는 것을 보였습니다. 즉, 복호화 회로를 동형 방식으로 평가해 암호문을 새로 고치고 잡음을 초기화하는 방식입니다.

대부분의 HE 체계는 격자 기반입니다(BGV, BFV, CKKS). 암호화하면 암호문에 잡음이 추가됩니다. 덧셈을 수행하면 잡음은 덧셈적으로 증가합니다. 곱셈을 수행하면 잡음은 곱셈적으로 증가합니다. 부트스트래핑은 암호문을 동형적으로 복호화하여 잡음을 초기 수준으로 재설정합니다. 부트스트래핑은 비용이 많이 듭니다.

FHE는 여전히 평문 계산보다 10^6배 느립니다. 32비트 정수 하나를 암호화하려면 암호문 몇 KB가 필요합니다. 부트스트래핑에는 게이트 하나당 수 초가 걸립니다. 실용적인 FHE는 머신러닝 추론, 데이터베이스 질의, 유전체 분석과 같은 특정 작업을 대상으로 합니다.

대부분의 HE 체계는 Learning With Errors (LWE) 또는 Ring-LWE (RLWE) 난제에 기반하며, 이 난제는 양자 컴퓨터에도 안전하다고 여겨집니다. HE를 깨려면 RLWE를 풀어야 하지만, 이를 상대로 상당한 속도 향상을 제공하는 알려진 양자 알고리즘은 없습니다.

SEAL(Microsoft, BFV/CKKS 지원), HEAAN(서울대학교, CKKS), OpenFHE(오픈 소스, BGV/BFV/CKKS/FHEW/TFHE), HElib(IBM, BGV)이 있습니다. 모두 연구 수준의 라이브러리이며, 실제 서비스 환경에 배포되는 경우는 드물고 특정 분야에 한정됩니다.

의료 유전체학: 유전체를 공개하지 않고 유전자 데이터베이스를 질의합니다. 암호화된 머신러닝 추론: 클라우드가 데이터를 보지 않고 데이터에 신경망을 실행합니다. 비공개 분석: 암호화된 사용자 데이터에 대해 통계량을 집계합니다. 기밀 포트폴리오를 대상으로 금융 위험을 계산합니다.

HE: 한 당사자가 다른 당사자가 암호화한 데이터에 대해 계산합니다. MPC: 여러 당사자가 서로의 입력을 공개하지 않고 공동으로 계산합니다. 하이브리드 방식: 오프라인 전처리에는 HE를 사용하고, 상호작용 프로토콜에는 MPC를 사용합니다. 절충점은 다음과 같습니다. HE는 지연 시간이 높고, MPC는 통신 오버헤드가 큽니다.

Somewhat Homomorphic Encryption (SHE)의 핵심적인 한계는 무엇입니까?

Homomorphic Encryption을 사용하면 암호문에 대해 계산할 수 있습니다. PHE는 하나의 연산을 지원하고, SHE는 제한된 깊이를 지원하며, FHE는 부트스트래핑을 통해 임의의 회로를 지원합니다. 이 기술은 LWE/RLWE 난제에 기반합니다. 다음 주제: LWE의 수학적 기반입니다.