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