What is BBS Signature?
(Boneh-Boyen-Shacham)
Kazue Sako
( with help of Ken Watanabe, Masato Tsutsumi and Dan Yamamoto)
Dept. Computer Science and Engineering
Waseda University
contact: kazuesako@aoni.waseda.jp
Internet Identity Workshop
Spring 2024
Q1: How is it different from ordinary signatures
i.e. compared to RSA, ECDSA, EdDSA, Schnorr signatures?
2
Comparison
one signature for one message.
one signature for multiple message.
Waseda University Sako Laboratory
3
Q2: Why one signature for multiple messages good?
unlinkable selective disclosure.
4
Selective Disclosure: Goal
Alice
Bob
Alice has
Attributes
(a1, a2, ..., an)
Bob can verify the correctness.
Bob does not learn other attributes.
Alice only wants to disclose
(a1, a2, a3)
Waseda University Sako Laboratory
5
Ordinary signature scheme is ‘show all or nothing’!
Alice
Bob
Alice has
Attributes
M=a1 || a2 || ..., || an
Bob can verify the correctness.
Bob does not learn other attributes.
Sig = sign(M)
Alice only wants to disclose
(a1, a2, a3)
Waseda University Sako Laboratory
6
Re: Comparison
one signature for one message.
one signature for multiple message.
Waseda University Sako Laboratory
7
Extra steps for selective disclosure
Sign
(issuer)
Verify Sig
(holder)
Prove
(holder)
Verify proof
(verifier)
Issuance
Presentation
Waseda University Sako Laboratory
8
Selective Disclosure: SD-JWT at IETF
Alice
Bob
Alice has
Attributes
(a1, a2, ..., an)
Bob can verify the correctness.
Bob does not learn other attributes.
M=hash(a1)|| hash (a2)||..||hash(an)
Sig = sign(M)
M, Sig, (a1,a2,a3)
Alice only wants to disclose
(a1, a2, a3)
Waseda University Sako Laboratory
9
Linkability in Selective Disclosure
Alice
Bob
Selectively disclose (a1,a2,a3)
David
Selectively disclose (a4,a5,a6)
linkable
Alice has
Attributes
(a1, a2, ..., an)
Same person!
Same person!
M, Sig, (a1,a2,a3)
M, Sig, (a4,a5,a6)
Unlinkability in Selective Disclosure using BBS
Alice
Bob
Selectively disclose (a1,a2,a3)
David
Selectively disclose (a4,a5,a6)
unlinkable
Alice has
Attributes
(a1, a2, ..., an)
Same person!
Same person???
(a1,a2,a3)+proof
(a4,a5,a6)+proof
Q3: What other algorithms provide one signature for multiple messages and why BBS?
There are CL signatures(2003) and PS signatures(2016). There are pros and cons.
12
Data Size Comparison
| Secret key | Public key | Signature | Proof | param. |
BBS+ (2016) | 52 B | 98 B | 112 B | 1008 B (**) | p=348 |
CL (2003) | 512 B | 11008 B(*) | 461 B | 5120 B(**) | N=2048 |
PS (2016) | 1312 B (*) | 3936 B(*) | 96 B | 950 B (**) | p=348 |
(*)Depends on the number of messages (40)
(**)Depends on the number of hiding messages (20)
Waseda University Sako Laboratory
13
Speed comparison
| Sign | VerifySig | Prove | VerifyProof | Param. |
BBS+ | 665.0 µs | 1.8 ms | 1.8 ms | 2.5 ms | p=348 |
CL | 202.1 ms | 224.3 ms | 70.9 ms | 57.2 ms | N=2048 |
PS | 404.4 µs | 5.2 ms | 4.3 ms | 5.2 ms | p=348 |
Waseda University Sako Laboratory
14
Q4: How fast is BBS?
I only have figures for BBS+ (which will be slower than BBS)
15
BenchMark
| Sign | VerifySig | Prove | VerifyProof | Param. |
BBS+ m=20 | 573 µs | 1665.6 µs | 1.6 ms | 2.5 ms | p=348 |
BBS+ m=40 | 6645 µs | 1776.3 µs | 1.8 ms | 2.5 ms | p=348 |
RSA | 1050 µs | 126.7 µs | - | - | N=2048 e=65537 |
EcDSA (secp256k1) | 57 µs | 67.4 µs | - | - | p=256 (shorter) |
Waseda University Sako Laboratory
16
BBS+ signatures: Influence of how many attributes to open
| Sign | VerifySig | Prove | VerifyProof | Keysize |
BBS+ m=40, open 10 | 664.99 µs | 1.7763 ms | 1.8317 ms | 2.4937 ms | p=348 |
BBS+ m=40 open 20 | same as above | same as above | 1.7870 ms | 2.5120 ms | same as above |
BBS+ m=40 open 30 | same as above | same as above | 1.7716 ms | 2.4881 ms | same as above |
BBS+ m=40 open 39 | same as above | same as above | 1.6472 ms | 2.4862 ms | same as above |
Waseda University Sako Laboratory
17
BBS+ signatures: Influence of how many attributes to sign
| Sign | VerifySig | Prove | VerifyProof | Keysize |
BBS+ m=20, open 10 | 573.67 µs | 1.6656 ms | 1.6107 ms | 2.5249 ms | p=348 |
BBS+ m=40 open 20 | 664.99 µs | 1.7763 ms | 1.8317 ms | 2.4937 ms | same as above |
BBS+ m=100 open 50 | 857.86 µs | 1.9677 ms | 2.1107 ms | 2.7521 ms | same as above |
BBS+ m=500 open 250 | 1875.6 µs | 3.0962 ms | 3.7500 ms | 3.9132 ms | same as above |
Waseda University Sako Laboratory
18
Q5: Where can we find open source library for BBS?
19
List of Open Source Libraries for BBS
- hyperledger-archives/ursa (public archived)
- mattrglobal/bbs-signatures
Some libraries that uses BBS
Additions to the list welcomed!
Waseda University Sako Laboratory
20
Q6:Do we have to use JSON-LD for BBS Sig?
NO
21
Q7: What kind of standards are there for BBS?
IRTF, IETF, W3C, ISO… incomplete list
22
List of ongoing Standards
uses IRTF-CFRG algorithm, in Verifiable Credential Data Integrity 1.0 format.
Additions to the list welcomed!
Waseda University Sako Laboratory
23
Q8: Is it BBS signatures or BBS+ signatures?
In 2004, we did not know how to prove security of BBS signatures. In 2016 there was technical modifications called BBS+ signatures which was proven secure. Recently(2023), original BBS signatures was proven secure, so I would go with BBS signatures.
NOTE: Proofs for SD may be different between 2004 and 2023 version.
24
Comparison: BBS+ signatures and BBS signatures
Waseda University Sako Laboratory
25
Comparison: BBS+ signatures and BBS signatures
Waseda University Sako Laboratory
26
Q9: Is it BBS signatures quantum secure?
Yes, in the sense undisclosed attributes will not be disclosed even in the presence of Quantum Computer. No, in the sense that Quantum Computer can falsificate signatures.
27
Q10: Are there hardware support for BBS?
If there is marketing needs, there should be products coming out, including HSM.
28
Q: (put your question here) ?
I will try to answer, though it may be my homework.
29
What is BBS Signature?�
It is a signature scheme giving one signature for multiple messages, suitable for unlinkable selective disclosure, not broken for 20+yrs, awaiting for wide adoption!
Summary