Dear viewer, these subtitles were generated by a machine via the service Trint and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/396 Thanks!
OK, ladies and gentlemen,
our next talk is coming up,
DPE five Pray
for privacy preserving presents,
a framework that allows you to
have better control of your privacy
if you have a space as free
seat next to you.
Could you please raise your hands so
anyone can find seats really
quickly, even for the
people coming in right now?
Now, there will be a notice
about the translation as gift from
D.M. English and talk I Nahdlatul love
about that song Betoota
Steck, Tel Naiman on
Canale Art and Science.
Vean on Don't follow through but
that's about that's fun.
English Nadege.
OK, so we are ready to start
here. We have Ian and
George and let's give them a warm
round of applause.
OK, this is fine.
Yes, all right.
Hi, everyone. I'm Engleberg.
I'm from the University of Waterloo in
Canada. And this is George Denise's from
University College London in London.
Our colleague Nikita Borshoff,
unfortunately, could not be with us
today. So it's just the two of us.
So we're going to be talking about DPE
five PR for privacy preserving
president presents.
No, I
will be talking about PR or private
information retrieval for the first part
of the talk and then we'll turn it over
to George.
Something popped up there doesn't
matter.
And we'll turn it over to George, who
we'll talk about deep five.
So first PR,
what is PR?
So imagine an online
database.
Not too hard to imagine.
There are all kinds of online databases.
Let's say this is a database of patents.
Right. So we have an online database of
all the, say, US patents.
And again, you don't have to imagine too
hard because there really are these
online databases you can query.
OK, and here's Alice.
Alice is a researcher and Alice
wants to look at patent six three six
eight two two seven method of swinging
on a swing. This is a real patent.
It covers pulling the chains of a swing
sideways. So you swing
left to right instead of forward and
backward. Again, this is a real
patent.
It has since been revoked on the grounds
of stupidity,
but it was issued.
So Alice wants
to hook up this patent, but
Alice does not want to
let the database server
know that swings are a
hot new research topic.
OK, now swings, of course,
this is a silly example,
but if you replace swing by like
one three dimethyl mumble, mumble
Alman. All right.
Some some
pharmacological molecule or something
like this, then you can see it might be
very important to be able to look
up things in this database without
revealing to the database what you
were looking for.
Right. Otherwise, the database operator
could themselves then go
and say, oh, someone
is interested in this drug.
We may as well go research that
ourselves.
Right. Or we saw examples
long ago called domain frontrunning.
When you would look up, you would do who
is to see if your favorite
domain name was available.
And the act of doing the WHO is
would cause some unscrupulous
network operators to then go register
it before you can register it and
then sell it to you at an inflated price.
Right. So you want to be able to look up
things in the database without
letting the database itself
know what you asked for.
OK, this is private information
retrieval.
OK, no to that.
We're not talking about anonymity.
We're not hiding Alice's identity here.
The problem isn't that we're hiding the
fact that Alice is the one looking up
swing's what we're trying to hide
is that swings are interesting,
right? That anybody is looking up swings
at all. Of course, if you want
to
add anonymity on top of this, no problem.
You just add Tor to it or something like
that and it works just fine,
but you don't have to.
And in fact, you can have business models
based on PR that have that
allow us to pay for these private
workups. So Alice logs
in, authenticates herself, then does a
private look up and may pay for the
privilege of doing a private lookup.
OK, so.
Alice, does this PR query
and the idea is that
the server has no idea what
it was, Alice looked up.
OK, now you may be thinking to yourself,
this is clearly impossible.
Who's thinking this is clearly
impossible?
Right. Right.
It is clearly impossible.
Yet the magic of cryptography
is such that things that are clearly
impossible are often straightforward
and vice versa.
So here's a simple example
called the trivial PR protocol
to show you that it's not impossible.
Alice connects to the server, says,
I would like a patent, please, on the
server, says, OK, here's all the
patents. Look it up yourself.
OK, clearly this is completely
private. The server hustla no information
about what patent Alice was looking for,
but at the same time, this is a
ridiculous protocol.
Why it sends way too much
data right off the databases
of any reasonable size.
You're not going to be able to send all
that information to house in a reasonable
amount of time.
OK, and there are other objections
to the to the trivial
Pyaar protocol as well.
So what we aim for
in better PR protocols is
to achieve the same level of privacy
while sending much less data.
OK, and we're going to see a simple
example of a protocol in
a few minutes just to let you know
that this is a real possible thing.
OK, there are a couple
of main categories
of PR protocols.
The first is called computational PR.
And this is where the security
of the PR system relies on
the fact that the
server who is your adversary,
the server is trying to learn what you're
asking for and you're trying to not let
it.
So you're relying on the fact in
computational PR that the
server is computationally limited, it
doesn't have an infinite computing
power, and in particular, it can't break
certain types of public key cryptography.
OK, so a brief taste
of how it works, I won't go into the
details on this one.
Basically, Alice takes her query
and encrypts it.
But unlike the case where Alice
is, say, connecting to the server
over, for example, tells
where what Alice would do is
take the query, encrypt it to the servers
publicly and send it so
that third parties can read it
here. Alice is trying to protect
the query from the server itself.
And so Alice doesn't encrypt
the query to the servers.
Public key Alice encrypts the query
to her own public key.
This is weird.
How is the server going to be able to
read it? Well, that's the point.
The server isn't going to be able to read
it. And then Alice sends the encrypted
query over to the server.
So what can the server do with this
encrypt encrypted query?
Well, it turns out there's some kinds
of public key encryption that
allow for an operation
that's technically called home amorphous.
And you might have heard in the news
about recent results in so-called
fully Haoma morphic cryptography,
which promises to allow all kinds
of crazy computation, not only exorbitant
costs.
But this isn't that this is
the simpler kind of what's called
partially homo morphic cryptography
that's actually totally reasonable.
And what it allows
is for the server to take the encrypted
query encrypted with Alice's public key
and the plain text database and
combine them to form an encrypted
response still encrypted with Alice's
public key, even though the database
can't decrypt the query or
the response.
And then the database sends that
encrypted response back to Alice, who
decrypt it.
So that's the general structure of
computational pyaar.
Now, these Haoma morphic operations are
somewhat expensive, and so
it kind of sometimes costs a lot
to do these kind of computational
pyaar queries.
So there's another kind of picture
called information theoretic, Piara.
It's here and
here.
What you have is that
the servers are no
longer computationally limited.
Now the servers are allowed
to have unlimited computational power,
a quantum computer, magic computer,
whatever. They can compute anything they
want in no time and.
Alice's query is still protected,
even against unlimited computational
power. How can that possibly be?
Well, we use a different security
assumption, not one based on
cryptography, but one based on
information theory and same information
theoretic.
And here the idea is you have to have
multiple servers.
And Alice asks a question
of each of the servers
and gets back the responses
and then combines those responses
in order to
get her her answer.
Now, the security property
we have is a non collusion assumption.
So we have to assume that some,
at least some threshold of
these various servers are honest
and not colluding with each other.
To try to break Alice's
privacy in this kind of non collusion
assumption is common
in privacy enhancing technologies.
Things like Tor, of course, use it.
If all of the servers and you're in your
path are colluding against you, you're
kind of scrod.
How did that come up on the.
Yeah. If all the servers are colluding
against you, that's bad.
And some kinds of
electronic voting have this kind of non
collusion assumption. So this is a pretty
typical assumption.
So and then there are ways that
combine these to combine a little bit
of computational protection with a little
bit of information theoretic protection
if you want a bit of each.
OK, so that's information
information theoretic, Piara.
And the advantage of it is
it's much faster, like 70 to 100 times
faster than computational K.R..
Right. So that's a bit
of an advantage there.
OK, but on the downside, you need these
multiple servers.
So that's the tradeoff you're making.
OK, so let's
look at a simple example
of an information theoretic picture
just so you can have a little taste.
And I'm going to do a little bit of math.
Who's scared? Who likes math?
Yay, math.
OK, it's going to be pretty easy math.
Like in some countries, high
school math and other countries may be
first year college math.
OK, so depen.
Yeah, it depends where you are.
It's around then.
So it's, it's vectors and matrices.
Who's happy with vectors and matrices.
Who. OK, so vectors
and matrices.
So this will be if you're happy with that
it'll be easy if not just come along
and, and pretend you know the words.
So
we're going to say our database, we're
going to represent it as a matrix,
like a matrix is just a rectangular
block of in this case, bits,
zeros and ones where each
row is one record of the database.
So the first row is record one, the next
rose record to the next rose, record
three and so on.
And let's say there are rows in this
database and each
record is SBX long.
So this is an R by S matrix,
OK?
And what the queerer wants to do
is retrieve one of the records.
Right. Say the third one, this one
here. So it wants to retrieve one of the
rows of the database.
OK, so in
order for this PR system to work,
we just need to recall two facts
from maybe high school, maybe first year
college math.
One is if you take
the elementary vector,
if you take the elementary vector II,
which is all zeros except for
a one in the eighth place.
Right. So this would be three here.
Right.
If you take eEye, this vector
of length R
and multiply it by this matrix.
In fact, when's the last time I did
matrix math?
How does this go?
You turn sideways and you multiply anyway
you can trust me.
What comes out is the throw
of the matrix
i.e. block I of the
database.
OK, so of course
you could say, well that's our protocol.
Then you, you construct this
vector containing the,
the index of
the record you're interested in, you send
it to the server, the server multiplies
it by D and sends you your answer.
But of course that's not private.
Right. The server can just look at
this vector and say, oh, the one is in
the third place. You're looking up record
three, no privacy.
So the second piece of
high school math we need is the
distributive law.
OK, you may recognize the distributive
law as working on numbers,
but it also works on on vectors
and matrices. It works just fine.
So what's the distributive V one
time Z plus be two times D plus did it
plus V.
All times the is the some of the veejays
times D so how
are we going to make a PR
protocol?
You may be able to see it just from these
lines. So here's how it's going to work
out. Let's say Alice wants
row three of the database.
Alice constructs II doesn't send it
to anybody.
Alice then picks that say there are
L servers.
Alice picks L completely
random vectors zero one
vectors under the condition
that they add up to eEye
mod to all
binaries are going to mod two.
OK, so how does she do that?
The easiest way is just pick L minus one
completely random vectors
and then figure out what the last
one has to be so they all add up.
So eEye minus the some of the ones
you have already right now, you have l
completely random vectors and you send
V one to serve one, V two to serve or
two. V three to serve a three and so on.
And each server is getting just a
random string and that if
you work it out, contains very formally
absolutely no information
about this number three here.
OK, so each server gets absolutely no
information. In fact, any coalition
of as many servers as you
want, as long as it's not all of them
has no information about AI.
And then what is the protocol?
Each server just multiplies the V,
it gets by the database.
Gets the answer, sends the answer back to
Alice, like this one, Alice just adds
up the answers by the distributor FVA
That's the sum of the Veejays Times D
But the some of the veejays we chose to
buy, which is this Anei Times
D is Bloche Puf.
OK, so is this actually
more efficient transfers,
less information than
the naÃ¯f, just download
the entire thing, the trivial protocol?
Well, how much data does Alice
send each server?
It's a vector of length are
so Alice sends are bits to each
server. And how much does she get back?
Well, this time this is
a is a vector of length.
So Alice gets bits back.
OK, so are plus
s bits are transferred between
Alice and each server.
And how many bits are there in the
database. It's our times s bits
which is much, much bigger for
any reasonable use of our in us.
Right. And in fact we get the best
protocol if our interests
are about equal. If this database is
squarish, then you're sending about the
square root of the size of the database
to each server and receiving the square
root back.
OK, so two times the square root
of N if and is the number of bits of the
database times l
the number of servers as opposed to
and the size of the whole
database and the square root of N
is much smaller than anif and is of
reasonable size.
OK, so this
was one of the very first peer
protocols proposed by Tor and others
in nineteen ninety five, almost
twenty years ago now.
But it has some shortcomings
that many of which have been addressed
over the subsequent 20 years.
So let's look at a couple of them.
One of them is that
click the the
shape of this database is rather
simplistic, right?
This database consists of some
number of equally sized records.
Not all databases have equally sized
records. So other work has shown how to
extend this very same protocol
or related protocols to handle variable
size records.
And you might think that's a little
tricky because the answer gets
has to not reveal the size
of the record I was looking for.
So it's a little tricky to do this
securely, but that's
been done in previous work.
Other previous work has
looked at the query
write. The query in this protocol is I
want to record three.
Right. Typically a client of a
database does not know which physical
record number they want to look
up. They know some other information.
They have some more expressive
query, for example, keywords
or even ask you well, in previous work
has shown how to put that into picture
so that you can do Enescu query
on a server without telling the server
what your query is.
That's pretty cool.
That's previous work that already exists,
we have code and everything.
So.
These are previous work and one other
thing, one other shortcoming of.
Of this simplistic scheme
is that it's not robust and what we
mean by robust, so if you look
here, what happens?
Click.
OK, over here.
OK, next slide.
OK, there we go.
Lasers working, OK, so.
What do we mean by robust?
Well, imagine one of the servers is
down and doesn't give you a response
or worse, one of the servers is malicious
and gives you the wrong answer.
When Alice adds up the answers,
she'll just get some garbage.
And worse, she can't tell which server
gave her the wrong answer.
OK, so a robust protocol
would allow Alice to retrieve
her correct block even if some of the
servers were down or malicious.
And at the same time, she'll be able to
identify which servers were malicious
and of course, that's a disincentive for
the server to be malicious in the first
place. So let's look at briefly
how these robust protocols work.
So it uses something called Shamir's
secret sharing, which is pretty
fun and cool. So I'm going to talk about
that for a little bit.
Who's heard of Shamir's secret sharing?
Not as many people as I've heard of
matrices. Who's heard of polynomials?
OK, good.
We're going to use polynomials,
OK, so Shamir's secretory.
So what is this? You have some secret in
the case of the PR scheme, the secret is
this Victor II.
Right. Which represents which block
number you're interested in.
So you have some secret and
you want to share pieces of
the secret among a number of
parties such that
there some threshold T
that if it most T of those parties
come together, they have no idea
what the secret is.
It's not that they have some few bits of
the secret. They have none of the secret,
none at all.
OK, but if more than t come together
they get the secret.
OK, so here's how that's going to work.
You have your secret
and you have your privacy threshold
level that you care about.
We'll call T and what you do
is you make
you draw your x y axes
and you draw a green dot at
zero comma your secret.
OK, and then you pick a random
polynomial off of the green tea
that goes through that dot.
OK, so you're picking a random polynomial
of degree T.
Who's y intercept is
your secret, OK, that's what
you're doing.
So when T is one, this is a random line
that goes through the door.
20 is two. It's a random
parabola that goes through the door and
is three. It's a random Kubic that goes
through the dot.
OK, so what
do you do next then you just hand
out other points on this polynomial.
So these blue points here, you hand
them out to the parties,
then what happens if someone said, oh,
someone just got it.
OK, so what's about to happen?
So let's just look at the simple linear
case as an example.
If you only have one dot,
you have no idea what the y intercept
of the line going through this dot is,
because it could literally be anything.
And similarly, if you have two dots, you
have no idea what the y intercept of the
problem is because it could literally be
anything and so on.
But if you have more than T let's say you
have two dots, of course, two points
make a line. So you draw the line and
there's your Y intercept and you can just
read off the secret right from there.
So this is Shamir's secret sharing
and this is what we use
instead of this splitting the eEye
into just V.R.
V1 plus V two plus V three and so
on. We split it in this slightly
more complex way.
But this has the nice feature that you
don't need all the servers
to come back and give you the answers.
You only need T plus one of them
and then one of some of the servers give
you wrong answers.
Well, that's where we use something
called error correcting codes.
So with error correcting codes, we can
tell, for example,
which when we have some
click, some wrong
points, which points
are wrong. So here's a little quiz.
T is three. So we're looking for a Kubic
that passes through all but one
of these points.
So there are six points up there.
One of them is wrong.
Which one is wrong?
Who says the one at this
end is wrong?
Who says the second one third
one fourth one
fifth one sixth one.
OK, the answer is in fact,
the first one.
That's the Kubic.
And this kind of error correction
is actually used quite commonly.
It's used in CDs and
DVDs.
It's used in QR codes.
Right. You're probably familiar with
this. Quick, what is this QR code resolve
to know?
But the reason that it's using QR
codes is so you can do this and just
blot some stuff obscuring
part of the QR code and this code will
still scan to the same thing.
The other code scan to which is in fact
the homepage.
OK, so these error correction
codes are
used all over in in ordinary life
because you want to make sure usually
that scratches on your DVD or Tear's
in your QR code, don't mess things up.
And they are also used in PR
to handle malicious servers.
OK, so all this is implemented
in our Pursey plus plus open
source library.
That's a pun on Pyaar in C++,
pure C++ now.
OK, fine.
For those of you who I get, there's a
gift. For those of you who don't like get
there is a sourceforge.
For those of you who don't like
SourceForge, find someone who you
know who likes get.
OK, so now I'm going to turn it over to
George, who's going to talk about
using Pyaar
to make privacy, preserving protocols.
Thank you.
Good afternoon, everybody.
I hope this works, so the cool thing
about crypto is that it's about math and
mass is cool.
But what is even better is that we can
use crypto in order to protect our
privacy against adversaries that we would
never have imagined without crypto to be
able to protect ourselves against.
So the example that I will use to
illustrate why Peer can be useful, that
it relates to achieving
privacy in kind of social interactions
online.
So you may have noticed that in
the last 15 years we started using
computers to talk to each other.
OK, and you have things like Twitter,
you have things like Facebook,
no reaction, OK?
And you have different chat protocols.
Knew this thing works sometimes and
not other times.
All right. Tricky.
OK, so all of these have something
in common.
Namely, they have a sense
that some users are friends with other
users. Again, this is kind of crucial to
all of them, even even Twitter,
which doesn't, you know, handle secrets.
Usually all that much has a sense
that you have people following you and
you follow people and that kind of rules
information around and it's kind of
important.
OK, now one further
thing that is important, particularly
when it comes to chat and we're
particular kind of chat because we would
like to eventually protect the privacy of
people. Chatting is presence.
Now, what is presence?
Presence is just a little green dot that
you see next to someone's name when
they're online. This is really presents.
I mean, it's kind of a simple thing.
However, we kind of grew used to it
in the sense that in the old days
you would just call a number and hope
that someone picks it up, particularly
when it was a home number.
And most most of the time no one would
pick it up. And it was very frustrating.
Now, what was the last time you had this
frustration? Right.
I mean, 10 years ago, something
nowadays you can see when people are
online, you can just call them.
And you know that more often than not,
they will answer unless they actually
don't want to talk to you, at which point
it's a bit awkward.
And in order to
avoid such awkwardness, in
fact, we have we have
improved our presence protocols with
some additional information.
You don't just see green or nothing.
You actually have this kind of
intermediate states of orange, which is
kind of I'm going away or, you
know, red. I'm quite busy.
So we don't just want to know if people
are online or offline, but we also want
to associate some further information
with what they're doing.
You know, what kind of status they have
some little message that says, I'm away,
I'll be back at 5:00 or something like
this. So our presence protocols will
try to replicate this facility,
both of finding out if people are online
and also convey some little
amount of associated information that
will help any further communications.
Now, how is presence
achieved today in
most services, including very big
commercial services or
smaller services run by good people
like, you know, the job of services of
the CCC that many of us are using?
The the way this is done
is actually quite shared in
some sense.
What happens is that you have usually
some kind of server and
there is some kind of a notion of a
social network of users having friends
and contacts, et cetera, et cetera,
they'd like to hear from or they would
like information about it from what they
would like to find out if they're online.
And the service has to
simply know the full social graph,
OK, that's how it's done.
And then what happens is that Bob
comes online,
but then Alice comes online and
Alice authenticates, says,
Hi, I'm Alice.
The service knows that Bob is a friend of
Alice.
And then the service
sends back to Alice, who's online,
who's not online, what their status is.
OK, now.
Maybe I should I'm clicking
furiously here, I will actually
move towards there so that I stop doing
that.
OK, now.
And then some present information is
routed back, so
there is a fundamental privacy
problem with relying on services
that have these social graph as a
necessary information to provide
presence.
OK, now what is
the problem associated with that?
The problem is that who your friends
are basically
leaks a lot of information about who you
are. OK, if all my friends
are hackers, the probabilities are
that I'm a hacker.
If all my friends are journalists, the
probabilities are that I'm a journalist.
If all my friends are from Sudan,
I have some association from Sudan.
So suddenly who, you know, actually
has gives away a lot of information about
you in particular,
who you contact or who you
know, who you include as
a friend, as a new friend, et cetera.
If suddenly I start including a lot of
doctors or a lot of lawyers
in my circle of friends, well, that
actually leaks information about me.
OK, and you may say, well, you
know, what's the big deal about
this? This is not a big deal.
However, what we have learned from
the Snowden leaks is that
if we have services that hold this
information, what may happen,
such as, for example, a friendly ISP
like Lavabit, what may happen is
that the government who wants to discover
this information about you will go to the
service provider who never intended to
betray you and will say thank you very
much.
Can we have all this database of who is
friends with whom?
OK, and we know that there are specific
programs that do target those databases
for collection, either by coercing
providers or by
actually just stealing the data off
the wire or from their databases.
Now, what's the big deal
with that? Well, we actually had a very
interesting confession
last year by General Michael
Hayden.
He said we kill people based on metadata.
So you being in the social
graph of particular, other people may, in
fact go as far as putting on a kill list.
And even when that doesn't happen,
it go we might go so far as
putting you on a particular targeted
surveillance list or make you
a target for harassment, et cetera, et
cetera, et cetera. So we would like to
hide this metadata.
We do not want to rely on third party
services holding that graph
in order to provide presence or
any other associated data that comes with
presence.
OK.
Now, what do we expect from
a privacy friendly present system?
First of all, there are some functional
features that we would not want to lose.
We want users to be able to
somehow associate friends with
each other and register that they're
online and extract people status
and then suspend friends if they
do not wish to share any more information
with them.
Now, we would like our privacy
friendly system to be resistant against
some pretty serious adversaries out there
because we know they exist and they're
interested in this information.
We assume our adversaries are.
OK, we assume our adversaries,
for example, can observe most
communications on the network, all
communications, we assume our adversary,
sometimes our our friends, we would like
to hide information even
from other uses that we have tagged
as friends. However, we will assume
that we have some aces up our sleeve.
In particular, the computers we're using
are secure. And if you know that is
not the case for your computer, I'll go
and talk to the people who maintain tales
or any such distribution.
They may be able to help you and we will
assume that both are cryptography,
is secure, cannot be broken
by the adversary, and also that
we have some infrastructure servers that
will not all collude with each other to
violate our privacy.
This is very much in line with the
assumption that Ian mentioned earlier
today.
And with those tools, what
we will try to do is, first of all,
protect the privacy of our social
network. We do not want any third party
to be able to see the full social
network. We will try to protect the
privacy and integrity of the associated
status information and also provide
some additional properties, most notably
for the purpose of this talk and
likability, namely the inability
from one time period to learn information
that will be used in another time period
to violate any privacy properties of the
network, as well as forward and backward
secrecy, et cetera, that are
very interesting to resist, very
powerful adversaries.
Now, some of you may already
be thinking, ha, I can
think of a trivial way of doing this
right.
And this is not like using a lot
of very advanced technologies.
What we can do is we simply have Alice
and she basically contacts through an
anonymity channel like Tor, for
example, to a chat server that
is either a hidden service or on
the other side of the anonymous channel
and registers using a pseudonym.
And then we will have Bob down the line
that also registered to the same server
and also says, hey,
by the way, is Alice or the pseudonym
of Alice online, OK?
And that, you may think
solves the problem.
However, this is not quite the case
because what happens on the servers is
that the pseudonym of Alice in the
pseudonym of Bob are somehow associated
with each other and so is the pseudonym
of Alice. Will all the pseudonyms of her
other friends and the pseudonym of Bob
with none of his other
friends. And what happens in effect
is that a kind of isomorphic
a to the real social graph starts being
constructed in the service?
OK, we have pseudonyms being friends with
pseudonyms. However, the shape of that
graph, the links are one to one
mapping with the real graph.
And therefore, despite the fact that
maybe these are just pseudonyms instead
of Alice, we have a instead of Bob, we
have B.
If the adversary has any side
information, such as, for example,
you know, contributions of people
and their friends on, you
know, kind of online
video review site or anything like that,
they may be able to use that information
to reconstruct the graph and the
anonymize it.
And we have seen particular attacks
against Netflix that do that.
Therefore, it is not actually a safe way
to just do this, OK, because the
adversary would be able to just go to the
server and or operate
even such a server and recover
a graph that is pretty damn
close to the graph we are trying to hide.
We don't want to do that.
We want to leak no information,
not just hide a little bit of
information.
OK, so here is a high level
overview of how do we actually
achieve this? And you
will recognize a few of the ideas that
you mentioned.
So the basic problem
is that we have Alisson, we have Bob and
their friends and they would like to use
a service.
And this service runs our specific
protocol called DP five,
and that stands for the National Privacy
Preserving Present Protocol
and the extra PS for extra privacy.
So they would like to use a service that
runs the Deep Five protocol to
gain some present information.
However, we would like all the servers
that run deep inside not to learn
anything. So let's see how we could
achieve this, first of all, because
the servers should not actually
be able to extract any information about
what's going on. Clearly, Alice and Bob
need to share some secret that the
servers don't know. So we assume that
Alice and Bob share a key that they can
either share when they meet each other or
they can derive using public key
cryptography.
Then Bob somehow has to send
some information about his
presence and his status to
the infrastructure to DP five server or
servers. OK, and then naively,
you may think, well, you know,
Alice, we'll just have to go and ask, you
know, is Bob there?
Is Charlie there and recover that
information?
However, this would be insecure, of
course, because that would leak to
the infrastructure that
Alice and Bob and Charlie are associated
with each other.
OK, so wouldn't it be.
If at this stage we had
some kind of mechanism for Alice
to ask the server
for a particular record associated with
Bob without however
leaking which record that is because
that, in fact, would allow us to then
have private presence.
And in fact, this is exactly
the protocol that Ian
talked about before.
And the key inside, behind the DP five
protocols is that we use
private information retrieval
to recover,
to request, to query
on Alice's side a record that corresponds
to all her friends without letting the
infrastructure find out which
are those friends.
OK, so here is how the
five works cryptographically,
we divide first of all time into epochs.
This could be longer, short, and
I will discuss this in a second.
And the idea is that at every epoch,
users register their presence
with the service and
at each epoch, other users
or the same users can actually recover
who is online in the previous epochs.
So.
Alice, when she needs to register, first
of all, takes a key she shares with Bob
Key of Alice and Bob and using
a pseudo random function, which you can
think of as a hash
function that is keyed,
basically applies that to the
time epoch
and gets to things.
First of all, she gets an ID
for.
Alice's presence at this time
period, and she also gets a symmetric
key. OK, now,
Alice, first of all, can use this
symmetric and effectively encrypt
her status using
a strong cipher and using a particular
mode of operation called
a D authenticated
encryption with associated data.
OK, and that
basically is just secure encryption.
You can think about it in this way.
And then she can make a record
of just the idea for this period
and the encrypted status and just
store it in the database.
OK, now
Bob comes along at the
next period and wants to find
out if Alice is online.
OK, so Bob, of
course, shares a key with Alice the cab.
So what Bob does is he uses the same
pseudo random function with the same key
and applies that to the previous time
period identifier and extracts
hopefully the same idea in the same key,
then using the I.D.
and a private information retrieval
protocol.
Bob can try to retrieve
the record that Alice has left in the
database.
OK, and hopefully he gets back
the record, see, and then tries
to decrypt that record with the key.
And if the decryption is successful,
it means that Alice is on line in the
previous epoch.
And furthermore.
He can decrypt the status.
OK.
Now, I hope that
everybody is half convinced that this
is secure.
This would just work and this would
defeat subject to all our assumptions,
very powerful adversaries from finding
out who's friends with whom and who's
online and who's
who's actually caring who else is
online at any point.
Now, however, there is a problem with
all this, which is associated with the
fact that this database tends to get very
large.
As I said, for every relationship
in the world, we will have to include
a record in the database.
And furthermore, we would like to include
some more records in order to hide how
many friends each person has so that each
person always basically submits 100
relationships and queries for 100
relationships as well.
So these databases tend to get quite big.
OK, and that's a problem because big
databases are less efficient
to update and query.
And we would like these time periods,
these epochs, to be as short as possible
because you have to register at one epoch
and then query at the next
epoch who was there before.
So if these e-books are a day, you just
find out the next day that someone was
online the previous day.
And that's not very useful, let's face
it.
So we need to basically do something to
improve efficiency so that these queries
and these registrations are very fast.
And as my academic grand grandfather
said, that David Wheeler,
any problem in computer science can be
solved with another layer of indirection.
He, by the way.
He is worth a round of applause
because he invented the subroutine along
with many other cool things, which is
indeed a layer of redirection.
She was also wise enough to
add that usually this creates another
problem.
So what do we do basically
is we run two versions of the protocol
that are described to you back
to back, one feeding into the other,
we define two different times of time
period, two different epochs, the long
epoch and the short epoch.
And we basically,
first of all, have Alice
and Bob store one
type of recording the long epoch into the
database. And that record has
as a status, just a public
key. So now, Alice,
basically in a long book that we envisage
to be about a day, just stores
a public key for Bob
into this database.
And then in the short ebook,
Bob can both retrieve the
public key associated with Alice
in the long period and then use that
key to query for Alice
in the short epoch.
Now, the trick here is that this public
key is shared by old friends
of Alice.
OK, so we now go from a situation
where we have one record per
relationship, which is still the case in
the long term database to just
having one record for active users,
which makes for a much shorter database.
And now that becomes tractable enough
of these periods to be as short as a
minute or even a few seconds, depending
on how many machines you throw at the
problem. So Alice can then
store using this public key in the short
term database, her actual
status. And Bob will retrieve every
minute, let's say, the status of Alice
back and make sure that she's both in
line and that he
has an up to date status for her.
By the way, the status is very important
to us because we don't just think of it
as being busy, not there or, you know,
go away for five minutes.
But we actually think of this protocol as
being able to support other
cryptographic and anonymity protocol.
So you can think of this status
information as being by the way, this
is my anonymous pseudonym for you to
contact me on this service.
Or by the way, this is actually the
address of a Tor
hidden service on which you can talk to
me.
So we were extremely keen to have this
associated information so that we can
build more secure chat protocols
on top of this presence protocol
and on the back of its properties.
Now,
cypherpunks write code, I believe.
Is that how it goes?
That's how it used to go.
And I hope that this is how it's going to
go from now on as well.
So all of this has been implemented.
We use the Pursey plus plus code
as the core for our peer protocol
and the rest of the DP five protocol
at a low level is implemented in C++
and we have python bindings that we use
as part of a cherry pie framework
and Twisted
Core to implement
all of the networking so that
we can time it and make sure
that it all works.
However, this is still a work in progress
because it has not been integrated with
any client.
So the protocol is there.
We can do all our timings.
Sadly, though, we can't actually find
who's online, who's not offline
among real users, just our
robots that do our tests for the moment.
So this is a missing part that I hope
we will be working on the next year.
And the cost of running this
is surprisingly low
for the kind of very strong properties it
offers.
Sadly, the cost per user
rise as the more users you have,
because that's how Pyaar is
OK. Now, if you have a service with,
let's say, 10000 users, it
will cost you a fraction of of a penny
per user to actually run this
protocol for a month.
If, however, you start having millions
and millions of users, it will cost you
in the order of magnitude of a dollar or
more per user to actually serve
users given rational loads.
So the takeaways here are
that, first of all, metadata
in chat protocols and social protocols
is an active target for national
security agencies and everybody else.
So we need to protect it if we're serious
about protecting communications,
secrecy, because we know how to
protect content.
But metadata is something we're not very
good yet at protecting.
OK, now private information retrieval
as a general primitive is pretty cool.
OK, you can do things that many of you
at the beginning of this talk were not
convinced were even possible.
And Deep five leverages private
information retrieval in order to
implement a specific protocol that does
private presence.
And given the characteristics
of this protocol, it is actually quite
practical and I hope that many
services will start considering using
this kind of technology prediction.
Thank you very much. We're open for
questions.
OK.
Oh, the git repository.
OK, could you line up at the microphones
for the questions?
And we also have one
question from the Internet.
Please go ahead. Our signal angel.
Hi.
So the first question or the only
question currently is how does
DP five program that Eve gets
information about Ellis or BOP, which
they don't want to share with her?
Right. So is the sun.
Yes.
OK, so if you remember
at the beginning, George showed that
Alice and Bob shared a
key.
Right. And Alice
shares a separate key with each of her
friends. The key is what enables
Bob to look up information about Alice.
But no, none
of Alice is non friends can look up
information. So Eve won't have a shared
key with Alice, and so he won't be able
to look up the information in the online
database.
OK, microphone number four there, please.
Hello. Thank you.
And I wanted
to ask if you had looked at the
the price graph looks pretty terrifying
because if you have one million users and
if one dollar per user, that's one
million dollars for months, that's quite
a lot of money. Have you looked at what
is actually causing this?
Is it the Pyaar requests?
Yeah, it's exactly right.
So it's I mean, it's a lot
of money, but it's not a ridiculous lot
of money. If you really have a million
users running a privacy
service for a subscription
rate of you charge them a buck a month
is not a ridiculous, totally ridiculous
thing to do. But it is unfortunate that
the price does go up per user.
And the answer is the reason is exactly
because of PR, because the
size of the database scales with
the number of of
users.
Right. And so every query
does a PR look
up on an increasing
size database, increasing with the number
of users and the cost of a PR query
is proportional to the size of the
database. Why is that?
Well, you can easily reason
that if the server has to
learn nothing about what record
you were interested in, then it clearly
has to process every record in
the database somehow, because if
it doesn't touch this record on disk,
then clearly you didn't ask for that
record. Right?
So the server has to process
every record in the database in
some fashion. And so it's computational
cost is proportional to the size
of the database, but the communication
cost is much smaller.
OK, microphone number one up here,
please.
Hi, thanks for the talk, was really
interesting. I have a question about
the, um, the non
collusion assumption.
Um, so in the scenario where
there's a patent server,
Alice doesn't trust the one server
to to not use the
the information requests for their own
competitive advantage.
Seems like in that instance
where you've got several different servers,
she still has to trust at least one of
them not to collude.
And why is the first assumption
not reasonable?
But the second one is if you trust
a server to to to
not to not collude, then why
wouldn't you also trust them not to to
use your in your question.
Right. So there are some I
mean, it is unsettling to some
extent that for many protocols
you cannot achieve them on your own
and you cannot achieve them just with
your communication partner.
One classic example of that is anonymity
protocols. Right? I mean, we usually have
to use relays.
And the traditional wisdom is that using
one relays is actually very fragile
because at any time this one person, if
they are corrupt to some extent or
if they're coerced, even if they were not
corrupt, might actually be able to to
leak who you're talking to.
You know, however, if you have more than
one, they would all have to be either
corrupted or collude or collude
to to do that.
So all the logic that goes
into why we trust things like mixed
networks or onion routing
to some extent or
things like that really applies here.
Why would you trust more than one in
preference to just one?
Because they might be in different
jurisdictions, because they might
actually have different operators that
will do different things to
protect the data, because it's actually
logistically quite difficult to
simultaneously go to people
and simultaneously ask for the secret
information. And remember, something I
don't mention here is that it is
perfectly forward, secure.
So going after some amount of time
doesn't work. You have to simultaneously
go there. Right.
But it is a social assumption and social
assumptions are fragile
because they rely on people like us and
our community is actually providing those
infrastructures.
And as the people from other
free software projects that rely on
those, no, this is not automatic.
If people like us do not run these
things, it's very unlikely that we'll
ever be run by anyone.
OK, microphone number six back
there, please.
How we're charting the user database
effect performance and the privacy
correct characteristics of the system.
So it would so if you charged
the user database into copses,
the performance gets better by a factor
of K, but then
only users in the same Shahd can be
friends with each other.
Right, so if your
user population naturally
falls into these shards, OK,
but in some sense, that's exactly
if that's true, that's exactly the
information you're trying to protect,
right?
You don't want someone
to observe which Shajarian which would
be visible.
Right. So that's why we
don't we try not to do that, because
if you would guard the database,
although your performance goes up, your
privacy goes quite a bit down.
OK, then we have a question from
microphone number two and two more from
the Internet then.
Hey, quick question.
Doesn't the public key that's
used to query the short
apoc database, doesn't
that allow a third party to reconstruct,
again, a graph which represents
the real one? Or is the public also
behind a picture that doesn't really make
it public but is just shared between
the users who not only Alice's
friends learn that key?
Right, because you have to go through the
first instance of the DP five
protocol to get that key
and then so only your friends have
it.
So it's a public key.
And in a sense that
Alice has the private half and other
people have the public, but not everybody
has the public if the closest friends of
the public.
So the public is not really the query
that goes to the.
It's never revealed.
Right. It's never revealed to anyone
outside that circle.
And the second round of protocol
derives keys from that key.
So it's never actually revealed in such a
way that it can link different queries
from different people.
Thank you, ma'am.
OK, our signal answer a question
from the Internet.
So there are some
similar questions
going along the line.
So the first one, what do I have to do to
use this on Jaba?
The second one, can
I use this to build a distributed DNS
system, which is I think.
Yeah. Can I use this for X.
Well the first question is more easy, so
I'll take it and then I'll leave the hard
question for you.
So what you need to do
to use that on Jaberi, understand
correctly is the question is that you
will have to spend some time integrating
this protocol to the job of presence
mechanism, which is not something we have
done yet.
We have actually spent quite some time
thinking how this could could be done.
And we foresee a
solution based on implementing a kind of
JABA protocol proxy or something like
that, working where your client
talks to some local proxy
and the local proxy actually translated
the president related event into DP five
and then translates the responses back
into Jabor events so that we can reuse
a lot of the code. However, this work is
still to be done. This integration work
is actually one of the trickiest parts of
computer security to make sure that it's
actually usable and we haven't actually
done that yet.
The question of the second question is
how can we use that to do DNS?
So it's not a very good match for
DNS because in DNS, the
whole point is that you want everybody
to know the DNS
information, right? So it's probably a
better fit, for example, for
a short messaging service.
Right. You want Alice wants to tell
Bob in particular some small
amount of information, which would be the
auxiliary data in here.
So you can imagine DP five or
very similar protocol being used
for some kind of short messaging service
where Alice is sending
a particular message to
one or a small subset of
people, her friends in this example.
But DNS, you want to send it to
everybody.
And so I don't think that's a good fit
for this protocol.
OK, two minutes left, two questions.
Microphone number one, please.
In the protocol, A-list
stars are encrypted information with an
X, and then later on, Bob
queries the database for that same X..
So what prevents the server from knowing
the relationship between Alice and Bob?
Because the lookup is done using private
information retrieval.
So Bob looks up
with X, but in a way
that doesn't reveal to the server what X
is.
All right. Right.
OK, so you're using the disputed model.
That's right. That's the magic.
OK, OK, microphone number
one again.
What happens if the database
are not synchronized?
For example, if they run out of sync for
one time and have some different
information about the same user?
Right. So that would be bad.
But it's not so bad
because as I said in the first
half, right at the end of the first half,
these pure protocols support robustness.
So if some of the servers are out of
sync, as long as not too many are out of
sync, no problem, because the robustness
properties of the peer protocol will
just think, oh, that server is giving me
the wrong data.
So as long as enough of the
servers agree, then the
the answer that the most
of the servers agree on will be the
answer returned.
OK, so it's the most it's
no value in between.
It's the most agreeing.
No, it's the most agreeing value.
Thank you.
OK, we have been asked to finish a second
time, so unfortunately, you have to close
the Q&A now.
Again, thank you very much for coming
here. Thank you very much.
And.