Zero-Knowledge Proofs (ZKP)

Privacy-Preserving Digital Identity

​

October 11, 2018

Clare Nelson, CISSP, CIPP/E

VP Business Development & Product Strategy, North America

Sedicii

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Why?

Raison d’Être for Zero-Knowledge Proofs

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Zero-Knowledge Proofs (ZKPs) Enhance Privacy

https://docs.google.com/document/d/1spgtYG8iXZ_NjUXdN8AEdKdGmaulE8r-mf7NsQ-_y4E/edit#

Personal

Privacy

Institutional

Integrity

Graphic: https://scattering-ashes.co.uk/ashes-help-and-advice/much-ash-cremation/

SSIMeetup.org

zk-STARKs Paper�Scalable, transparent, and post-quantum secure computational integrity (March 2018)

https://eprint.iacr.org/2018/046.pdf

Human dignity demands that personal information, like medical and forensic data, be hidden from the public.

​

But veils of secrecy designed to preserve privacy may also be abused to cover up lies and deceit by institutions entrusted with Data, unjustly harming citizens and eroding trust in central institutions.

​

​

​

Zero knowledge (ZK) proof systems are an ingenious cryptographic solution to this tension between the ideals of personal privacy and institutional integrity, enforcing the latter in a way that does not compromise the former.

​

– Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev

SSIMeetup.org

Scope

Digital Identity

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Scope

Out of Scope

In Scope

ZKP and Digital Identity

What Problems Are We Solving?

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Zero-Knowledge Proofs

�If your per­son­al data is nev­er col­lect­ed, it can­not be sto­len.

https://www.zurich.ibm.com/identity_mixer/

https://www.ted.com/talks/maria_dubovitskaya_take_back_control_of_your_personal_data, TED Talk

– Maria Dubovitskaya Cryptographer, Research Staff Member, IBM Zurich Research Laboratory, Ph.D. in cryptography and privacy from ETH Zurich

Graphic: https://www.youtube.com/watch?v=jp_QGwXsoXM

SSIMeetup.org

Motivations for ZKP �and Digital Identity

Digital Identity Risks

• Loss of privacy, control
• Data breaches
• Identity theft
• Identity fraud, crime
• Human, drug trafficking
• Terrorist funding
• Surveillance, Profiling
• Social engineering

https://zkproof.org/

https://gpsbydesign.org/

https://docs.google.com/document/d/1spgtYG8iXZ_NjUXdN8AEdKdGmaulE8r-mf7NsQ-_y4E/edit#

Graphic: https://gpsbydesign.org/

International Council on Global Privacy and Security, by Design

• We don’t need to give up personal privacy for public safety.
• We don't need to sacrifice privacy for data analytics.
• We can have both. We must have both.

TUPS

Ideal for Identification

ZKPs are the ideal solution to challenges in identification

• Users can prove identities
• No exchange of sensitive information
• Mitigates identity theft

​

– Sultan Almuhammadi

– Charles Neuman

University of Southern California, Los Angeles

(2005)

https://ieeexplore.ieee.org/document/1524082/

Graphic: https://www.equifax.com.au/personal/articles/what-identity-watch

SSIMeetup.org

Zero-Knowledge Proofs

Definition

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Zero-Knowledge Proofs

One of the most powerful tools cryptographers have ever devised

​

​

https://z.cash/team.html

https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

– Matthew Green

Professor at Johns Hopkins University

Co-founder of Zcash

SSIMeetup.org

Definition of Zero-Knowledge Proof�Proof System, not Geometry Proof

http://www0.cs.ucl.ac.uk/staff/J.Groth/ShortNIZK.pdf

http://www.austinmohr.com/work/files/zkp.pdf

Proof system, not a geometry proof

​

SSIMeetup.org

Definition of Zero-Knowledge Proof

Enable a Prover to convince a Verifier of the validity of a statement

• Yields nothing beyond validity of the statement
• Incorporates randomness
• Is probabilistic
• Does not provide absolute certainty

​

​

http://www0.cs.ucl.ac.uk/staff/J.Groth/ShortNIZK.pdf

http://www.austinmohr.com/work/files/zkp.pdf

