000230355 001__ 230355
000230355 005__ 20190812205955.0
000230355 020__ $$a978-1-5090-5533-3
000230355 0247_ $$2doi$$a10.1109/Sp.2017.45
000230355 022__ $$a1081-6011
000230355 02470 $$2ISI$$a000413081300025
000230355 037__ $$aCONF
000230355 245__ $$aScalable Bias-Resistant Distributed Randomness
000230355 260__ $$bIeee$$c2017$$aNew York
000230355 269__ $$a2017
000230355 300__ $$a17
000230355 336__ $$aConference Papers
000230355 490__ $$aIEEE Symposium on Security and Privacy
000230355 520__ $$aBias-resistant public randomness is a critical component in many (distributed) protocols. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability, and it depends on the pigeonhole principle to ensure output integrity, even for non-random, adversarial group choices. RandHerd implements an efficient, decentralized randomness beacon. RandHerd is structurally similar to a BFT protocol, but uses RandHound in a one-time setup to arrange participants into verifiably unbiased random secret-sharing groups, which then repeatedly produce random output at predefined intervals. Our prototype demonstrates that RandHound and RandHerd achieve good performance across hundreds of participants while retaining a low failure probability by properly selecting protocol parameters, such as a group size and secret-sharing threshold. For example, when sharding 512 nodes into groups of 32, our experiments show that RandHound can produce fresh random output after 240 seconds. RandHerd, after a setup phase of 260 seconds, is able to generate fresh random output in intervals of approximately 6 seconds. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary.
000230355 6531_ $$adistributed randomness
000230355 6531_ $$averifiable randomness
000230355 6531_ $$arandomness beacon
000230355 6531_ $$asecret sharing
000230355 6531_ $$acollective authority
000230355 700__ $$aSyta, Ewa
000230355 700__ $$0249578$$g264772$$aJovanovic, Philipp Svetolik
000230355 700__ $$0250278$$g254967$$aKokoris Kogias, Eleftherios
000230355 700__ $$0250934$$g195531$$aGailly, Nicolas
000230355 700__ $$0(EPFLAUTH)111443$$g111443$$aGasser, Linus
000230355 700__ $$aKhoffi, Ismail
000230355 700__ $$aFischer, Michael J.
000230355 700__ $$0249220$$g257875$$aFord, Bryan Alexander
000230355 7112_ $$dMay 22-24, 2017$$cSan Jose, California, USA$$a38th IEEE Symposium on Security and Privacy
000230355 773__ $$t2017 Ieee Symposium On Security And Privacy (Sp)$$q444-460
000230355 8564_ $$zIEEE S&P'17 Slides$$yIEEE S&P'17 Slides$$uhttps://infoscience.epfl.ch/record/230355/files/2017-05-23-randomness-ieeesp.pdf$$s2226493
000230355 8564_ $$zPublisher's version$$yPublisher's version$$uhttps://infoscience.epfl.ch/record/230355/files/sp17-final.pdf$$s627274
000230355 909C0 $$xU13061$$pDEDIS$$0252572
000230355 909CO $$ooai:infoscience.tind.io:230355$$qGLOBAL_SET$$pconf$$pIC
000230355 917Z8 $$x264772
000230355 937__ $$aEPFL-CONF-230355
000230355 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000230355 980__ $$aCONF