Information-theoretically secure equality-testing protocol with dispute resolution

Go Kato, Mikio Fujiwara, and Toyohiro Tsurumaru Go Kato and Mikio Fujiwara are with National Institute of Information and Communications Technology (NICT), Nukui-kita, Koganei, Tokyo 184-8795, Japan (e-mail: [email protected], [email protected]). Toyohiro Tsurumaru is with Mitsubishi Electric Corporation, Information Technology R&D Center, 5-1-1 Ofuna, Kamakura-shi, Kanagawa, 247-8501, Japan (e-mail: [email protected]).

Abstract

There are often situations where two remote users each have data, and wish to (i) verify the equality of their data, and (ii) whenever a discrepancy is found afterwards, determine which of the two modified his data. The most common example is where they want to authenticate messages they exchange. Another possible example is where they have a huge database and its mirror in remote places, and whenever a discrepancy is found between their data, they can determine which of the two users is to blame.

Of course, if one is allowed to use computational assumptions, this function can be realized readily, e.g., by using digital signatures. However, if one needs information-theoretic security, there is no known method that realizes this function efficiently, i.e., with secret key, communication, and trusted third parties all being sufficiently small.

In order to realize this function efficiently with information-theoretic security, we here define the “equality-testing protocol with dispute resolution” as a new framework. The most significant difference between our protocol and the previous methods with similar functions is that we allow the intervention of a trusted third party when checking the equality of the data. In this new framework, we also present an explicit protocol that is information-theoretically secure and efficient.

Index Terms:

Information-theoretic security, data integrity, non-repudiation, equality-testing, quantum key distribution.

I Introdution

There are often situations where two remote users each have data which are supposed to be the same, and they want to (i) verify that their data are indeed the same, and (i) whenever a discrepancy between their data is found afterwards, determine which of the two actually modified his data. Here, we consider “equality-testing protocols with dispute resolution” (or ET protocols for short) for realizing this function and study its information-theoretic security.

The most straightforward application of this protocol would be where the two party want to authenticate messages they exchange, and also prevent further change. Another possible example is where the two users have a huge database and its mirror in remote places. If this type of protocols is realized, they will be able to confirm the equality of the data on both sides, and moreover, whenever a discrepancy is found afterwards, they can determine which of the two users is to blame.

Of course, if one is allowed to use computational assumptions, our ET protocol can be realized readily, e.g., by using digital signatures. However, if one needs information-theoretic security, there is no known method for realizing it efficiently, i.e., with sufficiently small amounts of secret keys and communication, and with at most one trusted third party (TTP). At first glance, this function seems feasible by a straightforward use of the $A^{2}$ code [1, 2, 3, 4] or the unconditionally secure digital signature schemes (USDS) [5, 6], but these methods consume enormous resources (communication and secret key) and thus not practical. More precisely, both the communication length and the secret key length of these methods must exceed the data length, so they become virtually impossible when one needs to handle larger data, such as an entire data center (see section II-C).

Here we rigorously define a framework for ET protocols which admits information-theoretic security and efficient implementation. The most significant difference between our protocol and the previous methods with similar functions (i.e., $A^{2}$ codes and USDSs) is that we allow the intervention of a TTP in the equality-testing phase, which corresponds to message authentication tag generation in the previous methods (see II-C4 section for the detail). Then in this generalized framework, we also present an explicit protocol that is information-theoretically secure and efficient. Namely, we present a protocol achieving

	$\displaystyle{\rm lengths\ of\ communication\ and\ secret\ key}$
	$\displaystyle=O\left(\log(1/\epsilon)\cdot\log r\right)$		(1)

with $r$ being the data length and $\epsilon$ being the security parameter (success probability of a malicious player). Note that parameter region (1) indeed overcomes the limitations of the aforementioned previous methods.

We note that our ET protocols are particularly useful in and compatible with quantum key distribution networks (QKDNs) [7, 8], for the following two reasons. First, a QKDN normally has a key management authority, which can be used as the TTP for our protocol. Second, our protocols need to be supplied with a new secret key each time they are executed. The only ways to fulfill this requirement, at least at present, are either to use the so-called trusted courier or to use a QKDN.

Note that this implies that our protocols greatly enhance the functionality of QKDNs. It is often thought that QKDNs can only be used for limited purposes, namely, one-to-one secret communication and authentication. Our protocols, however, indeed provide more versatile cryptographic functionalities, such as the message authentication with non-repudiation, or the mirroring of huge databases with modification prevention, mentioned at the beginning of this section.

Finally we note that our ET method can also be seen as an improvement of the method proposed and implemented in Ref. [9] which realizes ITS message authentication function using QKDN, secret sharing, and TTPs. In this method, tamper resistance and dispute resolution functions are implemented using two types of TTPs: a shared calculator and a verifier. Our method here realizes a similar function with a reduced number of TTPs, i.e., with only one TTP, and benefits in terms of cost savings and scalability.

