A Decentralized Online Sortition Protocol

Ramezanian, R.; Pourpouneh, M.

doi:10.22042/isecure.2018.113240.403

A Decentralized Online Sortition Protocol

Document Type : Research Article

Authors

R. Ramezanian ¹

M. Pourpouneh ²

¹ Ferdowsi University of Mashhad, Department of Mathematical Sciences, Mashhad, Iran

² Sharif University of Technology, Department of Mathematical Sciences, Tehran, Iran

https://doi.org/10.22042/isecure.2018.113240.403

Abstract

We propose a new online sortition protocol which is decentralized. We argue that our protocol has safety, fairness, randomness, non-reputation and openness properties. Sortition is a process that makes random decision and it is used in competitions and lotteries to determine who is the winner. In the real world, sortition is simply done using a lottery machine and all the participant can be sure about the safety, fairness, randomness, non-reputation, and openness properties. But how we can do the sortition in virtual world such that it satisﬁes the desired properties? The idea is decentralization. Using cryptography notions, we provide a protocol where all agents participate in computing the winner of sortition. Our proposed protocol is novel and completely differs from other sortition protocols and also it is decentralized. It is simple and easily can be implemented and find the commercial use for those markets who want to give present to their customers in a fair and clear manner.

Keywords

Sortition

Protocols

Mechanism Design

20.1001.1.20082045.2018.10.1.7.9

[1] Atila Abdulkadiroglu and Tayfun Sönmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3):689–701, 1998.
[2] Yeon-Koo Che and Fuhito Kojima. Asymptotic equivalence of probabilistic serial and random priority mechanisms. Econometrica, 78(5):1625–1672, 2010.
[3] Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 129–140. ACM, 1999.
[4] Kenneth J Arrow, Amartya Sen, and Kotaro Suzumura. Handbook of social choice and welfare, volume 2. Elsevier, 2010.
[5] Felix Brandt, Vincent Conitzer, Ulle Endriss, Ariel D Procaccia, and Jérôme Lang. Handbook of computational social choice. Cambridge University Press, 2016.
[6] Atila Abdulkadiroglu and Tayfun Sönmez.School choice: A mechanism design approach. The American Economic Review, 93(3):729–747, 2003.
[7] Rafik Makhloufi, Grégory Bonnet, Guillaume Doyen, and Dominique Gaïti. Decentralized aggregation protocols in peer-to-peer networks: a survey. In IEEE International Workshop on Modelling Autonomic Communications Environments,
pages 111–116. Springer, 2009.
[8] JA Alvarez Bermejo, MA Lodroman, and JA Lopez-Ramos. A decentralized protocol for mobile control access. The Journal of Supercomputing,70(2):709–720, 2014.
[9] Airlie Chapman, Eric Schoof, and Mehran Mesbahi.Semi-autonomous networks: theory and decentralized protocols. In Robotics and Automation(ICRA), 2010 IEEE International Conference on, pages 1958–1963. IEEE, 2010.
[10] Manuel Blum. Coin flipping by telephone a protocol for solving impossible problems. ACM SIGACT News, 15(1):23–27, 1983.
[11] Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 73–85. ACM, 1989.
[12] Richard Cleve. Limits on the security of coin flips when half the processors are faulty. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 364–369.ACM, 1986.
[13] Biao He and Yu Wei. Electronic sortition. In The 2009 International Symposium on Intelligent Information Systems and Applications (IISA 2009),page 203, 2009.
[14] Stéphane Grumbach and Robert Riemann. Distributed random process for a large-scale peer to peer lottery. In IFIP International Conference on Distributed Applications and Interoperable Systems, pages 34–48. Springer, 2017.
[15] Arjen K Lenstra and Benjamin Wesolowski. A random zoo: sloth, unicorn, and trx. IACR Cryptology ePrint Archive, - -:366, 2015.
[16] David M Goldschlag and Stuart G Stubblebine. Publicly verifiable lotteries: Applications of delaying functions. In International Conference on Financial Cryptography, pages 214–226. Springer,1998.
[17] Sherman SM Chow, Lucas CK Hui, Siu-Ming Yiu, and KP Chow. An e-lottery scheme using verifiable random function. In International Conference on Computational Science and its Applications, pages 651–660. Springer, 2005.
[18] Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 120–130. IEEE, 1999.