# A Protocol for Provably Secure Authentication of a Tiny Entity to a High Performance Computing One

Authors: Siniša Tomović; Miodrag J. Mihaljević; Aleksandar Perović; Zoran Ognjanović
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

The problem of developing authentication protocols dedicated to a specific scenario where an entity with limited computational capabilities should prove the identity to a computationally powerful Verifier is addressed. An authentication protocol suitable for the considered scenario which jointly employs the learning parity with noise (LPN) problem and a paradigm of random selection is proposed. It is shown that the proposed protocol is secure against active attacking scenarios and so called GRS man-in-the-middle (MIM) attacking scenarios. In comparison with the related previously reported authentication protocols the proposed one provides reduction of the implementation complexity and at least the same level of the cryptographic security.


---

## Body

## 1. Introduction

Expansion of Internet of Things (IoT) and Machine-to-Machine (M2M) communications has implied additional challenges regarding the information security issues. In a number of scenarios at least one of the entities involved is a tiny device with very limited computational capabilities and heavy restriction regarding power consumption. Accordingly, a challenge is developing of the information security techniques which minimize the computational and power consumption overheads implied by the security requirements.Authentication of one entity, called Prover, to another, called Verifier, has been well recognized as one of the cornerstones for achieving the desired level of information security (as well as cybersecurity). Authentication protocols for restricted implementation scenarios have been considered in a number of papers including [1–3]. This is also in line with a discussion recently reported in [4].This paper considers an authentication approach suitable for scenarios where an entity with highly constrained computational capabilities should in a secure way perform authentication to the verification party with high performance computational capabilities.The reported protocols appear as not enough suitable because either (i) they are not enough lightweight for a tiny party of an authentication protocol and do not take into account the asymmetrical implementation constraints (ii) or/and they do not provide the desired level of cryptographic security.Consequently, in this paper, we jointly employ certain elements of the reported protocols to achieve our main goal: development of the authentication protocols with asymmetric implementation complexity at Prover and Verifier sides which provides desired provable level of cryptographic security.


## 2. Background

### 2.1. Family of HB Authentication Protocols

The origin of a family of authentication protocols based on hardness of learning parity with noise (LPN) problem is a lightweight two-pass authentication protocol called the HB protocol reported in [5]. Simplicity of the approach and its provable security implied by the fact that the LPN problem is NP-complete (see [6]) have attracted much interest. The HB protocol requires only basic AND and XOR operations and it has been proved to be secure against passive attacks via reduction to the LPN problem. However, it is insecure against a stronger adversary, active adversary, who has ability to impersonate a reader and interact with legitimate tags. In order to address this weakness, a modified HB protocol called the HB+ protocol has been reported in [7–9]. The HB+ protocol has been proved to be secure against active attacks, but it has been shown in [10] that the HB+ protocol is insecure against a man-in-the-middle (MIM) attack. Specifically, in [10], a linear time MIM attack against the HB+ protocol that is called the GRS-MIM attack has been reported. Later on a number of variants of the HB+ protocol have been proposed to prevent the GRS-MIM attack (including [11, 12]), but all of them were shown to be insecure later. After a number of unsuccessful attempts, [13] has extended the HB+ protocol and proposed a new protocol called the HB# that only requires three-pass communication and is secure against GRS-MIM attacks. While two vectors are shared by the Prover and the Verifier as the secret keys in the HB+ protocol, two matrices are shared by the parties as the secret keys in the HB# protocol: by increasing the size of secret keys, the HB# protocol achieves stronger security and reduces the communication complexity. However, [14] has described an MIM attack against the HB# protocol. After that, several three-pass protocols that resist MIM attacks were proposed. Three-pass authentication protocols which have stronger security had been well studied. From a practical aspect, however, two-pass authentication protocol is more desirable than three-pass authentication protocol. Construction of a two-pass authentication scheme with even the active security had been open problem for a long time. In [15] a two-pass authentication protocol called the AUTH protocol has been proposed. The AUTH protocol is the first two-pass protocol which achieves the active security and yields a large improvement in terms of round complexity. Also [15] has reported two variants of the AUTH protocol, which could be called the AUTH+ protocol and the AUTH# protocol. In the AUTH+ protocol, the computational complexity decreases in exchange for increasing the number of secret keys. In the AUTH# protocol, the communication complexity decreases in exchange for the increasing the size of secret keys like the HB# protocol. Later on in [16] the active security of the AUTH# protocol has been proved employing a modular approach, which simplifies the proof: for this proof, a new computational assumption has been introduced and called the MSLPN assumption.


### 2.2. HB# Authentication Protocol

HB# authentication protocol is a three-round challenge-response protocol which has been proposed and analyzed in [13]. Random-HB# is a generalization of HB+ where the form of the secrets x and y has been changed from k-bit vectors into (k
X
×
m)- and (k
Y
×
m)-binary matrices X and Y. Random-HB# protocol is displayed as follows.Parameters:k
x
,
k
Y
,
m
,
τ
,
uP
s
e
c
r
e
t
X
,
Y
V
s
e
c
r
e
t
X
,
Y
e
←
B
e
r
τ
m
b
←
$
Z
2
k
Y
⟶
b
⟵
a
a
←
$
Z
2
k
X
z
=
a
X
+
b
Y
+
e
⟶
z
?
z
⊕
a
X
⊕
b
Y
≤
m
u.For an additional explanation of the notations, please refer to Section3.2.While Random-HB# has a number of similarities with the HB+ protocol, there are important differences as well. In particular, the final verification by the reader consists of the comparison of twom-bit vectors a
·
X
⊕
b
·
Y and z.


### 2.3. Authentication Employing Random Selection

Design and security evaluation of authentication protocols based on random selection paradigm have been initially reported in [17–19]. The principle of random selection can be described as follows. Suppose that the Verifier Alice and the Prover Bob run a challenge-response authentication protocol which uses a lightweight symmetric encryption operation(1)
E
:
0,1
n
×
K
⟶
0,1
m of block length n, where K denotes an appropriate key space. Suppose further that E is weak in the sense that a passive adversary can efficiently compute the secret key K
∈
K from samples of the form (
u
,
E
K
(
u
)
). This is obviously the case if E is linear.Random selection denotes a method for compensating the weakness ofE by using the following mode of operation. Instead of holding a single K
∈
K, Alice and Bob share a collection K
1
,
…
,
K
L of keys from K as their common secret information, where L
>
1 is a small constant.(i)
Upon receiving a challengeu
∈
{
0,1
}
n from Alice, Bob chooses a random index l
∈
{
1,2
,
…
,
L
} and outputs the response y
=
E
(
u
,
K
l
).
(ii)
The verification ofy with respect to u can be efficiently done by computing E
K
l
-
1
(
y
) for all l
=
1,2
,
…
,
L.


### 2.4. Security Evaluation of an Authentication Protocol

