서브메뉴
검색
A New Paradigm for Efficient and Scalable Zero-Knowledge Proofs
A New Paradigm for Efficient and Scalable Zero-Knowledge Proofs
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20250211151514
- ISBN
- 9798384015529
- DDC
- 004
- 저자명
- Weng, Chenkai.
- 서명/저자
- A New Paradigm for Efficient and Scalable Zero-Knowledge Proofs
- 발행사항
- [Sl] : Northwestern University, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 158 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-02, Section: B.
- 주기사항
- Advisor: Wang, Xiao.
- 학위논문주기
- Thesis (Ph.D.)--Northwestern University, 2024.
- 초록/해제
- 요약Zero-Knowledge proof (ZKP) is a combination of cryptographic protocol and mathematical proof that allows a prover to convince a verifier on the correctness of a statement, without revealing its private information that validates the statement. It is a privacy-enhancing technique that can not only prove NP statements, but also correct operations over secrets. The exemplary functionalities of ZKP-based systems include proving sufficiency of bank deposit without revealing the amount; proving correct inference of an image by a private neural network model; proving correct SQL execution on a private database.Most of existing ZKPs are designed for the asynchronous setting with focus on noninteractiveness, public verifiability and succinctness. However, they suffer from long proof generation time and large memory usage. In this thesis, we propose a new paradigm for streaming interactive zero-knowledge proof protocols. By allowing a constant number of round communication, it enables low proving time and memory overhead, which leads to significantly better efficiency, regarding the end-to-end running time, and scalability, regarding the complexity of statement that can be proven with constrained memory resource.(1) We introduce the vector oblivious linear evaluation (VOLE), which is the most important building block for these interactive ZKPs. It allows a prover to efficiently commit to extended witnesses in tens to hundreds of nanoseconds per wire.(2) We present the Wolverine protocol, which utilizes VOLE to construct an interactive commitment scheme. Then it leverages the cut-and-bucketing technique to verify the correctness of extended witnesses with respect to non-linear gates. The Wolverine protocols works for both small (F2) and large (Fp) fields. Furthermore, we present the Quicksilver protocol that improves from Wolverine on its verification process and reduces its communication by 3x. Its method is also extended to the verification of polynomial sets.(3) To further improve the communication overhead, we propose the AntMan protocol that proves (B,C)−SIMD circuits with cost O(C), while the naive implementation requires O(BC). By adding a check of wiring consistency, it is able to prove an arbitrary size-C circuit with O(C3/4) communication overhead.(4) We discuss the Mystique protocol that enables Quicksilver to handle mixed statements. Specifically, it allows the statement representation to compose both Boolean and arithmetic circuits as well as polynomials. This design allows efficient proof of complicated statements and promotes the versatility of ZKP applications such as the zero-knowledge machine learning (ZKML).
- 일반주제명
- Computer science
- 일반주제명
- Applied mathematics
- 일반주제명
- Information technology
- 키워드
- AntMan protocol
- 기타저자
- Northwestern University Computer Science
- 기본자료저록
- Dissertations Abstracts International. 86-02B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008250123s2024 us c eng d■001000017162012
■00520250211151514
■006m o d
■007cr#unu||||||||
■020 ▼a9798384015529
■035 ▼a(MiAaPQ)AAI31300240
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aWeng, Chenkai.
■24512▼aA New Paradigm for Efficient and Scalable Zero-Knowledge Proofs
■260 ▼a[Sl]▼bNorthwestern University▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a158 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-02, Section: B.
■500 ▼aAdvisor: Wang, Xiao.
■5021 ▼aThesis (Ph.D.)--Northwestern University, 2024.
■520 ▼aZero-Knowledge proof (ZKP) is a combination of cryptographic protocol and mathematical proof that allows a prover to convince a verifier on the correctness of a statement, without revealing its private information that validates the statement. It is a privacy-enhancing technique that can not only prove NP statements, but also correct operations over secrets. The exemplary functionalities of ZKP-based systems include proving sufficiency of bank deposit without revealing the amount; proving correct inference of an image by a private neural network model; proving correct SQL execution on a private database.Most of existing ZKPs are designed for the asynchronous setting with focus on noninteractiveness, public verifiability and succinctness. However, they suffer from long proof generation time and large memory usage. In this thesis, we propose a new paradigm for streaming interactive zero-knowledge proof protocols. By allowing a constant number of round communication, it enables low proving time and memory overhead, which leads to significantly better efficiency, regarding the end-to-end running time, and scalability, regarding the complexity of statement that can be proven with constrained memory resource.(1) We introduce the vector oblivious linear evaluation (VOLE), which is the most important building block for these interactive ZKPs. It allows a prover to efficiently commit to extended witnesses in tens to hundreds of nanoseconds per wire.(2) We present the Wolverine protocol, which utilizes VOLE to construct an interactive commitment scheme. Then it leverages the cut-and-bucketing technique to verify the correctness of extended witnesses with respect to non-linear gates. The Wolverine protocols works for both small (F2) and large (Fp) fields. Furthermore, we present the Quicksilver protocol that improves from Wolverine on its verification process and reduces its communication by 3x. Its method is also extended to the verification of polynomial sets.(3) To further improve the communication overhead, we propose the AntMan protocol that proves (B,C)−SIMD circuits with cost O(C), while the naive implementation requires O(BC). By adding a check of wiring consistency, it is able to prove an arbitrary size-C circuit with O(C3/4) communication overhead.(4) We discuss the Mystique protocol that enables Quicksilver to handle mixed statements. Specifically, it allows the statement representation to compose both Boolean and arithmetic circuits as well as polynomials. This design allows efficient proof of complicated statements and promotes the versatility of ZKP applications such as the zero-knowledge machine learning (ZKML).
■590 ▼aSchool code: 0163.
■650 4▼aComputer science
■650 4▼aApplied mathematics
■650 4▼aInformation technology
■653 ▼aZero-knowledge proof
■653 ▼aNoninteractiveness
■653 ▼aAntMan protocol
■690 ▼a0984
■690 ▼a0489
■690 ▼a0364
■71020▼aNorthwestern University▼bComputer Science.
■7730 ▼tDissertations Abstracts International▼g86-02B.
■790 ▼a0163
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17162012▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
