# FTP: An Approximate Fast Privacy-Preserving Equality Test Protocol for Authentication in Internet of Things

Authors: Youwen Zhu; Yue Zhang; Jiabin Yuan; Xianmin Wang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Privacy-preserving string equality test is a fundamental operation of many algorithms, including privacy-preserving authentication in Internet of Things (IoT). Existing secure equality test schemes can theoretically achieve string equality comparison and preserve the private strings. However, they suffer from heavy computation and communication cost, especially while the strings are of hundreds of bits or longer, which is not suitable for IoT applications. In this paper, we propose an approximateFast privacy-preserving equality  Test  Protocol (FTP), which can securely complete string equality test and achieve high running efficiency at the cost of little accuracy loss. We strictly analyze the accuracy of our proposed scheme and formally prove its security. Additionally, we leverage extensive simulation experiments to evaluate the running cost, which confirms our high efficiency; for instance, our proposed FTP can securely compare two 256-bit strings within 0.7 seconds on ordinary laptops.


---

## Body

## 1. Introduction

In recent years, with the growth of privacy concern, privacy-preserving computation [1–4] receives increasing attention, since various privacy-preserving computation schemes can support computation on private data while keeping the privacy of the involved data. Sensitive data collection and analysis over the encrypted data become the current trend [5–12]. Based on this situation,   Privacy-preserving  Equality  Test (PET) aims at securely comparing two binary strings which are privately held by two parties. That is, by PET scheme, two participants can securely work out whether their binary strings are exactly equal or not; meanwhile each participant can obtain no useful information about the private binary string of the other participant; even two strings are the same. PET is a significant basic building of many privacy-preserving schemes, such as privacy-preserving authentication [13–15], secure comparison of biological characteristics [16–18], privacy-preserving machine learning [19–21], secure cost comparison in wireless network [22, 23], privacy-preserving threshold schema in recommendation systems [3], attribute comparison in attribute-based encryption [24–26], and secure query in cloud [27, 28]. For example, Internet-of-Things (IoT) applications may authenticate users in privacy-preserving manner. For completing the authentication, a user needs to submit his/her authentication credential to IoT system, and the system decides whether the user is legal or not by comparing the user’s authentication credential with authentication information stored in the system database. As privacy concern, the user cannot reveal his/her authentication credential to the system, and the latter can just access them in encrypted form. Meanwhile, to protect the privacy of the IoT system, any user cannot learn useful information of database stored in the IoT system. This dilemmatic problem can be solved by employing a PET protocol.As its wide applications, several works have devoted to PET recently. Nateghizad et al.’s scheme [29], denoted as NEL16, is the state-of-the-art approach to achieve PET, which is also the most efficient PET method up to now. NEL16 can be viewed as an improved method of Lipmaa and Toft’s PET scheme in [30] denoted as LT13. In LT13 [30], Lipmaa and Toft compute the Hamming distance of two private binary strings in encrypted form. Then, they generate a Lagrange interpolating polynomial that outputs 0 if the input equals 0 and outputs 1 otherwise. Finally, the comparison result is figured out in encrypted form by securely evaluating the Lagrange interpolating polynomial with encrypted Hamming distance as input. Compared to LT13, NEL16 further computes the number of “1" of binary representation of the Hamming distance in encrypted form and uses the number of “1", instead of the Hamming distance, to evaluate the Lagrange interpolating polynomial. Suppose binary representation of the Hamming distance has t bits. The number of “1” must be not bigger than t, which can be represented by using just ⌈log2t⌉ bits. While t⩾2, it always has t>⌈log2t⌉. Thus, NEL16 requires a lower-degree Lagrange polynomial and can reduce running time. However, NEL16 still cannot achieve practical running efficiency, since computing the number of “1" in encrypted form is also time-consuming. As shown in [29], while implementing them on a Linux machine of 64-bit microprocessor and 8 GB RAM to compare two 256-bit binary strings, LT13 and NEL16 both cost tens of seconds. Therefore, existing PET schemes still suffer from low efficiency.In this paper, we propose a new PET scheme, namedFast privacy-preserving equality  Test  Protocol (FTP), which has high efficiency at the cost of little error rates. In FTP, we randomly convert the original binary strings into shorter ones, then the shorter binary strings are securely compared to decide whether the original ones are the same, by which we can dramatically reduce both computation cost and communication overheads. Although FTP just compares shorter strings, we can ensure the comparison result is exactly correct if the original binary strings are the same or they have an odd number of different bits, and the comparison result has low false-positive rates while they have an even number of different bits. For data privacy, our proposed FTP can achieve provable security, and no private information is disclosed throughout the protocol. In general, our main contributions in this paper can be summarized as follows:(i)
We propose a Fast privacy-preserving equality Test Protocol, named FTP, which can achieve much high running efficiency than the state-of-the-art PET schemes. FTP can guarantee an exactly correct comparison result while the involved binary strings are the same or have an odd number of different bits and has a low false-positive rate if the compared strings have an even number of different bits.(ii)
We formally prove the security of FTP and can guarantee no privacy is disclosed throughout the proposed protocol.(iii)
We strictly analyze the accuracy loss of FTP and leverage extensive experiments to evaluate the running cost. The results indicate that FTP is highly accurate and can dramatically reduce running cost.The rest of this paper is organized as follows. In Section2, we describe preliminaries and system model. In Section 3, we present our approximate fast privacy-preserving equality test in detail and theoretically analyze its accuracy loss. In Section 4, we formally prove the security of our scheme, evaluate our running efficiency, and compare our scheme with previous ones. In Section 5, we simply review the related work. At last, we conclude this paper in Section 6.


## 2. System Model and Preliminaries

### 2.1. Paillier Encryption System

