Show HN: Read Wikipedia privately using homomorphic encryption

This is the first thing out of homomorphic encryption <i>I personally have seen</i> that seems to be in the ballpark of useful for some practical use, which is impressive. Have I missed out on any other such things of interest?<p>(And this is not a criticism; this is a compliment. You start so far behind the eight-ball with homomorphic encryption with regard to the resources it consumes I wasn&#x27;t convinced it was ever going to be even remotely useful for much of anything. Precisely because I was so skeptical, I am that impressed to see something work this well. It&#x27;s not the fastest Wikipedia mirror, but... honestly... I&#x27;ve been on slower websites! Websites with <i>far</i> less excuse.)

Interesting! But, it&#x27;d be helpful to clarify further the strength of the following claim:<p><i>&gt; This demo allows private access to 6 GB (~30%) of English Wikipedia. In theory, even if the server is malicious, it will be unable to learn which articles you request. All article title searches are performed locally, and no images are available.</i><p>In this demo, the number of article-titles is relatively small – a few million – &amp; enumerable.<p>If the server is truly malicious, and it issues <i>itself</i> requests for every known title, does it remain true that this &quot;Private Information Retrieval&quot; (PIR) scheme still gives it <i>no</i> hints that subsequent requests from others for individual articles retrieve particular data?<p>(Presumably: <i>every</i> request touches every byte of the same full 6GB of data, and involves every such byte in constant-run-time calculations that vary per request, and thus have the effect of returning only what each request wanted – but not at all in any way correlatable with other requests for the exact same article, from the same or different clients?)

Can this be applied usefully to non-public datasets?<p>Would it be feasible to add some other zero knowledge proof to this that would confirm a user has paid a subscription for access? For example, if this were a news site, the user would have to prove a valid subscription to read articles, but the site would not be able to know which articles any subscriber decided to read?<p>If that is possible, what could the site to to prevent a paying subscriber from sharing their access to an unreasonable number of others? Would it be possible to impose a rate limit per subscriber?

In another comment you’ve said:<p>&gt; With a proper implementation of PIR, the server still needs to scan through the entire encrypted dataset (this is unavoidable, otherwise its I&#x2F;O patterns would leak information)<p>Is this technique therefore practical only when the server side dataset is relatively small (or full scans for every query are tolerable)?<p>(edit: sorry, misattributed the quote)

Could this be used for DNS?

Last year, there was a detailed presentation with several speakers on state of the art Secure Multi-Party Computation for practical applications in healthcare, fighting financial crime and machine learning from CWI (Centrum Wiskunde &amp; Informatica) Netherlands. The recording is here (2,5h): <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=gE7-S1sEf6Q" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=gE7-S1sEf6Q</a>

&gt; A malicious server is unable to determine which article the client retrieved.<p>This sounds like magic :O. How does it behave when new articles (elements) are added, does it need to rebuild the whole database and distribute new parameters?<p>I wonder how practical it would be for clients to synchronize content without server not being able to deduce the synchronization state at which the client is.

Does homophobic in this case mean that I can edit the content of an article and the diff is directly applied to the crypt?

What is the maximum throughput the server can maintain? Or, in other words, how much does it cost per query?

Extremely cool. Now we can serve content without any ability to observe what people are being served exactly. I was hoping that someday soon such technology could be used to serve search results and give us a <i>truly</i> private search engine experience.

Theoretically, can this scheme be turned into a generic O(N) key-value retrieval for non-static content (in this example — supporting adding, removing and replacing articles without re-encrypting the whole database and re-sending the client setup data)?

Not able to read the full paper at the moment, and confused about something:<p>If the server needs to go pull the article from Wikipedia, how is it blind to which one is being requested?<p>If you&#x27;ve pre-seeded the server with an encrypted 30% of Wikipedia, how can I trust you haven&#x27;t retained information that would enable you to derive what I requested?<p>The only way I understand this works is if the client itself seeded the encrypted data in the first place (or at least an encrypted index if all the server pushes back is article numbers).<p>Maybe I&#x27;m ignorant of something; if so thanks for ELI5.

Can this functionality be implemented as a peer-to-peer (or federated) service?<p>I&#x27;m assuming it&#x27;ll depend on breaking down questions into hierarchical sub-questions that can either be recomposed locally or in another homomorphic context. But can that sort of thing be done without data-leaks, or prohibitively expensive inter-node communication?<p>Are there any introductory resources (that you know of) on homomorphic encryption and compute that&#x27;ll turn this into less of a mind-fuck?

I understand that you do some kind of dot product (with two steps, Regev and GSW). However, it looks to me that those steps involve fixed dimension vectors.<p>- How do you handle variable length data? Do you need to pad it?<p>- What is the memory overhead of the storage of encrypted data?<p>I think that at least for video data, the streaming scheme &quot;leaks&quot; the size of the encrypted data with the number of streaming packets.

If you say a malicious server can&#x27;t determine which article was retrieved, is that private information retrieval (PIR)? Something must be different here. I thought there was a theorem that for single-server PIR to work, the client has to download the entire DB, which is the right way to read Wikipedia privately anyway.

Do you have a blog or Twitter? I&#x27;d like to keep up with any other cool projects you&#x27;re working on!

I wonder if this can be done on sqlite?<p><a href="http:&#x2F;&#x2F;static.wiki&#x2F;" rel="nofollow">http:&#x2F;&#x2F;static.wiki&#x2F;</a><p>See the previous news article. <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=28012829" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=28012829</a>

Fantastic project.<p>Have you considered running (# of cpus) parallel scanners continuously? An inbound query “hops on” the the least-loaded scanner; at each article&#x2F;chunk the scanner runs all the queries; each query “hops off” and returns after it has completed the cycle through the entire DB.

Well but you get into the security space and license your server db technology for shit like IoT lights. I don&#x27;t want the company knowing if my lights are on or off, but if they had a homomorphic encrypted backend and app, I might trust it.

This is wonderful! I&#x27;ve never seen anything like this in practical form.<p>I hope it doesn&#x27;t become standard practice for general websites(As I imagine some would like to see), but it&#x27;s an amazing tool and there will probably be many wonderful uses.

This kind of stuff gives some of the best arguments for open source software (OSS) to date. Otherwise, it has to be taken completely on faith, which then defeats nearly the entire purpose and makes the performance overhead untenable.

&gt; As a real product, you’d probably want to distribute a signed client executable (or Electron app) since otherwise, a malicious server could simply deliver bad client JS on the fly.<p>Arguably, a malicious server could deliver a bad executable too.

Idea: Apply this to personalized advertising. Client sends his interests + habits + personal info encrypted to the server. Server finds and sends back to client the best ad based on clients info.

Can anyone recommend an explanation of this concept geared towards people with only a superficial knowledge of encryption?<p>This seems to be some kind of search applied on an encrypted dataset, is that right?

Very nice! Great against snoopers that lack authority but for when they do have some authority (bosses, government) without plausible deniability it can do more harm than good.

This sounds like the ultimate anti-user profiling and targeted advertising solution. I hope google and other advertising giants can’t stop this. Thoughts?

This is very cool OP! I interviewed to be a privacy engineer with Wikimedia a while back.<p>I suggested that my goal would be to add a v3 onion service. They actually had listed years of &quot;homomorphic encryption&quot; as a requirement. I phoned up the recruiter and basically said it&#x27;s ok if there is a personality conflict, but the role as written was impossible to fill, and it scared me that very good suggestions for privacy as well as the health of the Tor network were discarded.<p>(If you set up a dot onion, that frees up traffic on exit nodes, whose capacity are limited.)<p>Big thanks to the OP for being willing to share this work, it&#x27;s very cool and I&#x27;m about to read your eprint.<p>I&#x27;m excited about the potential of homomorphic encryption, though I worry about things like CPU cost -- I recall when folks had to really be nudged not to encrypt huge blocks of data with PGP, but instead use it to encrypt the passphrase to a Truecrypt volume using a symmetric cipher like AES.<p>(I&#x27;d love how to know we got to a point Twitter added an onion service then banned me, but Wikipedia continues to not even support MFA for logins -- I recently registered an account intending to eventually upload some art to the commons, but the perpetual refusal to allow folks to make healthy choices disturbs me.<p>In fact, after reading articles like these ones[1][2], it makes me question the integrity of the folks I interacted with during the interview process.<p>On my end, it was especially disturbing since prior to enrolling in my PhD, the alternative path I discussed was becoming an FBI agent focused on counter intelligence in the &quot;cyber&quot; realm.<p>The agent I spoke with told me I&#x27;d serve &quot;at the needs of the bureau&quot;, so that would mean probably not using my computer skills, which would then languish, then after a couple years I might still not get my desired position, and gave me a card, which I eventually lost.<p>Years later, prior to the insurrection, I had to walk down to Carnegie Mellon and ask if anyone had his contact information, and was shocked that folks refused to even point me at a link to the lecture, which had been listed as open to the public.<p>I&#x27;m someone who <i>reads</i> Wikipedia, not really edits, but the vast majority of users are readers not editors, and this perpetual pattern of refusing to enable privacy enhancing technologies, paired with using privileges access to make hiring decisions against folks who lack the physical ability to make good privacy decisions offended me on a deep, personal level, and is why I often post in brash, erratic manner.<p>Because I see zero incentive to stay silent -- if I&#x27;m quiet, people will slowly drain my bank account.<p>If I post, there is a chance someone will see what I say, notice my skills, and offer full time employment. So I have to continue risking offending folks until I find a full time job, which I have not had since I left the Center for Democracy and Technology under duress following a series of electronic and physical attacks, paired with threats and harassment by staffers in the organization.<p>TL;DR: Great research, but I hope they also add an onion service rather than jump straight to using this :-)<p>[1] <a href="https:&#x2F;&#x2F;lists.wikimedia.org&#x2F;hyperkitty&#x2F;list&#x2F;wikimedia-l@lists.wikimedia.org&#x2F;thread&#x2F;6ANVSSZWOGH27OXAIN2XMJ2X7NWRVURF&#x2F;#6ANVSSZWOGH27OXAIN2XMJ2X7NWRVURF" rel="nofollow">https:&#x2F;&#x2F;lists.wikimedia.org&#x2F;hyperkitty&#x2F;list&#x2F;wikimedia-l@list...</a><p>[2] <a href="https:&#x2F;&#x2F;slate.com&#x2F;technology&#x2F;2021&#x2F;10&#x2F;wikipedia-mainland-china-admins-banned.html" rel="nofollow">https:&#x2F;&#x2F;slate.com&#x2F;technology&#x2F;2021&#x2F;10&#x2F;wikipedia-mainland-chin...</a>

How does the server select the article in a way that we can be sure they don&#x27;t record the article sent back? Are the articles encrypted on the server too?