Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Gemini: Elastic SNARKs for Diverse Environments
 
conference paper

Gemini: Elastic SNARKs for Diverse Environments

Bootle, Jonathan
•
Chiesa, Alessandro  
•
Hu, Yuncong
Show more
January 1, 2022
Advances In Cryptology - Eurocrypt 2022, Pt Ii
41st Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt)

We introduce a new class of succinct arguments, that we call elastic. Elastic SNARKs allow the prover to allocate different resources (such as memory and time) depending on the execution environment and the statement to prove. The resulting output is independent of the prover's configuration. To study elastic SNARKs, we extend the streaming paradigm of [Block et al., TCC'20]. We provide a definitional framework for elastic polynomial interactive oracle proofs for R1CS instances and design a compiler which transforms an elastic PIOP into a preprocessing argument system that supports streaming or random access to its inputs. Depending on the configuration, the prover will choose different trade-offs for time (either linear, or quasilinear) and memory (either linear, or logarithmic). We prove the existence of elastic SNARKS by presenting Gemini, a novel FFT-free preprocessing argument. We prove its security and develop a proof-of-concept implementation in Rust based on the arkworks framework. We provide benchmarks for large R1CS instances of tens of billions of gates on a single machine.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-031-07085-3_15
Web of Science ID

WOS:000832305300015

Author(s)
Bootle, Jonathan
Chiesa, Alessandro  
Hu, Yuncong
Orru, Michele
Date Issued

2022-01-01

Publisher

SPRINGER INTERNATIONAL PUBLISHING AG

Publisher place

Cham

Published in
Advances In Cryptology - Eurocrypt 2022, Pt Ii
ISBN of the book

978-3-031-07085-3

978-3-031-07084-6

Series title/Series vol.

Lecture Notes in Computer Science

Volume

13276

Start page

427

End page

457

Subjects

Computer Science, Information Systems

•

Computer Science, Theory & Methods

•

Mathematics, Applied

•

Computer Science

•

Mathematics

•

succinct non-interactive arguments

•

interactive oracle proofs

•

proofs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
COMPSEC  
Event nameEvent placeEvent date
41st Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt)

Trondheim, NORWAY

May 30-Jun 03, 2022

Available on Infoscience
August 15, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/190038
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés