summaryrefslogtreecommitdiff
path: root/blog/private-contact-discovery
diff options
context:
space:
mode:
Diffstat (limited to 'blog/private-contact-discovery')
-rw-r--r--blog/private-contact-discovery/index.html80
-rw-r--r--blog/private-contact-discovery/mori_semi_psi_talk.odpbin0 -> 35999576 bytes
-rw-r--r--blog/private-contact-discovery/mori_semi_psi_talk.pdfbin0 -> 11600295 bytes
3 files changed, 80 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..cbb3814
--- /dev/null
+++ b/blog/private-contact-discovery/index.html
@@ -0,0 +1,80 @@
+<!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>
+ <div class="internal">
+
+ <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>
+ </div>
+ <div class="external">
+ <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>
+ </span>
+</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="/about/">About</a>
+ / <a href="/imprint/">Imprint</a>
+</footer>
+<script>
+ if(navigator.getEnvironmentIntegrity!==undefined)document.querySelector('body').innerHTML=`<h1>Your browser
+ contains Google DRM</h1>"Web Environment Integrity" is a Google euphemism for a DRM that is designed to
+ prevent ad-blocking, and which Google has forced into their browsers against widespread public opposition.
+ In support of an open web, this website does not function with this DRM. Please install a browser such
+ as <a href="https://www.mozilla.org/en-US/firefox/new/">Firefox</a> that respects your freedom and supports
+ ad blockers.`;
+ </script>
+ </body>
+</html>
diff --git a/blog/private-contact-discovery/mori_semi_psi_talk.odp b/blog/private-contact-discovery/mori_semi_psi_talk.odp
new file mode 100644
index 0000000..e7df32e
--- /dev/null
+++ b/blog/private-contact-discovery/mori_semi_psi_talk.odp
Binary files differ
diff --git a/blog/private-contact-discovery/mori_semi_psi_talk.pdf b/blog/private-contact-discovery/mori_semi_psi_talk.pdf
new file mode 100644
index 0000000..e06fd63
--- /dev/null
+++ b/blog/private-contact-discovery/mori_semi_psi_talk.pdf
Binary files differ