The common scenarios for security evaluation against impersonation attacks are as follows. The basic one is a passive attack scenario which proceeds in two phases: in the first phase the adversary eavesdrops a (large) number of interactions betweenP and V and then attempts to cause V to accept the authentication response in the second phase (where P is no longer available). In an active attack, the adversary is additionally allowed to interact with P in the first phase. The strongest and most realistic attack model is a man-in-the-middle attack (MIM), where the adversary can arbitrarily interact with P and V (with polynomially many concurrent executions allowed) in the first phase.


## 2.1. Family of HB Authentication Protocols

The origin of a family of authentication protocols based on hardness of learning parity with noise (LPN) problem is a lightweight two-pass authentication protocol called the HB protocol reported in [5]. Simplicity of the approach and its provable security implied by the fact that the LPN problem is NP-complete (see [6]) have attracted much interest. The HB protocol requires only basic AND and XOR operations and it has been proved to be secure against passive attacks via reduction to the LPN problem. However, it is insecure against a stronger adversary, active adversary, who has ability to impersonate a reader and interact with legitimate tags. In order to address this weakness, a modified HB protocol called the HB+ protocol has been reported in [7–9]. The HB+ protocol has been proved to be secure against active attacks, but it has been shown in [10] that the HB+ protocol is insecure against a man-in-the-middle (MIM) attack. Specifically, in [10], a linear time MIM attack against the HB+ protocol that is called the GRS-MIM attack has been reported. Later on a number of variants of the HB+ protocol have been proposed to prevent the GRS-MIM attack (including [11, 12]), but all of them were shown to be insecure later. After a number of unsuccessful attempts, [13] has extended the HB+ protocol and proposed a new protocol called the HB# that only requires three-pass communication and is secure against GRS-MIM attacks. While two vectors are shared by the Prover and the Verifier as the secret keys in the HB+ protocol, two matrices are shared by the parties as the secret keys in the HB# protocol: by increasing the size of secret keys, the HB# protocol achieves stronger security and reduces the communication complexity. However, [14] has described an MIM attack against the HB# protocol. After that, several three-pass protocols that resist MIM attacks were proposed. Three-pass authentication protocols which have stronger security had been well studied. From a practical aspect, however, two-pass authentication protocol is more desirable than three-pass authentication protocol. Construction of a two-pass authentication scheme with even the active security had been open problem for a long time. In [15] a two-pass authentication protocol called the AUTH protocol has been proposed. The AUTH protocol is the first two-pass protocol which achieves the active security and yields a large improvement in terms of round complexity. Also [15] has reported two variants of the AUTH protocol, which could be called the AUTH+ protocol and the AUTH# protocol. In the AUTH+ protocol, the computational complexity decreases in exchange for increasing the number of secret keys. In the AUTH# protocol, the communication complexity decreases in exchange for the increasing the size of secret keys like the HB# protocol. Later on in [16] the active security of the AUTH# protocol has been proved employing a modular approach, which simplifies the proof: for this proof, a new computational assumption has been introduced and called the MSLPN assumption.


## 2.2. HB# Authentication Protocol

HB# authentication protocol is a three-round challenge-response protocol which has been proposed and analyzed in [13]. Random-HB# is a generalization of HB+ where the form of the secrets x and y has been changed from k-bit vectors into (k
X
×
m)- and (k
Y
×
m)-binary matrices X and Y. Random-HB# protocol is displayed as follows.Parameters:k
x
,
k
Y
,
m
,
τ
,
uP
s
e
c
r
e
t
X
,
Y
V
s
e
c
r
e
t
X
,
Y
e
←
B
e
r
τ
m
b
←
$
Z
2
k
Y
⟶
b
⟵
a
a
←
$
Z
2
k
X
z
=
a
X
+
b
Y
+
e
⟶
z
?
z
⊕
a
X
⊕
b
Y
≤
m
u.For an additional explanation of the notations, please refer to Section3.2.While Random-HB# has a number of similarities with the HB+ protocol, there are important differences as well. In particular, the final verification by the reader consists of the comparison of twom-bit vectors a
·
X
⊕
b
·
Y and z.


## 2.3. Authentication Employing Random Selection

Design and security evaluation of authentication protocols based on random selection paradigm have been initially reported in [17–19]. The principle of random selection can be described as follows. Suppose that the Verifier Alice and the Prover Bob run a challenge-response authentication protocol which uses a lightweight symmetric encryption operation(1)
E
:
0,1
n
×
K
⟶
0,1
m of block length n, where K denotes an appropriate key space. Suppose further that E is weak in the sense that a passive adversary can efficiently compute the secret key K
∈
K from samples of the form (
u
,
E
K
(
u
)
). This is obviously the case if E is linear.Random selection denotes a method for compensating the weakness ofE by using the following mode of operation. Instead of holding a single K
∈
K, Alice and Bob share a collection K
1
,
…
,
K
L of keys from K as their common secret information, where L
>
1 is a small constant.(i)
Upon receiving a challengeu
∈
{
0,1
}
n from Alice, Bob chooses a random index l
∈
{
1,2
,
…
,
L
} and outputs the response y
=
E
(
u
,
K
l
).
(ii)
The verification ofy with respect to u can be efficiently done by computing E
K
l
-
1
(
y
) for all l
=
1,2
,
…
,
L.


## 2.4. Security Evaluation of an Authentication Protocol

The common scenarios for security evaluation against impersonation attacks are as follows. The basic one is a passive attack scenario which proceeds in two phases: in the first phase the adversary eavesdrops a (large) number of interactions betweenP and V and then attempts to cause V to accept the authentication response in the second phase (where P is no longer available). In an active attack, the adversary is additionally allowed to interact with P in the first phase. The strongest and most realistic attack model is a man-in-the-middle attack (MIM), where the adversary can arbitrarily interact with P and V (with polynomially many concurrent executions allowed) in the first phase.


## 3. Proposal of a Dedicated Authentication Technique

This section proposes an authentication protocol with asymmetric implementation complexity which is suitable for authentication of a Prover with low computational capabilities to a Verifier with high performance computational capabilities.


### 3.1. Underlying Ideas for Design

Taking into account results on the authentication protocols reported in [13, 17–20], this paper proposes a novel authentication protocol which is based on a nontrivial hybridization and upgrading of certain previously reported results.The initial observations regarding certain previously reported protocols are the following ones:(i) The protocols reported in [13, 20] provide a number of interesting framework elements for developing highly secure authentication protocols, but they appear as not light enough for a number of M2M authentication scenarios and do not take into account asymmetric implementation constraints. It is desirable to reduce implementation complexity of certain authentication protocols with implementation potential in tiny Provers, like HB# authentication protocol [13].(ii) The protocols reported in [17–19] employ an interesting paradigm of random selection but do not provide the desired level of cryptographic security.Accordingly, the underlying ideas for developing the novel authentication protocols were the following ones:(i)
Employ framework elements of HB# authentication protocol and modify it in order to fit into implementation restrictions at a tiny Prover and asymmetric implementation and execution capabilities of Prover and Verifier sides.
(ii)
Do not employ elements of the reported protocols which do not support lightweightness of the authentication at the party (usually the Prover) with tiny capabilities.
(iii)
Employ the power of random selection approach to enhance cryptographic security of the protocol at the tiny party as a trade-off between the cryptographic security of the protocol and its increased implementation complexity at the more powerful party (usually the Verifier).Particularly, note the following:(i)
Instead of employment of two secret keysX and Y as in the source HB# protocol, we propose employment of one secret key and the random selection paradigm for achieving the same security goals.


