Internet-Draft spartan March 2022
Setty Expires 27 September 2022 [Page]
Workgroup:
Crypto Forum
Internet-Draft:
draft-setty-cfrg-spartan-incubation-latest
Published:
Intended Status:
Informational
Expires:
Author:
S. Setty
Microsoft Research

Spartan High-speed zkSNARKs (incubation)

Abstract

Spartan is a high-speed zero-knowledge proof system, a cryptographic primitive that enables a prover to prove a mathematical statement to a verifier without revealing anything besides the validity of the statement.

This work shows how to leverage zkSNARKs to add selective disclosure and unlinkability to verifiable credentials without any trusted setup.

About This Document

This note is to be removed before publishing as an RFC.

The latest revision of this draft can be found at https://decentralized-identity.github.io/spartan_zkSNARK_signatures/draft-setty-cfrg-spartan-incubation.html. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-setty-cfrg-spartan-incubation/.

Discussion of this document takes place on the Crypto Forum Research Group mailing list (mailto:[email protected]), which is archived at https://mailarchive.ietf.org/arch/search/?email_list=cfrg.

Source for this draft and an issue tracker can be found at https://github.com/decentralized-identity/spartan_zkSNARK_signatures.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on 27 September 2022.

Table of Contents

1. Introduction

References: * Official Paper: https://eprint.iacr.org/2019/550.pdf * Open Source Implementation: https://github.com/Microsoft/Spartan * Draft Repo: https://github.com/decentralized-identity/spartan_zkSNARK_signatures

In an identity system, an issuer (e.g., DMV using Azure AD) issues a credential to a credential holder by digitally signing a set of attribute-value pairs (e.g., name, address, date of birth, photograph, etc.). The credential holder stores such credentials in a wallet app on their mobile devices and can then prove to verifiers (or relying parties) that they hold certain attribute-value pairs issued by a particular issuer. Such credentials are referred to as verifiable credentials, and there is now an emerging W3C standard for issuing such user-controlled, cryptographically verifiable credentials.

Two basic and intuitive privacy guarantees in this context are: (1) Selective Disclosure and (2) Unlinkability. Selective Disclosure means that a credential holder can choose to disclose only a subset of the attribute-value pairs in the credential to a verifier and the verifier learns nothing about the remaining attribute-value pairs in the holder's credential. For example, if a credential such as a driver's license includes name, date of birth, full address, and a photograph, the subject can choose to selectively disclose to the verifier their name and ZIP code but nothing else, the name and their state but nothing else, or their name and date of birth but nothing else. Unlinkability means that if the same credential holder presents their credential at two different verifiers, the verifiers--even if they collude--cannot correlate that activity back to the same holder (unless the credential holder reveals uniquely identifying information).

1.1. zkSNARK Signatures

We describe how to add selective disclosure and unlinkability to verifiable credentials issued with standard digital signatures over standardized curves. When a credential holder wishes to provably disclose a subset of attribute-value pairs in their credential to a verifier, the credential holder produces a derived credential containing only the disclosed attribute-value pairs. Such derived credentials are then presented to the verifier who can verify the validity of the credential.

A challenging aspect here is: how does a credential holder produce such derived credentials, with selective disclosure and unlinkability guarantees? Note that the credential holders cannot "call the issuer" for any interaction with verifiers, as this poses additional privacy threats. Furthermore, credential holders should not be able to derive fake credentials. Standard signature schemes such as ECDSA or EdDSA do not support such functionality.

We address both requirements with zkSNARKs, a cryptographic primitive that allows a prover to prove an arbitrary mathematical statement to a verifier. In particular, we plan to leverage Spartan, a high-speed zkSNARK that uses only standardized cryptography and offers state-of-the-art performance. Spartan also does not require any trusted setup (e.g., creating a structured reference string).

An attractive aspect of our approach is that we can retrofit the aforementioned privacy properties to existing verifiable credentials issued with standard signature schemes (e.g., ECDSA over secp256k1 or P-256), with minimal resource overheads and engineering effort. Specifically, an issuer issues credentials as before with a standard signature scheme (e.g., ECDSA) so it is unmodified and incurs no overheads to support privacy features. Deriving a derived credential and verification of a derived credential happens on the credential holder and the verifier side, respectively. Specifically, the credential presentation protocol flow is as follows: * The issuer digitally signs a set of attribute-value pairs using its private key and sends ( to the holder, where is a digital signature (e.g., ECDSA signature). * The holder with produces a derived credential where is the disclosed subset of attribute-value pairs and is a proof of knowledge of such that: (i) is valid under the issuer's public key for , and (ii) is a subset of . * The verifier with knowledge of the issuer's public key verifies the derived credential .

2. Conventions and Definitions

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

3. Security Considerations

TODO Security

4. IANA Considerations

This document has no IANA actions.

5. Normative References

[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/rfc/rfc2119>.
[RFC8174]
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfc-editor.org/rfc/rfc8174>.

Acknowledgments

TODO acknowledge.

Author's Address

Srinath Setty
Microsoft Research