diff options
| author | jaseg <git@jaseg.de> | 2021-08-15 14:32:23 +0200 |
|---|---|---|
| committer | jaseg <git@jaseg.de> | 2021-08-15 14:32:23 +0200 |
| commit | 6c1bf0bbf6189c6927514f58271dd63831909640 (patch) | |
| tree | d3c6f5b6ea8c90b1e0d9751c411d83c7ce113513 /posts/private-contact-discovery/index.html | |
| parent | 088e9c83e8683f9bfbf694771c128a3cc1d62c50 (diff) | |
| parent | fc5a5cf688997d7eb4705ad5c152497d175134af (diff) | |
| download | blog-6c1bf0bbf6189c6927514f58271dd63831909640.tar.gz blog-6c1bf0bbf6189c6927514f58271dd63831909640.tar.bz2 blog-6c1bf0bbf6189c6927514f58271dd63831909640.zip | |
deploy.py auto-commit
Diffstat (limited to 'posts/private-contact-discovery/index.html')
| -rw-r--r-- | posts/private-contact-discovery/index.html | 122 |
1 files changed, 122 insertions, 0 deletions
diff --git a/posts/private-contact-discovery/index.html b/posts/private-contact-discovery/index.html new file mode 100644 index 0000000..593c4ab --- /dev/null +++ b/posts/private-contact-discovery/index.html @@ -0,0 +1,122 @@ +<!DOCTYPE html> +<html lang="en-us"> + <head> + <meta charset="utf-8"> + <meta name="viewport" content="width=device-width, initial-scale=1"> + <title>Private Contact Discovery | jaseg.de</title> + <link rel="stylesheet" href="/css/style.css" /> + <link rel="stylesheet" href="/css/fonts.css" /> + + <header> + + + <link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/atom-one-light.min.css"> + <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js"></script> + <script>hljs.initHighlightingOnLoad();</script> + <nav> + <ul> + + + <li class="pull-left "> + <a href="https://blog.jaseg.de/">/home/jaseg.de</a> + </li> + + + + + </ul> + </nav> +</header> + + </head> + + <body> + <br/> + +<div class="article-meta"> +<h1><span class="title">Private Contact Discovery</span></h1> + +<h2 class="date">2019/06/22</h2> +<p class="terms"> + + + + + +</p> +</div> + + + +<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> + +<script> +(function() { + function center_el(tagName) { + var tags = document.getElementsByTagName(tagName), i, tag; + for (i = 0; i < tags.length; i++) { + tag = tags[i]; + var parent = tag.parentElement; + + if (parent.childNodes.length === 1) { + + if (parent.nodeName === 'A') { + parent = parent.parentElement; + if (parent.childNodes.length != 1) continue; + } + if (parent.nodeName === 'P') parent.style.textAlign = 'center'; + } + } + } + var tagNames = ['img', 'embed', 'object']; + for (var i = 0; i < tagNames.length; i++) { + center_el(tagNames[i]); + } +})(); +</script> + + + <div id="license-info"> + ©2020 by Jan Götte. This work is licensed under + <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC-BY-NC-SA 4.0</a>. + </div> + <div id="imprint-info"> + <a href="/imprint">Impressum und Haftungsausschluss und Datenschutzerklärung</a>. + </div> + </footer> + </body> +</html> + |