Dr. Greg Bernstein

May 23rd, 2023

- Signature Review
- VCs and Signatures
- BBS Signatures
- Selective Disclosure
- Anonymity and Unlinkability

My website: Grotto Networking

- Dr. Greg M. Bernstein (BS, MS, PhD UC Berkeley) - part time consultant, teacher, implementor
- Spent the pandemic teaching cybersecurity and web programming. Big
interest in
*privacy*and*security* - Lot’s of networking standards work at IETF, OIF, ITU-T, etc.
- Formerly R&D manager at big telecoms and startup

- A Graduate Course in Applied Cryptography (B&S), Dan Boneh and Victor Shoup, version 0.6 (latest version, Jan. 2023).
- K. C. Garillot François and V. Nikolaenko, Taming the many EdDSAs.
- RFC8032: Edwards-Curve Digital Signature Algorithm (EdDSA)

From B&S Chapter 13

A signature scheme \(S = (G, S, V)\)
is a triple of efficient algorithms, \(G\), \(S\)
and \(V\), where \(G\) is called a *key generation
algorithm*, \(S\) is called a
*signing algorithm*, and \(V\)
is called a *verification algorithm*. Algorithm \(S\) is used to generate signatures and
algorithm \(V\) is used to verify
signatures.

From B&S Chapter 13

We give the adversary the power to mount a *chosen message
attack*, namely the attacker can request the signature on any
message of his choice. Even with such power, the adversary should not be
able to create an **existential forgery**, namely the
attacker cannot output a valid message-signature pair \((m, \sigma )\) some new message \(m\).

This is called EUF-CMA (existential unforgeability under chosen message attacks)

- SUF-CMA (strong unforgeability under chosen message attacks) “but
also cannot find a new signature on an old message” EdDSA can be but
ECDSA is
**not**SUF-CMA see B&S chapter 19. - Binding signature (BS) “A binding signature makes it impossible for the signer to claim later that it has signed a different message”

- Strongly Binding signature (SBS) “require(s) a signature to not only be binding to the message but also be binding to the public key.”

- EdDSA Cryptosuite v2022 Featuring EdDSA style signatures using curve Ed25519. In latest FIPS 186-5 (February 2023)
- ECDSA Cryptosuite v2019 Based on widely deployed ECDSA algorithm
- BBS Cryptosuite v2023 Getting started…

- Key Generation:
*sk*is a random 256 bit (**32 bytes**),*pk*is a group element encoded into 256 bits (**32 bytes**) - Given message
*M*signer produces signature*(R, S)*where R is an encoded group element,*S*is a “scalar” canonically encoded into 256 bits. Total length of the signature is**64 bytes**! - EdDSA with curve Ed25519 is efficient, fast, and secure (when properly implemented)

From draft EdDSA Cryptosuite v2022

- What to protect?
- Unsigned document
- Options that related to cryptographic parameters!

- Additional Tools
- JSON canonicalization algorithm (RDF or JCS)
- Cryptographic Hash (SHA-256)

```
{
"@context": [
"https://www.w3.org/ns/credentials/v2",
"https://www.w3.org/ns/credentials/examples/v2"
],
"id": "urn:uuid:58172aac-d8ba-11ed-83dd-0b3aef56cc33",
"type": ["VerifiableCredential", "AlumniCredential"],
"name": "Alumni Credential",
"description": "A minimum viable example of an Alumni Credential.",
"issuer": "https://vc.example/issuers/5678",
"validFrom": "2023-01-01T00:00:00Z",
"credentialSubject": {
"id": "did:example:abcdefgh",
"alumniOf": "The School of Examples"
}
}
```

```
{
"type": "DataIntegrityProof",
"cryptosuite": "eddsa-2022",
"created": "2023-02-24T23:36:38Z",
"verificationMethod": "https://vc.example/issuers/5678#z6MkrJVnaZkeFzdQyMZu1cgjg7k1pZZ6pvBQ7XJPt4swbTQ2",
"proofPurpose": "assertionMethod",
"@context": [
"https://www.w3.org/ns/credentials/v2",
"https://www.w3.org/ns/credentials/examples/v2"
]
}
```

