Protocols Tutorial

Example: Verifiable oblivious pseudorandom function (VOPRF)

In this notebook, we’ll take a look at how to implement a simple protocol: VOPRFs (based on this paper).

🗒 The basic setup

A VOPRF is, first and foremost, a PRF. The secret key \(k\) for the PRF is a random scalar and we’ll call \(h = g^k\) the “public key”. The values of the \(\mathrm{PRF}_k: \{0,1\}^* \rightarrow \{0,1\}^n\) are

\[\mathrm{PRF}_k(x) = H_2(h, x, H_1(x)^k)\]

where \(H_1:\{0,1\}^*\rightarrow \mathbb{G}\), \(H_2:\{0,1\}^* \rightarrow \{0,1\}^n\) are hash functions modeled as random oracles.

This is a PRF because under appropriate (Diffie-Hellman-type) assumptions (essentially the only way to distinguish a PRF-value \(\mathrm{PRF}_k(x)\) from random is to compute \(H_1(x)^k\) without knowing \(k\)).

🥸 How to obliviously retrieve function values

Now in an oblivious PRF, there is a protocol between two parties: the issuer and the user. The issuer holds a PRF key \(k\) and publishes the public key \(h = g^k\). The user wants to retrieve \(\mathrm{PRF}(x)\) for some bit string \(x\in\{0,1\}^*\) from the issuer without revealing \(x\). In our case, this protocol works as follows:

• The user chooses a random scalar \(r\) and sends \(a = H_1(x)^r\) to the issuer.
• The issuer replies with \(a^k\) and a zero-knowledge proof that he has used the right \(k\) to compute \(a^k\).

Note that in this protocol, the user only sends a random value \(a\) that holds no information about \(x\), so the issuer cannot learn \(x\). The zero-knowledge proof ensures that the issuer cannot send incorrect responses (which he might otherwise do to “tag” requests).

---

Note: You can also check this page out in an interactive Jupyter notebook by clicking the badge below:

---

📡 Implementation - Setup

So let’s implement this using our library. First, let’s do the basic setup.

%maven org.cryptimeleon:math:3.+
%maven org.cryptimeleon:craco:3.+

import org.cryptimeleon.math.structures.groups.elliptic.nopairing.*;
import org.cryptimeleon.math.structures.groups.lazy.*;
import org.cryptimeleon.math.hash.impl.SHA256HashFunction;
import org.cryptimeleon.math.structures.rings.zn.Zn;
import org.cryptimeleon.math.hash.impl.ByteArrayAccumulator;
import org.cryptimeleon.math.structures.groups.*;
import org.cryptimeleon.math.serialization.converter.JSONPrettyConverter;
import org.cryptimeleon.craco.protocols.arguments.sigma.schnorr.*;
import org.cryptimeleon.craco.protocols.arguments.sigma.*;
import org.cryptimeleon.craco.protocols.*;
import org.cryptimeleon.craco.protocols.arguments.fiatshamir.FiatShamirProofSystem;

//Set up group and generate key
var group = new Secp256k1(); 
var H1 = new HashIntoSecp256k1();
var H2 = new SHA256HashFunction();
var jsonConverter = new JSONPrettyConverter(); //for serialization later

var g = group.getGenerator();
var k = group.getUniformlyRandomNonzeroExponent(); //secret key
var h = g.pow(k).precomputePow(); //public key

With this setup, we can naively (without hiding x) evaluate \(\mathrm{PRF}_k(x) = H_2(h, x, H_1(x)^k)\) as follows:

byte[] evaluatePRF(Zn.ZnElement k, byte[] x) {
    var h2Preimage = new ByteArrayAccumulator();
    h2Preimage.escapeAndSeparate(h);
    h2Preimage.escapeAndSeparate(x);
    h2Preimage.escapeAndAppend(H1.hash(x).pow(k));
    
    return H2.hash(h2Preimage.extractBytes());
}

var result = evaluatePRF(k, new byte[] {4, 8, 15, 16, 23, 42});
Arrays.toString(result)

