diff options
| author | jaseg <git@jaseg.de> | 2023-03-19 00:54:56 +0100 |
|---|---|---|
| committer | jaseg <git@jaseg.de> | 2023-03-19 00:54:56 +0100 |
| commit | 490ca12809a2625549aae16311affdd546e9c201 (patch) | |
| tree | 58024389e48d91731efa352ae772a058b376b8cf /blog/private-contact-discovery/index.html | |
| parent | 92e3b5f49f6f5336530988e7839ab3ed283b86e4 (diff) | |
| parent | f21dea91904d7bf9628457a5758016c9a0df6d38 (diff) | |
| download | blog-490ca12809a2625549aae16311affdd546e9c201.tar.gz blog-490ca12809a2625549aae16311affdd546e9c201.tar.bz2 blog-490ca12809a2625549aae16311affdd546e9c201.zip | |
deploy.py auto-commit
Diffstat (limited to 'blog/private-contact-discovery/index.html')
| -rw-r--r-- | blog/private-contact-discovery/index.html | 69 |
1 files changed, 69 insertions, 0 deletions
diff --git a/blog/private-contact-discovery/index.html b/blog/private-contact-discovery/index.html new file mode 100644 index 0000000..e143e74 --- /dev/null +++ b/blog/private-contact-discovery/index.html @@ -0,0 +1,69 @@ +<!DOCTYPE html> +<html><head> + <meta charset="utf-8"> + <title>Private Contact Discovery | Home</title> + <meta name="description" content=""> + <meta name="viewport" content="width=device-width, initial-scale=1"> + <meta name="mobile-web-app-capable" content="yes"> + <meta name="color-scheme" content="dark light"> + <link rel="stylesheet" href="/style.css"> +</head> +<body><nav> + + <a href="/" title="Home">Home</a> + <a href="/blog/" title="Blog">Blog</a> + <a href="/projects/" title="Projects">Projects</a> + <a href="/about/" title="About">About</a> + <span class="spacer"></span> + <a href="https://git.jaseg.de/" title="cgit">cgit</a> + <a href="https://github.com/jaseg" title="Github">Github</a> + <a href="https://gitlab.com/neinseg" title="Gitlab">Gitlab</a> + <a href="https://chaos.social/jaseg" title="Mastodon">Mastodon</a> +</nav> + + <header> + <h1>Private Contact Discovery</h1> +<ul class="breadcrumbs"> + <li><a href="/">jaseg.de</a></li> + <li><a href="/blog/">Blog</a></li><li><a href="/blog/private-contact-discovery/">Private Contact Discovery</a></li> +</ul> + <strong>2019-06-22</strong> + </header> + <main> + <div class="document" id="private-contact-discovery"> +<h1 class="title">Private Contact Discovery</h1> + +<p>Private Contact Discovery (PCD) is the formal name for the problem modern smartphone messenger applications have on +installation: Given a user's address book, find out which of their contacts also use the same messenger without the +messenger's servers learning anything about the user's address book. The widespread non-private way to do this is to +simply upload the user's address book to the app's operator's servers and do an SQL JOIN keyed on the phone number field +against the database of registered users. People have tried sprinkling some hashes over these phone numbers in an +attempt to improve privacy, but obviously running a brute-force preimage attack given a domain of maybe a few billion +valid inputs is not cryptographically hard.</p> +<p>Private Contact Discovery can be phrased in terms of Private Set Intersection (PSI), the cryptographic problem of having +two parties holding one set each find the intersection of their sets without disclosing any other information. PSI has +been an active field of research for a while and already yielded useful results for some use cases. Alas, none of those +results were truly practical yet for usage in PCD in a typical messenger application. They would require too much CPU +time or too much data to be transferred.</p> +<p>At USENIX Security 2019, Researchers from technical universities Graz and Darmstadt published a paper titled <em>Private +Contact Discovery at Scale</em> +(<a class="reference external" href="https://eprint.iacr.org/2019/517">eprint</a> | <a class="reference external" href="https://eprint.iacr.org/2019/517.pdf">PDF</a>). +In this paper, they basically optimize the hell out of existing cryptographic solutions to private contact discovery, +jumping from a still-impractical state of the art right to practicality. Their scheme allows a client with 1k contacts +to run PCD against a server with 1B contacts in about 3s on a phone. The main disadvantage of their scheme is that it +requires the client to in advance download a compressed database of all users, that clocks in at about 1GB for 1B users.</p> +<p>I found this paper very interesting for its immediate practical applicability. As an excuse to dig into the topic some +more, I gave a short presentation at my university lab's research seminar on this paper +(slides: <a class="reference external" href="mori_semi_psi_talk.pdf">PDF</a> | <a class="reference external" href="mori_semi_psi_talk.odp">ODP</a>).</p> +<p>Even if you're not working on secure communication systems on a day-to-day basis this paper might interest you. If +you're working with social account information of any kind I can highly recommend giving it a look. Not only might your +users benefit from improved privacy, but your company might be able to avoid a bunch of data protection and +accountability issues by simply not producing as much sensitive data in the first place.</p> +</div> + </main><footer> + Copyright © 2023 Jan Sebastian Götte + / <a href="http://jaseg.de/about/">About</a> + / <a href="http://jaseg.de/imprint/">Imprint</a> +</footer> +</body> +</html> |