834 lines
89 KiB
Plaintext
834 lines
89 KiB
Plaintext
Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
Contents lists available at ScienceDirect
|
||
|
||
|
||
Journal of Systems Architecture
|
||
journal homepage: www.elsevier.com/locate/sysarc
|
||
|
||
|
||
|
||
|
||
Fast post-quantum private set intersection from oblivious pseudorandom
|
||
function for mobile social networks✩
|
||
Zhuang Shan a , Leyou Zhang a ,∗, Qing Wu b , Qiqi Lai c , Fuchun Guo d
|
||
a School of Mathematics and Statistics, Xidian University, Xi’an 710126, China
|
||
b
|
||
School of Automation, Xi’an University of Posts and Telecommunications, Xi’an 710121, China
|
||
c
|
||
School of Computer Science, Shaanxi Normal University, Xi’an 710121, China
|
||
d
|
||
Centre for Computer and Information Security Research, University of Wollongong, Wollongong, NSW 2522, Australia
|
||
|
||
|
||
|
||
ARTICLE INFO ABSTRACT
|
||
|
||
Keywords: Mobile social networks have become integral to our daily lives, transforming communication methods and
|
||
Mobile social networks facilitating social interactions. With technological advancements, users generate vast amounts of valuable
|
||
Private set intersection and sensitive personal data, which is stored on servers to enable instant information sharing. To protect the
|
||
Oblivious pseudorandom function
|
||
sharing data, each platform has implemented many techniques such as end-to-end encryption mechanisms,
|
||
Private information retrieval
|
||
fully homomorphic encryption, etc. However, these approaches face several security and privacy challenges,
|
||
including potential leaks of user data, vulnerabilities in encryption that expose privacy ciphertexts to
|
||
probabilistic attacks, and threats posed by future quantum computers.
|
||
Aimed at the above, we introduce a private set intersection (PSI) protocol based on oblivious pseudorandom
|
||
functions (OPRF) under ring LPR problem from lattice. The proposed perturbed pseudorandom generator
|
||
not only enhances the PSI’s resistance to probabilistic attacks, but also leads to generate a more efficient
|
||
OPRF and a PSI. It boasts a time complexity of 𝑂(𝑛 log 𝑛) and is superior to existing well-known fast post-
|
||
quantum PSI protocol operating at 𝑂(𝑚𝑛 log(𝑚𝑛)), where 𝑚 is the bit length of the cryptographic modulus and 𝑛
|
||
represents the dimension of the security parameter. Simulation experiments and security analyses demonstrate
|
||
that our proposal effectively preserves user privacy, ensures collusion resilience, verifies computation results,
|
||
and maintains low computational costs. Finally, as an expansion of our OPRF, we also give a fast private
|
||
information retrieval (PIR) protocol.
|
||
|
||
|
||
|
||
1. Introduction respective data sets. This way, even if data is stored in distributed
|
||
systems, it can effectively prevent data breaches and violations of user
|
||
Mobile social networks have greatly enriched the ways people com- privacy, such as those caused by data leaks or unauthorized access.
|
||
municate and enhanced the convenience of social interactions. With the The application of PSI in mobile social networks not only enhances
|
||
development of technology, users generate a large amount of useful data security but also strengthens user trust in the platform, which
|
||
and sensitive personal data within mobile social networks. This data
|
||
is crucial for protecting user privacy and improving the platform’s
|
||
often needs to be stored and processed to provide more personalized
|
||
competitiveness. In this way, mobile social networks can continue to
|
||
services and experiences [1,2]. However, due to the limited storage
|
||
capacity of mobile social network devices, it is impossible to store all provide a rich and vibrant social experience and efficient information
|
||
the data generated at any given moment, which presents challenges for services while safeguarding personal privacy. Furthermore, as an im-
|
||
data storage and privacy protection. portant application in the field of privacy computing, PSI has recently
|
||
To address this issue while ensuring data confidentiality and se- garnered widespread attention due to its efficiency and practicality,
|
||
curity, many mobile social network platforms have started adopting jointly promoting the rapid implementation of privacy computing tech-
|
||
advanced privacy-preserving technologies, such as private set inter- nology and ensuring the secure flow and value extraction of data
|
||
section (PSI). The technology allows two or more parties to securely elements.
|
||
compute the intersection of their datasets without disclosing their
|
||
|
||
|
||
✩ This document is the results of the research project funded by the National Science Foundation.
|
||
∗ Corresponding author.
|
||
E-mail addresses: arcsec30@stu.xidian.edu.cn (Z. Shan), lyzhang@mail.xidian.edu.cn (L. Zhang), xiyouwuq@126.com (Q. Wu), laiqq@snnu.edu.cn (Q. Lai),
|
||
fuchun@uow.edu.au (F. Guo).
|
||
|
||
https://doi.org/10.1016/j.sysarc.2025.103346
|
||
Received 3 November 2024; Received in revised form 24 December 2024; Accepted 16 January 2025
|
||
Available online 25 January 2025
|
||
1383-7621/© 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
set intersection from oblivious pseudorandom function is proposed in
|
||
this paper, and it has the following advantages:
|
||
|
||
• Symmetric encryption is adopted, which is efficient and reduces the risk of
|
||
privacy leakage. The PSI in this paper is constructed based on OPRF,
|
||
which belongs to asymmetric encryption, thus reducing the number
|
||
of interactions between users and lowering the risk of user privacy
|
||
leakage. Compared to symmetric encryption, the operational cost of
|
||
asymmetric encryption is lower, reducing reliance on authoritative
|
||
institutions.
|
||
• The structure of OPRF is simple, and it is relatively efficient in post-
|
||
quantum OPRF. The OPRF used to construct PSI in this paper is based
|
||
on a new lattice problem, namely the learning parity with rounding
|
||
Fig. 1. Mobile social networks.
|
||
over ring problem(Ring-LPR). The Ring-LPR problem not only has a
|
||
simple structure but also possesses the capability to resist quantum
|
||
attacks.
|
||
• A perturbed pseudorandom generator (PPRG) can withstand probabilistic
|
||
attacks. In addition to OPRF, the PSI in this paper also includes
|
||
a structure with a perturbed pseudorandom generator, which can
|
||
overcome the weakness of weak encryption in symmetric encryp-
|
||
tion, thereby preventing adversaries from guessing the corresponding
|
||
plaintext using statistical methods on the ciphertext ratios.
|
||
|
||
|
||
Fig. 2. Private set intersection. 1.2. Technical overview
|
||
|
||
We adopted oblivious transfer technique and hamming correlation
|
||
There are many common construction tools for PSI [3], and obliv- robustness, both of which are used in the OPRF construction presented
|
||
ious transfer (OT) is one of them. An OT [4] is a crucial tool used in this paper. For the incidental pseudorandom function subject, we
|
||
for secure multiparty computation. In this tool, the sender transmits initially aimed to use learning parity with noise (LPN) over rings.
|
||
data from a set of messages to the receiver but remains oblivious to However, this approach results in varying encryption outcomes for the
|
||
which specific message was sent, while the receiver is unaware of the same private data, preventing the recipient from matching the private
|
||
other messages they did not receive. This protocol is also known as the
|
||
data. Thus, we sought to make LPN over rings behave consistently
|
||
oblivious transfer protocol. The essence of an oblivious pseudorandom
|
||
like learning with rounding (LWR), leading to the introduction of the
|
||
function is a pseudorandom function (PRF) enhanced with oblivious
|
||
concept of learning parity with rounding over rings (LPR over rings) in
|
||
transfer capabilities.
|
||
this paper.
|
||
In 1986, Goldreich, Goldwasser, and Micali introduced a new cryp-
|
||
To prove that LPR over rings is quantum-resistant, we established
|
||
tographic primitive known as the pseudorandom function, whose out-
|
||
put appears to be randomly chosen [5]. Two decades later, Naor and a reduction bridge between LPR over rings and LWR. Yes, LPR over
|
||
Reingold [6] noticed that their number-theoretic PRF allows for an rings is reduced to LWR, not LPN over rings. For (𝑞 = 2𝑛 , 𝑝)-LWR
|
||
interactive and oblivious evaluation, where a ‘‘client’’ with input 𝑥 instances, we demonstrated the hardness of (𝑞 = 2, 𝑝 = 1)-LWR instances
|
||
obtains 𝐹𝑘 (𝑥) for a function 𝐹𝑘 (𝑥) that is contributed by a ‘‘server’’. and (𝑞 = 2, 𝑝 = 1)-LWR over rings, where (𝑞 = 2, 𝑝 = 1)-LWR over
|
||
Neither does the client learn the function (i.e., its key 𝑘), nor does the rings corresponds to LPR over rings. To verify that the computational
|
||
server learn 𝑥 or 𝐹𝑘 (𝑥). Freedman et al. later called such two-party efficiency of the post-quantum OPRF in this paper is quite fast, we
|
||
protocol an OPRF and gave first formal definitions and two OPRFs compared the OPRF with the LWE-instantiated OPRF from [14]. The
|
||
based on the Naor-Reingold PRF [7]. In 2009, Jarecki and Liu presented results showed that, as theoretical analysis suggested, the computation
|
||
an efficient OPRF for securing intersection data [8]. efficiency improves with the increase of security parameters.
|
||
Oblivious pseudorandom functions have been utilized in PSI [9]. Based on OPRF, we constructed private set intersection (PSI) based
|
||
The additional functionalities of oblivious pseudorandom functions on OPRF. Since the paper [15] analyzed that PSI based on symmetric
|
||
also exhibit diversity, such as verifiable oblivious pseudorandom func- encryption does not resist probabilistic attacks and proposed the con-
|
||
tions (VOPRF, [10]) and partially oblivious pseudorandom functions cept of perturbed pseudorandom generator, we used LPN over rings
|
||
(POPRF, [11]). to construct a pseudorandom generator and proved that it satisfies the
|
||
Currently, OPRFs still faces challenges, as summarized by Casacu- definition of PPRG as given in [15].
|
||
berta, Hesse, and Lehmann [12]. Efficient OPRF constructions often
|
||
rely on discrete-log or factoring-type hardness assumptions, which
|
||
1.3. Organizations
|
||
are vulnerable to quantum computers. This paper aims to address
|
||
this by constructing OPRFs based on lattice-hardness assumptions and
|
||
improving their efficiency (see Figs. 1 and 2). The structure of this paper is as follows. Section 3 provides the
|
||
necessary definitions and lemmas as a foundation for the readers’
|
||
1.1. Contributions knowledge. Section 4 presents the construction and efficiency analysis
|
||
of OPRF, along with the definition and reduction of Ring-LPR. Section 5
|
||
Regarding the open problem proposed by Casacuberta, there are details the construction of the PSI in this paper, security proofs, and
|
||
currently quantum-resistant OPRFs, namely Albrecht et al.’s lattice- LWE-based efficiency analysis, as well as the construction of the PPRG
|
||
based VOPRF [10] and Boneh et al.’s isogeny-based OPRF [13]. Both and the proof of its pseudorandomness. Finally, Section 6 summarizes
|
||
constructions represent significant feasibility results but require further the advantages and limitations of the PSI presented in this paper, as
|
||
research to improve their efficiency [12]. So, fast post-quantum private well as the extension of OPRF to PIR
|
||
|
||
2
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
2. Preliminary ⎛ 0 0 0 ⋯ 0 −1 ⎞
|
||
⎜ 1 0 0 ⋯ 0 0 ⎟
|
||
Each element of a lattice in R𝑛 can be expressed linearly by 𝑛 ⎜ ⎟
|
||
0 1 0 ⋯ 0 0 ⎟
|
||
𝑋=⎜ .
|
||
linearly independent vector integer coefficients. This set of linearly ⎜ 0 0 1 ⋯ 0 0 ⎟
|
||
independent vectors is called a lattice basis, and we know that the ⎜ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⎟⎟
|
||
⎜
|
||
lattice basis is not unique. Given a set of lattice bases (𝑣1 , … , 𝑣𝑛 ) in ⎝ 0 0 0 ⋯ 1 0 ⎠
|
||
the lattice , then the fundamental parallelelepiped is
|
||
{ 𝑛 } So there is
|
||
∑ |
|
||
(𝑣1 , … , 𝑣𝑛 ) = 𝑘𝑖 𝑣𝑖 ||𝑘𝑖 ∈ [0, 1) . ⎛ 𝑎0 −𝑎𝑛−1 ⋯ −𝑎1 ⎞
|
||
| ⎜ ⎟
|
||
𝑖=1 𝑎1 𝑎0 ⋯ −𝑎2 ⎟
|
||
𝑅𝑜𝑡(𝑓 ) = ⎜ ,
|
||
If the lattice base (𝑣1 , … , 𝑣𝑛 ) is determined, use the symbol () to ⎜ ⋮ ⋮ ⋱ ⋮ ⎟
|
||
replace (𝑣1 , … , 𝑣𝑛 ). ∀𝑥 ∈ R𝑛 , project it onto (). According to the ⎜ 𝑎 𝑎𝑛−2 ⋯ ⎟
|
||
𝑎0 ⎠
|
||
⎝ 𝑛−1
|
||
properties of projection, there is a unique 𝑦 ∈ () makes 𝑦 − 𝑥 ∈ .
|
||
it is easy to prove that this mapping relationship is isomorphic.
|
||
Use the symbol det () to represent the volume of the fundamental
|
||
parallelelepiped of the lattice . In other words, the symbol det ()
|
||
Definition 3 (Learning with Rounding, [16,17]). Let 𝜆 be the security
|
||
represents the determinant of a matrix composed of a set of lattice bases
|
||
parameter, 𝑛 = 𝑛(𝜆), 𝑚 = 𝑚(𝜆), 𝑞 = 𝑞(𝜆), 𝑝 = 𝑝(𝜆) be integers. The LWR
|
||
(𝑣1 , … , 𝑣𝑛 ). For a given 𝑛 dimensional lattice, the det () size of any set
|
||
problem states that for 𝐴 ∈ Z𝑚×𝑛 𝑛 𝑚
|
||
𝑞 , 𝑠 ∈ Z𝑞 , 𝑢 ∈ Z𝑞 the following distri-
|
||
of lattice bases of the lattice is constant.
|
||
butions are computationally indistinguishable: (𝐴, ⌊𝐴𝑠⌋𝑝 ) ≈𝐶 (𝐴, ⌊𝑢⌋𝑝 ).
|
||
Given 𝑛 lattice , (𝑣1 , … , 𝑣𝑛 ) and (𝑢1 , … , 𝑢𝑛 ) are two arbitrary groups
|
||
∑ Here ⌊𝑥⌋𝑝 = ⌊ 𝑞𝑝 𝑥⌋, ⌊𝑥⌋ represents the floor function, which rounds down
|
||
of lattice respectively lattice bases. Therefore, there is 𝑣𝑖 = 𝑛𝑗=1 𝑚𝑖𝑗 𝑢𝑗
|
||
∑𝑛 ′ to the nearest integer. For example, ⌊3.14⌋ = 3 and ⌊3⌋ = 3.
|
||
and 𝑢𝑖 = 𝑗=1 𝑚𝑖𝑗 𝑣𝑗 , 𝑖 ∈ {1, … , 𝑛}, there are two integer matrices 𝑀 and
|
||
𝑀 ′ such that
|
||
⎛ 𝑣1 ⎞ ⎛ 𝑢1 ⎞ ⎛ 𝑢1 ⎞ ⎛ 𝑣1 ⎞ Definition 4 (Learning Parity with Noise, [18,19]). Let 𝜆 be the security
|
||
⎜ ⋮ ⎟ = 𝑀 ⎜ ⋮ ⎟ and ⎜ ⋮ ⎟ = 𝑀 ′ ⎜ ⋮ ⎟ . parameter, 𝑛 = 𝑛(𝜆), 𝑚 = 𝑚(𝜆) be integers. The LPN problem states
|
||
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
|
||
⎝ 𝑣𝑛 ⎠ ⎝ 𝑢𝑛 ⎠ ⎝ 𝑢𝑛 ⎠ ⎝ 𝑣𝑛 ⎠ that for 𝐴 ∈ Z𝑚×𝑛
|
||
2
|
||
, 𝑠 ∈ Z𝑛2 , 𝑢, 𝑒 ∈ Z𝑚
|
||
2
|
||
the following distributions are
|
||
computationally indistinguishable: (𝐴, 𝐴𝑠 + 𝑒) ≈𝐶 (𝐴, 𝑢).
|
||
It is easy to prove that 𝑀 and 𝑀 ′ are inverse to each other, and 𝑀
|
||
and 𝑀 ′ are both integer matrices, there are det (𝑀)⋅ det (𝑀 ′ ) = 1 and
|
||
det (𝑀) = det (𝑀 ′ ) = ±1, so Definition 5 (Hamming Correlation Robustness, [14]). For a hash func-
|
||
det (𝑣1 , … , 𝑣𝑛 ) = ± det (𝑢1 , … , 𝑢𝑛 ). tion (⋅) and a pseudorandom function 𝐹𝑘 (⋅) with key 𝑘, (⋅) is Ham-
|
||
ming correlation robust if (𝑥) ≈𝐶 𝐹𝑘 (𝑥).
|
||
|
||
|
||
Definition 1. An ideal lattice is a subset of rings or domains that Definition 6 (OT1 ). The message sender sends data to the receiver
|
||
satisfies the following two properties: from a set of pending messages but remains oblivious to which specific
|
||
message was sent. Meanwhile, the receiver is unaware of the additional
|
||
1. Additive closure: If any two elements in the ideal are added, the data they want to receive. This protocol is also known as oblivious
|
||
result is still in the ideal. In other words, for any elements 𝑎 and transfer.
|
||
𝑏 in the ideal, 𝑎 + 𝑏 also belongs to that ideal.
|
||
2. Multiplicative absorptivity: If an element in the ideal is multi-
|
||
plied by any element in the ring (or field), the result is still in Definition 7 (OPRF, [20]). Let the PRF key 𝑘 consist of two bit-
|
||
the ideal. In other words, for any element 𝑎 in the ideal and any strings 𝑞 , 𝑠 ∈ {0, 1}𝜆 . Let 𝐹 (⋅)be a pseudorandom code that produces a
|
||
element 𝑟 in the ring (or field), 𝑎𝑟 and 𝑟𝑎 belong to that ideal. pseudorandom string and let be a hash function. The pseudorandom
|
||
function is computed as
|
||
For a commutative ring, further require that the ideal be closed for both
|
||
addition and multiplication. Such an ideal is called a true ideal. OPRF𝑘 (𝑥) = (𝑞 ⊕ [𝐹 (𝑥) ⋅ 𝑠]),
|
||
|
||
where ⋅ denotes bitwise-AND and ⊕ denotes bitwise-XOR. For a ran-
|
||
Definition 2. Referring to the definition of ideal, the ideal lattice is domly generated s, if 𝐹 (𝑥) has enough Hamming weight then the
|
||
a subset of the lattice that satisfies the following two properties: function OPRF𝑘 (𝑥) is pseudorandom assuming the hash function is
|
||
correlation robust.
|
||
1. Additive closure: If any two elements in an ideal lattice are
|
||
added, the result is still in the ideal lattice. In other words, for
|
||
any elements 𝑎 and 𝑏 in an ideal lattice, 𝑎+𝑏 also belongs to that Definition 8 (PSI, [14]). PSI enables two parties, each holding a private
|
||
ideal lattice. set of elements, to compute the intersection of the two sets while
|
||
2. Multiplicative absorptivity: If an element in an ideal lattice is revealing nothing more than the intersection itself.
|
||
multiplied by an element in any other ideal lattice, the result
|
||
remains in the ideal lattice. In other words, for any element 𝑎 in
|
||
Definition 9 (Dihedral Coset Problem). Given a security parameter 𝜅, for
|
||
the ideal and any element 𝑟 in another ideal lattice, both 𝑎𝑟 and
|
||
an instance of the DCP𝓁𝑞 problem, where 𝑁 denotes the modulus and 𝓁
|
||
𝑟𝑎 belong to that ideal lattice.
|
||
represents the number of states. Each state is expressed as
|
||
|0⟩|𝑥𝑖 ⟩ + |1⟩|(𝑥𝑖 + 𝑠) mod 𝑞⟩, 𝑖 ≤ 𝓁,
|
||
Corollary 1. The ideal lattice is a true idea of the lattice . and it stores 1 + ⌈log2 𝑞⌉ bits, where 𝑥 ∈𝑅 Z𝑛𝑞 and 𝑠 ∈ Z𝑛𝑞 . If 𝑠 can be
|
||
For 𝑓 (𝑥) = 𝑎0 + 𝑎1 𝑥 + ⋯ + 𝑎𝑛−1 𝑥𝑛−1 is mapped to computed with probability poly(1∕ log 𝑞) in time poly(log 𝑞), then the
|
||
DCP𝓁𝑞 problem is considered to be broken.
|
||
𝑅𝑜𝑡(𝑓 ) = 𝑎0 𝐼 + 𝑎1 𝑋 + ⋯ + 𝑎𝑛−1 𝑋 𝑛−1 ∈ .
|
||
̃
|
||
|
||
Among them, ̃ is the mapping of all Z[𝑥]∕<𝑥𝑛 + 1> to the elements in
|
||
1
|
||
the ideal lattice collection, and https://blog.csdn.net/m0_61869253/article/details/139362753
|
||
|
||
|
||
3
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
3.2. Security proof of OPRF
|
||
|
||
Note 1. The Dihedral Coset Problem is a difficult problem in quantum In this subsection, we will provide the definition of the underly-
|
||
computing, and solving it has a time complexity of 𝑂(𝑒𝑛 ) or 𝑂(𝑛!). ing lattice problem for OPRF, learning parity with rounding, and its
|
||
reduction proof.
|
||
|
||
Lemma 1. If an efficient algorithm can solve DCP𝓁2 in polynomial
|
||
Definition 11 (Learning Parity with Rounding). Let 𝜆 be the security
|
||
time, then there exists an efficient algorithm ′ that can solve DCP𝓁𝑞 in
|
||
parameter, 𝑛 = 𝑛(𝜆), 𝑚 = 𝑚(𝜆) be integers. The LPR problem states
|
||
polynomial time.
|
||
that for 𝐴 ∈ Z𝑚×𝑛
|
||
2
|
||
, 𝑠 ∈ Z𝑛2 , 𝑢 ∈ Z𝑚 2
|
||
the following distributions are
|
||
computationally indistinguishable: (𝐴, ⌊𝐴𝑠 mod 4⌋1 ) ≈𝐶 (𝐴, ⌊𝑢⌋1 ).
|
||
Proof. We use a proof by contradiction. Suppose 𝑞 = 2𝑛 and there exists
|
||
an efficient algorithm that can solve DCP𝓁2 in polynomial time. For Definition 12 (Learning Parity with Rounding Over Ring). The Ring LPR
|
||
instances of DCP𝓁4 , we have problem states that for 𝑎, 𝑠, 𝑢 ∈ 2 the following distributions are
|
||
|0⟩|𝑥𝑖 ⟩+|1⟩|(𝑥𝑖 + 𝑠) mod 4⟩ = |0⟩|𝑥′𝑖 ⟩ + |1⟩|(𝑥′𝑖 + 𝑠′ ) mod 2⟩ computationally indistinguishable: (𝑎, ⌊𝑎𝑠 mod 4⌋1 ) ≈𝐶 (𝑎, ⌊𝑢⌋1 ).
|
||
+ 2(|0⟩|𝑥′′ ′ ′′
|
||
𝑖 ⟩ + |1⟩|(𝑥𝑖 + 𝑠 ) mod 2), 𝑖 ≤ 𝓁,
|
||
|
||
so running the algorithm twice will solve DCP𝓁4=22 . Similarly, run- Lemma 4. For an LWR problem instance ⌊𝐴𝑠⌋𝑝 , if there exists an algorithm
|
||
ning four times will solve DCP𝓁16=24 , and continuing in this manner, for solving 𝑠 from ⌊𝐴𝑠⌋1 , then there also exists an algorithm ′ for
|
||
running the algorithm 𝑛 times will solve DCP𝓁𝑞 . Let 𝑂() represent solving the LWR problem.
|
||
the time complexity of the algorithm . Thus, we have ′ ≤ 𝑛𝑂()
|
||
and algorithm ′ is an efficient algorithm. □ Proof. Given that there exists an algorithm that can solve ⌊𝐴𝑠⌋1 =
|
||
⌊ 𝐴𝑠 ⌋, for an LWR problem instance ⌊𝐴𝑠⌋𝑝 , we have:
|
||
𝑞 ⌊ ⌋
|
||
Definition 10 (Extrapolated Dihedral Coset Problem with model 2, [21]). 1 1 𝑝𝐴𝑠
|
||
⌊𝐴𝑠⌋𝑝 =
|
||
Given a security parameter 𝜅, an instance of EDCP𝓁𝑛,2,𝜌 is provided, 𝑝 𝑝 𝑞
|
||
( )
|
||
where 2 denotes the modulus, 𝜌 represents the probability density 1 𝑝𝐴𝑠
|
||
= +𝑒 (𝑒 ∈ (−1, 0]𝑚 )
|
||
function, and 𝓁 denotes the number of states. Each state is expressed 𝑝 𝑞
|
||
( ( ]𝑚 )
|
||
as 1 1
|
||
∑ = 𝐴𝑠 + 𝑒′ 𝑒′ ∈ − , 0
|
||
𝜌(𝑗)|𝑗⟩|(𝑥𝑖 + 𝑗 𝑠) mod 2⟩, 𝑖 ≤ 𝓁, 𝑞 𝑝
|
||
𝑗∈supp(𝜌) ≈ ⌊𝐴𝑠⌋1 .
|
||
and stores 2 bits, where 𝑥𝑖 ∈𝑅 Z𝑛2 and 𝑠 ∈ Z𝑛2 . If 𝑠 can be determined
|
||
Thus, the algorithm can be used to solve the LWR problem. □
|
||
with probability poly(1∕(𝑛 log 2)) in time poly(𝑛 log 2), then the EDCP𝓁𝑛,2,𝜌
|
||
problem is considered to be broken. We get next corollary by Lemma 3.
|
||
√
|
||
Corollary 3. Let (𝑛, 2, 𝑟 = 𝛺( 𝜅)) be an instance of G-EDCP and (𝑛, 2, 𝛼)
|
||
Lemma 2. If there exists an algorithm for solving EDCP𝓁𝑛,4,𝜌 , then this be an instance of 2-LWR. If there exists an algorithm for solving 2-LWR,
|
||
algorithm can also solve DCP𝓁4 . then there exists an algorithm for solving G-EDCP𝓁𝑛,2,𝜌 .
|
||
𝑟
|
||
|
||
|
||
√
|
||
Proof. Let Corollary 4. Let (𝑛, 2, 𝑟 = 𝛺( 𝜅)) be an instance of G-EDCP and (𝑛, 2, 𝛼)
|
||
1 1 be an instance of LPR. If there exists an algorithm for solving LPR, then
|
||
|𝑏⟩ = √ |0⟩|𝑥𝑖 ⟩ + √ |1⟩|(𝑥𝑖 + 𝑠) mod 4⟩.
|
||
2 2 there exists an algorithm for solving G-EDCP𝓁𝑛,2,𝜌 .
|
||
𝑟
|
||
|
||
Thus, 𝜌(0)|0⟩ = √1 |0⟩ and 𝜌(1)|1⟩ = √1 |1⟩. Hence, DCP𝓁2 is a special
|
||
2 2
|
||
case of EDCP𝓁𝑛,2,𝜌 . Therefore, if there exists an algorithm for solving Lemma 5. If there exists an algorithm for solving the Ring-LPR problem,
|
||
EDCP𝓁𝑛,2,𝜌 , this algorithm can also solve DCP𝓁2 . □ then there also exists an algorithm ′ for solving the LPR problem.
|
||
|
||
|
||
√ Proof. For an instance of the inner product Ring-LPR
|
||
Lemma 3 ([21]). Let (𝑛, 𝑞 , 𝑟 = 𝛺( 𝜅)) be an instance of G-EDCP and
|
||
(𝑛, 𝑞 , 𝛼) be an instance of LWE. If there exists an algorithm for solving 𝑏 = ⌊𝑎 ⋅ 𝑠⌋1
|
||
LWE𝑛,𝑞,𝛼 , then there exists an algorithm for solving G-EDCP𝓁𝑛,𝑞,𝜌 . where 𝑎 = 𝑎0 + 𝑎1 𝑥 + ⋯ + 𝑎𝑛−1 𝑥𝑛−1 , we can represent 𝑎 as a circulant
|
||
𝑟
|
||
matrix, specifically
|
||
√ ⎛ 𝑎0 −𝑎𝑛−1 ⋯ −𝑎1 ⎞
|
||
Corollary 2. Let (𝑛, 2, 𝑟 = 𝛺( 𝜅)) be an instance of G-EDCP and (𝑛, 2, 𝛼) ⎜ ⎟
|
||
𝑎 𝑎0 ⋯ −𝑎2 ⎟
|
||
be an instance of LPN. If there exists an algorithm for solving LPN𝑛,𝛼 , then 𝐴1 ∶= ⎜ 1
|
||
.
|
||
⎜ ⋮ ⋮ ⋱ ⋮ ⎟
|
||
there exists an algorithm for solving G-EDCP𝓁𝑛,2,𝜌 . ⎜ 𝑎 ⎟
|
||
𝑟
|
||
⎝ 𝑛−1 𝑎𝑛−2 ⋯ 𝑎0 ⎠
|
||
Thus,
|
||
3. Ring-LPR based OPRF
|
||
𝑏 = ⌊𝑎 ⋅ 𝑠⌋1 ⇒ 𝑏 = 𝐴1 𝑠.
|
||
3.1. Constructing OPRF where 𝑎 = (𝑎0 , 𝑎1 , … , 𝑎𝑛−1 ) ← 𝑎 = 𝑎0 + 𝑎1 𝑥 + ⋯ + 𝑎𝑛−1 𝑥𝑛−1 . We use
|
||
a proof by contradiction. Suppose there exists an efficient algorithm
|
||
Fig. 3 presents the ring LPR-based oblivious pseudorandom func- that can solve Ring-LPR in polynomial time. We take the first row
|
||
tion. In the next section, we will prove the security of the oblivious from 𝐴1 , denote it as 𝛼1 , and have ⌊𝛼1 𝑠⌋1 = 𝑏1 , where 𝑏1 is the first
|
||
pseudorandom function. component of 𝑏. For the LWR problem instance, 𝛽⃗ = ⌊𝛬𝑠⃗⌋1 , assume
|
||
|
||
4
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
|
||
|
||
Fig. 3. Oblivious Pseudorandom Function (OPRF).
|
||
|
||
|
||
|
||
𝛬𝑇 = (𝛼1 , 𝛼2 , … , 𝛼𝑚 ).
|
||
|
||
Thus, we use the algorithm 𝑚 times to find 𝛽𝑖 such that ⌊𝛾𝑖 ⌋1 = 𝛽𝑖 =
|
||
⌊𝛼1 𝑠1 ⌋1 , and thus we can solve the equation
|
||
𝛾 = 𝛬𝑠⃗, 𝛾 𝑇 = (𝛾1 , … , 𝛾𝑚 ).
|
||
|
||
|
||
Assuming that the time complexity of solving 𝑠 from LWR problem
|
||
instance is 𝑂(𝛬, 𝛽), according to Corollary 3, let 𝑂(𝛾 = 𝛬𝑠⃗) be the
|
||
computational complexity of solving the equation 𝛾 = 𝛬𝑠⃗, we have
|
||
𝑚𝑂() + 𝑂(𝛾 = 𝛬𝑠⃗) ≥ 𝑂(𝛬, 𝛽) ≥ 𝑂(𝑛!) or 𝑂(𝑒𝑛 ).
|
||
|
||
Let 𝑚 = 𝑛, then
|
||
𝑂(𝛬, 𝛽) − 𝑂(𝛾 = 𝛬𝑠⃗)
|
||
𝑂() ≥
|
||
𝑛
|
||
𝑂(𝑛!) − 𝑂(𝛾 = 𝛬𝑠⃗) 𝑂(𝑒𝑛 ) − 𝑂(𝛾 = 𝛬𝑠⃗)
|
||
≥ or .
|
||
𝑛 𝑛
|
||
This contradicts the assumption that there is an efficient algorithm
|
||
that can solve the inner product Ring-LPR in polynomial time, thus the
|
||
theorem holds. □
|
||
|
||
|
||
3.3. Efficiency analysis
|
||
|
||
This section simulates the OPRF computation efficiency of this
|
||
paper and OPRF in [14] on MAC, Pad and Phone. The PRF of [14]
|
||
is instantiated based on LWE.
|
||
|
||
3.3.1. Efficiency analysis on MAC
|
||
The tools used in the subsection are Python 3.12, the programs are
|
||
performed on MacBook Air MAC Desktop Apple M1, RAM 8.00 GB (see
|
||
Fig. 4).
|
||
|
||
3.3.2. Efficiency analysis on mobile pad
|
||
The tools used in the subsection are Pydriod 3, the programs are
|
||
performed on Xiaomi Pad 6 Pro File Explorer 1th Qualcomm(R)AI En-
|
||
gine(TM) Xiaolong 8+ mobile platform@3.2 GHz, RAM 8.00+3.00 GB
|
||
(see Fig. 5).
|
||
Fig. 4. Parallel comparison of OPRF on MAC, where 𝑛 represents the security
|
||
parameter, unit is microseconds.
|
||
3.3.3. Summary of data comparison
|
||
From the simulation results, it can be seen that for 𝑛 ≤ 250, the
|
||
LWE-based OPRF in [14] is slightly faster, while for 𝑛 > 250, the ring
|
||
LPR-based OPRF in this paper is faster. Furthermore, as 𝑛 increases, 4. PSI based on OPRF
|
||
the advantages of ring LPR become more pronounced. Based on the
|
||
simulation results for Pad, the OPRF in this paper is more stable; In this paper, apart from OPRF, another tool used in the construction
|
||
although there are fluctuations, they are less significant compared to of PSI is a perturbed pseudorandom generator [15]. The perturbed
|
||
the LWE-based OPRF in [14]. pseudorandom generator in this paper is constructed from Ring-LPN.
|
||
|
||
5
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
|
||
|
||
Fig. 6. Pseudorandom generator with perturbation 𝐺𝛾 (⋅).
|
||
|
||
|
||
|
||
√
|
||
√𝑛−1
|
||
√∑
|
||
‖𝑎‖ = √ |𝑎 |2 . 𝑖
|
||
𝑖=0
|
||
|
||
|
||
|
||
|
||
Definition 15 ([15]). A pseudorandom generator with perturbation,
|
||
denoted as 𝐺𝛾 (⋅), is defined such that for 𝑥1 , 𝑥2 ∈ , there exists 𝛾
|
||
satisfying the following conditions:
|
||
|
||
1. When 𝑥1 = 𝑥2 , Pr (𝐺𝛾 (𝑥1 ) = 𝐺𝛾 (𝑥2 )) ≤ 𝑂(exp(−𝑛)),
|
||
2. When 𝑥1 = 𝑥2 , such that ‖𝐺𝛾 (𝑥1 ) − 𝐺𝛾 (𝑥2 )‖ < 𝛾, there exists 𝑁
|
||
such that ‖𝐺𝛾 (𝑥1 ) − 𝐺𝛾 (𝑥2 )‖ ≥ 𝛾 ⋅ 𝑁, where clearly 𝑁 = 1 is
|
||
optimal.
|
||
|
||
|
||
|
||
Theorem 1. The Ring-LPN problem itself can be viewed as a pseudorandom
|
||
function with perturbations.
|
||
|
||
|
||
Proof. We prove each statement separately. First, when 𝑥1 = 𝑥2 , we
|
||
Fig. 5. Parallel comparison of OPRF on mobile pads, where 𝑛 represents the security have
|
||
parameter, unit is microseconds. ( ) 1
|
||
Pr 𝐺𝛾 (𝑥1 ) = 𝐺𝛾 (𝑥2 ) = Pr (𝑒1 = 𝑒2 ) = 𝑛 .
|
||
2
|
||
√
|
||
Additionally, set 𝛾 = 𝑛 + 1, so
|
||
Next, we will present the reduction process for Ring-LPN.
|
||
‖(𝐴𝑥1 + 𝑒1 ) − (𝐴𝑥2 + 𝑒2 )‖ = ‖𝑒1 − 𝑒2 ‖ < 𝛾 .
|
||
4.1. Reduction of ring-LPN When 𝑥1 ≠ 𝑥2 , set 𝑣1 = 𝐺𝛾 (𝑥1 ), 𝑣2 = 𝐺𝛾 (𝑥2 ), and know that
|
||
√ ∑𝑛 ( )𝑘 ( )𝑛−𝑘
|
||
1 1
|
||
Definition 13 (Learning Parity with Noise Over Ring). The learning parity Pr (‖𝑣1 − 𝑣2 ‖ ≤ 𝑛) = 𝐶𝑛𝑘
|
||
𝑘=0
|
||
3 2
|
||
with noise over ring problem states that for 𝑎, 𝑠, 𝑒, 𝑢 ∈ {0,1} the
|
||
following distributions are computationally indistinguishable: (𝑎, 𝑎𝑠 + ∑
|
||
𝑛∕2 ( )𝑘 ( )𝑘 ( )𝑛−2𝑘
|
||
1 1 1
|
||
+ 𝐶𝑛𝑘 .
|
||
𝑒) ≈𝐶 (𝑎, 𝑢). 3 6 2
|
||
𝑘=0
|
||
|
||
Because
|
||
( )𝑘 ( )𝑛−𝑘 ( ( )2 ( )𝑛 )
|
||
Corollary 5. If there exists an efficient algorithm that can solve the ∑𝑛
|
||
1 1 1 2 2 2
|
||
Ring-LPN problem in polynomial time, then there also exists an algorithm 𝐶𝑛𝑘 = 𝑛 + +⋯+
|
||
𝑘=0
|
||
3 2 2 3 3 3
|
||
′ that can solve the LPN problem. ( ( )𝑛 )
|
||
3 2
|
||
= 𝑛 1− ,
|
||
2 3
|
||
Proof. The proof method is similar to that of Lemma 5, but this way
|
||
and
|
||
the computational complexity of will decrease. If we want the Ring- ( )
|
||
∑
|
||
𝑛∕2 ( )𝑘 ( )𝑘 ( )𝑛−2𝑘 ( ) 2𝑛
|
||
LPN problem to be ‘approximately’ as hard as the LPN problem, then 1 1 1 3⋅6 1 1
|
||
𝐶𝑛𝑘 ≤ 1− .
|
||
for the security parameters 𝜅1 of the Ring-LPN problem and 𝜅2 of the 𝑘=0
|
||
3 6 2 17 2𝑛− 2𝑛 3⋅6
|
||
LPN problem, we have
|
||
Therefore
|
||
𝑒𝜅1 (𝜅 )! ( √ √ )
|
||
≥ 𝑒𝜅2 , or 1 ≥ (𝜅2 )!. 1
|
||
Pr ‖𝑣1 − 𝑣2 ‖ ≤ 𝑛 < 𝑛 + 1 ≤ 𝑛 .
|
||
𝜅12 𝜅12 2
|
||
√
|
||
Thus, we can roughly obtain 𝜅1 ≥ 1.5𝜅2 and 𝜅2 ≥ 12. Note that 𝑂(𝑛) Thus, there is a very high probability that ‖𝑣1 −𝑣2 ‖ ≥ 𝑛 + 1, and 𝑁 = 1
|
||
is an asymptotically large quantity with respect to 𝑛. We use the most (see Fig. 6). □
|
||
extreme case to determine the relationship between 𝜅1 and 𝜅2 . □
|
||
|
||
|
||
4.2. Perturbed pseudorandom generator 4.3. PSI based on OPRF
|
||
|
||
Definition 14. Let 𝑎 = 𝑎0 + 𝑎1 𝑥 + ⋯ + 𝑎𝑛−1 𝑥𝑛−1 ∈ {0,1} . Define the Lemma 6. Assuming 𝑓 (𝑦) ≈𝐶 𝑢1 and 𝑔(𝑢1 ) ≈𝐶 𝑢2 , then (𝑔◦𝑓 )(𝑦) ≈𝐶 𝑢2 .
|
||
norm of 𝑎 as ‖𝑎‖, and
|
||
|
||
6
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
|
||
|
||
Fig. 7. PSI based on OPRF.
|
||
|
||
|
||
|
||
|
||
Fig. 9. Parallel comparison of PSI on mobile pads, where 𝑛 represents the security
|
||
parameter, unit is microseconds.
|
||
|
||
|
||
|
||
|
||
Fig. 8. Parallel comparison of PSI on MAC, where 𝑛 represents the security parameter, Fig. 10. Comparison of PSI on mobile phones, where 𝑛 represents the security
|
||
unit is microseconds. parameter, unit is microseconds.
|
||
|
||
|
||
|
||
7
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
|
||
|
||
Fig. 11. PIR based on OPRF.
|
||
|
||
|
||
Proof. On one hand, because the pseudorandom 𝐹̃𝑘 ∶ {0,1} × {0, 1}∗ →
|
||
{0,1} , for any 𝑘 ∈ {0,1} , 𝑦 ∈ ⊂ {0, 1}∗ , we have 𝐹̃𝑘 (𝑦) ≈𝐶 𝑢𝜔 ∈
|
||
{0,1} .
|
||
On the other hand, due to the pseudorandom function 𝐹𝑘 ∶ {0,1} ×
|
||
{0,1} → {0,1} , for 𝑢𝓁1 ∈ {0,1} , we have 𝐹𝑘 (𝑢𝓁1 ) ≈𝐶 𝑢𝜔 . According
|
||
to the property of the hash function, have 1 (𝑦) ≈𝐶 𝑢𝓁1 . Combining
|
||
with Lemma 6, one can obtain that 𝐹𝑘 (1 (𝑦)) ≈𝐶 𝑢𝜔 . Consequently,
|
||
𝐹̃𝑘 (𝑦) ≈𝐶 𝐹𝑘 (1 (𝑦)). □
|
||
|
||
|
||
Theorem 2. If 1 is a collision resistant hash function, 2 and 3
|
||
are hamming correlation robustness, then the protocol in Fig. 7 securely
|
||
realizes 𝑃 𝑆 𝐼 in the semi-honest model when parameters 𝑚, 𝑤 are chosen
|
||
as described in [14].
|
||
|
||
|
||
Proof. Perspective from 𝑃1 .
|
||
Hyb0 𝑃1 ’s view and 𝑃2 ’s output in the real protocol.
|
||
Hyb1 Same as Hyb0 except that on 𝑃2 ’s side, for each 𝑖 ∈ [𝜔], if 𝑠[𝑖] = 0,
|
||
then sample 𝐴𝑖 ← {0, 1}𝑚 and compute 𝐵𝑖 = 𝐴𝑖 ⊕ 𝐷𝑖 ; otherwise
|
||
sample 𝐵𝑖 ← {0, 1}𝑚 and compute 𝐴𝑖 = 𝐵𝑖 ⊕ 𝐷𝑖 . This hybrid is
|
||
identical to Hyb0 .
|
||
Hyb2 Initialize an 𝑚 × 𝑤 binary matrix 𝐷 to all 1’s. Denote its column
|
||
vectors by 𝐷1 , … , 𝐷𝜔 . Then 𝐷1 = ⋯ = 𝐷𝜔 = 1𝑚 . For 𝑦 ∈ ,
|
||
randomly select 𝑣 ← [𝑚]𝜔 , and set 𝐷𝑖 [𝑣[𝑖]] = 0 for all 𝑖 ∈ [𝜔].
|
||
Hyb3 Find a suitable pseudorandom function 𝐹̃𝑘 ∶ {0,1} × {0, 1}∗ →
|
||
{0,1} . For 𝑦 ∈ , compute 𝑣̃ = 𝐹̃𝑘 (𝑦), randomly select 𝑣 ← [𝑚]𝜔 ,
|
||
and set 𝐷𝑖 [𝑣[𝑖]] = 0 for all 𝑖 ∈ [𝜔].
|
||
Hyb4 Let there be a pseudorandom function 𝐹 ∶ {0,1} ×{0,1} → {0,1}
|
||
and a hash function 1 ∶ {0, 1}∗ → {0,1} . For 𝑦 ∈ , compute
|
||
𝑣′ = 𝐹𝑘 (1 (𝑦)), randomly select 𝑣 ← [𝑚]𝜔 , and set 𝐷𝑖 [𝑣[𝑖]] = 0 for
|
||
all 𝑖 ∈ [𝜔].
|
||
Hyb5 Let there be a pseudorandom function 𝐹 ∶ {0,1} × {0,1} →
|
||
{0,1} , Hamming Correlation Robustness 2 ∶ Z𝑚×𝜔 {0,1}
|
||
→ {0,1}
|
||
and a hash function 1 ∶ {0, 1}∗ → {0,1} . For 𝑦 ∈ , compute
|
||
𝑣′ = 𝐹𝑘 (1 (𝑦)), 𝑣 = 2 (𝑣′ ), and set 𝐷𝑖 [𝑣[𝑖]] = 0 for all 𝑖 ∈ [𝜔].
|
||
Fig. 12. Parallel comparison of PIR on MAC, where 𝑛 represents the security parameter, Given that Hyb0 ≈𝐶 Hyb1 ≈𝐶 Hyb2 ≈𝐶 Hyb3 , Hyb4 ≈𝐶 Hyb5 and
|
||
unit is microseconds. according to Lemma 7, it be known that Hyb3 ≈𝐶 Hyb4 . Therefore, we
|
||
have Hyb0 ≈𝐶 Hyb5 .
|
||
Perspective from 𝑃2 .
|
||
Lemma 7. Find a suitable pseudorandom function 𝐹̃𝑘 ∶ {0,1} × {0, 1}∗ → Hyb0 𝑃2 ’s view in the real protocol.
|
||
{0,1} . Assuming that the pseudo-random function 𝐹𝑘 ∶ {0,1} × {0,1} →
|
||
Hyb1 𝜓 ← {0,1} , all other aspects are consistent with the real
|
||
{0,1} and the hash function 1 ∶ {0, 1}∗ → {0,1} are indistinguishable,
|
||
protocol.
|
||
we have
|
||
Hyb2 Introduce 𝐺𝛾 ∶ {0,1} → {0,1} and Hamming Correlation
|
||
𝐹̃𝑘 (𝑦) ≈𝐶 𝐹𝑘 (1 (𝑦)).
|
||
Robustness 3 ∶ Z𝑚×𝜔 {0,1}
|
||
→ {0,1} , let the initial matrices be
|
||
𝐶1 = ⋯ = 𝐶𝜔 = 1𝑚 , randomly select 𝑣 ∈ [𝑚]𝜔 , set 𝐶𝑖 [𝑣[𝑖]] = 0
|
||
for all 𝑖 ∈ [𝜔]. Compute 𝐺𝛾 (𝐶1 [𝑣[1]]‖ ⋯ ‖𝐶𝜔 [𝑣[𝜔]]).
|
||
|
||
8
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
Hyb3 Let the initial matrices be 𝐶1 = ⋯ = 𝐶𝜔 = 1𝑚 , find an appropriate • Setup The simulator generates some necessary parameters for the
|
||
pseudorandom function 𝐹̃𝑘 ∶ {0,1} × {0, 1}∗ → {0,1} . For 𝑦 ∈ , algorithms and selects an appropriate hash functions 1 ∶ {0, 1}∗ →
|
||
compute 𝑣̃ = 𝐹̃𝑘 (𝑦), randomly select 𝑣 ← [𝑚]𝜔 , set 𝐶𝑖 [𝑣[𝑖]] = 0 for {0,1} , Hamming Correlation Robustness 2 ∶ {0,1} → [𝑚]𝜔 , Ham-
|
||
all 𝑖 ∈ [𝜔]. Compute 𝐺𝛾 (𝐶1 [𝑣[1]]‖ ⋯ ‖𝐶𝜔 [𝑣[𝜔]]). ming Correlation Robustness 3 ∶ Z𝑚×𝜔 → {0,1} and a 𝐺𝛾 ∶ {0,1} →
|
||
{0,1}
|
||
Hyb4 Let the initial matrices be 𝐶1 = ⋯ = 𝐶𝜔 = 1𝑚 , set a pseudo- {0,1} , a pseudorandom function 𝐹 ∶ {0,1} × {0,1} → {0,1} with
|
||
random function 𝐹 ∶ {0,1} × {0,1} → {0,1} , a hash function key 𝑘 ∈ {0,1} . The adversary 𝑃1 selects 𝑠 and transmits 𝑠 to the
|
||
1 ∶ {0, 1}∗ → {0,1} and Hamming Correlation Robustness simulator using OT.
|
||
𝑚×𝜔
|
||
3 ∶ Z{0,1} → {0,1} . For 𝑦 ∈ , compute 𝑣′ = 𝐹𝑘 (1 (𝑦)), • H-Query, PRF-Query and PRG-Query The adversary 𝑃1 makes
|
||
randomly select 𝑣 ← [𝑚]𝜔 . Set 𝐶𝑖 [𝑣[𝑖]] = 0 for all 𝑖 ∈ [𝜔]. Compute queries about the hash function, pseudorandom function, oblivious
|
||
𝐺𝛾 (3 (𝐶1 [𝑣[1]]‖ ⋯ ‖𝐶𝜔 [𝑣[𝜔]])). transfer values, and pseudorandom generator. The simulator pre-
|
||
Hyb5 Let the initial matrices be 𝐶1 = ⋯ = 𝐶𝜔 = 1𝑚 , set a pseu- establishes lists for handling H-Query, PRF-Query, and PRG-Query
|
||
dorandom function 𝐹 ∶ {0,1} × {0,1} → {0,1} and a hash respectively.
|
||
function 1 ∶ {0, 1}∗ → {0,1} , Hamming Correlation Robustness
|
||
𝑚×𝜔
|
||
2 ∶ Z{0,1} → {0,1} and 3 ∶ Z𝑚×𝜔 → {0,1} . For 𝑦 ∈ , – 1 -Query For the 𝑖th query 𝑥𝑖 ∈ {0, 1}∗ corresponding to the
|
||
{0,1}
|
||
compute 𝑣′ = 𝐹𝑘 (1 (𝑦)), compute 𝑣′ = 𝐹𝑘 (1 (𝑦)). Set 𝐶𝑖 [𝑣[𝑖]] = 0 value of 1 , the simulator selects from the hash value list
|
||
for all 𝑖 ∈ [𝜔]. Compute 𝐺𝛾 (3 (𝐶1 [𝑣[1]]‖ ⋯ ‖𝐶𝜔 [𝑣[𝜔]])). if available, otherwise selects a random 𝑋𝑖 ∈ {0,1} . Set 𝑋𝑖 =
|
||
Similarly, it can be proven that Hyb0 ≈𝐶 Hyb5 . □ 1 (𝑥𝑖 ) and update the list accordingly.
|
||
– 2 -Query For the 𝑖th query 𝑦𝑖 ∈ {0,1} corresponding to the
|
||
value of 2 , the simulator selects from the hash value list if
|
||
Definition 16 (CPA Security Model of the Protocol in Fig. 7). Assume available, otherwise selects a random 𝑌𝑖 ∈ [𝑚]𝜔 . Set 𝑌𝑖 = 2 (𝑦𝑖 )
|
||
there exists a perturbed pseudorandom oracle machine 𝑃 𝑟𝑀𝛾 (where
|
||
and update the list accordingly.
|
||
𝛾 is the upper bound on the norm of the perturbation in 𝑃 𝑟𝑀𝛾 ), such
|
||
– 3 -Query For the 𝑖th query 𝑧𝑖 ∈ Z𝑚×𝜔 corresponding to the
|
||
that for an input 𝑥, it outputs two values: one is a random value 𝑦0 , {0,1}
|
||
value of 3 , the simulator selects from the hash value list
|
||
and the other is a pseudorandom value 𝑦1 with 𝑥 as its input.
|
||
if available, otherwise selects a random 𝑍𝑖 ∈ {0,1} . Set 𝑍𝑖 =
|
||
• Setup The simulator generates the necessary parameters for 3 (𝑧𝑖 ) and update the list accordingly.
|
||
the algorithms. The adversary chooses 𝑠 and sends it to the – 𝐹 -Query For the 𝑖th query 𝑢𝑖 ∈ {0,1} corresponding to the value
|
||
simulator using OT. of 𝐹 , the simulator selects from the pseudorandom function
|
||
• Hash Queries, PRF Queries and PRG Queries The adversary value list if available, otherwise selects a random 𝑈𝑖 ∈ {0,1} .
|
||
sequentially performs hash function queries, pseudorandom Set 𝑈𝑖 = 𝐹 (𝑢𝑖 , 𝑘) and update the list accordingly.
|
||
function queries, and pseudorandom synthesizer queries. Here,
|
||
– 𝐺𝛾 -Query For the 𝑖th query 𝑤𝑖 ∈ {0,1} corresponding to the
|
||
the adversary cannot know the key in pseudorandom function
|
||
value of 𝐺𝛾′ , the simulator selects from the pseudorandom
|
||
queries.
|
||
generator value list if available, otherwise selects a random
|
||
• Challenge The adversary selects a private message 𝑚 and sends
|
||
𝑊𝑖 ∈ {0,1} . Set 𝑊𝑖 = 𝐺𝛾′ (𝑤𝑖 ) and update the list accordingly.
|
||
it to the simulator . The simulator queries the hash function,
|
||
pseudorandom function, and oblivious transfer values of the real Note that 𝐺𝛾′ is not 𝐺𝛾black-box .
|
||
scheme, inputs these results into the pseudorandom oracle ma-
|
||
chine 𝑃 𝑟𝑀𝛾 , obtains two ciphertexts 𝑐0 and 𝑐1 , and sends them • Challenge 𝑃1 selects 𝑚 ∈ ∕ and sends it to . using the corre-
|
||
to the adversary . sponding hash function queries and pseudorandom function queries,
|
||
• Guessing After receiving the two ciphertexts 𝑐0 and 𝑐1 , guesses inputs the queried values into the black-box 𝐺𝛾′ , obtaining 𝜓0 and 𝜓1 ,
|
||
which ciphertext corresponds to the encryption of 𝑚 and sends the and then sends 𝜓0 , 𝜓1 to 𝑃1 .
|
||
guess back to the simulator . • Guess Based on the received 𝜓0 and 𝜓1 , 𝑃1 guesses whether 𝜓0 or
|
||
The advantage of the adversary is defined as the advantage of the 𝜓1 is the ciphertext of the encrypted message 𝑚.
|
||
simulator in distinguishing the outputs of 𝑃 𝑟𝑀𝛾 . According to the assumption, if the adversary 𝑃1 can break the
|
||
scheme with a non-negligible advantage, then the simulator can
|
||
Note 2. The 𝑃 𝑟𝑀 mentioned in this paper differs from [22]. In [22], also break the black-box 𝐺𝛾′ with a non-negligible advantage. This
|
||
𝑃 𝑟𝑀 refers to a pseudorandom oracle machine that outputs random contradicts the assumption that 𝐺𝛾′ is secure. □
|
||
values when the adversary does not know the pseudorandom function key,
|
||
and outputs pseudorandom function values based on the key known to the
|
||
adversary when the key is known. This is a single-value output. However, the 4.4. Efficiency analysis PSI
|
||
𝑃 𝑟𝑀 required in this paper outputs both of these values simultaneously,
|
||
making it a multi-value output. This section simulates the PSI computation efficiency of this pa-
|
||
per and PSI in [14] on MAC, Pad, and Phone. The PRF of [14] is
|
||
Theorem 3. If 1 is a collision resistant hash function, 2 and 3 are instantiated based on LWE.
|
||
hamming correlation robustness, then the protocol in Fig. 7 securely realizes
|
||
𝑃 𝑆 𝐼 in Definition 16.
|
||
4.4.1. Efficiency analysis on MAC
|
||
The tools used in the subsection are Python 3.12, the programs are
|
||
Proof. Suppose the adversary 𝑃1 can break the scheme with non- performed on MacBook Air MAC Desktop Apple M1, RAM 8.00 GB (see
|
||
negligible advantage. Now, the simulator simulates the scheme. Fig. 8).
|
||
Suppose there exists a black-box 𝐺𝛾𝑏𝑙𝑎𝑐 𝑘−𝑏𝑜𝑥 such that
|
||
𝑦0 = 𝐺𝛾 (𝑥) ∈ {0,1} ,
|
||
4.4.2. Efficiency analysis on mobile pad
|
||
↗ The tools used in the subsection are Pydriod 3, the programs are
|
||
𝐺𝛾𝑏𝑙𝑎𝑐 𝑘−𝑏𝑜𝑥 (𝑥) → (𝑦0 , 𝑦1 )
|
||
↘ performed on Xiaomi Pad 6 Pro File Explorer 1th Qualcomm(R)AI En-
|
||
𝑦1 ∈𝑅 {0,1} . gine(TM) Xiaolong 8+ mobile platform@3.2 GHz, RAM 8.00+3.00 GB
|
||
(see Fig. 9).
|
||
|
||
9
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
4.5. Analysis of efficiency on mobile phones Acknowledgments
|
||
|
||
The tools used in the subsection are Pydriod 3, the programs are per- This work was supported in part by the National Nature Science
|
||
formed on Redmi K30 File Explorer 4th Qualcomm(R)AI Engine(TM) Foundation of China under Grant 61872087 and Grant 51875457; in
|
||
Qualcomm Xiaolong 730G 8+ mobile platform@2.2 GHz, RAM 6.00 GB part by the Key Foundation of National Natural Science Foundation
|
||
(see Fig. 10). of China under Grant U19B2021; and in part by the Key Research
|
||
and Development Program of Shaanxi under Program 2022GY-028 and
|
||
Program 2022GY-050.
|
||
4.5.1. Summary of data comparison
|
||
From the simulation results, it can be seen that for 𝑛 ≤ 400, the Data availability
|
||
LWE-based OPRF in [14] is slightly faster, while for 𝑛 > 400, the ring
|
||
LPR-based OPRF in this paper is faster. Furthermore, as 𝑛 increases, No data was used for the research described in the article.
|
||
the advantages of ring LPR become more pronounced. Based on the
|
||
simulation results for Pad, the OPRF in this paper is more stable;
|
||
although there are fluctuations, they are less significant compared to References
|
||
the LWE-based OPRF in [14].
|
||
[1] R. Lei, X. Chen, D. Liu, C. Song, Y. Tan, A. Ren, CEIU: Consistent and efficient
|
||
incremental update mechanism for mobile systems on flash storage, J. Syst. Ar-
|
||
5. Expansion of this work chit. 152 (2024) 103151, http://dx.doi.org/10.1016/j.sysarc.2024.103151, URL:
|
||
https://www.sciencedirect.com/science/article/pii/S1383762124000882.
|
||
[2] J. Sun, L. Yin, M. Zou, Y. Zhang, T. Zhang, J. Zhou, Makespan-minimization
|
||
Private Information Retrieval (PIR) [23–29] is a technique that workflow scheduling for complex networks with social groups in edge
|
||
enables a client to securely download a specific element, such as a computing, J. Syst. Archit. 108 (2020) 101799, http://dx.doi.org/10.1016/
|
||
movie or a friend’s record, from a database managed by an untrusted j.sysarc.2020.101799, URL: https://www.sciencedirect.com/science/article/pii/
|
||
server, such as a streaming service or a social network, without disclos- S1383762120300928.
|
||
[3] Y. Gao, Y. Luo, L. Wang, X. Liu, L. Qi, W. Wang, M. Zhou, Efficient scalable
|
||
ing to the server which particular element has been retrieved. Given
|
||
multi-party private set intersection(-variants) from bicentric zero-sharing, in:
|
||
the functional similarities between PIR and PSI, this paper extends its
|
||
Proceedings of the Conference on Computer and Communications Security, CCS,
|
||
exploration into the construction of PIR using OPRF (see Fig. 11). Association for Computing Machinery (ACM), New York, NY, USA, 2024.
|
||
[4] M.O. Rabin, How to exchange secrets with oblivious transfer, 2005, URL: https:
|
||
5.1. Efficiency analysis PIR //eprint.iacr.org/2005/187.
|
||
[5] O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions, J.
|
||
ACM 33 (4) (1986) 792–807, http://dx.doi.org/10.1145/6490.6503.
|
||
This section simulates the PSI computation efficiency of this paper [6] M. Naor, O. Reingold, Number-theoretic constructions of efficient pseudo-random
|
||
and machine learning-based PIR in [30](DLMI for short) on MAC. functions, J. ACM 51 (2) (2004) 231–262, http://dx.doi.org/10.1145/972639.
|
||
The tools used in the subsection are Python 3.12, the programs are 972643.
|
||
[7] M.J. Freedman, Y. Ishai, B. Pinkas, O. Reingold, Keyword search and oblivious
|
||
performed on MacBook Air MAC Desktop Apple M1, RAM 8.00 GB.
|
||
pseudorandom functions, in: J. Kilian (Ed.), Theory of Cryptography, Springer
|
||
The OPRF-based PIR proposed in this paper has a runtime that Berlin Heidelberg, Berlin, Heidelberg, 2005, pp. 303–324.
|
||
differs from the machine learning-based PIR by no more than approx- [8] S. Jarecki, X. Liu, Efficient oblivious pseudorandom function with applications
|
||
imately 5 × 10−3 seconds. Additionally, the security of our PIR scheme to adaptive OT and secure computation of set intersection, in: O. Reingold (Ed.),
|
||
is theoretically supported in comparison to [30] (see Fig. 12). Theory of Cryptography, Springer Berlin Heidelberg, Berlin, Heidelberg, 2009,
|
||
pp. 577–594.
|
||
[9] V.K. Yadav, N. Andola, S. Verma, S. Venkatesan, A survey of oblivious trans-
|
||
6. Conclusion fer protocol, ACM Comput. Surv. 54 (10s) (2022) http://dx.doi.org/10.1145/
|
||
3503045.
|
||
This paper presents a PSI based on efficient post-quantum OPRF and [10] M.R. Albrecht, A. Davidson, A. Deo, N.P. Smart, Round-optimal verifiable
|
||
oblivious pseudorandom functions from ideal lattices, in: J.A. Garay (Ed.), Public-
|
||
proves its security under the semi-honest model, demonstrating security
|
||
Key Cryptography – PKC 2021, Springer International Publishing, Cham, 2021,
|
||
even in the CPA model in Definition 16. The addition of PPRG enables pp. 261–289.
|
||
the PSI to effectively resist probabilistic attacks. In the simulation [11] N. Tyagi, S. Celi, T. Ristenpart, N. Sullivan, S. Tessaro, C.A. Wood, A fast
|
||
experiments, the proposed PSI shows greater efficiency compared to and simple partially oblivious PRF, with applications, in: O. Dunkelman, S.
|
||
post-quantum PSIs represented by LWE. Dziembowski (Eds.), Advances in Cryptology – EUROCRYPT 2022, Springer
|
||
Although the PIR in this study is not as efficient as the machine International Publishing, Cham, 2022, pp. 674–705.
|
||
[12] S. Casacuberta, J. Hesse, A. Lehmann, Sok: Oblivious pseudorandom functions,
|
||
learning-based PIR, the gap between the two is already quite small.
|
||
in: 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P),
|
||
However, there are also notable shortcomings; the efficiency of the 2022, pp. 625–646, http://dx.doi.org/10.1109/EuroSP53844.2022.00045.
|
||
proposed PSI still lags behind that of non-post-quantum PSIs, which [13] D. Boneh, D. Kogan, K. Woo, Oblivious pseudorandom functions from isogenies,
|
||
will be addressed in future work. in: S. Moriai, H. Wang (Eds.), Advances in Cryptology – ASIACRYPT 2020,
|
||
Springer International Publishing, Cham, 2020, pp. 520–550.
|
||
[14] M. Chase, P. Miao, Private set intersection in the internet setting from lightweight
|
||
CRediT authorship contribution statement oblivious PRF, in: D. Micciancio, T. Ristenpart (Eds.), Advances in Cryptology –
|
||
CRYPTO 2020, Springer International Publishing, Cham, 2020, pp. 34–63.
|
||
Zhuang Shan: Writing – original draft, Conceptualization. Leyou [15] Z. Shan, L. Zhang, Q. Wu, Q. Lai, Analysis, modify and apply in IIOT form
|
||
Zhang: Writing – review & editing, Writing – original draft. Qing Wu: light-weight PSI in CM20, 2024, URL: https://eprint.iacr.org/2024/969.
|
||
[16] J. Alwen, S. Krenn, K. Pietrzak, D. Wichs, Learning with rounding, revisited, in:
|
||
Conceptualization. Qiqi Lai: Writing – review & editing. Fuchun Guo:
|
||
R. Canetti, J.A. Garay (Eds.), Advances in Cryptology – CRYPTO 2013, Springer
|
||
Writing – review & editing. Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 57–74.
|
||
[17] A. Banerjee, C. Peikert, A. Rosen, Pseudorandom functions and lattices, in: D.
|
||
Declaration of competing interest Pointcheval, T. Johansson (Eds.), Advances in Cryptology – EUROCRYPT 2012,
|
||
Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 719–737.
|
||
[18] D. Bellizia, C. Hoffmann, D. Kamel, H. Liu, P. Méaux, F.-X. Standaert, Y.
|
||
The authors declare that they have no known competing finan- Yu, Learning parity with physical noise: Imperfections, reductions and FPGA
|
||
cial interests or personal relationships that could have appeared to prototype, IACR Trans. Cryptogr. Hardw. Embed. Syst. 2021 (2021) 390–417,
|
||
influence the work reported in this paper. URL: https://api.semanticscholar.org/CorpusID:235814670.
|
||
|
||
|
||
10
|
||
Z. Shan et al. Journal of Systems Architecture 160 (2025) 103346
|
||
|
||
|
||
[19] Y. Yu, J. Zhang, Smoothing out binary linear codes and worst-case sub- Leyou Zhang received the M.S. and Ph.D. degrees from Xid-
|
||
exponential hardness for LPN, in: T. Malkin, C. Peikert (Eds.), Advances in ian University, Xi’an, China, in 2002 and 2009, respectively.
|
||
Cryptology – CRYPTO 2021, Springer International Publishing, Cham, 2021, pp. From 2013 to 2014, he served as a visiting scholar at the
|
||
473–501. University of Wollongong, Australia. He currently worked
|
||
[20] V. Kolesnikov, R. Kumaresan, M. Rosulek, N. Trieu, Efficient batched oblivious in Xidian University as a professor.
|
||
PRF with applications to private set intersection, in: Proceedings of the 2016 His current research interests include public key cryp-
|
||
ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, tography, network security and computer security. He has
|
||
Association for Computing Machinery, New York, NY, USA, 2016, pp. 818–829, over 120 scientific publications in many highly ranked
|
||
http://dx.doi.org/10.1145/2976749.2978381. cybersecurity journals and conferences.
|
||
[21] Z. Brakerski, E. Kirshanova, D. Stehlé, W. Wen, Learning with errors and
|
||
extrapolated dihedral cosets, in: Public-Key Cryptography – PKC 2018, Springer
|
||
International Publishing, 2018, pp. 702–727.
|
||
[22] A. Jain, H. Lin, J. Luo, D. Wichs, The pseudorandom oracle model and ideal
|
||
obfuscation, in: H. Handschuh, A. Lysyanskaya (Eds.), Advances in Cryptology –
|
||
CRYPTO 2023, Springer Nature Switzerland, Cham, 2023, pp. 233–262.
|
||
Qing Wu received the M.S. and Ph.D. degrees from the Xid-
|
||
[23] S. Angel, H. Chen, K. Laine, S. Setty, PIR with compressed queries and amortized
|
||
ian University, Xi’an, China, in 2006 and 2009, respectively.
|
||
query processing, in: 2018 IEEE Symposium on Security and Privacy, SP, 2018,
|
||
She currently works with Xi’an University of Posts and
|
||
pp. 962–979, http://dx.doi.org/10.1109/SP.2018.00062. Communications, Xi’an, as a Professor. Her current research
|
||
[24] A. Burton, S.J. Menon, D.J. Wu, Respire: High-rate PIR for databases with small interests include artificial intelligence security and cloud
|
||
records, in: Proceedings of the Conference on Computer and Communications security.
|
||
Security, CCS, Association for Computing Machinery (ACM), New York, NY, USA,
|
||
2024.
|
||
[25] J. Dujmovic, M. Hajiabadi, Lower-bounds on public-key operations in PIR, in: M.
|
||
Joye, G. Leander (Eds.), Advances in Cryptology – EUROCRYPT 2024, Springer
|
||
Nature Switzerland, Cham, 2024, pp. 65–87.
|
||
[26] B. Fisch, A. Lazzaretti, Z. Liu, C. Papamanthou, Thorpir: Single server PIR via
|
||
homomorphic thorp shuffles, in: Proceedings of the Conference on Computer and
|
||
Communications Security, CCS, Association for Computing Machinery (ACM),
|
||
New York, NY, USA, 2024.
|
||
Qiqi Lai received the B.S. from PLA University of Informa-
|
||
[27] A. Gascon, Y. Ishai, M. Kelkar, B. Li, Y. Ma, M. Raykova, Computationally
|
||
tion Engineering, henan, China, in 2008. And he received
|
||
secure private information retrieval and aggregation in the shuffle model, in:
|
||
the M.S. and Ph.D. degrees from Xidian University, Xi’an,
|
||
Proceedings of the Conference on Computer and Communications Security, CCS, China, in 2011 and 2015.
|
||
Association for Computing Machinery (ACM), New York, NY, USA, 2024. His currently works with Shaanxi Normal University,
|
||
[28] A. Ghoshal, M. Zhou, E. Shi, Efficient pre-processing PIR without public- Xi’an, as a Professor. His current research interests include
|
||
key cryptography, in: M. Joye, G. Leander (Eds.), Advances in Cryptology – the theory of lattice-based public key cryptography and its
|
||
EUROCRYPT 2024, Springer Nature Switzerland, Cham, 2024, pp. 210–240. provable security, as well as the construction and analysis
|
||
[29] M. Luo, F.-H. Liu, H. Wang, Faster FHE-based single-server private information of homomorphic encryption schemes.
|
||
retrieval, in: Proceedings of the Conference on Computer and Communications
|
||
Security, CCS, Association for Computing Machinery (ACM), New York, NY, USA,
|
||
2024.
|
||
[30] M. Lam, J. Johnson, W. Xiong, K. Maeng, U. Gupta, Y. Li, L. Lai, I. Leontiadis,
|
||
M. Rhu, H.-H.S. Lee, V.J. Reddi, G.-Y. Wei, D. Brooks, E. Suh, GPU-based
|
||
Funcun Guo received the B.S. and M.S. degrees from Fujian
|
||
private information retrieval for on-device machine learning inference, in:
|
||
Normal University, China, in 2005 and 2008, respectively,
|
||
Proceedings of the 29th ACM International Conference on Architectural Support and the Ph.D. degree from the University of Wollongong,
|
||
for Programming Languages and Operating Systems, Volume 1, ASPLOS ’24, Australia, in 2013. He is currently an Associate Research
|
||
Association for Computing Machinery, New York, NY, USA, 2024, pp. 197–214, Fellow with the School of Computing and Information
|
||
http://dx.doi.org/10.1145/3617232.3624855. Technology, University of Wollongong.
|
||
His primary research interests include the public
|
||
key cryptography, in particular protocols, encryption and
|
||
Zhuang Shan received the B.S. from Liaoning Institute of signature schemes, and security proof.
|
||
Science and Technology, benxi, China, in 2019. And he
|
||
received the M.S. from North Minzu University, yinchuan,
|
||
China, in 2022.
|
||
He is currently pursuing the Ph,D. degree in mathemat-
|
||
ics with Xidian University, Xi’an, China. His current interests
|
||
include cryptography, reduction of hard problems in lattice,
|
||
and network security.
|
||
|
||
|
||
|
||
|
||
11
|
||
|