Plausible Deniability in Fully Homomorphic Computation

기술 요약: 완전 동형 연산에서의 그럴듯한 부인 (PD-FHC)

1. 문제 정의

신뢰할 수 없는 클라우드 제공자에게 연산을 외주로 맡기는 것은 사용자들을 기존 기술들이 동시에 해결하지 못하는 두 가지 뚜렷한 위협에 노출시킨다:

1. 연산 프라이버시 (Computational Privacy): 정직하지만 호기심 많은(honest-but-curious) 제공자로부터 데이터를 보호함 (FHE 및 TEE에 의해 해결됨).
2. 그럴듯한 부인 (Plausible Deniability): 강력한 적대자가 강요할 때, 연산의 존재 또는 의도를 신빙성 있게 부인할 수 있는 능력.

현재의 솔루션들은 다음과 같은 결정적인 결함을 가지고 있다:

• FHE (완전 동 홈 암호): 데이터 값은 숨기지만, 암호문(ciphertext)의 전송은 눈에 띈다. 강압적인 적대자는 복호화 키를 요구할 수 있으며, FHE를 사용하는 것 자체가 사적인 연산이 수행되고 있음을 확인해 준다.
• TEE (신뢰 실행 환경): 실행에 대한 부정할 수 없는 증거로서 어테스테이션 로그(attestation logs)를 생성한다. 또한, 사이드 채널 누출에 취약하다.
• MPC (다자간 보안 연산): 단일 참여자의 쉐어(share)를 드러내는 것에는 강건하지만, 참여자들이 연산이 일어났다는 사실 자체를 부인하거나 다른 연산으로 대체하는 것을 허용하지 않는다.
• 부인 가능한 암호화/저장 (Deniable Encryption/Storage): 정적인 데이터(메시지나 파일)는 다루지만, 동적인 연산 의도까지는 확장되지 않는다.

본 논문은 사용자가 불리언(Boolean) 연산을 외주로 맡기면서도, 무엇을 연산했는지에 대한 의도를 부인하고, 외부 관찰자에게는 연산이 발생했다는 사실 자체를 부인할 수 있는 간극을 식별한다.

2. 방법론

저자들은 PD-FHC를 제안하며, 이는 **프레드킨 게이트(Fredkin gates)**와 최하위 비트(LSB) 스테가노그래피를 사용하여 불리언 연산을 커버 매체(특히 RGB 이미지) 내에 삽입하는 방식이다.

핵심 메커니즘:

• 공유된 배선, 가변적 의미론 (Shared Wiring, Variable Semantics): 이 프레임워크는 범용 프레드킨 게이트의 단일하고 고정된 배선을 활용한다. 프레드킨 게이트는 제어 비트가 두 데이터 비트를 교환할지 여부를 결정하는 가역적인 3-입력/3-출력 게이트이다.
  • 제어 비트가 0이면, 게이트는 통과(pass-through) 역할을 한다.
  • 제어 비트가 1이면, 게이트는 두 데이터 비트를 교환(swap)한다.
  • 제어 비트를 임베딩된 데이터로 설정함으로써, 동일한 물리적 배선이 서로 다른 위치에서 서로 다른 논리 함수(예: AND, OR, NOT 또는 복잡한 회로)를 구현할 수 있다.
• 다중 위치 임베딩 (Multi-Location Embedding): 사용자는 하나의 "실제" 회로와 $L-1$개의 "기만용(decoy)" 회로를 이미지의 LSB에 임베딩한다.
  • 실제 회로 (Real Circuit): 비밀 위치 집합 $\Lambda_{j^*}$에 임베딩된다.
  • 기만 회로 (Decoy Circuits): 다른 서로소인 위치 집합 $\Lambda_j$에 임베딩된다.
  • 채우기 비트 (Fill Bits): 나머지 모든 LSB 위치는 특정 분포 $\pi$에서 추출된 비트로 채워진다.
• 균등한 처리 (Uniform Processing): 클라우드 제공자(Carol)는 이미지를 받고 배선 명세($C_{obf}$)를 받는다. 그녀는 모든 픽셀 위치에 병렬적으로 프레드킨 게이트를 균등하게 적용한다. 그녀는 어떤 위치에 실제 데이터, 기만 데이터, 또는 채우기 노이즈가 있는지 알 수 없다.
• 강요에 대한 대응 (Coercion Response): 강요를 받을 경우, 사용자는 위치 집합, 입력, 그리고 출력을 기만용 회로에 대해 공개한다. 배선이 동일하고 기만 회로가 클라우드의 출력과 일치하는 검증 가능한 결과를 생성하기 때문에, 적대자는 기만 회로를 실제 연산과 구별할 수 없다.

이론적 기초:

• 부인 가능한 연산 매체 (Deniable Computation Medium, DCM): 주소 지정 가능한 비트 위치, 읽기/쓰기 기능, 그리고 균등하게 적용되는 게이트 패밀리를 가진 매체를 정의하는 추상적 프레임워크.
• 일치 마진 조건 (Matched-Marginal Condition): 정보 이론적 보안을 위해, 실제 위치, 기만 위치, 채우기 위치의 비트는 동일한 위치별 확률 법칙 $\pi$에서 추출되어야 한다. 이 조건 하에서 LSB 평면은 "교환 가능(exchangeable)"하며, 즉 이미지의 통계적 분포는 위치의 치환에 대해 불변이다.

3. 주요 기여