In [31], Paillier proposes a probabilistic public key encryption scheme with semantic security (Indistinguishability under Chosen-Plaintext Attack, IND-CPA). Its steps are concisely described as follows.Key Generation. Select two large enough primes p and q. Then, the secret key sk is λ=lcm(p-1,q-1), i.e., the least common multiple of p-1 and q-1. The public key pk is (n,g), where n=pq and g∈Zn2∗ such that gcd(L(gλmodn2),n)=1, that is, the maximal common divisor of L(gλmodn2), and n equals 1. Here, L(x)=(x-1)/n.Encryption. Let m0 be a number in plaintext space Zn. Select a random r∈Zn∗ as the secret parameter, then the ciphertext of m0 is c0=gm0rnmodn2.Decryption. Let c0∈Zn2 be a ciphertext. The plaintext hidden in c0 is (1)m0=Lc0λmodn2Lgλmodn2modn.In Paillier encryption system, it obviously has(2)Epkm1,r1∗Epkm2,r2=Epkm1+m2,r1∗r2modn2where Epk(m,r) denotes the encrypted result of m using public key pk and random secret parameter r. That is, the product of ciphertexts of m1 and m2 is a ciphertext of m1+m2. Thus, Paillier encryption scheme is additively homomorphic. Further, for any k∈Zn, there is (3)Epkm,rk=Epkk∗m,rkmodn2, i.e., the k-th power of Epk(m,r) is a ciphertext of k∗m.Besides, Paillier cryptosystem has the self-blinding property as it is a probabilistic encryption. For any plaintextm∈Zn, it has Epk(m,r1)∗r2n=Epk(m,r1r2)modn2 and m=Dsk(Epk(m,r1))=Dsk(Epk(m,r1)), in which Dsk(·) denotes the corresponding decryption function.Paillier encryption system is a significant secure basic tool of our scheme, which will be utilized to encrypt private data and support necessary computation. For simplicity, we usem to denote the ciphertext of m encrypted by Paillier cryptosystem, while the random parameter r is no need to be pointed out.


### 2.2. System Model

In this paper, we consider privacy-preserving user authentication in IoT. A user (named Bob) submits au-bit authentication credential to system (named Alice), and the system decides whether the user is legal or not by comparing Bob’s authentication credential with the authentication information stored in the system database. As privacy concern, Bob cannot reveal the authentication credential and authentication result to Alice, and Alice just obtains them in encrypted form. Meanwhile, to protect the privacy of Alice, Bob cannot learn any information of Alice’s database. This dilemmatic problem can be seen as a privacy-preserving equality test (PET) problem as follows.Privacy-Preserving Equality Test (PET) Problem. PET involves two parties: Alice and Bob. Alice privately hold u-bit binary strings x=(x1,x2,⋯,xu) and Bob y=(y1,y2,⋯,yu). Here, x and y can be also considered as two integers that belong to [0,2u-1]. Besides, Bob has a public key pair (pk,sk) of Paillier encryption system, where pk is public key and sk is secret key. They want to securely compare x and y such that only Alice obtains the comparison result in encrypted form; i.e., Alice gains θ in which(4)θ=1,ifx=y,0,otherwise.Additionally, x should be privately kept to Alice throughout the protocol, and Bob’s private string y cannot be disclosed to Alice or anybody else. Neither Alice nor Bob can learn the real value of θ.


### 2.3. Security Model

In this paper, we assume that the participants Alice and Bob are semihonest. It means that each participant follows the protocol correctly but records all the received information in the protocol to infer as much information about the private data of the other participant as possible. In [32], Goldreich gives a formal definition of security against semihonest adversaries, which can be described as follows.Definition 1 (privacy under semi-honest model [32]).
Letf(x,y) be a functionality and f1(x,y) (resp. f2(x,y)) denote the first (resp., second) element of f(x,y). Let Π be a two-party protocol for computing f(x,y) such that the first (resp., second) party obtains f1(x,y) (resp., f2(x,y)). The view of the first (resp., second) party during an execution of Π on (x,y), denoted as VIEW1(x,y) (resp., VIEW2(x,y)), is (x,r,m1,⋯,mt) (resp., (y,r,m1,⋯,mt)), where x (resp., y) represents the input of the first (resp., second) party, r represents its random number, and mi represents the i-th message it has received. We say that protocol Π privately computes function f, i.e., Π is secure against semihonest adversaries, if there exist probabilistic polynomial-time algorithms S1 and S2, such that(5)S1x,f1x,y≡cVIEW1x,y(6)S2y,f2x,y≡cVIEW2x,ywhere ≡c represents computational indistinguishability.


### 2.4. Design Goal

For PET problem shown in Section2.2, we aim at proposing a new solution to achieve the following security and performance goals.(i)
High Accuracy. The protocol should arrive at a correct output with high probability while both participants exactly follow the protocol steps. That is, the solution should be of high accuracy to output a correct comparison result.(ii)
Input Privacy. Throughout the protocol, each bit of the private inputs x and y should be known to its owner only. That it, any useful information about x cannot be disclosed to Bob, and y cannot be revealed to Alice.(iii)
Result Privacy. Both users cannot get the value of result θ in plaintext, and only Alice can obtain the encrypted output θ which is encrypted by Bob’s public key.(iv)
Efficiency. The protocol needs to employ a sublinear number of public key encryption and decryption such that it can achieve high running efficiency even while x and y are of hundreds of bits.


### 2.5. Review of LT13 Scheme

