Dr. Greg Bernstein

September 3rd, 2024

- Attacks on Credentials
- Public Key based Holder Binding
- Anonymous Holder Binding
- Commitments
- ZKPs of commitments
- Application: Signal Usernames
- Blind BBS Signing

* W3C “Invited Expert”, semi-retired, website: Grotto Networking

- Helping (co-editor) with: VC-DI, VC-DI-EdDSA, VC-DI-ECDSA, VC-DI-BBS specs
- Helping out with IETF BBS specs: BBS, Blind BBS, BBS per Verifier Id (pseudonym).
- Reference page Grotto Networking: Verifiable Credentials with links to demonstrations, presentations, and open source code.

Previous we talked about tracking

It’s ** evil** when done without our knowledge
and/or consent.

Using a verifiable credential without the holders consent or knowledge.

- Credential intercepted between issuer and holder, or holder and verifier
- Credential obtained via data breach at issuer, holder, or verifier

Illicit use of a credential with complicity of the credential’s holder, i.e., somebody other than the intended holder is using the credential with the holder’s knowledge.

- Account sharing (beyond contracted limits) – multi device and access, app and browser.
- Restriction evasions – age limits, qualification requirements, etc.
- Unlinkability can make this abuse easier => Per verifier ids (pseudonyms) helps mitigate

This is **extremely difficult** if the cryptography
implemented correctly and signing key kept secret. This is what
cryptographic papers are all about!

- Idea: Verifier comes up with a fresh cryptographic random value to have the holder incorporate into the credential.
- VC Data Integrity: challenge
- VC Data Integrity: Verify Proof

**Holder** has to get **issuer** involved
in providing a “fresh” credential to satisfy
**verifier**.

- Mechanism for guaranteeing additional data between
*holder*and*verifier*. - See BBS Presentation Header Usage
- See VC-DI-BBS: serialize derived proof for BBS presentation header with VCs.

**Issuer**<->**Holder**:`Sign(SK, PK, header, messages)`

and`Verify(PK, signature, header, messages)`

**Holder**<->**Verifier**:`ProofGen(PK, signature, header, ph, messages, disclosed_indexes)`

and`ProofVerify(PK, proof, header, ph, disclosed_messages, disclosed_indexes)`

*header*info must be shared with all parties,*ph*must be shared between**Holder**and**Verifier**.

Note issuer is **not** involved

Holder Binding based on Public Key Cryptography

**Holder**generates a public/private key pair for creating digital signatures, such as for ECDSA signatures.- The
*public key*is sent to the**issuer**for inclusion in the credential that is sent to the**holder**.

- When requesting the credential the
**verifier**also includes a message acting as a test. The**holder**signs this message with their private key and includes it with the credential sent to**verifier**. - The
**verifier**then validates the signature on the test message with the**holder’s**public key contained in the VC and it verifies the signed credential with the**issuer’s**public key.

**Pros**: Prevents anyone else from using the credential without the*holder’s*consent. As strong as the ability of the*holder*to keep their private key secret.**Cons**: Holder public key in VC is a unique identifer for the holder and allows**tracking**on every credential use.

- Put it someplace really safe, so know one can steal it
- Only use it in a really safe place, so know one and learn it
- This gets us into trusted computing such as Trusted Execution Environments, and TPMs

From Wikipedia: TPM, older TPM 1.1, new TPM 2.0 includes Elliptic Curve Cryptography

- Wikipedia: Secure Element “A secure element (SE) is a secure operating system (OS) in a tamper-resistant processor chip or secure component. It can protect assets (root of trust, sensitive data, keys, certificates, applications) against high-level software and hardware attacks.”
- Example hardware: EdgeLock® SE050: Plug and Trust Secure Element IoT oriented, T33TPHF2XSPI: TPM 2.0 device with an SPI interface.

Key secure element features used By Public Key Holder Binding:

- Key Pair Generation (public/private keys)
- Private Keys
**never**leave secure element (unless they are encrypted – AKA key wrapping) - Signature generation

