Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups

1.1. Change log

draft-05:¶

• Move to ristretto255 and decaf448 ciphersuites.¶
• Clean up ciphersuite definitions.¶
• Pin domain separation tag construction to draft version.¶
• Move key generation outside of context construction functions.¶
• Editorial changes.¶

draft-04:¶

• Introduce Client and Server contexts for controlling verifiability and required functionality.¶
• Condense API.¶
• Remove batching from standard functionality (included as an extension)¶
• Add Curve25519 and P-256 ciphersuites for applications that prevent strong-DH oracle attacks.¶
• Provide explicit prime-order group API and instantiation advice for each ciphersuite.¶
• Proof-of-concept implementation in sage.¶
• Remove privacy considerations advice as this depends on applications.¶

draft-03:¶

• Certify public key during VerifiableFinalize¶
• Remove protocol integration advice¶
• Add text discussing how to perform domain separation¶
• Drop OPRF_/VOPRF_ prefix from algorithm names¶
• Make prime-order group assumption explicit¶
• Changes to algorithms accepting batched inputs¶
• Changes to construction of batched DLEQ proofs¶
• Updated ciphersuites to be consistent with hash-to-curve and added OPRF specific ciphersuites¶

draft-02:¶

• Added section discussing cryptographic security and static DH oracles¶
• Updated batched proof algorithms¶

draft-01:¶

• Updated ciphersuites to be in line with https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-04¶
• Made some necessary modular reductions more explicit¶

1.2. Terminology

The following terms are used throughout this document.¶

• PRF: Pseudorandom Function.¶
• OPRF: Oblivious Pseudorandom Function.¶
• VOPRF: Verifiable Oblivious Pseudorandom Function.¶
• Client: Protocol initiator. Learns pseudorandom function evaluation as the output of the protocol.¶
• Server: Computes the pseudorandom function over a secret key. Learns nothing about the client's input.¶
• NIZK: Non-interactive zero knowledge.¶
• DLEQ: Discrete Logarithm Equality.¶

1.3. Requirements

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

2.1. Prime-order group API

In this document, we assume the construction of an additive, prime-order group GG for performing all mathematical operations. Such groups are uniquely determined by the choice of the prime p that defines the order of the group. We use GF(p) to represent the finite field of order p. For the purpose of understanding and implementing this document, we take GF(p) to be equal to the set of integers defined by {0, 1, ..., p-1}.¶

The fundamental group operation is addition + with identity element I. For any elements A and B of the group GG, A + B = B + A is also a member of GG. Also, for any A in GG, there exists an element -A such that A + (-A) = (-A) + A = I. Scalar multiplication is equivalent to the repeated application of the group operation on an element A with itself r-1 times, this is denoted as r*A = A + ... + A. For any element A, the equality p*A=I holds. Scalar base multiplication is equivalent to the repeated application of the group operation on the base point with itself r-1 times, this is denoted as ScalarBaseMult(r). The set of scalars corresponds to GF(p).¶

We now detail a number of member functions that can be invoked on a prime-order group.¶

• Order(): Outputs the order of GG (i.e. p).¶
• Identity(): Outputs the identity element of the group (i.e. I).¶
• Serialize(A): A member function of GG that maps a group element A to a unique byte array buf.¶
• Deserialize(buf): A member function of GG that maps a byte array buf to a group element A, or fails if the input is not a valid byte representation of an element.¶
• HashToGroup(x): A member function of GG that deterministically maps an array of bytes x to an element of GG. The map must ensure that, for any adversary receiving R = HashToGroup(x), it is computationally difficult to reverse the mapping. Examples of hash to group functions satisfying this property are described for prime-order (sub)groups of elliptic curves, see [I-D.irtf-cfrg-hash-to-curve].¶
• HashToScalar(x): A member function of GG that deterministically maps an array of bytes x to an element in GF(p). A recommended method for its implementation is instantiating the hash to field function, defined in [I-D.irtf-cfrg-hash-to-curve] setting the target field to GF(p).¶
• RandomScalar(): A member function of GG that chooses at random a non-zero element in GF(p).¶