II Definition of equality-testing protocol with dispute resolution

II-A Setting and the definition of the protocol

Suppose that a trusted third party (TTP) and two players, Alice and Bob, are connected to each other by unauthenticated public channels¹¹1Channels where messages are neither encrypted nor authenticated.. Also suppose that Alice and Bob each holds data $m^{A},m^{B}\in\{0,1\}^{r}$ , which are supposed to be equal. Our goal here is to (i) verify the equality of $m^{A}$ and $m^{B}$ , and (ii) whenever a discrepancy is found afterwards, determine with certainty which of the two actually modified his data. To this goal we define the following type of protocols.

Definition 1 (Equality-testing protocol with dispute resolution (ET protocol, for short), Fig. 1).

A equality-testing protocol with dispute resolution is where Alice and Bob check the equality of their data with the help of the TTP, and consists of the following three phases.

1.

Key-distribution phase: The TTP distributes secret keys to Alice and Bob ²²2They share secret keys by using some method other than the public channels..
2.

Equality-testing phase: The TTP communicates with Alice and Bob, and verifies the equality of their data (whether $m^{A}=m^{B}$ or not). If the equality is confirmed, the TTP announces “success”; otherwise, it announces “failure”.
3.

Dispute-resolution phase: After a successful completion of the equality-testing phase, if there is a dispute between Alice and Bob about the equality of their data, the TTP arbitrates as follows:

The TTP receives data $m^{A*},m^{B*}$ from Alice and Bob respectively, which they claim to be correct. Then he compares them with the communication content of the equality-testing phase, and announces one of the following: “both are correct”, “ $m^{A*}$ is correct”, “ $m^{B*}$ is correct” or “undecidable”.

Throughout the paper, whenever the TTP “announces” something, it means that he sends the same message to both Alice and Bob simultaneously.

The “dispute” that triggers the dispute-resolution phase can occur, e.g., when an outsider (other than Alice, Bob, or the TTP) retrieves the same part of Alice’s and Bob’s data respectively, which should equal, but finds a discrepancy.

Refer to caption — Figure 1: Conceptual diagram of our ET protocol.

II-B Security criteria

The basic concept behind our security is that “honest players lose nothing.” The situations can be classified into the following three cases.

•

If both Alice and Bob are honest, their claims are always accepted (soundness).
•

If only one of Alice or Bob is honest, then the honest one will lose with a negligible probability ( $\epsilon$ -unmodifiable).
•

If both Alice and Bob are malicious (i.e., not honest), they gain nothing; i.e., our protocols are not responsible for this case.

Of these three cases, the first two needs to be addressed. We define these cases rigorously as follows.

Definition 2 (Security criteria of our ET protocols).

We say that an ET protocol is $\epsilon$ -secure if it satisfies the following two conditions.

•

Soundness: If both Alice and Bob are honest and their data are the same ( $m^{A}=m^{B}$ ), then the equality-testing phase always succeeds.
•

$\epsilon$ -unmodifiability: Suppose that Alice is honest and the TTP announces “success” in the equality-testing phase. Then in the subsequent dispute-resolution phase, the TTP announces an outcome unfavorable to Alice (namely, “ $m^{B*}$ is correct” or “undecidable”) with a probability $\leq\epsilon$ .

In addition, the same condition also holds with the roles of Alice and Bob being exchanged.

This definition does not prohibit malicious players from intentionally disabling the equality-testing phase. However, this does not mean that the security is compromised. Indeed, there is no protocol from which one can expect more, as can be seen as follows: Suppose, for example, that Alice is honest and Bob is malicious, and Bob performs the equality-testing phase correctly as specified, though by using a wrong data $m^{B*}(\neq m^{A})$ . From the perspective of the TTP, this situation cannot be distinguished from the one in which the “honest” Bob has the “correct” data $m^{B*}$ , and the “malicious” Alice tries to claim a “wrong” data $m^{A}$ . In such situation, and if the equality-testing phase cannot fail and thus Bob can trigger the dispute-resolution, Alice will be judged malicious with a significant probability of $1/2$ , even though she is actually honest.

II-C Background to the definition above

Next, we explain the background that led to the above settings and security criteria.

II-C1 We want to be able to handle huge data

Even when the data is huge (e.g., genome data ( $r\geq 10^{9}$ ) or the entire data center ( $r\geq 10^{15}$ )), the resource comsumption (namely, communication volume, and secret key length) should be sufficiently smaller than $r$ , so that the protocol can be executed efficienly in practice.

II-C2 Dispute-resolution phase as a deterrent

It is natural that Alice and Bob disclose their data $m_{A}^{*},m_{B}^{*}$ themselves in the dispute-resolution phase. However, if this happens frequently, the average communication length per protocol execution will be enormous, contradicting the requirements of the preceding paragraph.