- Security is more than the hardware root of trust. Adversaries will go around it or try to gain control of it. Though they cannot extract the private keys!
- How do apps get fair access to such devices without worrying about compromise?
- Hardware can be slow to evolve. Current ECC support is limited to P-256 and ECSDSA.

- The giving the verifier the holder’s public key allows the holder to
“prove” that they know a
**secret**, i.e., the private part of the key pair. - The public key is “bound” to the private key part of the key pair.
- But the public key is
*linked*to the secret key and doesn’t “hide” the holder

From Wikipedia: Commitment Scheme

A

commitment schemeis a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes arebinding.

A Graduate Course in Applied Cryptography, Dan Boneh and Victor Shoup, section 8.12

**Binding**: Once a commitment*c*is generated, Alice can only open it to a single message.” => No changing the message/value after the commitment has been made.**Hiding**: The commitment string*c*should reveal no information about the committed message” => this is true even if the message set is under the control of the adversary.

- Let
*m*be the value/message being committed - Choose
*r*randomly - Compute the commitment \(c = H(m ||
r)\) where
*H()*is a hash function - Send \((c, r)\)
- Verification on reveal of
*m*by checking \(c = H(m || r)\).

- Let
*g*and*h*be generators of the same (prime) group - Let
*x*be a number (message) to be committed - Let
*r*be a random number (blinding factor) - Compute the commitment as \(c = g^x h^r\)

- If the
**holder**reveals the*secret*they can be impersonated. - If the
**holder**uses the same*commitment*more than once they can be tracked - The
**holder**needs to prove to the**issuer**and**verifier**that they know the secret without revealing it.

From ZKProof Community Reference

A ZKP system is a specification of how a prover and verifier can interact for the prover to convince the verifier that the statement is true. The proof system must be

complete,soundandZK.

From ZKProof Community Reference

*Complete*: If the statement is true and both prover and verifier follow the protocol; the verifier will accept.*Sound*: If the statement is false, and the verifier follows the protocol; the verifier will not be convinced.*You can’t fool me!**Zero-knowledge*: If the statement is true and the prover follows the protocol; the verifier will not learn any confidential information from the interaction with the prover but the fact the statement is true.

From ZKProof Community Reference

The theory of ZKPs distinguishes between proofs and arguments, as related to the computational power of the prover and verifier.

Proofsneed to be sound even against computationally unbounded provers, whereasargumentsonly need to preserve soundness against computationally bounded provers.

Typically the term proof is used unless more precision is needed.

- Wikipedia: Zero-knowledge proof
- Wikipedia: Non-interactive zero-knowledge proof Also has a nice summary of schemes by year.
- zk-SNARK = zero-knowledge succinct non-interactive argument of knowledge
- zk-STARK = zero-knowledge scalable transparent argument of knowledge

- The BBS
*proof*provided by a holder to a verifier is a zero knowledge proof of knowledge of the BBS*signature*and the BBS*messages*.*Proof*can’t be linked to*signature*. - Each BBS
*proof*generated uses a set of cryptographic random numbers and hence different*proofs*cannot be linked to each other.

- BBS
*proofs*are based on a much older (20+ years) ZKP approach known as Sigma Protocols. - Very efficient in terms of space, creation and verification computation. Limited to relations among discrete logarithms.
- See
*Chapter 19: Identification and signatures from sigma protocols*of Boneh and Shoup online cryptography textbook - A recent proposal to standardize sigma protocols

Signal, secure, open source messaging app

Signal is the world’s most widely used truly private messaging app, and our cryptographic technologies provide extra layers of privacy beyond the Signal app itself. Since launching in 2013, the Signal Protocol—our end-to-end encryption technology—has become the de facto standard for private communication, protecting the contents of billions of conversations in WhatsApp, Google Messages, and many others. Signal also continues to invest in research and development in the pursuit of extending communications privacy.

