Skip to content

Latest commit

 

History

History
219 lines (145 loc) · 11.4 KB

MATH.md

File metadata and controls

219 lines (145 loc) · 11.4 KB
Raw

Primitives

Curve and Bilinear Maps

The protocol uses pairing-friendly curves as the basic building block under the hood.

This implementation uses BLS12-381 but can easily change to any other pairing-friendly curve.

The curve parameters are denoted as

  • : The security parameter in bits.
  • : The field modulus
  • : The subgroup order
  • : Points in the cyclic group of order
  • : Points in the multiplicative group of order
  • : A pairing function that takes and and returns a result in the multiplicative group in
  • : The base point in
  • : The base point in
  • : The point at infinity in
  • : The point at infinity in
  • : The point at infinity in

Scalars operate in and are denoted as lower case letters. Scalars are represented with 32 bytes with BLS12-381.

Points operating in are denoted as capital letters. points in BLS12-381 are 48 bytes compressed and 96 bytes uncompressed.

Points operating in are denoted as capital letters with a wide tilde. points in BLS12-381 are 96 bytes compressed and 192 bytes uncompressed.

Hash to Curve

Oberon uses Hash to curve to map arbitrary byte sequences to random points with unknown discrete logs.

This is denoted as for hashing to a point in .

The hash to curve standard demands a unique DST to be defined. Oberon uses

OBERON_BLS12381G1_XOF:SHAKE-256_SSWU_RO_

Hash to Field

Oberon hashes arbitrary byte sequences to a field element. The tricky part here is to generate enough bytes such that the result is distributed uniformly random.

A common approach is to use SHA256 to hash to byte sequence then reduce modulo . However, this results in a biased result that isn't uniform. Instead more bytes should be generated then reduced modulo . The number of bytes is calculated with L = ceil((ceil(log2(p)) + k) / 8). For BLS12-381 this is L=48 bytes.

This implementation uses SHAKE-256 to output 48 bytes.

Hash to field is denoted as .

Hash to field uses the domain separation tag OBERON_BLS12381FQ_XOF:SHAKE-256_

Signatures

Oberon uses BLS keys in combination with Pointcheval Saunders (PS) signatures with improvements in Reassessing Security of PS signatures to be secure under Existential Unforgeability against Adaptively Chosen Message Attacks (EUF-CMA).

Notations

  • a || b: is the byte concatenation of two elements a, b
  • : is a random number in the field
  • is the user’s identification string

Algorithms

Oberon has the following algorithms:

KeyGen

By default, Oberon only signs a user’s identity string , but PS signatures support many attributes if needed with the tradeoff that keys get bigger but not the token.

KeyGen()

Generate BLS keys and set them for

The output is

The secret key and is 96 bytes.

The public key and is 288 bytes.

IdToInternals

This function maps the user's identity string to the various internals and checks if they are valid.

IdToInternals()

$$\begin{align} m &= H_{\mathbb{Z}_q}(id) ;& \text{if}\ m &= 0\ \text{abort} \\\ m' &= H_{\mathbb{Z}_q}(m) ;& \text{if}\ m' &= 0\ \text{abort} \\\ U &= H_{\mathbb{G}_1}(m') ;& \text{if}\ U &= 1_{\mathbb{G}_1}\ \text{abort} \\\ \end{align}$$

The function outputs (, , )

Sign

Sign creates a token to be given to a user and works as follows

Sign(, )

$$\begin{align} m, m', U &= \text{IdToInternals}(id) \\\ \sigma &= (x + m.y + m'.w)\cdot U ;& \text{if}\ \sigma &= 1_{\mathbb{G}_1}\ \text{abort} \\\ \end{align}$$

Output token is

Blinding factor

Oberon can use a blinding factor in combination with the normal token to blind the original token such that without knowledge of the 2nd factor, the token is useless. Blinding factors can be computed by using HG1 on any arbitrary input.

For example, the user could select a 6-digit pin that needs to be entered each time they want to use it. To require the pin to use the token, the following can be computed

Store

Multiple blinding factors can be applied in a similar manner. Each blinding factor can be different based on the platform where the token resides.

Verify

Verify takes a token and checks its validity. Meant to be run by the token holder since the token should never be disclosed to anyone.

Verify(, , )

$$\begin{align} m, m', U &= \text{IdToInternals}(id) \\\ e(U, &\widetilde{X} + m \cdot \widetilde{Y} + m' \cdot \widetilde{W}).e(\sigma, -\widetilde{P}) = 1_{\mathbb{G}_T} \end{align}$$

can be cached by the holder for performance if desired in which case those steps can be skipped.

Prove

Prove creates a zero-knowledge proof of a valid token instead of sending the token itself. This allows the token to be reused while minimizing the risk of correlation.

Below is the algorithm for Prove assuming a blind factor with a pin.

Prove(, , )

can be a timestamp or publicly verifiable value like the latest Bitcoin hash.

$$\begin{align} m, m', U &= \text{IdToInternals}(id) \\\ r &\xleftarrow{\$} \mathbb{Z}_q* ;& \text{if}\ r &= 0\ \text{abort} \\\ U' &= r \cdot U ;& \text{if}\ U' &= 1_{\mathbb{G}_1}\ \text{abort} \\\ t &= H_{\mathbb{Z}_q}(U' || n) ;& \text{if}\ t &= 0\ \text{abort} \\\ Z &= -(r + t) \cdot (\sigma' + B) ;& \text{if}\ Z &= 1_{\mathbb{G}_1}\ \text{abort} \\\ \tau &= U', Z \end{align}$$

Open

Open validates whether a proof is valid against a specific public key and is fresh enough.

Open(, , )

$$\begin{align} & & \text{if}\ U' = 1_{\mathbb{G}_1}\ \text{abort} \\\ & & \text{if}\ Z = 1_{\mathbb{G}_1}\ \text{abort} \\\ m, m', U &= \text{IdToInternals}(id) \\\ t &= H_{\mathbb{Z}_q}(U' || n) ;& \text{if}\ t = 0\ \text{abort} \\\ e(&U' + t\cdot U, \widetilde{X} + m \cdot \widetilde{Y} + m' \cdot \widetilde{W})e(Z, \widetilde{P}) == 1_{\mathbb{G}_T} \end{align}$$

Other notes

PS signatures support blind signatures methods such that could be blinded before being signed by the token issuer.

They also support multiple attributes that can be added to the signature with the cost of an additional BLS keypair per attribute.

Oberon is meant to be simple and for now doesn't handle these features but might in future work.

Threshold

Since the keys are BLS based, they can use any suitable threshold key gen and sign technique.

This process should be handled outside of Oberon. Another crate will probably be created for this.