### 3.2. Notations

We use the following notations:(i)
Z
2
m and Z
2
m
×
n denote, respectively, set of all m-dimensional binary vectors and set of binary matrices m
×
n.
(ii)
We use normal, bold, and capital bold letters such asx, x, and X to denote single elements, vectors, and matrices.
(iii)
For a vectorx
,
x
[
i
] denotes the ith element of x.
(iv)
x
⊕
y is the bitwise XOR operation of two vectors x and y; that is, (
x
⊕
y
)
[
i
]
=
x
[
i
]
⊕
y
[
i
], for all i. Similarly, X
⊕
Y is defined as bitwise XOR of two binary matrices X and Y.
(v)
x denotes the Hamming weight of binary vector x, which is the number of its nonzero elements x
[
i
].
(vi)
x
←
$
X is the operation of sampling a value x from the uniform distribution on the finite set X.
(vii)
B
e
r
τ represents the Bernoulli distribution with parameter τ, and ν
←
B
e
r
τ means that for a bit ν, Pr
⁡
[
ν
=
1
]
=
τ, and Pr
⁡
[
ν
=
0
]
=
1
-
τ.
(viii)
e
←
B
e
r
τ
m means that the vector e was randomly chosen among all the vectors of length m, such that e
[
i
]
←
B
e
r
τ and τ
∈
(
0,1
/
2
), for 0
≤
i
≤
m
-
1.
(ix)
Lete
∗ be a vector of length m and weight Δ.A circulant matrix
E
∗
=
C
i
r
c
n
(
e
∗
) over the vector e
∗ is a matrix with n columns, whose first column is e
∗, and each next column is produced by a rotation of the previous column one position downwards.
The elements of the setE
m
,
n
,
Δ
∗ of circulant matrices with n columns, generated over vectors of length m and weight Δ, can be ordered in the array E
m
,
n
,
Δ
∗
[
1
]
,
…
,
E
m
,
n
,
Δ
∗
[
m
Δ
].
(x)
(
m
×
n
)-binary Toeplitz matrix is a matrix where for each diagonal from upper-left to lower-right all the elements on the diagonal have the same value. Note that the entire matrix is specified by the top row and the first column, so it can be parametrized by m
+
n
-
1 bits. Note that circulant matrices are also a kind of Toeplitz matrices. Toeplitz matrices can be generated efficiently and have good statistical properties [13].An algorithmA isprobabilistic if it makes random choices during its execution. A probabilistic algorithm A isprobabilistic polynomial-time (PPT) if for any input the computation of algorithm terminates in at most polynomial number of steps in the length of input. We also use the termefficient algorithm as a synonym for PPT algorithm. A function f
(
x
) isnegligible if for every positive polynomial p, with x being large enough, it holds that f
(
x
)
<
1
/
p
(
x
).


### 3.3. Proposal of the Authentication Protocol

The authentication protocol NHB# (Nondeterministic HB#) is displayed as follows:Parameters:m
,
n
,
τ
,
t
h
rP
s
e
c
r
e
t
Y
V
s
e
c
r
e
t
Y
b
←
$
Z
2
m
⟶
b
⟵
a
a
←
$
Z
2
m
e
←
B
e
r
τ
m
e
∗
←
$
Z
2
m
,
e
∗
=
Δ
E
∗
=
C
i
r
c
n
(
e
∗
)
z
=
a
E
+
b
Y
+
e
⟶
z
?
z
⊕
a
E
∗
i
⊕
b
Y
≤
t
h
r
for some
i
,
1
≤
i
≤
m
Δ,
w
h
e
r
e
E
∗
i
=
E
m
,
n
,
Δ
∗
i.This authentication protocol NHB# (Nondeterministic HB#) is an interactive protocol being executed betweenProver
P andVerifier
V which are efficient algorithms. They share one secret key, a matrix Y
∈
Z
2
m
×
n, which is produced by the key-generation algorithm K
G
(
1
k
), for the security parameter k. As a result of the protocol execution, Verifier V outputs indicator of acceptance value I
N
D, such that I
N
D
=
1 if V confirms that the Prover is valid; otherwise the indicator value is set to I
N
D
=
0.Public Parameters
(i)
m
,
n
∈
N: dimensions of the secret matrix Y, which depend on the security parameter k;
(ii)
τ
∈
(
0,1
/
4
): parameter of the Bernoulli distribution (B
e
r
τ);
(iii)
t
h
r: the acceptance threshold, such that t
h
r
≪
m
/
2.Key Generation. Algorithm K
G
(
1
k
) samples a random matrix Y
←
$
Z
2
m
×
n as a secret key and returns it to P and V.Protocol Specification
Phase I: the protocol initialization, executed byP
b
←
$
Z
2
m;
b
↦
V (P sends message b to V).
Phase II: challenge generation, executed byV
a
←
$
Z
2
m;
a
↦
P (V sends message a to P).
Phase III: response generation, executed byP
e
←
B
e
r
τ
n;
e
∗
←
$
Z
2
m
,
e
∗
=
Δ;
E
∗
=
C
i
r
c
n
(
e
∗
)
z
≔
a
E
∗
+
b
Y
+
e;
z
↦
V (P sends z to V).
Phase IV: the verification process, executed byV
I
N
D
≔
0,  i
≔
1;
while(
I
N
D
=
0
a
n
d
i
≤
m
Δ
) do
ifz
⊕
a
E
m
,
n
,
Δ
∗
[
i
]
⊕
b
Y
≤
t
h
r then I
N
D
≔
1;
V outputs I
N
D value.Let us discuss the error rates of the protocol. The false rejection happens when a legitimate Prover gets rejected by the Verifier, that is, when the weight of vectore
←
B
e
r
τ
n generated in the response phase is greater than t
h
r value. Therefore, the probability of this event (thecompleteness error) is(2)
P
F
R
=
∑
i
=
t
h
r
+
1
n
n
i
τ
i
1
-
τ
n
-
i
.The false acceptance occurs when an illegitimate Prover sends a randomly chosen response to the Verifier and gets authenticated, which happens with the following probability (thesoundness error):(3)
P
F
A
=
m
Δ
2
n
∑
i
=
0
t
h
r
n
itaking into account the number of binary vectors of length n whose weight is at most t
h
r and m
Δ different acceptance subcriteria of the Verifier.Protocol Storage Optimization. Following the proposal in [13], the storage cost of the secret key Y may be reduced to m
+
n
-
1 bits, by using a Toeplitz matrix as Y instead of the random matrix. This type of storage reduction was applied in [13] to the Random-HB# protocol, resulting in the HB# protocol, which uses two Toeplitz matrices X and Y as secret keys. The security of HB# is based on the conjecture about hardness of the so-called Toeplitz-MHB Puzzle. In our case, the security of this optimized protocol version is based on the analogously plausible conjecture about hardness of the Toeplitz-MLPN problem (see Note 1, Section 5).