In this following, we will simply introduce the previous PET schemes LT13 [30].Generally, LT13 consists of two stages:(1) Computing the encrypted Hamming distance d between x and y such that only Alice learns d. During the first stage, Bob uses the public key pk to encrypt his private bit yi for i=1 to u and sends each yi to Alice. Then, based on (7) and the additively homomorphic property of Paillier encryption scheme,(7)xi⊕yi=1-yi,ifx=1,yi,ifx=0.Alice can obtain the encrypted Hamming distance d=∏i=1uxi⊕yi where xi⊕yi=1∗yi-1 if xi=1 and xi⊕yi=yi if xi=0.( 2 ) Computing the final result θ which is also known to Alice only. To this end, they first select a u-degree public Lagrange interpolation polynomial F(z)=∑i=0uαizi that satisfies F(1)=1,F(2)=F(3)=⋯=F(u+1)=0.Namely, we can correctly attain the output by settingθ=F(d+1), since 0⩽d⩽l. Second, Alice sets D=d∗1, i.e., D=d+1, and w=DS where S=R-1modn, R is randomly selected from Zn∗, and n is the large integer in the public key. After that, w will be sent to Bob, who decrypts w, encrypts wi, and returns the ciphertext wi to Alice for i=2,3,⋯,u. Finally, Alice can gain Di=wiRi and F(D)=α0∗Dα1∗∏i=2uDi, which is exactly θ because θ=F(d+1)=F(D).As can be seen, for a largerl, LT13 needs more computation and communication cost. While u=256, LT13 uses tens of seconds [29], which is far away from being practical. In this paper, we will introduce a new PET scheme which can reduce the number of invoking Paillier encryption system and thus dramatically lessen running cost at the expense of small accuracy loss.


## 2.1. Paillier Encryption System

In [31], Paillier proposes a probabilistic public key encryption scheme with semantic security (Indistinguishability under Chosen-Plaintext Attack, IND-CPA). Its steps are concisely described as follows.Key Generation. Select two large enough primes p and q. Then, the secret key sk is λ=lcm(p-1,q-1), i.e., the least common multiple of p-1 and q-1. The public key pk is (n,g), where n=pq and g∈Zn2∗ such that gcd(L(gλmodn2),n)=1, that is, the maximal common divisor of L(gλmodn2), and n equals 1. Here, L(x)=(x-1)/n.Encryption. Let m0 be a number in plaintext space Zn. Select a random r∈Zn∗ as the secret parameter, then the ciphertext of m0 is c0=gm0rnmodn2.Decryption. Let c0∈Zn2 be a ciphertext. The plaintext hidden in c0 is (1)m0=Lc0λmodn2Lgλmodn2modn.In Paillier encryption system, it obviously has(2)Epkm1,r1∗Epkm2,r2=Epkm1+m2,r1∗r2modn2where Epk(m,r) denotes the encrypted result of m using public key pk and random secret parameter r. That is, the product of ciphertexts of m1 and m2 is a ciphertext of m1+m2. Thus, Paillier encryption scheme is additively homomorphic. Further, for any k∈Zn, there is (3)Epkm,rk=Epkk∗m,rkmodn2, i.e., the k-th power of Epk(m,r) is a ciphertext of k∗m.Besides, Paillier cryptosystem has the self-blinding property as it is a probabilistic encryption. For any plaintextm∈Zn, it has Epk(m,r1)∗r2n=Epk(m,r1r2)modn2 and m=Dsk(Epk(m,r1))=Dsk(Epk(m,r1)), in which Dsk(·) denotes the corresponding decryption function.Paillier encryption system is a significant secure basic tool of our scheme, which will be utilized to encrypt private data and support necessary computation. For simplicity, we usem to denote the ciphertext of m encrypted by Paillier cryptosystem, while the random parameter r is no need to be pointed out.


## 2.2. System Model

In this paper, we consider privacy-preserving user authentication in IoT. A user (named Bob) submits au-bit authentication credential to system (named Alice), and the system decides whether the user is legal or not by comparing Bob’s authentication credential with the authentication information stored in the system database. As privacy concern, Bob cannot reveal the authentication credential and authentication result to Alice, and Alice just obtains them in encrypted form. Meanwhile, to protect the privacy of Alice, Bob cannot learn any information of Alice’s database. This dilemmatic problem can be seen as a privacy-preserving equality test (PET) problem as follows.Privacy-Preserving Equality Test (PET) Problem. PET involves two parties: Alice and Bob. Alice privately hold u-bit binary strings x=(x1,x2,⋯,xu) and Bob y=(y1,y2,⋯,yu). Here, x and y can be also considered as two integers that belong to [0,2u-1]. Besides, Bob has a public key pair (pk,sk) of Paillier encryption system, where pk is public key and sk is secret key. They want to securely compare x and y such that only Alice obtains the comparison result in encrypted form; i.e., Alice gains θ in which(4)θ=1,ifx=y,0,otherwise.Additionally, x should be privately kept to Alice throughout the protocol, and Bob’s private string y cannot be disclosed to Alice or anybody else. Neither Alice nor Bob can learn the real value of θ.


## 2.3. Security Model

In this paper, we assume that the participants Alice and Bob are semihonest. It means that each participant follows the protocol correctly but records all the received information in the protocol to infer as much information about the private data of the other participant as possible. In [32], Goldreich gives a formal definition of security against semihonest adversaries, which can be described as follows.Definition 1 (privacy under semi-honest model [32]).
Letf(x,y) be a functionality and f1(x,y) (resp. f2(x,y)) denote the first (resp., second) element of f(x,y). Let Π be a two-party protocol for computing f(x,y) such that the first (resp., second) party obtains f1(x,y) (resp., f2(x,y)). The view of the first (resp., second) party during an execution of Π on (x,y), denoted as VIEW1(x,y) (resp., VIEW2(x,y)), is (x,r,m1,⋯,mt) (resp., (y,r,m1,⋯,mt)), where x (resp., y) represents the input of the first (resp., second) party, r represents its random number, and mi represents the i-th message it has received. We say that protocol Π privately computes function f, i.e., Π is secure against semihonest adversaries, if there exist probabilistic polynomial-time algorithms S1 and S2, such that(5)S1x,f1x,y≡cVIEW1x,y(6)S2y,f2x,y≡cVIEW2x,ywhere ≡c represents computational indistinguishability.


