Perfectly Secure Message Transmission Against Rational Timid Adversaries

Abstract

Secure Message Transmission (SMT) is a two-party cryptographic protocol by which the sender can securely and reliably transmit messages to the receiver using multiple channels. It is assumed that an adversary corrupts a subset of the channels, and makes eavesdropping and tampering over the corrupted channels. In this work, we consider a game-theoretic security model for SMT. Specifically, we introduce a rational adversary who has the preference for the outcome of the protocol execution. We show that, under some reasonable assumption on the adversary’s preference, even if the adversary corrupts all but one of the channels, it is possible to construct SMT protocols with perfect security against rational adversaries. More specifically, we consider “timid” adversaries who prefer to violate the security requirement of SMT, but do not prefer the tampering actions to be detected. In the traditional cryptographic setting, perfect SMT can be constructed only when the adversary corrupt a minority of the channels. Our results demonstrate a way of circumventing the impossibility results of cryptographic protocols based on a game-theoretic approach.

1 Introduction

It is common to use the information network to send and receive messages. In the physical sense, the channels between senders and receivers might be realized by combining apparatus for communication, which allow some adversary to eavesdrop or tamper. As a technique for protecting data over communication from their leakage, we often use public-key cryptosystems. Since the security of public-key cryptosystems is based on computational assumptions and the computational assumptions might be falsified, it is desirable to develop methods of protecting data in the information-theoretic sense.

While a single communication channel is assumed in the typical two-party cryptographic schemes, the current information network technologies can let many channels be available. Secure Message Transmission (SMT), originally proposed by Dolev et al. [10], is a cryptographic protocol by which a sender can transmit messages through multiple channels in a secure way. Even if any adversary corrupts t out of n channels and makes eavesdropping and tampering over the corrupted channels, the messages are securely and correctly transmitted to the receiver by using SMT. The requirements for SMT consist of privacy and reliability. The privacy guarantees that the adversary can obtain no information about the transmitted message, and the reliability does that the message transmitted by the sender is recovered by the receiver. If an SMT protocol satisfies both the requirements in the perfect sense, the protocol is called a perfect SMT. The most round-efficient perfect SMT is given by Kurosawa and Suzuki [29]. Dolev et al. [10] showed that any one-round perfect SMT must satisfy $t < n/3$ and any perfect SMT whose round complexity is at least two must satisfy $t < n/2$. Franklin and Wright [11] defined almost-reliable SMT, which allows transmission failures of small probability. They showed that almost-reliable SMT against $t < n$ corruptions is achievable by using a public channel in addition to the normal channels. Later, Garay and Ostrovsky [15] and Shi et al. [32] gave the most round-efficient almost-reliable SMT protocols using public channels.

In the standard setting in cryptography, the participants are assumed to be either honest or malicious. The former follow the protocol description honestly, and the later may deviate from the protocol maliciously. In general, malicious behavior may be illegal and involve some risks, which implies that adversaries in the standard cryptographic setting behave maliciously regardless of their risk. However, some adversary in reality may decide his behavior by taking the risk into account. To capture such situations, we incorporate the notion of “rational” participants of game theory into cryptography. Halpern and Teague [22] firstly studied the rational behavior of participants in cryptography in the context of secret sharing. Since then, rational secret sharing has been intensively studied [1, 4, 12, 16, 26,27,28]. Moreover, there have been many studies using game-theoretic analysis of cryptographic primitives/protocols, including two-party computation [3, 18], leader election [2, 17], Byzantine agreement [19], consensus [23], public-key encryption [35, 36], delegation of computation [5, 7, 8, 20, 21, 24], and protocol design [13, 14]. Among them, several work [5, 13, 19,20,21] used the rationality of adversaries to circumvent the existing impossibility results.

Groce et al. [19] studied the problem of Byzantine agreement in the presence of a rational adversary. They showed that, given some knowledge of the adversary’s preference, perfectly secure Byzantine agreement is possible for t corruptions among n players for any $t < n$, for which the impossibility against $t \ge n/2$ corruptions is known in the standard setting.

In this work, we show that the impossibility results of SMT can be also circumvented by considering the rationality of adversaries. As in the case of Byzantine agreement, we introduce a rational adversary for SMT who has some preference for the outcome of the protocol execution. More specifically, we define timid adversaries who prefer to violate the security requirements of SMT, but do not prefer the tampering actions to be detected. For such adversaries, first we show that the almost-reliable SMT protocol of [32], which employs a tamper-proof public channel, works as a “perfect” SMT protocol. Second, we show that, for “strictly” timid adversaries, who prefer being undetected to violating the security requirements, secret sharing schemes with some robustness can be used as a non-interactive SMT protocol. Both protocols are perfectly secure against timid adversaries corrupting t out of n channels for any $t < n$, which is impossible in the standard setting of SMT protocols. In addition, we present an impossibility result of constructing SMT protocols against general timid adversaries corrupting $t \ge n/2$ channels. The result demonstrates the necessities of the tamper-proof public channel in the first protocol and the restriction of strictly timid adversaries in the second protocol. The results are summarized in Table 1.

Table 1. Summary of previous work and our results.

2 Preliminaries

2.1 Secure Message Transmission

We assume that a sender $\mathcal {S}$ and a receiver $\mathcal {R}$ are connected by n channels, and they may use an authentic and reliable public channel. Messages sent over the public channel are publicly accessible and correctly delivered to the receiver. SMT protocols proceed in rounds. In each round, one party may synchronously send a message over each channel and the public channel. The messages will be delivered before the next round starts.

The adversary $\mathcal {A}$ can corrupt at most t channels. Such an adversary is referred to as t-adversary. Messages sent over corrupted channels can be eavesdropped and tampered by the adversary. We assume that $\mathcal {A}$ is computationally unbounded.

Let $\mathcal {M}$ be the message space. In SMT, the sender tries to send a message in $\mathcal {M}$ to the receiver by using n channels and the public channel, and the receiver outputs some message after the protocol execution. For an SMT protocol $\varPi$, let $M_S$ denote the random variable of the message sent by $\mathcal {S}$ and $M_R$ the message output by $\mathcal {R}$ in $\varPi$. An execution of $\varPi$ can be completely characterized by the random coins of all the parties, namely, $\mathcal {S}$, $\mathcal {M}$, and $\mathcal {A}$, and the message $M_S$ sent by $\mathcal {S}$. Let $V_A(m, r_A)$ denote the view of $\mathcal {A}$ when the protocol is executed with $M_S = m$ and the random coins $r_A$ of $\mathcal {A}$. Specifically, $V_A(m, r_A)$ consists of the messages sent over the corrupted channels and the public channel when the protocol is run with $M_S = m$ and $\mathcal {A}$’s random coins $r_A$.

