122 lines
4.9 KiB
HTML
122 lines
4.9 KiB
HTML
<!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>
|
|
|