## 2.4. Design Goal

For PET problem shown in Section2.2, we aim at proposing a new solution to achieve the following security and performance goals.(i)
High Accuracy. The protocol should arrive at a correct output with high probability while both participants exactly follow the protocol steps. That is, the solution should be of high accuracy to output a correct comparison result.(ii)
Input Privacy. Throughout the protocol, each bit of the private inputs x and y should be known to its owner only. That it, any useful information about x cannot be disclosed to Bob, and y cannot be revealed to Alice.(iii)
Result Privacy. Both users cannot get the value of result θ in plaintext, and only Alice can obtain the encrypted output θ which is encrypted by Bob’s public key.(iv)
Efficiency. The protocol needs to employ a sublinear number of public key encryption and decryption such that it can achieve high running efficiency even while x and y are of hundreds of bits.


## 2.5. Review of LT13 Scheme

In this following, we will simply introduce the previous PET schemes LT13 [30].Generally, LT13 consists of two stages:(1) Computing the encrypted Hamming distance d between x and y such that only Alice learns d. During the first stage, Bob uses the public key pk to encrypt his private bit yi for i=1 to u and sends each yi to Alice. Then, based on (7) and the additively homomorphic property of Paillier encryption scheme,(7)xi⊕yi=1-yi,ifx=1,yi,ifx=0.Alice can obtain the encrypted Hamming distance d=∏i=1uxi⊕yi where xi⊕yi=1∗yi-1 if xi=1 and xi⊕yi=yi if xi=0.( 2 ) Computing the final result θ which is also known to Alice only. To this end, they first select a u-degree public Lagrange interpolation polynomial F(z)=∑i=0uαizi that satisfies F(1)=1,F(2)=F(3)=⋯=F(u+1)=0.Namely, we can correctly attain the output by settingθ=F(d+1), since 0⩽d⩽l. Second, Alice sets D=d∗1, i.e., D=d+1, and w=DS where S=R-1modn, R is randomly selected from Zn∗, and n is the large integer in the public key. After that, w will be sent to Bob, who decrypts w, encrypts wi, and returns the ciphertext wi to Alice for i=2,3,⋯,u. Finally, Alice can gain Di=wiRi and F(D)=α0∗Dα1∗∏i=2uDi, which is exactly θ because θ=F(d+1)=F(D).As can be seen, for a largerl, LT13 needs more computation and communication cost. While u=256, LT13 uses tens of seconds [29], which is far away from being practical. In this paper, we will introduce a new PET scheme which can reduce the number of invoking Paillier encryption system and thus dramatically lessen running cost at the expense of small accuracy loss.


## 3. Privacy-Preserving Equality Test

