“ 왜곡 된 회로 ” 란 정확히 무엇입니까?

회로 는 계산을 나타내는 방법 일뿐입니다. 회로에 대해 특별히 암호화 된 것은 없습니다. 이는 AND, OR, NOT과 같이 비트 에 대한 연산만으로 구성된 직선 계산 (루핑 또는 흐름 제어 구조 없음)을 의미합니다.

A 왜곡 된 회로 는 계산의 출력 만 표시하지만 입력 또는 중간 값에 대해서는 표시하지 않는 “계산을 암호화”하는 방법입니다. . 왜곡 된 회로는 회로로 표현 한 계산을 수행 한 다음 회로의 각 작업 (AND, OR, NOT)에 대해 일부 암호화 작업을 수행하여 작동하기 때문에 “회로”라는 용어를 사용합니다. .

좀 더 정확하고 싶다면 “garbling scheme”은 다음과 같이 구성됩니다.

• (Garble) (일반)을 변환하는 방법 회로 $ C $를 왜곡 된 회로 $ \ widehat C $로 변환합니다.

• (인코딩) 모든 (일반) 입력 $ x $를 변환하는 방법 회로에 대한 불량 입력 $ \ widehat x $. $ x $를 $ \ widehat x $로 인코딩하기 위해 회로를 왜곡하는 데 사용 된 비밀 무작위성이 필요합니다.

• (평가) 왜곡을 취하는 방법 회로 $ \ widehat C $ 및 불량 은 $ \ widehat x $를 입력하고 회로 출력 $ C (x) $를 계산합니다. 누구나 할 수 있습니다. $ C (x) $를 평가하고 배우기 위해 $ x $ 또는 $ \ widehat C $ 내부의 비밀 무작위성을 알 필요는 없습니다.

여기서 약간 단순화합니다. 그러나 보안의 주요 아이디어는 $ \ widehat C $와 $ \ widehat x $가 함께 $ C (x) $보다 더 많은 정보를 유출하지 않는다는 것입니다. 특히, 그들은 $ x $에 대해 아무것도 드러내지 않지만 $ C (x) $ 계산이 (분명히) 수행되도록 허용합니다. 이것이 제가 “계산 암호화”를 의미하는 것입니다.

왜곡 된 회로의 주요 응용 프로그램은 안전한 2 자 계산입니다. Alice가 개인 입력 $ x $를 가지고 있고 Bob이 개인 입력 $ y $를 가지고 있다고 상상해보십시오. 그들은 $ f $ 함수에 동의하고 둘 다 $ f (x, y) $를 배우고 싶다는 데 동의하지만 상대방이 $ f (x, y)보다 더 많은 것을 배우기를 원하지 않습니다. ) $.이를 달성하기 위해 다음을 수행 할 수 있습니다 (이것이 Yao의 고전적 프로토콜입니다).

1. 당사자들은 $ f $를 (일반)로 표현하는 방법에 동의합니다. ) 회로. Alice는 $ f \ mapsto \ widehat f $ 회로를 왜곡합니다. 그녀는 $ \ widehat f $와 자신의 “잘못된 입력”$ \ widehat x $를 Bob에게 보냅니다.

2. Alice는 $ f $에 대한 입력을 다음으로 인코딩하는 방법을 알고 있습니다. “왜곡 된”입력이지만 Bob만이 개인 입력 $ y $를 알고 있습니다. 그래서 당사자들은 Alice가 $ y $가 무엇인지 배우지 않고 Bob이 잘못된 버전 $ \ widehat y $를 집어 들도록 준비합니다. 이것은 oblivious transfer라는 원시적 인 것으로 할 수 있습니다.

3. 이제 Bob은 잘못된 회로 $ \ widehat f $와 잘못된 입력 $ \ widehat x, \ widehat y $를가집니다. 그 회로를 위해. 그런 다음 평가 절차를 실행하고 $ f (x, y) $를 배울 수 있습니다. 그는 $ f (x, y) $를 Alice에게 공개 할 수 있습니다.

프로토콜이 다음에서 $ f (x, y) $ 이상을 공개하지 않는다고 주장 할 수 있습니다. 방법 :

• Alice는이 프로토콜에서 최종 답변 $ f (x, y) $ 외에는 아무것도 보지 못합니다. (분명한 전송의 보안은 단계에서 아무것도 배우지 못하도록합니다. 2).

• 밥이 $ \ widehat f $, $ \ widehat x $ 및 $ \ widehat y $를 보더라도 왜곡 된 회로의 보안은 이러한 값이 t $ f (x, y) $ 이외의 것을 드러내십시오.

이 접근 방식은 Alice & Bob이 반 정직 할 때 효과적입니다. (즉, 지시에 따라 프로토콜을 따릅니다). 그러나 Alice가 악의적 일 때 그녀는 그들이 동의 한 $ f $ 대신 $ f “$ 다른 함수를 왜곡 할 수 있습니다.따라서 악의적 인 공격자에 대한 보안을 원할 때 이러한 일이 발생하지 않도록 프로토콜에 다른 사항을 추가해야합니다.

참조 자료 :

• The Yao Construction and its Proof Of Security (video), Yehuda Lindell
• A Proof of Yao s Protocol 안전한 2 자 컴퓨팅 , Yehuda Lindell & Benny Pinkas
• 왜곡 된 회로의 기초 , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• A Brief History of Practical Garbled Circuit Optimizations , a video of my video . 처음 몇 개의 슬라이드는 왜곡 된 회로의 “고전적인”구성을 다룹니다.

댓글

• Bob은 어떻게 y 앨리스가가 블링 방식을 생각해 낼 때 선택한 비밀 무작위성을 알지 못합니까?
• 왜곡 된 인코딩은 비트 단위로 작동합니다. Bob을 가져 가십시오. 의 첫 번째 비트. Alice는 스스로 생각할 수 있습니다. " Bob이 입력 비트 0을 가지고 있다면 그의 잘못된 인코딩은 $ G_0 $이어야합니다. 그가 입력 비트 1을 가지고 있다면 그의 잘못된 인코딩은 $ G_1 $이어야합니다. " 명백한 전송 은 Alice가 두 개의 문자열 $ G_0, G_1 $를 제공하는 프리미티브입니다. 입력으로. Bob은 $ b $를 입력으로 제공하고 $ G_b $를 배웁니다 (하지만 다른 $ G_ {1-b} $는 아님). Alice는 ' $ b $를 배우지 않습니다. 당사자는 Bob ' 입력의 각 비트에 대해 모호한 전송을 수행 할 수 있습니다. 무명 전송이 실제로 작동하는 방법 은 또 다른 질문입니다.)
• Yao 옆에 ' 회로가 깨질 수 있습니다. ' 재사용하지 마십시오. " 왜곡 된 회로가 실행되거나 입력 비트 0 및 1에 대해 키가 고정 될 때마다 다른 키를 할당 할 수 있다는 내 혼란을 해결할 수 있습니까 "