How efficient is it now? The last time I checked, FHE required minutes of computation and gigabytes of memory to store tiny amounts of data, and since it does not hold IND-CCA, I could not find any use cases.
Very inefficient. Like wildly so. Specifically if you have a very small database and you preprocess it with their techniques, the resulting database is petabytes in size. But the results are very beautiful.
There are no obvious ways to improve on this work, so it is not a matter of engineering. We really do need another breakthrough result to get us closer to practicality.
Pretty efficient! E.g. a recent paper describes a system to do fully private search over the common crawl (360 million web pages) with an end to end latency of 2.7 seconds: https://dl.acm.org/doi/10.1145/3600006.3613134
The benchmarks listed there are approximately 100 times slower than the original Intel 8088 microprocessor released 1979 on which the original IBM PC was based.
That microprocessor was efficient enough for many applications of general purpose computing, but we still need Moore's law to give us a 100-fold increase in compute power to reach this level.
This level of performance seems comparable to (and IMHO slower than) the very first electronic stored-program computer, the 1948 Manchester Baby.
Not an answer, but a question that I hope someone can answer. Is the lack of speed because of a lack of optimization or compute? Is this something that could be fixed by an accelerator?
It's often hard to compare things in an accurate way. I mean many current methods might already have hardware specific acceleration and researchers aren't always good at optimization (why should they be?). So is the problem of FHE a bigger lack of just not enough people (specialists) putting in time to optimize it or is it so computationally intensive that we need hardware to get better before it becomes practical? I mean look at llama.cpp and how much faster it is or stable diffusion? Sure, both kinda slow (diffusion's no GAN and SD's not straight diffusion) but very usable for many applications.
Based on my recollection of a conversation with the authors after their STOC talk: the RAM scheme is not efficient enough to be competitive with circuit-based FHE schemes; for problems with low RAM usage, existing circuit-based methods are more efficient, and problems with higher RAM usage are infeasible to run on any FHE method right now.
They were 50/50 on whether or not this technique could be made feasible in the same way that, say, the CKKS scheme is.
I remain unconvinced of the practical applications of solutions like this.
These seem like academic toys.
Pre-processing a dynamic database is a non-starter. No database that is used for any real world use case is static at scale, especially not internet traffic.
I’m not expecting FHE that’s fast in my lifetime, but I’ve been wrong before.
Context: I led a team which built the first open source production-grade implementation of hardware-accelerated PIR which is currently at use at scale.
I don't think the purpose of this sort of research is to be immediately applicable, it more shows a direction that could be useful in the future. Shor's algorithm has not been used practically, but it's hard to imagine modern cryptography without "post quantum" being an important topic.
I think you are right that this paper isn't practically useful. But that is much like saying that making one chip off of a block of granite isn't art. It isn't, but the first chip enables further research until it is practical.
The first time I can across PIR was via the 2014 blog post from Signal on how Private Contact Discovery was a hard problem and how it required PIR to be solved. https://signal.org/blog/contact-discovery/
Maybe this will help Signal get to a viable solution in a few years.
> Unfortunately, for a reasonably large user base, this strategy doesn’t work because the bloom filters themselves are too large to transmit to mobile clients. For 10 million TextSecure users, a bloom filter like this would be ~40MB, requested from the server 116 times a second if every client refreshes it once a day.
They decided to run computations inside a 'secure' hardware environment instead (SGX specifically) so that they can't get access to the computation themselves but it also doesn't need to be run client side. I assume you meant the former thing, but the approach they actually use is fundamentally different from homomorphic encryption / PIR.
I know of the concept of zero-knowledge proofs, but didn't know that the blockchain industry advanced cryptography a lot in that area. What are the practical applications of those new things? Or which new things are there to begin with? The Wikipedia article on zero-knowledge proof doesn't seem to say
> But using their private lookup method as scaffolding, the authors constructed a new scheme which runs computations that are more like the programs we use every day, pulling information covertly without sweeping the whole internet.
Doesn’t Google already accomplish this? Or is the key here that Google doesn’t do the sweeping in a covert way? So search boils down to two problems: building the index and using the index.
It understand it's inefficient, but could it be used by a well-resourced organization where confidentiality is extremely high-value and the database is small, such as intelligence, military plans, Apple's product plans, etc.?
How do people with pen and paper operate on 10k pieces of data? Which is honestly a rather small number. There's a reason we use computers and why statistics accelerated after its invention.
You run Google’s algorithm yourself and secretly pull data from the internet when necessary.
yeah isn't this the same offline viewing? why do you need a new algorithm for that? we've known about this forever. obviously, if you download the database and access it, this is more secure than being online , but way slower. Regarding the library example, this too has easy solutions: checkout many books at once, have a stranger check out the book, etc.
This article seems to do a poor job explaining what exactly this solves, only that it's revolutionary. The metaphors are not helpful.
How I interpreted this is that you download the google search algorithm, then scan their database over the internet with that algorithm. Which would take ages or millenia depending on how much data google has.
You wouldn't need to download the entire database and there would be alot of uncertainty over which search result you'd actually used.
so, not private nor efficient nor solution to homomorphic data.
basically a polynomial factor hash of the index keys... basically you will need the entire db plus the larger hashed keys. doesn't help at all implementing any of the outlandish claims.
guess the merit is in proving the poly fact they build on as secure. but that is not a game changer as there are better alternatives and nobody solved the claimed problems with them.
Readit News
Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
https://eprint.iacr.org/2022/1703
Dead Comment
There are no obvious ways to improve on this work, so it is not a matter of engineering. We really do need another breakthrough result to get us closer to practicality.
That microprocessor was efficient enough for many applications of general purpose computing, but we still need Moore's law to give us a 100-fold increase in compute power to reach this level.
This level of performance seems comparable to (and IMHO slower than) the very first electronic stored-program computer, the 1948 Manchester Baby.
It's often hard to compare things in an accurate way. I mean many current methods might already have hardware specific acceleration and researchers aren't always good at optimization (why should they be?). So is the problem of FHE a bigger lack of just not enough people (specialists) putting in time to optimize it or is it so computationally intensive that we need hardware to get better before it becomes practical? I mean look at llama.cpp and how much faster it is or stable diffusion? Sure, both kinda slow (diffusion's no GAN and SD's not straight diffusion) but very usable for many applications.
No.
>Is this something that could be fixed by an accelerator?
No.
They were 50/50 on whether or not this technique could be made feasible in the same way that, say, the CKKS scheme is.
These seem like academic toys.
Pre-processing a dynamic database is a non-starter. No database that is used for any real world use case is static at scale, especially not internet traffic.
I’m not expecting FHE that’s fast in my lifetime, but I’ve been wrong before.
Context: I led a team which built the first open source production-grade implementation of hardware-accelerated PIR which is currently at use at scale.
Can you tell us more about that?
Maybe this will help Signal get to a viable solution in a few years.
> Unfortunately, for a reasonably large user base, this strategy doesn’t work because the bloom filters themselves are too large to transmit to mobile clients. For 10 million TextSecure users, a bloom filter like this would be ~40MB, requested from the server 116 times a second if every client refreshes it once a day.
They decided to run computations inside a 'secure' hardware environment instead (SGX specifically) so that they can't get access to the computation themselves but it also doesn't need to be run client side. I assume you meant the former thing, but the approach they actually use is fundamentally different from homomorphic encryption / PIR.
Doesn’t Google already accomplish this? Or is the key here that Google doesn’t do the sweeping in a covert way? So search boils down to two problems: building the index and using the index.
Or am I confused?
yeah isn't this the same offline viewing? why do you need a new algorithm for that? we've known about this forever. obviously, if you download the database and access it, this is more secure than being online , but way slower. Regarding the library example, this too has easy solutions: checkout many books at once, have a stranger check out the book, etc.
This article seems to do a poor job explaining what exactly this solves, only that it's revolutionary. The metaphors are not helpful.
You wouldn't need to download the entire database and there would be alot of uncertainty over which search result you'd actually used.
basically a polynomial factor hash of the index keys... basically you will need the entire db plus the larger hashed keys. doesn't help at all implementing any of the outlandish claims.
guess the merit is in proving the poly fact they build on as secure. but that is not a game changer as there are better alternatives and nobody solved the claimed problems with them.