▲

동형암호화된 CRDTs

 (jakelazaroff.com)
11P by GN⁺ 1일전 | ★ favorite | 댓글 1개
  • 로컬-퍼스트 소프트웨어에서 협업 문서의 보안을 유지하기 위해 동형암호화(Homomorphic Encryption)와 CRDTs를 결합
  • 종단 간 암호화만으로는 서버가 데이터를 병합할 수 없어 동기화와 업데이트 효율에 제약이 발생함
  • 동형암호화는 서버가 내용을 알지 못한 채로 CRDT 업데이트를 병합할 수 있도록 프로그램 실행을 가능하게 하는 기술
  • 하지만 동형암호화의 근본적 한계(성능 저하, 공간·연산량 증가, 코드의 최악 케이스 동작 필요) 로 인해 실제 적용에는 중대한 난점이 존재함
  • CRDTs와 보안 연산의 공존을 위한 다양한 접근이 연구되고 있으며, 아직 완전한 해결책은 모색 중임

로컬-퍼스트와 보안 협업의 과제

  • 원격 협업에서 문서를 로컬-퍼스트 방식으로 CRDT에 저장한 뒤, 동기화를 통해 공동 편집 경험을 제공하는 구조임
  • 문서 내용이 앱 개발자 등 제3자에게도 절대 노출돼서는 안 되는 보안 요구가 있을 경우, 종단 간 암호화가 흔히 활용되는 방법임
  • 종단 간 암호화는 동작이 단순하지만, 동기화 서버가 데이터를 병합하지 못하므로, 오랜 기간 비동기로 작업하면 비효율적 데이터 통신이 발생함

동형암호화란?

  • 동형암호화는 암호화된 데이터상에서 직접 알고리듬 실행이 가능하게 하는 특수 암호화 방식임
  • 이를 활용하면 동기화 서버가 데이터의 내용을 알지 못한 채로 CRDT 업데이트 병합을 수행할 수 있음
  • 동형암호화에서 지원하는 연산 종류에 따라 부분 동형(덧셈/곱셈 중 하나만) , 일부 동형/계층 동형(양쪽 일부 횟수) , 완전 동형(제한 없음) 으로 구분함
  • 연산이 많아질수록 암호문에 노이즈가 쌓이고 해독이 곤란해져 Bootstrapping 등 고급 기법이 요구됨
  • 암호화된 비트(0/1) 수준에서 XOR, AND 같은 기본 연산 게이트 조합만으로 일반적 불리언 회로 구현 가능임

실제 동형암호화 CRDT 구현 사례

  • Rust 기반 라이브러리 TFHE-rs로 Last Write Wins Register라는 대표적인 CRDT를 동형암호화로 구현함
  • 평문 구조체와 암호화 구조체의 필드와 메서드(암호화/복호화)는 거의 동일하나, 실제 병합 로직에서 중요한 차이가 발생함
  • if/else, match 구문 등 실행 경로 분기가 암호문 해독에 힌트를 줄 수 있으므로, 암호화 환경에서는 모든 분기·루프를 즉시 평가하는 방식이 필수임
  • 주요 조건 비교, 병합 연산 모두 비트 단위 FheBool 연산자와 select 메서드 등으로 처리해 어떤 조건에서 값이 바뀌었는지 외부에 감지 불가함

동형암호화의 근본적 한계

  • 암호키와 데이터 크기 불균형: 예시에서는 32바이트의 데이터에 123MB 서버 키 필요(압축해도 27MB)로 공간 비효율이 심각함
  • 성능 저하: 동형암호화된 CRDT merge는 미암호화 대비 약 20억 배 느린 1초 수준 측정
  • 루프·분기가 입력값에 따라 변하면 정보 노출이 발생하므로, 항상 최악의 케이스 기준으로 연산수·메모리를 소모해야 함
  • 예를 들어, last-write-wins map과 같이 key-value가 희소한 경우라도, 모든 키를 고정 크기로 꽉 채운 채 병합해야 하므로 실질적 확장성 저하
  • 암호문 구조나 변경 내역에서 값이 변화했는지, 어느 부분이 갱신됐는지 외부 관찰자가 추론 불가하게 설계해야 함

