summaryrefslogtreecommitdiff
path: root/posts/private-contact-discovery/index.html
diff options
context:
space:
mode:
Diffstat (limited to 'posts/private-contact-discovery/index.html')
-rw-r--r--posts/private-contact-discovery/index.html123
1 files changed, 123 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..609a95e
--- /dev/null
+++ b/posts/private-contact-discovery/index.html
@@ -0,0 +1,123 @@
+<!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 | blog.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/blog.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">
+ &#169;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>.<br/>
+ <a href="/about">About this blog</a>.
+ </div>
+ </footer>
+ </body>
+</html>
+