- Canonize unsigned VC
- Canonize configuration options
- combine cryptographic hashes of canonized configuration options and unsigned VC
- create signature with combined hash as message
- created signed VC with unsigned VC, options, and signature

```
{
"@context": [
"https://www.w3.org/ns/credentials/v2",
"https://www.w3.org/ns/credentials/examples/v2"
],
"id": "urn:uuid:58172aac-d8ba-11ed-83dd-0b3aef56cc33",
"type": [
"VerifiableCredential",
"AlumniCredential"
],
"name": "Alumni Credential",
"description": "An minimum viable example of an Alumni Credential.",
"issuer": "https://vc.example/issuers/5678",
"validFrom": "2023-01-01T00:00:00Z",
"credentialSubject": {
"id": "did:example:abcdefgh",
"alumniOf": "The School of Examples"
},
"proof": {
"type": "DataIntegrityProof",
"cryptosuite": "eddsa-2022",
"created": "2023-02-24T23:36:38Z",
"verificationMethod": "https://vc.example/issuers/5678#z6MkrJVnaZkeFzdQyMZu1cgjg7k1pZZ6pvBQ7XJPt4swbTQ2",
"proofPurpose": "assertionMethod",
"proofValue": "zytcLynZ8bVqCNnfw9zrGQonkmMgwRVsNiQs5WFUnUxpQsUzjT1tG27Tz9A7x8M4rGgA3nzqdQi3xjvAVhet1vFP"
}
}
```

The name

BBSis derived from the authors of the original academic work of Dan Boneh, Xavier Boyen, and Hovav Shacham, where the scheme was first described.

- The BBS Signature Scheme (DIF/IETF draft)
- Paper 2023/275 Revisiting BBS Signatures, Stefano Tessaro and Chenzhi Zhu, also EUROCRYPT 2023. Optimizations and additional security proofs.
- Paper 2016/663 Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited, Jan Camenisch, Manu Drijvers, and Anja Lehmann. Sections 4.3-4.5 are basis for current IETF draft.

In browser JavaScript only BBS Demo

- Uses Hex representation for all fields except messages with are UTF-8 text
- Uses JSON to hold information at various stages. These are not VCs or VPs.
- Simple list of
*BBS messages*for selective disclosure, content is arbitrary

From DIF/IETF draft

**SUF-CMA**: Strong unforgeability under chosen message attacks.**Selective Disclosure**: The scheme allows a signer to sign multiple messages and produce a single -constant size- output signature.

From DIF/IETF draft

**Unlinkable Proofs**: The proofs generated by the scheme are known as zero-knowledge, proofs-of-knowledge of the signature**Proof of Possession**: The proofs generated by the scheme prove to a verifier that the party who generated the proof (holder/prover) was in possession of a signature without revealing it.

- Keys: sk is a random “scalar” encoded in
*32 bytes*, pk is an encoded G2 group element in**96 bytes** - Signature length on for
*L*messages:*(A, e, s)*encoded G1 group element 48 bytes,*e*and*s*are 32 byte scalars for a total of**112 bytes**. New optimization and security results requires just*(A, e)*for**80 bytes**. Just 16 bytes longer than an EdDSA Ed25519 signature.

From Grotto BBS demo, not a VC or mDL…

```
{
"publicKey": "b65b7cbff4e81b723456a13936b6bcc77a078bf6291765f3ae13170072249dd7daa7ec1bd82b818ab60198030b45b8fa159c155fc3841a9ad4045e37161c9f0d9a4f361b93cfdc67d365f3be1a398e56aa173d7a55e01b4a8dd2494e7fb90da7",
"header": "11223344556677889900aabbccddeeff",
"messages": [
"FirstName: Sequoia",
"LastName: Sempervirens",
"Address: Jedediah Smith Redwoods State Park, California",
"Date of Birth: 1200/03/21",
"Height: 296 feet",
"Eyes: None",
"Hair: Brown bark, green needles",
"Picture: Encoded photo",
"License Class: None, Trees can't drive"
],
"signature": "94bb93062e05bc702d0ab222b861fd0311533d6dcbcad4050e45dd2392de951a912915af08bd87b2284807432245f9960e1f59680a59cd9fae490dee659d63fd3922a728e2ba3ee33db6bcc806ec2cea3d7264489a42ca09deeac7ca88b1811c2158b51d81560832daf6a0000037a87a"
}
```