[20, 59, 6, -90, -45, -92, 56, -23, -79, -106, -92, 26, -78, -37, 105, -37, -96, -65, -65, 49, 123, 79, 117, -42, -34, 111, 13, 40, 48, -42, 45, -118]

↔️ Implementation - Zero-knowledge proof

To implement the oblivious evaluation protocol, we start with the subprotocol to prove that the issuer’s response is valid. Specifically, when the issuer gets \(a\) and replies with \(b = a^k\), he needs to prove knowledge of \(k\) such that \(b = a^k \land h = g^k\), i.e. \(a\) was exponentiated with the correct secret key belonging to public key \(h\). In Camenisch-Stadler notation:

\[\mathrm{ZKPoK}\{(k) :\ b = a^k \land h = g^k\}\]

For this, we implement our own Schnorr-style protocol. Within the protocol framework of our library, we think of Schnorr-style protocols as being composed of “fragments”. In our case, the protocol will consist of two fragments, one that handes the \(b = a^k\) part, one that handles the \(h = g^k\) part (in general, fragments can also handle more complicated statements, such as “\(z \leq 100\)”, but those are not needed in this example).

Essentially, what we want is a DelegateProtocol, i.e. one that delegates its functionality to two sub-“fragments”. For this protocol, we need to define mostly two things:

1. which variables/witnesses are proven knowledge of and which subprotocols (fragments) shall be instantiated? (we call this the subprotocol spec)
2. which value(s) for the witness(es) shall the prover use? (we call this the prover spec)

With this defined, composing this into a Schnorr-style protocol is done automatically behind the scenes.

class ProofCommonInput implements CommonInput {
    public final GroupElement a,b;
    
    public ProofCommonInput(GroupElement a, GroupElement b) {
        this.a = a;
        this.b = b;
    }
}

class ProofWitnessInput implements SecretInput {
    public final Zn.ZnElement k;
    
    public ProofWitnessInput(Zn.ZnElement k) {
        this.k = k;
    }
}

class ReplyCorrectnessProof extends DelegateProtocol {
    @Override
    protected SendThenDelegateFragment.SubprotocolSpec provideSubprotocolSpec(CommonInput commonInput, SendThenDelegateFragment.SubprotocolSpecBuilder builder) {
        //In this method, we define (for prover and verifier alike) what the proof parameters shall be.
        //We want to prove knowledge of a single variable, namely k. So we register "k" of type Zp with the builder.
        var kVar = builder.addZnVariable("k", group.getZn());
        //the result is a variable kVar that we will reference in the following.
        
        //Now we need to define what shall be proven. For this, we reference the knowledge variable created above.

        //statementToBeProven is an Expression "a^k = b" with variable k (not something that's computed here and now)
        var statementToBeProven = ((ProofCommonInput) commonInput).a.pow(kVar).isEqualTo(((ProofCommonInput) commonInput).b); 
        
        //With this expression format we tell the framework to add the fragment for "a^k = b" to the proof
        builder.addSubprotocol("replyCorrect", new LinearStatementFragment(statementToBeProven));

        //Similarly, we handle the other fragment
        builder.addSubprotocol("publicKeyCorrect", new LinearStatementFragment(g.pow(kVar).isEqualTo(h)));

        //Aaaand that's it :) - We have defined to prove knowledge of k such that a^k = b and g^k = h.
        return builder.build();
    }
    
    @Override
    protected SendThenDelegateFragment.ProverSpec provideProverSpecWithNoSendFirst(CommonInput commonInput, SecretInput secretInput, SendThenDelegateFragment.ProverSpecBuilder builder) {
        //Here, we need to set up which witnesses the issuer shall use, i.e. their secret key.
        //For every builder.addZnVariable() above, we must set the witness here (usually from secretInput)
        builder.putWitnessValue("k", ((ProofWitnessInput) secretInput).k);
        
        //That's it already, that's all the additional info the prover needs.
        return builder.build();
    }

