# BBS+ Signatures
BBS+ is a pairing-based cryptographic signature used for signing 1 or more messages. As described in the
[BBS+ spec](https://eprint.iacr.org/2016/663.pdf), BBS+ keys function in the following way:
1. A a prime field _ℤp_
1. A bilinear pairing-friendly curve _E_ with three groups _𝔾1, 𝔾2,
𝔾T_ of prime order _p_.
1. A type-3 pairing function _e_ such that _e : 𝔾1 X 𝔾2 ⟶
𝔾T_. More requirements for this can be found in section 4.1 in the
[BBS+ spec](https://eprint.iacr.org/2016/663.pdf)
1. A base generator _g1 ∈ 𝔾1_ for curve _E_
1. A base generator _g2 ∈ 𝔾2_ for curve _E_
1. _L_ messages to be signed
1. **Key Generation**
1. Inputs (_L_)
1. Generate a random generator for each message _(h1, ... , hL) ⟵
𝔾1L+1_
1. Generate a random generator used for blinding factors _h0 ⟵ 𝔾1_
1. Generate random _x ⟵ ℤp_
1. Compute _w ⟵ g2x_
1. Secret key is _x_ and public _pk_ is _(w, h0, h1, ... , hL)_
1. Output (_pk_, _x_)
1. **Signature**
1. Inputs (_pk, x, { M1, ... , ML }_)
1. Each message _M_ is converted to integers _(m1, ..., mL) ∈ ℤp_
1. Generate random numbers _ε, s ⟵ ℤp_
1. Compute _B ⟵ g1h0s ∏i=1L
himi_
1. Compute _A ⟵B1⁄x+ε_
1. Output signature _σ ⟵ (A, ε, s)_
1. **Verification**
1. Inputs _(pk, σ, { M1, ..., ML })_
1. Each message _M_ is converted to integers _(m1, ..., mL) ∈ ℤp_
1. Check _e(A, wg2ε) ≟ e(B, g2)_
1. **Zero-Knowledge Proof Generation**
1. To create a signature proof of knowledge where certain messages are disclosed and others remain hidden
1. _AD_ is the set of disclosed attributes
1. _AH_ is the set of hidden attributes
1. Inputs _(pk, AD, AH, σ)_
1. Generate random numbers _r1, r2 ⟵ ℤp_
1. Compute _B_ as done in the signing phase
1. Compute _A' ⟵ Ar1_
1. Compute _A̅ ⟵ A'-εBr1_
1. Compute _d ⟵ Br1h0-r2_
1. Compute _r3 ⟵ 1⁄r1_
1. Compute _s' ⟵ s - r2 r3_
1. Compute _π1 ⟵ A'-ε h0r2_
1. Compute for all hidden attributes _π2 ⟵
dr3h0-s'∏i=1AH
himi_
1. **Zero-Knowledge Proof Verification**
1. Check signature _e(A', w) ≟ e(A̅, g2)_
1. Check hidden attributes _A̅⁄d ≟ π1_
1. Check revealed attributes _g1∏i=1AD
himi ≟ π2_
The BBS+ spec does not specify when the generators _(h0, h1, ..., hL)_, only that they
are random generators. Generally in cryptography, public keys are created entirely during the key generation step.
However, Notice the only value in the public key _pk_ that is tied to the private key _x_ is _w_. If we
isolate this value as the public key _pk_, this is identical to the
[BLS signature keys](https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html) or ECDSA. The remaining values
could be computed at a later time, say during signing, verification, proof generation and verification. This means key
generation and storage is much smaller at the expense of computing the generators when they are needed. Creating the
remaining generators in this manner will require that all parties are able to arrive at the same values otherwise
signatures and proofs will not validate. In this Spec, we describe an efficient and secure method for computing the
public key generators on-the-fly.
## Proposal
In a prime field, any non-zero element in a prime order group generates the whole group, and ability to solve the
discrete log relatively to a specific generator is equivalent to ability to solve it for any other. As long as the
generators are valid elliptic curve points, then any point should be secure. To compute generators, we propose using
IETF's [Hash to Curve](https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/?include_text=1) algorithm which
is also constant time combined with known inputs. This method allows any party to compute generators that can be used in
the BBS+ signature scheme.
## Algorithm
Using these changes, the API changes to be identical to ECDSA and BLS except signing and verification can include any
number of messages vs a single message.
The API's change in the following way and compute the message specific generators by doing the following
1. _H2C_ is the hash to curve algorithm
1. _I2OSP_ Thise function is used to convert a byte string to a non-negative integer as described in
[RFC8017](https://tools.ietf.org/html/rfc8017#section-4.1).
1. Compute _h0 ⟵ H2C( w || I2OSP(0, 1) || I2OSP(L, 4) )_
1. Compute _hi ⟵ H2C( hi-1 || I2OSP(0, 1) || I2OSP(i, 4) )_
1. **Key Generation**
1. Inputs _()_
1. Generate random _x ⟵ ℤp_
1. Compute _w ⟵ g2x_
1. Secret key is _x_ and public _pk_ is _w_
1. Output _(pk, x)_
1. **Signature**
1. Inputs _(x, \{M1, ..., ML)_
1. Compute _w ⟵ g2x_
1. Compute message specific generators.
1. Same as before
1. **Verification**
1. Inputs _(pk, \{M1, ..., ML, σ)_
1. Compute message specific generators.
1. Verify as before