가블드 회로 (Garbled Circuit)
한 줄 정의: 함수를 논리 회로로 바꾼 뒤 각 게이트를 암호화해, 두 참여자가 서로의 입력을 드러내지 않고 결과만 계산하게 하는 기법입니다.
쉽게 풀면
두 사람이 각자의 비밀 값을 보여 주지 않고 "누가 더 부자인가" 같은 결과만 알고 싶다고 해 봅시다. 가블드 회로에서는 한쪽이 계산할 함수를 AND·XOR 같은 게이트로 이루어진 회로로 만들고, 각 게이트의 입출력을 무작위 암호 라벨로 바꿔 상대에게 건넵니다. 상대는 이 암호화된 회로를 차례로 풀어 최종 결과만 얻게 됩니다.
왜 중요한가
안전 다자간 계산을 실제로 구현하는 대표 방법이어서, 프라이버시 보존 머신러닝이나 개인정보를 공유하지 않는 공동 분석 연구에서 자주 쓰입니다. 계산·통신량을 줄이는 최적화 기법이 꾸준히 발표되는 분야이기도 합니다.
논문에서는 이렇게 쓰입니다
"제안 프로토콜은 [[garbled-circuit|가블드 회로]]에 Free-XOR 최적화를 적용하여 통신량을 줄였다."
효율 개선을 성과로 보고하는 암호 프로토콜 논문의 문장입니다.
조금 더 깊게 보면
가블드 회로는 1980년대 앤드루 야오(Andrew Yao)의 2자 안전 계산 연구에서 비롯되었습니다. 회로를 만드는 쪽(garbler)은 각 선마다 0과 1에 해당하는 무작위 라벨을 정하고 게이트별 암호화된 진리표를 보냅니다. 평가하는 쪽(evaluator)은 자기 입력에 해당하는 라벨을 망각 전송으로 받아, 상대가 어떤 값을 줬는지 모르게 합니다. 기본 형태는 준정직(semi-honest) 공격자 모델에서 안전하며, 악의적 공격자까지 막으려면 cut-and-choose 같은 추가 기법이 필요합니다.
주의할 점
안전 다자간 계산이 달성하려는 목표 전체를 가리킨다면, 가블드 회로는 그 목표를 이루는 구체적 구성 기법 중 하나입니다. 비밀 분산 기반 방식이나 동형암호 기반 방식과는 구조와 비용 특성이 다르므로 서로 바꿔 쓰지 마세요.