                                                               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
