A publicly verifiable protocol for random number generation
Resumo
Chance plays an essential role in many decision procedures such as lotteries, draws etc. As such procedures are moving on-line, several web services offering randomness have appeared over the last few years. NIST’s randomness beacon, which publishes a sequence of 512 random bytes every minute, unfortunately lacks transparency: the beacon does not eliminate the possibility of an insider attack who knows the outcomes beforehand. We propose an improvement of NIST’s beacon which is publicly verifiable and fully transparent: any outsider who did not witness the bit generation in person but has internet access can convince himself that the beacon acted honestly, provided he can be sure that fresh, independent random bits were contributed to the seed value. Our proposal is based on a novel cryptographic assumption: the existence of functions that are slow to compute even on the fastest supercomputers.Referências
BBC (1999). Italy hit by lottery scandal. http://news.bbc.co.uk/1/hi/world/europe/256206.stm.
Biryukov, A., Dinu, D., and Khovratovich, D. (2016). Argon2: New generation of memory-hard functions for password hashing and other applications. In IEEE European Symposium on Security and Privacy, EuroS&P 2016, pages 292–302.
Blum, M. (1983). Coin Flipping by Telephone a Protocol for Solving Impossible Problems. SIGACT News, 15(1):23–27.
Fischer, M. J., Iorga, M., and Peralta, R. (2011). A public randomness service. In SECRYPT 2011, pages 434–438.
Lenstra, A. K. and Wesolowski, B. (2015). A random zoo: sloth, unicorn, and trx. IACR Cryptology ePrint Archive, 2015:366.
NIST (2016). Truly random numbers – but not by chance. https://www.nist.gov/news-events/news/2012/10/truly-random-numbers-not-chance.
Rabin, M. O. (1983). Transaction protection by beacons. J. Comput. Syst. Sci., 27(2):256–267.
Simmons, D. (2015). Us lottery security boss charged with fixing draw. http://www.bbc.com/news/technology-32301117.
Syta, E., Jovanovic, P., Kokoris-Kogias, E., Gailly, N., Gasser, L., Khoffi, I., Fischer,
M. J., and Ford, B. (2017). Scalable bias-resistant distributed randomness. In IEEE Symposium on Security and Privacy, pages 444–460.
Togyer, J. (1999). Putting in the fix. http://www.tubecityonline.com/history/perry.html.
Biryukov, A., Dinu, D., and Khovratovich, D. (2016). Argon2: New generation of memory-hard functions for password hashing and other applications. In IEEE European Symposium on Security and Privacy, EuroS&P 2016, pages 292–302.
Blum, M. (1983). Coin Flipping by Telephone a Protocol for Solving Impossible Problems. SIGACT News, 15(1):23–27.
Fischer, M. J., Iorga, M., and Peralta, R. (2011). A public randomness service. In SECRYPT 2011, pages 434–438.
Lenstra, A. K. and Wesolowski, B. (2015). A random zoo: sloth, unicorn, and trx. IACR Cryptology ePrint Archive, 2015:366.
NIST (2016). Truly random numbers – but not by chance. https://www.nist.gov/news-events/news/2012/10/truly-random-numbers-not-chance.
Rabin, M. O. (1983). Transaction protection by beacons. J. Comput. Syst. Sci., 27(2):256–267.
Simmons, D. (2015). Us lottery security boss charged with fixing draw. http://www.bbc.com/news/technology-32301117.
Syta, E., Jovanovic, P., Kokoris-Kogias, E., Gailly, N., Gasser, L., Khoffi, I., Fischer,
M. J., and Ford, B. (2017). Scalable bias-resistant distributed randomness. In IEEE Symposium on Security and Privacy, pages 444–460.
Togyer, J. (1999). Putting in the fix. http://www.tubecityonline.com/history/perry.html.
Publicado
06/11/2017
Como Citar
PENNA, João; VAN DE GRAAF, Jeroen.
A publicly verifiable protocol for random number generation. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 17. , 2017, Brasília.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 525-532.
DOI: https://doi.org/10.5753/sbseg.2017.19527.
