96 research outputs found
Improved Range Searching And Range Emptiness Under FHE Using Copy-And-Recurse
No full textRange counting is the problem of preprocessing a set of points, such that given a query range we can efficiently compute . In the more general range searching problem the goal is to compute , for some function .
It was already shown (Kushnir et al. PETS\u2724) how to efficiently answer a range searching query under FHE using a technique they called Copy-and-Recurse to traverse partition trees.
In the Range emptiness problem the goal is to compute only whether . This was shown (in plaintext) to be done more efficiently.
Range emptiness is interesting on its own and also used as a building block in other algorithms.
In this paper we improve and extend the results of Kushnir et al.
First, for range searching we reduce the overhead term to the optimal , so for example if the ranges are halfspaces in bounded by hyperplanes then range searching can be done with a circuit of size , where is the size of the sub-circuit that checks whether a point lies under a hyperplane.
Second, we introduce a variation of copy-and-recurse that we call leveled copy-and-recurse. With this variation we improve range searching in the 1-dimensional case as well as traversal of other trees (e.g., binary trees and B-trees).
Third, we show how to answer range emptiness queries under FHE more efficiently than range counting.
We implemented our algorithms and show that our techniques for range emptiness yield a solution that is faster than the previous results for a database of points
Honorary Members of the Polish Society of Nephrology. Part X — Professor Shaul G. Massry
No full textNiniejsza publikacja jest już dziesiątą częścią serii Członkowie Honorowi Polskiego Towarzystwa Nefrologicznego, którą autorzy przedstawiają na gościnnych łamach „Forum Nefrologicznego” od początku 2013 roku. Warto przypomnieć, że dotychczas zaprezentowano życiorysy dziewięciu Członków Honorowych, z czego sześciu pochodzi z Polski, a trzech z Niemiec, Stanów Zjednoczonych i Francji. Pierwszą postacią był prof. Tadeusz Orłowski, a w ostatnim numerze zaprezentowano postać niespodziewanie i przedwcześnie zmarłego prof. Olgierda Smoleńskiego. W obecnym numerze przyszedł czas na przedstawienie postaci Profesora Shaula Massry, znanego na całym świecie internisty i nefrologa, autora setek oryginalnych publikacji i wydań książkowych, członka honorowego wielu narodowych towarzystw naukowych, doktora honoris causa licznych uczelni medycznych na wielu kontynentach, redaktora wielu renomowanych czasopism medycznych, zwłaszcza nefrologicznych. Profesor Shaul Massry wielokrotnie przebywał w Polsce na zaproszenie wielu uczelni medycznych i Polskiej Akademii Nauk, biorąc udział w konferencjach naukowych. W klinice Profesora w Stanach Zjednoczonych przebywali też na stażach naukowych liczni młodzi polscy lekarze. Między innymi z tego powodu można Profesora nazwać przyjacielem Polski i polskich lekarzy.This is the tenth publication in the series of the Honorary Members of the Polish Society of Nephrology which has been kindly hosted by Forum Nefrologiczne since the early 2013. The nine Honorary Members presented so far have included six figures from Poland and three from Germany, the USA and France. The series was opened with the biographical sketch of prof. Tadeusz Orłowski and its latest part depicted prof. Olgierd Smoleński. This issue offers a chance to present the figure of Professor Shaul Massry, the world-famous internist and nephrologist, the author of hundreds of original publications and books, the honorary member of numerous national scientific societies, the doctor honoris causa of many medical universities on various continents, the editor of many renowned medical journals, especially in the field of nephrology. Having been invited by many medical universities as well as the Polish Academy of Sciences Professor Shaul Massry was frequent visitor in Poland participating in many scientific conferences. His clinic hosted many young Polish doctors as trainees. For these reasons and others not mentioned here it is justified to call Shaul Massry a friend of Poland and Polish doctors
Improved Construction of Vertical Decompositions of Three-Dimensional Arrangements
No full textWe present new results concerning the refinement of three-dimensional arrangements by vertical decompositions. First, we describe a new output-sensitive algorithm for computing the vertical decomposition of arrangements of n triangles in O(n log n + V log n) time, where V is the complexity of the decomposition. This improves significantly over the best previously known algorithms. Next, we propose an alternative sparser refinement, which we call the partial vertical decomposition and has the advantages that it produces fewer cells and requires lower degree constructors. We adapt the output-sensitive algorithm to efficiently compute the partial decomposition as well. We implemented algorithms that construct the full and the partial decompositions and we compare the two types theoretically and experimentally. The improved output-sensitive construction extends to the case of arrangements of n well-behaved surfaces with the same asymptotic running time. We also extended the implementation to the case of polyhedral surfaces -- this can serve as the basis for robust implementation of approximations of arrangements of general surfaces
Ray shooting and stone throwing with near-linear storage
No full textAbstractThe paper presents two algorithms involving shooting in three dimensions. We first present an algorithm for performing ray shooting amid several special classes of n triangles in three dimensions, including sets of fat triangles, and sets of triangles stabbed by a common line. In all these special cases, our technique requires near-linear preprocessing and storage, and answers a query in O(n2/3+ɛ) time. This improves the best known result of O(n3/4+ɛ) query time (with near-linear storage) for general triangles. The second algorithm handles stone-throwing amid arbitrary triangles in 3-space, where the curves along which we shoot are vertical parabolic arcs that are trajectories of stones thrown under gravity. We present an algorithm that answers stone-throwing queries in O(n3/4+ɛ) time, using near linear storage and preprocessing. As far as we know, this is the first nontrivial solution of this problem. Several extensions of both algorithms are also presented
Secure k -ish Nearest Neighbors Classifier
No full textAbstract
The k-nearest neighbors (kNN) classifier predicts a class of a query, q, by taking the majority class of its k neighbors in an existing (already classified) database, S. In secure kNN, q and S are owned by two different parties and q is classified without sharing data. In this work we present a classifier based on kNN, that is more efficient to implement with homomorphic encryption (HE). The efficiency of our classifier comes from a relaxation we make to consider κ nearest neighbors for κ ≈k with probability that increases as the statistical distance between Gaussian and the distribution of the distances from q to S decreases. We call our classifier k-ish Nearest Neighbors (k-ish NN). For the implementation we introduce double-blinded coin-toss where the bias and output of the toss are encrypted. We use it to approximate the average and variance of the distances from q to S in a scalable circuit whose depth is independent of |S|. We believe these to be of independent interest. We implemented our classifier in an open source library based on HElib and tested it on a breast tumor database. Our classifier has accuracy and running time comparable to current state of the art (non-HE) MPC solution that have better running time but worse communication complexity. It also has communication complexity similar to naive HE implementation that have worse running time.</jats:p
Secure Data Retrieval on the Cloud: Homomorphic Encryption meets Coresets
No full textSecure report is the problem of a client that retrieves all records matching specified attributes from a database table at the server (e.g. cloud), as in SQL SELECT queries, but where the query and the database are encrypted. Here, only the client has the secret key, but still the server is expected to compute and return the encrypted result. Secure report is theoretically possible with Fully Homomorphic Encryption (FHE). However, the current state-of-the-art solutions are realized by a polynomial of degree that is at least linear in the number m of records, which is too slow in practice even for very small databases. We present the first solution that is realized by a polynomial that attains degree independent of the number of records m, as well as the first implementation of an FHE solution to Secure report. This is by suggesting a novel paradigm that forges a link between cryptography and modern data summarization techniques known as coresets (core-sets), and sketches in particular. The key idea is to compute only a coreset of the desired report. Since the coreset is small, the client can quickly decode the desired report that the server computes after decrypting the coreset. We implemented our main reporting system in an open source library. This is the first implemented system that can answer such database queries when processing only FHE encrypted data and queries. As our analysis promises, the experimental results show that we can run Secure report queries on billions records in minutes on an Amazon EC2 server, compared to less than a hundred-thousands in previous FHE based solutions
Secure Search via Multi-Ring Fully Homomorphic Encryption
No full textSecure search is the problem of securely retrieving from a database table (or any unsorted array) the records matching specified attributes, as in SQL ``SELECT...WHERE...\u27\u27 queries, but where the database and the query are encrypted. Secure search has been the leading example for practical applications of Fully Homomorphic Encryption (FHE) since Gentry\u27s seminal work in 2009, attaining the desired properties of a single-round low-communication protocol with semantic security for database and query (even during search). Nevertheless, the wide belief was that the high computational overhead of current FHE candidates is too prohibitive in practice for secure search solutions (except for the restricted case of searching for a uniquely identified record as in SQL UNIQUE constrain and Private Information Retrieval). This is due to the high degree in existing solutions that is proportional at least to the number of database records m.
We present the first algorithm for secure search that is realized by a polynomial of logarithmic degree (log m)^c for a small constant c>0. We implemented our algorithm in an open source library based on HElib, and ran experiments on Amazon\u27s EC2 cloud with up to 100 processors. Our experiments show that we can securely search to retrieve database records in a rate of searching in millions of database records in less than an hour on a single machine.
We achieve our result by:
(1) Designing a novel sketch that returns the first strictly-positive entry in a (not necessarily sparse) array of non-negative real numbers; this sketch may be of independent interest.
(2) Suggesting a multi-ring evaluation of FHE -- instead of a single ring as in prior works -- and leveraging this to achieve an exponential reduction in the degree
- …