Prover

Verifier

Statement

SSIMeetup.org

Interactive Zero-Knowledge Proof

​

Derived from http://blog.stratumn.com/zkp-hash-chains/

​

Non-Interactive ZKP

Transform multiple messages into one message, or string

SSIMeetup.org

ZKP Requirements

Completeness

• If statement is true, verifier will be convinced by prover

Soundness

• If statement is false, a cheating prover cannot convince verifier it is true
• Except with some small probability

Zero-Knowledge

• Verifier learns nothing beyond the statement’s validity

​

​

​

http://www0.cs.ucl.ac.uk/staff/J.Groth/ShortNIZK.pdf

http://www.austinmohr.com/work/files/zkp.pdf

http://www.wisdom.weizmann.ac.il/~oded/zk-tut02.html

Graphic: http://mentalfloss.com/article/64108/15-things-you-should-know-about-dogs-playing-poker

SSIMeetup.org

007 Wants to Read the News

Credit to Anna Lysyanskaya for the 007 metaphor

Graphic: http://www.007.com/characters/the-bonds/

SSIMeetup.org

007 Uses Subscription

007 Reveals Personal Data:

- Zip code when he looks up the weather

- Date of birth when he reads his horoscope

- More data when he browses the personal ads

Credit to Anna Lysyanskaya for the 007 metaphor

Graphic: http://www.007.com/characters/the-bonds/

SSIMeetup.org

Completeness: Telegraph Accepts Proof

Credit to Anna Lysyanskaya for the 007 metaphor

Graphic: http://www.007.com/characters/the-bonds/

Completeness

• Verifier is convinced of true statement

SSIMeetup.org

Soundness

Credit to Anna Lysyanskaya for the 007 metaphor

Graphic: https://en.wikipedia.org/wiki/M_(James_Bond)

SSIMeetup.org

ZKP Illustration

Interactive ZKP

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Zero-Knowledge Proof Illustration�Matthew Green

Telecom Company

• Cell towers
• Vertices
• Avoid signal overlap
• Use 1 of 3 signals

​

​

​

https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

SSIMeetup.org

Zero-Knowledge Proof Illustration�Matthew Green

3-Color Graph Problem

• Use colors to represent frequency bands
• Solve for 1,000 towers
• Hire Brain Consulting

​

https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

SSIMeetup.org

Zero-Knowledge Proof Illustration�Matthew Green

Proof of Solution

• Prove have solution without revealing it
• Hats hide the solution

​

​

​

https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

SSIMeetup.org

Zero-Knowledge Proof Illustration�Matthew Green

Proof of Solution

• Remove any two hats
• See vertices are different colors

​

https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

SSIMeetup.org

Zero-Knowledge Proof Illustration�Matthew Green

Repeat this process

• Clear previous solution
• (Add randomness)
• Solve again
• Telecom removes two hats

​

Accept or Reject

• Complete for preset number of rounds
• Telecom accepts or rejects

​

https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

SSIMeetup.org

ZKP Variants

Examples

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Examples of ZKP Variants

​

https://www.slideshare.net/arunta007/elliptic-curve-cryptography-and-zero-knowledge-proof-27914533?next_slideshow=1

https://www.youtube.com/watch?v=CKncw6mIMJQ&list=PLpr-xdpM8wG8DPozMmcbwBjFn15RtC75N

https://www.starkware.co/

http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf

https://eprint.iacr.org/2017/1066.pdf, Bulletproofs

https://thexvid.com/video/O8QA6Nvg8RI/zcash-genesis-block.html, trusted setup, live stream of Zcash launch

​

ZKP

NIZKP

zk-SNARK

zk-STARK

Designated Verifier

Lattice-Based

Interactive, multiple messages, need stable communication channel

Not interactive, one message

Need one-time, trusted setup to generate key at launch

No setup, working on memory issues, I or NI, post-quantum secure

No setup, 188 bytes, 10 ms in some cases, not post-quantum secure

Lattice-based cryptography, post-quantum secure, research

Graph Isomorphism

zk-STIK

Bulletproof

Interactive, compare graphs, efficient computation

