식사 암호자 문제

암호학에서 다이닝 암호학자 문제는 부울-XOR 함수의 안전한 다당제 계산을 수행하는 방법을 연구한다.데이비드 차움(David Chaum)은 1980년대 초반에 이 문제를 처음 제안했고 무조건적인 발신자와 수신자의 추적불가능성으로 익명의 메시지를 보낼 수 있다는 것을 보여주기 위해 이를 사례로 활용했다.이 문제에 기반한 익명 통신 네트워크는 흔히 DC-net(여기서 DC는 "디닝 암호학자"^[1]를 의미한다)이라고 한다.

식사라는 단어에도 불구하고, 식사 암호문제는 식사 철학자들의 문제와 관련이 없다.

설명

세 명의 암호학자가 저녁 식사를 위해 테이블 주위에 모인다.웨이터는 그들에게 식사가 암호인이나 국가안보국(NSA)의 한 사람일 수도 있는 누군가에 의해 지불되었다고 알려준다.암호학자들은 익명의 지불을 할 수 있는 서로의 권리를 존중하지만 NSA가 지불했는지 여부를 알고 싶어한다.그래서 그들은 2단계 프로토콜을 실행하기로 결정했다.

첫 번째 단계에서, 두 명의 암호학자가 한 명씩의 암호학자가 한 명씩 차례로 결과를 볼 수 있도록 메뉴 뒤에 동전을 던짐으로써, 모든 두 명의 암호학자가 하나의 비트 비밀을 공유한다.예를 들어, 동전 던지기 후에 암호학자 A와 B가 비밀 비트 $1$을 공유하고$,$ A와 $C$는 $비밀{\displaystyle \mathrm{}}$ $비트$ $1$을 $공유$하고$,$ A와 C는 0을 공유하고$,$ B와 $C$는 $1$을 공유한다고 가정합시다$.$

두 번째 단계에서 각 암호학자는 다음과 같이 약간씩 공개적으로 발표한다.

• 만약 그들이 식사비를 지불하지 않았다면, 그들이 두 이웃과 공유하는 두 비트 중 독점적인 OR (XOR)은
• 만약 그들이 식사에 대한 대가를 지불했다면, 그 XOR와는 정반대였죠.

Supposing none of the cryptographers paid, then A announces ${\displaystyle 1\oplus 0=1}$, B announces ${\displaystyle 1\oplus 1=0}$, and C announces ${\displaystyle 0\oplus 1=1}$. On the other hand, if A paid, she announces ${\displaystyle \lnot (1\oplus 0)=0}$.

세 가지 공고를 종합하면 그들의 질문에 대한 답을 알 수 있다.하나는 단순히 발표된 3비트의 XOR를 계산한다.만약 결과가 0이라면, 그것은 암호학자 중 아무도 돈을 지불하지 않았다는 것을 암시한다(그러므로 NSA가 그 비용을 지불한 것이 틀림없었다).그렇지 않으면 암호인 중 한 명이 돈을 냈지만 다른 암호인들에게는 그들의 정체를 알 수 없다.

David Chaum은 이 프로토콜을 위해 다이닝 암호 네트워크, 즉 DC-net이라는 용어를 만들었다.

제한 사항