## 3.1. Underlying Ideas for Design

Taking into account results on the authentication protocols reported in [13, 17–20], this paper proposes a novel authentication protocol which is based on a nontrivial hybridization and upgrading of certain previously reported results.The initial observations regarding certain previously reported protocols are the following ones:(i) The protocols reported in [13, 20] provide a number of interesting framework elements for developing highly secure authentication protocols, but they appear as not light enough for a number of M2M authentication scenarios and do not take into account asymmetric implementation constraints. It is desirable to reduce implementation complexity of certain authentication protocols with implementation potential in tiny Provers, like HB# authentication protocol [13].(ii) The protocols reported in [17–19] employ an interesting paradigm of random selection but do not provide the desired level of cryptographic security.Accordingly, the underlying ideas for developing the novel authentication protocols were the following ones:(i)
Employ framework elements of HB# authentication protocol and modify it in order to fit into implementation restrictions at a tiny Prover and asymmetric implementation and execution capabilities of Prover and Verifier sides.
(ii)
Do not employ elements of the reported protocols which do not support lightweightness of the authentication at the party (usually the Prover) with tiny capabilities.
(iii)
Employ the power of random selection approach to enhance cryptographic security of the protocol at the tiny party as a trade-off between the cryptographic security of the protocol and its increased implementation complexity at the more powerful party (usually the Verifier).Particularly, note the following:(i)
Instead of employment of two secret keysX and Y as in the source HB# protocol, we propose employment of one secret key and the random selection paradigm for achieving the same security goals.


## 3.2. Notations

We use the following notations:(i)
Z
2
m and Z
2
m
×
n denote, respectively, set of all m-dimensional binary vectors and set of binary matrices m
×
n.
(ii)
We use normal, bold, and capital bold letters such asx, x, and X to denote single elements, vectors, and matrices.
(iii)
For a vectorx
,
x
[
i
] denotes the ith element of x.
(iv)
x
⊕
y is the bitwise XOR operation of two vectors x and y; that is, (
x
⊕
y
)
[
i
]
=
x
[
i
]
⊕
y
[
i
], for all i. Similarly, X
⊕
Y is defined as bitwise XOR of two binary matrices X and Y.
(v)
x denotes the Hamming weight of binary vector x, which is the number of its nonzero elements x
[
i
].
(vi)
x
←
$
X is the operation of sampling a value x from the uniform distribution on the finite set X.
(vii)
B
e
r
τ represents the Bernoulli distribution with parameter τ, and ν
←
B
e
r
τ means that for a bit ν, Pr
⁡
[
ν
=
1
]
=
τ, and Pr
⁡
[
ν
=
0
]
=
1
-
τ.
(viii)
e
←
B
e
r
τ
m means that the vector e was randomly chosen among all the vectors of length m, such that e
[
i
]
←
B
e
r
τ and τ
∈
(
0,1
/
2
), for 0
≤
i
≤
m
-
1.
(ix)
Lete
∗ be a vector of length m and weight Δ.A circulant matrix
E
∗
=
C
i
r
c
n
(
e
∗
) over the vector e
∗ is a matrix with n columns, whose first column is e
∗, and each next column is produced by a rotation of the previous column one position downwards.
The elements of the setE
m
,
n
,
Δ
∗ of circulant matrices with n columns, generated over vectors of length m and weight Δ, can be ordered in the array E
m
,
n
,
Δ
∗
[
1
]
,
…
,
E
m
,
n
,
Δ
∗
[
m
Δ
].
(x)
(
m
×
n
)-binary Toeplitz matrix is a matrix where for each diagonal from upper-left to lower-right all the elements on the diagonal have the same value. Note that the entire matrix is specified by the top row and the first column, so it can be parametrized by m
+
n
-
1 bits. Note that circulant matrices are also a kind of Toeplitz matrices. Toeplitz matrices can be generated efficiently and have good statistical properties [13].An algorithmA isprobabilistic if it makes random choices during its execution. A probabilistic algorithm A isprobabilistic polynomial-time (PPT) if for any input the computation of algorithm terminates in at most polynomial number of steps in the length of input. We also use the termefficient algorithm as a synonym for PPT algorithm. A function f
(
x
) isnegligible if for every positive polynomial p, with x being large enough, it holds that f
(
x
)
<
1
/
p
(
x
).


## 3.3. Proposal of the Authentication Protocol

The authentication protocol NHB# (Nondeterministic HB#) is displayed as follows:Parameters:m
,
n
,
τ
,
t
h
rP
s
e
c
r
e
t
Y
V
s
e
c
r
e
t
Y
b
←
$
Z
2
m
⟶
b
⟵
a
a
←
$
Z
2
m
e
←
B
e
r
τ
m
e
∗
←
$
Z
2
m
,
e
∗
=
Δ
E
∗
=
C
i
r
c
n
(
e
∗
)
z
=
a
E
+
b
Y
+
e
⟶
z
?
z
⊕
a
E
∗
i
⊕
b
Y
≤
t
h
r
for some
i
,
1
≤
i
≤
m
Δ,
w
h
e
r
e
E
∗
i
=
E
m
,
n
,
Δ
∗
i.This authentication protocol NHB# (Nondeterministic HB#) is an interactive protocol being executed betweenProver
P andVerifier
V which are efficient algorithms. They share one secret key, a matrix Y
∈
Z
2
m
×
n, which is produced by the key-generation algorithm K
G
(
1
k
), for the security parameter k. As a result of the protocol execution, Verifier V outputs indicator of acceptance value I
N
D, such that I
N
D
=
1 if V confirms that the Prover is valid; otherwise the indicator value is set to I
N
D
=
0.Public Parameters
(i)
m
,
n
∈
N: dimensions of the secret matrix Y, which depend on the security parameter k;
(ii)
τ
∈
(
0,1
/
4
): parameter of the Bernoulli distribution (B
e
r
τ);
(iii)
t
h
r: the acceptance threshold, such that t
h
r
≪
m
/
2.Key Generation. Algorithm K
G
(
1
k
) samples a random matrix Y
←
$
Z
2
m
×
n as a secret key and returns it to P and V.Protocol Specification
Phase I: the protocol initialization, executed byP
b
←
$
Z
2
m;
b
↦
V (P sends message b to V).
Phase II: challenge generation, executed byV
a
←
$
Z
2
m;
a
↦
P (V sends message a to P).
Phase III: response generation, executed byP
e
←
B
e
r
τ
n;
e
∗
←
$
Z
2
m
,
e
∗
=
Δ;
E
∗
=
C
i
r
c
n
(
e
∗
)
z
≔
a
E
∗
+
b
Y
+
e;
z
↦
V (P sends z to V).
Phase IV: the verification process, executed byV
I
N
D
≔
0,  i
≔
1;
while(
I
N
D
=
0
a
n
d
i
≤
m
Δ
) do
ifz
⊕
a
E
m
,
n
,
Δ
∗
[
i
]
⊕
b
Y
≤
t
h
r then I
N
D
≔
1;
V outputs I
N
D value.Let us discuss the error rates of the protocol. The false rejection happens when a legitimate Prover gets rejected by the Verifier, that is, when the weight of vectore
←
B
e
r
τ
n generated in the response phase is greater than t
h
r value. Therefore, the probability of this event (thecompleteness error) is(2)
P
F
R
=
∑
i
=
t
h
r
+
1
n
n
i
τ
i
1
-
τ
n
-
i
.The false acceptance occurs when an illegitimate Prover sends a randomly chosen response to the Verifier and gets authenticated, which happens with the following probability (thesoundness error):(3)
P
F
A
=
m
Δ
2
n
∑
i
=
0
t
h
r
n
itaking into account the number of binary vectors of length n whose weight is at most t
h
r and m
Δ different acceptance subcriteria of the Verifier.Protocol Storage Optimization. Following the proposal in [13], the storage cost of the secret key Y may be reduced to m
+
n
-
1 bits, by using a Toeplitz matrix as Y instead of the random matrix. This type of storage reduction was applied in [13] to the Random-HB# protocol, resulting in the HB# protocol, which uses two Toeplitz matrices X and Y as secret keys. The security of HB# is based on the conjecture about hardness of the so-called Toeplitz-MHB Puzzle. In our case, the security of this optimized protocol version is based on the analogously plausible conjecture about hardness of the Toeplitz-MLPN problem (see Note 1, Section 5).


