►
From YouTube: Private Information Retrieval & Content Routing - @ninitrava - Content Routing 2: Privacy
Description
No description was provided for this meeting.
If this is YOUR meeting, an easy way to fix this is to add a description to your video, wherever mtngs.io found it (probably YouTube).
A
Okay,
so
I
know
that
in
the
program
it
was
written
that
I
will
talk
only
about
private
information
retrieval,
but
I
decided
that's
not
the
best
solution
for
this.
Okay,
maybe
we
can
decide
together
and
I
will
present
you
a
bunch
of
cryptographic
protocols
that
may
help
with
privacy
in
in
the
setting
of
content
routing.
So
this
is
kind
of
more
of
a
exploratory
talk.
I
I'm
not
sure
any
of
this
solution
will
solve
the
problems.
A
I'm
very
happy
to
brainstorm
so
feel
free
to
ask
questions
and
interrupt
me
or
give
suggestions
just
to
set
up
the
actors.
So
we
had
this
morning
the
talk
by
one.
We
have
the
content
providers,
the
content,
consumers
and
the
content
rooters,
and
each
one
has
very
specific
roles.
So
the
providers
store
the
data
for
the
consumers
and
make
it
available
at
any
moment.
A
But
in
order
to
find
the
good
provider,
a
consumer
will
need
to
talk
to
a
good
old
with
this
indexer
r
and,
of
course,
providers
should
advertise
their
their
records
to
the
to
the
indexer
to
distributor
and
consumers
will
will
query
this
content
ids
in
order
to
find
out.
What's
the
closest
provider
for
the
data?
Okay,
so
we
want
to
do
this
preserving
privacy
of
the
content.
For
now
we
are
okay
with
the
indexer
learning.
A
A
There
are
many
flavors,
it's
not
completely
secure,
but
it
has
some
advantages.
So
deterministic
encryption
for
exact
matching
can
be
used
to
just
compile
data
while
encrypted.
We
have
some
more
relaxed
version
of
this,
which
just
shows
some
property
about
two
different
ciphertexts.
So
this
is
property
preserving
encryption
and
order
preserving
encryption,
which
is
kind
of
broken.
I
don't
recommend
it,
but
I
just
to
to
be
complete.
I
I
list
it
here.
A
So
the
drawbacks
of
such
solution
is
that,
of
course,
they
leak
repetitions
on
on
the
queries.
If
you
query
twice
the
same,
the
same
content
id
then
the
the
router
will
see
that,
because
it's
deterministic-
and
there
are
some
existing
attacks
in
the
literature
that
allows
to
recover
all
the
data.
If
we
have
many
queries
or
if
some
conditions
are
met,
but
of
course
hiding
everything
about
the
data
implies
accessing
the
entire
data
and
communicating
something
in
the
size
of
the
entire
data.
So
we
have.
A
We
need
a
trade-off,
another
more
recent
tool
that
we
can
use
here.
It's
fully
homomorphic
encryption.
This
techniques
allow
to
encrypt
the
data
in
such
a
way
that
further
on
someone
can
perform
computation
on
the
ciphertext
and
the
result
will
be
encrypted
as
well.
So
the
one
who
has
the
secret
decryption
key
can
just
take
the
result
and
like
this
cipher
text
and
find
out
the
result
and
nobody
else
so
this
offers
nice
privacy
properties.
A
There
is
no
interaction
between
the
two
actors
when
retrieving
the
data,
but
as
we
know
it
today
is
not
that
efficient
for
any
kind
of
queries,
so
maybe
for
our
basic
needs.
We
can
find
something
in
it
and
it
may
have
costly
communication,
because
if
we
want
to
hide
everything,
this
encrypted
result
may
be
as
long
as
all
the
database
like
there.
We
can
find
something
as
well
and
what
about
the
key
management?
A
Okay,
we
have
multiplied
computation,
which
is
an
interactive
kind
of
cryptographic
scheme,
a
family
of
interactive
schemes,
and
this
allows
for
two
or
multiple
users
to
perform
a
computation
or
their
personal
local
data,
without
revealing
anything
about
their
inputs
and
learning
only
the
outputs.
So
I
thought
that
we
may
use
this
in
the
context
of
a
consumer
talking
to
a
router
and
ask
them
to
interact
such
that
the
communication
is
smaller
than
the
entire
database
and
the
the
router
will
not
learn
any
inputs
from
the
consumer
and.
B
A
A
No,
the
router
has
a
huge
set
of
all
the
correlated
data
with
the
indexes
and,
at
the
end
of
the
day,
private
intersection
will
make
the
the
consumer
learn
only
if
the
intersection
between
their
set
and
what?
What
is
on
the
router
side-
and
we
want
more-
we
want
to
learn
the
label
with
respect
to
to
the
intersection,
because
the
intersection
doesn't
show
show
the
consumer
where
to
go
to
it,
give
the
data,
so
we
can
do
that
with
private
set
intersection.
A
A
No
question:
okay,
let's
start
with
searchable
encryption,
so
index
based
searchable
encryption,
it's
a
primitive
that
I
think
it.
It
has
some
ears
now
and
it's
based
on
some
keywords
that
are
used
to
search
and
updates
that
allow
the
the
data
store,
the
the
one
who
stores
the
data
to
to
decrypt
the
exact
information
that
the
consumer
is
looking
for.
So
each
query
allows
for
some
partial
decryption.
A
So
more
precisely,
everything
is
encrypted.
Here
we
have
the
encrypted
content
id.
We
have
this.
We
don't
have
yet
until
we
have
a
query-
and
this
is
the
provider
id
like
where
to
find
the
data
which
is
still
encrypted,
but
it
can
be
decrypted
when
we
have
a
query,
so
the
consumer
sends
a
trapdoor
which
is
actually
a
decryption
key
for
this
part
of
the
table
for
exactly
that
line
and
the
router
can
decrypt
that
and
send
back
and
how
it
finds
that
the
the
consumer
also
has
to
send
this
encrypted
context.
Content.
A
That
is
a
deterministic
encryption
and
compare
to
know
what
line
it
should
decrease.
Okay,
so
generically
this
has
some
leakage.
As
I
said,
if
it's
static,
we
know
the
search
pattern.
We
only
see
the
repetitions
and
things
like
that
and
in
a
dynamic
database
that
allows
for
updates,
we
can
reveal
even
more
to
the
to
the
router.
Maybe
that's
not
a
problem.
In
our
context,
I
think
here
we
are
safe
because
it's
the
provider
who
up
up
updates
the
the
these
records.
So
it's
fine
okay.
A
So
now
I
try
to
imagine
this
generic
cryptographic
protocol
for
our
scenario.
Maybe
it's
very
simplified
yeah.
Let
me
know
what
we
miss
here.
So
we
have
the
provider
that
has
to
encrypt
their
their
table
of
what
they
are.
Storing
or
those
are
all
providers
that
put
information
in
this
table
and
send
them
to,
but
they
have
to
send
it
encrypted.
A
How
can
we
coordinate
between
the
consumers
and
the
providers,
so
we
have
the
same
trapdoor
the
encrypted
content
id
is
done
under
the
same
key
in
some
way
or
let's
say
those
are
hashes.
We
can
solve
that
with
hashes
because
it
has
to
be
deterministic
and
we
never
decrypt
them
so
yeah.
This
can
be
hashes,
but
still,
how
do
we
encrypt
the
provider
id
and
obtain
the
trapdoor?
C
A
C
C
C
A
You
can
re-encrypt,
you
can
change
the
trapdoor
and
inquiry
and
send
it
again
to
the
database
to
the
router,
so
the
router
doesn't
know
it's
the
same.
If
you
are
worried
about
your
record
being
already
in
clear,
I
think
that's
an
idea,
yeah
yeah
yeah.
I
think
there
are
yeah
interesting
things
that
we
can
look
at
here.
A
A
A
So
the
limitation
of
fhe
is
that
we
have
to
write
up
the
computation
as
a
boolean
circuit
and
yes,
that's
sufficient,
but
maybe
not
the
best
for
practice
and
also
I
better
execute
more
more
recently
and
that's
kind
of
makes
a
simple
computation
here.
I
took
like
compared
to
integrals
of
two
bits
representation
into
a
big
circuit
like
we
need
to
evaluate
this
circuit
over
encrypted
data
and
yeah.
That's
that's
not
ideal
in
practice,
so
that's
so
becomes
like
more
popular
as
a
problem
and
there
are
more
compilers
out
there.
A
So,
probably
that's
that's
a
direction
we
can
look
at
and
I
wanted
to
present
two
new
schemes
that
may
be
interesting
here.
It's
tfhe,
which
is
a
an
fhe
that
allows
for
a
selector
gate,
which
is
not
usually
the
case
in
fhe
schemes.
So
we
can
evaluate
this
kind
of
gate
homomorphically,
and
this
makes
this
comparing
two
integrals
of
two
bits:
less
expensive,
that
in
the
boolean
secret
I
was
just
showing
you
before
you
do
some
yeah.
You
use
this.
A
A
This
is
the
like
popular
value
that
they
choose.
So
actually
it's
just
expressing
some
function
as
a
polynomial
in
order
to
be
able
to
do
only
like
arithmetic
operation
on
on
top
of
the
the
encrypted
values.
So
you
can
approximate
a
function
quite
close
to
a
polynomial
and
t
decides
the
precision.
So
the
degree
of
the
polynomial
here
t
so
more
precision
you
want
bigger.
Your
polynomial
is
like
your
degree,
it's
higher,
so
you
have
more
computation.
A
Like
in
the
approximation
of
this
suit,
oh
the
one,
the
other
one,
because
it's
called
torus
fhe,
it
uses
some
fancy,
toys,
structure,
yeah
and
those
are
the
names
of
the
authors.
I
don't
remember
them:
okay,
yeah
they're
here
here,
they're
sick,
I
guess
okay,
so
this
is
the
landscape
of
fully
homomorphic
encryption
schemes.
A
They
become
more
and
more
performant
and
what's
impressive
about
new
libraries
is
that
they
optimize
and
they
have
these
good
compilers
in
order
to
make
any
secret
very,
very,
like
specific
circuits,
very
efficient
okay.
So
I
just
recap
how
we
do
a
comparison,
a
simple
comparison,
the
naive
way
with
old
schemes.
A
A
A
A
C
C
A
C
A
C
B
A
Okay
and
mpc
the
interactive
solution-
I
was
mentioning
so
how
it
works.
We
have
multiple
parties,
they
all
have
their
inputs.
We
want
to
compute
collaboratively
with
a
function
on
all
the
inputs
and
to
learn
the
result,
or
maybe
we
can
also
distribute
parts
of
the
result
to
some
partisan
others
and
the
goal
is
to
preserve
the
privacy
of
each
input
here
for
the
parties
and
the
correctness
of
the
computation,
of
course.
A
A
What's
the
adversarial
power,
it
can
be
corrupting
a
lot
of
the
parties
or
not.
Is
it
adaptive
or
not
on
the
network
model?
How
are
connected
how
the
parties
are
connected
between
if
it's
the
star
network,
it
may
be
easier
than
if
it's
like
just
random,
to
have
the
meaning
of
the
security
for
such
protocols,
so
they
are
complicated
protocol.
The
literature
has
so
many
flavors
of
them
and
the
ones
that
are
the
most
efficient
use.
A
Some
pre-processing
and
pre-processing
allows
to
defend
all
the
cryptographic
steps
all
the
operations
that
are
expensive
to
to
some
offline
phase,
where
the
parties
are
just
generating
some
correlated
randomness
between
each
other.
So
then,
the
online
phase,
when
you
compute
exactly
what
you
need
it's
very
fast,
it's
it's
performant
and
the
reconstruction
phase
decides.
If
you
give
the
result
to
some
parties
or
to
others
like
that's,
that's
separate,
okay,
so
that's
the
general
overview
of
mpc
and
about
the
advisory
so
adversary.
A
A
Then
he
is
allowed
or
malicious,
so
active.
So
it
looks
at
like
the
the
the
intermediate
steps
and
change.
Some
value
is
not
consistent
with
what
inputs
originally
and
change
things
on
on
the
fly
in
order
to
learn
more
information
and
what
we
call
an
fhe
in
mbc,
honest
majority,
is
that
it
corrupts
only
a
smaller
fraction
of
the
parties
like
the
minority
of
them,
and
dishonest
majority
means
that
the
adversary
can
corrupt
more
than
half
of
the
parties.
A
Okay,
also,
we
want
output
delivery,
which
are
schemes
that
are
even
harder
to
achieve
because
in
in
this
mpc
protocols,
at
any
point
the.
If
the
adversaries
are
more
than
half
of
the
network,
they
can
just
avoid
and
everybody
the
honest
parties
will
not
be
able
to
recover
any
result.
So
that's
something
that
wastes
a
lot
of
computation
and
interaction.
A
A
Yeah,
those
are
the
conditions
so
that
that's
why
I
would
believe
this
is
the
the
scheme
we
are
looking
for.
We
don't
want
to
be
like
abandoned
in
the
middle
of
the
protocol
and
not
have
any
result
right
yeah,
I
don't
know
so.
There
are
two
ways
to
achieve
two
main
ways
to
achieve:
mpc
one
is
from
secret
sharing,
so
this
is
mostly
designed
for
arithmetic
circuits
and
the
like
the
diffic.
The
efficiency
is
influenced
by
the
number
of
multiplication.
So
that's
the
overhead
more
multiplication,
so
more
rounds
of
interaction.
A
Okay,
I
will
skip
this
because
I'm
going
to
too
many
details
and
the
second
way
to
to
do
a
multiply,
the
computation
or
more
two-party
computation
originally,
is
by
modeling
your
computation
as
a
boolean
circuit
and
kind
of
encrypt,
all
the
gates
in
the
circuit-
and
this
is
a
guideball
circuit
known
as
that-
and
the
limited
factor
is
not
the
number
of
gates
but
the
sacred
depth.
So
the
non
like
paralyzable
gates,
yeah
I'll,
skip
this
okay
yeah
any
ideas.
So
far
for
this
one.
C
A
A
C
B
B
A
A
A
A
A
A
Communication
is
more
expensive
in
the
information
theoretic
part
and
better
communication
in
the
computational
one
at
the
cost
of
some
pre-processing
in
general
and
some
schemes
I
was
looking
at
for
two
servers.
We
have
communication
in
of
order
and
to
here
one
over
three
and
for
a
case
servers.
We
have
this
communication
and
so
on
and
in
the
computational
part,
we
have
kind
of
better
con
communication
here
in
all
log
n
to
the
a
where
a
is
some
parameters
that
we
can
tune.
A
A
A
So
there
is
a
theorem
of
a
lower
bound
that
says
that
the
expected
computation
for
the
servers
all
together,
probably
is
like
o-n,
at
least
so,
not
very
promising,
but
we
can
do
improvements
via
pre-processing,
so
doing
some
of
the
work
offline
amortization.
When
we
have
many
queries,
offline
computation,
which
is
kind
of
people,
sensing
yeah,
so
yeah,
that's
the
hope.
I
think
that's
the
open
question
and
in
the
computational
period
as
well,
maybe
finding
better
assumption
that
gives
better
communication,
and
this
was
exactly
from
some
recent
paper
at
eurocrypt
this
year.
A
A
A
C
A
A
A
C
B
C
A
Okay,
should
we
move
on
okay,
now
private
set
intersection
using
fhe?
I
was
really
happy
to
see
the
talk
this
morning
of
private
set
intersection,
because
I
have
something
very
similar
that
looks
to
me
adapted
for
this
setting.
So
what
square
was
said
intersection
we
already
saw
a
receiver
has
like
I
will
call
them
receiver
and
sender
as
in
in
the
original
protocol.
A
A
We
have
here
like
a
set
that
may
have
the
elements
of
the
receiver
and
some
label,
which
is
the
router
like
the
no
the
provider
id
okay,
so
we
can
do
like.
Instead
of
looking
at
this
table,
we
encode
it
as
a
polynomial
that
has
nice
property.
We
interpolate
in
such
a
way
that
the
polynomial
evaluated
in
each
of
the
elements
of
the
set
will
have
the
exact
label
as
a
result
and
what
the
receiver
will
do
will
encrypt
their
query.
A
Their
element
of
data
set
send
it
encrypted
and
because
I
have
a
polynomial
which
is
a
function
and
a
fully
homomorphic
encryption
scheme,
I
can
now
evaluate
this
polynomial,
that
is
of
degree,
my
my
set
size
in
the
encrypted
values
from
the
receiver
and
what
I
obtain
exactly
the
label
corresponding
but
encrypted.
So
I
obtain
encryption
of
two
right.
A
A
A
The
communication
is
our
log
n,
because
receivable
will
send
this
log
n
powers
of
a
and,
if
we
don't
need
circuit
privacy,
which
means
that
we
don't
have
to
protect
the
sender
against
receive
the
receiver,
so
the
receiver
learns
a
little
bit
more.
We
have
better
fhe
parameters,
so
we
can
exploit
that
okay.
So
these
are
the
values
from
the
paper
that
introduced
this.
A
C
A
C
A
So
if
we
don't
want
to
compute
a
function
that
has
degree
the
size
of
of
the
set
for
the
sender,
we
can
use
cuckoo
tables
where
we
pick
some
function,
some
hash
function
and
hash
and
place
the
elements
in
in
our
set
in
a
table
according
to
the
result
of
this
hash.
So
this
hash
gives
you
the
index
where
to
place
the
hashed
value
a
so
here.
A
So
what
we
do,
when
n
is
sent
again
to
the
second
place,
we
apply
the
cuckoo
technique,
so
we
like
give
away
the
previous
b
there
and
pick
another
hash
for
it.
H1
was
two
so
h3
and
put
it
in
the
first
and
we
apply
it
at
it,
and
there
are
some
theorems
that
this.
This
will
always
finish
if
we
pick
as
many
indexes
here
bigger
than
the
the
size
of
the
receiver
set
okay.
So
what
do
we
save?
Here?
A
We
have
to
compare
b
on
the
first,
the
encryption
of
b.
We
have
to
compare
it
only
with
the
first
line
and
we
are
sure
if
it,
if
there
is
in
the
intersection,
it
will
be
in
the
first
line,
because
of
course
we
use
one
of
the
hashes
here
and
here
we
use
them
all
yeah,
and
this
is
a
polynomial
of
really
like
lower
degree.
C
A
A
So
yeah,
I
guess
if
we
use
this
in
combination
with
the
fhe
private
set
intersection
yeah
how
it
works.
As
I
said,
the
lines
are
functions
which
have
the
lower
degree
than
this
set,
but
we
have
four
of
them
and
we
evaluate
f1
only
on
on
the
first
cipher
text,
f2
on
the
second
one
and
so
on,
and
send
the
result
for
the
decryption.