dataesr/scientific-paragraphs-categorization huggingface dataset:
Experimental setting To show that our library is usable by everyone for many applications we use commodity hardware in almost all the settings. Our cPIR Server runs on a MSI GT60 laptop with a Core i7-3630QM 2. 67GHz (mobile), and 8GB of DDR3 RAM. As our library is able to process database content very fast, the data storage medium considerably influences performance, specially if this data is pre-processed. In our evaluation, we use two media: RAM (100Gbit/s access), or an OCZ Vertex 460 SSD (4Gbit/s access). The contiguous read speed of our SSD is sufficient to feed the server in all of the dynamic data settings. If data is static, we are able to process it quite faster than what a usual SSD disk can offer. If the database is in RAM this is of course not an issue, but in some applications such as the Netflix-like server, the database is huge and does not fit in RAM.
High Throughput on Static Databases High-throughput applications (i. e. applications requiring a high user-perceived reception throughput) only make sense if the database elements are big enough, if they are very small and quickly sent we consider the essential issue is latency which will be studied in Section 4. 4. We therefore consider here only databases with files going from 10Mbit and up. Our experimental results showed user-perceived throughput is independent of file sizes when they were in that range, henceforth the lines in this Figure are valid for any file size greater or equal to 10Mbit. Figure  6  shows the user-perceived throughput achieved using our library on the experimental setting laptop. The red line shows performance when no recursion is done (i. e. when query size is proportional to n).
The red filled (91 bits security) and green dash-and-dotted (256 bits security) lines give throughput when no recursion is done (i. e. database is processed as a one dimension array) and the blue dashed line with one level of recursion (i. e. database is processed as a two dimension array). The horizontal lines correspond to the needed throughput to see a movie in 1024p (2Mbps), 720p 60Hz (800Kbps) and 720p 30Hz (400Kbps), or to listen to a 128Kbps audio file. Performance on a server with a better processor (e. g. ten-core Xeon E7-4870) roughly doubles and caps at that level as RAM bandwidth is saturated. will see in Figure  7. Note that this line is pretty close to the straight line defined by 15/n Gbps (more precisely values slowly drift from 19/n Gbps to 14/n Gbps for large n values). The green line shows the same results as the red line in a higher security setting (256 bits security).
As noted previously this has almost no impact on processing but doubles the size of each ciphertext and query size (as we will see in Figure  7 ). Note that the scale is logarithmic, and thus even if the difference with the red line is very small, in this setting performance is roughly 10% worse. The blue line shows performance with one level of recursion (i. e. when the database is seen as a twodimensional √ n × √ n array and query size is proportional to 2 √ n). Recursion results in a significant computational overhead for small databases as the database is processed a first time resulting in an intermediate database of size F √ n, that we have to process again before getting the final reply. In our implementation the cost of processing this database is roughly ten times the usual cost. If √ n >> 10F computation over this intermediate database is negligible as it is small enough with respect to the initial database.
Indeed, the Figure shows that the overhead of a level of recursion fades out as n grows. Fig. 7. Initial latency before the user starts to receive streaming data (mainly due to query generation and transmission time to the server). There is no initial latency for trivial PIR. Thin lines are for ADSL and thick lines for FTTH. Colors and line styles are associated to the same settings as in Figure  6. The results highlight that latency grows linearly in n in dimension 1 and in √ n in dimension 2, and that the main bottleneck is the available upload bandwidth. Initial latency: Even if obtaining the best user-perceived throughput is the goal of an application, an important parameter is how much the user will have to wait until he starts receiving the requested stream. Figure  7  highlights the benefit of using a level of recursion for databases with many elements.
This is specially true when n ≥ 1000 as we have seen that this implies almost no computational overhead in this case. On a FTTH line, latency will be below ten seconds (if we use d=2 for n ≥ 1000). An ADSL line has limited upload bandwidth, henceforth latency ranges from 5 to 500 seconds. Therefore, in such a case, one level of recursion should definitely be used, even if it implies a significant overhead for the reply generation. The strange behaviour of the FTTH lines for a small number of elements comes from the fact that we use TCP sockets to transmit the queries and for very small time values, buffering and windowing gets in the way. It is possible to tune the low level sockets or to use UDP to have a more linear behaviour if needed. The Netflix Use-case The Netflix movie database is composed (more precisely was composed in 2009 according to the Wikipedia page for Netflix) of 100.
If the user is willing to receive a 720p-30fps video stream he can hide his choice among 35K movies from the server. Of course a computational trade-off is also possible, with 8K movies and 720p-30fps eight percent of the server's CPU is used and thus it is possible to handle 12 users per processor. Medium Access Issues: Obtaining experimental results with databases of up to 10 Gbits was simple as they fit in RAM. To obtain performance results with the largest databases, we processed them in large chunks that did fit in our RAM removing the disk transfer times for each chunk. If we use our SSD disk to access the data and take into account the transfer times, disk access is the bottleneck and thus we obtain as performance result a straight line at 2/n Gbps (our disk allows 4 Gbps access and pre-computed data is twice larger than the initial data).
In the use-case described, this would mean that the maximum amount of movies among which the choice is hidden would be reduced by a factor seven for a given resolution. We consider though that in applications requiring large databases and throughput, such as the Netflix use-case, the provider has high performance disks. In order to match the computational performance of our library it is possible to use for example two OCZ Vertex RevoDrive PCIe SSD in RAID 0 which delivers 30Gbps read throughput, at roughly a cost of 1000$. Multiple Users: Note that if data is accessed synchronously for concurrent users, disk access costs do not increase, so scalability is not an issue. Thus, if for example if 12 users hide their choice among 8K movies with quality 720p-30fps the server can access the database at just eight percent of its processing speed 15 * 8/100 = 1.
2Gbits/s so a commodity hard disk is enough. For an excellent analysis of a private Netflix use-case, the related CPU and I/O performance trade-offs, see  [48]. We also further discusses this in the conclusion. Trivial PIR over a 100Mbits/s FTTH connection (thick black line) is between five and fifty times slower than cPIR. The red line gives throughput when no recursion is done (i. e. database is processed as a one dimension array) and the blue line with one level of recursion (i. e. database is processed as a two dimension array). The horizontal lines correspond to the needed throughput to see a movie in 1024p (2Mbps), 720p-60fps (800Kbps) and 720p-30fps (400Kbps), or to listen to a 128Kbps audio file. Performance on a server with a better processor (e. g. ten-core Xeon E7-4870) can be two to three times higher.
High Throughput on Dynamic Data At first sight, dynamic databases are similar to static ones apart that data cannot be pre-processed offline, such as it is the case with IPTV for example. However, they can have a large span of shapes and contents and are not always a simple extension of static databases to "infinite size" files. An exhaustive analysis of dynamic databases is beyond the scope of this paper, but we show two different settings : IPTV and a private sniffer. The first setting is pretty simple : usual data streams that cannot be pre-processed such as for IPTV. Figure  8  presents the same results as 6 but with dynamic data. As one can see, the user-perceived throughput is roughly divided by six. For an IPTV like application, a single processor can handle one hundred 720p-30fps streams for 50 simultaneous clients (e.
g. classical TV), or five thousand such streams for a single client (e. g. a large set of distant IP web cameras). The second setting is more tricky, as the dynamic data elements are most of the time null, and the non nulls can be very small. We describe this setting in our second use-case. The Private Sniffer Use-Case In this use-case we suppose someone creates a sniffer that stores all the packets that have a given source IP address, but wants to ensure that nobody that would find the sniffer and analyze its code could learn which IP the sniffer is inter-ested in. Of course, it is possible to store every message (as with trivial PIR) but, as described in Section 2. 3, using cPIR the storage is much more compact. With this approach, a cPIR query is generated and each query element is associated to a given source IP.
For every packet the sniffer intercepts, he builds a database such that each query element is associated to a null element, except the query element corresponding to the source IP of the intercepted packet which is associated to the packet. Then the sniffer generates a cPIR reply storing the reply in the disk using the compression techniques described in Section 2. 3. The dynamic database is thus pretty special as it is almost null and the element to process will be often much smaller (between 320 bits and 12Kbits) than what can be absorbed in a ciphertext (roughly 20Kbits for the smaller parameters and 90Kbits for the larger ones). A trivial implementation will thus not use all the power our library can provide in other settings. The red line in Figure  9  gives the throughput at which the sniffer is able to process the intercepted packets.
Latency on Static/Dynamic Databases In this Section, we want to evaluate XPIR latency, i. e. round trip time (RTT), in settings where data is static or dynamic. Figure  10  shows the RTT achieved with static data and Figure  11  with dynamic data. The x-axis represents the size of the database ranging from 1Mb to 1Tb. The green line shows the request processing time (RP), the red line shows the RTT with no network (i. e. the client on the same machine as the server), and the various blue lines represent the RTT with a FTTH network for different values for n. While, when considering throughput, the request processing and data importation were the most striving parameters, when looking at RTT, performance results of a balance between reply processing time and upload/download times. It is very important to note that usual techniques in cPIR such as aggregation and recursion (see Section 2.
2) are mandatory to keep RTT low. In Figure  10  we used parameters (1024, 60) for the Ring-LWE cryptosystem and thus query element size is 128Kb and F 6. For n = 10000 and l = 1M b, if no aggregation and no recursion is used, sending the query (10000 * 128Kb) over the FTTH link takes 12. 8 seconds and sending the reply (6*1Mb) takes 0. 06 seconds while generating the query (at 2. 2 Gbps) takes 0. 05 second, processing it (at 10 Gbps) takes 0. 1 second and decrypting the reply (at 5. 6Gbps) takes about 1ms. Using recursion divides query sending time by a factor 50 and has little impact on the other times so it is clearly beneficial. Using aggregation and recursion, when beneficial, the optimizer can set the cPIR parameters in order to transform the shape of a database with a high n value into a database with a smaller n.
This is why, on both Figures, the higher is n the lower is the RTT. Indeed, the shape of the database is transformed in order to lower this parameter if a smaller n is more favorable. As one can observe, the high n lines tend to approach the RTT limit which is the RP line. The only difference between static and dynamic databases lies in the request process- ing speed that is impacted by the need to pre-process the data in the dynamic case. One can observe the different values of request processing (red dashed lines on both Figures). Henceforth, with dynamic databases, the high n lines will tend towards the RP line later, i. e. with larger databases. This implies that in most networked situations RTT will be similar for static and dynamic databases, except for the largest ones.
Match. com Use-Case In this use-case we consider that an online dating database server wants to provide a paying private keyword search mechanism to its clients. When using this system, users can define some public criteria, such as the city in which they would like to meet people (which is anyways probably revealed by their IP). This set of public parameters will reduce the database size over which a second search, based on private criteria, will be done. Fig. 11. Round-trip (RTT) and request processing (RP) times of XPIR serving dynamic data on a MSI GT60 laptop with a Core i7-3630QM 2. 67GHz on a FTTH network (database sizes are in bits). Trivial PIR has been masked for clarity as the same remarks as most comments on Figure  10  also apply. As data is not already pre-processed, request processing time is higher, but upload/download times do not change.
This explains why blue lines are almost identical except for the fact that the gap to reach ideal RTT is smaller. In practice this implies that RTT is not affected much by pre-processing except for very large databases. pose that the average profile has five keywords, using the RTT given in Figure  10  a user would have to wait for ten minutes before having a reply which is probably too much for a web experience. Using the public keyword pre-filtering we described we can hope to divide the size of the database by a factor 10 to 100 (if users are distributed in various cities and public keywords are specific enough) which would lower the waiting time to 6-60 seconds, a much more reasonable time for a search. Of course if we consider Match. com 5 Millions users (according to Wikipedia's page which cites 2014 sources) and profiles of multiple megabytes, public filtering will have to be much more efficient.
Other cryptosystems As noted before, in almost all situations the Ring-LWE based cPIR is chosen by the optimizer, as it gives the best results. In some extreme cases however, the optimizer chooses to do a Paillier based cPIR or a trivial (full-database download) PIR. The Paillier based cPIR will be chosen for extremely small bandwidths in which case the cPIR reply generation throughput is not important as most of time is spent sending the reply and reply expansion factor is the most important parameter. On the opposite side, trivial PIR will be of course the natural choice when available bandwidth is higher than our database processing throughput. The limit should therefore be not very far of 20Gbps for static pre-processed databases, and 5Gbps for dynamic databases. Other extreme settings in which trivial PIR will be the natural choice exist.
An example is for database with two to four elements. In this case a cPIR reply with our Ring-LWE scheme will be larger than the database itself due to our encryption scheme's expansion factor. Another example is for very small databases in which query size may be larger than database size. For example, using an ADSL connection (1Mbps upload / 20Mbps download) on a 10Mbit database with ten elements, sending a Ring-LWE query will take at least 1 second, whereas the full database download only needs half a second (note that using aggregation to reduce query size does not solve the issue). Of course, such settings may in some situation correspond to real life situations, but only scarcely.
Conclusion Lattice based cryptography brought groundbreaking advances on worst-case to average-case reductions and on fully-homomorphic encryption. However it has been for a long time seen as impractical, despite its excellent asymptotic results. This field of research has matured a lot. The arrival of the ideal lattice setting, and the development of many performance tweaks has completely changed attainable performances in a non-asymptotic sense. cPIR has often been considered as an impratictal protocol  [1]  but lattice-based cryptography brings a real overhaul on this, as cPIR becomes feasible even without a high-end server. We have shown that our protocol can be used to process a wide range of databases in a few seconds, even for 100Gb databases. These experiments would have taken thousands of seconds with a number theory cryptosystem as Paillier, which would have processed the database at 1Mbit/s.
Sending the database, even over a 100Mbit/s link would have increased by a factor one hundred the times we presented in our experiments. The results presented in this paper were obtained on a commodity laptop, using a high end server in a multi-core setting can only increase this difference further. However this is not our purpose, what we wanted to highlight is that lattice-based cryptography has transformed the utterly impractical into something feasible by everyone. As we want to show that it is feasible by everyone, we have included the auto-optimize tools that will allow anybody to use our library without being an expert on cryptography. We are eager to hear from these people's experiences. Finally it is important to note that even if we have shown that cPIR can be used with very large databases, in practice, as databases grow, cPIR can be used as a building block combined with other techniques to improve scalability.
A Algorithms Algorithms for the PIR client-server protocol ) the optimizer may have to do a lot of tests before reaching the best result. To lower the amount of tests we used a convexity assumption to do a dichotomy when looking for the best α. When α grows, query size is reduced and reply size increased. Using this monotony it is reasonable to assume that the target functions we use are close to convex. In practice the optimizer always returned very reasonable results and was able to run in a few milliseconds for any database.
Performance cache generation (Client and Server):Input: Set of parameters for encryption schemes Output: Set of performance results for these parameters 1. Client: For each set of parameters of each encryption scheme -Evaluate encryption and decryption throughput -Store the resulting values for this set of parameters 2. Server: For each set of parameters of each encryption scheme -Evaluate precomputation and reply generation throughput -Store the resulting values for this set of parameters Optimization (Client and Server): Input: Recursion range (d 1 , d 2 ), Aggregation range (α 1 , α 2 ), potential encryption parameters list EncParams, upload/download usable bandwidth (U, D), target optimization function ftarget Output: Best crypt and PIR parameters taking ftarget as a measure 1. Server: Send optimization information -The database shape (n and ) -The server performance cache 2.
Client: If U or D are null do a bandwidth test to redefine them 3. Client: Optimize For every encryption scheme parameters in EncParams For every dimension d between d 1 and d 2 For every aggregation value α between α 1 and α 2 -Estimate queryGenerationTime with the performance cache -Estimate querySendingTime with the upload bandwidth -Estimate replyGenerationTime with the performance cache -Estimate replySendingTime with the download bandwidth -Estimate replyDecryptionTime with the performance cache -Give a performance measure applying ftarget to these values 4. Client: Output the parameters with the best performance measure Choice (Client and Server): Input: Database Output: Index of the element chosen by the user 1. Server: For each file send a description and an associated index or a global description of the set of files 2.
Client: Present the catalog to the user, and return the chosen index Query generation (Client): Input: PIR parameters (n, , α, d), crypto parameters Enc. Params, chosen index i Output: Query 1. Redefine n = ceil(n/α) and note n 1= • • • = n d = ceil(n 1/d ) 2. Define (i 1 ,. , i d ) the decomposition in base ceil(n 1/d ) of i 3. For j in [1. d] generate a query Q j with the Basic cPIR protocol for retrieving an element of index i j in a database of n j elements using an encryption scheme based on Enc. Params4. Return Q = (Q 1 ,. , Q d )Reply generation (Server):Input: PIR parameters (n, , α, d), crypto parameters Enc. Params, query (Q 1 ,. , Q d ), database elements (db 1 ,. , dbn) Output: PIR reply 1. Redefine n = ceil(n/α) and note n 1 = • • • = n d = ceil(n 1/d ) 2. For j ∈ [1. n]redefine b j as the aggregation of db jα+k for k ∈ [1.
α] 3. For j ∈ [1. n] -Note (j 1 ,. , j d ) the decomposition of j in base ceil(n 1/d ) -Define db (j 1 ,. ,j d ) = db j 4. For j ∈ [1. d] For each tuple (i j+1 ,. , i d ) in [1. n j+1 ] × • • • × [1. n d ] -Compute using the cPIR basic algorithm a PIR reply using (db (1,i j+1 ,. ,i d ) ,. , db (n j ,i j+1 ,. ,i d ) ) as a database and Q j -Define with this PIR reply db (i j+1 ,. ,i d ) if j < d or RES if j = d 5. Return RES Reply extraction (Client): Input: PIR parameters (n, , α, d), crypto parameters Enc. Params, chosen index i, PIR reply Output: Element of index i in the database 1. Decrypt the d encryption layers of the reply to get α elements 2. Return the element corresponding to index i and drop the others Remark (convexity): If α 1 = 1, α 2 = n and n is large (say 10 9.
encryption parameters list EncParams, upload/download usable bandwidth (U, D), target optimization function ftarget, index of the element to retrieve i (pot. undefined), boolean serverDriven Output: Chosen database element 1. If serverDriven is true -Server: Send mandatory parameters to the client -Client: Check if the parameters give enough security -Jump to step 4 2. If performance results do not exist for all parameters in EncParams -Client and Server: Run the Performance cache algorithm → Performance results 3. If multiple PIR and encryption parameters are possible given the input constraints -Client and Server: Run the Optimization algorithm Else use the only possible choice → Optimal parameters for this setting given the constraints 4.
Trivial PIR (from top to bottom the second filled line) is faster than cPIR for databases under ten elements, which is natural as cPIR has a reply expansion factor around five. For databases with more elements, cPIR can be up to fifty times faster. When the client is local, RTT (red thick dashed line) matches RP (green thick filled line), specially for large databases. Each thin blue line gives RTT for a fixed n and varying database sizes. For large databases reply size is the limiting factor, which explains why performance is closer to ideal RTT as n grows (when n grows for a fixed database size shrinks). For small databases, query size is the limiting factor. RTT does not grow as fast as n because the optimizer uses aggregation.
The users can then do a cPIR-based keyword search (see Section 2. 3) to get the profiles matching a set of private keywords. If we suppose the database has one million profiles, each of one megabit, the complete database will be of one Terabit. We must also take into account that each profile may match a set of keywords and that reply generation costs are multiplied by the average number of matching keywords in a private keyword search. If we sup-.