## CryptoDB

### Amjed Shareef

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Sanitizable signatures with strong transparency in the standard model
Abstract

Sanitizable signatures provide several security features which
are useful in many scenarios including military and medical applications. Sanitizable signatures allow a semi-trusted party to update some part of the digitally signed document without interacting with the original signer. Such schemes, where the verifer cannot identify whether the message has been sanitized, are said to possess strong transparency. In this paper, we have described the first efficient and provably secure sanitizable signature scheme having strong transparency under the standard
model.

2010

EPRINT

Collusion Free Protocol for Correlated Element Selection Problem
Abstract

A common problem in many markets is that competing firms cannot plan joint business strategies which are socially beneficial, as each firm has its own preferable business strategy which would yield higher profits for it and lower profits for the others. The solution to this problem becomes complex because each firm need not stick to its commitment to follow the pre-designated strategy. Game theory suggests to us a way to enforce this commitment, as when every player chooses his actions according to his observation of the value of a common public signal and, assuming that the others do not deviate, no player is willing to deviate from his recommended strategy. The players do not deviate from their recommended strategy as playing them would yield them a much higher expected pay-off than playing individually. The common public channel can be a trusted external mediator which may send each player his recommended strategy. This mediator can be simulated by a cryptographic protocol, which all the players agree to implement. This problem of suggesting the protocol is known as the \textit{Correlated Element Selection Problem}. The first two-player protocol was proposed by Dodis et. al\cite{dhr00} in Crypto 2000. The extension of the two-player protocol to an $n$-player protocol is highly prone to collusions, as two firms can collude and cheat the rest of the firms. The main contribution of the paper is the first $n$-player collusion free protocol for the \textit{correlated element selection problem} that does not use hardware primitives. We assume that players are honest but curious.

2010

EPRINT

Rational Secret Sharing without Broadcast
Abstract

We consider the concept of rational secret sharing, which was initially introduced by Halpern and Teague \cite{ht04}, where players' preferences are that they prefer to learn the secret than not, and moreover they prefer that as few others learn the secret as possible. This paper is an attempt to introduce a rational secret sharing scheme which defers from previous RSS schemes in that this scheme does not rely on broadcast to send messages but instead uses point to point transmissions. Not only that, but the protocol will not rely on any cryptographic primitives and is coalition resilient except for when the short player colludes with a long player.

2010

EPRINT

Collusion Free Protocol for Rational Secret Sharing
Abstract

We consider the \textit{rational secret sharing problem} introduced by Halpern and Teague\cite{ht04}, where players prefer to get the secret rather than not to get the secret and with lower preference, prefer that as few of the other players get the secret. Some positive results have been derived by Kol and Naor\cite{stoc08} by considering that players only prefer to learn. They have proposed an efficient $m$-out-of-$n$ protocol for rational secret sharing without using cryptographic primitives. Their solution considers that players are of two types; one player is the short player and the rest of the players are long players. But their protocol is susceptible to coalitions if the short player colludes with any of the long players. We extend their protocol, and propose a completely collusion free, $\varepsilon$-Nash equilibrium protocol, when $n \geq 2m -1 $, where $n$ is the number of players and $m$ is the number of shares needed to construct the secret.

2010

EPRINT

Terrorists in Parliament, Distributed Rational Consensus
Abstract

\The \textit{consensus} is a very important problem in distributed computing, where among the $n$ players, the honest players try to come to an agreement even in the presence of $t$ malicious players. In game theoretic environment, \textit{the group choice problem} is similar to the \textit{rational consensus problem}, where every player $p_i$ prefers come to consensus on his value $v_i$ or to a value which is as close to it as possible. All the players need to come to an agreement on one value by amalgamating individual preferences to form a group or social choice. In rational consensus problem, there are no malicious players. We consider the rational consensus problem in the presence of few malicious players. The players are assumed to be rational rather than honest and there exist few malicious players among them. Every rational player primarily prefers to come to consensus on his value and secondarily, prefers to come to consensus on other player's value. In other words, if $w_1$, $w_2$ and $w_3$ are the payoffs obtained when $p_i$ comes to consensus on his value, $p_i$ comes to consensus on other's value and $p_i$ does not come to consensus respectively, then $w_1 > w_2 > w_3$. We name it as \textit{distributed rational consensus problem} DRC. This situation resembles situation of a parliament, where two political parties fight for their choice to be followed, and there are few terrorists among them, whose main objective is that parliament should not make any decision. The players can have two values, either 1 or 0, i.e binary consensus. The rational majority is defined as number of players, who wants to agree on one particular value, and they are more than half of the rational players. Similarly rational minority can be defined. We have considered EIG protocol, and characterized the rational behaviour, and shown that EIG protocol will not work in rational environment. We have proved that, there exists no protocol, which solves distributed consensus problem in fixed running time, where players have knowledge of other players values during the protocol. This proof is based on Maskin's monotonicity property. The good news is, if the players do not have knowledge about other players values, then then it can be solved. This can be achieved by verifiable rational secret sharing, where players do not exchange their values directly, but as pieces of it.

#### Coauthors

- Shivank Agrawal (1)
- Akshay Agrawal (1)
- Swarun Kumar (1)
- C. Pandu Rangan (2)