rwc.iacr.org

rwc.iacr.org

Zero knowledge, subversion-resistance, and concrete attacks Steven Goldfeder Princeton University @sgoldfed Joint work with Matteo Campanelli, Rosario Gennaro, Luca Nizzardo City University of New York

City University of New York IMDEA Software Institute Universidad Politcnica de Madrid Youve likely heard that SNARKs require a trusted setup 2

But what could actually go wrong? 3 Zero-knowledge contingent payments 4 The problem Ill pay after I

get the solution Ill give you the solution after you pay 5 Zero Knowledge Contingent Payments

6 [Maxwell] Hash-locked transactions 7 Hash-locked transactions

signed: Alice Pay Bobbi iff she reveals x: SHA2(x)=y 8 Hash-locked transactions signed: Alice

Pay Bobbi iff she reveals x: SHA2(x)=y signed: Bobbi Here is x 9 Zero Knowledge Contingent Payments

Ill pay after I get the solution [Maxwell] Ill tell you the solution after you pay 10

Zero Knowledge Contingent Payments 11 [Maxwell] Zero Knowledge Contingent Payments 12

[Maxwell] Zero Knowledge Contingent Payments 13 [Maxwell] Zero Knowledge Contingent Payments

14 [Maxwell] Zero Knowledge Contingent Payments [Maxwell] y = SHA2(

15 ) Zero Knowledge Contingent Payments [Maxwell] y

y = SHA2( 16 ) Zero Knowledge Contingent Payments y

17 [Maxwell] Zero Knowledge Contingent Payments y ZK Proof is in

and y = SHA2( ) 18 [Maxwell] Zero Knowledge Contingent Payments y

ZK Proof is in and y = SHA2( ) 19 [Maxwell]

Zero Knowledge Contingent Payments y 20 [Maxwell] Zero Knowledge Contingent Payments y signed: Alice

Pay Bobbi iff she reveals : SHA2( ) = y 21 [Maxwell] Zero Knowledge Contingent Payments y

signed: Alice Pay Bobbi iff she reveals : SHA2( ) = y signed: Bobbi Here is 22 [Maxwell]

Zero Knowledge Contingent Payments y signed: Alice Pay Bobbi iff she reveals : SHA2( ) = y signed: Bobbi Here is

23 [Maxwell] Zero Knowledge Contingent Payments y signed: Alice Pay Bobbi iff she reveals : SHA2( ) = y

signed: Bobbi Here is 24 [Maxwell] Zero Knowledge Contingent Payments y signed: Alice

Pay Bobbi iff she reveals : SHA2( ) = y signed: Bobbi + =

Here is 25 [Maxwell] Zero Knowledge Contingent Payments y I know the solution!

signed: Alice Pay Bobbi iff she reveals : SHA2( ) = y I was paid! signed: Bobbi +

= Here is 26 [Maxwell] How do we implement the proof? ZK Proof

is in and y = SHA2( ) 27 28

Zero-knowledge Proofs [GMR85] Soundness: Bobbi needs to prove that she actually encrypted a valid solution Zero-knowledge: Alice can learn nothing about the solution from the proof other than its valid 29

Non-interactive ZK Proofs [BFM88] requires a trusted set of common parameters called a common reference string (CRS) Succinct Non-Interactive Arguments of Knowledge (zkSNARKs) [GGPR12, PGHR13]

very efficient non-interactive arguments require a trusted setup 30 Implementing the proof with zkSNARKs 31

Who performs the trusted setup? source: https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-paymentsannouncement/ 32 Zero Knowledge Contingent Payments CRS 33

[Maxwell] Zero Knowledge Contingent Payments [Maxwell] CRS Protects against a malicious seller

Does not protect against a malicious buyer 34 Concrete Attack [CGGN17] Malicious CRS 35

Concrete Attack [CGGN17] Malicious CRS 36 Concrete Attack

[CGGN17] I got the solution for free! Malicious CRS 37 Dual adversarial model

zero-knowledge adversary soundness adversary CRS 38 We implemented this attack - interacts with the honest pay-to-sudoku seller

- steals part of the solution 39 Key Takeaway The GGPR12 trusted setup is for both ZK and soundness 40

Can we fix this? Yes! Subversion Zero Knowledge G. Fuchsbauer, Subversion-zero-knowledge SNARKs. Cryptology ePrint Archive: Report 2017/587. B. Abdolmaleki, K. Baghery, H. Lipmaa, M. Zajac. A Subversion-Resistant SNARK. Asiacrypt 2017. S. Bowe, A. Garbizon, M. Green, A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK. Cryptology ePrint Archive: Report 2017/602.

41 Subversion Zero-knowledge Zero knowledge no longer relies on trust Soundness still requires trust 42 Zcash setup: What could go wrong?

If setup is subverted, the adversary can create false proofs/mint money (soundness) cannot break anonymity (zero-knowledge) 43 Subversion ZK is very expensive For Zcash, this is a one time cost, so doesnt matter But, for ZKCP, the setup happens every time