It is convenient in cryptographic applications to instantiate such prime-order groups using elliptic curves, such as those detailed in [SEC2]. For some choices of elliptic curves (e.g. those detailed in [RFC7748], which require accounting for cofactors) there are some implementation issues that introduce inherent discrepancies between standard prime-order groups and the elliptic curve instantiation. In this document, all algorithms that we detail assume that the group is a prime-order group, and this MUST be upheld by any implementer. That is, any curve instantiation should be written such that any discrepancies with a prime-order group instantiation are removed. See Section 4 for advice corresponding to implementation of this interface for specific definitions of elliptic curves.¶

2.2. Other conventions

• We use the notation x <-$ Q to denote sampling x from the uniform distribution over the set Q.¶
• For any object x, we write len(x) to denote its length in bytes.¶
• For two byte arrays x and y, write x || y to denote their concatenation.¶
• I2OSP and OS2IP: Convert a byte array to and from a non-negative integer as described in [RFC8017]. Note that these functions operate on byte arrays in big-endian byte order.¶

All algorithm descriptions are written in a Python-like pseudocode. We use the ABORT() function for presentational clarity to denote the process of terminating the algorithm or returning an error accordingly. We also use the CT_EQUAL(a, b) function to represent constant-time byte-wise equality between byte arrays a and b. This function returns true if a and b are equal, and false otherwise.¶

3.1. Overview

Both participants agree on the mode and a choice of ciphersuite that is used before the protocol exchange. Once established, the core protocol runs to compute output = F(skS, input) as follows:¶

   Client(pkS, input, info)                 Server(skS, pkS)
  ----------------------------------------------------------
    token, blindToken = Blind(input)

                         blindToken
                        ---------->

                         evaluation = Evaluate(skS, pkS, blindToken)

                         evaluation
                        <----------

    issuedToken = Unblind(pkS, token, blindToken, evaluation)
    output = Finalize(input, issuedToken, info)

In Blind the client generates a token and blinding data. The server computes the (V)OPRF evaluation in Evaluation over the client's blinded token. In Unblind the client unblinds the server response (and verifies the server's proof if verifiability is required). In Finalize, the client produces a byte array corresponding to the output of the OPRF protocol.¶

Note that in the final output, the client computes Finalize over some auxiliary input data info. This parameter SHOULD be used for domain separation in the (V)OPRF protocol. Specifically, any system which has multiple (V)OPRF applications should use separate auxiliary values to ensure finalized outputs are separate. Guidance for constructing info can be found in [I-D.irtf-cfrg-hash-to-curve]; Section 3.1.¶

3.2. Context Setup

Both modes of the OPRF involve an offline setup phase. In this phase, both the client and server create a context used for executing the online phase of the protocol. Prior to this phase, keys (skS, pkS) should be generated by calling a KeyGen function. KeyGen generates a private and public key pair (skS, pkS), where skS is a non-zero element chosen at random from the scalar field of the corresponding group and pkS = ScalarBaseMult(skS).¶

The base mode setup functions for creating client and server contexts are below:¶

def SetupBaseServer(suite, skS):
  contextString = I2OSP(modeBase, 1) || I2OSP(suite.ID, 2)
  return ServerContext(contextString, skS)

def SetupBaseClient(suite):
  contextString = I2OSP(modeBase, 1) || I2OSP(suite.ID, 2)
  return ClientContext(contextString)

The verifiable mode setup functions for creating client and server contexts are below:¶

def SetupVerifiableServer(suite, skS, pkS):
  contextString = I2OSP(modeVerifiable, 1) || I2OSP(suite.ID, 2)
  return VerifiableServerContext(contextString, skS), pkS

def SetupVerifiableClient(suite, pkS):
  contextString = I2OSP(modeVerifiable, 1) || I2OSP(suite.ID, 2)
  return VerifiableClientContext(contextString, pkS)

Each setup function takes a ciphersuite from the list defined in Section 4. Each ciphersuite has a two-byte field ID used to identify the suite.¶

3.3. Data Structures

The following is a list of data structures that are defined for providing inputs and outputs for each of the context interfaces defined in Section 3.4. Each data structure description uses TLS notation (see [RFC8446], Section 3).¶

The following types are a list of aliases that are used throughout the protocol.¶

A ClientInput is a byte array.¶

opaque ClientInput<1..2^16-1>;

A SerializedElement is also a byte array, representing the unique serialization of an Element.¶

opaque SerializedElement<1..2^16-1>;

A Token is an object created by a client when constructing a (V)OPRF protocol input. It is stored so that it can be used after receiving the server response.¶

struct {
  opaque data<1..2^16-1>;
  Scalar blind<1..2^16-1>;
} Token;

