이 기사는이 기사는앰비 연구소 (ID: SECBIT)
, 저자 Guo Yu는 Odaily에서 승인을 받아 복제했습니다.
https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md
이 글은 Github에 업데이트 되었습니다.
"도전은 때때로 당신에 대한 주님의 신뢰의 표시입니다." 도전은 때때로 당신에 대한 하나님의 신뢰의 표시입니다. ― D. 토드 크리스토퍼슨
시리즈 3: "지식" 검색
상호작용과 도전
이전에 소개한 영지식 증명 시스템은 모두 "상호작용적"이므로 검증자 Bob은 "지도 삼색 문제"("시리즈 2" 참조)와 같이 상호작용 중에 도전할 하나 이상의 "무작위 숫자"를 제공해야 합니다. ) , 검증자 Bob은 Bob이 만족할 때까지 Alice의 답변에 도전할 면을 "지속적으로" 무작위로 선택해야 하며 Alice의 부정 행위 확률은 "기하급수적으로" 감소합니다. 그리고 Bob이 증명을 믿을 수 있는 "근거"는 Bob이 선택한 난수가 충분히 임의적인지 여부에 달려 있습니다. Alice가 Bob의 난수를 미리 예측할 수 있다면 재난이 발생하고 현실 세계는 "이상적인 세계"로 퇴보하고 Alice는 즉시 "시뮬레이터"로 업그레이드하여 초능력을 통해 Bob을 속일 수 있습니다.
"시리즈 3"에서 우리는 Schnorr 프로토콜을 분석했습니다. 프로토콜에서 검증자 Bob은 Alice에게 도전하고 그녀에게 값 z를 계산하도록 요청하기 위해 임의의 숫자 c를 선택하기만 하면 되지만, Bob은 Alice가 예측할 수 있는 능력을 갖도록 해서는 안 됩니다. c의 값 어떤 지식이든, 그렇지 않으면 앨리스도 시뮬레이터로 변신할 것입니다.
난수의 중요성은 자명합니다.
난수 챌린지는 대화형 영지식 증명을 위한 "신뢰의 근원"입니다.
그러나 "상호작용 프로세스"는 애플리케이션 시나리오를 제한합니다. 대화형 영지식 증명이 "비대화형"으로 바뀔 수 있다면 어떨까요? 아주 아주 신나는 일이 될 것입니다. 소위 비대화형은 "일회성" 증명 프로세스로 간주될 수 있습니다. 즉, Alice는 검증을 위해 Bob에게 직접 증명을 보냅니다.
비대화형 영지식 증명, 영어는 비대화형 영지식, 줄여서 NIZK입니다. 전체 증명이 "문자열"로 인코딩되어 종이에 작성되어 이메일 및 채팅 도구와 같은 다양한 방법을 통해 임의의 검증자에게 보낼 수 있음을 의미합니다. 문자열은 모든 사람을 위해 Github에 배치될 수도 있습니다. 언제든지 다운로드하려면 확인하십시오.
블록체인 세계에서 "NIZK"는 합의 프로토콜의 일부로 사용될 수 있습니다. 트랜잭션을 확인하려면 여러 광부가 필요하기 때문입니다. 트랜잭션 발신자와 각 광부가 상호 작용하고 광부가 도전하도록 해야 한다면 합의 프로세스가 매우 느려질 것이라고 상상해 보십시오. 비대화형 영지식 증명은 모든 채굴자 노드에 직접 전파되어 스스로 검증할 수 있습니다.
어떤 친구들은 이렇게 물을 수 있습니다: 광부가 한 명만 도전해도 충분하지 않나요? 광부와 거래 발신자 간의 상호 작용 스크립트를 증명으로 인코딩한 다음 다른 광부에게 브로드캐스트하면 다른 광부가 직접 챌린지 프로세스가 신뢰할 수 있다고 믿게 될 것입니다. 가능하지 않습니까? 그러나 최초의 대화식 채굴기는 신뢰할 수 있는 제3자로서 신뢰를 받아야 하는 것이 분명한데, 제3자? 좋은 생각은 아닌듯...
대화형 영지식 증명이 아니라 아래에서 "NIZK"라고 직접 말할 것입니다. 이는 이상적이며 차이를 만드는 제3자는 없습니다.
"비대화형"으로 인한 혼란
비대화형 영지식 증명(NIZK)이 존재한다면 대화형 증명보다 훨씬 강력합니다.
대화형 증명은 한 검증자만 신뢰할 수 있는 반면 NIZK는 여러 검증자, 심지어 모든 사람이 신뢰할 수 있습니다.
대화형 증명은 상호작용하는 순간에만 유효하지만 NIZK는 항상 유효합니다.
NIZK는 공간뿐만 아니라 시간도 확장할 수 있습니다.
아름답지 않나요? 하지만,……
이전 섹션의 결론을 반복합니다.
난수 챌린지는 대화형 영지식 증명을 위한 "신뢰의 근원"입니다.
그러나 NIZK가 챌린지 프로세스에서 패하면 결과는 어떻게 됩니까?
우리는 이미 "영지식" 증명을 상기했습니다.("시리즈 2" 참조) 증명 프로세스는 이상적인 세계에서 검증자(Bob)와 검증자 Bob과도 상호 작용하는 시뮬레이터(알고리즘)를 구성해야 합니다. 상대방이 진짜 앨리스인지 시뮬레이터인지 구별하는 능력이 없다.
이제 NIZK의 비대화형을 고려한다면, "나"가 "진정한" 증거 X가 적힌 종이를 "당신"에게 보여주고 "당신"이 이 논문을 읽은 후 나를 정말로 믿는다면; 프로토콜이 "영지식"인 경우 "I"가 시뮬레이터로 대체되면 시뮬레이터는 거짓 증거 Y를 "위조"할 수 있으며 이는 "당신"을 설득할 수도 있습니다.
좋아, 여기에 문제가 온다:
참과 거짓인 X와 Y를 어떻게 구별합니까? 물론 프로토콜이 영지식이기 때문에 차이를 구분할 수 없습니다. 차이를 구분할 수 없어야 합니다.
같은 방식으로 Y를 보여줄 수 있습니다. "나"가 당신을 속일 수 있다는 의미가 아닙니까?
불협화음인가? 여기서 2분만 생각해주세요.
(2분 후...)
NIZK에는 상호 작용이 없기 때문에 도전 프로세스가 없습니다. 모든 증명 프로세스에는 Alice가 계산하고 작성해야 합니다. 이론적으로 Alice는 원하는 대로 작성할 수 있으며 아무도 그녀를 막을 수 없습니다. 예를 들어 Alice는 "이상적인 세계"를 거짓으로 작성했습니다. Y의 증명
아마도 시뮬레이터에 대해 깊이 이해하고 있는 친구들은 여기에서 핵심 포인트를 발견할 것입니다. 시뮬레이터는 "이상적인 세계"에서만 Y를 구성해야 합니다. 즉, Y와 같은 악한 것은 "이상적인 세계"에만 존재할 수 있습니다. 도달할 수 없습니다. "현실 세계"는 세계의 재앙입니다.
계속 생각해...
더 깊은 문제도 있다."지도 삼색 문제"를 떠올려보라. 시뮬레이터가 "현실 세계"에서 악을 행할 수 없는 핵심 이유는 이상 세계에서 "되감기 시간"의 초능력을 가지고 있기 때문이다. 그리고 "현실 세계"에는 그런 흑 마법이 없습니다. 현실 세계의 "비존재"가 핵심입니다.
더욱이 NIZK에는 상호 작용이 없으므로 심각한 결과를 초래합니다.시뮬레이터는 "되감기 시간"이라는 초능력을 사용할 방법이 없으며 물론 두 세계에서 증명자의 행동을 구별할 수 없는 것 같습니다.
즉, 우리가 어떤 NIZK 시스템에 직면하면 "시뮬레이터"는 땅 위에 서기가 어렵고 세상에 떨어져 평범한 필사자가 될 수 밖에 없을 것 같습니다. 이 추론에 따라 시뮬레이터에 더 이상 초능력이 없다고 가정하면 Alice와 시뮬레이터가 다르지 않고 Alice도 시뮬레이터가 될 수 있으며 계속 추론하면 Alice는 " 현실 세계" 밥이 그 과정에서 임의로 속았다면 이 증명 시스템은 "신뢰성"을 잃기 때문에 더 이상 가치가 없습니다. 결론: 모든 NIZK는 신뢰할 수 없습니다.
여기에 뭔가 문제가 있는 것이 분명합니다...
위의 분석 과정에서 우리는 대화식 도전의 부족을 언급했습니다. 실제로 Bob이 Alice의 증명 생성 프로세스에 참여하지 않으면 증명에 포함된 모든 비트는 Alice가 제공하며 "증명" 자체에는 Bob이 신뢰할 수 있는 "루트"가 없는 것 같습니다. 이것은 "직관적으로" 말이 안되는 것 같습니다.
그것은 Bob의 참여 없이는 "신뢰의 루트"를 설정할 "완전히" 방법이 없다는 것을 의미합니까? 신뢰의 기초는 또 어디에서 올 수 있습니까?
대답은 "제3자"입니다!
잠깐만요... 프로토콜 상호 작용에는 두 당사자만 있는 것 아닙니까? Alice와 Bob, 제3자는 어디에 있습니까?
특별한 방법으로 서드파티를 도입해야 하고 여러 가지 방법이 있는데 먼저 첫 번째 방법부터 알아보도록 하겠습니다.
(눈물: 말 잘하지 않았어, 우리가 제3자를 소개하지 않았나?)
Schnorr 프로토콜 검토
우리의 오랜 친구인 Schnorr 프로토콜을 살펴보겠습니다. 이 프로토콜은 3단계 프로토콜입니다. 첫 번째 단계에서 Alice는 약속을 보내고 두 번째 단계에서는 Bob이 난수 챌린지를 보내고 세 번째 단계에서는 Alice가 도전에 응답합니다.
3단계 Schnorr 프로토콜을 1단계로 전환하는 방법을 살펴보겠습니다.
c = Hash(PK, R)
Schnorr 프로토콜의 두 번째 단계를 보십시오. Bob은 임의의 도전 번호 c를 제공해야 합니다. 여기에서 Alice가 다음 공식을 사용하여 도전 번호를 계산하도록 할 수 있으므로 프로토콜의 두 번째 단계를 제거하는 목적을 달성할 수 있습니다.
여기서 R은 Alice가 Bob에게 보낸 타원 곡선 점이고 PK는 공개 키입니다. 해시 알고리즘을 사용하여 c를 계산하는 이 공식을 잘 살펴볼 수 있습니다. 이 공식은 두 가지 용도로 사용됩니다.
Alice가 커밋 R을 생성하기 전에 c를 예측할 방법이 없습니다. 비록 c가 변장한 Alice에 의해 최종적으로 선택되더라도
c Hash 함수에 의해 계산되며, 정수 필드에 고르게 분포되며 난수로 사용될 수 있습니다.
참고: Alice는 R을 생성하기 전에 c를 예측할 수 없습니다. 그렇지 않으면 Alice는 변장한 "역 시간"의 초강력을 가지므로 임의로 Bob을 속일 수 있습니다.
그리고 암호학적으로 안전한 해시 함수는 SHA256, SHA3, blake2 등과 같이 "단방향"입니다. 이와 같이 앨리스가 c를 계산하더라도 앨리스는 c를 선택하여 속일 수 있는 능력이 없습니다. Alice가 R을 생성하자마자 c는 고정되는 것과 같습니다. 우리는 필멸의 앨리스가 "실제 세계"에서 해시를 역으로 계산할 수 있는 능력이 없다고 가정합니다.
위의 그림을 보면 Hash 함수를 사용하여 3단계 Schnorr 프로토콜을 한 단계로 결합합니다. Alice는 (R, c, z)를 직접 보낼 수 있습니다. 그리고 Bob이 PK를 가지고 있기 때문에 Bob은 스스로 c를 계산할 수 있으므로 Alice는 (R, z)만 보낼 수 있습니다.
우리는 위의 체계를 약간 변형하여 "디지털 서명" 체계를 얻었습니다. 소위 디지털 서명은 "나"가 "해가 산 끝에 있고, 황하가 바다로 흐른다"와 같이 "당신"에게 문자열을 제시하는 것을 의미하며, 이 시가 제가 선물을 받았는데 서명을 해야 합니다. 이것은 내 정체성이 이 시와 연결되어 있음을 증명할 수 있습니다.
NIZK 관점의 디지털 서명
느슨하게 말하면 디지털 서명 체계는 (1) 내가 개인 키를 가지고 있고 (2) 개인 키와 메시지가 계산과 연관되어 있음을 증명하는 것과 같습니다.
나는 먼저 내 신원을 증명해야 하므로 간단하다. 이것이 Schnorr 프로토콜의 기능으로, 상대방에게 "나는 개인 키를 가지고 있다"는 진술을 증명할 수 있다. 그리고 이 증명 프로세스는 영지식입니다. "개인 키"에 대한 지식이 공개되지 않습니다.
m = "그렇다면 이 당나라 시와 어떤 관련이 있을까요? c를 계산하는 프로세스를 수정합니다."
c = Hash(m, R)
태양은 산 끝에 있고 황하가 바다로 흐릅니다.
여기서는 공격자가 서명을 마음대로 위조할 수 없도록 하기 위해 DLP(Discrete Logarithm Problem)와 해시 함수가 2차 프리이미지 저항(Secondary Preimage Resistance)을 만족하는 것으로 가정한다.
참고: 엄밀히 말하면 디지털 서명의 위조 불가능성을 보장하기 위해 Schnorr 프로토콜이 "시뮬레이션 건전성"이라는 더 강력한 속성을 충족함을 증명해야 합니다. 이에 대해서는 [2]를 참조하십시오.
위의 그림은 잘 알려진 디지털 서명 방식인 Schnorr 서명 방식이다[1]. 여기에 또 다른 최적화가 있습니다.R은 c, z를 통해 계산할 수 있기 때문에 Alice가 Bob에게 보내는 것은 (R, z)가 아니라 (c, z)입니다.
참고: 이것이 "최적화"인 이유는 무엇입니까? 현재 타원곡선 공격에는 Shanks 알고리즘, Lambda 알고리즘, Pollard의 rho 알고리즘이 있는데 알고리즘 복잡도는 [3] 정도이고, n은 유한체의 자릿수라는 점을 기억해두시기 바랍니다. 2^256에 매우 가까운 유한 필드를 사용한다고 가정합니다. 즉, z는 256비트이고 타원 곡선 그룹의 크기는 거의 256비트에 가깝기 때문에 2^256의 제곱근은 2^입니다. 128이므로 256비트 타원곡선 그룹의 보안은 128비트에 불과합니다. 그러면 챌린지 번호 c는 128비트만 있으면 충분합니다. 이런 식으로 앨리스가 R을 보내는 것보다 c를 보내는 것이 더 공간을 절약하고 후자는 적어도 256비트가 필요합니다. c와 z의 두 값을 더하면 총 384비트가 됩니다. 널리 사용되는 ECDSA 서명 체계와 비교하여 소중한 공간을 1/4로 절약할 수 있습니다. 이제 비트코인 개발 팀은 ECDSA 서명 체계를 Schnorr와 유사한 서명 체계인 muSig[4]로 변경할 준비가 되었습니다. 이는 다중 서명 및 집계를 보다 유연하게 지원할 수 있습니다.
해시함수를 이용하여 대화형 증명 시스템을 비대화형 방식으로 바꾸는 방법을 Fiat-Shamir 변환[5]이라고 하는데, 1986년 암호학의 베테랑인 Amos Fiat와 Adi Shamir가 제안하였다.
신뢰 회복 - 무작위 예언 마법사
앞서 언급했듯이 도전 없이는 증명의 "신뢰 기반"이 손실된 것 같습니다. Schnorr 서명 체계에서 Hash 함수는 "도전자"의 역할을 수행합니다. 이 역할은 "Random Oracle"(Random Oracle)[6]이라는 매우 학술적인 이름을 가지고 있습니다.
그런데 여기서 해시를 사용하는 이유는 무엇입니까? 사실 Alice가 공개 난수를 생성하고자 할 때 그녀는 "랜덤 오라클"이라는 것이 필요합니다.
브레인스토밍 시간입니다!
우리는 "현실 세계"에서 하늘에 "엘프"가 있다고 상상합니다. 그는 2열 형태를 들고 있고 왼쪽 열은 문자열이고 오른쪽 열은 숫자입니다. Alice와 Bob을 포함하여 여러분과 저를 포함하여 누구나 "elf"에게 문자열을 보낼 수 있습니다.
elf는 문자열을 얻은 후 테이블의 왼쪽 열을 확인하여 테이블에 해당 문자열이 있는지 확인합니다.다음과 같은 두 가지 상황이 있습니다.
상황 1: 왼쪽 열에서 문자열을 찾을 수 없는 경우 엘프는 "진정한 난수"를 생성한 다음 문자열과 난수를 테이블에 쓴 다음 난수를 땅에 있는 필사자에게 반환합니다.
사례 2: 왼쪽 열에 이 문자열 레코드가 있으면 엘프는 오른쪽 열의 숫자를 그라운드로 직접 반환합니다.
이 스프라이트는 난수 생성기처럼 작동하지만 매우 다릅니다 차이점은 동일한 문자열을 보낼 때 동일한 숫자를 반환한다는 것입니다. 이 엘프는 전설적인 "랜덤 오라클"입니다.
Schnorr 프로토콜을 병합하는 과정에서 실제로 필요한 것은 Hash 함수가 아니라 이러한 임의의 오라클 마법사입니다. 둘의 차이점은 무엇입니까? 차이점은 다음과 같습니다.
랜덤 오라클은 새 문자열에 대해 매번 일관된 분포로 "참" 난수를 반환합니다.
Hash 함수로 계산한 결과는 분포가 일관적인 진정한 난수가 아닙니다.
그렇다면 Hash 함수가 더 일찍 사용된 이유는 무엇입니까? 실제 세계에는 진정한 임의의 오라클이 존재하지 않기 때문입니다! 왜? 사실, 해시 함수는 "결정적" 알고리즘이고 매개변수를 제외하고 다른 임의의 양이 도입되지 않기 때문에 해시 함수가 진정한 난수를 생성하는 것은 불가능합니다.
그리고 암호화 보안 강도가 "보이는" 해시 함수는 "의사" 랜덤 오라클 역할을 할 수 있습니다. 그런 다음 결합된 보안 프로토콜은 다음과 같은 추가적인 강력한 보안 가정을 추가해야 합니다.
가설: 암호학적으로 안전한 해시 함수는 전설적인 "랜덤 오라클"에 근접할 수 있습니다.
이 가정은 증명할 수 없기 때문에 이 가정을 신뢰하거나 공리로 사용할 수만 있습니다. 여담으로 해시 함수의 일반화된 충돌 방지 속성은 그 출력이 난수를 시뮬레이션할 수 있음을 결정합니다.동시에 많은 경우(전부는 아님) 해시 함수를 공격하기가 매우 어렵기 때문에 많은 암호 작성자가 과감하게 사용합니다.
이러한 가정을 사용하지 않는 보안 모델을 "표준 모델"이라고 하며, 이러한 가정을 사용하는 보안 모델을 "비표준 모델"이라고 할 수는 없습니다. "랜덤 오라클 모델"이라는 좋은 용어가 있습니다.
세상에는 단팥을 좋아하는 사람과 좋아하지 않는 사람, 두 부류의 사람이 있습니다. 유사하게, 세상에는 랜덤 오라클 모델을 좋아하는 사람과 랜덤 오라클 모델을 좋아하지 않는 사람의 두 가지 유형의 암호 작성자가 있습니다[6].
구조적 기초 - 납치된 엘프
Schnorr 프로토콜은 Fiat-Shamir 변환을 거친 후 NIZK 속성을 갖습니다. 이것은 우리가 증명한 SHVZK와는 다릅니다.SHVZK는 검증자가 정직할 것을 요구하는 반면, NIZK는 더 이상 검증자가 상호 작용에 참여하지 않기 때문에 검증자에 대한 비현실적인 요구 사항이 없으며 소위 정직성을 요구하는 문제가 있습니다. 검증자는 더 이상 존재하지 않습니다.
참고: 검증자 Bob이 부정직하면 어떻게 됩니까? 그런 다음 Bob이 Alice의 지식을 추출하는 것이 가능합니다. 그러나 3단계 Schnorr 프로토콜의 경우 "영지식"을 충족하는지 여부는 아직 알 수 없습니다. 우리는 시리즈 3: SHVZK에서 상대적으로 약한 속성을 만족한다는 것을 증명했을 뿐입니다.
그러나 Schnorr 프로토콜이 비대화형 영지식 증명 시스템으로 변환되면 진정한 "영지식"이 됩니다.
그러나 귀하의 질문도 올 수 있습니다.이 주장은 합리적으로 들립니다.그것을 증명할 수 있습니까?
"Cuihua, 시뮬레이터에 타십시오"
시뮬레이터 방법을 사용하여 "이상적인 세계"를 구성하는 방법은 무엇입니까? 당신은 그것에 대해 생각할 수 있습니다, 우리는 이전에 "시간을 거슬러"를 사용하고 "시뮬레이터"가 속임수를 쓰도록 "난수 컨베이어 벨트"의 슈퍼 파워를 수정했습니다. 그러나 상호 작용이 없으므로 "시간을 되돌려"라는 슈퍼 파워를 사용할 수 없으며 Bob의 난수 컨베이어 벨트가 존재하지 않으며 "컨베이어 벨트 조작"이라는 슈퍼 파워도 사용할 수 없습니다!
그러나 시뮬레이터는 신뢰의 "루트"를 구축할 수 있도록 항상 일종의 "슈퍼 파워"를 가지고 있어야 합니다.
(시뮬레이터가 초능력 없이 치트를 할 수 있는 능력이 있다면, 그것은 프로토콜의 신뢰성이 없음을 증명하는 것과 같습니다.)
아마도 모든 사람들이 지금까지 그것을 추측했을 것입니다. 시뮬레이터는 "무작위 오라클"에서 무언가를 해야 합니다.먼저 "영 지식"을 증명하기 위해 "이상적인 세계"를 구축하는 것을 고려하십시오. 이상적인 세계에서 시뮬레이터는 예언을 제공하는 "엘프"를 "납치"합니다. Bob이 엘프에게 난수를 요청했을 때 엘프는 실제 난수를 제공하지 않고 Zlice에게 제공했습니다(시뮬레이터는 be Alice) 사전에 준비된 숫자(또한 일관된 분포를 준수하고 구별 불가능함을 보장함), "지니"는 임의로 보이지만 실제로는 백도어가 있는 숫자를 Bob에게 반환할 수밖에 없습니다.
소위 백도어는 이 번호가 Zlice 자신이 미리 선택했음을 의미합니다.
1단계: Zlice는 z를 무작위로 선택하고 c를 무작위로 선택하고 R'=z*G - c*PK를 계산합니다.
2단계: Zlice는 c와 (m, R')을 스프라이트의 테이블에 기록합니다.
3단계: Zlice는 서명(c, z)을 Bob에게 보냅니다.
4단계: Bob은 R=z*G - c*PK를 계산하고 (m, R)을 elf에게 보내고 elf는 c'를 반환합니다. 여기서 Bob의 계산된 R과 Zlice의 계산된 R'은 동일합니다.
5단계: Bob은 elf가 반환한 난수가 상대방이 보낸 난수와 같은지 확인하기 위해 c ?= c'인지 확인합니다. 동일하면 확인 서명이 통과되고 그렇지 않으면 확인이 실패합니다.
"엘프"를 납치함으로써 Zlice는 사전에 난수를 예측할 수 있어 시간을 거슬러 올라가는 것과 같은 효과를 얻을 수 있습니다.
우리는 시뮬레이터 Zlice의 "존재"를 증명했으므로 위에서 NIZK를 증명했습니다.
sk = (z1 - z2)/(c1 - c2)
다음으로 이 프로토콜의 "신뢰성"을 증명합니다. 또 다른 "이상적인 세계"에서 "extractor"라는 것이 엘프를 납치했다고 상상해보십시오. 순진한 앨리스가 "elf"에게 임의의 숫자를 물었을 때 "elf"는 c1을 반환했고 "extractor"는 elf의 테이블에서 c1을 엿 보았습니다. Alice가 z1을 계산한 후 "extractor"는 여전히 슈퍼를 활성화할 수 있습니다. "reverse time"의 힘, Alice가 두 번째 단계로 돌아가서 "elf"에게 다시 임의의 숫자를 요청하면 Alice가 보낸 문자열은 분명히 처음 보낸 문자열과 동일합니다. (R, m ) . 논리적으로 (R, m)은 이미 스프라이트 시트의 "왼쪽 열"에 쓰여져 있으므로 정직한 "스프라이트"는 c1을 반환해야 합니다. 그러나 "추출기"는 스프라이트를 납치했고 테이블의 행(R, m)에 해당하는 "오른쪽 열"을 다른 숫자 c2로 변경했습니다. Alice가 또 다른 z2를 계산한 후 추출기는 작업을 완료하고 다음 방정식을 통해 Alice의 개인 키 sk를 계산합니다.
Fiat-Shamir 변환 - Public-Coin에서 NIZK로
Schnorr 프로토콜뿐만 아니라 모든 "Public-Coin 프로토콜"에 대해 Fiat-Shamir 변환을 사용하여 전체 프로토콜을 원스텝 상호 작용, 즉 비대화형 증명 시스템으로 "압축"할 수 있습니다. 변환 기술은 Amos Fiat와 Adi Shamir가 1986년 Crypto Conference에서 발표한 "How to Prove Yourself: Practical Solutions to Identification and Signature Problems"라는 논문에서 처음 등장했습니다[5]. 또한 이 기술은 Manuel Blum[6]에서 나온 것이라고 합니다.
다시 말하지만 Public-coin 프로토콜에서 유효성 검사기 Bob은 한 가지 유형의 작업만 수행합니다. 즉, 난수를 생성하고 Alice에게 도전하는 것입니다. Fiat-Shamir 변환을 통해 Bob의 각 "도전적인 행동"은 "무작위 예언"으로 대체될 수 있습니다.
특정 구현에서 랜덤 오라클은 암호화 보안 강도가 있는 해시 함수를 사용해야 하며(임의로 선택할 수 없으며 암호화 보안 해시를 사용해야 함) 해시 함수의 매개변수는 이전의 모든 컨텍스트 입력이어야 합니다. 다음은 이 Fiat-Shamir 변환의 실행을 빠르게 이해할 수 있는 예시 다이어그램입니다.
앞서 언급했듯이 비대화형 증명 시스템에서는 Bob이 Alice가 구축한 증명을 완전히 신뢰할 수 있도록 신뢰의 "루트"를 구축하기 위해 제3자를 도입해야 합니다. 여기서 제3자는 "elf"이며 학술 속어로는 "Random Oracle"입니다. 이 엘프는 현실의 제3자가 아니라 '현실세계'와 '이상세계'에 모두 존재하는 가상의 제3자다. '현실세계'에서 엘프는 책임감 있고 조용한 미남이지만 '이상세계'에서는 '시뮬레이터'에게 납치된다.
Public-Coin 프로토콜에는 "Arthur-Merlin Game"이라는 멋진 이름도 있습니다...
위의 사진을 보면 왼쪽의 "백의"는 멀린(마법사 멀린)이고 가운데에 검을 든 미남은 아서왕(King Arthur)이다. 아서왕의 원탁의 기사단.
아서는 동전을 가지고 다니는 참을성 없는 왕이고, 멀린은 무한한 컴퓨팅 파워를 가진 마법의 마술사입니다. 마술사, 그리고 마술사는 제 시간에 응답해야 하며 k 라운드 후에 왕이 자신의 판단을 믿게 해야 합니다. 멀린에게는 마법이 있기 때문에 아서 왕이 던진 모든 동전은 멀린[7]이 볼 수 있습니다.이것은 우리와 함께"시리즈 1"
에서 언급한 Interactive Proof System(줄여서 IP)은 다소 유사하지만 다릅니다. IP는 1985년 Goldwasser, Micali 및 Rackoff(줄여서 GMR)에 의해 공식적으로 제안되었으며 그 증명 능력은 많은 종류의 계산 복잡성 문제를 포괄합니다. 차이점은 IP의 정의에서 Prover와 Verifier는 모두 동전을 던질 수 있는 Turing 기계이고 Verifier는 비밀리에 동전을 던지고 Prover로부터 숨길 수 있는 반면 Arthur-Merlin 게임에서는 왕이 A 동전 던지기만 할 수 있고, 뿐만 아니라 Merlin은 항상 동전 던지기의 결과를 알고 있습니다.
그러나 Fiat-Shamir 변환은 "랜덤 오라클 모델" 하에서만 보안을 증명할 수 있으며 해시 함수를 사용하여 랜덤 오라클을 구현하는 프로세스가 안전한지 여부는 보안 증거가 부족합니다. 뿐만 아니라 "랜덤 오라클 모델" 하의 보안 프로토콜은 안전하지 않을 수 있으며 일부 반례가 발견되었습니다[8]. 더 불행하게도 S. Goldwasser와 Y. Tauman은 2003년에 그 자체로 반례 [9]. 그러나 이것은 Fiat-Shamir 변환을 사용할 수 없다는 의미는 아니지만 사용 중에 매우 주의해야 하며 맹목적으로 적용할 수 없습니다.
그럼에도 불구하고 극도로 널리 사용되는 Fiat-Shamir 변환의 유혹을 뿌리칠 수 없습니다. Fiat-Shamir 변환이 가장 인기 있는 범용 비대화형 영지식 증명 zkSNARK의 다양한 체계에 많다는 점을 언급할 가치가 있습니다. 예를 들어 Bulletproofs(방탄)에 익숙할 수 있으며 Hyrax, Ligero, Supersonic, Libra 등 당분간 잘 알려지지 않은 범용 영지식 증명 체계가 있습니다. (우리는 후속 조치를 취하고 하나씩 설명할 것입니다).
주의: Fiat-Shamir 변환의 보안 의미
Fiat-Shamir 변환에서 Hash 함수에 입력되는 매개 변수에 특히 주의하십시오.실제 코드 구현에서 Hash 함수의 일부 매개 변수가 생략되는 경우가 있습니다.
예를 들어, A, Hash(A), B, Hash(B)에서 두 번째 Hash 함수는 매개변수 A를 놓치고 올바른 방법은 A, Hash(A), B, Hash(A,B)여야 합니다. 이러한 유형의 접근 방식은 심각한 보안 허점을 도입합니다.예를 들어, 스위스 전자 투표 시스템 SwissPost-Scytl에서 Fiat-Shamir 변환의 구현 코드는 존재해야 하는 매개 변수를 반복적으로 누락하여 공격자가 투표를 무효화할 수 있을 뿐만 아니라 사기의 목적을 달성하기 위해 투표 용지를 마음대로 위조할 수 있습니다[10]. 따라서 엔지니어링 구현에 주의하십시오.
신중한 독자는 Schnorr 서명을 다시 살펴볼 수 있으며 Schnorr 서명의 해시 알고리즘이 엄격한 Fiat-Shamir 변환이 아닌 Weak Fiat-Shamir 변환이라고 하는 매개변수 PK를 놓친 것 같습니다[11 ]. 단, 이 특별한 경우[3]에는 보안상 문제가 없으므로 미성년자를 임의로 흉내내지 마시기 바랍니다.
최근 일부 학자들은 표준 모델 하에서 Fiat-Shamir 변환의 보안을 엄격하게 증명하는 방법에 대한 연구를 시작했으며 현재는 강력한 보안 가정을 추가로 도입하거나 특정 프로토콜에 대해 이를 증명하는 방법을 사용하고 있지만 그다지 많지 않은 것으로 보입니다. 진전.
상호 작용의 힘
1985년 GMR 트리오의 논문이 여러번의 거절 끝에 STOC'85에 받아들여졌을 때 비슷한 또 다른 작업이 동시에 STOC'85에 받아들여졌다고 합니다. , 그리고 Israel Institute of Technology[7]의 Shlomo Moran이 저술한 "Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes" 논문은 공개 코인 상호작용 프로토콜(이름에서 알 수 있듯이 Verifier 전용 공개적으로 동전 던지기) .
King Arthur의 방법은 매우 간단합니다. Merlin의 주장은 반복되는 "무작위" 도전으로 테스트되며, 이는 앞서 설명한 직관과 일치합니다: 무작위 도전을 사용하여 신뢰의 "루트"를 구축합니다. Babai는 논문에서 AM[k]=AM[2]라는 흥미로운 결론을 증명했습니다. 여기서 k는 상호 작용의 수를 나타내며 여러 상호 작용의 효과는 두 개의 상호 작용과 동일합니다. 소위 상호작용은 두 번 의미합니다. Arthur가 챌린지 번호를 보낸 다음 Merlin이 응답합니다.
참고: MA에 속하는 또 다른 유형의 문제가 있습니다. 이러한 유형의 문제의 대화형 순서는 AM의 순서와 다릅니다. MA에서는 Merlin이 먼저 증명을 제공한 다음 Arthur가 검사를 위해 동전을 던집니다. MA가 처리할 수 있는 문제는 AM의 하위 집합이라는 것이 입증되었습니다.
뿐만 아니라 Babai는 대담하게 추측했습니다. AM[poly]는 IP와 동일합니다. 이것은 마법의 주장입니다. 왕은 게으르고 다항식 동전을 던지기만 하면 마술사에게 성공적으로 도전할 수 있으며 이 방법의 표현력은 GMR에서 설명하는 대화형 증명 시스템 IP와 완전히 동일합니다. 아니나 다를까, STOC'86 회의에서 S. Goldwasser와 M. Sipser의 논문이 AM[poly] == IP[12]라는 사실을 증명했습니다.
즉, 반복되는 공개 "랜덤 챌린지"는 무한히 강력하며 모든 대화식 증명 시스템과 동일합니다. 그러나 AM[poly]와 다른 계산 복잡성 클래스 간의 관계는 다음 연구 핫스팟입니다.
AM[poly] == IP == PSPACE
3년 후, 정확히 30년 전인 1989년 11월 말, 젊은 암호학자 노암 니산(Noam Nisan)은 여러 암호학자에게 자신의 잠정적인 학문적 결론을 이메일로 보낸 다음 휴가 중 남미로 달려갔습니다. 그러나 그는 이 이메일이 M. Blum, S. Kannan, D. Lipton, D. Beaver, J. Feigenbaum, H. Karloff, C. Lund 등의 대규모 그룹과 함께 역사상 치열한 학술 경쟁을 폭발시킬 것이라고는 생각하지 못했습니다. . 엘리트들이 전투에 참여하기 시작했습니다. 그들은 밤낮으로 서로 논의하고 경쟁하여 연구 결과를 발표했습니다. 마침내 정확히 한 달인 12월 26일, Adi Shamir는 다음과 같은 결론을 증명했습니다.
"유효 증명" 개념의 계산 이론적 특성을 설명하고 "상호 작용 증명 시스템" 개념이 다루는 컴퓨팅 성능을 설명합니다.
참고: NP 클래스는 PSPACE 클래스의 하위 집합으로, 전자는 모든 사람에게 더 친숙하고 후자는 게임이나 체스에서 이기는 전략과 관련이 있습니다[13].
그리고 L. Babai는 "이메일과 예상치 못한 상호작용의 힘"(Email and the 예기치 않은 상호작용의 힘)[14]이라는 기사를 썼고, 이 달 전체에 대해 "이메일 상호작용"에서 자세히 설명했습니다. "대화식 증명".
공개 참조 문자열 - 또 다른 "신뢰의 루트"
예, 맞습니다. 여기에 다시 "제3자"가 있습니다! 제3자가 증명에 직접 참여하지는 않지만 무작위 문자열 생성 프로세스의 신뢰성을 보장해야 합니다. CRS를 생성하는 과정은 "신뢰할 수 있는 설정"이라고도 하는데 모두가 좋아하고 싫어하는 것입니다. 분명히 실제 시나리오에서 제3자를 데려오는 것은 골칫거리가 될 수 있습니다. CRS는 정확히 무엇을 위해 사용됩니까? Trusted Setup의 신뢰는 여기서 어디로 갑니까? 이 부분은 이 시리즈의 다음 기사를 위해 예약되어 있습니다.
계속되다
계속되다
비대화형 영지식은 NIZK의 "신뢰의 근원"에도 어떤 형태의 임의의 "도전"이 필요하다는 것을 증명합니다. "도전"의 한 형태는 "무작위 예언 엘프"에게 전달되며 달성하기 위해 임의의 문자열을 공유합니다. 두 형태의 챌린지 모두 본질적으로 제3자를 도입하고, 둘 다 "시뮬레이터"가 이용할 수 있는 "백도어"를 제공해야 합니다. "실제 세계"에서 실패하십시오.
NIZK는 무한한 매력을 발산하여 때때로 놀라움을 선사합니다.지난 30년 동안 선구자들은 미묘한 결론을 탐구했으며 동시에 미지의 구석이 너무 많아 영감의 빛을 기다리고 있습니다.이 기사 시리즈는 Github에 있습니다.프로젝트 저장소
Jingyu Hu(colortigerhu)의 첫 번째 Pull Request를 받고 몇 마디만 바꿨을 뿐인데 그 순간 활력을 느꼈습니다. 지식의 교환, 아이디어의 충돌이 매력적이지 않습니까?
"우리가 상호 작용하는 모든 사람은 우리의 일부가 됩니다." 우리가 상호 작용하는 모든 사람은 우리의 일부가 됩니다. ―조디 아만
텍스트
참조
[1] Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174.
[2] Paillier, Pascal, and Damien Vergnaud. "Discrete-log-based signatures may not be equivalent to discrete log." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2005.
[3] Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures." Journal of cryptology 13.3 (2000): 361-396.
[4] Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. "Simple schnorr multi-signatures with applications to bitcoin." Designs, Codes and Cryptography 87, no. 9 (2019): 2139-2164.
[5] Fiat, Amos, and Adi Shamir. "How to prove yourself: Practical solutions to identification and signature problems." Conference on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1986.
[6] Bellare, Mihir, and Phillip Rogaway. "Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols." Proc. of the 1st CCS (1995): 62-73.
[7] László Babai, and Shlomo Moran. "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes." Journal of Computer and System Sciences 36.2 (1988): 254-276.m
[8] Canetti, Ran, Oded Goldreich, and Shai Halevi. "The random oracle methodology, revisited." Journal of the ACM (JACM)51.4 (2004): 557-594.
[9] Shafi Goldwasser, and Yael Tauman . "On the (in) security of the Fiat-Shamir paradigm." 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. IEEE, 2003.
[10]Lewis, Sarah Jamie, Olivier Pereira, and Vanessa Teague. "Addendum to how not to prove your election outcome: The use of nonadaptive zero knowledge proofs in the ScytlSwissPost Internet voting system, and its implica tions for castasintended verifi cation." Univ. Melbourne, Parkville, Australia (2019).
[11] Bernhard, David, Olivier Pereira, and Bogdan Warinschi. "How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2012.
[12] Goldwasser, Shafi, and Michael Sipser. "Private coins versus public coins in interactive proof systems." Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM, 1986.
[13] Papadimitriou, Christos H. "Games against nature." Journal of Computer and System Sciences 31.2 (1985): 288-301.
[14] Babai, László. "E-mail and the unexpected power of interaction." Proceedings Fifth Annual Structure in Complexity Theory Conference. IEEE, 1990.
[15] Yi Deng. "참조" https://zhuanlan.zhihu.com/p/29491567
IOS
Android