Broken pay-to-sudoku ran in < 1 minute With subversion ZK , ceremony takes > 45 minutes 44 What if we dont need zeroknowledge? 45 46

Witness Indistinguishability [FS90] cannot distinguish between proofs w/ different witnesses May leak information that is common to all witnesses GGPR12 already showed how to get subversion-WI WI is not enough! ZK Proof is in and y = SHA2(

) 47 Our protocol Ill pay after I get the solution Ill tell you the

solution after you pay 48 Our protocol OR 49

Our protocol OR 50 Our protocol 51 Our protocol

y = SHA2( ) OR SHA3( 52 ) Our protocol

y y = SHA2( ) OR SHA3( 53 )

Our protocol y 54 Our protocol y WI Proof

if is in then y = SHA2( ) if

is in then y = SHA3( ) 55 Our protocol y

ZK Proof if is in then y = SHA2( )

if is in then y = SHA3( ) 56

Our protocol y 57 Our protocol y signed: Alice Pay Bobbi iff she reveals :

SHA2( ) = y Bobbi only knows the SHA2 pre-image of y if the encrypted value is a Sudoku solution 58 Our protocol y signed: Alice Pay Bobbi

iff she reveals : SHA2( ) = y signed: Bobbi Here is 59 Our protocol y signed: Alice

Pay Bobbi iff she reveals : SHA2( ) = y signed: Bobbi Here is 60 Our protocol y

signed: Alice Pay Bobbi iff she reveals : SHA2( ) = y signed: Bobbi + =

Here is 61 Our protocol y signed: Alice Pay Bobbi iff she reveals : SHA2( ) = y

signed: Bobbi + = Here is Alice learns the solution iff Bobbi gets paid62

Witness Indistinguishability is now enough! WI Proof if is in then y = SHA2( )

if is in then y = SHA3( ) 63

Much faster than subversion ZK Protocol completes in < 1 minute 64 Conclusions

Must be careful when applying cryptographic primitives in ways for which they were not designed. Subversion ZK reduces our reliance on SNARKs trusted setup Witness Indistinguishability is a weaker form of zero-knowledge,

and allows us to fix ZKCP at minimal cost 65 Questions? Paper: Code: https://eprint.iacr.org/2017/566

https://github.com/matteocam/pay-to-sudoku-attack https://github.com/matteocam/zkcsp-over-bitcoin @sgoldfed 66

Recently Viewed Presentations

  • Chicago - VA-FSC Internet

    Chicago - VA-FSC Internet

    the keys to sgl & fms a/o oct 08
  • Jane Schaffer&#x27;s Writing Across the Curriculum Review

    Jane Schaffer's Writing Across the Curriculum Review

    Jane Schaffer's Writing Strategy What all Subject Area Paragraphs have in Common Topic Sentence (TS) Concrete Detail (CD) Commentary (CM) Concluding Sentence (CS) Chunk Ratio TOPIC SENTENCE (TS) This sentence tells what the paragraph is about. It is based on...
  • Installation Best Practices

    Installation Best Practices

    3. The WX-CC411 is designed for single lane operation of drive-thru outlets; the WX-CC412 is designed for dual lane operation. A system compliant with the 1.9 GHz band DECT* standard is used so the voices of the store personnel and...
  • Kingdom Protista

    Kingdom Protista

    Arial Constantia Wingdings 2 Calibri Times New Roman Times protist 1_protist 2_protist 3_protist 4_protist Kingdom Protista What are protist? Protist Phylums Parts of the amoeba Protist Phylums Slide 6 Protist Phylums Slide 8 Protist Phylums Slide 10 Bellwork 1-27-2014 Plant...
  • The Need for New Antibiotics - The Pew Charitable Trusts

    The Need for New Antibiotics - The Pew Charitable Trusts

    The Need for New Antibiotics. July 28, 2015. Helen Boucher, MD, FACP, FIDSA. ... Most CRE in the U.S.—including the type in the 2011 NIH Clinical Center outbreak that sickened 18 and killed 11—produce Klebsiellapneumoniae ... exam notable for new...
  • Vendor Feedback - NYSED

    Vendor Feedback - NYSED

    Vendor Template Excel worksheet - track changes. NYSED should plan changes ahead of time and have fewer changes. Provide materials sooner for review prior to the meetings. Split meetings (HR & Student). More timely delivery of SIRS Manual with complete...
  • GOM 3 Future Plans Tony Dupont Earth Science

    GOM 3 Future Plans Tony Dupont Earth Science

    This will allow an extension of GOMsmart mapping while the more difficult local data delivery is worked out. User Conference 10/27/2016. Near-term GIS Data Update Changes. Main monthly updates moving from middle of month to start of month.
  • INTRODUCTION  Noninvasive technique to determine the molecular metabolites

    INTRODUCTION Noninvasive technique to determine the molecular metabolites

    From Larmor equation, ω = γ. B. precessionalfrequency of any proton is directly proportional to external magnetic field strength. Chemical Shift in Hz will be different at different magnetic field strengths. Hence, Chemical shift is expressed in terms of ....