결론 및 전망

  • CRDTs와 동형암호화는 이론적으로는 자연스럽게 결합될 수 있지만, 현실적으로 공간/시간 효율성 및 프로그램 구조상 치명적 제약이 큼
  • 현 시점에서는 완전한 실용 솔루션이 나오지 않았으나, CRDTs 자체도 비교적 젊은 기술로 지속적 연구가 이루어지는 중임
  • 로컬-퍼스트 협업앱에서 보안성과 사용성의 균형을 위한 혁신적 솔루션에 대한 가능성은 여전히 남아 있음
▲
GN⁺ 1일전  [-]
Hacker News 의견

  • 완전 동형 암호화 분야가 정말 느리고 비효율적인 것은 사실이지만, 이 분야 자체가 2009년에 등장한 비교적 신생 영역임을 언급하고 싶음, 지난 15년 동안 이 분야의 발전은 정말 대단한 수준임, 최초 동형 암호화 스킴은 수 TB/PB에 달하는 키가 필요했고, 부트스트래핑(동형 암호화에서 곱셈 연산이 많아졌을 때 필수적인 연산)은 수천 시간이 걸렸음, 이제는 키가 30MB 수준이고, 부트스트래핑이 0.1초 내에 가능해짐, 앞으로도 계속 발전해서 실용적으로 쓰일 날이 오길 기대함

    • 초기 CRDT(CRDT: Conflict-free Replicated Data Type)들도 WOOT처럼 매우 비실용적이었는데, 요즘 최신 CRDT 데이터베이스는 일반적인 LSM에 비해 퍼포먼스가 그리 떨어지지 않는 수준임, 예를 들면 RDX CRDT들은 머지 소트와 유사한 알고리즘으로 동작해서 모두 O(N)임, 대다수 구현에서 메타데이터 오버헤드도 잘 제어함, WOOT, librdx, go-rdx 참고

    • CRDT의 아키텍처 특성상 느릴 수밖에 없고, 최고의 알고리즘조차 구조적으로 비용이 큼, 여기에 동형 암호화를 더하면 도전 난이도가 훨씬 높아짐, 정말 인상적이긴 한데 실제로 쓸만한지 궁금함, 주장에 대한 근거로 "서버가 새 맵을 계산하려면 모든 키를 하나씩 머지하고, 그 후 전체 맵을 각 피어에 전송해야 함—서버 입장에서는 전체 맵이 매번 다르기 때문"이라는 설명을 인용함

  • CRDT는 Conflict-free Replicated Data Type의 약자로, 충돌 없이 분산 동기화를 할 수 있는 특수한 데이터 타입임, CRDT 위키백과 링크 참고

    • 예를 들어 문서를 여러 명이 동시에 편집해야 하는 앱들이 자주 CRDT를 사용함

  • 기사에서 성능이 부족하다고 언급한 부분이 있는데, 실제로 M4 MacBook Pro에서 last write wins 레지스터를 평범하게 돌릴 경우 머지에 0.52 나노초가 걸리지만, 동형 암호화 버전은 1.06초가 소요됨, 즉 연산 속도가 20억 배 차이남, 정말 충격적인 수치임

  • FHE(Full Homomorphic Encryption)는 정말 느리지만 2009년 이후 놀라운 발전이 있었음, 부트스트래핑 속도만 해도 수천만 배는 빨라짐, tfhe-rs를 이용하여 이미 동형 암호 기반 AES-128도 시연함, AI 추론/학습을 위한 실시간 FHE 도입 가능성이 점점 높아진다는 생각임, tfhe-aes-128 깃허브 링크 참고

  • 서버가 클라이언트의 변경 사항을 더이상 이해할 수 없다는 내용에 동의할 수 없음, 서버는 사용자가 아직 보지 못한 변경분만 보내주고, 사용자는 그걸 복호화·머지하여 문서의 최신 버전을 만드는 방식임, 동형 암호화가 흥미롭긴 하지만, 합리적인 성능이나 대역폭이 필요한 상황에서는 거의 적합하지 않음, 예전에 (커스텀 CPU+RAM을 암호로 인코딩한 뒤 각 클럭 신호마다 한 명령씩 처리하는) 동형 암호 기반 완전 비밀 컴퓨팅을 논문에서 본 적 있음, 실제로 동작하지만 1초에 가상 CPU 명령 1개 처리 가능한 수준임, 이런 속도와 비용이 괜찮을 정도라면 차라리 로컬에서 돌리거나, 정말 부자라면 직접 하드웨어 사서 로컬로 처리하는 편이 현명함

    • 컴퓨터과학 및 암호학 논문들은 종종 실용성과는 먼, 예를 들어 공격 복잡도를 2^250에서 2^230으로 줄이는 식의 황당하게 비현실적인 연구 내용이 많은 편임, 이런 연구는 실제 R&D나 가능한 영역을 넓히는 데 의미가 있음

    • 서버가 내용을 직접 다룰 수 없다면 CRDT 문서를 병합하지 못하고, 매번 CRDT의 전체 상태를 받았다가 전송해야 함, 친구가 동시에 온라인이라면 연산 결과(operations)를 보내서 실시간 머지가 가능한데, 그렇지 않으면 매우 비효율적임

  • 학생들이 FHE로 암호화된 WASM이나 JS 채점 코드를 JupyterLite, ottergrader 조합으로 자신의 크롬북에서 직접 돌려도 신뢰할 수 있을지 의문임, 코드서명과 SETI@home screensaver와의 관계도 궁금함

  • THFE-rs는 Zama 측이 프로토타입 용도 이외에는 상업적 라이선스를 요구하므로 쓰지 않는 게 좋겠음, 라이선스 조건이 불편함, 그 대신 openFHE(C++), lattigo(golang) 라이브러리를 추천하며, 둘 다 상업적으로 자유롭게 쓸 수 있음

  • FHE는 여기서 쓰기에 본질적으로 맞지 않는 도구라고 생각함, FHE는 중앙 서버가 소유하거나 아는 데이터를 다루는 데 적합함, 여기서는 여러 사용자가 분산된 데이터를 함께 처리해야 하므로 MPC(멀티파티 연산: 여러 참가자가 각자 비밀 데이터를 합산 등으로 공동 연산하는 방식)가 훨씬 효율적임

    • 나 역시 FHE를 쓰고 싶다가 결국 더 좋은 도구나 최적의 방식이 있다는 걸 자주 깨달음, FHE 적용할 수 있는 상황 자체가 꽤 한정적임

  • 기사에서 제시한 가정이 이해가 잘 안 됨, CRDT와 동형 암호 개념은 알지만, 왜 동기화하려면 양쪽이 모두 동시에 온라인이어야 하는지 의문임, 비동기적으로 업데이트를 주고받는 ‘store-and-forward’ 방식이면 비행 중 데이터도 암호화된 채 전송 가능한데, 왜 굳이 서버가 상태를 유지해야 하고(그것도 암호화된 상태로), 제안된 것처럼 수정해야 하는지 궁금함

    • 서버가 각 피어마다 레지스터 사본을 따로 저장해야 하는 문제 때문이라고 생각함, 서버가 가장 최신 상태를 판별하지 못하니까임, FHE를 쓰면 서버가 하나의 사본만 유지할 수 있음, 즉 모든 피어가 항상 온라인이면(동시에 접속하면) 서버는 그냥 전달만 하고 따로 저장할 필요가 없음

  • FHE의 느림과 비효율성에 CRDT의 저장 공간 낭비가 어우러진 모습이 재미있어 보임

답변달기