We formally define the properties of SMT protocols.

Definition 1

A protocol between $\mathcal {S}$ and $\mathcal {R}$ is $(\varepsilon , \delta )$-Secure Message Transmission (SMT) against t-adversary if the following three conditions are satisfied against any t-adversary $\mathcal {A}$.

• Correctness: For any $m \in \mathcal {M}$, if $M_S = m$ and $\mathcal {A}$ does not corrupt any channels, then $\Pr [ M_R = m ] = 1$;

• Privacy: For any $m_0, m_1 \in \mathcal {M}$ and $r_A \in \{0,1\}^*$, it holds that

  $$\begin{aligned} \mathrm {SD}( V_A(m_0, r_A), V_A(m_1, r_A) ) \le \varepsilon , \end{aligned}$$

  where $\mathrm {SD}(X, Y)$ denotes the statistical distance between two random variables X and Y over a set $\varOmega$, which is defined by

  $$\begin{aligned} \mathrm {SD}(X, Y) = \frac{1}{2} \sum _{u \in \varOmega } \left| \Pr [X = u] - \Pr [Y = u] \right| ; \end{aligned}$$

• Reliability: For any message $m \in \mathcal {M}$, when $M_S = m$,

  $$\begin{aligned} \Pr [ M_R \ne m ] \le \delta , \end{aligned}$$

  where the probability is taken over the random coins of $\mathcal {S}$, $\mathcal {R}$, and $\mathcal {A}$.

If a protocol achieves (0, 0)-SMT, the protocol is called perfect SMT, and if a protocol achieves $(0,\delta )$-SMT, which admits transmission failures of small probability $\delta$, the protocol is called almost-reliable SMT.

For perfect SMT, Dolev et al. [10] showed the below.

Theorem 1

([10]). Perfect SMT protocols against t-adversary are achievable if and only if $t < n/2$.

2.2 Secure Message Transmission with Public Channel

In this paper, we will employ an almost-reliable SMT protocol given by Shi, Jiang, Safavi-Naini, and Tuhin [32], and refer it as the SJST protocol. Note that we only use some specific properties of the SJST protocol in the security analysis. Thus, other protocols, such as one by Garay and Ostrovsky [15], can also be employed instead of the SJST protocol.

Let us review the SJST protocol, which uses the public channel. The protocol is based on the simple protocol for “static” adversaries in which the sender sends a random key $R_i$ over the i-th channel for each $i \in \{1,\dots ,n\}$, and the encrypted message $c = m \oplus R_1 \oplus \dots \oplus R_n$ over the public channel. Suppose that the adversary sees the messages sent over the corrupted channels, but does not change them. Since the adversary cannot see at least one key $R_j$ when corrupting less than n channels, the mask $R_1 \oplus \dots \oplus R_n$ for the encryption looks random for the adversary. Thus, the message m can be securely encrypted and reliably sent through the public channel. To cope with “active” adversaries, who may change messages sent over the corrupted channels, the SJST protocol employs a mechanism for detecting the adversary’s tampering by using hash functions. Specifically, the universal hash functions (see Appendix A) satisfy the following property: when a pair of keys $(r_i, R_i)$ is changed to $(r_i',R_i') \ne (r_i, R_i)$, the hash value for $(r_i,R_i)$ is different from that for $(r_i',R_i')$ with high probability if the hash function is chosen randomly after the tampering occurred. In the SJST protocol, the sender sends a pair of keys $(r_i, R_i)$ over the i-th channel. Then, the receiver chooses n universal hash functions $h_i$’s, and sends them over the public channel. By comparing hash values for $(r_i,R_i)$’s sent by the sender with those for $(r_i',R_i')$’s received by the receiver, they can identify the channels for which messages, i.e., keys, were tampered with. By ignoring keys sent over such channels, the sender can correctly encrypt a message m with untampered keys and send the encryption reliably over the public channel.

We describe the SJST protocol below, which is a three-round protocol, and achieves the reliability with $\delta = (n-1)\cdot 2^{1-\ell }$, where $\ell$ is the length of hash values.

Protocol 1

(The SJST protocol [32]). Let n be the number of channels, $m \in \mathcal {M}$ the message to be sent by the sender $\mathcal {S}$, and $H = \{h :\{0,1\}^k \rightarrow \{0, 1\}^\ell \}$ a class of universal hash functions.

• 1. For each $i \in \{1, \dots , n\}$, $\mathcal {S}$ chooses $r_i \in \{0,1\}^\ell$ and $R_i \in \{0,1\}^k$ uniformly at random, and sends the pair $(r_i, R_i)$ over the i-th channel.

• 2. For each $i \in \{1, \dots , n\}$, $\mathcal {R}$ receives $(r_i',R_i')$ through the i-th channel, and then chooses $h_i \leftarrow H$ uniformly at random. If $|r_i'| \ne \ell$ or $|R_i'| \ne k$, set $b_i = 1$, and otherwise, set $b_i = 0$. Then, set $T_i' = r_i' \oplus h_i(R_i')$, and $H_i = (h_i, T_i')$ if $b_i=0$, and $H_i = \bot$ otherwise. Finally, $\mathcal {R}$ sends $(B, H_1, \dots , H_n)$ over the public channel, where $B = (b_1, \dots , b_n)$.

• 3. $\mathcal {S}$ receives $(B, H_1, \dots , H_n)$ through the public channel. For each $i \in \{1, \dots , n\}$ with $b_i = 0$, $\mathcal {S}$ computes $T_i = r_i \oplus h_i(R_i)$, and sets $v_i = 0$ if $T_i = T_i'$, and $v_i = 1$ otherwise. Then, $\mathcal {S}$ sends (V, c) over the public channel, where $V = (v_1, \dots , v_n)$, and $c = m \oplus (\bigoplus _{v_i=0}R_i)$.

• 4. On receiving (V, c), $\mathcal {R}$ recovers $m = c \oplus (\bigoplus _{v_i=0}R_i)$.

