NDLI: Scalable mechanisms for rational secret sharing

Please wait, while we are loading the content...

Scalable mechanisms for rational secret sharing

Content Provider	Springer Nature Link
Author	Dani, Varsha Movahedi, Mahnush Saia, Jared
Copyright Year	2014
Abstract	We consider the classical secret sharing problem in the case where all agents are rational. In recent work, Kol and Naor show that, when there are two players, in the non-simultaneous communication model, i.e., when rushing is possible, there is no Nash equilibrium that ensures both players learn the secret. However, they describe a mechanism for this problem, for any number of players, that is an $$\epsilon $$ -Nash equilibrium, in that no player can gain more than $$\epsilon $$ utility by deviating from it. Unfortunately, the Kol and Naor mechanism, and, to the best of our knowledge, all previous mechanisms for this problem require each agent to send $$O(n)$$ messages in expectation, where $$n$$ is the number of agents. We address this issue by describing mechanisms for rational secret sharing that are designed for large $$n \ge 3$$ . Our first result is a non-cryptographic mechanism for $$n$$ -out-of- $$n$$ rational secret sharing that is Nash equilibrium, rather than just $$\epsilon $$ -Nash equilibrium. Our second result is a cryptographic mechanism for rational $$t$$ -out-of- $$n$$ secret sharing that is everlasting $$\epsilon $$ -Nash equilibrium. Both our mechanisms are scalable in the sense that they requires each player to send only an expected $$O(\log n)$$ bits. Furthermore, the latency of these mechanisms is $$O(\log n)$$ in expectation, compared to $$O(n)$$ expected latency for the Kol and Naor result. Both of our mechanisms are not susceptible to backwards induction.
Starting Page	171
Ending Page	187
Page Count	17
File Format	PDF
ISSN	01782770
Journal	Distributed Computing
Volume Number	28
Issue Number	3
e-ISSN	14320452
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2014-11-13
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Distributed scalable algorithm Game theory Rational secret sharing Computer Communication Networks Computer Hardware Computer Systems Organization and Communication Networks Software Engineering/Programming and Operating Systems Theory of Computation
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient distributed computation of distance sketches in networks

Fast and scalable rendezvousing

Stable and scalable universal swarms

Lower bound for scalable Byzantine Agreement

A fast distributed approximation algorithm for minimum spanning trees

Scalable and dynamic quorum systems

An optimal bit complexity randomized distributed MIS algorithm

Asynchronous Byzantine Agreement with optimal resilience

On spectrum sharing games

Scalable mechanisms for rational secret sharing

Similar Documents

Efficient distributed computation of distance sketches in networks

Fast and scalable rendezvousing

Stable and scalable universal swarms

Lower bound for scalable Byzantine Agreement

A fast distributed approximation algorithm for minimum spanning trees

Scalable and dynamic quorum systems

An optimal bit complexity randomized distributed MIS algorithm

Asynchronous Byzantine Agreement with optimal resilience

On spectrum sharing games

Scalable mechanisms for rational secret sharing