- Keep your phone number private with Signal usernames, 20 Feb 2024, “Connect without sharing your phone number”
- Signal’s Usernames and Ristretto Hashes, April 10, 2024, “A look into Signal’s use of Ristretto hashes and zero-knowledge proofs for usernames”
- The user names are also kept secret from
**Signal**

From Signal’s Usernames and Ristretto Hashes

**Usernames**consist of a*nickname*(text), and a discriminator (a number) e.g.,`WindCadet.1117`

- A commitment to the username is computed as:
`C = sha512(nickname,discriminator)∗G1 + nickname∗G2 + discriminator∗G3`

. This is sent to signal by owner of username. - To connect with another user, you must know their username. From that you compute the commitment and compute a sigma protocol based ZKP that you know the username.

- Holder and verifier know \(g, h \in \mathbb{G}\) (generators)
- Holder knows: \(\alpha\) and \(\beta\), computes \(u = g^\alpha h^\beta\)
- Holder gives \(u\) to the verifier and wants to prove they know \(\alpha\) and \(\beta\)
- where \(\alpha\) is the “secret” and \(\beta\) is the “hiding factor”

- The prover selects random values \(\alpha_t\) and \(\beta_t\) and computes \(u_t = g^{\alpha_t} h^{\beta_t}\). This value is sent to the verifier.
- The verifier selects a random value \(c\) and sends it to the prover.
- The prover computes \(\alpha_z = \alpha_t + \alpha c\) and \(\beta_z = \beta_t + \beta c\) and sends them to the prover.
- The verifier checks if \(g^{\alpha_z}h^{\beta_z} = u_t \cdot u^c\). If so the proof is accepted.

See A Graduate Course in
Applied Cryptography for *special soundness* and
*HVZK*.

\[\begin{array}{rcl} g^{\alpha_z}h^{\beta_z} & = & g^{\alpha_t + \alpha c}h^{\beta_t + \beta c} \\ & = & g^{\alpha_t} h^{\beta_t} \cdot (g^\alpha h^\beta)^c \\ & = & u_t \cdot u^c \end{array}\]

From Wikipedia: Blind Signatures

In cryptography a blind signature is a form of digital signature in which the content of a message is disguised (blinded) before it is signed. The resulting blind signature can be publicly verified against the original, unblinded message in the manner of a regular digital signature.

From Wikipedia: Blind Signatures

Blind signatures are typically employed in privacy-related protocols where the signer and message author are different parties. Examples include cryptographic election systems and digital cash schemes.

From BBS Blind Signatures

The BBS digital signature scheme can be extended to support blind signatures functionality. In a blind signatures setting, the user (called the Prover in the context of the BBS scheme) will request a signature on a list of messages, without revealing those messages to the Signer (who can optionally also include messages of their choosing to the signature).

*BlindSign(SK, PK, commitment_with_proof, header, messages, signer_blind)*, Blind BBS signatures work with a commitment and its proof (from*holder*).*messages*are from the*issuer**BlindProofGen(PK,signature, header, ph, messages, committed_messages, disclosed_indexes, disclosed_commitment_indexes, secret_prover_blind, signer_blind)*

From Blind BBS Signatures

- Commitment formula (Holder computation):
`commit = Q_2 * secret_prover_blind + J_1 * msg_1 + ... + J_M * msg_M`

where`J_1`

to`J_M`

are generators for the holder’s secret (blind) messages - Signing Formula 1 (Issuer):
`B = P1 + Q_1 * domain + H_1 * msg_1 + ... + H_L * msg_L + commit`

where`commit`

comes from holder - Signing Formula 2 (Issuer):
`A = B * (1 / (SK + e))`

where`A`

and`e`

form the final signature.

- Hardware roots of trust and infrastructure currently support ECDSA type signatures
- Would like to be able to make existing signatures unlinkable
- How: Come up with a ZKP for ECDSA signatures. This isn’t easy, but
new techniques are emerging.
*Watch this space*