**Issuer**: Signs VC as part of issuing process**Holder**: Verifies signed VC**Holder**: Selects what to disclose from VC (which messages in BBS terminology), constructs VP based on these choices**Verifier**: Verifies VP with selectively disclose information.

Let *M* be number of messages, *U* number of
undisclosed messages

- Lots of individually signed
*messages*: Cost: A signature per message, i.e.,*M*x*(Signature Size)* - Merkel (hash) Trees: Single signature for tree. Presentation cost
general overhead plus a hash for each undisclosed message, i.e.,
*U*x*(Hash size)* - BBS: Fixed signature size, Presentation cost: general overhead and a
scalar (32 bytes) per undisclosed message, i.e.,
*U*x*(32 bytes)*

```
{
"pk": "b65b7cbff4e81b723456a13936b6bcc77a078bf6291765f3ae13170072249dd7daa7ec1bd82b818ab60198030b45b8fa159c155fc3841a9ad4045e37161c9f0d9a4f361b93cfdc67d365f3be1a398e56aa173d7a55e01b4a8dd2494e7fb90da7",
"header": "11223344556677889900aabbccddeeff",
"ph": "",
"disclosedIndexes": [
0,
3,
7
],
"disclosedMsgs": [
"FirstName: Sequoia",
"Date of Birth: 1200/03/21",
"Picture: Encoded photo"
],
"proof": "a6089a46f59e005a11885fe29e8e67679d6545b42e1126858ef2a3b6cbd5b2f1de1577194ce57077bfb1d555476e10a8afb64592f6e37e2e9f2f99422c7b6466cc49499f2e0a7d670a19a0e3765e6522b95376c06a776965a81e29238c3c9350b0e367daa23010490da97c2002027b43c6f7ba181f601eb4462964883c08e4ffcb9424180aaadc103f89c923d88b88c4015ff3d28a64887a88ae0944d3aaf1ed371173f068b3d0b79a5177c287b1c64271807cc03d331a3b18d3491898a1be13c6404cae9acbacd7ce635a4d7a6b520b1a33fb1ca1dbcbc90158269b2e2a58714fc97c892a5ebd839fb22f307d29bdf822b21bf1a906b428ee75f0dc408ebbb4085e6f4e057bb3b1f783e636e0de07eb542e2d1054e89b0451148bf703a9e59cce2e49e000d8aa1448acd514393d7f661b028cdbaec607bef03384028f6a47907c0d1e2b16c03e37c73b75b2d6d85a670186be482b4abbc2cecc90d29b16c11a12eeededc68fc16e0729e97a14d44a5e6cedca243afad6024d46f7fa738e635ff3e93c5502ad3b7772c1f0bc86d5fa930a34ea0771bddb3a9da5e308613b468421de3dc6789ae5c014915199d978082615a81214f0efb12fc824b3a1b5c9ab2ba7b62a4e44ef21eabe9fbf2803d13d360730c49c8e5c67617b739593e0824fc0f2e626f30e88d365007df318571b467b"
}
```

**Important**: We have a terminology collision! Both BBS
signatures and verifiable credentials use the terms *proof* and
*signature*. However these can have very different meanings,
hence we will be verbose and use terms like “BBS signature”, “BBS
proof”, and “VC data integrity proof”.

- The
*issuer*issues a VC to the holder that is signed via a**BBS signature**to the*holder*. This VC is signed with the issuers BBS*secret key*and attached to the VC with a “VC data integrity proof” - The
*holder*creates a VP containing the appropriate subset of the VC and adds a “VC data integrity proof” to the VP based on a**BBS proof**which the*holder*derives from the issued VC, the*BBS signature*and issuer’s*public key*.

- The
*verifier*can verify that the subset of information contained in the VP has not been modified by validating the*BBS proof*contained in the VP against the*issuer*’s*public key*. Note no holder keys are involved.