Scalable Transparent Interactive Oracle of Proof (IOP) of Knowledge

DVNIZK, not just any entity can be verifier, verifier must know secret

Aurora

SSIMeetup.org

Trusted Setup�Zcash example

https://z.cash/technology/paramgen

https://z.cash/blog/the-design-of-the-ceremony/

https://thexvid.com/video/O8QA6Nvg8RI/zcash-genesis-block.html, trusted setup, live stream of Zcash launch

Multi-Party Computation (MPC) Ceremonies

Zcash Sprout (2016)

Six participants in the ceremony:

• Andrew Miller
• Peter Van Valkenburgh
• John Dobbertin (pseudonym)
• Zooko Wilcox
• Derek Hinch
• Peter Todd

Zcash Sapling (2017-2018)

• 87 Participants

Private transactions in Zcash rely on zk-SNARK public parameters for constructing and verifying zero-knowledge proofs

• Generating zk-SNARK public parameters is equivalent to generating a public/private key pair
• Keep public key
• Destroy private key
• If an attacker gets a copy of the private key, could
• Create counterfeit Zcash
• Not violate anyone else’s privacy
• Not steal other people’s Zcash

SSIMeetup.org

ZKP Examples

Digital Identity

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

ZKP Flexibility, Variety of Use Cases

• Range proofs
• Age range: 25-45 years old
• Set membership
• Citizen of European Union
• Comparison
• Do identity attributes or secrets match?
• Computational integrity

​

Logical combination of any of the above

Preserve Privacy

SSIMeetup.org

Graph Isomorphism ZKP�Paper by Manuel Blum, UC Berkeley, 1986

Prover

Verifier

(Graph Isomorphism Problem: Given two graphs with 𝑛 vertices each, decide whether they are isomorphic.)

1986: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.469.9048&rep=rep1&type=pdf

2006: https://www.cs.cmu.edu/~ryanw/crypto/lec6.pdf

2009: http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture18.pdf

2011: http://www.cs.haifa.ac.il/~orrd/IntroToCrypto/Spring11/Lecture9.pdf

https://kriptan.org/white-papers.html

http://gauss.ececs.uc.edu/Courses/c653/lectures/PDF/zero.pdf

​

Compare identity attributes

without transferring them

SSIMeetup.org

Graph Isomorphism ZKP��

Passport

Driver’s License

National ID

Relying

Party

Authoritative Sources

No personal data leaves mobile phone or authoritative source

1986: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.469.9048&rep=rep1&type=pdf

2006: https://www.cs.cmu.edu/~ryanw/crypto/lec6.pdf

2009: http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture18.pdf

2011: http://www.cs.haifa.ac.il/~orrd/IntroToCrypto/Spring11/Lecture9.pdf

https://kriptan.org/white-papers.html

http://gauss.ececs.uc.edu/Courses/c653/lectures/PDF/zero.pdf

https://medium.com/@kriptannetwork/we-did-it-before-it-was-cool-1a3b69627cc5

Verifier

zk-STARK Example�(Ben-Sasson, Bentov, Horesh, Riabzev)

https://eprint.iacr.org/2018/046.pdf

National Offender DNA Database

Presidential Candidate, Jaffa

Prove to public that Jaffa is not in offender database

Graphic: https://www.linkedin.com/in/jaffaedwards/, with permission May 25, 2018.

No reliance on any external trusted party

Designated Verifier

https://eprint.iacr.org/2017/1029.pdf

Designated-Verifier

Non-Interactive

Zero-Knowledge Proof of Knowledge (DVNIZK)

​

• Know verifier in advance
• Provides efficient, privacy-preserving authentication

​

Graphic: http://www.cs.technion.ac.il/images/events/2018/3031/fullsize.jpg

EUROCRYPT 2018

SSIMeetup.org

ZKP Identity-Related Landscape�Identity Verification, Authentication

Considerations

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

ZKP Considerations�Depends on Implementation or Use Cases

• Transparent
• Setup with no reliance on any third party
• No trapdoors
• Scalable
• Verify proofs exponentially faster than database size
• Succinct
• Universal
• Compliant with upcoming ZKP standards
• Interactive, non-interactive