DC-net 프로토콜은 간단하고 우아하다.그러나 후속 연구(아래 참조)에서 살펴본 몇 가지 해결책은 다음과 같다(아래 참조 섹션을 참조하십시오.

충돌

만약 두 명의 암호학자가 저녁식사 비용을 지불했다면, 그들의 메시지는 서로를 취소하고 최종 XOR 결과는 $[\displaystyle 0$이를 충돌이라고 하며, 이 프로토콜을 사용하여 한 번에 한 명의 참가자만 전송할 수 있다.보다 일반적인 경우, 짝수 수의 참가자들이 메시지를 보내는 한 충돌이 발생한다.

중단

그룹이 성공적으로 통신하는 것을 원하지 않는 악성 암호학자는 XOR의 정확한 결과 대신 무작위 비트를 보내는 것만으로 최종 XOR 결과가 무용지물이 되도록 프로토콜을 방해할 수 있다.이 문제는 원래 프로토콜이 공개키 기술을 전혀 사용하지 않고 설계되었기 때문에 발생하며, 참가자들이 프로토콜을 정직하게 따르는지 여부를 확인할 수 있는 신뢰할 수 있는 메커니즘이 없기 때문이다.^[2]

복잡성

프로토콜은 참가자들 간에 쌍방향으로 공유된 비밀키를 요구하는데, 참가자가 많을 경우 문제가 될 수 있다.또한, DC-net 프로토콜은 "조건 없이 안전하다"지만, 실제로는 참가자의 쌍들 사이에 "조건 없이 안전한" 채널이 이미 존재한다는 가정에 따라 달라지는데, 이는 실제로 달성하기가 쉽지 않다.

관련 익명 거부권 네트워크 알고리즘은 DC-net에서처럼 논리 XOR가 아닌 여러 사용자의 입력에 대한 논리적 OR을 계산하는데, 이는 논리 OR 결합 연산이 자연스럽게 적합한 애플리케이션에 유용할 수 있다.

역사

David Chaum은 1980년대 초에 이 문제에 대해 처음 생각했다.기초적인 사상을 개괄적으로 설명한 첫 번째 출판물은 그의 것이다.^[3]저널 버전은 Cryptology 저널의 첫 번째 호에 실렸다.^[4]

일반화

DC-net은 쉽게 일반화되어, 3명 이상의 참가자와 2진수 0과 1이 아닌 임의의 "알파벳"의 전송을 허용한다. bit 이상의 전송을 허용한다.

더 긴 메시지의 전송

익명의 송신자가 DC-net 라운드당 2비트 이상의 정보를 전송할 수 있도록 하기 위해, 암호자 그룹은 원하는 수의 비트 전송 대역폭을 만들기 위해 원하는 횟수만큼 프로토콜을 반복할 수 있다.이러한 반복은 연속적으로 수행할 필요가 없다.실제 DC-net 시스템에서는 참가자들 쌍이 Diffie-를 사용하여 하나의 공유된 "마스터" 비밀에 대해 미리 동의하는 것이 일반적이다.예를 들어 헬먼 키 교환.그런 다음 각 참가자는 익명의 송신자가 여러 비트의 정보를 전송할 수 있도록 원하는 만큼 공유된 "코인 플립"을 생산하기 위해 이 공유 마스터 비밀을 유사 번호 생성기에 로컬로 공급한다.

더 큰 그룹 크기

프로토콜은 $n{\displaystyle }$ ${\displaystylen}$명의$$ 참가자 그룹으로 일반화할 수 있으며, 각 참가자는 서로 공통적으로 비밀키를 공유한다.프로토콜의 각 라운드에서, 참가자가 그룹에게 추적 불가능한 메시지를 전달하고 싶을 경우, 그들은 공개적으로 발표된 비트를 뒤집는다.참가자는 참가자를 나타내는 정점과 공유 비밀키를 나타내는 가장자리를 가진 완전히 연결된 그래프로 시각화할 수 있다.

스파스 비밀 공유 그래프

이 프로토콜은 참여자들이 서로 연결된 개별 구성요소로 비밀 공유 그래프를 분할할 수 있는 경우 익명성을 감소시킬 수 있는 잠재적 위험으로 실제 DC-net 구현의 성능과 확장성을 개선할 수 있는 완전하게 연결되지 않은 비밀 공유 그래프로 실행될 수 있다.예를 들어 링 위상(topology)을 사용하는 > 3 ${\displaystyle n>3}$ 참가자에게 직관적으로 호소하지만 덜 안전한 일반화를 통해 테이블 주위에 앉아 있는 각 암호학자는 다른 모든 암호학자와는 상관 없이 자신의 바로 옆 좌우에 있는 암호학자와만 비밀을 공유한다.그러한 토폴로지는 각 $암호학자$가$$n {\$displaystyn}$이 아닌 라운드당 2개의 동전 넘김을 조정해야 하기 때문에 매력적이다$.$그러나 실제로 아담과 찰리가 무고한 희생자인 밥의 바로 좌우에 앉아 있는 NSA 요원이라면, 그리고 아담과 찰리가 몰래 결탁하여 서로 비밀을 누설하려 한다면, t.그들은 총 참가자의 수에 관계없이, 밥이 DC 네트 런에서 1비트의 송신자인지 아닌지를 확실히 판단할 수 있다.참여자 아담과 찰리가 공모한 비밀 공유 그래프는 밥만 포함된 두 개의 분리된 구성 요소로 효과적으로 "분할"되기 때문인데, 하나는 다른 모든 정직한 참여자가 포함된 것이다.

확장성을 위해 반대론 시스템에서 채택된 또 다른 타협 비밀 공유 DC-net 토폴로지는 클라이언트/서버 또는 사용자/수탁자 토폴로지로 설명될 수 있다.^[5]이 변종에는 익명성을 원하는 잠재적으로 많은 수의 사용자와 사용자가 익명성을 얻도록 돕는 역할을 하는 훨씬 적은 $수의{\displaystyle }$ $수탁자 중$ 두 가지 유형의 참여자가 있다고 가정한다$.$이 토폴로지에서 $n{\displaystyle }$ ${\displaystyle$ n$} 사용자$는 $각각{\displaystyle }$ m ${\displaystyle m}$ 수탁자와 비밀을$$ 공유하지만 사용자는 다른 사용자와 직접 비밀을 공유하지 않으며, 수탁자는 다른 $수탁자$와 직접 비밀을 공유하지 않으므로 n ${\displaystyle \times }$ ${\displaystyle m}$ {\$displaystyle n\times m}$ 비밀$$ 공유 매트릭스에서 발생한다.수탁자 $m{\displaystyle }$ ${\displaystyle m}$이(가) 적으면 각 사용자는 몇 개의 공유 비밀만 관리하면 링 토폴로지와 같은 방식으로 사용자의 효율성이 향상된다.그러나 적어도 한 명의 수탁자가 정직하게 행동하고 자신의 비밀을 누설하거나 다른 참여자와 결탁하지 않는 한, 그 정직하지 않은 수탁자는 어느 사용자나 얼마나 많은 다른 사용자 및/또는 수탁자가 부정하게 공모할 수 있는지에 관계없이 모든 정직한 사용자를 완전히 연결된 단일 구성요소로 연결하는 "허브"를 형성한다.사용자는 어떤 수탁자가 정직한지 알거나 추측할 필요가 없다. 그들의 보안은 적어도 한 명의 정직하고 결탁하지 않은 수탁자의 존재에 달려 있다.

대체 알파벳 및 결합 연산자

단순한 DC-nets 프로토콜은 이진수를 전송 알파벳으로 사용하고 XOR 연산자를 사용하여 암호문을 결합하지만, 기본 프로토콜은 어떤 알파벳에도 일반화하며 일회용 패드 암호화에 적합한 연산자를 결합한다.이러한 유연성은 많은 참가자들 간에 공유되는 비밀이 사실상 단일 DC-net 라운드 내에서 대칭적으로 결합된 일회용 패드에 불과하다는 사실에서 자연스럽게 발생한다.

DC-nets 알파벳과 결합 연산자의 유용한 대안 중 하나는 공개키 암호화에 적합한 유한 그룹을 알파벳(예: Schnorr 그룹 또는 타원 곡선)으로 사용하고 관련 그룹 연산자를 DC-net 결합 연산자로 사용하는 것이다.그러한 알파벳과 연산자를 선택하면, 참가자가 DC-net이 제공하는 익명성을 훼손하지 않고 전송 채널을 "재밍"하지 않는 것과 같이, 고객이 생산하는 DC-net 암호문서에 대한 정확성 특성을 증명하기 위해 제로 지식 증명 기법을 사용할 수 있다.이 기법은 처음에는 골레와 쥴스에 의해 제안되었고,^[6][7] 프랑크에 의해 더욱 발전되었다가 나중에 암호학적으로 증명할 수 있는 반대론 시스템의 구현인 평결에서 실행되었다.^[8]

충돌 처리 또는 방지

당초 데이비드 차움이 충돌을 피하기 위해 제시한 대책은 충돌이 감지되면 메시지를 재전송하는 것이지만, 이 논문은 재전송을 어떻게 배열할 것인지 정확히 설명하지 않고 있다.

반대자는 검증 가능한 셔플을 사용하여 DC-net 전송 스케줄을 설정함으로써 의도하지 않은 충돌의 가능성을 피한다. 즉, 각 참가자는 스케줄의 어떤 비트가 자신의 전송 슬롯에 해당하는지 정확히 알 수 있지만, 다른 전송 슬롯을 소유한 사람은 알 수 없다.^[9]

중단 공격 대응

초식동물은 대규모 익명성 네트워크를 소규모 DC-net 그룹으로 나누어 참가자가 방해물이 없는 그룹을 찾을 때까지 방해받은 그룹을 탈퇴하고 다른 그룹에 가입함으로써 방해 시도를 피할 수 있다.^[10]이러한 회피 접근방식은 많은 노드를 보유한 적이 완전히 타협하지 않은 그룹만을 선택적으로 교란시킬 수 있는 위험을 도입하여 참가자가 완전히 타협되었기 때문에 정확하게 기능할 수 있는 그룹을 "소거"할 수 있다.^[11]

반대자들은 혼란에 대처하기 위해 몇 가지 계획을 시행한다.원본 프로토콜은^[9] 검증 가능한 암호 셔플을 사용하여 DC-net 전송 스케줄을 형성하고 "전송 할당"을 배포하여 단순한 암호 해시 검사로 후속 DC-net 암호문의 정확성을 확인할 수 있었다.그러나 이 기법은 모든 DC 네트 라운드에 앞서 새롭게 검증할 수 있는 것을 요구했고, 높은 지연으로 이어졌다.나중에 보다 효율적인 계획을 세우면 교란 없이 일련의 DC-net 라운드가 진행되지만, 교란 사건에 대한 대응은 교란 피해자가 가해자의 신원을 노출하고 증명할 수 있는 익명의 고발 내용을 배포하기 위해 교란 행위를 사용한다.^[5]마지막으로, 보다 최신 버전은 DC-net에서 공개키 암호화의 사용으로 인해 계산 효율성에 상당한 비용을 들여 완전하게 검증 가능한 DC-nets를 지원하며, 일반 사례에서 효율적인 XOR 기반 DC-net을 사용하고 중단 시에만 검증 가능한 DC-nets를 사용하는 하이브리드 모드를 지원하여, 타당성보다 더 신속하게 고발 내용을 배포한다.검증할 ^[8]수 있는 분쇄기를 사용하여 표백하다

참조