Assumer=(r1,r2,⋯,ru) is a uniform random vector from {1,-1}u. For two binary strings x=(x1,x2,⋯,xu) and y=(y1,y2,⋯,yu), if setting d~=∑i=1uri(xi-yi)2, we have the following observations. Here, we use Δxy to denote the number of different bits of x and y. It is easy to say 0⩽Δxy⩽u.Observation 1.
Ifx=y, then d~ always equals 0.Proof.
Whilex=y, each xi-yi equals 0; thus d~≡0.Observation 2.
Ifx≠y and Δxy is odd, then it must be d~≠0.Proof.
Without loss of generality, we assume the firstΔxy bits of x and y are different from each other. That is, xi≠yi for i=1 to Δxy, and xi=yi for i=Δxy+1 to u.
In this case,(xi-yi)2=1 for i=1 to Δxy and (xi-yi)2=0 for i=Δxy+1 to u. Then, d~=∑i=1Δxyri, in which each ri∈{1,-1}. Since Δxy is odd, the number of ri=1 is impossibly equal to that of ri=-1.
Therefore, it must bed~=∑i=1Δxyri≠0, which completes the proof.Observation 3.
Ifx≠y and Δxy is even, suppose Δxy=2k(obviously,0<k⩽⌊u/2⌋), then d~=0 with the probability (2k)!/(4k∗(k!)2), and correspondingly d~≠0 with the probability (1-(2k)!/(4k∗(k!)2)).Proof.
Without loss of generality, we assume thatxi≠yi for i=1 to 2k and xi=yi for i=2k+1 to u. Then, (xi-yi)2=1 for i=1 to 2k and (xi-yi)2=0 for i=2k+1 to u. Further, we have d~=∑i=12kri.
Letλ1, λ-1 denote the number of ri=1, ri=-1, respectively, for i=1 to 2k. Then, d~=λ1-λ-1. Hence, d~=0 iff λ1=λ-1. As ri is uniformly randomly selected from {1,-1}, the probability of λ1=λ-1 is 2kk/22k, where 2kk denotes 2k choose k. Then, the probability of d~≠0 is 2kk/22k=(2k)!/(4k∗(k!)2). Accordingly, the probability of d~≠0 is (8)1-2kk22k=1-2k!4k∗k!2. It completes the proof.Observations1, 2, and 3 show we can approximatively determine x=y by comparing d~ and 0. Besides, we have (9)d~=∑i=1urixi-yi2=∑i=1urixi-2xi-1yi=∑i=1urixi-∑i=1uri2xi-1yi,since xi2=xi and yi2=yi. Then, we can get an approximative scheme for securely comparing x and y with high efficiency as follows.Basic Approach. Alice selects u numbers ri∈{1,-1} uniformly at random and computes A=∑i=1urixi. Then, Alice sets a u-bit binary vector s=(s1,s2,⋯,su) where si=1 if ri(2xi-1)=1 and si=0 otherwise and sends s to Bob. While receiving s, Bob can locally compute B=∑i=1u(2si-1)yi. Finally, Alice and Bob utilize LT13 [30] to securely compare private numbers A and B such that Alice gains A=B, i.e., Alice obtains 1 if A=B and 0 otherwise.Asxi∈{0,1}, it has (2xi-1)∈{1,-1} and ri(2xi-1)∈{1,-1}. For the security Bob cannot learn any information about xi from s, because ri is uniformly randomly selected from {1,-1}. Since 2si-1=ri(2xi-1), thus B=∑i=1u(2si-1)yi=∑i=1u(ri(2xi-1))yi. Hence, d~=0 iff A=B. That is, the basic scheme substantially determines x=y by checking d~=0. We will analyze accuracy of the basic approach in Theorem 2.Due to|A|,|B|⩽u; thus A and B can be represented by using ⌈log2u⌉+1 bits, in which ⌈log2u⌉ bits represent the value of |A|, |B| and one bit is used to denote their sign. While u⩾4, it always is ⌈log2u⌉+1<u. For example, when u=256, we have ⌈log2u⌉+1=9. Therefore, our basic scheme can dramatically reduce the running cost.Theorem 2.
For Alice and Bob’s binary stringsx=(x1,x2,⋯,xu) and y=(y1,y2,⋯,yu), when x≠y, let the probability of Δxy=i be qi for i=1,2,⋯,u, where 0⩽qi⩽1 and ∑i=1uqi=1. Namely, qi denotes the condition probability Pr(Δxy=i∣x≠y). For simplicity, suppose each qi is identical, i.e., each qi=1/u. Then, for the basic scheme, we have
( 1 ) if x=y, the basic approach always arrives at a correct result, i.e., Alice always gains 1.
( 2 ) if x≠y, the basic approach returns a false result (i.e., Alice gains 1) with the condition probability Pr(d~=0∣x≠y) in average, and correspondingly the basic scheme returns a correct result (i.e., Alice gains 0) with the probability Pr(d~≠0∣x≠y)=1-Pr(d~=0∣x≠y). Besides, it has(10)Prd~=0∣x≠y=∑i=1u/22i!u∗4i∗i!2.To simplify, we use E0 to denote the probability Pr(d~=0∣x≠y), i.e., E0=Pr(d~=0∣x≠y).Proof.
( 1 ) If x=y, it always has d~=0 according to Observation 1. As d~=A-B, then A=B holds. Thus, Alice will gain 1, i.e., the basic scheme will get an exactly correct result.
( 2 ) If x≠y, the correct result is 0. Thus, the basic will correctly complete the comparison only when A≠B. According to (9), we have A≠B iff d~≠0. Hence, in this situation, the probability that the basic scheme returns a correct result equals the condition probability Pr(d~≠0∣x≠y). Correspondingly, the basic scheme returns a false result with the probability Pr(d~=0∣x≠y). Since Δxy may be 1 to u while x≠y, then Pr(d~=0∣x≠y)=∑i=1uPr(d~=0∣Δxy=i)Pr(Δxy=i∣x≠y). On account of Observation 2, if Δxy is odd, it always has d~≠0, i.e., the probability Pr(d~=0∣Δxy=i)=0 for each odd i. Besides each Pr(Δxy=i∣x≠y)=1/u; therefore,(11)Prd~=0∣x≠y=∑i=1u/2Prd~=0∣Δxy=2iPrΔxy=2i∣x≠y=∑i=1u/2Prd~=0∣Δxy=2iu.
Observation3 has shown Pr(d~=0∣Δxy=2i)=(2i)!/(4i∗(i!)2). As a result, (12)Prd~=0∣x≠y=∑i=1u/22i!u∗4i∗i!2, which completes the proof.Theorem 3.
Let the functionsg(),f() be (13)gk=2k!4k∗k!2,fu=∑i=1u/22i!u∗4i∗i!2,where k⩾1, u⩾16, and i and u are integers. We have
( 1 )   g ( k ) > g ( k + 1 ) for any i⩾1,
( 2 ) if u is even, then f(u)>f(u+1) and f(u)>f(u+2),
( 3 ) if u is odd, then f(u)>f(u+2).Proof.
( 1 ) According to the setting, we have (14)gk+1-gk=2k+2!4k+1∗k+1!2-2k!4k∗k!2=2k+2!-2k!∗4∗k+124k+1∗k+1!2=2k!∗2k+22k+1-2k+224k+1∗k+1!2
Then,(15)gk+1-gk=2k!∗2k+2∗-14k+1∗k+1!2<0,
Therefore,g(k)>g(k+1) holds.
( 2 ) It is easy to say (16)fu=∑i=1u/22i!u∗4i∗i!2=∑i=1u/2giu.
Ifu is even, assume u=2∗v, then v=u/2=(u+1)/2 and v+1=(u+2)/2. Hence,(17)fu+1-fu=∑i=1vgiu+1-∑i=1vgiu=∑i=1v-giuu+1<0.
Besides,(18)fu+2-fu=∑i=1v+1giu+2-∑i=1vgiu=12∑i=1v+1giv+1-∑i=1vgiv=12gv+1v+1-∑i=1vgivv+1=12vv+1v∗gv+1-∑i=1vgi.
Sinceg(k)>g(k+1), we have v∗g(v+1)-∑i=1vg(i)<0. Thus, f(u+2)-f(u)<0.
As a result,f(u)>f(u+1) and f(u)>f(u+2) both are proved.
( 3 ) If u is odd, assume u=2∗v+1, then v=u/2 and v+1=(u+2)/2. Then, (19)fu+2-fu=∑i=1v+1giu+2-∑i=1vgiu.Since (u+2)/(u+1)<u/(u-1), we have (20)fu+2-fu<u+2u+1∗∑i=1v+1giu+2-uu-1∗∑i=1vgiu.That is, (21)fu+2-fu<∑i=1v+1giu+1-∑i=1vgiu-1.Because v=(u-1)/2 and v+1=(u+1)/2, it has f(u+1)=∑i=1v+1(gi/u+1) and f(u-1)=∑i=1v(gi/(u-1)). Besides, u-1 is an even integer. We have proved f(u-1)>f(u-1+2)=f(u+1). Thus,(22)fu+2-fu<fu+1-fu-1<0.Consequently, f(u)>f(u+2) is correct. It completes the proof.As we can see,Pr(d~=0∣x≠y)=f(u). Theorem 3 shows that Pr(d~=0∣x≠y) has a downward trend, as u increases. While u=16, the error probability E0=Pr(d~=0∣x≠y)=0.146 which may be too high for real applications. We can reduce the probability by generating multiple A and B with different random vector r, which can exponentially reduce the error probability. For example, if we use double A and B, then the error probability will be E02. Even when u=16, the error probability will be 0.021 around. Figure 1 shows the error probability while u ranges from 16 to 256. It indicates our error probability will be smaller than 1% while the bit length is larger than 42. When using our scheme to compare two 256-bit binary strings, the error probability will be about 0.21% only.Figure 1
E 0 2: the error probability of using double A and B, while x and y are inequal.In general, the details of our scheme with doubleA and B are formally shown in Protocol 1. First, Alice randomly generates r,R∈{1,-1}u and shares ri(2xi-1),Ri(2xi-1) with Bob. Second, Alice locally computes a=∑i=1urixi and A=∑i=1uRixi, and Bob gains b=∑i=1uri(2xi-1)yi and B=∑i=1uRi(2xi-1)yi. They decide x=y iff a=b and A=B. Third, they use 2(⌈log2u⌉+1)-bit x′ and y′ to represent (a,A) and (b,B), respectively. Finally, Alice and Bob utilize the similar methods of LT13 to securely compare x′ and y′ such that Alice gains x′=y′.Protocol 1:FTP: approximate Fast privacy-preserving equality Test Protocol.
Input: Alice privately holds a u-bit binary string x=(x1,x2,⋯,xu), and Bob holds a private u-bit binary string y=(y1,y2,⋯,yu) and the public key pair (pk,sk) of Paillier encryption scheme where pk and sk are public key and private key, respectively. Output:Alice obtains θ where θ=(x=y)?1:0, and Bob learns nothing. 1: Alice generates two random u-dimension vectors r,R∈{1,-1}u. For each i=1, let ri and Ri denote the i-th dimension of r and R, respectively. 2: Alice computes two u-dimension binary vectors s,S∈{0,1}u such that their i-th bits si and Si satisfy (1)si=1 if ri(2xi-1)=1, otherwise si=0. (2)  Si=1 if Ri(2xi-1)=1, otherwise Si=0. Alice sends s and S to Bob. 3: Alice computes a=∑i=1u‍rixi and A=∑i=1u‍Rixi. Then, Alice utilizes log2u+1 bits to represent a, A, respectively. The first bit denotes the sign where 0 denotes positive and 1 denotes negative, and the latter log2u bits represents the their absolute value. Let t=2(log2u+1). We use x′=(x1′,x2′,⋯,xt′) to denote the 2(log2u+1) bits of a and A, in which the first log2u+1 bits correspond to a, and the latter log2u+1 bits correspond to A. 4: Bob computes b=∑i=1u‍(2si-1)yi and B=∑i=1u‍(2Si-1)yi. Then, Bob utilizes log2u+1 bits to represent b, B, respectively. The first bit denotes the sign where 0 denotes positive and 1 denotes negative, and the latter log2u bits represents the their absolute value. Similarly, y′=(y1′,y2′,⋯,yt′) is used to denote the 2(log2u+1) bits of b and B, in which the first log2u+1 bits correspond to b, and the latter log2u+1 bits correspond to B. 5: For i=1 to t, Bob uses his public key pk to encrypt each private bit yi′, and sends yi′ to Alice. 6: Alice computes encrypted Hamming distance d=∏i=1t‍xi′⊕yi′, where xi′⊕yi′=1∗yi′-1 if xi′=1 and x i ′ ⊕ y i ′ = y i ′ if xi′=0. 7: Alice and Bob select a t-degree public Lagrange interpolation polynomial F(z)=∑i=0t‍αizimodn in which n is the large integer in the public key, such that F(z) satisfies F(1)=1,F(2)=F(3)=⋯=F(t+1)=0. Namely, we can correctly attain the output by setting θ=F(d+1), since 0⩽d⩽l. 8: Alice sets D=d∗1, i.e. D=d+1, and w=Dλ where λ=R-1modn and R is randomly selected from Zn∗. After that, Alice sends w to Bob. 9: Bob decrypts w, encrypts wi, and returns the ciphertext wi to Alice for i=2,3,⋯,t. 10: Alice computesDi=wiRi, and further gains the final output θ=F(D)=α0∗Dα1∗∏i=2t‍Di.


