dataesr/scientific-paragraphs-categorization huggingface dataset:
Private Information Retrieval (PIR) schemes aim to provide the same confidentiality to the user (with regard to the choice of the requested element) that downloading the entire database does, with sub-linear communication cost. PIR was introduced by Chor, Goldreich, Kushilevitz, and Sudan in 1995  [2]. They proposed a set of schemes to implement PIR through replicated databases that provide users with information-theoretic security, so long as some of the database replicas do not collude against the users. Note, however, that PIR schemes do not ensure database confidentiality: a user can retrieve more than a database element using a PIR scheme without the database being aware of it. A PIR scheme ensuring that users retrieve a single database element with each query is called a Symmetric PIR (or SPIR) scheme.
Generic transformations exist from PIR to SPIR but this is beyond the scope of this paper (see  [3] ). Performance in initial PIR schemes was evaluated when retrieving single-bit elements from a database. All recent protocols  [4] [5] [6]  are evaluated when retrieving multi-bit elements from a database. This setting was initially called Private Block Retrieval  [2]  but nowadays both terms are used interchangeably. All-or-nothing-disclosure-ofsecrets (ANDOS) protocols (e. g. [7] ) are simply multi-bit SPIR protocols. In this paper, we focus on PIR schemes that do not need the database to be replicated, and whose security is based on the computational security of a cryptographic algorithm, which are usually called singledatabase computationally-Private Information Retrieval (cPIR) schemes.
Performance Issues in cPIR A major issue with computationally-private information retrieval schemes is that they are computationally expensive. In order to answer a query, a database must process all of its entries. If a protocol does not process some entries, the database will learn that the user is not interested in them. This would reveal to the database partial information on which entry the user is interested in, and therefore, it is not as private as downloading the whole database and retrieving locally the desired entry. The computational cost for a server replying to a cPIR query is therefore linear on the database size. More precisely, in  [8] , Lipmaa proves that using a particular representation, this lower bound is slightly sub-linear (in O(n/log(log(n))). Moreover, most of the schemes have a very large cost per bit in the database, a multiplication over a large modulus.
This restricts both the database size and the throughput shared by the users and thus, limits their usage for many databases as well as for other applications such as private keyword search  [9]. In NDSS'07, Sion and Carbunar presented a paper on cPIR practicality  [1]. They showed that the existing, number theory based, cPIR protocols were not practical and that it was always faster to send the whole database than to compute a cPIR reply. Indeed, basing the security of the underlying number theoretic encryption schemes on the hardness to factor a 1024 bit RSA modulus, one could not expect a cPIR scheme to process the database at more than a megabit per second. Sending the whole database over most of the current Internet connections is at least an order of magnitude faster (and generally two orders of magnitude in local area networks).
Focused issue. As in  [1] , we tackle the issue of practical usage of cPIR. The main performance metric we use is the time needed for a client to retrieve an element privately, supposing one or more clients are querying a server with a commodity-CPU and can exchange data with the server at various speeds (xDSL, FTTH, etc. ). We consider that the client is ready to pay a significant overhead for privacy, and compare the time needed using different approaches (trivial full database download, number-theory based cPIR, lattice-based cPIR).
A noteworthy exception to this list of schemes is the cPIR scheme of Gasarch and Yerukhimovich  [24]  which relies on a lattice-based standard encryption scheme  [25]. However, this underlying encryption scheme has an extremely large expansion factor (large ciphertexts encoding only a few bits) that compromises the efficiency of the cPIR scheme. Alternatives to cPIR. Oblivious RAM (ORAM) protocols, which are used to access (and write on) a database privately, can handle efficiently databases of many Terabits. However, ORAM and PIR protocols are used for different applications and cannot be exchanged. Indeed, in the ORAM setting the database content is encrypted data outsourced from the user. ORAM cannot be used directly to privately download elements from a public database which is the paradigm of PIR, for example accessing a movie database à la Netflix.
In ORAM the data in the server is encrypted and user must know this key to access the data and to hide their access patterns. With PIR, no shared secret is needed, i. e. each user has an independent key whose objective is just to hide his own choice. ORAM is thus able to deal with larger databases but can only be used in personal or group-with-a-shared-key settings (e. g. for an encrypted and shared filesystem in the cloud). It is possible to transform an ORAM protocol into a PIR protocol using a hardware module (e. g. see  [26] ). When using a trusted hardware module is an acceptable constraint, such protocols allow clients to send expressive queries (interpretable by the module) to define the elements to be retrieved and have very low overhead. Instead of using a trusted hardware module, one can build efficient PIR protocols using replicated databases as shown by Chor, Goldreich, Kushilevitz, and Sudan  [27]  and by Olumofin and Goldberg  [28].
If replicating a database ont not colluding servers is an acceptable constraint, such protocols allow to retrieve data privately with very small computational and communication overhead. Interesting recent work by Devet and Goldberg  [22]  uses replicated-database PIR and cPIR jointly to achieve high performance results without compromising security when databases collude. This paper requires the database to be replicated, and therefore is very different from our setting. The proposed protocol uses Aguilar et al. 's cPIR scheme  [5]  as a building block, replacing it with our protocol would result in a performance boost and provide a secure instance of their construction. Works considering only computational or communication costs. In the Oblivious Transfer setting  [29] , the objective is to limit the computational cost for the user and the database without considering communication efficiency.
The whole database is sent encrypted to the client together with some extra information, with the added benefit that the server is guaranteed that the client can retrieve information about one element only per query. Some cPIR protocols focus only on communication efficiency without considering computational costs. In  [30] , a communication efficient cPIR protocol, from an asymptotic perspective, is built based on a fully-homomorphic scheme. The underlying encryption scheme we use is just an additively-homomorphic building block in  [30]  but our objective is to allow users to retrieve elements faster than the trivial solution of downloading the entire database in realistic settings. This implies taking into account computational and communication constraints. In  [31] , an implementation of a fully-homomorphic encryption based scheme is given.
The contribution of this scheme is on the communication overhead, which they show to be very small in some settings (when multiple database elements are retrieved). Computational costs are considered but this paper does not give a contribution in this sense that the database is at best processed at 20Kbits/s which is below the processing throughput of classic, number-theory based, cPIR schemes. As already noted, sending the whole database can be done at a higher throughput in most settings allowing to retrieve an element privately much faster. Finally, in  [32]  Kiayias et al. present a new cPIR scheme based on a number-theoretic homomorphic en-cryption scheme. The communication performance is extremely interesting, but again computational performance is still an issue. Adapting such work to latticebased encryption schemes would be of great practical and theoretical interest.
From a practical point of view the implementation we provide offers multi-gigabit processing throughput on a commodity CPU, and an optimizer to automatically tune the system (hardware/network/application/security). In Section 2, we present the basic tools a reader should be comfortable with in order to understand the rest of the paper: homomorphic encryption, which allows to compute over encrypted data; the objectives and the classical approaches to obtain private information retrieval protocols; and a special setting of cPIR called private keyword searching, in which instead of retrieving elements by their index as usually done in cPIR we retrieve elements based on the keywords they are associated to. In Section 3, we first present an overview of our protocol and describe the optimization process, and then we present our fast Ring-LWE based cPIR, the proposed algorithmic optimizations and performance results for the basic operations: query generation (encryption), database importation, reply generation, and reply extraction (decryption).
We use the Ring-LWE based homomorphic encryption scheme presented in  [30]. We describe it below, in order to justify some of our performance results. As in  [30]  we present the symmetric version and then explain how an asymmetric scheme can be derived. Notations: Z q denotes the set of relative integers modulo q. If S is a set x ← S represents a uniform sample from S, for a distribution χ, x ← χ represents a sample following that distribution. R q = Z q [X]/ < X N + 1 > represents the polynomials with coefficients over Z q such that after each operation they are reduced by division modulo X N + 1. Note that we use uppercase N for the polynomial degree (which is an unusual notation) to distinguish the polynomial degree from the number of elements in the database we will be dealing with in the cPIR protocol.
Definition 1 (cPIR Protocol). A (Single-Database) Computationally-Private Information Retrieval Protocol is a probabilistic polynomial-time (PPT) algorithm Γ, that for input k outputs the description of a polynomial-time randomized algorithm Q(•, •) (the query generator), and two polynomial-time deterministic algorithms, R(•, •) (the reply generator), and X(•, •) (the reply decoder), with the two following properties: (Correctness) For any number of elements n, index i, and database contents {db 1 ,. , db n }, and any (q, s) ← Q(i, n), X(R(q, {db 1 ,. , db n }), s) outputs db i. (Privacy) For any positive integers n > i 1 > i 2 , any polynomial-time probabilistic attacker A, there exists a negligible function (i. e. asymptotically smaller than any inverse polynomial) in k, such that, P r(A(α, i 1 , i 2 , P pir ) = i|Q ← Γ[k]; (α, s) ← Q(i, n)) < 1/2+ (k) i being randomly chosen among {i 1 , i 2 }, and P pir being the set of all the public information about the PIR protocol.
In this paper, we use a simple cPIR protocol whose basic idea is the one of  [27] , using the performance improvements on multi-bit database elements of  [7]  (but without taking into account the zero-knowledge proof ensuring symmetric privacy that is also proposed in  [7] ), described hereafter. It can be used with any additively homomorphic encryption scheme. The protocol can be formally described as follows: Security is defined with an indistinguishability game: no attacker can in practice distinguish queries for any two database elements. When used for a cPIR protocol, an encryption scheme with indistinguishability against plaintext attacks ensures that two queries for two different elements of a database are indistinguishable, using a standard hybrid argument (see  [7]  for a formal definition and proof).
With this simple approach, query size is n times the size of a ciphertext and reply is roughly × F , F being the expansion factor of the encryption scheme used. To reduce query size it is possible to aggregate them by groups of size α and obtain a database with n/α elements of size × α. It is also possible to use this protocol recursively. Due to space restrictions the recursive version of this algorithm is presented in the Appendix. In practice, recursion takes as parameter an integer d called dimension and results in a scheme in which the client only needs to send d × n 1/d query elements (ciphertexts) and the reply will be of size (roughly) F d ×. For example if F = 2 and we have a database with one million elements, it is possible to: send a query of 10 6 ciphertexts and get the database element with an expansion factor of 2 (d = 1, no recursion); send a query of 2 × 1000 ciphertexts and get the database element with an expansion factor of 4 (d = 2); send a query of.
Setup (user): 1. Set up an instance of the cryptosystem with k security bits Query Generation to retrieve element i 0 : 1. For i from 1 to n generate the i-th query element q i as -A random encryption of zero if i = i 0 -A random encryption of one if i = i 0 2. Send the ordered set {q 1 , • • • , qn} to the database Reply Generation: 1. Note db i the database elements, the bit size of the db i and 0 , the bits that can be absorbed in a ciphertext 2. For i from 1 to n -Split db i in chunks of 0 bits noted db i,j for j ∈ [1. ceil( / 0 )] 3. For j from 1 to ceil( / 0 ) -Compute R j := Sum n i=1 Absorb(db i,j , q i ) 4. Return R = (R 1 ,. , R ceil( / 0 ) ) Reply extraction: 1. Decrypt the coordinates of the reply vector R and recover db i 0 as the concatenation of the decrypted chunks 3 × 100 ciphertexts and get the database element with an expansion factor of 8 (d = 3); etc.
The reader is referred to  [7]  for a more elaborated description of these techniques and a justification of correctness. It is possible to make different choices on how the database is split and to change the cryptographic parameters used on each level to improve the performance of recursion. For a complete description, generalization and optimization of this process, the reader is referred to  [36]  which proposes many interesting variants. In our library, we have decided to stick to the basic approach for recursion although it would be interesting to develop other optimizations, such as those proposed in  [32, 36].
Private Searching The basic idea of private keyword search  [37]  is that the database can arrange its elements by grouping them using keywords. With this technique, users can get, using a cPIR protocol, all the database elements that match a given keyword. In this case, the query size is proportional to the amount of possible keywords D (Dictionary size) and the computational cost for the server may change as a database entry that is associated to multiple keywords will be copied once in front of each keyword. Thus, the computational cost will be the database size times the average amount of keywords a database element matches. It is also possible to use this to filter streamed data based on private criteria  [38]. The idea is to build ephemeral keyword-based databases for each message passing.
These databases have null elements everywhere except in front of the keywords that the passing message matches. The computational cost to process a packet is therefore its size times the number of keywords it matches (null elements cost nothing to process). With such an approach it is possible to build a filter that outputs for every passing message an encryption of zero when the message does not match the keyword and an encryption of the message when it does. We use this approach to build a sniffer over a gigabit link in Section 4 that is only interested in messages corresponding to a given IP address. In this sniffer, the streamed messages are the packets on the network, the keywords are the set of IP addresses used in a local area network, and a packet matches the IP-keyword corresponding to its source and destination address.
The sniffer's code includes a cPIR query selecting the IP that is being observed and thus even analyzing the code of the sniffer it is not possible to learn which is the IP address as the chosen keyword is hidden in the cPIR query. Important note: After processing an input, the filter always outputs a ciphertext and it is not possible to distinguish useful outputs from encryptions of zero. If we store all these results we will do not better than a trivial PIR based equivalent (which would store unencrypted all the input data). The main interest of using cPIR, is that it is possible to compress the output so that encryptions of zero are packed and useful outputs preserved, even if it is not known which of the outputs are useful. These techniques are beyond the scope of this paper (see  [39]  for the most recent proposal on the subject), but it is possible to have efficient filters which have only a small overhead with respect to an unencrypted filter that would store only the keyword-matching data.
In XPIR there is a set of predefined encryption schemes: no cryptography (trivial PIR with a full database download), Paillier  [40] , and Ring-LWE (see Section 2. 1). Each of the encryption schemes has a predefined list of possible parameters for security varying from 80 to 256 bits (following NIST recommendations for factoring-based cryptography for Paillier and  [35]  for lattice-based schemes). By default, the target function for optimization is the round-trip time of the retrieval which, using self-explanatory variable names, is given by the function max(queryGenerationT ime, querySending-T ime) + max(replyGenerationT ime, replySending-T ime, replyDecryptionT ime). This is due to the fact that query generation and sending are pipelined, then the server waits until it has the complete query and reply generation, sending and decryption are pipelined.
Tests correspond to the same laptop that will be used in Section 4 using all of its cores with multi-threading. Implications on cPIR performance These values have an impact in cPIR reply generation. Pre-processing corresponds to database element importation and processing to reply generation. When launching a server, database elements can be imported into RAM in NTT-CRT form at roughly 5Gbits/s. After importation, the database is processed during the reply generation phase at roughly 20Gbits/s. If data is quickly obsolete (e. g. 1. Pre-processing of a polynomial corresponds to NTT and CRT transforms, the main operation during database importation. Inverse transforms give similar results. Processing corresponds to a fused multiply and add (FMA), the main operation during reply generation. This operation's throughput will vary a lot depending on memory saturation: in this setting, if all operands and result change on each operation, processing time is multiplied by three with respect to the given values.
Here we used the same memory transfers as in our PIR scheme: for a given thread only one operand varies most of the time. Throughput is given with respect to input data: in pre-processing for each polynomial (Input size) bits are treated; in processing two polynomials must be processed to deal with (Input size) bits. IPTV streams) the main bottleneck is getting the data into NTT-CRT form and processing is limited by the importation phase to roughly 5 Gbits/s. For comparison purposes, using a Paillier based cPIR the same computer is able to process the database at 1Mbit/s (for a modulus of 2048 bits giving 112 bits of security). Again, for comparison purposes, in trivial PIR (i. e. full database download) processing a bit corresponds to sending it to the client and thus the database is processed at the available download throughput (e.
HElib supposes that the user defines the homomorphic computations he needs to do and then a routine defines a complete FHE context for him. In particular the user cannot choose to just use one or two primes, so we had to tweak the code to do comparable tests. Performance for polynomial multiplications is noticeably improved (between x2 and x3) with NTTTools, as Figure  3  shows. The gap is larger for pre-computation (x10). The reason for this is our choice to restrict polynomial degrees to powers of two, which opens up the usage of nice algorithms such as the one in  [44]. Finally, memory usage is much lower with NTT-Tools, which is not surprising given that we are in a simpler setting. For polynomials of degree 1024 and 60bit coefficients, the memory footprint in NTTTools is of 8 Kbytes by default and twice that with pre-computed quotients.
Using Double-CRT it is harder to evaluate the footprint as some data (such as the FHE context) is shared, but for large amounts of Double-CRT objects memory usage increases linearly at 40Kbytes per object. NTTTools and the schemes we developed over it will thus be an interesting replacement of Double-CRT for those looking for fast basic polynomial computation on the ideal setting or simple homomorphic operations. Those looking for more advanced operations should use Double-CRT.
Correctness is proven in  [44]. NTTTools provides functions to pre-compute the data needed for this algorithm for a polynomial. When such data is available, polynomial multiplications are done in 2n (normal) integer multiplications instead of n modular multiplications. Of course the performance of an application depends on how often the same operands are used. The encryption scheme we built over NTT-Tools, only needs to do two polynomial multiplications to encrypt, and a single polynomial multiplication to decrypt, always using the same multipliers: the secret and public keys. In the cPIR protocol, the reply is generated by constantly multiplying database element chunks with query elements. In most settings, each query element is multiplied many times by different chunks. Both the secret key and the queries use the pre-computation mechanism.
Performance and Use-Cases In this section, we analyze the performance of XPIR using two metrics: latency and user-perceived throughput. The latency measurement is the round-trip time from the moment the client starts generating the cPIR query to the moment it has finished to decrypt the reply. User-perceived throughput is the throughput (measured in bits per second) at which the user is able to get the requested element after decryption. We will consider two types of settings for our databases: static databases in which pre-processing of the database elements can be done; and dynamic databases whose contents are ephemeral (TV Streams, sensor data, etc. ) and which cannot be pre-processed ahead of time. Pre-processing is independently executed for each element at speeds that vary from 5Gbps (for a high-end laptop) to 10Gbps (for a high end server) as shown in Section 3.
2. 1. A database is thus considered static if the life-time of an element is well larger than its conversion time (e. g. 1-2 seconds for a 10Gbit movie) and the elements are known early enough with respect to the first cPIR transaction in which they will be used. Use-cases To illustrate the versatility of our library, we highlight performance values with four use-cases combining dynamic/static settings and throughput/latency goals. For high throughput applications we use a Netflixlike server (relatively static data) and a sniffer that ob-fuscates what he is interested in (dynamic data). For low latency applications we use a Match. com-like online dating database server (relatively static data) and a stock-market information service (dynamic data). Note that finding the best application for a fast cPIR protocol is beyond the scope of this paper.