BBS has *sign* and *verify*

`signature = Sign(Secret_Key, Public_key, header, messages)`

used by*issuer*`result = Verify(Public, signature, header, messages)`

is used when the*holder*verifies the VC it receives from the*issuer*.

but BBS is more than *sign* and
*verify*

`bbs_proof = ProofGen(Public_key, signature, header, ph, messages, disclosed_indexes)`

is used when the*holder*want to prepare a VP that selectively discloses original VC information.`result = ProofVerify(Public_key, bbs_proof, header, ph, disclosed_messages, disclosed_indexes)`

is used by the*verifier*to validate the VP, against the original issuers public key.

- An issuer signs a VC by including a cryptographic signature. By their security properties these tend to be “unique”
- When a holder creates a VP that includes the signed VC the cryptographic signature is included.
- If a holder sends this VP to multiple verifiers and those verifiers
share data, i.e., collude, then the holder’s activities can be
**tracked**or**worse**.

- Cover your Tracks Try out their tool to see how unique your computer/browser combination is
- Mozilla: What is fingerprinting
- NPM: FingerprintJS 300K downloads a week…

From DIF/IETF draft

**Unlinkable Proofs**: The proofs generated by the scheme are known as zero-knowledge, proofs-of-knowledge of the signature**Proof of Possession**: The proofs generated by the scheme prove to a verifier that the party who generated the proof (holder/prover) was in possession of a signature without revealing it.

But what does this mean?

- A tree goes into a bar and needs to prove it lives in a local state park in order to get a very large glass of water.
- It then goes to another local bar for another very large glass of water.
- It doesn’t want to be tracked across bars or have its water consuming habits tracked.
- Solution: Generate a separate
**BBS proof**for each bar it visits

BBS Proof presented at first bar

```
{
"pk": "b65b7cbff4e81b723456a13936b6bcc77a078bf6291765f3ae13170072249dd7daa7ec1bd82b818ab60198030b45b8fa159c155fc3841a9ad4045e37161c9f0d9a4f361b93cfdc67d365f3be1a398e56aa173d7a55e01b4a8dd2494e7fb90da7",
"header": "11223344556677889900aabbccddeeff",
"ph": "",
"disclosedIndexes": [
2
],
"disclosedMsgs": [
"Address: Jedediah Smith Redwoods State Park, California"
],
"proof": "a312e2476de36c0fc2a815ebd9236c6cc1831a3fcdb3d2cdaf4d3ff325259a4d36e910ea06b75f6708f035924c6488da989a57fbbcfe187e78d2550f23eabb577a3c2457147cbf68f82f16c75ba9b52ea0e36d264a7ac3304fb8892ad9c4c33ea2505ffb8c9aaa203094bf2bd917c1c18c62fd3b7c7459616dced8836d3d5f608201c7d0b7a80daf8205d2451bd33d5b06fab9f3dda846137539b4ae53d9dbaf699bb3f43f9ab38d936e8f4d035128af0e19867e3edcfeb58175d44ac6a4f471b2bca58d9b4de80291b2809658a804f570e9d7e0aa55bf157d138cdd6a82b7364db5443e1fa5fc9d52f404097d85889755761f48befdcb5d2d581d2911808e9d6b4b213b7eeb4c38b878195f13b004ba1179b5a7f88cc39aeca21ab781a5107c4e69b29db00876274df71d4460f09dfd3df287bb384c6efb9c6fd3cbb7f0f0d3545b07c5a039686ac1a10b7eb0cf52f46e28d38f970dccf6f4d039b78a11f42349a52d06397a10ed80ac567ee29f21e6022200ca71c088cf7bada1878150cd776716f66495ff0337e72572a325329539466cc3d1745034798b0a09e1c62090f3be3d4a22b518aff620a484d0bd5461f95c5ca7e5a8f50ddb96e29dda0192def462c611bccb9465c3457e1b69bce4b6676e190be338e030da06b481014271828eee6648b40626f4b293980e4267b22c39121236376dc2e786f92ba760d21f174068028e87c29e7167a5023295a4af6a8141ba8c5de8dd25e2f1b8b7fdfa72d60324c6c81e2ca3951dc761b75e10d05646"
}
```