Theorem 2

([32]). The SJST protocol is $(0,(n-1)\cdot 2^{1-\ell })$-SMT against t-adversary for any $t < n$.

We can find a complete proof of the above theorem in [32]. For self-containment, we give a brief sketch of the proof.

• Privacy: The adversary can get $c = m \oplus (\bigoplus _{v_i=0} R_i)$ through the public channel. Since m is masked by uniformly random $R_i$’s, the adversary has to corrupt all the i-th channels with $v_i=0$ to recover m. However, since any t-adversary can corrupt at most t $(< n)$ channels, the adversary can cause $v_i = 1$ for at most $n-1$ i’s. Hence, there is at least one i with $v_i = 0$, for which the adversary cannot obtain $R_i$. Thus, the protocol satisfies the perfect privacy.

• Reliability: Since the protocol uses the public channel at the second and the third rounds, the adversary can tamper with channels only at the first round. Suppose that the adversary tampers with $(r_i,R_i)$. If $R_i \ne R_i'$ and $T_i = T_i'$, then $\mathcal {R}$ would recover a wrong message, but the tampering is not detected. It follows from Lemma 1 that the probability that the above event happens is at most $(n-1)2^{1-\ell }$. Thus, the protocol achieves the reliability with $\delta = (n-1)\cdot 2^{1-\ell }$.

2.3 Robust Secret Sharing

Secret sharing, introduced by Shamir [31] and Blackley [6], enables us to distribute the secret information in a secure way. Let $s \in \mathbb {F}$ be a secret from some finite field $\mathbb {F}$. A (threshold) secret-sharing scheme gives a way for distributing s into n shares $s_1, \dots , s_n$ such that, for some parameter $t > 0$, (1) any t shares give no information about s; and (2) any $t+1$ shares uniquely determine s. Shamir [31] give a scheme based on polynomial evaluations for any $t < n$.

Shamir’s scheme also achieves robustness in the sense that even if t / 3 shares are maliciously tampered, the original secret can be correctly recovered. Although the robustness is a desirable property, it is known that robust secret sharing is impossible when t / 2 shares are tampered with [25].

In this work, we need a weaker notion of robustness in which any tampering actions should be detected with high probability. Such robust secret sharing was studied by Cramer et al. [9]. They introduced the notion of algebraic manipulation detection (AMD) codes, and presented a simple way for constructing robust secret sharing from linear secret sharing and AMD codes. More precisely, the robustness required for our protocol is slightly different from one defined in [9].¹

Definition 2

Let t, n be positive integers with $t < n$. A $(t, n, \delta )$-robust secret sharing scheme with range $\mathcal {G}$ consists of two algorithms $(\mathsf {Share}, \mathsf {Reconst})$ satisfying the following conditions:

• Correctness: For any $s \in \mathcal {G}$ and $I \subseteq \{1, \dots , n\}$ with $|I| > t$,

  $$\begin{aligned} \Pr \left[ \mathsf {Reconst}\left( \{i, s_i\}_{i \in I}\right) = s \right] = 1, \end{aligned}$$

  where $(s_1, \dots , s_n) \leftarrow \mathsf {Share}(s)$.

