A Verifiable Random Function (VRF) allows the owner of a private key the ability to create a hashed value of data, while anyone with the associated public key can prove the validity of the hash. Thus the onwer of the private key can produce \(H(x\) from \(H(x)=f_{priv}(x)\), while someone with the public key can prove that \(H(x)\) is the hash of \(x\). This is similar to the approach of keyed cryptography hashes, but uses public key encryption for the key operation. We will use the method coded by Google and defined in the appendix of [1].
Verifiable Random Function (VRF) |
Background
Initially Alice create a random private key of \(k\). Her public key is then:
\(Q=k \cdot G\)
and where \(G\) is the base point on the curve. Next she selects a random value of \(r\), and then takes a hash of the message (\(m\)) and matches it to the curve:
\(H_x, H_y = H_1(m)\)
Next she computers the \(VRF\) value:
\(VRF = k \cdot H\)
and then creates a scalar value (\(s\)) using the following:
\(s = H_2(G, H, kG, VRF, rG, rH)\)
and:
\(t = r−s.k \pmod N\)
and where \(N\) is the order of the curve. The proof is then \((s, t, VRF)\). To prove, Bob takes Alice's public key (\(kG\)) and computes:
\([t+ks] \cdot G = t \cdot G + s \cdot (kG)\)
Next Bob computes:
\(H = H_1(m)\)
\((t+ks) \cdot H = t \cdot H + s \cdot VRF\)
Now Bob computes:
\(h_2=H_2(G, H, k \cdot G, VRF, t \cdot G + s \cdot (kG), t \cdot H + s \cdot VRF)\)
Bob then checks that \(h_2\) is equal to \(s\). If so, the hash has been proven.
Note that \(H_1()\) hashes the data to a point on the curve, while \(H_2()\) hashes to a scalar value.
Coding
We will use the code defined [here]:
package main import ( "fmt" "os" "github.com/google/keytransparency/core/crypto/vrf/p256" ) func main() { k, pk := p256.GenerateKey() d1 := "This is a test" d2 := "This is not a test" argCount := len(os.Args[1:]) if argCount > 0 { d1 = os.Args[1] } if argCount > 1 { d2 = os.Args[2] } m1 := []byte(d1) m2 := []byte(d2) index1, proof1 := k.Evaluate(m1) index2, proof2 := k.Evaluate(m2) fmt.Printf("== Creation of proofs ===\n") fmt.Printf("Data: [%s] Index: %x Proof: %x\n", m1, index1, proof1) fmt.Printf("Data: [%s] Index: %x Proof: %x\n", m2, index2, proof2) fmt.Printf("\n== Verfication of proofs ===\n") newindex1, _ := pk.ProofToHash(m1, proof1) fmt.Printf("Result 1: %x\n", newindex1) if index1 == newindex1 { fmt.Printf("Proven\n") } newindex2, _ := pk.ProofToHash(m2, proof2) fmt.Printf("Result 2: %x\n", newindex2) if index2 == newindex2 { fmt.Printf("Proven\n") } }
A sample run shows that a valid encryption key produces a valid proof, and then an invalid one generates an incorrect proof:
== Creation of proofs === Data: [hello] Index: 071a928acd52349f74f932c183946b4a8c4d44de59a627e16d3dff2104d5f8d5 Proof: 816851f928f1ff5f15504cffa51e4be12df9ad0ccb67158718db3268d6d6ca3355ad33f888588f7e862ac8ca428e62c775b6063fc7f39751cbedde36689ce01d041173d72b619f3b5ddfe398bab6851ec5870aa29d8bc4655ef8c6a4fb8575f058be8282179f1e90eedfa9ed04837f32dde01c143826db05fcd12a93689c650dbf Data: [hello2] Index: cbdb230c421f0f72d8d5e1c64edbb78cec6c1439448db19f414a93ccaf2f2f2f Proof: a9a7650a7c5decc9a1a10d2d854bb08a183fb3f20c641e3149b15fb55d7cc8bdc72d1ca42b41232ea6453ac186e0fe0ed9c09deedd0e56833fc4e1894567512104ad6c7761e441683e665fcafbbbe1dfa298404ae835a740ec26d72585f4ecf860993ce99512e16ef7b7abe357891f03cd04e10652d781e2dd440661adec7cd2ab == Verfication of proofs === Result 1: 071a928acd52349f74f932c183946b4a8c4d44de59a627e16d3dff2104d5f8d5 Proven Result 2: cbdb230c421f0f72d8d5e1c64edbb78cec6c1439448db19f414a93ccaf2f2f2f Proven
Coding
Reference
[1] Melara, M. S., Blankstein, A., Bonneau, J., Felten, E. W., & Freedman, M. J. (2015). {CONIKS}: Bringing Key Transparency to End Users. In 24th {USENIX} Security Symposium ({USENIX} Security 15) (pp. 383-398).