“Updatable and Universal CRS with applications to zk-SNARK” 정리

Hankyung Ko
Nov 3 · 3 min read

Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meiklejohn, Ian Miers, in Crypto 2018.

문제 정의

  • 기존의 zk-SNARK 시스템에서 CRS는 Relation에 종속되어 생성되기 때문에 매번 새롭게 Setup이 필요하다. → Universal Setup이 필요
  • CRS를 Trusted Party가 생성한다. → Subvertible Setup이 필요
    * Proof들은 공유된 CRS를 이용해서 생성 및 검증되는데, zero knowledge를 만족하기 위해 CRS를 생성할 때 simulation trapdoor를 생성하고, 버리게 된다. 만약 Setup을 한 주체가 honest하지 않아 trapdoor를 버리지 않고 저장해놓는다면 false proof를 언제나 생성할 수 있게 된다.

Subvertible Setup

Setup generator가 직접 setup하지 않고, Adversary로부터 CRS를 받고, 이를 verify한 뒤 사용한다. 따라서, Subvertible Setup이 가장 이상적이나, subversion soundness와 standard zero-knowledge는 동시에 만족될수 없다.
따라서 이 논문에서는 Updatable Setup을 제안하고, 이러한 updatable soundness는 subversion zero-knowledge와 동시에 만족될수 있기 때문에, updatable zero-knowledge와도 동시에 만족될 수 있다.

Updatable Setup

  • Monomial 기법을 이용해서 updatably sound한 scheme을 만드는 것은 어렵지 않으나[Gro10b], 이렇게 하기 위해서는 quadratic-sized reference string이 필요하고, 즉, quadratic prover complexity를 야기한다.
  • 따라서 이 논문에서는 quadratic-sized universal CRS에서 linear-sized relation-dependent CRS를 derive해서 사용하는 scheme을 제안하고 있고, 그렇기 때문에 본 논문에서 prover는 linear complexity를 가진다.

Hankyung Ko

Written by

Currently pursuing PhD degree at Hanyang University, Seoul, Korea. www.linkedin.com/in/hankyung-ko-b892a7119

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade