Implement Oblivious Pseudo Random Functions

[lognorman20]

Overview

An Oblivious Pseudorandom Function (OPRF) is a two-party protocol between client and server for computing the output of a Pseudorandom Function (PRF). The server provides the PRF private key, and the client provides the PRF input. At the end of the protocol, the client learns the PRF output without learning anything about the PRF private key, and the server learns neither the PRF input nor output. An OPRF can also satisfy a notion of 'verifiability', called a VOPRF. A VOPRF ensures clients can verify that the server used a specific private key during the execution of the protocol.

The birds-eye view of the OPRf algorithm is to have the following interaction between a client C and a server S:

1. S & C choose a PRF G to commonly refer to
2. S chooses a private server constant k
3. C generates a private key x
4. C concatenates the x with some random constant r to produce a
5. C encrypts input message d with a to produce some blind token b
6. C sends b over to S
7. S evaluates b k G and passes it as an output o back to C
8. C verifies o by multiplying o by the inverse of r

Proposed Implementation

I aim to create a variation of the methodology used in this paper.

Data Structures

PrivateInput: inputs that are known only to the client in the protocol

PublicInput: inputs that are known to both client and server in the protocol

Opaque: byte strings of arbitrary length no larger than 2^16 - 1 bytes. This length restriction exists because PublicInput and PrivateInput values are length-prefixed with two bytes before use throughout the protocol.

Proof: stores the secret key and the output?

OPRFServerContext: data structure that stores a context string and the relevant key material for each party

OPRFClientContext: data structure that stores a context string and the relevant key material for each party

Group: An implementation of a Prime-Order Group. This is to help generate constants/scalars easily and quickly. Further, it allows for easy key generation. This API will have the following functions:

• Order(): Outputs the order of the group (i.e. p)
• Identity(): Outputs the identity element of the group (i.e. I)
• Generator(): Outputs the generator element of the group.
• HashToGroup(x): Deterministically maps an array of bytes x to an element of Group. The map must ensure that, for any adversary receiving R = HashToGroup(x), it is computationally difficult to reverse the mapping. This function is optionally parameterized by a domain separation tag (DST)
• HashToScalar(x): Deterministically maps an array of bytes x to an element in GF(p). This function is optionally parameterized by a DST
• RandomScalar(): Chooses at random a non-zero element in GF(p).
• ScalarInverse(s): Returns the inverse of input Scalar s on GF(p)
• SerializeElement(A): Maps an Element A to a canonical byte array buf of fixed length Ne.
• DeserializeElement(buf): Attempts to map a byte array buf to an Element A, and fails if the input is not the valid canonical byte representation of an element of the group. This function can raise a DeserializeError if deserialization fails or A is the identity element of the group
• SerializeScalar(s): Maps a Scalar s to a canonical byte array buf of fixed length Ns.
• DeserializeScalar(buf): Attempts to map a byte array buf to a Scalar s. This function can raise a DeserializeError if deserialization fails for group-specific input validation steps.

Functionality

Pseudocode of Protocol:

Client blinds input with Blind(input), stores locally, and sends to the server

Server processes blindedInput using BlindEvalutate() and sends output back to client

Client processes evaluatedInput with Finalize()

(Optional?) An entity which knows both the private key and the input can compute the PRF result using the Evaluate() function

Regarding the Group API Implementation, there are many different Cipher-suites to choose from in the paper. I'm not sure which one to pick, nor do I fully understand the tradeoffs of each yet, so I'd have to investigate this further.

Following the necessary functions from here

Input: PrivateInput input 
Output: Scalar blind Element blindedElement Parameters: Group G 
Errors: InvalidInputError 

def Blind(input): blind = G.RandomScalar() 
    inputElement = G.HashToGroup(input) 
    if inputElement == G.Identity(): 
        raise InvalidInputError blindedElement = blind * inputElement       
    return blind, blindedElement

Input: Scalar skS Element blindedElement 
Output: Element evaluatedElement 
def BlindEvaluate(skS, blindedElement): 
    evaluatedElement = skS * blindedElement 
    return evaluatedElement

Input: 
PrivateInput input 
Scalar blind 
Element evaluatedElement 
Output: opaque output[Nh] 
Parameters: Group G 
def Finalize(input, blind, evaluatedElement): 
    N = G.ScalarInverse(blind) * evaluatedElement 
    unblindedElement = G.SerializeElement(N) 
    hashInput = I2OSP(len(input), 2) || input || I2OSP(len(unblindedElement), 2) || unblindedElement || "Finalize" 
    return Hash(hashInput)

Input: 
Scalar skS
PrivateInput input
Output: opaque output[Nh]

Parameters: Group G
Errors: InvalidInputError

def Evaluate(skS, input):
    inputElement = G.HashToGroup(input)
    if inputElement == G.Identity():
        raise InvalidInputError
    evaluatedElement = skS * inputElement
    issuedElement = G.SerializeElement(evaluatedElement)
    hashInput = I2OSP(len(input), 2) || input || I2OSP(len(issuedElement), 2) || issuedElement || "Finalize"
    return Hash(hashInput)

References

These papers gave me some background on OPRFs

• https://cfrg.github.io/draft-irtf-cfrg-voprf/draft-irtf-cfrg-voprf.html#name-online-protocol
• https://www.ietf.org/archive/id/draft-irtf-cfrg-voprf-05.html#name-overview
• https://www.iacr.org/archive/tcc2009/54440575/54440575.pdf
• https://eprint.iacr.org/2016/799.pdf

This VOPRF implementation in Rust by Facebook engineers

• https://docs.rs/voprf/latest/voprf/

[nanaknihal]

@lognorman20 this is great -- thank you. I think we can do something simpler such as the 2HashDH OPRF, covered in a section of https://eprint.iacr.org/2022/302.pdf. The reason why is

• It is extremely efficient to compute
• It is amenable to MPC
• Simplicity is safest

2HashDH is where we are working in some predefined curve (such as BabyJubJub or secp256k1) of order n with generator G. There is also a hash function H. For this, let's use blake512 or sha512, mod n.

Server always has key k and Client has input x, which they want the PRF of. The PRF is the function PRF(x,k) = H(H(x)kG). Let's see how this it works:

1. Client calculates a random value r and sends Server r*H(x)*G. Note Server learns no information at all about r or H(x) from this value.
2. Server multiplies this by his private key to get r*H(x)*k*G and returns this value. Note this does not reveal the private key due to discrete logarithm assumption.
3. Client multiplies by r^-1 to retrieve H(X)kG
4. Client hashes this value

Just now noticed there's an implementation it here https://github.com/multiparty/oprf/blob/master/src/oprf.slim.ts which is pretty cool. It still would be nice to have the same in babyjubjub library though so we can do it with our MPC network eventually.