10
$\begingroup$

I have a network of $N \gg 1$ nodes. Some relatively low fraction $p$ (e.g., $p \simeq 0.01$) of them is under the control of a malicious attacker. Nodes can talk to each others and verify each other's identity (i.e., when a node communicates with another one it can verify the other's identity and membership to the network).

Now, I need my nodes to agree on a random number. It should be the same random number for all the nodes, and it should indeed be random. In other words, the malicious attacker shouldn't be able to steer the distributed random number generation to produce a number of its choice, unless $p$ is larger than some reasonably large amount (e.g. $0.1$).

Is there any way to do so with $O(N \log(N))$ communication complexity? For example, a trivial way of doing this with $O(N^2)$ communication complexity is that each node generates a random number, hashes it with a secure hash and communicates it to all the other nodes. When all the commitments are exchanged, everyone sends out its own random number, and all the numbers are XOR-ed or modulo-summed or so. But this is expensive in terms of communication, and definitely not scalable.

What I need this for

I am developing a peer to peer storage network, where a potentially very large set of nodes contribute to storing each other's data. I am working under the assumption that only that fraction $p$ of the nodes is malicious and willing, e.g., to corrupt or make unavailable some data. Now, I am using a redundancy protocol where a group of, e.g., 36 nodes store each other's data using an erasure code that allows up to 12 nodes to be wiped before the data is lost. This is nicely reliable, as long as the attacker has no way to infiltrate more than $12$ nodes in any specific group. Since $p$ is small, if I have a way of organizing the nodes into groups at random, the probability of any group having more than $12$ malicious nodes is vanishingly small.

This is why I need globally verifiable random numbers: I need all my nodes to be certain that the groups they have been organized into are really random.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Matteo Monti
    Commented Mar 27, 2017 at 13:40
  • $\begingroup$ DO you think our RNG would help? See details from this paper: p4796 Vol. 42, No. 23 / December 1 2017 / Optics Letters (osapublishing.org/ol/abstract.cfm?uri=ol-42-23-4796) $\endgroup$
    – P. Liu
    Commented Mar 27, 2018 at 14:13
  • $\begingroup$ @P.Liu If you would have read the question instead of bluntly throwing your paper to a question just because it contains the word "random", you would have noticed there is a need for a protocol and not an RNG. So, there’s an incredibly big chance that the answer is… no. $\endgroup$
    – e-sushi
    Commented Mar 28, 2018 at 8:10

1 Answer 1

Reset to default
7
$\begingroup$

The commit-then-reveal approach above is not secure as it allows an attacker to bias the output by forcing the protocol to restart. For an overview on generation of distributed unbiasable randomness, checkout our research paper: https://eprint.iacr.org/2016/1067.pdf

A Golang prototype of RandHound, one of the protocols proposed in the above article, is available in the DEDIS cothority project of EPFL: https://github.com/dedis/cothority/tree/master/randhound

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is really cool! Do you know what the communication complexity of RandHerd is? Before diving in the details, I had a look at the abstract but could only find some experimental estimates for very small groups. $\endgroup$
    – Matteo Monti
    Commented Mar 30, 2017 at 16:36
  • $\begingroup$ The asymptotic costs of generating randomness with RandHerd is approximately $O(c^2 \log n) \approx O(\log n)$ for a constant c. Note though that you need to run a one-time setup using RandHound that has asymptotic costs of roughly $O(c^2 n)$. You can find a high-level discussion of the costs in Sections III.A and IV.A, respectively. Hope this helps! $\endgroup$
    – Daeinar
    Commented Apr 2, 2017 at 11:27
  • $\begingroup$ For further clarification: the trick, which is commonly used to scale distributed systems, is to shard the $n$ nodes into smaller subgroups of a constant size $c$ (approximately) and run the randomness generation protocols on the subgroups. The algorithms are designed in such a way that the output verifiably depends on all subgroups. $\endgroup$
    – Daeinar
    Commented Apr 2, 2017 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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