• Perfect Privacy: For any $s, s' \in \mathcal {G}$ and $I \subseteq \{1, \dots , n\}$ with $|I| \le t$,

  $$\begin{aligned} \mathrm {SD}\left( \{s_i\}_{i \in I}, \{s'_i\}_{i \in I}\right) = 0, \end{aligned}$$

  where $(s_1, \dots , s_n) \leftarrow \mathsf {Share}(s)$ and $(s_1', \dots , s_n') \leftarrow \mathsf {Share}(s')$.

• Robustness: For any $s \in \mathcal {G}$ and $I \subseteq \{1, \dots , n\}$ with $|I| \le t$ and adversary $\mathcal {A}$, if $\tilde{s}_i \ne s_i$ for some $i \in \{1, \dots , n\}$,

  $$\begin{aligned} \Pr \left[ \mathsf {Reconst}\left( \{i, \tilde{s}_i\}_{i \in \{1,\dots ,n\}}\right) \ne \bot \right] \le \delta , \end{aligned}$$

  where

  $$\begin{aligned} \tilde{s}_i = {\left\{ \begin{array}{ll} \mathcal {A}(i, s, \{s_i\}_{i \in I}) &{} \text {if } i \in I\\ s_i &{} \text {if } i \notin I \end{array}\right. } \end{aligned}$$

  and $(s_1, \dots , s_n) \leftarrow \mathsf {Share}(s)$.

We can see that the construction of [9] satisfies the above definition. Specifically, we have the following theorem, which will be used in our protocol against strictly timid adversaries in Sect. 4.2. See Appendix B for the proof.

Theorem 3

Let $\mathbb {F}$ be a finite field of size q and characteristic p, and d an integer such that $d+2$ is not divisible by p. For any positive integers t and n satisfying $t < n \le qd$, there is an explicit and efficient scheme of $(t, n, (d+1)/q)$-robust secret sharing with range $\mathbb {F}^d$, where each share is an element of $\mathbb {F}^{d+2}$.

3 Rational Secure Message Transmission

We define our security model of SMT in the presence of a rational adversary. A rationality of the adversary is characterized by a utility function which represents the preference of the adversary over possible outcomes of the protocol execution.

We can consider various preferences of the adversary regarding the SMT protocol execution. The adversary may prefer to violate the privacy or the reliability of SMT protocols. In addition, the adversary may prefer to violate the above properties without the detection of tampering actions. Here, we consider the adversary who prefers (1) to violate the privacy, (2) to violate the reliability, (3) the tampering actions to be undetected, and (4) the protocol execution to be finished without abort.

To define the utility function, we specify the SMT game as follows.

The SMT Game. First set four parameters $\mathsf {guess}= \mathsf {suc}= \mathsf {detect}= \mathsf {abort}= 0$. Given an SMT protocol $\varPi$ with the message space $\mathcal {M}$, choose $m \in \mathcal {M}$ uniformly at random, and run the protocol $\varPi$ in which the message to be sent is $M_S = m$. In the protocol execution, as in the usual SMT, the adversary $\mathcal {A}$ can corrupt at most t channels, and tamper with any messages sent over the corrupted channels. If the protocol finishes with abort, set $\mathsf {abort}= 1$. If the sender or the receiver sends a special message “DETECTION” during the execution, set $\mathsf {detect}= 1$. After running the protocol, the receiver outputs $M_R$, and the adversary outputs $M_A$. If $M_R = M_S$, set $\mathsf {suc}= 1$. If $M_A = M_S$, set $\mathsf {guess}= 1$. The outcome of the game is $(\mathsf {guess}, \mathsf {suc}, \mathsf {detect}, \mathsf {abort})$.

The utility of the adversary is defined as the expected utility in the SMT game.

Definition 3

(Utility). The utility $u(\mathcal {A},U)$ of the adversary $\mathcal {A}$ with utility function U is the expected value $E[U(\mathsf {out})]$, where U is a function that maps the outcome $\mathsf {out}= (\mathsf {guess}, \mathsf {suc}, \mathsf {detect}, \mathsf {abort})$ of the SMT game by $\mathcal {A}$ to real values, and the probability is taken over the random coins of the sender, the receiver, and the adversary, and a random choice of message $M_S$.

The utility function U characterizes the type of adversaries. If the adversary has the preferences (1)-(4) as above, the utility function may have the property such that for any two outcomes $\mathsf {out}= (\mathsf {guess}, \mathsf {suc}, \mathsf {detect}, \mathsf {abort})$ and $\mathsf {out}' = (\mathsf {guess}', \mathsf {suc}', \mathsf {detect}', \mathsf {abort}')$ of the SMT game,

• 1. $U(\mathsf {out}) > U(\mathsf {out}')$ if $\mathsf {guess}> \mathsf {guess}'$, $\mathsf {suc}= \mathsf {suc}'$, $\mathsf {detect}= \mathsf {detect}'$, and $\mathsf {abort}= \mathsf {abort}'$;

• 2. $U(\mathsf {out}) > U(\mathsf {out}')$ if $\mathsf {guess}= \mathsf {guess}'$, $\mathsf {suc}< \mathsf {suc}'$, $\mathsf {detect}= \mathsf {detect}'$, and $\mathsf {abort}= \mathsf {abort}'$;

• 3. $U(\mathsf {out}) > U(\mathsf {out}')$ if $\mathsf {guess}= \mathsf {guess}'$, $\mathsf {suc}= \mathsf {suc}'$, $\mathsf {detect}< \mathsf {detect}'$, and $\mathsf {abort}= \mathsf {abort}'$;

• 4. $U(\mathsf {out}) > U(\mathsf {out}')$ if $\mathsf {guess}= \mathsf {guess}'$, $\mathsf {suc}= \mathsf {suc}'$, $\mathsf {detect}= \mathsf {detect}'$, and $\mathsf {abort}< \mathsf {abort}'$.

Based on the utility function of the adversary, we define the security of rational secure message transmission.

Definition 4

(Security of RSMT). An SMT protocol $\varPi$ is perfectly secure against rational t-adversaries with utility function U if there is a t-adversary $\mathcal {B}$ such that for any t-adversary $\mathcal {A}$,

• 1. Perfect security: $\varPi$ is (0, 0)-SMT against $\mathcal {B}$; and

• 2. Nash equilibrium: $u(\mathcal {A},U) \le u(\mathcal {B},U)$ in the SMT game.

The perfect security guarantees that an adversary $\mathcal {B}$ is harmless. The Nash equilibrium guarantees that no adversary $\mathcal {A}$ can gain more utility than $\mathcal {B}$. Thus, the above security of RSMT implies that no adversary $\mathcal {A}$ can gain more utility than the harmless adversary. Namely, the adversary does not have an incentive to deviate from the strategy of the harmless adversary $\mathcal {B}$.

In the security proof of our protocol, we will consider an adversary $\mathcal {B}$ who does not corrupt any channels, and outputs $M_A$ by choosing a message uniformly at random from $\mathcal {M}$. For such $\mathcal {B}$, the perfect privacy and reliability immediately follows if $\varPi$ satisfies the correctness.

4 Protocols Against Timid Adversaries

We present several protocols that are secure against timid rational adversaries. Timid adversaries are rational adversaries who firstly do not prefer the tampering to be detected, and secondly prefer to violate the reliability.

More formally, utility function U of such adversaries should have the properties such that

• 1. $U(\mathsf {out}) > U(\mathsf {out}')$ if $\mathsf {suc}< \mathsf {suc}'$ and $\mathsf {detect}= \mathsf {detect}'$; and

• 2. $U(\mathsf {out}) > U(\mathsf {out}')$ if $\mathsf {suc}= \mathsf {suc}'$ and $\mathsf {detect}< \mathsf {detect}'$,

where $\mathsf {out}= (\mathsf {guess}, \mathsf {suc}, \mathsf {detect}, \mathsf {abort})$ and $\mathsf {out}' = (\mathsf {guess}', \mathsf {suc}', \mathsf {detect}', \mathsf {abort}')$ are the outcomes of the SMT game. Let $U_\mathsf {timid}$ be the set of utility functions that satisfy the above conditions.

In addition, timid adversaries may have the following property:

• 3. $U(\mathsf {out}) > U(\mathsf {out}')$ if $\mathsf {suc}> \mathsf {suc}'$ and $\mathsf {detect}< \mathsf {detect}'$.

Let $U_\mathsf {timid}^\mathsf {st}$ be the set of utility functions satisfying the above three conditions. An adversary is said to be timid if his utility function is in $U_\mathsf {timid}$, and strictly timid if the utility function is in $U_\mathsf {timid}^\mathsf {st}$.

In the analysis of our protocols, we need the following four values of utility:

• $u_1$ is the utility when $\Pr [\mathsf {guess}= 1] = 1/|\mathcal {M}|$, $\mathsf {suc}= 0$, $\mathsf {detect}= 0$, and $\mathsf {abort}= 0$;

• $u_2$ is the utility when $\Pr [\mathsf {guess}= 1] = 1/|\mathcal {M}|$, $\mathsf {suc}= 1$, $\mathsf {detect}= 0$, and $\mathsf {abort}= 0$;

• $u_3$ is the utility when $\Pr [\mathsf {guess}= 1] = 1/|\mathcal {M}|$, $\mathsf {suc}= 0$, $\mathsf {detect}= 1$, and $\mathsf {abort}= 0$;

• $u_4$ is the utility when $\Pr [\mathsf {guess}= 1] = 1/|\mathcal {M}|$, $\mathsf {suc}= 1$, $\mathsf {detect}= 1$, and $\mathsf {abort}= 0$;

It follows from the properties of utility functions in $U_\mathsf {timid}$ that the relations $u_1 > \max \{u_2, u_3\}$ and $\min \{u_2, u_3\} > u_4$ hold. For utility functions in $U_\mathsf {timid}^\mathsf {st}$, it holds that $u_1> u_2> u_3 > u_4$.

4.1 Protocol with Public Channel

We show that the SJST protocol of [32] works as a perfect SMT protocol against timid adversaries. More specifically, we slightly modify the SJST protocol such that in the second and the third rounds, if $b_i = 1$ in B or $v_j = 1$ in V for some $i, j \in \{1, \dots , n\}$, the special message “DETECTION” is also sent together. We clarify the parameters for which the SJST protocol works as RSMT against timid adversaries.

Theorem 4

If the parameter $\ell$ in the SJST protocol satisfies

$$\begin{aligned} \ell \ge \max \left\{ 1 + \log t + \log \frac{u_3 - u_4}{u_2 - u_4 - \alpha }, 1 + \frac{1}{t} \log \frac{u_1-u_3}{\alpha } \right\} \end{aligned}$$

for some $\alpha \in (0, u_2 - u_4)$, then the protocol is perfectly secure against rational t-adversaries with utility function $U \in U_\mathsf {timid}$ for any $t < n$.

Proof

We consider the adversary $\mathcal {B}$ in Definition 4 such that $\mathcal {B}$ does not corrupt any channels, and outputs a uniformly random message from $\mathcal {M}$ as $M_A$. Then, the perfect security of Definition 4 immediately follows.

Next, we show that the strategy of $\mathcal {B}$ is a Nash equilibrium. Note that $u(\mathcal {B}, U) = u_2$, since $\Pr [ \mathsf {guess}= 1] = \Pr [ M_A = M_S] = 1/|\mathcal {M}|$ in the SMT game. Thus, it is sufficient to show that $u(\mathcal {A}, U) \le u_2$ for any t-adversary $\mathcal {A}$. Also, note that, since the SJST protocol achieves the perfect privacy, it holds that $\Pr [ \mathsf {guess}= 1] = 1/|\mathcal {M}|$ for any t-adversary.

Since messages in the second and the third rounds are sent through the public channel, the adversary $\mathcal {A}$ can tamper with messages only in the first round. If $\mathcal {A}$ changes the lengths of $r_i$ and $R_i$, the tampering of the i-th channel will be detected. Such channels are simply ignored in the second and third rounds. Thus, such tampering cannot increase the utility. Hence, we assume that $\mathcal {A}$ does not change the lengths of $r_i$ and $R_i$ in the first round.

Suppose that $\mathcal {A}$ corrupts some t channels in the first round. Namely, there are exactly t distinct i’s such that $(r_i', R_i') \ne (r_i, R_i)$. Note that the tampering on the i-th channel such that $r_i' \ne r_i$ and $R_i' = R_i$ does not increase the probability that $\mathsf {suc}= 0$, but may increase the probability of detection. Thus, we also assume that $R_i' \ne R_i$ for all the corrupted channels. We define the following three events:

• $E_1$: No tampering action is detected in the protocol;

• $E_2$: At least one but not all tampering actions are detected;

• $E_3$: All the t tampering actions are detected.

Note that all the events are disjoint, and either event should occur. Namely, we have that $\Pr [E_1] + \Pr [E_2] + \Pr [E_3] = 1$. It follows from the discussion in Sect. A that the probability that the tampering action on one channel is not detected is $2^{1-\ell }$. Since each hash function $h_i$ is chosen independently for each channel, we have that $\Pr [ E_1] = 2^{(1-\ell )t}$. Similarly, we obtain that $\Pr [ E_3 ] = (1 - 2^{1-\ell })^t$. Note that the utility when $E_1$ occurs is at most $u_1$. Also, the utilities when $E_2$ and $E_3$ occur are at most $u_3$ and $u_4$, respectively. Therefore, the utility of $\mathcal {A}$ is

$$\begin{aligned} u(\mathcal {A}, U)&\le u_1 \cdot \Pr [E_1] + u_3 \cdot \Pr [E_2] + u_4 \cdot \Pr [E_3] \nonumber \\&= u_3 + (u_1 - u_3) \Pr [E_1]- (u_3 - u_4)\Pr [E_3]\nonumber \\&\le u_3 + (u_1 - u_3) 2^{(1-\ell )t} - (u_3 - u_4)\left( 1- t 2^{1-\ell }\right) \nonumber \\&\le u_3 + \alpha - (u_3 - u_4)\left( 1- t 2^{1-\ell }\right) \end{aligned}$$

(1)

$$\begin{aligned}&\le u_2, \end{aligned}$$

(2)

where we use the relations $\ell \ge 1 + \frac{1}{t} \log \frac{u_1-u_3}{\alpha }$ and $\ell \ge 1 + \log t + \log \frac{u_3 - u_4}{u_2 - u_4 - \alpha }$ in (1) and (2), respectively. Thus, the utility of $\mathcal {A}$ is at most $u_2$, and hence the statement follows.    $\square$

If $u_2 > u_3$, which holds for strictly timid adversaries, by choosing $\alpha = u_2 - u_3$, the condition on $\ell$ is that

$$\begin{aligned} \ell \ge \max \left\{ 1 + \log t, 1 + \frac{1}{t} \log \frac{u_1 - u_3}{u_2-u_3} \right\} . \end{aligned}$$

4.2 Protocol Without Public Channel Against Strictly Timid Adversaries

We show that, under the condition that $u_2 > u_3$, robust secret sharing of Definition 2 gives a non-interactive perfect SMT protocol. Namely, we can construct a non-interactive protocol for strictly timid adversaries.

Let $(\mathsf {Share}, \mathsf {Reconst})$ be a $(t,n,\delta )$-robust secret sharing scheme with range $\mathcal {M}$. In the protocol, given a message $m \in \mathcal {M}$, the sender generates n shares $(s_1, \dots , s_n)$ by $\mathsf {Share}(m)$, and sends each $s_i$ over the i-th channel. The receiver simply recovers the message by $\mathsf {Reconst}(\{i, \tilde{s}_i\}_{i \in \{1,\dots ,n\}})$, where $\tilde{s}_i$ is the received message over the i-th channel.

Theorem 5

The above protocol based on a $(t, n, \delta )$-robust secret sharing scheme is perfectly secure against rational t-adversaries with utility function $U \in U_\mathsf {timid}^\mathsf {st}$ if U satisfies that $u_2 > u_3$ and

$$\begin{aligned} \delta \le \frac{u_2 - u_3}{u_1 - u_3}. \end{aligned}$$

Proof

As in the proof of Theorem 4, we consider $\mathcal {B}$ who does not corrupt any channels, and output a random message as $M_A$. Then, the perfect security immediately follows.

We show that, for any t-adversary $\mathcal {A}$, $u(\mathcal {A},U) \le u(\mathcal {B},U)$. As discussed in the proof of Theorem 4, it is sufficient to prove that $u(\mathcal {A}, U) \le u_2$ for any $\mathcal {A}$. Since the underlying secret sharing has the perfect privacy, we have that $\Pr [ \mathsf {guess}= 1] = 1/|\mathcal {M}|$ for any t-adversary. Suppose $\mathcal {A}$ corrupts some t channels and alters some messages $s_i$ into different $\tilde{s}_i$. It follows from the robustness of secret sharing that the tampering actions is detected with probability at least $1-\delta$, in which case the secret is not recovered. Thus, the utility of $\mathcal {A}$ is

$$\begin{aligned} u(\mathcal {A}, U)&\le (1 - \delta ) u_3 + \delta u_1\nonumber \\&\le u_2, \end{aligned}$$

(3)

where (3) follows from the assumption. Therefore, the statement follows.   $\square$

The following corollary immediately follows.

Corollary 1

Let $\mathbb {F}$ be a finite field of size $q = 2^\ell$, and d be any odd integer. The non-interactive protocol based on Theorem 3 is an SMT protocol with message space $\mathbb {F}^d$ that is perfectly secure against rational t-adversaries with utility function $U \in U_\mathsf {timid}^\mathsf {st}$ for any $t < n \le 2^\ell d$ if

$$\begin{aligned} \ell \ge \log (d+1) + \log \frac{u_1 - u_3}{u_2 - u_3}. \end{aligned}$$

5 Impossibility Result for General Timid Adversaries

We show that there is no RSMT protocol without public channel that is secure against general timid t-adversaries for $t \ge n/2$. The result implies that the use of the public channel in Theorem 4 is necessary for achieving $t \ge n/2$. It also demonstrates the necessity of restricting the utility in Theorem 5 for constructing protocols for $t \ge n/2$ without using public channels.

Theorem 6

For any SMT protocol without public channel that is perfectly secure against rational t-adversaries with utility function $U \in U_\mathsf {timid}$, if U has the relation

$$\begin{aligned} u_2 < \frac{1}{2}\left( 1 - \frac{1}{|\mathcal {M}|}\right) u_3 \end{aligned}$$

then $t < n/2$, where $\mathcal {M}$ is the message space of the protocol.

Proof

Let $\varPi$ be a protocol in the statement. We construct a t-adversary $\mathcal {A}$ for $t = \lceil n/2 \rceil$ that can successfully attack $\varPi$. For simplicity, we assume that $n = 2t$.

Let $\mathcal {B}$ be any (harmless) adversary in the security of RSMT protocols of Definition 4. Since $\varPi$ is (0, 0)-SMT against $\mathcal {B}$, it holds that $u(\mathcal {B},U) \le u_2$. We show the existence of a t-adversary $\mathcal {A}$ that achieves $u(\mathcal {A},U) > u_2$, which implies that $\varPi$ cannot achieve a Nash equilibrium.

In the SMT game, a message $m \in \mathcal {M}$ is randomly chosen, and, on input m, $\varPi$ generates $(s_1^j, \dots , s_n^j)$ for $j = 1, \dots$, where $s_i^j$ is the message to be sent over the i-th channel in the j-th round. In the game, $\mathcal {A}$ does the following:

• Randomly choose $I \subseteq \{1, \dots , n\}$ such that $|I| = t$, and corrupt the i-th channel for every $i \in I$.

• Randomly choose $\tilde{m} \in \mathcal {M}$, and simulate $\varPi$ on input $\tilde{m}$. Let $\tilde{s}_i^j$ be the message generated for the i-th channel in the j-th round.

• In each round j, for every $i \in I$, on receiving $s_i^j$ through the i-th channel, exchange $s_i^j$ for $\tilde{s}_i^j$.

For this attack, it is impossible for the receiver to distinguish which message, m or $\tilde{m}$, was originally transmitted by the sender, since both messages for m and $\tilde{m}$ are equally mixed. Hence, the probability that $\mathsf {suc}= 1$, denoted by $p_s$, is at most

$$ p_s \le \frac{1}{2}\left( 1 - \frac{1}{|\mathcal {M}|} \right) + \frac{1}{|\mathcal {M}|} = \frac{1}{2}\left( 1 + \frac{1}{|\mathcal {M}|} \right) , $$

where $1/|\mathcal {M}|$ comes from the even that $\tilde{m} = m$.

Let $p_d$ be the probability that $\varPi$ outputs “DETECTION” messages during the execution against the above attack. Without loss of generality, we assume that if $\varPi$ does not output “DETECTION” messages, the receiver outputs some message at the end of the protocol. If the tampering actions of $\mathcal {A}$ are not detected, the utility of $\mathcal {A}$ is at least $u_1$ with probability $1 - p_s$, and at least $u_2$ with probability $p_s$. If some tampering actions are detected, then there can be two cases: (1) the receiver does not output any message; and (2) the receiver outputs some message. In case (1), the utility of $\mathcal {A}$ is $u_3$. In case (2), the probability that the $\mathsf {suc}= 1$ is at most $p_s$ by the same argument as above. Hence, the utility of $\mathcal {A}$ when the tampering was detected is at least $(1-p_s)u_3$. Thus, the utility of $\mathcal {A}$ in the SMT game is at least

$$\begin{aligned} u(\mathcal {A},U)&\ge (1 - p_d) \left( (1-p_s) u_1 + p_s u_2 \right) + p_d (1-p_s) u_3 \nonumber \\&= (1-p_s) u_1 + p_s u_2 - p_d \left( (1 - p_s)u_1 + p_s u_2 - (1-p_s)u_3 \right) \nonumber \\&\ge (1 - p_s) u_3 \\&\ge \frac{1}{2}\left( 1 - \frac{1}{|\mathcal {M}|}\right) u_3 \nonumber \end{aligned}$$

(4)

$$\begin{aligned}&> u_2, \end{aligned}$$

(5)

where (4) follows from the fact that $p_d \le 1$ and $(1-p_s)u_1 + p_s u_2 - (1-p_s)u_3 \ge 0$, and the assumption on U is used in (5). Therefore, $\varPi$ does not satisfy the security of RSMT protocols for $t \ge n/2$.

When $n = 2t-1$, the same attack of the above $\mathcal {A}$ can be realized by invalidating the n-th channel by substituting $\bot$ for every message over the n-th channel.

   $\square$

The theorem gives the following corollary.

Corollary 2

There is no SMT protocol without public channel that is perfectly secure against rational t-adversaries with utility function U for every $U \in U_\mathsf {timid}$ and $t \ge \lceil n/2 \rceil$.

6 Conclusion

We have introduced the notion of rationality into secure message transmission. Specifically, we have defined timid adversaries, who prefer to violate the security requirements of SMT, but do not prefer the tampering actions to be detected. It is shown that some type of almost-reliable SMT protocols using a public channel (such as [32]) work as perfect SMT for any timid adversary corrupting $t < n$ channels. By imposing the assumption that $u_2 > u_3$, which captures strictly timid adversaries, it is possible to construct a non-interactive perfect SMT protocol against $t < n$ corruptions without using public channels.

A future work is to construct protocols against adversaries having different preferences from timid ones. It is important to clarify for which rational adversary the existing impossibility results hold.

Appendices

A Universal Hash Functions

Wegman and Carter [34] defined a notion of (almost) universal hash functions and gave its construction. We use an SMT protocol in which universal hash functions are used.

Definition 5

Suppose that a class of hash functions $H = \{h :\{0,1\}^m \rightarrow \{0, 1\}^\ell \}$, where $m \ge \ell$, satisfies the following: for any distinct $x_1,x_2\in \{0,1\}^m$ and $y_1,y_2\in \{0,1\}^\ell$,

$$\begin{aligned} \mathop {\Pr }\limits _{h\in H} [ h(x_1)=y_1 \wedge h(x_2)=y_2 ] \le \gamma . \end{aligned}$$

Then H is called $\gamma$-almost strongly universal. In the above, the randomness comes from the uniform choice of h over H.

Here we mention a useful property of almost universal hash functions, which guarantees the security of some SMT protocols.

Lemma 1

([32]). Let $H = \{h :\{0,1\}^m \rightarrow \{0, 1\}^\ell \}$ be a $\gamma$-almost strongly universal hash function family. The for any $(x_1,c_1)\ne (x_2,c_2)\in \{0,1\}^m\times \{0,1\}^\ell$, we have

$$\begin{aligned} \mathop {\Pr }\limits _{h\in H} [ c_1\oplus h(x_1) = c_2\oplus h(x_2) ] \le 2^{\ell }\gamma . \end{aligned}$$

In [34], Wegman and Carter constructed a family of $2^{1-2\ell }$-almost strongly universal hash functions. In particular, their hash function family $H_{wc} = \{ h :\{0,1\}^m\rightarrow \{0,1\}^{\ell } \}$ satisfies that

$$\begin{aligned} \mathop {\Pr }\limits _{h\in H_{wc}} [ h(x_1)=y_1 \wedge h(x_2)=y_2 ] = 2^{1-2\ell } \end{aligned}$$

for any distinct $x_1,x_2\in \{0,1\}^m$ and for any $y_1,y_2\in \{0,1\}^{\ell }$ and also

$$\begin{aligned} \mathop {\Pr }\limits _{h\in H_{wc}} [ c_1\oplus h(x_1) \wedge c_2 \oplus h(x_2) ] = 2^{1-\ell } \end{aligned}$$

for any distinct pairs $(x_1,c_1)\ne (x_2,c_2)\in \{0,1\}^m\times \{0,1\}^{\ell }$.

B Proof of Theorem 3

To prove the theorem, we define the notion of algebraic manipulation detection (AMD) codes in which the security requirement is slightly different from that in [9] for our purpose.

Definition 6

An $(M, N, \delta )$-algebraic manipulation detection (AMD) code is a probabilistic function $E :\mathcal {S} \rightarrow \mathcal {G}$, where $\mathcal {S}$ is a set of size M and $\mathcal {G}$ is an additive group of order N, together with a decoding function $D :\mathcal {G} \rightarrow \mathcal {S} \cup \{\bot \}$ such that

• Correctness: For any $s \in \mathcal {S}$, $\Pr [ D( E(s) ) = s] = 1$.

• Security: For any $s \in \mathcal {S}$ and $\varDelta \in \mathcal {G} \setminus \{0 \}$, $\Pr [D ( E(s) + \varDelta ) \ne \bot ] \le \delta$.

An AMD code is called systematic if $\mathcal {S}$ is a group, and the encoding is of the form

$$\begin{aligned} E :\mathcal {S} \rightarrow \mathcal {S} \times \mathcal {G}_1 \times \mathcal {G}_2, s \mapsto (s, x, f(x,s)) \end{aligned}$$

for some function f and random $x \in \mathcal {G}_1$. The decoding function D of a systematic AMD code is given by $D( s', x', f') = s'$ if $f' = f(x',s')$, and $\bot$ otherwise.

Note that, for a systematic AMD code, the correctness immediately follows from the definition of the decoding function. The security requirement can be stated such that for any $s \in \mathcal {S}$ and $(\varDelta _s, \varDelta _x, \varDelta _f) \in \mathcal {S} \times \mathcal {G}_1 \times \mathcal {G}_2 \setminus \{ (0,0,0)\}$, $\Pr _x[ f(s + \varDelta _s, x + \varDelta _x) = f(s, x) + \varDelta _f] \le \delta$.

We show that a systematic AMD code given in [9] satisfies the above definition.

Proposition 1

Let $\mathbb {F}$ be a finite field of size q and characteristic p, and d any integer such that $d+2$ is not divisible by p. Define the encoding function $E :\mathbb {F}^d \rightarrow \mathbb {F}^d \times \mathbb {F}\times \mathbb {F}$ by $E(s) = (s, x, f(x,s))$ where

$$\begin{aligned} f(x,s) = x^{d+2} + \sum _{i=1}^{d} s_i x^i \end{aligned}$$

and $s = (s_1, \dots , s_d)$. Then, the construction is a systematic $(q^d, q^{d+2}, (d+1)/q)$-AMD code.

Proof

We show that for any $s \in \mathbb {F}^{d}$ and $(\varDelta _s, \varDelta _x, \varDelta _f) \in \mathbb {F}^d \times \mathbb {F}\times \mathbb {F}\setminus \{(0^d,0,0)\}$, $\Pr [ f(s+\varDelta _s, x+ \varDelta _x) = f(s,x) + \varDelta _f] \le \delta$. The event in the probability is that

$$\begin{aligned} (x+\varDelta _x)^{d+2} + \sum _{i=1}^d s_i'(x+\varDelta _x)^i = x^{d+2} + \sum _{i=1}^d s_ix^i + \varDelta _f, \end{aligned}$$

(6)

where $s_i'$ is the i-th element of $s+\varDelta _s$. The left-hand side of (6) can be represented by

$$\begin{aligned} x^{d+2} + (d+2)\varDelta _x x^{d+1} + \sum _{i=1}^d s_i' x^i + \varDelta _x p(x) \end{aligned}$$

for some polynomial p(x) of degree at most d. Thus, (6) can be rewritten as

$$\begin{aligned} (d+2)\varDelta _x x^{d+1} + \sum _{i=1}^d (s_i' - s_i) x^i + \varDelta _x p(x) - \varDelta _f = 0. \end{aligned}$$

(7)

We discuss the probability that (7) happens when x is chosen uniformly at random. We consider the following cases:

• 1. When $\varDelta _x \ne 0$, the coefficient of $x^{d+1}$ is $(d+2) \varDelta _x$, which is not zero by the assumption that $d+2$ is not divisible by p. Then, (7) has at most $d+1$ solutions x. Hence the event happens with probability at most $(d+1)/q$.

• 2. When $\varDelta _x = 0$, we consider two subcases:

  • (a) If $\varDelta _s \ne 0$, then $s_i' - s_i \ne 0$ for some i. Hence (7) has at most d solutions x. Thus the event happens with probability at most d / p.

  • (b) If $\varDelta _s = 0$, (7) is equivalent to $\varDelta _f = 0$. Since $\varDelta _f \ne 0$ for this case, the event cannot happen.

In every case, the event happens with probability at most $(d+1)/q$. Thus the statement follows.    $\square$

As discussed in [9], a robust secret sharing scheme can be obtained by combining an AMD code and a linear secret sharing scheme. Let $(\mathsf {Share}, \mathsf {Reconst})$ be a (t, n)-secret sharing scheme with range $\mathcal {G}$ that satisfies correctness and perfect privacy of Definition 2, where we drop the parameter $\delta$ for robustness. A linear secret sharing scheme has the property that for any $s \in \mathcal {G}$, $(s_1, \dots , s_n) \in \mathsf {Share}(s)$, and vector $(s_1', \dots , s_n')$, which may contain $\bot$ symbols, it holds that $\mathsf {Reconst}( \{i, s_i + s_i'\}_{i \in I}) = s + \mathsf {Reconst}( \{i, s_i'\}_{i \in I})$ for any $I \subseteq \{1, \dots , n\}$ with $|I| > t$, where $\bot + x = x + \bot = \bot$ for all x. Examples of linear secret sharing schemes are Shamir’s scheme [31] and the simple XOR-based $(n-1,n)$-scheme, in which secret $s \in \{0,1\}^n$ is shared by $(s_1, \dots , s_n)$ for random $s_i\in \{0,1\}^n$ with the restriction that $s_1 \oplus \dots \oplus s_n = s$.

We show that the same construction as in [9] works as a construction of robust secret sharing of Definition 2.

Proposition 2

Let $(\mathsf {Share}, \mathsf {Reconst})$ be a linear (t, n)-secret sharing scheme with range $\mathcal {G}$ that satisfies correctness and perfect privacy of Definition 2, and let (E, D) be an $(M,N,\delta )$-AMD code of Definition 6 with $|\mathcal {G}| = N$. Then, the scheme $(\mathsf {Share}', \mathsf {Reconst}')$ defined by $\mathsf {Share}'(s) = \mathsf {Share}(E(s))$ and $\mathsf {Reconst}'(S) = D(\mathsf {Reconst}(S))$ is a $(t,n,\delta )$-robust secret sharing scheme.

Proof

Let $(s_1, \dots , s_n) \in \mathsf {Share}'(s)$. Let $I \subseteq \{1,\dots ,n\}$ with $|I| \le t$, and $(\tilde{s}_1, \dots \tilde{s}_n)$ be a sequence of shares satisfying the requirement for input shares in robustness of Definition 2. We assume that $\tilde{s}_i = s_i + \varDelta _i'$ for each $i \in \{1,\dots ,n\}$. Note that $\varDelta _i' = 0$ for every $i \notin I$. Then,

$$\begin{aligned}&\Pr \left[ \mathsf {Reconst}'\left( \{i,\tilde{s}_i\}_{i \in \{1,\dots ,n\}}\right) \ne \bot \right] \\&= \Pr \left[ D\left( E(s) + \mathsf {Reconst}(\{ i, \varDelta _i\}_{i \in \{1,\dots ,n\}}) \right) \ne \bot \right] \\&= \Pr \left[ D\left( E(s) + \varDelta \right) \ne \bot \right] , \end{aligned}$$

where $\varDelta = \mathsf {Reconst}\left( \{ i, \varDelta _i\}_{i \in \{1,\dots ,n\}}\right)$ is determined by the adversary. It follows from perfect privacy of the secret sharing scheme that $\varDelta$ is independent of E(s). Thus, if $\tilde{s}_i \ne s_i$ for some $i \in \{1, \dots , n\}$, the probability is at most $\delta$ by the security of the AMD code. Hence, the statement follows.    $\square$

By combining Shamir’s secret sharing scheme with range $\mathbb {F}^d$ and the AMD code of Proposition 1, the robust secret sharing scheme of Theorem 3 is obtained by Proposition 2.