## 4. The Security Evaluation Framework

We consider two types of attack scenarios for our protocol: active and GRS-MIM scenarios. Both of them consist of two phases: the so-calledlearning andforgery phases. In the first phase, the adversary interacts with the Prover and/or Verifier, learning the information she needs in order to be successful in the second phase, where she interacts with the verifier trying to make him output I
N
D
=
1.Definition 1.
Theactive attack is being executed in two phases.Phase 1. The adversary interacts only with the honest Prover P for a polynomial number of times q.Phase 2. The adversary interacts with the Verifier trying to impersonate the Prover.Definition 2.
GRS-MIM attack is being executed in two phases.Phase 1. The adversary interferes in q executions of the protocol. The adversary can eavesdrop or modify all messages between the honest Prover and honest Verifier and also gets the Verifier’s decision, on each execution of protocol.Phase 2. The adversary interacts with the Verifier trying to impersonate the Prover.Let〈
T
,
V
〉 denote a complete execution of NHB# protocol between a party T and the Verifier V and say that 〈
T
,
V
〉 takes value 1 if the execution ends with Verifier’s acceptance (i.e., I
N
D
=
1) and takes value 0 otherwise (I
N
D
=
0).Then we define the advantage of an active adversaryA as(4)
A
d
v
A
a
c
t
i
v
e
τ
,
t
h
r
,
m
,
n
=
Pr
⁡
A
,
V
⟶
1
∣
Y
⟵
$
Z
2
m
×
nand the advantage of a GRS-MIM adversary A as(5)
A
d
v
A
M
I
M
τ
,
t
h
r
,
m
,
n
=
Pr
⁡
A
,
V
⟶
1
∣
Y
⟵
$
Z
2
m
×
n
.If this advantage is nonnegligible, we say that the adversaryA issuccessful in the given attack scenario against the protocol. The protocol issecure against active attacks if, for all efficient active adversaries A, the advantage A
d
v
A
a
c
t
i
v
e
(
τ
,
t
h
r
,
m
,
n
,
m
) is negligible. Similarly, the protocol issecure against MIM attacks if, for all efficient MIM adversaries A, the advantage A
d
v
A
M
I
M
(
τ
,
t
h
r
,
m
,
n
) is negligible.


## 5. Security Evaluation in the Active Attacking Scenario