An Evaluation is the type output by the Evaluate algorithm. The member proof is added only in verifiable contexts.¶

struct {
  SerializedElement element;
  Scalar proof<0...2^16-1>; /* only for modeVerifiable */
} Evaluation;

Evaluations may also be combined in batches with a constant-size proof, producing a BatchedEvaluation. These carry a list of SerializedElement values and proof. These evaluation types are only useful in verifiable contexts which carry proofs.¶

struct {
  SerializedElement elements<1..2^16-1>;
  Scalar proof<0...2^16-1>; /* only for modeVerifiable */
} BatchedEvaluation;

3.4. Context APIs

In this section, we detail the APIs available on the client and server (V)OPRF contexts. This document uses the types Element and Scalar to denote elements of the group GG and its underlying scalar field GF(p), respectively. For notational clarity, PublicKey is an item of type Element and PrivateKey is an item of type Scalar.¶

Input:

  PrivateKey skS
  SerializedElement blindToken

Output:

  Evaluation Ev

def Evaluate(skS, blindToken):
  BT = GG.Deserialize(blindToken)
  Z = skS * BT
  serializedElement = GG.Serialize(Z)

  Ev = Evaluation{ element: serializedElement }

  return Ev

Input:

  PrivateKey skS
  ClientInput input
  opaque info<1..2^16-1>

Output:

  opaque output<1..2^16-1>

def FullEvaluate(skS, input, info):
  P = GG.HashToGroup(input)
  T = skS * P
  issuedToken = GG.serialize(T)

  finalizeDST = "VOPRF05-Finalize-" || self.contextString
  hashInput = I2OSP(len(input), 2) || input ||
              I2OSP(len(issuedToken), 2) || issuedToken ||
              I2OSP(len(info), 2) || info ||
              I2OSP(len(finalizeDST), 2) || finalizeDST

  return Hash(hashInput)

Input:

  PrivateKey skS
  ClientInput input
  opaque info<1..2^16-1>
  opaque output<1..2^16-1>

Output:

  boolean valid

def VerifyFinalize(skS, input, info, output):
  T = GG.HashToGroup(input)
  element = GG.Serialize(T)
  issuedElement = Evaluate(skS, [element])
  E = GG.Serialize(issuedElement)

  finalizeDST = "VOPRF05-Finalize-" || self.contextString
  hashInput = I2OSP(len(input), 2) || input ||
              I2OSP(len(E), 2) || E ||
              I2OSP(len(info), 2) || info ||
              I2OSP(len(finalizeDST), 2) || finalizeDST

  digest = Hash(hashInput)

  return CT_EQUAL(digest, output)

Input:

  PrivateKey skS
  PublicKey pkS
  SerializedElement blindToken

Output:

  Evaluation Ev

def Evaluate(skS, pkS, blindToken):
  BT = GG.Deserialize(blindToken)
  Z = skS * BT
  serializedElement = GG.Serialize(Z)

  proof = GenerateProof(skS, pkS, blindToken, serializedElement)
  Ev = Evaluation{ element: serializedElement, proof: proof }

  return Ev

Input:

  PrivateKey skS
  PublicKey pkS
  SerializedElement blindToken
  SerializedElement element

Output:

  Scalar proof[2]

def GenerateProof(skS, pkS, blindToken, element)
  blindTokenList = [blindToken]
  elementList = [element]

  a = ComputeComposites(pkS, blindTokenList, elementList)

  M = GG.Deserialize(a[0])
  r = GG.RandomScalar()
  a2 = GG.Serialize(ScalarBaseMult(r))
  a3 = GG.Serialize(r * M)

  challengeDST = "VOPRF05-challenge-" || self.contextString
  h2Input = I2OSP(len(pkS), 2) || pkS ||
            I2OSP(len(a[0]), 2) || a[0] ||
            I2OSP(len(a[1]), 2) || a[1] ||
            I2OSP(len(a2), 2) || a2 ||
            I2OSP(len(a3), 2) || a3 ||
            I2OSP(len(challengeDST), 2) || challengeDST

  c = GG.HashToScalar(h2Input)
  s = (r - c * skS) mod p

  return [c, s]

Input:

  PublicKey pkS
  SerializedElement blindTokens[m]
  SerializedElement elements[m]

Output:

  SerializedElement composites[2]

