Skip to content

Latest commit

 

History

History
105 lines (95 loc) · 6.47 KB

ALGORITHM.md

File metadata and controls

105 lines (95 loc) · 6.47 KB
Raw

BBS+ Signatures

BBS+ is a pairing-based cryptographic signature used for signing 1 or more messages. As described in the BBS+ spec, BBS+ keys function in the following way:

  1. A a prime field ℤp
  2. A bilinear pairing-friendly curve E with three groups 𝔾1, 𝔾2, 𝔾T of prime order p.
  3. 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
  4. A base generator g1 ∈ 𝔾1 for curve E
  5. A base generator g2 ∈ 𝔾2 for curve E
  6. L messages to be signed
  7. Key Generation
    1. Inputs (L)
    2. Generate a random generator for each message (h1, ... , hL) ⟵ 𝔾1L+1
    3. Generate a random generator used for blinding factors h0 ⟵ 𝔾1
    4. Generate random x ⟵ ℤp
    5. Compute w ⟵ g2x
    6. Secret key is x and public pk is (w, h0, h1, ... , hL)
    7. Output (pk, x)
  8. Signature
    1. Inputs (pk, x, { M1, ... , ML })
    2. Each message M is converted to integers (m1, ..., mL) ∈ ℤp
    3. Generate random numbers ε, s ⟵ ℤp
    4. Compute B ⟵ g1h0s ∏i=1L himi
    5. Compute A ⟵B1⁄x+ε
    6. Output signature σ ⟵ (A, ε, s)
  9. Verification
    1. Inputs (pk, σ, { M1, ..., ML })
    2. Each message M is converted to integers (m1, ..., mL) ∈ ℤp
    3. Check e(A, wg2ε) ≟ e(B, g2)
  10. Zero-Knowledge Proof Generation
    1. To create a signature proof of knowledge where certain messages are disclosed and others remain hidden
    2. AD is the set of disclosed attributes
    3. AH is the set of hidden attributes
    4. Inputs (pk, AD, AH, σ)
    5. Generate random numbers r1, r2 ⟵ ℤp
    6. Compute B as done in the signing phase
    7. Compute A' ⟵ Ar1
    8. Compute A̅ ⟵ A'-εBr1
    9. Compute d ⟵ Br1h0-r2
    10. Compute r3 ⟵ 1⁄r1
    11. Compute s' ⟵ s - r2 r3
    12. Compute π1 ⟵ A'-ε h0r2
    13. Compute for all hidden attributes π2 ⟵ dr3h0-s'∏i=1AH himi
  11. Zero-Knowledge Proof Verification
    1. Check signature e(A', w) ≟ e(A̅, g2)
    2. Check hidden attributes A̅⁄d ≟ π1
    3. 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 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 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

  2. I2OSP Thise function is used to convert a byte string to a non-negative integer as described in RFC8017.

  3. Compute h0 ⟵ H2C( w || I2OSP(0, 1) || I2OSP(L, 4) )

  4. Compute hi ⟵ H2C( hi-1 || I2OSP(0, 1) || I2OSP(i, 4) )

  5. Key Generation

    1. Inputs ()
    2. Generate random x ⟵ ℤp
    3. Compute w ⟵ g2x
    4. Secret key is x and public pk is w
    5. Output (pk, x)

  6. Signature

    1. Inputs (x, {M1, ..., ML)
    2. Compute w ⟵ g2x
    3. Compute message specific generators.
    4. Same as before

  7. Verification

    1. Inputs (pk, {M1, ..., ML, σ)
    2. Compute message specific generators.
    3. Verify as before