BBS Proof presented at second bar

```
{
"pk": "b65b7cbff4e81b723456a13936b6bcc77a078bf6291765f3ae13170072249dd7daa7ec1bd82b818ab60198030b45b8fa159c155fc3841a9ad4045e37161c9f0d9a4f361b93cfdc67d365f3be1a398e56aa173d7a55e01b4a8dd2494e7fb90da7",
"header": "11223344556677889900aabbccddeeff",
"ph": "",
"disclosedIndexes": [
2
],
"disclosedMsgs": [
"Address: Jedediah Smith Redwoods State Park, California"
],
"proof": "8175e24b57337bd8abed395c0d2440efe71e55cf06fbb1ead5d4e8589e2a5dc295688f561851d5f2e169a417c2ddde32b7801550cb442227db1503f1dfdf803125c9f10aae16b69ec58ad33a0ff9acc18405f0f24640e5381a2abadefcc6fb6e952bbd8ec908a60c28dc5913a25a586ee9b49f9a8fec0eff51dafc283ea44d07dd60292e6ef5711a202ef055fa7a203f727bdf0087f1b91d96a91e07ca417eed8cc03f00a1de1b013ceff998d9a6ff55559105abc53a80b30d68eb644150602f55cfb3de0bc949d9d3c85732df6d5d1535798679d0d29895bfe1ef58d9aa63f0fc160394a5739c65602d9bb21fffa4ed27408be6c0beb579b997eb0426d85fc3c7db1961992e85df1fd35cd421dc007b130d9f41568b7d9984689c883ea9a8b6e50b95c8cfd1bee71f2ad1c08cb2134b5337794d6a387aefc44af1929e456d857197d02acf1caddbd751380a9ac5a00c10c6df911dd00bc27e4d68dc6af5023e83e2e45f80b416b98d7d46ea967835c3155f3b6a22fcb8534a23b15c16805ae4adb98bfd17bc096a9ad0636dbdb844344c862d44b5d8d55d4fa0be73623ce5f1ea558cdb1e8dc8f4b958a8bda851115802a3b12ce54177b236dd98d819a2dbeafa1a04e0214fbb3bccb5edf94e0c9cfa575334bf48ffa11755435bc40945fc46e862f67c8f5ee6247f9f9a3c57dbd4122551605f3db005764db0717e2f8365a8458141c94549db43c8034798532817582507b679e7fc724518e281443a0f1d59c9d030df6e8ef65cd33093919ae1a018"
}
```

- The values (cryptographic byte array) contained in the
*BBS proofs*are unlinkable. In particular they appear essentially random - Unlinkable proofs do not prevent correlation on disclosed messages! This information has been disclosed by the holder.

The generated/presented proofs work just like *signatures*
from the point of view of the verifier

- They verify against the
**issuers***public key*(no holder keys need be involved) - They are existentially unforgeable, i.e., any modification to the messages will cause proof verification to fail.

Go to BBS Demo

- Create a BBS signature on a list of messages
- Create a BBS Proof from a selected set of the messages
- Verify the BBS Proof against the
*issuers*public key - Change a message slightly in the
*proof*JSON - Re-process JSON try to verify proof

- At its heart BBS uses the hardness of the
*discrete logarithm problem*(DLP) - It uses
*elliptic curves*to keep the element values reasonable size - It uses a
*elliptic curve pairing*to get the selective disclosure and unlinkable properties

- How do we take a VC with multiple claims and create a list of messages for BBS
- What additional information should be in the signed VC?
- What is the processing algorithm and format of the signed VC
- How does the holder process the signed VC perform selective disclosure and produce the VP

- The issuer may require that certain information must be disclosed from the list of messages
- If information is very fine grained we may need/want to prevent items (messages) from being taken out of context. Could require that messages be released in sets of indexes, i.e., as a group together or not at all.

- Unique or somewhat identifiers in messages
- JSON information leakage
- Canonicalization information leakage
- Fingerprinting when many messages and selective disclosure