## 4. Analysis Evaluation

### 4.1. Security

We prove the security of our proposed scheme FTP through the following Theorem4.Theorem 4.
Our proposed scheme FTP discloses nothing useful about the privacy of input values and the final result.Proof.
We will discuss the view of Alice and Bob, respectively.
In our scheme FTP, Alice receivesyi′, wi for i=1,2⋯,2(⌈log2u⌉+1). Based on IND-CPA security of Paillier encryption system [31], Alice can learn nothing useful about yi′ and wi. Thus, Bob’s private data can be securely preserved.
Throughout FTP, Bob learns justs,S, and w. For each bit si in s, it has si=1 if ri(2xi-1)=1; otherwise si=0. That is, (2xi-1)=(2si-1)ri. Each ri∈{1,-1} is unknown to Bob, and we can simply assume Pr(ri=1)= Pr(ri=0)=0.5 for the view of Bob. Hence, for any si, conditional probability Pr(xi=1∣si)= Pr(xi=0∣si)=0.5, which means Bob can learn nothing about xi from si. Similarly, it is provable that S discloses nothing about xi. For w, based on the additive homomorphic property, we have w=D∗R-1modn. As R is randomly selected from Zn∗, Bob can infer no information about D from w. In general, s,S, and w reveal nothing of Alice’s private data.
To sum up, the privacy of Alice and Bob both can be preserved in our scheme FTP, which completes the proof.


