텍스트

프라이버시 비교는 두 당사자의 특정 값을 밝히지 않고 두 당사자 간의 크기 관계를 얻는 것을 말합니다. 백만장자 문제는 처음에 Yao Zhizhi에서 비롯되었습니다: 두 명의 백만장자가 누가 더 부자인지 비교하고 싶지만 그들이 얼마나 많은 돈을 가지고 있는지 공개하고 싶지 않은데, 신뢰할 수 있는 제3자가 없이 어떻게 비교할 수 있습니까? 이 질문은 1980년대 중국 최초이자 유일한 튜링상 수상자인 Yao Qizhi에 의해 제기되었으며, 그는 중국 최초의 컴퓨터 과학 및 교육 분야의 인물이자 현대 암호학의 새로운 문을 열었습니다.

앞선 글 "우아한 구직활동-프라이버시 비교 알고리즘 예제"에서는 구직 사례를 통해 프라이버시 비교의 적용 시나리오와 구현 방법을 소개하였으며, 본 글에서는 현재 상대적으로 효율성이 높은 프라이버시 비교 프로토콜을 주로 소개한다.

이 프로토콜은 [1] CrypTFlow2: Practical 2-Party SecureInference에서 제안한 하위 프로토콜이며, 이 프로토콜을 기반으로 DRelu 활성화 기능을 신경망에 적용합니다.

--관련기술--

이 프로토콜은 주로 부울 비밀 공유 및 무의식 전송의 두 가지 기술을 사용하여 구성됩니다.

▲ 우발적 전송

Oblivious Transfer(OT, Oblivious Transfer)는 데이터를 보낸 사람이 n개의 데이터를 가지고 있고, 데이터를 받는 사람은 그 중 하나의 데이터를 받고, 데이터를 받는 사람은 다른 데이터를 얻을 수 없으며, 데이터를 보낸 사람은 받는 사람이 받은 데이터의 내용을 알지 못한다는 것을 의미합니다. 수신을 선택합니다. 어느 쪽입니까? 구현 체계는 이전 기사 "안전한 다중 당사자 컴퓨팅(MPC) 기반 개인 정보 보호 컴퓨팅 기술(1)"에서 소개되었으므로 이 기사에서는 반복하지 않습니다.

▲ 부울 비밀 공유

안전한 다자 컴퓨팅에서 비밀 공유는 데이터를 분할하고 공유하는 데 사용되며 각 당사자는 각 데이터의 해당 조각을 가져오고 원본 데이터에 대한 계산 논리는 조각 계산으로 변환됩니다. 전체 계산 논리가 완료되면 조각의 계산 결과를 집계하고 복원하여 원본 데이터의 계산 결과를 얻습니다.

부울 비밀 공유는 부울 값 b를 두 조각 b0 및 b1로 분할하고 두 조각을 함께 가져와 원래 데이터 b를 복원하는 것을 말합니다.

조각 생성: 임의로 부울 값 b0을 생성하고 b와 XOR을 수행하여 b1=b0⊕b를 계산합니다.

 b=b0⊕b1

샤드 복원: 두 개의 샤드에서 XOR 작업 실행

      a=a0⊕a1，b=b0⊕b1

      a⊕b=(a0⊕b0)⊕(a1⊕b1)

XOR 연산: 부울 비밀 공유는 XOR 연산의 동형 속성을 만족하며 로컬에서 조각에 대해 XOR 연산을 수행한 다음 복원하는 것은 원본 데이터에 대한 XOR 연산과 동일합니다.

AND 연산: 부울 비밀 공유는 AND 연산의 준동형 속성을 충족하지 않으며 안전한 AND 연산을 달성하기 위해 암묵적 전송 기술을 사용합니다.

Alice는 조각 a0과 b0을, Bob은 조각 a1과 b1을, AND 연산을 통해 Alice는 c0을, Bob은 c1을 얻습니다. 보장;

*Alice는 obvious transmission의 발신자로서 boolean 값 r을 c0으로 무작위로 생성하고 아래와 같이 obvious transmission의 입력을 생성합니다.

*Bob은 부주의한 전송의 수신자로서 데이터 r⊕((a0⊕a1)∧(b0⊕b1))을 c1로 얻기 위해 자신의 프래그먼트 a1과 b1을 부주의한 전송에 대한 옵션으로 a1||b1에 연결합니다.

c0⊕c1= r⊕r⊕((a0⊕a1)∧(b0⊕b1))=(a0⊕a1)∧(b0⊕b1);

AND 연산의 모든 가능성을 나열하는 것이 본질이며, 임의의 항목을 추가한 후 상대방은 자신의 데이터에 따라 혼란스러운 계산 결과를 선택합니다.

--구현 아이디어--

▲ 평문 비교

우선, 비교 작업의 프라이버시에 관계없이 정상적인 상황에서 두 숫자를 어떻게 비교합니까?

a=123，b=5879，a=>[0,1,2,3]，b=>[5,8,7,9]

*두 숫자를 같은 길이의 디지털 배열로 정렬하고 길이가 충분하지 않으면 앞에 0을 추가합니다.

*두 배열의 숫자를 순차적으로 비교하여 해당 자리의 숫자가 같으면 한 자리가 같지 않을 때까지 다음 자리를 계속 비교함 가장 앞의 같지 않은 자리의 비교 결과가 두 데이터의 비교 결과임 If 모든 숫자가 같으면 두 숫자가 같습니다. 전체 프로세스는 다음 공식으로 요약할 수 있습니다.