​

• Support for IoT or cars
• Security (threat model)
• Code bugs, compromise during deployment, side channel attacks, tampering attacks, MiTM
• Manual review, proof sketches, re-use gadgets, emerging tools for formal verification, testing
• ZKP protocol breach, how detect breach?
• Third-party audit
• Monero audits: Kudelski Security $30K, Benedikt Bünz, QuarksLab
• Post-quantum secure

​

https://eprint.iacr.org/2018/046.pdf

https://forum.getmonero.org/22/completed-tasks/90007/bulletproofs-audit-fundraising

SSIMeetup.org

Timeline�

https://groups.csail.mit.edu/cis/pubs/shafi/1985-stoc.pdf

https://zkproof.org/

It is Still Early Days

ZKP Standards

​

https://zkproof.org/

https://zkproof.org/documents.html

*https://zkproof.org/zcon0_notes.pdf

I think you should be more

explicit here in step two

ZKProof.org

• Open initiative
• Industry, academia
• Framework for a formal standard of Zero-Knowledge Proofs
• Working drafts:
• Security
• Implementation
• Applications

Cartoonist: Sydney Harris

Source: https://www.art.com/products/p15063445373-sa-i6847848/sidney-harris-i-think-you-should-be-more-explicit-here-in-step-two-cartoon.htm

ZKP Standards

​

https://docs.google.com/document/d/1spgtYG8iXZ_NjUXdN8AEdKdGmaulE8r-mf7NsQ-_y4E/edit#heading=h.1irq6vg7ivr

ZKProof Standards Applications Track Proceedings

• Identity Framework, Protocol Description, Functionality
• Third-party anonymous and confidential attribute attestations through credential issuance by the issuer
• Confidentially proving claims using Zero-Knowledge Proofs through the presentation of proof of credential by the holder
• Verification of claims through Zero-Knowledge Proof verifications by the verifier
• Unlinkable credential revocation by the issuer

​

​

Plus:

• Credential transfer
• Authority delegation
• Trace auditability

Graphic: http://www.activistpost.com/2015/09/fbi-biometrics-programs-surveillance-database.html

​

ZKP Standards

​

https://zkproof.org/

https://zkproof.org/documents.html

*https://zkproof.org/zcon0_notes.pdf (June 2018)

ZKProof Workshop at Zcon0

• Legal questions
• If a robber shows a ZKP that they hold my coins, who legally owns them?*
• Trust

Graphic: https://www.pymnts.com/fraud-attack/2018/payment-details-north-korean-hack-cyberattack-security/

​

Trust

https://zkproof.org/zcon0.html

Graphic: http://www.criticbrain.com/articles/india-needs-to-bridge-gap-between-academia-and-industry

​

Technical people that trust ZKPs because they understand the math

Non-technical people who trust the technical people

How bridge this gap?

SSIMeetup.org

Resources

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

ZKP Resources

• ISO/IEC 9798-5
• Letter to NIST
• Code
• libSNARK C++ library
• libSTARK C++ library
• Bulletproofs using Ristretto, Rust library
• Succinct Computational Integrity and Privacy Research (SCIPR) Lab
• Stanford Applied Cryptography
• ZKP Science
• ZKP Standards Organization
• References: 4 backup slides at end of this presentation

https://zkp.science/docs/Letter-to-NIST-20160613-Advanced-Crypto.pdf

https://github.com/chain/ristretto-bulletproofs/

A Hands-On Tutorial for Zero-Knowledge Proofs: Part I-III

http://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge.html

​

September-October, 2018

SSIMeetup.org

Gratitude

ZKP Inventors, Pioneers

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

We Stand on the Shoulders of Giants

https://www.csail.mit.edu/user/733

https://people.csail.mit.edu/silvio/

https://cyberweek.tau.ac.il/2017/about/speakers/item/207-eli-ben-sasson

https://z.cash/team.html

���@Safe_SaaS���

Questions?

www.slideshare.net/eralcnoslen/presentations

Clare_Nelson @ ClearMark . biz

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Mathematics

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Bulletproof

​

