비 상호작용 영지식 증명

NIZK,^[1] zk-SNARK,^[2] zk-STARK라고도 알려진 비인터랙티브 제로 지식 증명서는 프로베라와 검증자 사이의 상호작용이^{[clarification needed]} 필요 없는 제로 지식 증명이다.^{[3][full citation needed]}

역사

이 섹션은 제로 지식 증명서가 실제 애플리케이션과 앱에서 어떻게 그리고 어떤 목적으로 사용되는지에 대한 이력을 통해 확장할 필요가 있다. 덧셈으로 도움받을 수 있다(2020년 10월)

블럼, 펠드만, 미칼리는^[4] 1988년에 프로베라와 검증자가 공유하는 공통의 참조 문자열만으로도 상호작용이 필요 없이 연산 영지식을 달성하기에 충분하다는 것을 보여주었다. 골드리치와 오렌은^[5] 표준 모델에서 원샷 제로 지식 프로토콜에 대해 불가능한 결과를^{[clarification needed]} 주었다. 2003년에 샤피 골드워서와 야엘 타우만 칼라이는 어떤 해시함수라도 불안정한 디지털 서명 체계를 산출할 수 있는 식별 방식의 예를 발표했다.^[6] 골드레이치와 오렌의 불가능성^{[clarification needed]} 결과가 공통의 참조 문자열 모델이나 랜덤 오라클 모델에서 유지되지 않기 때문에 이러한 결과는 모순되지 않는다. 그러나 비인터랙티브 제로 지식 증명서는 표준 모델에서 달성할 수 있는 암호 업무와 '더 강력한' 확장 모델에서 달성할 수 있는 암호 업무 간의 분리를 보여준다.^{[citation needed]}

모델은 영지식 프로토콜에서 얻을 수 있는 속성에 영향을 미친다. Pass는^[7] 공통 기준 문자열 모델에서 비 상호작용 제로 지식 프로토콜이 대화형 제로 지식 프로토콜의 모든 속성을 보존하지 않는다는 것을 보여주었다. 예를 들어, 그것들은 deniability를 보존하지 않는다.

비 상호작용 영지식 증명서는 Fiat-Shamir 휴리스틱을 사용하여 랜덤 오라클 모델에서도 얻을 수 있다. 비탄스키 외 연구원의 2012년 기사는 제로 지식의 간결한 비 인터랙티브 지식의 주장을 위해 zk-SNARK라는 약자를 소개했다.^[2] zk-SNARKs의 첫 번째 광범위한 적용은 제로 지식 암호화가 계산적 백본을 제공하는 제로카시 블록체인 프로토콜에 있었는데, 그 정보가 무엇인지 밝히지 않고 한 당사자가 특정 정보를 소유한다는 수학적 증거를 용이하게 함으로써, 이 프로토콜에 있었다.^[8]

2017년에는 필드 및 그룹 요소의 로그(범위 비트 길이) 수를 사용하여 커밋된 값이 범위 내에 있음을 증명할 수 있는 방탄이 출시되었다.^[9] 방탄은 이후 밈블림블 프로토콜(그릭과 빔 암호화폐가 기반이 되는 곳)과 모네로 암호화폐에 구현됐다.^[10]

2018년에는 zk-STARK(지식의 확장 가능한 0-지식의 투명한 ARguation ^[11]of Knowledge) 프로토콜이 도입되어 투명성(신뢰할 수 없는 설정)과 준선형 입증시간, 다원형 검증시간을 제공한다.^[12][3]

정의

원래,^[4] 비 상호작용 제로 지식은 단일의 정리 증명 체계로만 정의되었다. 그러한 시스템에서 각 증명에는 자체적인 새로운 공통 참조 문자열이 필요하다. 일반적으로 일반적인 참조 문자열은 임의의 문자열이 아니다. 예를 들어, 그것은 모든 프로토콜 당사자들이 사용하는 임의로 선택된 그룹 요소들로 구성될 수 있다. 그룹 요소는 랜덤이지만, 참조 문자열은 랜덤성과 구별할 수 있는 특정 구조(예: 그룹 요소)를 포함하고 있기 때문에 그렇지 않다. 그 후 페이지, 라피도트, 샤미르는^[13] 비 인터랙티브 제로 지식 증명에 대해 보다 다용도 개념으로 다중이론 제로 지식 증빙을 도입하였다.

페어링 기반 비 상호 작용 증명

페어링 기반 암호화는 몇 가지 암호 진보로 이어졌다. 이러한 진보들 중 하나는 보다 강력하고 효율적인 비 상호 작용 제로 지식 증명이다. 중요한 아이디어는 쌍의 평가에 대한 가치를 공약으로 감추는 것이었다. 다른 약속 체계를 사용하여, 이 아이디어는 하위 그룹 은닉과^[14] 의사결정 선형 가정 하에서 제로 지식 증명 시스템을 구축하는데 사용되었다.^[1] 이러한 증명 시스템은 회로 만족도를 입증하며, 따라서 쿡-레빈 정리에 의해 NP의 모든 언어에 대한 구성원 자격을 증명할 수 있다. 공통 참조 문자열과 교정쇄의 크기는 비교적 작지만, 문장을 부울 회로로 변환하면 상당한 오버헤드가 발생한다.

하위 그룹 은닉, 의사결정 선형 가정 및 외부 Diffie- 아래의 증명 시스템페어링 기반 암호화에 공통적인 페어링 제품 방정식을 직접 증명할 수 있는 헬맨 가정이 제안됐다.^[15]

강력한 지식 가정 하에서, NP-완성 언어에 대해 계산적으로 건전한 증명 시스템을 만드는 방법을 알고 있다. 더 정확히 말하면, 그러한 증명 시스템의 증거는 소수의 이선형 그룹 요소들로만 구성된다.^[16][17]

참조