def ComputeComposites(pkS, blindTokens, elements):
  seedDST = "VOPRF05-seed-" || self.contextString
  compositeDST = "VOPRF05-composite-" || self.contextString
  h1Input = I2OSP(len(pkS), 2) || pkS ||
            I2OSP(len(blindTokens), 2) || blindTokens ||
            I2OSP(len(elements), 2) || elements ||
            I2OSP(len(seedDST), 2) || seedDST

  seed = Hash(h1Input)
  M = GG.Identity()
  Z = GG.Identity()
  for i = 0 to m-1:
    h2Input = I2OSP(len(seed), 2) || seed || I2OSP(i, 2) ||
              I2OSP(len(compositeDST), 2) || compositeDST
    di = GG.HashToScalar(h2Input)
    Mi = GG.Deserialize(blindTokens[i])
    Zi = GG.Deserialize(elements[i])
    M = di * Mi + M
    Z = di * Zi + Z
 return [GG.Serialize(M), GG.Serialize(Z)]

Input:

  ClientInput input

Output:

  Token token
  SerializedElement blindToken

def Blind(input):
  r = GG.RandomScalar()
  P = GG.HashToGroup(input)
  blindToken = GG.Serialize(r * P)

  token = Token{ data: input, blind: r }

  return (token, blindToken)

Input:

  Token token
  Evaluation Ev

Output:

  SerializedElement issuedToken

def Unblind(token, Ev):
  r = token.blind
  Z = GG.Deserialize(Ev.element)
  N = (r^(-1)) * Z

  issuedToken = GG.Serialize(N)

  return issuedToken

Input:

  Token token
  SerializedElement issuedToken
  opaque info<1..2^16-1>

Output:

  opaque output<1..2^16-1>

def Finalize(token, issuedToken, info):
  finalizeDST = "VOPRF05-Finalize-" || self.contextString
  hashInput = I2OSP(len(token.data), 2) || token.data ||
              I2OSP(len(issuedToken), 2) || issuedToken ||
              I2OSP(len(info), 2) || info ||
              I2OSP(len(finalizeDST), 2) || finalizeDST
  return Hash(hashInput)

Input:

  PublicKey pkS
  SerializedElement blindToken
  Evaluation Ev

Output:

  boolean verified