https://blog.chain.com/faster-bulletproofs-with-ristretto-avx2-29450b4490cd

Range Proof Protocol

Backup Slides

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Known Vulnerabilities

An Example

SSIMeetup.org

https://creativecommons.org/licenses/by-sa/4.0/

Zero-Knowledge Range Proof (ZKRP)

Validate

• Person is 18-65 years old
• Without disclosing the age
• Person is in Europe
• Without disclosing the exact location

​

https://github.com/ing-bank/zkrangeproof

SSIMeetup.org

ZKRP Vulnerability

• Madars Virza
• “The publicly computable value y/t is roughly the same magnitude (in expectation) as w^2 * (m-a+1)(b-m+1). However, w^2 has fixed bit length (again, in expectation) and thus for a fixed range, this value leaks the magnitude of the committed value.”
• The proof is not zero knowledge
• Response: will find alternative ZKP

​

https://github.com/ing-bank/zkrangeproof

Graphic: https://www.pexels.com/photo/milkweed-bug-perching-on-pink-flower-in-close-up-photography-1085549/

Source: https://www.usenix.org/legacy/event/hotsec08/tech/full_papers/parno/parno_html/index.html

If you have a PC,

you may have touched

Zero-Knowledge Proof

(TPM 1.2)

Graphic: https://www.windowscentral.com/best-dell-laptop

SSIMeetup.org

References

• Attribute-based Credentials for Trust (ABC4Trust) Project, https://abc4trust.eu/ (2017).
• AU2EU Project, Authentication and Authorization for Entrusted Unions, http://www.au2eu.eu/ (2017).
• Baldimsti, Foteini; Lysanskaya, Anna. Anonymous Credentials Light. http://cs.brown.edu/~anna/papers/bl13a.pdf (2013).
• Ben Sasson, Eli; Chiesa, Alessandro; Garman, Christina, et al. Zerocash: Decentralized Anonymous Payments from Bitcoin, http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf (May 2014).
• Bitansky, Nir; Weizman, Zvika Brakerski; Kalai, Yael. 3-Message Zero Knowledge Against Human Ignorance, https://eprint.iacr.org/2016/213.pdf (September 2016).
• Blum, Manauel; De Santos, Alfredo; Micali, Silvio; Persiano, Giuseppe. Non-Interactive Zero-Knowledge and its Applications, https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Noninteractive_Zero-Knowkedge.pdf (1991).
• Brands, Stefan. Rethinking Public Key Infrastructures and Digital Certificates. The MIT Press, http://www.credentica.com/the_mit_pressbook.html (2000).
• Bunz, Benedikt; Bootle, Jonathan; Boneh, Dan; et al. Bulletproofs: Short Proofs for Confidential Transactions and More, https://eprint.iacr.org/2017/1066.pdf (2017).
• Camenisch, Jan and E. Van Herreweghen, Design and implementation of the IBM Idemix anonymous credential system, in Proceedings of the 9th ACM conference on Computer and communications security. ACM, 2002, pp. 21–30.
• Camenisch, Jan; Dubovitskaya, Maria; Enderlein, Robert; et al. Concepts and languages for privacy-preserving attribute-based authentication, https://pdfs.semanticscholar.org/82e2/4078c9ba9fcaf6177a80b8496779676af114.pdf (2013).

References

