2
$\begingroup$

I've been thinking about verifiable random functions recently due to my interest in sortition (random selection of political officials). I wrote up this little paragraph below, and I'm wondering: Does this paragraph seem accurate? I'm not very confident in my thought process haha as I'm quite a newbie to cryptology and hadn't even heard of a VRF before yesterday.

If you do find problems in what follows, please let me know! I really want to understand at least the very basics of this correctly.


Of course, one time-honored method of random selection is to simply put some names in a big tub and mix them around. However, with recent advances in cryptology more sophisticated mechanisms could be used. In particular, verifiable random functions could be used to choose citizens. In general, the owner of a verifiable random function f employs a secret key and a chosen input x to compute f(x), which is essentially a random value. When x and f(x) are published, the owner also releases a proof that, combined with a previously disseminated public key, allows anyone to confirm that the published value f(x) was indeed correctly computed. However, the public never learns of the secret key and thus cannot evaluate the function for any input other than x. This is in part because verifiable random functions are a kind of “one-way function”: It is easy for the public to check the correctness of an output, but impossible for them to figure out how the function actually operates in general -- thereby preserving the secrecy and integrity of the procedure.

$\endgroup$
1
$\begingroup$

Sure VRFs can be used for sortition. One can say that a party is selected if the output of his VRF satisifies some property.

The VRF outputs two things - a random output and a proof that the output is computed correctly. It is not always the case that if the output of a VRF is f(x) the corresponding proof is x. For example, the VRF could simply output a pseudo random function $PRF_{sk}(x)$ along with a zero knowledge proof that the PRF was computed correctly.

"but impossible for them to figure out how the function actually operates in general" : This would not be accurate, everyone knows how the VRF operates, else how would one verify that the output is actually correct. In cryptography the working of a protocol is never hidden (Kerckhoff's principle)

You can find more information on VRFs here. This is a working IETF draft to standardize the construction of VRFs. They have some interesting constructions there.

Welcome to the community!

$\endgroup$
  • 1
    $\begingroup$ Moreover Algorand (eprint.iacr.org/2017/454) uses sortition to select a committee. This committee achieve consensus over the next block on the block chain. The authors have a nice article on VRFs. You should find that helpful too - medium.com/algorand/… $\endgroup$ – zkvroon Nov 12 '18 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.