    @Override
    public ZnChallengeSpace getChallengeSpace(CommonInput commonInput) {
        return new ZnChallengeSpace(group.getZn());
    }
}

//Wrap the sigma protocol into a Fiat-Shamir proof system
var fiatShamirProofSystem = new FiatShamirProofSystem(new ReplyCorrectnessProof());

🛠 Implementing the rest

We’re now ready to implement the rest of the protocol.

🙋 Client’s request

Let’s start with the user’s first message \(a = H_1(x)^r\).

//User's perspective

byte[] x = new byte[] {4, 8, 15, 16, 23, 42}; //want PRF(x)

var r = group.getUniformlyRandomExponent();
GroupElement a = H1.hash(x).pow(r);

//Send (serialized) group element
String messageOverTheWire = jsonConverter.serialize(a.getRepresentation());
messageOverTheWire

{
   "__type":"OBJ",
   "x":"INT:649a44705380f3aa9536b8273b3aa19b50425e6d8b9c9a39e71e8f44ce0b2d8b",
   "y":"INT:8670be17436dbfc8c22b716f04f4e5f49931a8fa3c501bb7cd44446cc3c5410a",
   "z":"INT:1"
}

💁 Server’s response

Now the server responds with \(b = a^k\) as well as a proof of correctness.

//Server's perspective

//Deserialize the request (also ensures the request is a valid group element)
GroupElement aServer = group.restoreElement(jsonConverter.deserialize(messageOverTheWire));

//Compute the response
var bServer = aServer.pow(k);

//Compute the proof
var proofServer = fiatShamirProofSystem.createProof(new ProofCommonInput(aServer,bServer), new ProofWitnessInput(k));

//Send response
var responseRepresentation = new org.cryptimeleon.math.serialization.ListRepresentation(bServer.getRepresentation(), proofServer.getRepresentation());
var responseOverTheWire = jsonConverter.serialize(responseRepresentation);
responseOverTheWire

[
   {
      "__type":"OBJ",
      "x":"INT:c741f91859dbf31a7d524da17eba114959fbd0474bd4cc2996d37d52384a6918",
      "y":"INT:2705d756f741706b3dc37530a7cea07d79353b603df5e59ca214acf77e24bd6f",
      "z":"INT:1"
   },
   {
      "__type":"OBJ",
      "challenge":"INT:1e69e9299833ef4065a99d7134ef219d80e4abbc470b997c577a2f8119d1b6a",
      "transcript":[
         null,
         [
            "INT:4174cacd7065719e394d742c54c3055d4176a612d7c8a161b22a6bc817c75898"
         ],
         null,
         null
      ]
   }
]

🧑‍🎓 Client unblinding and proof check

Now the client checks the proof and unblinds \(b\) as \(b^{1/r}\), getting \(H_1(x)^k\) and computing the PRF value from that.

//Deserialize stuff
var deserializedResponse = jsonConverter.deserialize(responseOverTheWire);
var b = group.restoreElement(deserializedResponse.list().get(0));

//Check proof
var commonInput = new ProofCommonInput(a,b); //set common input for proof
var proof = fiatShamirProofSystem.restoreProof(commonInput, deserializedResponse.list().get(1)); //deserialize proof
assert fiatShamirProofSystem.checkProof(commonInput, proof); //check proof

//Unblind b and compute PRF value
var h2Preimage = new ByteArrayAccumulator();
h2Preimage.escapeAndSeparate(h);
h2Preimage.escapeAndSeparate(x);
h2Preimage.escapeAndAppend(b.pow(r.inv()));

var result = H2.hash(h2Preimage.extractBytes());
Arrays.toString(result)

[20, 59, 6, -90, -45, -92, 56, -23, -79, -106, -92, 26, -78, -37, 105, -37, -96, -65, -65, 49, 123, 79, 117, -42, -34, 111, 13, 40, 48, -42, 45, -118]

✅ Done.

Thanks for looking at this tutorial 🙂