def VerifyProof(pkS, blindToken, Ev):
  blindTokenList = [blindToken]
  elementList = [Ev.element]

  a = ComputeComposites(pkS, blindTokenList, elementList)

  A' = (ScalarBaseMult(Ev.proof[1]) + Ev.proof[0] * pkS)
  B' = (Ev.proof[1] * M + Ev.proof[0] * Z)
  a2 = GG.Serialize(A')
  a3 = GG.Serialize(B')

  challengeDST = "VOPRF05-challenge-" || self.contextString
  h2Input = I2OSP(len(pkS), 2) || pkS ||
            I2OSP(len(a[0]), 2) || a[0] ||
            I2OSP(len(a[1]), 2) || a[1] ||
            I2OSP(len(a2), 2) || a2 ||
            I2OSP(len(a3), 2) || a3 ||
            I2OSP(len(challengeDST), 2) || challengeDST

  c  = GG.HashToScalar(h2Input)

  return CT_EQUAL(c, Ev.proof[0])

Input:

  PublicKey pkS
  Token token
  SerializedElement blindToken
  Evaluation Ev

Output:

  SerializedElement issuedToken

def Unblind(pkS, token, blindToken, Ev):
  if VerifyProof(pkS, blindToken, Ev) == false:
    ABORT()

  r = token.blind
  Z = GG.Deserialize(Ev.element)
  N = (r^(-1)) * Z

  issuedToken = GG.Serialize(N)

  return issuedToken

4.1. OPRF(ristretto255, SHA-256)

• Group: ristretto255 [RISTRETTO]¶

  • HashToGroup(): hash_to_ristretto255 [I-D.irtf-cfrg-hash-to-curve] with DST = "VOPRF05-" || contextString, where contextString is that which is computed in the Setup functions, and expand_message = expand_message_xmd using SHA-256.¶
  • HashToScalar(): Use hash_to_field from [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime modulus, with L=48, and expand_message_xmd with SHA-256.¶
  • Serialization: Serialization converts group elements to 32-byte strings using the 'Encode' function from [RISTRETTO]. Deserialization converts 32-byte strings to group elements using the 'Decode' function from [RISTRETTO].¶
• Hash: SHA-256¶
• ID: 0x0001¶

4.2. OPRF(decaf448, SHA-512)

• Group: decaf448 [RISTRETTO]¶

  • HashToGroup(): hash_to_decaf448 [I-D.irtf-cfrg-hash-to-curve] with DST = "VOPRF05-" || contextString, where contextString is that which is computed in the Setup functions, and expand_message = expand_message_xmd using SHA-512.¶
  • HashToScalar(): Use hash_to_field from [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime modulus, with L=84, and expand_message_xmd with SHA-512.¶
  • Serialization: Serialization converts group elements to 56-byte strings using the 'Encode' function from [RISTRETTO]. Deserialization converts 56-byte strings to group elements using the 'Decode' function from [RISTRETTO].¶
• Hash: SHA-512¶
• ID: 0x0002¶

4.3. OPRF(P-256, SHA-256)

• Group: P-256 (secp256r1) [x9.62]¶

  • HashToGroup(): P256_XMD:SHA-256_SSWU_RO_ [I-D.irtf-cfrg-hash-to-curve] with DST = "VOPRF05-" || contextString, where contextString is that which is computed in the Setup functions.¶
  • HashToScalar(): Use hash_to_field from [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime modulus, with L=48, and expand_message_xmd with SHA-256.¶
  • Serialization: The compressed point encoding for the curve [SEC1] consisting of 33 bytes.¶
• Hash: SHA-256¶
• ID: 0x0003¶

4.4. OPRF(P-384, SHA-512)

• Group: P-384 (secp384r1) [x9.62]¶

  • HashToGroup(): P384_XMD:SHA-512_SSWU_RO_ [I-D.irtf-cfrg-hash-to-curve] with DST = "VOPRF05-" || contextString, where contextString is that which is computed in the Setup functions.¶
  • HashToScalar(): Use hash_to_field from [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime modulus, with L=72, and expand_message_xmd with SHA-512.¶
  • Serialization: The compressed point encoding for the curve [SEC1] consisting of 49 bytes.¶
• Hash: SHA-512¶
• ID: 0x0004¶

4.5. OPRF(P-521, SHA-512)

• Group: P-521 (secp521r1) [x9.62]¶

  • HashToGroup(): P521_XMD:SHA-512_SSWU_RO_ [I-D.irtf-cfrg-hash-to-curve] with DST = "VOPRF05-" || contextString, where contextString is that which is computed in the Setup functions.¶
  • HashToScalar(): Use hash_to_field from [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime modulus, with L=98, and expand_message_xmd with SHA-512.¶
  • Serialization: The compressed point encoding for the curve [SEC1] consisting of 67 bytes.¶
• Hash: SHA-512¶
• ID: 0x0005¶

5.1. Security properties

The security properties of an OPRF protocol with functionality y = F(k, x) include those of a standard PRF. Specifically:¶

• Pseudorandomness: F is pseudorandom if the output y = F(k,x) on any input x is indistinguishable from uniformly sampling any element in F's range, for a random sampling of k.¶

In other words, consider an adversary that picks inputs x from the domain of F and evaluates F on (k,x) (without knowledge of randomly sampled k). Then the output distribution F(k,x) is indistinguishable from the output distribution of a randomly chosen function with the same domain and range.¶

A consequence of showing that a function is pseudorandom, is that it is necessarily non-malleable (i.e. we cannot compute a new evaluation of F from an existing evaluation). A genuinely random function will be non-malleable with high probability, and so a pseudorandom function must be non-malleable to maintain indistinguishability.¶

An OPRF protocol must also satisfy the following property:¶

• Oblivious: The server must learn nothing about the client's input or the output of the function. In addition, the client must learn nothing about the server's private key.¶

Essentially, obliviousness tells us that, even if the server learns the client's input x at some point in the future, then the server will not be able to link any particular OPRF evaluation to x. This property is also known as unlinkability [DGSTV18].¶

Optionally, for any protocol that satisfies the above properties, there is an additional security property:¶

• Verifiable: The client must only complete execution of the protocol if it can successfully assert that the OPRF output it computes is correct. This is taken with respect to the OPRF key held by the server.¶

Any OPRF that satisfies the 'verifiable' security property is known as a verifiable OPRF, or VOPRF for short. In practice, the notion of verifiability requires that the server commits to the key before the actual protocol execution takes place. Then the client verifies that the server has used the key in the protocol using this commitment. In the following, we may also refer to this commitment as a public key.¶

5.2. Cryptographic security

Below, we discuss the cryptographic security of the (V)OPRF protocol from Section 3, relative to the necessary cryptographic assumptions that need to be made.¶

    Given:
    - G, k * G, G_1, ... , G_N where G, G_1, ... G_N are elements of GG;
    - oracle access to an OPRF functionality using the key k;
    - oracle access to DDH solvers.

    Find Q+1 pairs of the form below:

    (G_{j_s}, k * G_{j_s})

    where the following conditions hold:
      - s is a number between 1 and Q+1;
      - j_s is a number between 1 and N for each s;
      - Q is the number of allowed queries.

    Given G1, G2, h*G2, (h^2)*G2, ..., (h^Q)*G2; for G1 and G2
    generators of GG.

    Output ( (1/(k+c))*G1, c ) where c is an element of FFp

5.3. Hashing to curve

A critical requirement of implementing the prime-order group using elliptic curves is a method to instantiate the function GG.HashToGroup, that maps inputs to group elements. In the elliptic curve setting, this deterministically maps inputs x (as byte arrays) to uniformly chosen points on the curve.¶

In the security proof of the construction Hash is modeled as a random oracle. This implies that any instantiation of GG.HashToGroup must be pre-image and collision resistant. In Section 4 we give instantiations of this functionality based on the functions described in [I-D.irtf-cfrg-hash-to-curve]. Consequently, any OPRF implementation must adhere to the implementation and security considerations discussed in [I-D.irtf-cfrg-hash-to-curve] when instantiating the function.¶

5.4. Timing Leaks

To ensure no information is leaked during protocol execution, all operations that use secret data MUST run in constant time. Operations that SHOULD run in constant time include all prime-order group operations and proof-specific operations (GenerateProof() and VerifyProof()).¶

5.5. Key rotation

Since the server's key is critical to security, the longer it is exposed by performing (V)OPRF operations on client inputs, the longer it is possible that the key can be compromised. For example,if the key is kept in circulation for a long period of time, then it also allows the clients to make enough queries to launch more powerful variants of the Q-sDH attacks from Section 5.2.3.¶

To combat attacks of this nature, regular key rotation should be employed on the server-side. A suitable key-cycle for a key used to compute (V)OPRF evaluations would be between one week and six months.¶

6.1. Preprocess

struct {
  Scalar blind;
  SerializedElement blindedGenerator;
  SerializedElement blindedPublicKey;
} PreprocessedBlind;

Input:

  PublicKey pkS

Output:

  PrepocessedBlind preproc

def Preprocess(pkS):
  PK = GG.Deserialize(pkS)
  r = GG.RandomScalar()
  blindedGenerator = GG.Serialize(ScalarBaseMult(r))
  blindedPublicKey = GG.Serialize(r * PK)

  preproc = PrepocessedBlind{
    blind: r,
    blindedGenerator: blindedGenerator,
    blindedPublicKey: blindedPublicKey,
  }

  return preproc

6.2. Blind

Input:

  ClientInput input
  PreprocessedBlind preproc

Output:

  Token token
  SerializedElement blindToken

def Blind(input, preproc):
  Q = GG.Deserialize(preproc.blindedGenerator) /* Q = ScalarBaseMult(r) */
  P = GG.HashToGroup(input)

  token = Token{
    data: input,
    blind: preproc.blindedPublicKey
  }
  blindToken = GG.Serialize(P + Q)           /* P + ScalarBaseMult(r) */

  return (token, blindToken)

6.3. Unblind

Input:

  Token token
  Evaluation ev
  SerializedElement blindToken

Output:

 SerializedElement unblinded

def Unblind(token, ev, blindToken):
  PKR = GG.Deserialize(token.blind)
  Z = GG.Deserialize(ev.element)
  N := Z - PKR

  issuedToken = GG.Serialize(N)

  return issuedToken

Let P = GG.HashToGroup(x). Notice that Unblind computes:¶

Z - PKR = k * (P + r * G) - r * pkS
        = k * P + k * (r * G) - r * (k * G)
        = k * P

by the commutativity of scalar multiplication in GG. This is the same output as in the Unblind algorithm for multiplicative blinding.¶

Note that the verifiable variant of Unblind works as above but includes the step to VerifyProof, as specified in Section 3.4.4.¶