forked from Hardmath123/hardmath123.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathfacade.html
291 lines (282 loc) · 17.5 KB
/
facade.html
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" type="text/css" href="/static/base.css"/>
<title>The FACADE Protocol - Comfortably Numbered</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta charset="utf-8"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
MathJax.Hub.Config({
tex2jax: {inlineMath: [['($','$)']]}
});
</script>
</head>
<body>
<header id="header">
<link rel="stylesheet" href="/octicons/octicons.css">
<script src="static/cheet.js" charset="utf-8"></script>
<script src="static/main.js"></script>
<h1>
<a href="/"><span class="left-word">Comfortably</span><span class="right-word">Numbered</span></a>
</h1>
<!-- You're reading the source to my blog? What do you think?
Do you have dinner plans? -->
</header>
<article id="postcontent" class="centered">
<section>
<h2>The FACADE Protocol</h2>
<h4>Wednesday, January 4, 2017 · 7 min read</h4>
<p>I think the best way to begin this article is by quoting James Mickens:</p>
<blockquote>
<p>[Cryptographers] are like smarmy teenagers who listen to goth music: they are
full of morbid and detailed monologues about the pervasive catastrophes that
surround us, but they are much less interested in the practical topic of what
people should do before we’re inevitably killed by ravens or a shortage of
black mascara.</p>
</blockquote>
<p>Now, I don’t listen to goth music and I didn’t even know “smarmy” was a word.
But I <em>am</em> a teenager and I <em>do</em> worry about the pervasive catastrophes that
surround us, including, but not limited to, the following three scenarios that
(for reasons beyond my control or understanding) I spent all winter break
contemplating.</p>
<blockquote>
<p><strong>Scenario 1:</strong> The CEOs of ACME, Inc. and Ajax, Inc. both want to know
whether or not the other one is willing to collude. But, they cannot ask the
question outright: if ACME says “Ajax, I want to collude with you,” then Ajax
can use that message to get ACME in trouble with antitrust laws, and thus
eliminate competition. So, both companies end up making less money than they
would in an ideal situation.</p>
<p><strong>Scenario 2:</strong> Alice and Bob both want to go to prom with each other, but
each is too afraid to ask the other. If Bob asks Alice to prom and Alice
rejects Bob, then Bob is in trouble (socially). The same holds if Alice asks
Bob. Game theoretically, each party has a higher expected payout by not
playing the game. The only winning move is not to play: they never end up
going to prom.</p>
<p><strong>Scenario 3:</strong> Alice is the world’s best safecracker and Bob is the world’s
best hacker. If Alice and Bob were to work together, they could pull off a
really lucrative heist. But neither one would suggest such a thing, because
the other would rat him or her out: it’s a round of potential-prisoners’
dilemma. As a result, the heist never occurs, and the only thing the world is
robbed of is another cheap crime novel “based on a true story.”</p>
</blockquote>
<p>Clearly, these scenarios are isomorphic in some way (no, not because they are
all potential Ryan Gosling movies). The common thread is the following: two
parties, each with a secret bit, wish to compute the logical AND of their bits
without revealing their individual bits. Neither party trusts the other, so
there is a deadlock and opportunities are missed. It’s worse than that time Jim
and Della invited a bunch of philosphers for dinner. For that matter, this is
awkwardly reminiscent of that time the two most powerful nations in the world
decided to build lots of nuclear weapons.</p>
<p>Abstractly, what we have is a situation where mutually distrusting parties need
to orchestrate a secure transfer of sensitive information. This sounds like a
job for cryptography.</p>
<h3 id="previous-work">Previous Work</h3>
<p>Apparently Scott Aaronson solved this problem before I did. See
<a href="http://stellar.mit.edu/S/course/6/sp08/6.080/courseMaterial/topics/topic1/lectureNotes/lec181/lec18.pdf">here</a>.
S. Dukhovni, J. Weisblat, and I. Chung improved upon his work. Their solution,
the SENPAI protocol, can be found
<a href="http://sigtbd.csail.mit.edu/pubs/veryconference-paper10.pdf">here</a>.</p>
<p>The problem with both protocols is <em>asymmetry</em>: Bob learns the result of the
protocol before Alice does. This means that Bob can carry out the protocol by
inputting a “1”, and obtain a proof that Alice also input “1”, which, if Bob
were malicious, could be catastrophic for Alice’s social life. Or, in the
isomorphic colluding-businesses case, ACME could obtain a proof that Ajax
intended to collude, and thus sabotage Ajax without completing the protocol.</p>
<p>In fact, if you think about it, <em>any</em> finite protocol should have this
weakness, because if you exchange information in a finite number of turns, then
at some point one person must have the proof before the other person (the act
of sending never creates information for the sender).</p>
<p>How can we solve this? I spent this winter break thinking deeply about this
problem. My result is a protocol that I named, following the tradition of
SENPAI, the FACADE (Feelings Are Complicated And I Don’t Even) protocol. In
case of a “1” result, FACADE gives <em>both</em> parties some proof of the other’s
guilt, thus solving the problem with SENPAI. Much like nuclear disarmament and
the formation of a friendship, both parties take turns making themselves a
little bit more vulnerable, until at last they reach a mutually-agreed-upon
level of nuclear and/or social détente.</p>
<p>Unfortunately, FACADE has some unfortunate quirks that I haven’t been able to
iron out yet—more on that in a moment.</p>
<h3 id="how-does-facade-work-">How does FACADE work?</h3>
<p>The FACADE protocol is based on Rabin’s 1981 paper, <a href="https://eprint.iacr.org/2005/187.pdf"><em>How to Exchange Secrets
with Oblivious Transfer</em></a>.</p>
<ol>
<li>Alice creates a large semiprime <em>N = pq</em> and sends <em>N</em> to Bob.</li>
<li>Bob selects some 1 < <em>a</em> < <em>N</em> and sends Alice <em>s</em>, the square of <em>a</em> mod
<em>N</em>.</li>
<li>Alice sends Bob exactly one square root <em>r</em> of <em>s</em> mod <em>N</em> (there are four
possibilities; she randomly selects one).</li>
<li>With 50% probability, Bob can now factor <em>N</em> by computing the GCD of <em>N</em> and
<em>r ± s</em>. If Bob’s bit is “1” or if he <em>cannot</em> factor <em>N</em>, then he
sends Alice <em>MAYBE</em>, otherwise he sends Alice <em>NO</em> followed by <em>p</em> and <em>q</em>.</li>
<li>The protocol repeats, with Alice and Bob’s roles reversed. Each <em>MAYBE</em>
increases the chances that the corresponding sender’s bit is “1”.</li>
<li>The protocol ends when one party sends a valid <em>NO</em> message, or when both
parties are satisfied that both bits are “1”.</li>
</ol>
<p>The way the FACADE protocol works is by creating plausible deniability for
<em>MAYBE</em> responses. If Bob has sent 10 <em>MAYBE</em> messages, then</p>
<ul>
<li>If Bob’s bit is “0”, the probability of this occurring is less than one in a
thousand.</li>
<li>If Bob’s bit is “1”, the probability of this occurring is one.</li>
</ul>
<p>In other words, each successive <em>MAYBE</em> makes it harder to believe that Bob’s
bit is “0”. However, Bob could still deny having a “1” bit and claim to be
extremely unlucky. Since he keeps <em>a</em> a secret, it is impossible for anyone to
tell whether or not he was “forced” to send <em>MAYBE</em>. Moreover, since Alice and
Bob alternate messages, if Alice decides to rat Bob out with her “evidence” of
<em>n</em> consecutive <em>MAYBE</em> messages from Bob, then Bob can retaliate by showing
<em>n-1</em> consecutive <em>MAYBE</em> messages from Alice, which should be good enough to
convince a jury that neither (or both) of them were up to no good.</p>
<h3 id="-why-does-facade-work-"><em>Why</em> does FACADE work?</h3>
<p>For completeness, I want to briefly touch on the number theory behind Rabin’s
oblivious transfer mechanism: why does this number-theoretic gymnastics make
sense?</p>
<p>When Bob generates <em>s</em>, it is a quadratic residue mod <em>N</em>, and consequently mod
both <em>p</em> and <em>q</em>. <em>s</em> has two square roots mod <em>p</em> and two square roots mod <em>q</em>
because a quadratic polynomial can only have at most two roots in the ring of
integers mod a prime, and we know that if <em>r</em> is a root then <em>-r</em> is also a
root. Using the Chinese Remainder Theorem on each pair, we can reconstruct a
total of four square roots mod <em>N</em>. (To find square roots mod the primes, Alice
can select primes such that both are congruent to 3 mod 4. Then, raising <em>s</em> to
the power <em>(p+1)/4</em> yields a square root of <em>s</em>. Showing that this works should
be easy if you know Fermat’s Little Theorem.)</p>
<p>Now, Alice has no idea which of the four square roots Bob chose when choosing
<em>a</em>. So, she <em>must</em> report a random root. With probability 50%, that root <em>r</em>
will be <em>±a</em>. Bob already knows this root, it’s easy to compute! Let’s
call this a <em>trivial</em> root: it means Bob can’t really do anything new with this
information, because he already knew it.</p>
<p>However, if Alice chooses a <em>nontrivial</em> root <em>r</em>, then the difference of
squares of <em>a</em> and <em>r</em> is zero; that is, we have the equation <em>(a+r)(a-r) = 0</em>.
Since <em>r</em> is a nontrivial root, neither of the factors is individually equal to
zero: so, by Euclid’s lemma, we must have <em>p</em> divide one of them and <em>q</em> divide
the other. That is, the GCD of <em>N = pq</em> and <em>a ± r</em> must be <em>p</em> or <em>q</em>,
and thus Bob can factor <em>N</em> easily.</p>
<p>In summary: Alice has no way of selecting a trivial (or nontrivial) root on
purpose, and thus Bob has a fair 50% chance of factoring <em>N</em>. Crucially, Alice
does not know whether or not Bob can factor <em>N</em> because she doesn’t know
whether or not her root was nontrivial.</p>
<p>I think Rabin’s oblivious transfer trick is one of the cleverest cryptographic
ideas ever, because of how elegantly it accomplishes something seemingly
impossible (“try to tell me something without knowing whether or not you told
it to me”).</p>
<h3 id="why-doesn-t-facade-work-">Why <em>doesn’t</em> FACADE work?</h3>
<p>An unfortunate “gotcha” of this protocol is that it is not reusable, because
<em>all</em> previous <em>MAYBE</em> messages are fair game to be used as evidence against
the sender. Alice can keep knocking at Bob’s door, getting a “1” response,
sending a “0” response, and eventually conclude that Bob’s bit is “1”.</p>
<p>Solving this problem is tough, because FACADE by nature inherently <em>does</em> leak
information. I experimented with strategies where you randomly choose to
pretend your bit is “0” every once in a while to throw off an adversary: that
turned out to be a fruitless endeavor since <em>any</em> such strategy will eventually
be detected by statistically analyzing a large enough set of transcripts
(convincing yourself of this is left as a fun exercise).</p>
<p>In any case, my opinion is that a one-time protocol is definitely better than
no protocol at all, and in each of the potential use-cases listed above, the
secret bits are unlikely to change in a short timeframe.</p>
<h3 id="bonus-protocol-toxic">Bonus protocol: TOXIC</h3>
<p>TOXIC stands for “Two Operators eXchange Information Concurrently,” and to be
perfectly honest it is kind of a cop-out because it requires both parties to be
present in the same physical space. But I think it’s kind of clever anyway, and
it is definitely worth sharing with you, if only because it is fun to imagine.</p>
<ol>
<li>Alice prepares a concentrated lead nitrate solution (solution A) and Bob
prepares a concentrated sodium chloride solution (solution B). Note that
both solutions are clear and visually indistinguishable from distilled
water.</li>
<li>In beaker A, Alice adds a quantity of either solution A or distilled water,
depending on whether her bit is “1” or “0”, respectively.</li>
<li>In beaker B, Bob adds a quantity of either solution B or distilled water,
depending on whether his bit is “1” or “0”, respectively.</li>
<li>Alice and Bob simultaneously empty their beakers onto a large plate.</li>
<li>The result of the protocol is “1” if a precipitate forms, and “0” if it does
not.</li>
<li>The result is immediately washed out to dispose of any evidence.</li>
</ol>
<p>As long as you discard the result immediately, there is no way for anyone to
know what the contents of beaker A and beaker B were. I suppose in practice an
adversary could use some high-tech forensics (e.g. licking the beaker with
their tongue) to recover some information, but in practice you shouldn’t be
doing sketchy protocols in a chemistry lab anyway.</p>
<h3 id="open-questions">Open questions</h3>
<p>One of my favorite blogs, GLL, closes each post with a set of open questions. I
think that is a lovely tradition, and so I invite you to ponder the following
with me:</p>
<p>What other applications are there for this type of protocol? What other flaws
are there in FACADE, and are there ways to fix them? How, at a fundamental
level, is the FACADE protocol related to the concept of a zero-knowledge proof,
or to that of homomorphic encryption? <em>What makes this problem hard?</em></p>
</section>
<div id="comment-breaker">◊ ◊ ◊</div>
<!--
<section>
<center>(<a id="comment-toggle" href="#comment-toggle">Click to load comments…</a>)</center>
<div id="disqus_thread"></div>
<script type="text/javascript">
var disqus_shortname = 'comfortablynumbered';
var disqus_identifier = 'facade.md';
window.addEventListener(
'load',
(function() {
document.getElementById('comment-toggle').addEventListener('click',
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
}),
true);
}),
true
);
</script>
</section>
-->
</article>
<footer id="footer">
<div>
<ul>
<li><a href="http://github.com/Hardmath123">
<span class="octicon octicon-mark-github"></span>
Github</a></li>
<li><a href="feed.xml">
<span class="octicon octicon-rss"></span>
Subscribe (RSS)</a></li>
<li><a href="https://github.com/Hardmath123/hardmath123.github.io/issues/new?title=Hi&body=How's%20it%20going%3F">
<span class="octicon octicon-comment-discussion"></span>
Feedback</a></li>
<li><a href="mailto:contact-at-comfortablynumbered-dot-appspotmail-dot-com">
<span class="octicon octicon-mail-read"></span>
Email me</a></li>
<li><a href="http://creativecommons.org/licenses/by-nc/3.0/deed.en_US">
<span class="octicon octicon-law"></span>
CC BY-NC 3.0</a></li>
<li><a href="appreciation.html">
<span class="octicon octicon-beer"></span>
Other</a></li>
</ul>
</div>
<!--
<span class="sc">ComfortablyNumbered</span> · Hardmath123 (2013) · <a href="feed.xml">RSS Feed</a>
·
<a href="/appreciation.html">
<span class="octicon octicon-beer"></span></a>
<a rel="license" href="http://creativecommons.org/licenses/by-nc/3.0/deed.en_US">
<img
alt="Creative Commons License"
src="http://i.creativecommons.org/l/by-nc/3.0/80x15.png"/>
</a>
-->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46120535-1', 'hardmath123.github.io');
ga('require', 'displayfeatures');
ga('send', 'pageview');
</script>
</footer>
</body>
</html>