Therefore, we here assume that the actual frequency of dispute-resolution is sufficiently low, and thus the communication length for the dispute-resolution can be ignored when evaluating the performance of the protocol. (On the other hand, the consumption of secret keys will always be taken into account). Note that this evaluation criterion is the same as that of conventional non-repudiation MACs (e.g., [5]), so it is by no means a weakness specific to our method.

In order to justify this evaluation criterion, we will focus on situations where “though the dispute-resolution is not frequent, once it actually happens and the fraud is discovered, the damage will be enormous.” In other words, we assume that dispute-resolution is a deterrent and that it will not be executed frequently. For example, if the data is an official document or a will, any modification to it would immediately mean an illegal act, and if discovered, would inevitably result in legal punishment³³3Conversely, our protocols are not suitable for situations where a malicious player can easily escape before an dispute resolution occurs..

II-C3 Straightforward use of MAC does not work

Next, we will make comparisons with the existing methods.

For the sake of simplicity, we first ignore resources. If Alice and Bob only needs to check the equality of their data, it suffices for them to exchange message authentication code (MAC) tags (Fig.2(a))⁴⁴4Bob consider $m^{B}$ in our scheme to be the message received from Alice, and verify its MAC. Alice also does the same.. In addition if they also wish to determine which of the two, Alice or Bob, actually modified the data (i.e., if they want $\epsilon$ -unmodifiability), they can do so by using a MAC scheme equipped with a non-repudiation function (hereafter referred to as non-repudiation MACs).

However, non-repudiation MACs are either limited in usage or consume too much resource to be practical. Indeed, as we require information theoretic security (ITS) here, we cannot use those schemes based on computational assumptions, such as the widely used digital signature schemes (see, e.g., Ref. [10], Chapter 13). There are also non-repudiation MACs achieving ITS, such as $A^{2}$ code [1, 2, 3, 4] and unconditionally secure digital signature (USDS) [5, 6], but they are subject to the following restrictions,

$\displaystyle({\rm communication\ of\ the\ equality}$	$\displaystyle\ {\rm testing\ phase}\geq)$
$\displaystyle\ {\rm MAC\ tag\ length}$	$\displaystyle>{\rm data\ length}\ r,$	(2)
$\displaystyle{\rm MAC\ key\ length}$	$\displaystyle>{\rm data\ length}\ r,$	(3)

again contradicting the requirements of Section II-C1.

Inequality (2) can readily be proved for non-repudiation MACs in general. On the other hand, Inequality (3) is an empirical relation which seems to hold for all the practical non-repudiation MAC schemes that we are aware of (see Refs. [1, 2, 3, 4, 5, 6] and references therin).

II-C4 TTP’s intervention is necessary in the equality-testing phase

Moreover, it can easily be shown that Inequality (2) in fact holds for any ET protocol in which the TTP does not intervene in the equality-testing phase (Fig.2(b)). Therefore, in order to avoid restriction (2), we need to generalize the setting by letting the TTP intervene in the equality-testing.

We consider this to be a natural generalization: All the existing non-repudiation MAC schemes allow the TTP’s intervention in the key-distribution and the dispute-resolution phases, so there is no reason to prohibit it only in the equality-testing phase.

II-D Compatibility with quantum key distribution networks

Furthermore, our ET protocols are particularly compatible with the quantum key distribution network (QKDN) [7, 8]. The reasons are as follows.

First, the generalized setting where the TTP intervenes in the equality-testing phase, described in the previous section, can easily be realized in QKDNs. This is because a QKDN normally has a key management authority, which is a TTP that is always in operation, and thus suitable for the present purpose.

Second, as is always the case with information-theoretic cryptographic protocols in general, this protocol needs to be supplied with a new secret key each time . In order to achieve this, at least at present, one must either use the so-called trusted courier (i.e., the TTP himself physically delivers a storage medium containing the key) or use quantum key distribution.

II-E Nontrivial part of the problem

Once one accepts that the TTP can intervene in the equality-testing phase, the simplest construction might seem to be the one in which both Alice and Bob send $m^{A},m^{B}$ and/or the corresponding MAC tags to the TTP. However, such constructions is again found impractical by a similar reasoning as in Section II-C3: If a MAC scheme without the non-repudiation function is used there, the protocol can indeed detect if there was a modification at all, but cannot determine which of the two, Alice or Bob, modified his/her data (no $\epsilon$ -nonmodifiability). Hence a non-repudiation MAC scheme with ITS is necessary, but that again makes the protocol subject to Inequalities (2) and (3), contradicting the requirements of Section II-C1.

Therefore, we need a construction different from the conventional non-repudiation MAC schemes.

III Efficient ET protocol with information-theoretic security

With the above setting and security criteria, we propose a secure and efficient protocol that is free from restrictions (2) and (3), and achieves (1); hence it can be used in the parameter region