### 4.2. Computation and Communication Cost

In this section, we will analyze the computation complexity and communication overheads of our proposed FTP in detail.Computation Complexity. Since simple addition and multiplication are much cheaper than encryption, decryption, and ciphertext multiplication of Paillier cryptosystem, we will ignore the simple addition and multiplication in the protocol. Throughout FTP, Bob encrypts each yi′ and wi for i=1 to 2(⌈log2u⌉+1) and decrypts one times to gain w. Alice uses yi′ and wi to compute D and θ, which requires ciphertext multiplication 2(⌈log2u⌉+1) times. In total, both Bob and Alice just employ Paillier encryption system O(logu) times.Communication Overheads. In our scheme FTP, Alice and Bob need to transmit s,S, yi′ and wi for i=1 to 2(⌈log2u⌉+1). If each ciphertext is β-bit, then the total communication overheads are 2u+2β(⌈log2u⌉+1). While u=256 and we set the public key of Paillier encryption system to be 2048 bits, the communication overheads will be 37376 bits.


### 4.3. Experiment Results

We implement our scheme and two existing efficient algorithms: LT13 and NEL16, using C language. During executing our scheme, we utilize GMP library [33] and Paillier library [34] with key size of 2048 bits. All experiments are performed on an Apple computer with macOS Sierra 10.12.6, Intel Core i5 1.6GHz CPU and 4 GB memory. Alice and Bob communicate through the socket where ping time is about 0.81 seconds.Figure2 shows the runtime of LT13, NEL16, and our scheme FTP while the compared string is of 16 to 256 bits. As can be seen, FTP can dramatically reduce the running time compared to LT13 and NEL16. When the length u is 256, LT13 costs about 25 seconds, NEL16 takes 6 seconds around, and FTP just needs 0.6 seconds. While the length is larger, the advantage of FTP will be more salient. The main reason is that we transform the original x, y into x′, y′ which is much shorter than the original ones. More importantly, our transformation just involves simple addition and multiplication and can be completed rapidly. In FTP, Paillier encryption system is employed only to securely compare x′ and y′. Therefore, FTP can reduce the running cost, especially when u is large. If the bit length is smaller than 16, FTP has no significant advantages on running time, and LT13 or NEL16 is suitable for the short-string equality comparison scenario.Figure 2
Runtime comparison of LT13, NEL16, and our scheme FTP.


### 4.4. Improvement

Though our scheme FTP can reduce the cost, it still takesu bits to transmit the vector s or S. We can further improve the scheme to avoid transmitting s or S. Let H():{0,1}∗→{0,1}u be a pseudorandom function. Alice and Bob, in advance, select a constant pad. While they decide to compare the private binary vectors, they can separately generate a random binary string H(time∥pad) where time denotes the time they decide to implement the protocol and ∥ denotes concatenation. Then, they set si=Hi in which Hi denotes the i-th bit of H(time∥pad). Since si=(ri(2xi-1)+1)/2 and (2xi-1)2=1, Alice can locally get ri=(2Hi-1)(2xi-1). Thus, Alice and Bob can compute A and B, respectively. By this method, Alice need not to send the vector s again. For S, they can preestablish another constant pad′ and use it avoid transmitting S by a similar method.


## 4.1. Security

We prove the security of our proposed scheme FTP through the following Theorem4.Theorem 4.
Our proposed scheme FTP discloses nothing useful about the privacy of input values and the final result.Proof.
We will discuss the view of Alice and Bob, respectively.
In our scheme FTP, Alice receivesyi′, wi for i=1,2⋯,2(⌈log2u⌉+1). Based on IND-CPA security of Paillier encryption system [31], Alice can learn nothing useful about yi′ and wi. Thus, Bob’s private data can be securely preserved.
Throughout FTP, Bob learns justs,S, and w. For each bit si in s, it has si=1 if ri(2xi-1)=1; otherwise si=0. That is, (2xi-1)=(2si-1)ri. Each ri∈{1,-1} is unknown to Bob, and we can simply assume Pr(ri=1)= Pr(ri=0)=0.5 for the view of Bob. Hence, for any si, conditional probability Pr(xi=1∣si)= Pr(xi=0∣si)=0.5, which means Bob can learn nothing about xi from si. Similarly, it is provable that S discloses nothing about xi. For w, based on the additive homomorphic property, we have w=D∗R-1modn. As R is randomly selected from Zn∗, Bob can infer no information about D from w. In general, s,S, and w reveal nothing of Alice’s private data.
To sum up, the privacy of Alice and Bob both can be preserved in our scheme FTP, which completes the proof.


## 4.2. Computation and Communication Cost

