B. Mi, D. Huang and S. Wan et al. / Computers and Electrical Engineering 75 (2019) 90–100 91
However, in practice, a trusted authority may not always be available or exists. This necessitates the design of a self-
contained privacy-preserving information fetching scheme; in other words, the need for an OT scheme. As for the 1-out- n
OT protocol (scheme and protocol are used interchangeably in the literature and this paper), F
OT
1
n
, the sender holds n
messages belonging to the plaintext space M while the receiver expects to obtain τ th message from the sender. Similar
to private information retrieval (PIR), it is required that the sender must be unaware of the receiver’s choice τ , but an
additional prerequisite (i.e., sender should keep all other messages private) is also required in OT.
In other words, in an OT protocol, the sender must faithfully and securely deliver all messages and the receiver should
only be able to recover one of them after the right conversation has taken place. Consequently, when the number of
candidate messages is considerable, such protocol is also practical if the plaintexts are obfuscated and distributed once
for all.
The first instantiation of 1-out- n OT protocol is presented in [4] . Since then, there have been a (large) number of proto-
cols presented in the literature, for example to improve the efficiency and security for fully simulatable adaptive OT, such
as the universally composable (UC) OT scheme of Green and Hohenberger [5] with an initialization overhead of O ( n ). How-
ever, Cao and Liu [6] pointed out that the parameters of Green and Hohenberger’s scheme are redundant, and presented
an improved scheme by removing the unnecessary generators. A comparative summary of the performance comparison of
standard model-based OT protocols is available in [7,8] .
However, as quantum computing fast becoming a reality, we need to also design quantum secure / resilient OT (and
other cryptographic) protocols. Lattice-based cryptography is one of the most promising post-quantum candidates [9] . While
there have been a number of different lattice-based cryptosystems, there are only a very small number of lattice-based OT
protocols. For example, by extending the trap-door generator proposed by Micciancio and Peikert, Li et al. [10] designed an
efficient 1-out- n OT protocol based on ring learning with errors (R-LWE) hardness. Using short integer solution (SIS) and
learning with errors (LWE), Libert et al. [11] proposed an adaptive OT protocol for access control, capable of enforcing any
access policy in NC1 (Nick’s Class 1). Other related studies include those of Liu et al. [12] .
At the time of this research, one of the most efficient 1-out- n OT scheme is that of Chou and Orlandi [13] . Specifically,
due to the fast scalar multiplications on twisted Edwards curve, the scheme of Chou and Orlandi achieves approximately
10,0 0 0 1-out-2 OTs per second, where the computational cost is only n +6 exponentiation (i.e., 3 for the receiver, n + 3 for
the sender) and only 2 group elements have to be transmitted during the 1-out- n OT phase. Despite the authors’ claim that
their scheme is fully simulatable and resistant to timing attacks in the random oracle model, Li and Micciancio [14] argued
that it is not secure against corrupted senders under the equational framework [15] . In addition, when the number of
message entries scales up significantly, the key exchange in their protocol will be expensive due to the exponentiation on
large moduli.
In this paper, we use the lattice-based NTRU cryptographic primitive to design a quantum secure and efficient 1-out- n
OT protocol. Our choice of NTRU been used as the underlying cryptographic primitive is because it is known that to be
quantum computing attack resilience [16] . In the next section, we will present related background materials relating to
NTRU. We then describe our proposed 1-out- n OT protocol in Section 3 . In Sections 4 and 5 , we will present the security
and performance evaluation of our proposed protocol. In the last section, we conclude this paper.
2. NTRU primitive
The building block of our protocol is mainly based on a quotient ring R = Z[ x ] / (x
N
− 1) , whose elements can be repre-
sented as a series of vectors a = (a
0
, a
1
, ··· , a
N−1
) ∈ Z
N
. In fact, the ring R can also be considered as a composition, consist-
ing of convolution polynomials
a (x ) = a
0
+ a
1
x + a
2
x
2
+ ···+ a
N−1
x
N−1
. (1)
Since identifying the irreducible polynomial factors for a truncated polynomial is reducible to the shortest vector problem
(SVP) on lattice, NTRUEncrypt is believed to be resistant against quantum computing attacks. Due to the simple convolution
polynomial multiplications used in NTRU, its computational cost only increases quadratically with the key size.
Each NTRU cryptosystem is determined by three parameters p, q and N , where N, p should be prime and the condition
gcd (N, q ) = gcd (p, q ) = 1 must be satisfied. According to p and q , the convolution polynomial ring R can be truncated as two
sub-rings R
p
= (Z/pZ)[ x ] / (x
N
− 1) and R
q
= (Z/qZ)[ x ] / (x
N
− 1) , whose elements are equivalent to that of R by central lifting.
To generate a NTRU key pair, the receiver randomly samples two vectors f ∈ J (d + 1 , d) and g ∈ J (d , d ) , in terms of a
predefined integer d , where
J (d
1
, d
2
) =
⎧
⎪
⎨
⎪
⎩
a ∈ {−1 , 0 , 1 }
N
:
d
1
elements of a are 1
d
2
elements of a are − 1
ot her elements of a are 0
⎫
⎪
⎬
⎪
⎭
, (2)
Then, one computes the inverse of f as f
q
= f
−1
∈ R
q
and f
p
= f
−1
∈ R
p
respectively. Noting that the vector f must be
re-sampled if any of the inverses does not exist. Therefore, the receiver is in a position to determine out and distribute
h = f
q
∗ g ∈ R
q
as his/her public key while keeping ( f , f
p
) private.