서브메뉴
검색
Scalable Succinct Arguments from Interactive Reductions
Scalable Succinct Arguments from Interactive Reductions
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202105612
- ISBN
- 9798265427625
- DDC
- 620
- 저자명
- Nguyen, Wilson.
- 서명/저자
- Scalable Succinct Arguments from Interactive Reductions
- 발행사항
- [Sl] : Stanford University, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 252 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-05, Section: B.
- 주기사항
- Advisor: Boneh, Dan.
- 학위논문주기
- Thesis (Ph.D.)--Stanford University, 2025.
- 초록/해제
- 요약A Succinct Non-interactive Argument of Knowledge (SNARK) is a cryptographic proof system, with which a prover can generate a short proof that it knows of a corresponding witness that attests to the veracity of a target statement. A verifier can check this proof in significantly less time than is required to plainly check the statement and witness. In the past decade, we have seen a Cambrian explosion of both academic and industry research to construct practically efficient SNARK provers. Despite this, modern SNARKs encounter several barriers which prevent their ubiquitous adoption. 1) SNARK provers require a significant amount of memory to run-often requiring terabytes of RAM, spread across numerous powerful machines. 2) SNARKs often rely on a trusted setup ceremony which, if done improperly, could allow a malicious prover to generate convincing proofs of false statements. 3) Popular SNARKs crucially rely on the hardness of the discrete-logarithm problem. A problem which can be efficiently solved with a quantum computer using Shor's algorithm.In this dissertation, we develop a generic framework to construct memory efficient SNARKs from folding schemes-a recent cryptographic primitive which reduces the task of proving several statements down to just a single statement. Amazingly, if the folding scheme does not require a trusted setup and is plausibly post-quantum secure, then the corresponding SNARK also does not require a trusted setup and is plausibly post-quantum secure. We give several constructions of folding schemes which do not require trusted setup, improve efficiency, and diversify the set of cryptographic assumptions. In particular, we give 1) a generalization of existing folding schemes based on DLP which enables folding committed statements, giving us a SNARK that, when run on a laptop, can prove large statements in under a gigabyte of RAM and in a projected order of magnitude less time 2) a plausibly post-quantum folding scheme constructed purely from hashing (random oracles) using a novel technique to reduce many claims about proximity to a code-word down to a single proximity claim with identical distance 3) another plausibly post-quantum folding scheme, based on the well-studied Module Short Integer Solution (MSIS) problem, that may outperform even our best pre-quantum constructions, is more hardware friendly, and has a pay-per-bit cost (the prover run-time scales closely with the exact number of bits of the statement). We develop several new frameworks (polynomial witness testing, interactive oracle reductions, restricted & relaxed reductions) which dramatically reduce the complexity to construct and prove the security of folding schemes.
- 일반주제명
- Circuits
- 일반주제명
- Protocol
- 일반주제명
- Communication
- 일반주제명
- Electrical engineering
- 기타저자
- Stanford University.
- 기본자료저록
- Dissertations Abstracts International. 87-05B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017360730
■00520260202105612
■006m o d
■007cr#unu||||||||
■020 ▼a9798265427625
■035 ▼a(MiAaPQ)AAI32316403
■035 ▼a(MiAaPQ)Stanfordgq907kq7220
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a620
■1001 ▼aNguyen, Wilson.
■24510▼aScalable Succinct Arguments from Interactive Reductions
■260 ▼a[Sl]▼bStanford University▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a252 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-05, Section: B.
■500 ▼aAdvisor: Boneh, Dan.
■5021 ▼aThesis (Ph.D.)--Stanford University, 2025.
■520 ▼aA Succinct Non-interactive Argument of Knowledge (SNARK) is a cryptographic proof system, with which a prover can generate a short proof that it knows of a corresponding witness that attests to the veracity of a target statement. A verifier can check this proof in significantly less time than is required to plainly check the statement and witness. In the past decade, we have seen a Cambrian explosion of both academic and industry research to construct practically efficient SNARK provers. Despite this, modern SNARKs encounter several barriers which prevent their ubiquitous adoption. 1) SNARK provers require a significant amount of memory to run-often requiring terabytes of RAM, spread across numerous powerful machines. 2) SNARKs often rely on a trusted setup ceremony which, if done improperly, could allow a malicious prover to generate convincing proofs of false statements. 3) Popular SNARKs crucially rely on the hardness of the discrete-logarithm problem. A problem which can be efficiently solved with a quantum computer using Shor's algorithm.In this dissertation, we develop a generic framework to construct memory efficient SNARKs from folding schemes-a recent cryptographic primitive which reduces the task of proving several statements down to just a single statement. Amazingly, if the folding scheme does not require a trusted setup and is plausibly post-quantum secure, then the corresponding SNARK also does not require a trusted setup and is plausibly post-quantum secure. We give several constructions of folding schemes which do not require trusted setup, improve efficiency, and diversify the set of cryptographic assumptions. In particular, we give 1) a generalization of existing folding schemes based on DLP which enables folding committed statements, giving us a SNARK that, when run on a laptop, can prove large statements in under a gigabyte of RAM and in a projected order of magnitude less time 2) a plausibly post-quantum folding scheme constructed purely from hashing (random oracles) using a novel technique to reduce many claims about proximity to a code-word down to a single proximity claim with identical distance 3) another plausibly post-quantum folding scheme, based on the well-studied Module Short Integer Solution (MSIS) problem, that may outperform even our best pre-quantum constructions, is more hardware friendly, and has a pay-per-bit cost (the prover run-time scales closely with the exact number of bits of the statement). We develop several new frameworks (polynomial witness testing, interactive oracle reductions, restricted & relaxed reductions) which dramatically reduce the complexity to construct and prove the security of folding schemes.
■590 ▼aSchool code: 0212.
■650 4▼aCircuits
■650 4▼aProtocol
■650 4▼aCommunication
■650 4▼aElectrical engineering
■690 ▼a0459
■690 ▼a0544
■71020▼aStanford University.
■7730 ▼tDissertations Abstracts International▼g87-05B.
■790 ▼a0212
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17360730▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