X와 Y는 모두 길이가 n인 데이터, 1{X

X=x0||x1||x2||...||x(n-1), Y=y0||y1||y2||...||y(n-1), xi, yi는 다음을 의미합니다. 분할 후 i 번째 데이터

1{X

1{X1

     ...

1{X(n-1)

Xi=xi||...||x(n-1), Yi=yi||...||y(n-1), 첫 번째 i-1 비트를 제거한 후의 데이터를 나타내는 데 사용됨

▲ 안전하지 않은 프라이버시 비교

위의 비교식을 비공개 비교로 변환하고 싶다면 가장 쉬운 방법은 이전 글 "우아한 취업준비-프라이버시 비교 알고리즘"에서 소개한 가장 작은 비교 단위 두 개를 비공개로 하는 것이라고 생각하면 된다. 예: 두 개의 가장 작은 비교 단위의 비교는 망각 전송 프로토콜을 통해 수행할 수 있습니다. 이것은 실제로 단일 최소 비교 단위의 보안을 보장하지만 경우에 따라 일부 데이터 상황이 노출됩니다.

a=1230 b=1231, 이 두 숫자의 비교를 위해 b가 ot의 수신자, 즉 가장 작은 비교 단위의 데이터 비교 결과 획득자이고 위의 방식에 따라 비교가 수행되면, 두 가지 추가 정보가 유출됩니다.

1) 처음 몇 자리가 같은 경우: b는 a의 처음 세 자리가 123임을 알게 됩니다.

2) 두 개의 가장 작은 단위의 데이터는 가장 작은 단위 범위의 양쪽 끝에 있는 데이터입니다. b는 a의 마지막 숫자가 0임을 알 것입니다.

▲ 불안감 해소

텍스트

본 논문의 프라이버시 비교 프로토콜에서 전체 비교 아이디어는 위의 비보안 프라이버시 비교와 일치하지만, 이 프로토콜은 비밀 공유 기술을 도입하고 있으며, 부주의한 전송을 통해 비교 결과를 얻었을 때 보낸 사람은 각 데이터에 대해 이전 것을 혼동합니다. 무작위 항목, 어느 쪽도 최소 비교 단위 데이터의 비교 결과를 얻지 못하지만 비교 결과의 조각을 얻고 조각을 사용하여 일반 텍스트 비교 프로세스에 따라 재귀적으로 비교합니다.모든 최소 비교 단위는 비교, 비교 결과 조각을 복원하여 전체 데이터에 대한 비교 결과를 얻습니다.

가장 작은 단위의 비교 결과는 모두 조각이므로 비교가 완료될 때까지 재귀 계산 결과가 복원되지 않으므로 가장 작은 비교 단위의 비교 결과를 얻음으로써 발생하는 정보 유출을 방지할 수 있습니다.

--계약 프로세스--

앨리스는 데이터 x, 밥은 데이터 y, 데이터의 이진 길이는 l, 최소 비교 단위의 이진 길이는 m, 최소 비교 단위의 나눗셈은 q=l/m, 십진법 최대값 최소 비교 단위는 M= 2^m-1

1) 두 당사자는 데이터를 개별적으로 나눕니다: x=x0||...||x(q-1), y=y0||...||y(q-1)

2) 모든 가장 작은 비교 단위에 대해 xi(0<=i_0，*Alice는 무의미한 전송의 발신자로서 데이터를 준비합니다: 무작위 부울 생성

sij=_0 ⊕ 1{xi

      tij=_0 ⊕ 1{xi=j}

_0, xi가 각각 yi보다 작거나 같은지 여부의 부울 공유 조각으로서 0<=j<=M에 대해 두 개의 의도하지 않은 전송 인스턴스의 입력은 각각 다음과 같이 설정됩니다.

*Bob은 yi를 입력으로 사용하여 각각 의도하지 않은 전송의 두 인스턴스를 실행하고 두 비교 결과의 조각을 얻습니다.1

1과_0，예를 들어 m이 2일 때 Alice의 첫 번째 최소 비교 단위 x0=2, Bob의 첫 번째 최소 비교 단위 y0=1일 때 Alice는 무작위로 생성합니다.

_0, 다음과 같이 2개의 무의미한 입력을 생성합니다.

_1=0⊕_0，_1=0⊕_0

Bob은 y0을 무시 전송에 대한 옵션으로 사용하여 다음을 얻습니다.

3) 모든 최소 비교 단위의 비교가 완료된 후 양 당사자는 해당 최소 비교 단위가 서로 작거나 같은지 여부에 대한 Boolean 공유 조각을 얻은 다음 일반 텍스트 비교 프로세스에 따라 조각 재귀를 사용하여 계산합니다. 최종 비교 결과의 조각.

프래그먼트의 XOR 연산의 경우 로컬에서 프래그먼트의 XOR을 수행하기만 하면 됩니다. 프래그먼트의 AND 연산을 위해서는 위에서 소개한 방식에 따라 계산된 결과의 프래그먼트를 실수로 전송해야 합니다.

재귀 프로세스에는 주로 AND 연산을 수행해야 하는 두 곳이 있습니다.

1{x0||x1 = y0||y1 } ∧ 1{x2 < y2 }

모든 이전 비교 단위가 동일하고 다음 비교 단위를 비교해야 하는 경우:

1{x0||x1 = y0||y1} = 1{x0 = y0 } ∧ 1{x1 = y1 }

이전의 모든 비교 단위가 같은지 여부를 계산할 때:

--요약하다--

단일 요소 비교의 경우 재귀 계산이 필요하고 전후 종속성이 있기 때문에 OT 확장을 통해 작업의 OT 인스턴스를 최적화할 수 없습니다. 배치 요소의 비교를 위해 동일한 위치와 작업을 가진 OT 인스턴스에 대해 수직 방향으로 OT 확장을 통해 효율성을 최적화할 수 있습니다.

저자 소개

저자 소개

텍스트

참조

참조