• Cutler, Becky. The Feasibility and Application of Using Zero-Knowledge Protocol for Authentication Systems, http://www.cs.tufts.edu/comp/116/archive/fall2015/bcutler.pdf (2015).
• Durcheva, Mariana. Zero Knowledge Proof Protocol Based on Graph Isomorphism Problem, http://www.jmest.org/wp-content/uploads/JMESTN42351827.pdf (2016).
• Fleischhacker, Nils; Goyal, Vuypil; Jain, Abhishek. On the Existence of Three Round Zero-Knowledge Proofs, https://eprint.iacr.org/2017/935.pdf (2017).
• Ganev, Valentin; Deml, Stefan. Introduction to zk-SNAKRs (Part 1), https://blog.decentriq.ch/zk-snarks-primer-part-one/ (2018).
• Gebeyehu, Worku; Ambaw, Lubak; Reddy, MA Eswar. Authenticating Grid Using Graph Isomorphism Based Zero Knowledge Proof, https://link.springer.com/chapter/10.1007/978-3-319-03107-1_2 (2014).
• Geraud, Rémi. Zero-Knowledge: More Secure than Passwords? https://blog.ingenico.com/posts/2017/07/zero-knowledge-proof-more-secure-than-passwords.html (July 25, 2017).
• Geers, Marjo; Comparing Privacy in eID Schemes, http://www.id-world-magazine.com/?p=923 (2017).
• Goldreich, Oded. Zero-Knowledge: a tutorial by Oded Goldreich, http://www.wisdom.weizmann.ac.il/~oded/zk-tut02.html has extensive reference list (2010).
• Goldreich, Oded; Yair, Oren. Definitions and Properties of Zero-Knowledge Proof Systems, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.2901 (19940.
• Goldwasser, Micali, Rackoff, The Knowledge Complexity of Interactive Proof-Systems, ACM 0-89791-151-2/85/005/02911 (1985).
• Green, Matthew. Zero Knowledge Proofs: An Illustrated Primer, https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ (November 2014).

​

​

References

• Groth, Jens. Short Pairing-Based Non-Interactive Zero-Knowledge Arguments, http://www0.cs.ucl.ac.uk/staff/J.Groth/ShortNIZK.pdf (2010).
• Groth, Jens; Lu, Steve. “A Non-Interactive Shuffle with Pairing Based Verifiability,” http://www0.cs.ucl.ac.uk/staff/J.Groth/AsiacryptPairingShuffle.pdf (2006).
• Groth, Jens; Ostrovsky, Rafail; Sahai, Amit. New Techniques for Non-interactive Zero-Knowledge, http://www0.cs.ucl.ac.uk/staff/J.Groth/NIZKJournal.pdf (2011).
• Guillou, Quisqater, “How to Explain Zero-Knowledge Protocols to Your Children,” http://pages.cs.wisc.edu/~mkowalcz/628.pdf (1998).
• Gupta, Anuj Das; Delight, Ankur. Zero-Knowledge Proof of Balance: A Friendly ZKP Demo, http://blog.stratumn.com/zero-knowledge-proof-of-balance-demo/ (June 2017).
• Hardjono, Thomas; Pentland, Alex “Sandy”; MIT Connection Science & Engineering; Core Identities for Future Transaction Systems, https://static1.squarespace.com/static/55f6b5e0e4b0974cf2b69410/t/57f7a1653e00be2c09eb96e7/1475846503159/Core-Identity-Whitepaper-v08.pdf (October 7, 2016). [TBD: check back, right now it is a DRAFT, do not cite]
• ISO/IEC Information technology — Security techniques — Entity authentication — Part 5: Mechanisms using zero-knowledge techniques, https://www.iso.org/standard/50456.html (2015).
• Johnstone, Mike; Why we need privacy-preserving authentication in the Facebook age, http://www.iaria.org/conferences2015/filesICSNC15/ICSNC_Keynote_v1.1a.pdf (November 2013).
• Kogta, Ronak. ZK-Snarks in English, https://www.slideshare.net/rixor786/zksnarks-in-english?qid=0e3be303-84fc-43d2-be96-6db2085a28ff&v=&b=&from_search=3 (July 2017).

References

• Lindell, Yehudi. Efficient Zero-Knowledge Proof, https://www.youtube.com/watch?v=Vahw28dValA, (2015).
• Lysyanskaya, Anna. How to Balance Privacy and Key Management in User Authentication, http://csrc.nist.gov/groups/ST/key_mgmt/documents/Sept2012_Presentations/LYSYANSKAYA_nist12.pdf (2012).
• Martin-Fernandez, Francisco; Caballero-Gil, Pino; Caballero-Gil, Candido. Authentication Based on Non-Interactive Zero-Knowledge Proofs for the Internet of Things. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4732108/ (January 2016).
• Mohr, Austin. A Survey of Zero-Knowledge Proofs with Applications to Cryptography, http://www.austinmohr.com/work/files/zkp.pdf.
• Montenegro, Jose.; Fischer, Michael; Lopez, Javier; et al. Secure Sealed-Bid Online Auctions Using Discreet Cryptographic Proof, http://www.sciencedirect.com/science/article/pii/S0895717711004535?via%3Dihub (June 2013).
• Nguyen, Quan; Rudoy, Mikhail; Srinivasan, Arjun. Two Factor Zero Knowledge Proof Authentication System, https://courses.csail.mit.edu/6.857/2014/files/16-nguyen-rudoy-srinivasan-two-factor-zkp.pdf (2014).
• Schukat, M; Flood, P. Zero-knowledge Proofs in M2M Communication, http://digital-library.theiet.org/content/conferences/10.1049/cp.2014.0697 (2014).
• Broadbent, Ann; Ji, Zhengfeng; Song, Fang. Zero-knowledge proof systems for QMA, https://arxiv.org/pdf/1604.02804.pdf (2016).
• Unruh, Dominique. Quantum Proofs of Knowledge, https://eprint.iacr.org/2010/212.pdf (February 2015).
• Wilcox, Zooko. Podcast, Zero Knowledge, The Future of Privacy. https://medium.com/blockchannel/episode-3-zero-knowledge-the-future-of-privacy-ea18479295f4 (February 21, 2017).
• Wu, Huixin; Wang, Feng. A Survey of Noninteractive Zero Knowledge Proof System and its Applications. https://www.hindawi.com/journals/tswj/2014/560484/ (May 2014).

​

​

​

Graph Isomorphism

https://en.wikipedia.org/wiki/Graph_isomorphism

G and H are isomorphic graphs

SSIMeetup.org

Graph Isomorphism ZKP (GIZKP)�Carnegie Mellon University, 2006

https://www.cs.cmu.edu/~ryanw/crypto/lec6.pdf

How does Prover prove to Verifier that an isomorphism exists?

​

Input:

2 isomorphic graphs G, H on n nodes each. Prover knows isomorphism f. A security parameter k (positive integer).

​

Output:

A zero-knowledge protocol that proves P knows f. Prover gives no info to V˜ P˜ can cheat (successfully) with probability ≤ 1/2 n .

​

Protocol:

Repeat k times.

​

Prover: Privately take G and randomly permute vertices to get a graph F.

​

Prover: Publicly present F to Verifier (G and H are public from the beginning).

​

Verifier: Toss a coin, and ask Prover to show that G ∼= F if heads, or H ∼= F if tails.

SSIMeetup.org

Graph Isomorphism ZKP (GIZKP)�Cornell University, 2009

http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture18.pdf

SSIMeetup.org

EUROCRYPT 2018

Efficient Designated-Verifier Non-Interactive Zero-Knowledge Proofs of Knowledge

• Pyrros Chaidos (University of Athens), Geoffroy Couteau (Karlsruhe Institute of Technology) 

Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs

• Dan Boneh (Stanford), Yuval Ishai (Technion and UCLA), Amit Sahai (UCLA), David J. Wu (Stanford) 

​

​

​

https://eurocrypt.iacr.org/2018/acceptedpapers.html

​

On the Existence of Three Round Zero-Knowledge Proofs

• Nils Fleischhacker (Johns Hopkins University and Carnegie Mellon University), Vipul Goyal (Carnegie Mellon University), Abhishek Jain (Johns Hopkins University) 

An Efficiency-Preserving Transformation from Honest-Verifier Statistical Zero-Knowledge to Statistical Zero-Knowledge

• Pavel Hubáček (Charles University in Prague), Alon Rosen (IDC Herzliya), Margarita Vald (Tel-Aviv University)

Partially Splitting Rings for Faster Lattice-Based Zero-Knowledge Proofs

• Vadim Lyubashevsky (IBM Research - Zurich), Gregor Seiler (IBM Research - Zurich)

​

​

​

SSIMeetup.org

Schnorr NIZK (IETF Draft)

The Schnorr NIZK proof is obtained from the interactive Schnorr identification scheme through a Fiat-Shamir transformation

​

• This transformation involves using a secure cryptographic hash function to issue the challenge instead �

​

​

​

https://tools.ietf.org/html/draft-hao-schnorr-01

​

Graphic: https://www.bswllc.com/resources-articles-preparing-for-the-2013-coso-internal-framework

SSIMeetup.org

Zero-Knowledge Proof, Formal Definition

http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture18.pdf

​

An interactive proof system (P, V) for a language L is zero-knowledge if for any PPT verifier V^∗ there exists an expected PPT simulator S such that

​

∀ x ∈ L, z ∈ {0, 1} ^∗, View_V∗ [P(x) ↔ V^∗ (x, z)] = S(x, z)

​

​

As usual, P has unlimited computation power (in practice, P must be a randomized TM).

​

Intuitively, the definition states that an interactive proof system (P, V) is zero-knowledge if for any verifier V^∗ there exists an efficient simulator S that can essentially produce a transcript of the conversation that would have taken place between P and V^∗ on any given input.

SSIMeetup.org

ZKPOK

I can’t tell you my secret,�but I can prove to you�that I know the secret

Source: J. Chou, SC700 A2 Internet Information Protocols (2001)

Graphic: http://www.flowmarq.com/single-post/2015/05/18/IDENTITY-Clarifying-Motivations

SSIMeetup.org

You can have security without privacy,

but you can’t have privacy without security.

​

— Carolyn Herzog, EVP and General Counsel, ARM

​

https://www.symantec.com/connect/blogs/you-can-t-have-privacy-without-security

https://www.microsoft.com/en-us/research/research-area/security-privacy-cryptography/

SSIMeetup.org

ZKP Variations

• GMR defined knowledge as the computational power of a party
• Differentiates “knowledge” from “information”
• Knowledge is coupled with computational power

​

https://eprint.iacr.org/2010/150.pdf

• One-Round ZKP
• Pairing-Based Non-Interactive Arguments
• Perfect ZKPs
• Private-coin ZKP
• Public-coin ZKP
• Scalable Transparent Argument of Knowledge (STARK)
• Scalable Transparent IOP of Knowledge (STIK)
• Schnorr Non-Interactive Zero-Knowledge Proof
• Statistical Zero-Knowledge
• Succinct Interactive Proof (SCIP)
• Succinct Non-Interactive Argument (SNARG)
• Succinct Non-Interactive Argument of Knowledge (SNARK)
• Super-Perfect ZKP
• Symbolic Zero-Knowledge Proof
• Three-Round ZKP
• ZK Arguments 
• ZKP Based on Graph Isomorphism
• ZKP of Proximity (ZKPP)�

​

​

https://ieeexplore.ieee.org/document/1524082/

https://eprint.iacr.org/2018/167.pdf

https://eurocrypt.iacr.org/2018/acceptedpapers.html

http://www0.cs.ucl.ac.uk/staff/J.Groth/NIZKJournal.pdf

https://eprint.iacr.org/2017/114.pdf

http://www.jmest.org/wp-content/uploads/JMESTN42351827.pdf

Examples: ZKP Variations, Terminology

SSIMeetup.org

Non-Interactive Zero-Knowledge Proof

​

http://slideplayer.com/slide/2891428/

zk-SNARK Proof

SSIMeetup.org

ISO/IEC 9798-5:2009

Compliance with ISO/IEC 9798-5 may involve the use of the following patents and their counterparts in other countries.

https://www.iso.org/standard/50456.html

SSIMeetup.org

Attack Resilience (From Academia) �

http://repository.ust.hk/ir/bitstream/1783.1-6277/1/pseudo.pdf

SSIMeetup.org

ZKP Challenges

https://www.slideshare.net/arunta007/elliptic-curve-cryptography-and-zero-knowledge-proof-27914533?next_slideshow=1

https://www.starkware.co/#jobs

• Requires expertise and experience
• PhD mathematics or cryptography
• Algebraic cryptography, high-performance computation in finite fields
• Applications of modern algebra to algorithms and computer science
• Correct usage
• Security, threat model
• Audited code, formal verification
• Known bugs and vulnerabilities

​

Graphic: http://www.digifotopro.nl/content/beklimming-mount-everest-360-graden-vastgelegd

SSIMeetup.org