In this section, we will analyze the computation complexity and communication overheads of our proposed FTP in detail.Computation Complexity. Since simple addition and multiplication are much cheaper than encryption, decryption, and ciphertext multiplication of Paillier cryptosystem, we will ignore the simple addition and multiplication in the protocol. Throughout FTP, Bob encrypts each yi′ and wi for i=1 to 2(⌈log2u⌉+1) and decrypts one times to gain w. Alice uses yi′ and wi to compute D and θ, which requires ciphertext multiplication 2(⌈log2u⌉+1) times. In total, both Bob and Alice just employ Paillier encryption system O(logu) times.Communication Overheads. In our scheme FTP, Alice and Bob need to transmit s,S, yi′ and wi for i=1 to 2(⌈log2u⌉+1). If each ciphertext is β-bit, then the total communication overheads are 2u+2β(⌈log2u⌉+1). While u=256 and we set the public key of Paillier encryption system to be 2048 bits, the communication overheads will be 37376 bits.


## 4.3. Experiment Results

We implement our scheme and two existing efficient algorithms: LT13 and NEL16, using C language. During executing our scheme, we utilize GMP library [33] and Paillier library [34] with key size of 2048 bits. All experiments are performed on an Apple computer with macOS Sierra 10.12.6, Intel Core i5 1.6GHz CPU and 4 GB memory. Alice and Bob communicate through the socket where ping time is about 0.81 seconds.Figure2 shows the runtime of LT13, NEL16, and our scheme FTP while the compared string is of 16 to 256 bits. As can be seen, FTP can dramatically reduce the running time compared to LT13 and NEL16. When the length u is 256, LT13 costs about 25 seconds, NEL16 takes 6 seconds around, and FTP just needs 0.6 seconds. While the length is larger, the advantage of FTP will be more salient. The main reason is that we transform the original x, y into x′, y′ which is much shorter than the original ones. More importantly, our transformation just involves simple addition and multiplication and can be completed rapidly. In FTP, Paillier encryption system is employed only to securely compare x′ and y′. Therefore, FTP can reduce the running cost, especially when u is large. If the bit length is smaller than 16, FTP has no significant advantages on running time, and LT13 or NEL16 is suitable for the short-string equality comparison scenario.Figure 2
Runtime comparison of LT13, NEL16, and our scheme FTP.


## 4.4. Improvement

Though our scheme FTP can reduce the cost, it still takesu bits to transmit the vector s or S. We can further improve the scheme to avoid transmitting s or S. Let H():{0,1}∗→{0,1}u be a pseudorandom function. Alice and Bob, in advance, select a constant pad. While they decide to compare the private binary vectors, they can separately generate a random binary string H(time∥pad) where time denotes the time they decide to implement the protocol and ∥ denotes concatenation. Then, they set si=Hi in which Hi denotes the i-th bit of H(time∥pad). Since si=(ri(2xi-1)+1)/2 and (2xi-1)2=1, Alice can locally get ri=(2Hi-1)(2xi-1). Thus, Alice and Bob can compute A and B, respectively. By this method, Alice need not to send the vector s again. For S, they can preestablish another constant pad′ and use it avoid transmitting S by a similar method.


## 5. Related Work

Privacy-preserving string equality test is one of secure multiparty computation (SMC) problems, and it has wide applications in various privacy-preserving scenes [35–38]. Up to now, a big number of works can be utilized to achieve privacy-preserving string equality test. We simply discuss the previous schemes as follows.In 1982, Yao [39] proposes the first SMC problem, Millionaire problem and gives a secure solution. After that, garbled circuits method [32, 40] is put forward to securely evaluate a general function. Nevertheless, the general approach is too expensive and can just theoretically solve the problem. Scalar product protocol (also known as dot product protocol) focuses on computing the scalar product of two private vectors with privacy-preservation. Privacy-preserving string equality test can be achieved by invoking scalar product protocol. We thus review the main solutions of scalar product protocol. In [41], Vaidya et al. proposed a scalar product protocol based on algebraic transformation. By using homomorphic encryption, two solutions for securely computing dot product of private vectors are given in [42] and [43], respectively. A polynomial secret sharing-based scalar product protocol is presented by Shaneck and Kim [44]. Nevertheless, the schemes either are not provably secure or have heavy computation and communication overheads. Recently, Zhu et al. propose two efficient solutions for secure scalar product protocol [45, 46], which can be utilized to securely compute the Hamming distance of two private strings but cannot support the distance comparison. Cheng et al. [47] review the approaches to secure Internet of Things in a quantum world. In [48], Li et al. leverage Paillier encryption to achieve secure comparison protocol, based on which they also propose a secure SVM classification scheme. Nevertheless, the comparison scheme in [48] focuses on securely figuring out the bigger one from two private integers but cannot directly support the equality comparison problem investigated in this paper.In [30], Lipmaa and Toft propose a secure string equality test scheme based on Paillier encryption scheme [31]. While comparing u-bit strings, Lipmaa and Toft’s scheme requires O(u) encryption of Paillier encryption system and thus is time-consuming. Nateghizad et al. [29] improve Lipmaa and Toft’s scheme by reducing the degree of Lagrange interpolation polynomial. As yet, the number of invoking Paillier encryption in Nateghizad et al.’s solution is also linear with u, which is not suitable for a large u either. In general, the existing privacy-preserving string equality test schemes are still far away from being practical.


## 6. Conclusions

In this paper, we considered efficient and privacy-preserving authentication in IoT applications. To this end, we proposed a new privacy-preserving equality test protocol, which can securely complete string equality test and achieve high running efficiency at the cost of little accuracy loss. We strictly analyzed the accuracy of our proposed scheme and formally proved our security. Additionally, we leveraged extensive simulation experiments to evaluate the running cost, which confirms our high efficiency.



---

*Source: 6909703-2018-10-18.xml*