Perfectly Secure Message Transmission Against Rational Timid Adversaries

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. 1.

   The robustness in [9] requires that the output of the reconstruction algorithm should be either the original message or the failure symbol with high probability. Namely, it is allowed to recover the original message even if some shares are tampered with. In Definition 2, we require that if some shares are tampered with, the output of the reconstruction algorithm should be the failure symbol.

This work was supported in part by JSPS Grant-in-Aid for Scientific Research Numbers 16H01705, 17H01695, and 18K11159. The second author thanks to Masaki Ueno for discussions about this work.

Authors and Affiliations

1. Graduate School of Science and Engineering, Saitama University, Saitama, Japan

   Maiki Fujita

2. Graduate School of Information Science and Technology, Osaka University, Osaka, Japan

   Kenji Yasunaga

3. Faculty of Education and Integrated Arts and Sciences, Waseda University, Tokyo, Japan

   Takeshi Koshiba

Corresponding author

Correspondence to Takeshi Koshiba .

Editors and Affiliations

1. University of Washington, Seattle, WA, USA

   Linda Bushnell

2. University of Washington, Seattle, WA, USA

   Radha Poovendran

3. University of Illinois at Urbana–Champaign, Urbana, IL, USA

   Tamer Başar

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 \),

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

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

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

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

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

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

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

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

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

1. 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. 2.

   When \(\varDelta _x = 0\), we consider two subcases:

   1. (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.

   2. (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,

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.

Reprints and permissions

© 2018 Springer Nature Switzerland AG

Policies and ethics