Sharing Secrets Rationally

The demand for network engineers today is ubiquitous – not only do they design and build networks connecting millions of nodes across the globe but also solve problems to improve existing ones. The parameters available to them to construct a network, say the number of nodes, capacity and so forth are almost always insufficient. Thus the underlying algorithm, called a distributed algorithm, used to make the various elements of the network come together and achieve an acceptable level of performance while solving a given problem, gains paramount importance. “That’s what I hope to be developing during the course of my Ph.D.,” says William K. Moses Jr., a research scholar at the Department of Computer Science and Engineering. “A simple instance of a distributed algorithm is how file sharing is done on DC++ [IITM’s internal LAN].”

But what really motivated him to undertake a Ph.D. in the field was the research topic for his MS degree earned from the same department at IITM, on Rational Secret Sharing.

“The challenge of actually designing an algorithm on my own and pushing existing limits led me to appreciate what research meant and more specifically what research in distributed algorithms was about,” he says. “While my MS gave me a taste of what it means to work in the broad area of distributed algorithms, I wish to use the time during my Ph.D. to really probe the field deeper.”

 

Rational Secret Sharing

Secret Sharing is a cryptographic concept which William explains with an example. “Suppose I am a manager in the bank looking after five subordinates. Only I have access to the main safe. On the days when I am not available, my subordinates need access to it. I devise a method by which I give each a unique key, and only if three or more of them come together, will they be able to crack the code. This way, I ensure that nobody independently has access to the safe but it can still be opened.” This can be achieved by constructing a second-degree polynomial, and giving each subordinate a data point – requiring at least three of them to reconstruct the original function.

This is a concept widely used to store confidential information among network servers. In the event of multiple server crashes, the information could still be retrieved with a minimum number of working servers.

However, secret sharing makes one critical assumption – the existence of ‘honest’ and ‘malicious’ players. ‘Honest’ players follow a certain protocol without deviation, and ‘malicious’ ones are those who look to crack the secret following everything but the protocol. However, this does not always model the players (or the users of a network) correctly. In fact, players are usually ‘rational’, where they work on the principle of ‘doing what is best for me’. Modelling the middle ground is the challenge, and this is where William has used Game Theory to redefine the behaviour of the players involved and effectively simulate a setting of rational secret sharing (RSS).

But what sets William’s work apart is the fact that he has applied RSS to an ‘asynchronous’ broadcast channel, which is what is usually in play in the real world. The network has no control over the time of sending and arrival of messages, making it difficult to provide a secure and reliable link for nodes to communicate. Previous work focused on solving the problem of RSS over simultaneous and ‘synchronous’ networks, and the those who have attempted to go down these lines have each come up with their own set of limitations. William hopes his work leads to further breakthroughs in the field.

 

Future Work

Currently, William is pursuing his Ph.D. and focusing his efforts on distributed algorithms. As the state of networks and how they are being used continues to evolve, challenges continue to present themselves. William hopes to be there on the bleeding edge of research and take the study of the area to new levels.


william_"billy"_mosesWilliam “Billy” Moses Jr. completed his MS at the Department of Computer Science and Engineering, guided by Prof C. Pandu Rangan. He is currently pursuing his Ph.D. under Prof John Augustine. A resident of Cauvery hostel, he is an avid reader and enjoys playing chess and table tennis.