Outline

1. Signature Review
2. VCs and Signatures
3. BBS Signatures
4. Selective Disclosure
5. Anonymity and Unlinkability

Who Am I

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

References General Signatures

• 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)

Signature Definition

From B&S Chapter 13

Signature Security (intuitive)

From B&S Chapter 13

Other Signature Security Properties 1

From Taming the many EdDSAs

• 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”

Other Signature Security Properties 2

From Taming the many EdDSAs

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

VC Signature Specifications in Progress

• 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…

EdDSA with Curve Ed25519

• 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)

Applying to VCs

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)

Example Unsigned VC

{
    "@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"
    }
}

Configuration Options for Data Integrity EdDSA

{
  "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"
  ]
}

Signing the VC and Configuration Options

1. Canonize unsigned VC
2. Canonize configuration options
3. combine cryptographic hashes of canonized configuration options and unsigned VC
4. create signature with combined hash as message
5. created signed VC with unsigned VC, options, and signature

Example Signed VC

{
  "@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

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

References

• 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.

BBS Demo

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

BBS Fundamental Properties 1

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.

BBS Fundamental Properties 2

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.

BBS Signature with Curve BLS12-381

• 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.

Example: Tree Drivers License

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"
}

Selective Disclosure and VC/VP Model 1

Selective Disclosure and VC/VP Model 2

• 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.

Selective Disclosure Approaches

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)

Example: A Tree goes to a bar…

Example Derived “Proof”

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

Terminology Collision!

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”.

VCs, VPs, and Selective Disclosure I

1. 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”
2. 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.

VCs, VPs, and Selective Disclosure II

3. 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 Signature Suite Procedures and VC/VPs 1

BBS has sign and verify

1. signature = Sign(Secret_Key, Public_key, header, messages) used by issuer
2. result = Verify(Public, signature, header, messages) is used when the holder verifies the VC it receives from the issuer.

BBS Signature Suite Procedures and VC/VPs 2

but BBS is more than sign and verify

3. 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.
4. 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.

Holders and Verifiers

• 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.

Verifiers Tracking Holders

Does this really happen?

• 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…

BBS and Anonymity

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?

Unlinkable Proofs Example 1

• 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

Unlinkable Proofs Example 2

BBS Proof presented at first bar

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

Unlinkable Proofs Example 3

BBS Proof presented at second bar

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

Unlinkable Proofs

• 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.

Proof of Possession

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.

Holder Modifying Messages after Signing

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

How does BBS Work

• 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

VCs and VPs based on BBS

• 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

Issuer Control and Selective Disclosure

• 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.

Information Leakage and Fingerprinting

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