LPN Problem. Let x
∈
Z
2
m be a secret key, and τ
∈
(
0,1
/
2
). We denote by Λ
τ
,
m
(
x
) the probability distribution over Z
2
m
×
n whose samples are pairs (
a
,
a
·
x
⊤
⊕
e
), where a
←
$
Z
2
m, e
←
B
e
r
τ. Let Λ
τ
,
m
(
x
) also denote the oracle taking a sample from distribution Λ
τ
,
m
(
x
). U
m
+
1 is the oracle taking samples from the uniform distribution over Z
2
m
+
1. L
P
N
τ
,
m problem consists of distinguishing the access to the oracle Λ
τ
,
m
(
x
) from access to the oracle U
m
+
1.TheL
P
N
τ
,
m advantage of a distinguisher D is defined as(6)
A
d
v
D
L
P
N
τ
,
m
=
Pr
⁡
D
Λ
τ
,
m
x
⟶
1
∣
x
⟵
$
Z
2
m
-
Pr
⁡
D
U
m
+
1
⟶
1
.Definition 3 (LPN problem).
L
P
N
τ
,
m problem is (
t
,
q
,
ϵ
)-hard if for every distinguisher D running in time t and making q queries, the advantage A
d
v
D
L
P
N
(
τ
,
m
) is less than ϵ. In asymptotic terms, L
P
N
τ
,
m is hard if for every efficient D, the advantage A
d
v
D
L
P
N
(
τ
,
m
) is negligible.Matrix LPN (MLPN) Problem. The matrix LPN problem is defined analogously to the LPN problem, with the difference that the secret key is now a matrix, not a vector.LetX
∈
Z
2
m
×
n be a secret key, and τ
∈
(
0,1
/
2
). We denote by Λ
~
τ
,
m
,
n
(
X
) the probability distribution Z
2
m
×
n with samples (
a
,
a
X
⊕
e
), where a
←
$
Z
2
m and e
←
B
e
r
τ
m. Let Λ
~
τ
,
m
,
n
(
X
) also denote the oracle producing samples from Λ
~
τ
,
m
,
n
(
X
). U
~
m
+
n is the oracle taking samples from the uniform distribution over Z
2
m
+
n. M
L
P
N
τ
,
m
,
n problem, that is, the matrix variant of L
P
N
τ
,
m
,
n problem, is to distinguish the access to the oracle Λ
~
τ
,
m
,
n
(
X
) from access to the oracle U
~
m
+
n.For a distinguisherD, we define M
L
P
N
τ
,
m
,
n advantage of D as(7)
A
d
v
D
M
L
P
N
τ
,
m
,
n
=
Pr
⁡
D
Λ
~
τ
,
m
,
n
X
⟶
1
∣
X
⟵
$
Z
2
m
×
n
-
Pr
⁡
D
U
~
m
+
n
⟶
1
.Definition 4 (MLPN problem).
M
L
P
N
τ
,
m
,
n problem is (
t
,
q
,
ϵ
)-hard if, for all distinguishers D running in time t and making q queries, the advantage A
d
v
D
M
L
P
N
(
τ
,
m
,
n
) is less than ϵ. In asymptotic terms, M
L
P
N
τ
,
m is hard if all efficient distinguishers D achieve a negligible A
d
v
D
M
L
P
N
(
τ
,
m
,
n
) advantage.Theorem 5 (equivalence to LPN).
IfL
P
N
τ
,
m problem is (
t
,
q
,
ϵ
)-hard, then M
L
P
N
τ
,
m
,
n problem is (
t
′
,
q
,
ϵ
n
)-hard; t
′
=
t
-
p
o
l
y
(
q
,
m
).Proof.
We slightly adapt the proof of Proposition2 in [16]. As usual, we will assume that there exists a distinguisher D
M
L
P
N with M
L
P
N
τ
,
m
,
n-advantage n
ϵ and use it as a subroutine to construct a distinguisher D
L
N
P using D
M
L
P
N as a subroutine and prove that the corresponding L
P
N
τ
,
m-advantage is equal to ϵ, which contradicts the hardness assumption of L
P
N
τ
,
m.
LetX
∈
Z
2
m
×
n be a matrix with columns x
1
⊤
,
…
,
x
n
⊤,  and i
∈
{
0
,
…
,
n
}. We define the probability distribution Λ
~
τ
,
m
,
n
i
(
X
) over Z
2
m
×
n whose samples are pairs (
a
,
z
), where z
=
(
a
·
x
1
⊤
⊕
e
1
,
…
,
a
·
x
i
⊤
⊕
e
i
,
a
i
+
1
,
…
,
a
n
), for a
←
$
Z
2
m, e
j
←
B
e
r
τ (j
=
1
,
…
,
i), and a
k
←
$
Z
2   (k
=
i
+
1
,
…
,
n).
Fori
=
0
,
…
,
n, we denote by p
i the probability that distinguisher D
M
L
P
N outputs 1, when its input is a sample Λ
~
τ
,
m
,
n
i
(
X
):(8)
p
i
=
Pr
⁡
D
M
L
P
N
Λ
~
τ
,
m
,
n
i
X
⟶
1
∣
X
⟵
$
Z
2
m
×
n
.
Note thatΛ
~
τ
,
m
,
n
0
(
X
) is the same as a sample from U
~
m
+
n, and Λ
~
τ
,
m
,
n
n
(
X
) is the same as a Λ
~
τ
,
m
,
n
(
X
) sample. Therefore(9)
p
0
=
Pr
⁡
D
S
L
P
N
U
~
m
+
n
⟶
1
,
p
n
=
Pr
⁡
D
M
L
P
N
Λ
~
τ
,
m
,
n
X
⟶
1
∣
X
⟵
$
Z
2
m
×
n
.
The distinguisherD
L
P
N will forward the samples Λ
~
τ
,
m
,
n
i
(
X
) for i
←
$
{
0
,
…
,
n
} as input to the distinguisher D
M
L
P
N. Each sample will contain a sample from the unknown oracle that D
L
P
N communicates with (Λ
τ
,
m
(
x
) or U
m
+
1). Then, D
L
P
N will produce the same output as D
M
L
P
N. Now follows the precise description of actions taken by D
L
P
N algorithm:(1)
Take a sample(
a
,
z
)
∈
Z
2
m
×
n from an unknown oracle O.
(2)
Choosei
←
$
0
,
…
,
n
,
x
j
←
$
Z
2
m, e
j
←
B
e
r
τ
(
j
=
1
,
…
,
i
-
1
), a
k
←
$
Z
2 (k
=
i
+
1
,
…
,
n).
(3)
Make a sample(
a
~
,
z
~
), where(10)
a
~
=
a
,
z
~
=
a
·
x
1
⊤
⊕
e
1
,
…
,
a
·
x
i
-
1
⊤
⊕
e
i
-
1
,
z
,
a
i
+
1
,
…
,
a
nand forward (
a
~
,
z
~
) as input to distinguisher D
M
L
P
N.
(4)
Output the same output valueI
N
D (0 or 1) returned by D
M
L
P
N.
Note that ifO is the oracle Λ
τ
,
m
(
x
), then (
a
~
,
z
~
) produced in Step (3) is a sample Λ
~
τ
,
m
,
n
i
(
X
). If O is the oracle U
m
+
1, then (
a
~
,
z
~
) is a sample Λ
~
τ
,
m
,
n
i
-
1
(
X
).
In particular,L
P
N
τ
,
m advantage of distinguisher D
L
P
N can be computed as follows:(11)
A
d
v
D
L
P
N
τ
,
m
=
Pr
⁡
D
L
P
N
Λ
τ
,
m
x
⟶
1
∣
x
⟵
$
Z
2
m
-
Pr
⁡
D
L
P
N
U
m
+
1
⟶
1
=
∑
j
=
1
n
Pr
⁡
D
L
P
N
Λ
τ
,
m
x
⟶
1
∣
x
⟵
$
Z
2
m
,
i
=
j
Pr
⁡
i
=
j
-
Pr
⁡
D
L
P
N
U
m
+
1
⟶
1
∣
i
=
j
Pr
⁡
i
=
j
=
1
n
∑
j
=
1
n
Pr
⁡
D
M
L
P
N
Λ
~
τ
,
m
,
n
j
X
⟶
1
∣
X
⟵
$
Z
2
m
×
n
-
Pr
⁡
D
M
L
P
N
Λ
~
τ
,
m
,
n
j
-
1
X
⟶
1
∣
X
⟵
$
Z
2
m
×
n
=
1
n
∑
j
=
1
n
p
j
-
p
j
-
1
=
1
n
p
n
-
p
0
≥
ϵ
.
Thus, distinguisherD
L
P
N achieves L
P
N
τ
,
m advantage greater or equal to ϵ, which contradicts that L
P
N
τ
,
m is (
t
,
q
,
ϵ
)-hard.Note 1.
Similarly as in Conjecture1 [13], the hardness of the Toeplitz variant of M
L
P
N problem can be conjectured, where the Toeplitz matrix is used as the secret key instead of a random matrix.Theorem 6.
Letn
=
Θ
(
k
), 0
<
τ
<
1
/
4, and t
h
r
=
τ
+
·
n, where τ
+ is a constant satisfying τ
<
τ
+
<
1
/
4. If L
P
N
τ
,
m problem is hard, then the protocol N
H
B
#
(
τ
,
t
h
r
,
m
,
n
) is safe against active attacks.Proof.
The proof consists of the following four parts: (i) specification of a contradiction scenario which is a framework for security evaluation where an active adversaryA exists; (ii) design of a distinguishing algorithm D which provides learning of A for solving a hard problem; (iii) procedure for distinguishing between two oracles; and (iv) estimation of the success rate of D in the distinguishing phase.
(i) We assume the opposite from Theorem6 statement; that is, the protocol is not actively secure and an active adversary exists achieving a nonnegligible advantage, but that will contradict the hardness assumption of M
L
P
N
τ
,
m
,
n problem. The addressed scenario is formally specified in the following claim.
Claim. Suppose that there is an active adversary A interacting with Prover P in at most q executions of N
H
B
# protocol, running in time t and achieving advantage A
d
v
A
a
c
t
i
v
e
(
τ
,
t
h
r
,
m
,
n
)
=
δ. Then there exists a PPT algorithm D, running in time O
(
t
) and making Θ
(
k
) oracle queries, such that (12)
Pr
⁡
D
Λ
~
τ
,
m
,
n
Y
⟶
1
∣
Y
⟵
$
Z
2
m
×
n
-
Pr
⁡
D
U
~
m
+
n
⟶
1
≥
δ
2
-
m
Δ
2
2
n
∑
i
=
0
2
·
t
h
r
n
i
.
(ii) The learning phase: at first,D initializes the learning phase of the adversary A, while simulating the honest Prover P
s
i
m of protocol NHB#:(1)
D takes the sample (
b
,
z
¯
) from oracle.
(2)
D as P
s
i
m sends b to adversary A.
(3)
The active adversaryA forwards a challenge a
←
$
Z
2
m to P
s
i
m.
D is taking the following actions:
(4)
chooses a vectore
∗
←
$
Z
2
m, e
∗
=
Δ. Then it makes E
∗
=
C
i
r
c
n
(
e
∗
) and sets the value z
≔
a
E
∗
+
z
¯;
(5)
asP
s
i
m sends the value z to active adversary A.
The previous steps are repeated forq times.
(iii) The oracle distinguishing phase:D is taking the following actions:(1)
initiates a communication with adversaryA (after its learning phase) which sends a blinding message b;
(2)
chooses two different random vectorsa
1
,
a
2
←
$
Z
2
n;
(3)
sends the challengea
1 to adversary A and receives a response z
1 in return;
(4)
rewindsA (behind Step (1)), sends another challenge a
2, and receives the answer z
2;
(5)
receives the answerz
2 from A;
(6)
fori
,
j
=
1
,
…
,
m
Δ makes values(13)
w
i
j
≔
z
1
⊕
z
2
⊕
a
1
E
m
,
n
,
Δ
∗
i
⊕
a
2
E
m
,
n
,
Δ
∗
jand sends I
N
D
=
1 as output if w
i
j
≤
2
·
t
h
r for some i. Otherwise, I
N
D
=
0.
(iv) The success rate ofD in the distinguishing phase: we analyze the success rate of the algorithm D in distinguishing the distribution used by the oracle O.
(1) IfO uses the uniform distribution, then b
¯, z
¯, and z are uniformly random. D outputs I
N
D
=
1 if z
1 and z
2 produced by the adversary A satisfy the condition z
1
⊕
z
2
⊕
a
1
E
m
,
n
,
Δ
∗
[
i
]
⊕
a
2
E
m
,
n
,
Δ
∗
[
j
]
≤
2
·
t
h
r for some i
,
j. Since A did not learn correctly, we can assume that z
1 and z
2 are random, so the event I
N
D
=
1 has a nonnegligible probability m
Δ
2
/
2
n
∑
i
=
0
2
·
t
h
r
‍
n
i.
(2) Suppose thatD had access to oracle Λ
~
τ
,
m
,
n
(
Y
). Then z
¯
=
b
Y
⊕
e, so z
=
a
E
∗
⊕
z
¯
=
a
E
∗
⊕
b
Y
⊕
e. Thus, D did simulate the P
s
i
m correctly in the learning phase of A, so the adversary authenticates to protocol with the nonnegligible probability δ. That means that δ
2 is the probability that for the answers z
1
,
z
2 of the adversary produced in Steps (3) and (4) of the oracle distinguishing phase; it holds that z
1
⊕
a
1
E
m
,
n
,
Δ
∗
[
i
]
⊕
b
Y
≤
t
h
r, and z
2
⊕
a
2
E
m
,
n
,
Δ
∗
[
j
]
⊕
b
Y
≤
t
h
r for some i
,
j. Therefore, by the triangle inequality in the Hamming metrics, we get that w
i
j
=
z
1
⊕
z
2
⊕
a
1
E
m
,
n
,
Δ
∗
[
i
]
⊕
a
2
E
m
,
n
,
Δ
∗
[
j
]
≤
2
·
t
h
r, so D outputs I
N
D
=
1.
Thus, depending on whetherD was interacting with the uniform or the M
L
P
N
τ
,
m
,
n oracle, we estimate the difference in probabilities of D producing I
N
D
=
1 as output:(14)
A
d
v
D
M
L
P
N
τ
,
m
,
n
=
Pr
⁡
D
Λ
~
τ
,
m
,
n
Y
⟶
1
∣
Y
⟵
$
Z
2
m
×
n
-
Pr
⁡
D
U
~
m
+
n
⟶
1
≥
δ
2
-
m
Δ
2
2
n
∑
i
=
0
2
·
t
h
r
n
i
.
Therefore, the distinguisherD is achieving a nonnegligible M
L
P
N
τ
,
m
,
n advantage, which contradicts the hardness assumption of M
L
P
N
τ
,
m
,
n problem.