1. 추상적 프레임워크: 특정 커버 매체(예: 이미지, 오디오, 패킷)와 보안 모델을 분리하는 부인 가능한 연산 매체(DCM) 및 **부인 가능한 연산 스킴(DCS)**의 정의.
2. 위협 모델 정식화: 다음 두 단계를 구분하는 모델:
   • 정직하지만 호기심 많은(HBC) 클라우드: 연산 프라이버시(데이터 은닉)에 관심이 있음.
   • 강압적 적대자 (Coercive Adversary): 그럴듯한 부인(존재 및 의도 은닉)에 관심이 있음.
     저자들은 "존재 구별"(숨겨진 회로의 존재를 적대자가 증명할 수 있는가?)과 "회로 발견"(적대자가 공개된 기만 회로들 사이에서 실제 회로를 식별할 수 있는가?)을 측정하는 새로운 **다회차 강요 게임(multi-round coercion games)**을 정의한다.
3. 이미지 기반 구현: RGB 이미지와 프레드킨 게이트를 사용한 구체적인 구현.
   • 위치 프라이버시 증명: 일치 마진 조건 하에서, 클라우드 제공자는 무작위 추측과 비교하여 실제 회로 위치를 찾는 데 있어 **제로(zero)**의 이득(정보 이론적 관점)을 얻음을 증명한다.
   • 부분적 회로 은닉: 배선은 보이지만, 게이트의 의미론은 숨겨져 있다. 본 논문은 제어 비트에 대한 지식 없이는 배선이 어떤 함수가 계산되고 있는지에 대해 아무것도 드러내지 않음을 증명한다.
4. 구현 및 벤치마킹: 회로 크기(5302개 게이트)와 이미지 차원($128^2$$512^2$)에 걸쳐 벤치마킹된 Python 구현.

4. 결과

• 보안 보장:
  • 연산 프라이버시: 게이트 패밀리가 비-비밀 위치의 통계적 분포를 보존하는 한(프레드킨 게이트가 비트 치환을 통해 이를 만족함), 클라우드는 비밀 데이터 값이나 특정 계산 함수에 대해 아무것도 알 수 없다.
  • 존재 은닉: 일치 마진 조건 하에서, 존재 이득은 정확히 **영(zero)**이다. 적대자는 채우기 비트만 포함된 이미지와 숨겨진 회로를 포함한 이미지를 구별할 수 없다.
  • 회로 발견: 공개되지 않은 기만 회로들 사이에서 실제 회로를 식별하는 이득은 **의미론적 타당성(semantic plausibility)**과 사이드 채널 누출에 의해 제한된다. 위치 및 배선 벡터는 적대자의 이득에 기여하지 않는다.
• 성능: 구현은 불리언 회로에 대해 선도적인 FHE 라이브러리인 TFHE와 경쟁력 있는 성능을 보이면서도, FHE가 제공할 수 없는 부인 가능성을 제공한다.
• 시각적 비가시성: LSB의 수정은 채널당 최대 $\pm 1$의 변화만을 유발하여 PSNR > 50 dB를 달로, 변화는 시각적으로 인지할 수 없다.

5. 의의 및 주장

본 논문은 연산 프라이버시, 존재 은칭(외부 관찰자 대상), 그리고 부분적 회로 은닉(클라우드 제공자 대상)을 동시에 만족하는 최초의 프레임워크라고 주장한다.

완곡한 주장 및 한계점:

• 커버 타당성의 범위: 저자들은 PD-FHC가 임의의 이미지(예: 휴가 사진)에서는 작동하지 않는다고 명시한다. 커버 서비스는 높은 엔트로피의 LSB 입력(예: 디더링, 노이즈 주입 또는 암호 영역 처리)을 정당하게 기대할 수 있어야 한다. 만약 선언된 서비스가 자연 이미지를 기대한다면, 보안을 위한 균등한 LSB 평면은 탐지될 수 있다.
• 실제 입력 제약: 정보 이론적 제로 이득 보장은 사용자의 실제 입력 비트가 기만 및 채우기 비트와 동일한 분포 $\pi$를 따를 때만 정확하게 성립한다. 구조화된 실제 입력을 사용하는 경우, 이득은 실제 입력 분포와 $\pi$ 사이의 통계적 거리($\Delta$)에 의해 제한된다.
• 의미론적 타당성: 기만 회로에 대한 발견 방지는 기만 회로의 $\epsilon$-타당성에 의존한다. 저자들은 (예: 밝기 체크 vs. 암호 해시) 의미론적으로 믿을만한 기만 회로를 구축하는 것이 아직 자동화되지 않은 수동적이고 도메인 특화된 작업임을 인정한다.
• 능동적 공격: 프레임워크는 정직하지만 호기심 많은 클라우드와 수동적 외부 관찰자를 가정한다. 이미지를 수정하거나 연산을 거부하는 능동적 공격자로부터는 보호하지 않는다.
• 암호학적 난독화 없음: 본 논문은 (불가능성 결과의 대상이 되는) 암호학적 회로 난독화를 주장하는 것을 명시적으로 피한다. 여기서의 "난독화"는 순수하게 스테가노그래피적이며, 제어 비트를 숨김으로써 게이트의 의미론을 변화시키는 것에 의존한다.

요약하자면, PD-FHC는 사용자가 강요 상황에서 검증 가능한 대안 함수를 제시함으로써 특정 연산 의도를 신빙성 있게 부인할 수 있는, 커버 매체의 통계적 조건이 충족되는 새로운 방식의 연산 외주 접근법을 제공한다.