{\rm communication\ length},\ {\rm key\ length}<<{\rm data\ length}\ r.

(4)

Our protocol is specified in Table “Protocol 1.”

Protocol 1 Efficient ET protocol with information-theoretic security

Key-distribution phase: The TTP distributes secret keys as follows.

Randomly select

n

distinct numbers out of

\{1,\dots,N\}

, and denote them by

\Omega

(i.e.

\Omega\subset_{\rm R}[N]

, with

[N]:=\{1,2,\cdots,N\}

Randomly select “equality-testing keys”

k^{A}_{\rm et}=(k^{A}_{1},k^{A}_{2},\cdots,k^{A}_{N})

k^{B}_{\rm et}=(k^{B}_{1},k^{B}_{2},\cdots,k^{B}_{N})

with

k^{A}_{i},k^{B}_{j}\in\{0,1\}^{l}

, such that

k^{A}_{j}=k^{B}_{j}

for

j\in\Omega

. (For example: First choose all

k^{A}_{i}

’s according to the uniform distribution, then let

k^{B}_{j}=k^{A}_{j}

for

j\in\Omega

, and then choose the undecided elements of

k^{B}_{j}

’s according to the uniform distribution.)

Randomly select “secure communication keys”

k^{A}_{\rm sc},k^{B}_{\rm sc}\in\{0,1\}^{l_{\rm sc}}

Send

k^{A}_{\rm et},k^{A}_{\rm sc}

to Alice, and

k^{B}_{\rm et},k^{B}_{\rm sc}

to Bob.

\dagger

All subsequent communications must be authenticated in an information theoretic manner; e.g., by using MAC scheme specified by Lemma 2 and consuming part of secure communication keys

k^{A}_{\rm sc},k^{B}_{\rm sc}

Equality-testing phase

Alice calculates hash values

s^{A}_{i}:=f(k^{A}_{i},m^{A})

(

i=1,\dots,N

) by using a hash function

f

specified by Lemma 1. Then she encrypts them (by using the one-time pad consuming part of

k^{A}_{\rm sc}

) and sends it to the TTP. Bob also does the same.

The TTP announces “success” if

s^{A}_{j}=s^{B}_{j}

for

\forall j\in\Omega

holds; otherwise she announces “failure”.

Dispute-resolution phase

Alice (Bob) sends data

m^{A*}

(

m^{B*}

) to the TTP.

The TTP performs the following checks: With

g^{\alpha\beta}:=\big{|}\{j\in U|f(k^{\alpha}_{j},m^{\beta})=s^{\alpha}_{j}\}\big{|}

for

\alpha,\beta\in\{A,B\}

1.

Announce “Both is correct” if $m^{A*}=m^{B*}$ and finish.
2.

Announce “ $m^{A*}$ is correct” if $g^{AA}=N\;\land\;(g^{BA}>g^{AB}\;\lor\;g^{BB}<N)$ , and finish.

Also perform the same check with indices $A,B$ exchanged.
3.

Announce “undecidable.”

The function $f$ appearing there should satisfy the condition of the following lemma.

Lemma 1 (Almost universal₂ hash function using polynomials, Ref. [11], or Ref. [10], Theorem 4.17).

There exists a function $f:(k,m)\mapsto s$ with $k\in\{0,1\}^{l},m\in\{0,1\}^{r},s\in\{0,1\}^{l}$ satisfying the following: With variable $K\in\{0,1\}^{l}$ being uniformly distributed, and for arbitrary distinct pair of data $m\neq m^{\prime}\in\{0,1\}^{r}$ , we have

\displaystyle\Pr\left[f(K,m)=f(K,m^{\prime})\right]

\displaystyle\leq\left\lceil\frac{r}{l}-1\right\rceil 2^{-l}.

(5)

Also, all the communications in the equality-testing and dispute-resolution phases should be authenticated in an information theoretic manner; e.g., by using the following MAC scheme and consuming part of pre-distributed keys.

Lemma 2 (Information-theoretically secure message authentication code (ITS-MAC). See, e.g, Ref. [10], Theorems 4.17 and 4.25).

There exists an ITS-MAC scheme satisfying the following: The MAC tag $t\in\{0,1\}^{n+l}$ is generated using a function $g:(k,m)\mapsto t$ from a message $m\in\{0,1\}^{r^{\prime}}$ with the uniformly distributed key $k\in\{0,1\}^{2(n+l)}$ , and it achieves $\left\lceil\frac{r^{\prime}}{n+l}-1\right\rceil 2^{-(n+l)}$ -security (i.e., the adversary can forge the MAC tag $t$ only with a probability $\leq\left\lceil\frac{r^{\prime}}{n+l}-1\right\rceil 2^{-(n+l)}$ ).

Then this protocol satisfies the following security.

Theorem 1.

For the data length $r\geq 256$ , and for the security parameter $\epsilon\leq 2^{-4}$ , Protocol 1 is $\epsilon$ -secure, if we choose its parameters as

$\displaystyle n$	$\displaystyle=$	$\displaystyle\lceil 3\log_{2}(16/\epsilon)\rceil,$	(6)
$\displaystyle l$	$\displaystyle=$	$\displaystyle\lceil\log_{2}r\rceil,$	(7)
$\displaystyle N$	$\displaystyle=$	$\displaystyle 2n,$	(8)
$\displaystyle l_{\rm sc}$	$\displaystyle=$	$\displaystyle 4nl+16(n+l).$	(9)

In this case, the total length of secret keys ( $k^{A}_{\rm et},k^{A}_{\rm sc},k^{B}_{\rm et},k^{B}_{\rm sc}$ ) is $8(nl+2n+2l)$ bits. The total communication length of the equality-testing phase achieves $4(nl+2n+2l+1)$ bits, and that of the dispute-resolution phase is $2(r+4n+4l+2)$ bits.

Hence it indeed satisfies condition (1), anticipated in Introduction. For example, even when the data pair is 1-Pbit long ( $r=2^{50}\geq 10^{15}$ ), we can achieve $10^{-12}$ -security, with the communication length in the equality-testing phase $\leq 64$ kbit and the total secret key length $\leq 32$ kbit.

Note that, if we let $N=2,n=1$ in Protocol 1 and also let $\Omega$ fixed at $\{2\}$ , our protocol becomes an example of the straightforward construction mentioned at the beginning of Section II-E. However, this example uses a MAC scheme without the non-repudiation function, and thus cannot achieve $\epsilon$ -nonmodifiability, as already discussed in the same section. In the present method, instead of using a non-repudiation MAC, we let $N$ and $n$ be sufficiently large, and choose $\Omega$ randomly. This improves the TTP’s ability to detect malicious actions by Alice or Bob during the equality-testing phase.

IV Proof of Theorem 1

Of the two conditions presented in Definition 2, the soundness is evident, so we prove $\epsilon$ -unmodifiability only. We begin by proving the following idealized case.

Lemma 3.

Suppose that Alice, Bob and the TTP can use ideal secure channels whenever necessary in the equality-testing and the dispute-resolution phases⁵⁵5In other words, they can use channels which are completely free of tampering in the equality-testing and the dispute-resolution phases, and in addition, those channels used in Step 1 of the equality-testing phase are free of eavesdropping. (thus they do not need to consume the secure communication keys $k^{A}_{\rm sc},k^{B}_{\rm sc}$ ).

Also suppose that $r\geq 2^{8}$ and $\epsilon_{1}\leq 2^{-8}$ . Then Protocol 1 is $\epsilon_{1}$ -unmodifiable with its parameters chosen as $n=\lceil 3\log_{2}(1/\epsilon_{1})\rceil$ , $N=2n$ , $l=\lceil\log_{2}r\rceil$ .

IV-A Proof of Lemma 3

We will prove this lemma in two steps.

Lemma 4.

Under the same setting as in Lemma 3, Protocol 1 is $\epsilon_{2}$ -unmodifiable, where

	$\displaystyle\epsilon_{2}$	$\displaystyle:=\max_{t\in\{n,\dots,N\}}\frac{(N-n)!t!}{N!(t-n)!}\sum_{u=t-n}^{N-n}{N-n\choose u}q^{u}(1-q)^{N-n-u},$		(10)
	$\displaystyle q$	$\displaystyle:=\left\lceil\frac{r}{l}-1\right\rceil 2^{-l}.$		(11)

Proof.

Since the protocol is invariant under the permutation of the roles of Alice and Bob, it suffices to show for the case where Alice is honest and Bob is malicious.

In this case, Alice always submits the correct hash value $s^{A}_{i}=f(k^{A}_{i},m^{A})$ and the correct data $m^{A}$ to the TTP. On the other hand, according to Definition 2, Bob’s goal is to (i) submit some hash value $s^{B*}$ and succeed in the equality-testing phase, knowing $m^{A}$ and $k^{B}$ , and then (ii) submit some $m^{B*}(\neq m^{A})$ in the dispute-resolution phase and let the TTP announce “ $m^{B*}$ is correct” or “undecidable.”

Note that in the equality-testing phase, Bob is informed only of the result, “success” or “failure,” and that he needs to submit $m^{B*}$ only when it was “success.” Thus his success probability does not change even if he fixes $m^{B*}$ in advance in the equality-testing phase. Therefore, we may modify Bob’s goal as follows.

Malicious Bob’s goal: (Knowing $m^{A}$ , $k^{B}$ ) choose the values of both $s^{B*}$ and $m^{B*}(\neq m^{A})$ in advance, then submit them to the TTP, and let the TTP announce “success” in the equality-testing phase, and “ $m^{B*}$ is correct” or “undecidable” in the dispute-resolution phase.

In light of the description of Protocol 1, the above goal is equivalent to selecting $s^{B*}$ and $m^{B*}(\neq m^{A})$ satisfying

$\displaystyle s_{j}^{B*}$	$\displaystyle=$	$\displaystyle f(k^{B}_{j},m^{A})\ {\rm for}\ j\in\Omega,$	(12)
$\displaystyle g^{BB}$	$\displaystyle=$	$\displaystyle N,$	(13)
$\displaystyle g^{AB}$	$\displaystyle\geq$	$\displaystyle g^{BA},$	(14)

where we used the fact that $k^{A}_{j}=k^{B}_{j}$ for $j\in\Omega$ in deriving (12). By noting that condition (13) means $s^{B*}_{i}=f(k^{B}_{i},m^{B*})$ for all $i=1,\dots,N$ , we can further rewrite these conditions as

	$\displaystyle f(k^{B}_{j},m^{B*})=f(k^{B}_{j},m^{A})\ {\rm for}\ \forall j\in\Omega,$		(15)
	$\displaystyle\left\|\left\{\,j\,\|f(k^{A}_{j},m^{A})=f(k^{A}_{j},m^{B*})\right\}\right\|\geq t,$		(16)

where

t:=\left|\left\{\,j\,|f(k^{B}_{j},m^{A})=f(k^{B}_{j},m^{B*})\right\}\right|.

(17)

Below we will evaluate the probabilities of conditions (15) and (16).

Condition (15) says that $t$ subscripts of (17) (which are uniquely determined by $m^{B*}$ ) include $\Omega$ . Bob must select those $t$ subscripts (by selecting $m^{B*}$ ) without knowing $\Omega$ . Hence (15) holds with a probability

p_{\rm et}(t)={N\choose t}{t\choose n}\left({N\choose t}{N\choose n}\right)^{-1}=\frac{(N-n)!t!}{N!(t-n)!}.

(18)

Condition (16) demands that $f(k^{A}_{j},m^{A})=f(k^{A}_{j},m^{B*})$ holds for more than $t-n$ subscripts $j\in\{1,\dots,N\}\setminus\Omega$ . However, Bob does not know keys $k^{A}_{j}$ corresponding to those indices $j\in\{1,\dots,N\}\setminus\Omega$ , since they are generated independently of $k_{j}^{B}$ ’s (cf. comment inside parentheses in Protocol 1, step 1). Due to this fact and Lemma 1, condition (16) holds only with a probability

p_{\rm dr}(t)\leq\sum_{u=t-n}^{N-n}{N-n\choose u}q^{u}(1-q)^{N-n-u}.

(19)

For a fixed value of $t$ , Bob’s success probability is upper bounded by $p_{\rm et}(t)p_{\rm dr}(t)$ . Thus we have the lemma. ∎

Lemma 5.

For $r\geq 2^{8}$ , $\epsilon_{1}\leq 2^{-8}$ , $n=\lceil 3\log_{2}(1/\epsilon_{1})\rceil$ , $N=2n$ , and $l=\lceil\log_{2}r\rceil$ , we have $\epsilon_{2}\leq\epsilon_{1}$ .

Proof.

Since $N=2n$ , $p_{\rm et}(t)$ of (18) can be bounded as

$\displaystyle p_{\rm et}(t)$	$\displaystyle=$	$\displaystyle\frac{n!t!}{(2n)!(t-n)!}$	(20)
	$\displaystyle=$	$\displaystyle\frac{t}{2n}\cdot\frac{t-1}{2n-1}\cdots\frac{t-(n-1)}{2n-(n-1)}$
	$\displaystyle\leq$	$\displaystyle\left(\frac{t}{2n}\right)^{n},$

where we used that fact that $\frac{t-s}{2n-s}\leq\frac{t}{2n}$ for $0\leq s\leq t\leq 2n$ .

By Theorem 11.1.4 of Ref. [12], $p_{\rm dr}$ of (19) can be bounded as

$\displaystyle p_{\rm dr}(t)$	$\displaystyle\leq$	$\displaystyle(2n-t+1)2^{-nD(p\|\|q)},$	(21)
$\displaystyle D(p\|\|q)$	$\displaystyle=$	$\displaystyle p\log_{2}\frac{p}{q}+(1-p)\log_{2}\frac{1-p}{1-q},$	(22)
$\displaystyle p$	$\displaystyle=$	$\displaystyle t/n-1.$	(23)

If we choose $n$ as specified by the lemma, we have for $t\leq 3n/2$ ,

p_{\rm et}(t)\leq\epsilon_{1}.

(24)

On the other hand for $t>3n/2$ , we have $p\geq 1/2$ and also $q\leq 1/8$ due to $r\geq 256$ . Then we have $D(p||q)\geq 1/2$ and thus

p_{\rm dr}(t)\leq(n/2+1)2^{-n/2}\leq(n/2+1)2^{-n/6}\cdot\epsilon_{1}\leq\epsilon_{1},

(25)

where the last inequality follows by noting that $n\geq 3\log_{2}(1/\epsilon_{1})\geq 24$ .

Combining (24) and (25), we obtain the lemma. ∎

IV-B Proof of Theorem 1

Unlike the ideal situation of Lemma 3, in the actual situation described in Definition 1 one can only use unauthenticated public channels. There Alice, Bob, and the TTP must use information-theoretic MAC and/or one-time pad encryption wherever necessary.

First, communications in Step 1 of the equality-testing phase must be secret in an information-theoretic sense. This can be realized by using the one-time pad (OTP) encryption, and consumes $4nl$ bits of the secret key.

In addition, all eight communication rounds in the equality-testing and the dispute-resolution phases must be authenticated in an information-theoretic manner. Since the length $r^{\prime}$ of the content of each round satisfies $r^{\prime}\leq\max\{r,2nl\}$ , one can authenticate each round with $\epsilon_{1}$ -security by using the MAC scheme of Lemma 2. Thus for all eight rounds in total, one can achieve the overall authenticity with $8\epsilon_{1}$ -security by consuming secret keys of $16(n+l)$ -bits.

By combining the secrecy and authenticity thus realized with the result of Lemma 3, and by letting $\epsilon_{1}=\epsilon/16$ , we can achieve the $\epsilon$ -nonmodifiability in the actual situation described in Definition 1.

The breakdown of secret key consumption here is: $4nl$ bits for the equality testing keys $k^{A}_{\rm et},k^{B}_{\rm et}$ , and $4nl+16(n+l)$ bits for the secure communication keys $k^{A}_{\rm sc},k^{B}_{\rm sc}$ . The latter consists of $4nl$ bits for the OTP encryption of $s^{A}_{i},s_{B}^{j}$ , and $16(n+l)$ bit for generating MAC tags for the eight rounds of communication. All of these add up to $8(nl+2n+2l)$ bits.

The communication length of the equality-testing phase consists of $4nl$ bits for $s^{A}_{i},s_{B}^{j}$ , four bits for the TTP’s announcements, and $8(n+l)$ bits for the MAC tags for these four rounds of communication. These add up to $4(nl+2n+2l+1)$ bits.

Similarly, for the dispute-resolution phase there are $2r$ bits of communication for $m^{A*}$ and $m^{B*}$ , two bits for the TTP’s announcements, and $8(n+l)$ bits for the MAC tags for these four rounds, all of which add up to $2(r+4n+4l+2)$ bits.

V Summary and outlook

We proposed a new type of cryptographic protocols called “equality-testing protocol with dispute resolution” (ET protocols) and also presented an explicit protocol that is information-theoretically secure and efficient. Our ET protocols enable two remote users each having data to (i) verify the equality of their data, and (ii) whenever a discrepancy is found afterwards, determine which of the two modified his data. The ET protocols are particularly useful in and compatible with quantum key distribution networks (QKDNs), and can also greatly enhance the functionality of QKDNs.

A possible future work is to reduce the amount of communication needed in the dispute-resolution phase. It will also be interesting to actually implement this type of protocols in one of real QKDNs.

Acknowledgment

M.F. and T.T. were supported in part by “ICT Priority Technology Research and Development Project” (JPMI00316) of the Ministry of Internal Affairs and Communications, Japan. This work was supported in part by JSPS KAKENHI Grant Numbers JP18H05237, JP20K03779, JP21K03388.

References

[1] T. Johansson, “Lower bounds on the probability of deception in authentication with arbitration,” IEEE Transactions on Information Theory, vol. 40, no. 5, pp. 1573–1585, 1994.
[2] ——, “On the construction of perfect authentication codes that permit arbitration,” in Advances in Cryptology — CRYPTO’ 93, D. R. Stinson, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1994, pp. 343–354.
[3] G. J. Simmons, “Message authentication with arbitration of transmitter/receiver disputes,” in Advances in Cryptology — EUROCRYPT’ 87, D. Chaum and W. L. Price, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1988, pp. 151–165.
[4] J. Bierbrauer, “A2—codes from universal hash classes,” in Advances in Cryptology — EUROCRYPT ’95, L. C. Guillou and J.-J. Quisquater, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995, pp. 311–318.
[5] G. Hanaoka, J. Shikata, Y. Zheng, and H. Imai, “Unconditionally secure digital signature schemes admitting transferability,” in Advances in Cryptology — ASIACRYPT 2000, T. Okamoto, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000, pp. 130–142.
[6] C. M. Swanson and D. R. Stinson, “Unconditionally secure signature schemes revisited,” Journal of Mathematical Cryptology, vol. 10, no. 1, pp. 35–67, 2016. [Online]. Available: https://doi.org/10.1515/jmc-2016-0002
[7] ITU-T, “Overview on networks supporting quantum key distribution,” International Telecommunication Union, Geneva, Recommendation Y.3800, Oct. 2019.
[8] M. Sasaki, M. Fujiwara, H. Ishizuka, W. Klaus, K. Wakui, M. Takeoka, S. Miki, T. Yamashita, Z. Wang, A. Tanaka, K. Yoshino, Y. Nambu, S. Takahashi, A. Tajima, A. Tomita, T. Domeki, T. Hasegawa, Y. Sakai, H. Kobayashi, T. Asai, K. Shimizu, T. Tokura, T. Tsurumaru, M. Matsui, T. Honjo, K. Tamaki, H. Takesue, Y. Tokura, J. F. Dynes, A. R. Dixon, A. W. Sharpe, Z. L. Yuan, A. J. Shields, S. Uchikoga, M. Legré, S. Robyr, P. Trinkler, L. Monat, J.-B. Page, G. Ribordy, A. Poppe, A. Allacher, O. Maurhart, T. Länger, M. Peev, and A. Zeilinger, “Field test of quantum key distribution in the Tokyo QKD network,” Opt. Express, vol. 19, no. 11, pp. 10 387–10 409, May 2011. [Online]. Available: https://opg.optica.org/oe/abstract.cfm?URI=oe-19-11-10387
[9] M. Fujiwara, R. Nojima, T. Tsurumaru, S. Moriai, M. Takeoka, and M. Sasaki, “Long-term secure distributed storage using quantum key distribution network with third-party verification,” IEEE Transactions on Quantum Engineering, vol. 3, pp. 1–11, 2022.
[10] J. Katz and Y. Lindell, Introduction to Modern Cryptography, ser. Chapman & Hall/CRC Cryptography and Network Security Series. CRC Press, 2020. [Online]. Available: https://books.google.co.jp/books?id=RsoOEAAAQBAJ
[11] M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger, “Polynomial hash functions are reliable,” in Automata, Languages and Programming, W. Kuich, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992, pp. 235–246.
[12] T. Cover and J. Thomas, Elements of Information Theory. Wiley, 2012. [Online]. Available: https://books.google.co.jp/books?id=VWq5GG6ycxMC

Go Kato was born in Japan, in 1976. He received the M.S. and Ph.D. degrees in science from The University of Tokyo in 2001 and 2004, respectively. From 2004 to 2022, he worked with the NTT Communication Science Laboratories, NTT Corporation, as a Scientist. In 2022, he joined NICT (National Institute of Information and Communications Technology), as a research manager. He has been engaged in the theoretical investigation of quantum information. He is especially interested in mathematical structures emerging in the field of quantum information. He is a member of the Physical Society of Japan.

Mikio Fujiwara received the B.S. and M.S. degrees in electrical engineering and the Ph.D. degree in physics from Nagoya University, Nagoya, Japan, in 1990, 1992, and 2002, respectively. He has been involved R&D activities at NICT (previous name CRL, Ministry of Posts and Telecommunications of Japan) since 1992.

Toyohiro Tsurumaru was born in Japan in 1973. He received the B.S. degree from the Faculty of Science, University of Tokyo, Japan in 1996, and M.S. and Ph.D. degrees in physics from the Graduate School of Science, University of Tokyo, Japan in 1998 and 2001, respectively. Then he joined Mitsubishi Electric Corporation in 2001. His research interests include theoretical aspects of quantum cryptography and of modern cryptography.

Information-theoretically secure equality-testing protocol with dispute resolution

Abstract

Index Terms:

I Introdution

II Definition of equality-testing protocol with dispute resolution

II-A Setting and the definition of the protocol

Definition 1 (Equality-testing protocol with dispute resolution (ET protocol, for short), Fig. 1).

II-B Security criteria

Definition 2 (Security criteria of our ET protocols).

II-C Background to the definition above

II-C1 We want to be able to handle huge data

II-C2 Dispute-resolution phase as a deterrent

II-C3 Straightforward use of MAC does not work

II-C4 TTP’s intervention is necessary in the equality-testing phase

II-D Compatibility with quantum key distribution networks

II-E Nontrivial part of the problem

III Efficient ET protocol with information-theoretic security

Lemma 1 (Almost universal2 hash function using polynomials, Ref. [11], or Ref. [10], Theorem 4.17).

Lemma 2 (Information-theoretically secure message authentication code (ITS-MAC). See, e.g, Ref. [10], Theorems 4.17 and 4.25).

Theorem 1.

IV Proof of Theorem 1

Lemma 3.

IV-A Proof of Lemma 3

Lemma 4.

Proof.

Lemma 5.

Proof.

IV-B Proof of Theorem 1

V Summary and outlook

Acknowledgment

References

Lemma 1 (Almost universal₂ hash function using polynomials, Ref. [11], or Ref. [10], Theorem 4.17).