1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
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>
|