## 6. Security Evaluation in the Restricted Man-in-the-Middle Attacking Scenario

We prove the GRS-MIM security following the technique used in [13].Lemma 7 (see [13]).
IfX
∈
Z
2
m
×
n is a random matrix, d an integer in the interval [
1
,
…
,
n
/
2
], and H the binary entropy function H
(
x
)
=
-
x
log
2
⁡
(
x
)
-
(
1
-
x
)
log
2
⁡
(
1
-
x
), then for y
m
i
n
=
min
a
≠
0
,
a
∈
Z
2
m
⁡
a
X it holds that(15)
Pr
⁡
y
m
i
n
≤
d
≤
2
-
1
-
m
/
n
-
H
d
/
n
n
.The previous lemma also holds ifX is a random Toeplitz matrix (Appendix C, [13]).Theorem 8.
Suppose that there exists an efficient GRS-MIM adversaryA attacking N
H
B
#
(
τ
,
t
h
r
,
m
,
n
) protocol by modifying at most q executions of protocol between the Prover and the Verifier, running in time t and achieving advantage at least δ. Then, under an easily met condition on the parameter set, there is an active adversary A
′ attacking N
H
B
#
(
τ
,
t
h
r
,
m
,
n
) interacting at most q times with honest Prover, running in time O
(
t
) and achieving a nonnegligible advantage.Proof.
The proof consists of the following two parts: (i) specification of the learning phase of an MIM adversary and (ii) evaluation of the advantage which MIM adversary can achieve after the learning phase.
The Learning Phase of MIM Adversary. In order to provide a valid learning phase for the adversary A, the adversary A
′ takes the roles of simulated honest Prover and honest Verifier, denoted by P
s
i
m and V
s
i
m.The honest ProverP sends a blinding vector b to A
′, and A
′ playing as P
s
i
m forwards b to A.
A
′ playing as V
s
i
m sends a random vector a
←
$
Z
2
m as a challenge to P
s
i
m.
A modifies a to a
^
=
a
⊕
a
¯ and sends a
^ to P
s
i
m, and A
′ forwards a
^ to the honest P.
P returns z
=
a
^
E
∗
⊕
b
Y
⊕
e to A
′.
A
′ as P
s
i
m forwards z to V
s
i
m.
Ifa
¯ is the all-zero vector, V
s
i
m sets I
N
D
=
1; otherwise I
N
D
=
0.
The previous procedure is being repeated inq iterations.
The Advantage of MIM Adversary. We consider that the adversary A has achieved successful learning if P
s
i
m and V
s
i
m were executed correctly in each iteration of the learning phase, that is, if they behaved like honest P and V.
SinceP
s
i
m forwards directly the responses of honest P to the received queries, P
s
i
m works correctly in each simulation step.
On the other hand, the behaviours of the honestV and V
s
i
m do not have to match in all circumstances.
This happens in two cases: whenV
s
i
m accepts the response which gets rejected by V, or when V
s
i
m rejects the response which gets accepted by V.
In the first situation, sinceV
s
i
m accepts the response, it means that it is the response of honest P which is rejected by V, so the probability of this event is equal to the completeness error of the protocol; that is, P
r
[
V
s
i
m
(
I
N
D
=
1
)
,
V
(
I
N
D
=
0
)
]
=
P
F
R.
The second case, when in some iterationV
s
i
m rejects the response which is accepted by V, means that it is the response z
^ where a
¯ is not all-zero, but still this response gets accepted by honest V.
The probability of this acceptance is the probability that the following holds for somei (where E
∗
[
i
]
=
E
m
,
n
,
Δ
∗
[
i
]):(16)
z
^
⊕
a
E
∗
i
⊕
b
Y
≤
t
h
r
.
That is,z
^
+
a
E
∗
[
i
]
+
b
Y
=
a
E
∗
[
i
]
+
a
¯
E
∗
[
i
]
+
b
Y
+
e
+
a
E
∗
[
i
]
+
b
Y
=
a
¯
E
∗
[
i
]
⊕
e
≤
t
h
r.
Let us denote byy
a
~ the vector a
¯
X
⊕
β. Then in vector y
a
~
⊕
e, (
n
-
y
a
~
) bits follow the distribution B
e
r
τ
n, and the rest y
a
~ follow the distribution B
e
r
1
-
τ
n. Therefore μ
(
y
a
~
)
=
E
(
y
a
~
⊕
e
) = y
a
~
(
1
-
τ
)
+
(
n
-
y
a
~
)
τ. Since μ is a linear function of y
a
~, it holds that μ
≥
t
h
r for each y
a
~
≥
x
0, where x
0
=
1
+
t
h
r
-
τ
n
/
1
-
2
τ.
Therefore, according to Chernoff bound, eventy
a
~
⊕
e
≤
t
h
r has the probability at most e
-
(
μ
-
t
h
r
)
2
/
2
μ when y
a
~
≥
d, for each d
≥
x
0.
Suppose thaty
m
i
n
=
min
a
¯
≠
0
,
a
¯
∈
Z
2
m
⁡
a
¯
E
m
,
n
,
Δ
∗
[
i
].
LetF
A
I
L denote the event V
s
i
m
(
I
N
D
=
0
)
,
V
(
I
N
D
=
1
). Therefore for each d
≥
x
0 it holds (17)
Pr
E
∗
i
,
e
⁡
F
A
I
L
=
P
r
e
F
A
I
L
∣
y
m
i
n
>
d
·
P
r
E
∗
i
y
m
i
n
>
d
+
P
r
e
F
A
I
L
∣
y
m
i
n
≤
d
·
P
r
E
∗
i
y
m
i
n
≤
d
≤
P
r
e
F
A
I
L
∣
y
m
i
n
>
d
+
P
r
E
∗
i
y
m
i
n
≤
d
=
P
r
e
y
a
~
⊕
e
≤
t
h
r
∣
y
m
i
n
>
d
+
P
r
E
∗
i
y
m
i
n
≤
d
≤
e
-
μ
-
t
h
r
2
/
2
μ
+
2
-
1
-
m
/
n
-
H
d
/
n
n
.
Suppose thatk
>
0 is some positive constant, and x
0 is the least integer such that μ
>
(
1
+
k
)
t
h
r  for y
a
~
≥
x
0. Then, for all d
≥
x
0, when y
m
i
n
>
d, we have e
-
(
μ
-
t
h
r
)
2
/
2
μ
≤
e
-
t
h
r
·
k
2
/
2
(
1
+
k
), so the first term in the upper bound is negligible.
In order that the second term also gets negligible, we choosed
≥
x
0 such that 1
-
m
/
n
-
H
(
d
/
n
) is always positive; that is, H
(
d
/
n
)
<
1
-
m
/
n (that condition is easily met for the usual parameter values [13]).
Therefore, we have that the probability of incorrect simulation in a single iteration is(18)
p
r
=
Pr
⁡
V
s
i
m
I
N
D
=
1
,
V
I
N
D
=
0
+
Pr
⁡
V
I
N
D
=
0
,
V
s
i
m
I
N
D
=
1
≤
P
F
R
+
e
-
μ
-
t
h
r
2
/
2
μ
+
2
-
1
-
m
/
n
-
H
d
/
n
n
.
Thus, the probability that allq iterations are correct, that is, that the learning phase is successfully conducted, is (
1
-
p
r
)
q, which has the asymptotic value of 1.
We conclude that the advantage of the active adversaryA
′ attacking N
H
B
#
(
τ
,
t
h
r
,
m
,
n
) is δ
′
=
δ
(
1
-
p
r
)
q, which is a nonnegligible value, so this contradicts the active security of that protocol.


## 7. A Concluding Discussion

This paper proposes an authentication protocol with asymmetric implementation complexity which is suitable for authentication of a Prover with low computational capabilities to a Verifier with high performance computational capabilities. The protocol is based on a trade-off between the execution overheads at Prover and Verifier: more computational efforts are required at the side of Verifier in order to maintain the desired level of the authentication security.The proposed protocol originates from HB# protocol [13], but it provides reduction of the required secret key dimension to the half of the one required in HB# protocol. Reduction of the required secret key dimension and the asymmetric computational overheads at Prover and Verifier appear as a consequence of employment the random selection paradigm. Security of the proposed authentication protocol results from joint employment of the LPN problem and random selection paradigms. In this paper, security of the proposed authentication protocol has been proved in active attacking and restrictive MIM (so called GRS-MIM) attacking scenarios. We conjecture that protocol could achieve security in MIM attacking scenarios stronger than GRS-MIM, and this is one of the directions for the related future work.



---

*Source: 9289050-2016-05-23.xml*