{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Example: Verifiable oblivious pseudorandom function (VOPRF)\n", "\n", "In this notebook, we'll take a look at how to implement a simple protocol: [VOPRFs](https://datatracker.ietf.org/doc/draft-irtf-cfrg-voprf/) (based on this [paper](https://eprint.iacr.org/2014/650)).\n", "\n", "## 🗒 The basic setup\n", "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\". \n", "The values of the $\\mathrm{PRF}_k: \\{0,1\\}^* \\rightarrow \\{0,1\\}^n$ are \n", "$$\\mathrm{PRF}_k(x) = H_2(h, x, H_1(x)^k)$$ \n", "where $H_1:\\{0,1\\}^*\\rightarrow \\mathbb{G}$, $H_2:\\{0,1\\}^* \\rightarrow \\{0,1\\}^n$ are hash functions modeled as random oracles.\n", "\n", "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$).\n", "\n", "## 🥸 How to obliviously retrieve function values\n", "\n", "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:\n", "\n", "- The user chooses a random scalar $r$ and sends $a = H_1(x)^r$ to the issuer.\n", "- The issuer replies with $a^k$ and a zero-knowledge proof that he has used the right $k$ to compute $a^k$.\n", "\n", "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)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 📡 Implementation - Setup\n", "\n", "So let's implement this using our library. First, let's do the basic setup. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "%maven org.cryptimeleon:math:3.+\n", "%maven org.cryptimeleon:craco:3.+\n", "\n", "import org.cryptimeleon.math.structures.groups.elliptic.nopairing.*;\n", "import org.cryptimeleon.math.structures.groups.lazy.*;\n", "import org.cryptimeleon.math.hash.impl.SHA256HashFunction;\n", "import org.cryptimeleon.math.structures.rings.zn.Zn;\n", "import org.cryptimeleon.math.hash.impl.ByteArrayAccumulator;\n", "import org.cryptimeleon.math.structures.groups.*;\n", "import org.cryptimeleon.math.serialization.converter.JSONPrettyConverter;\n", "import org.cryptimeleon.craco.protocols.arguments.sigma.schnorr.*;\n", "import org.cryptimeleon.craco.protocols.arguments.sigma.*;\n", "import org.cryptimeleon.craco.protocols.*;\n", "import org.cryptimeleon.craco.protocols.arguments.fiatshamir.FiatShamirProofSystem;\n", "\n", "//Set up group and generate key\n", "var group = new Secp256k1(); \n", "var H1 = new HashIntoSecp256k1();\n", "var H2 = new SHA256HashFunction();\n", "var jsonConverter = new JSONPrettyConverter(); //for serialization later\n", "\n", "var g = group.getGenerator();\n", "var k = group.getUniformlyRandomNonzeroExponent(); //secret key\n", "var h = g.pow(k).precomputePow(); //public key" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "With this setup, we can naively (without hiding x) evaluate $\\mathrm{PRF}_k(x) = H_2(h, x, H_1(x)^k)$ as follows:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "byte[] evaluatePRF(Zn.ZnElement k, byte[] x) {\n", " var h2Preimage = new ByteArrayAccumulator();\n", " h2Preimage.escapeAndSeparate(h);\n", " h2Preimage.escapeAndSeparate(x);\n", " h2Preimage.escapeAndAppend(H1.hash(x).pow(k));\n", " \n", " return H2.hash(h2Preimage.extractBytes());\n", "}" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "var result = evaluatePRF(k, new byte[] {4, 8, 15, 16, 23, 42});\n", "Arrays.toString(result)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## ↔️ Implementation - Zero-knowledge proof\n", "\n", "To implement the oblivious evaluation protocol, we start with the subprotocol to prove that the issuer's response is valid. \n", "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:\n", "$$ \\mathrm{ZKPoK}\\{(k) :\\ b = a^k \\land h = g^k\\} $$\n", "\n", "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).\n", "\n", "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:\n", "\n", "1. which variables/witnesses are proven knowledge of and which subprotocols (fragments) shall be instantiated? (we call this the *subprotocol spec*)\n", "2. which value(s) for the witness(es) shall the prover use? (we call this the *prover spec*)\n", "\n", "With this defined, composing this into a Schnorr-style protocol is done automatically behind the scenes." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class ProofCommonInput implements CommonInput {\n", " public final GroupElement a,b;\n", " \n", " public ProofCommonInput(GroupElement a, GroupElement b) {\n", " this.a = a;\n", " this.b = b;\n", " }\n", "}\n", "\n", "class ProofWitnessInput implements SecretInput {\n", " public final Zn.ZnElement k;\n", " \n", " public ProofWitnessInput(Zn.ZnElement k) {\n", " this.k = k;\n", " }\n", "}\n", "\n", "class ReplyCorrectnessProof extends DelegateProtocol {\n", " @Override\n", " protected SendThenDelegateFragment.SubprotocolSpec provideSubprotocolSpec(CommonInput commonInput, SendThenDelegateFragment.SubprotocolSpecBuilder builder) {\n", " //In this method, we define (for prover and verifier alike) what the proof parameters shall be.\n", " //We want to prove knowledge of a single variable, namely k. So we register \"k\" of type Zp with the builder.\n", " var kVar = builder.addZnVariable(\"k\", group.getZn());\n", " //the result is a variable kVar that we will reference in the following.\n", " \n", " //Now we need to define what shall be proven. For this, we reference the knowledge variable created above.\n", "\n", " //statementToBeProven is an Expression \"a^k = b\" with variable k (not something that's computed here and now)\n", " var statementToBeProven = ((ProofCommonInput) commonInput).a.pow(kVar).isEqualTo(((ProofCommonInput) commonInput).b); \n", " \n", " //With this expression format we tell the framework to add the fragment for \"a^k = b\" to the proof\n", " builder.addSubprotocol(\"replyCorrect\", new LinearStatementFragment(statementToBeProven));\n", "\n", " //Similarly, we handle the other fragment\n", " builder.addSubprotocol(\"publicKeyCorrect\", new LinearStatementFragment(g.pow(kVar).isEqualTo(h)));\n", "\n", " //Aaaand that's it :) - We have defined to prove knowledge of k such that a^k = b and g^k = h.\n", " return builder.build();\n", " }\n", " \n", " @Override\n", " protected SendThenDelegateFragment.ProverSpec provideProverSpecWithNoSendFirst(CommonInput commonInput, SecretInput secretInput, SendThenDelegateFragment.ProverSpecBuilder builder) {\n", " //Here, we need to set up which witnesses the issuer shall use, i.e. their secret key.\n", " //For every builder.addZnVariable() above, we must set the witness here (usually from secretInput)\n", " builder.putWitnessValue(\"k\", ((ProofWitnessInput) secretInput).k);\n", " \n", " //That's it already, that's all the additional info the prover needs.\n", " return builder.build();\n", " }\n", "\n", " @Override\n", " public ZnChallengeSpace getChallengeSpace(CommonInput commonInput) {\n", " return new ZnChallengeSpace(group.getZn());\n", " }\n", "}\n", "\n", "//Wrap the sigma protocol into a Fiat-Shamir proof system\n", "var fiatShamirProofSystem = new FiatShamirProofSystem(new ReplyCorrectnessProof());" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 🛠 Implementing the rest\n", "\n", "We're now ready to implement the rest of the protocol. \n", "\n", "### 🙋 Client's request\n", "Let's start with the user's first message $a = H_1(x)^r$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "//User's perspective\n", "\n", "byte[] x = new byte[] {4, 8, 15, 16, 23, 42}; //want PRF(x)\n", "\n", "var r = group.getUniformlyRandomExponent();\n", "GroupElement a = H1.hash(x).pow(r);\n", "\n", "//Send (serialized) group element\n", "String messageOverTheWire = jsonConverter.serialize(a.getRepresentation());\n", "messageOverTheWire" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 💁 Server's response\n", "\n", "Now the server responds with $b = a^k$ as well as a proof of correctness." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "//Server's perspective\n", "\n", "//Deserialize the request (also ensures the request is a valid group element)\n", "GroupElement aServer = group.restoreElement(jsonConverter.deserialize(messageOverTheWire));\n", "\n", "//Compute the response\n", "var bServer = aServer.pow(k);\n", "\n", "//Compute the proof\n", "var proofServer = fiatShamirProofSystem.createProof(new ProofCommonInput(aServer,bServer), new ProofWitnessInput(k));\n", "\n", "//Send response\n", "var responseRepresentation = new org.cryptimeleon.math.serialization.ListRepresentation(bServer.getRepresentation(), proofServer.getRepresentation());\n", "var responseOverTheWire = jsonConverter.serialize(responseRepresentation);\n", "responseOverTheWire" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 🧑‍🎓 Client unblinding and proof check\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "//Deserialize stuff\n", "var deserializedResponse = jsonConverter.deserialize(responseOverTheWire);\n", "var b = group.restoreElement(deserializedResponse.list().get(0));\n", "\n", "//Check proof\n", "var commonInput = new ProofCommonInput(a,b); //set common input for proof\n", "var proof = fiatShamirProofSystem.restoreProof(commonInput, deserializedResponse.list().get(1)); //deserialize proof\n", "assert fiatShamirProofSystem.checkProof(commonInput, proof); //check proof\n", "\n", "//Unblind b and compute PRF value\n", "var h2Preimage = new ByteArrayAccumulator();\n", "h2Preimage.escapeAndSeparate(h);\n", "h2Preimage.escapeAndSeparate(x);\n", "h2Preimage.escapeAndAppend(b.pow(r.inv()));\n", "\n", "var result = H2.hash(h2Preimage.extractBytes());\n", "Arrays.toString(result)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## ✅ Done.\n", "\n", "Thanks for looking at this tutorial 🙂" ] } ], "metadata": { "kernelspec": { "display_name": "Java", "language": "java", "name": "java" }, "language_info": { "codemirror_mode": "java", "file_extension": ".jshell", "mimetype": "text/x-java-source", "name": "Java", "pygments_lexer": "java", "version": "15.0.2+7" } }, "nbformat": 4, "nbformat_minor": 4 }