►
From YouTube: Threshold Factoring from Factoring - Abhi Shelat
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
A
Schuler
Josh
and
condi
sorry
Megan,
yes,
Megan,
and
it
also
involves
a
collaboration
with
Muthu
and
car
meet
and
they
are
from
their
company
lahir,
oh
okay,
so
the
goal
of
this
is
threshold,
factoring
from
factoring
so
we'd
like
to
create
an
RSA
modulus
n
and
the
only
assumptions
we'd
like
to
use
our
factoring
assumptions
and,
let's
say
symmetric
primitives
like
shower
256,
that's
kind
of
a
doctrinal
question:
that's
driving
this,
but
we're
not
really
tied
to
it.
The
main
reason
I
want
to
phrase
it.
A
That
way
is
that
we
are
trying
to
see
how
well
we
can
do
with
this
approach
without
using
something
like
lwe.
So
there
are
some
nice
approaches
with
even
just
additive
homomorphic
encryption
that
will
substantially
improve
one
factor
of
this
construction,
but
at
the
cost
of
some
other
factors,
so
in
particular
for
this
application.
A
It's
not
clear
that
if
you
want
to
use
a
vdf
for
for
consensus
that
that
you
want
this
sort
of
assumption
Ellucian,
you
want
extra
assumptions
that
that
that
make
there
were
in
there
and
that,
then
you
have
to
make
analysis
about
what
l-dub
you
parameters
are
etc.
So
this
is
how
good
can
we
do
just
using
sort
of
factoring
assumptions?
The
other
caveat
is
that
we
would
like
to
achieve
n
plus
n
minus
1
security,
and
this
is
this
is
again
for
the
application,
but
also
at
hid.
A
It
handles,
for
example,
questions
like
Joseph's
question
about
civil
attacks.
Mootoo
made
a
nice
point,
which
is
that
if,
when
you
have
n
minus
1
security,
all
you
really
sort
of
need
is
one
honest
participant,
so
even
if
they're
a
bunch
of
symbols
that
are
controlling
several
accounts
and
so
forth.
As
long
as
you
have
one
honest
participant,
then
the
privacy
of
the
company
computation
is
secure
and
of
course,
Diogenes
spent
the
whole
lifetime.
Looking
for
that,
one
on
this
part
discipline,
and
certainly
they
didn't
look
in
any
aetherium
for
him
and
find
them
there.
A
So
it's
not
clear
if
you
could
find
an
honest
person,
but
but
but
we
can
hope
so.
This
talk
is
going
to
discuss
the
semi,
honest
version
of
this
construction
I'm
just
going
to
highlight
this
is
a
work
in
progress.
We
don't
I
thought
we'd
have
a
better
paper
at
this
point.
We
don't
have
a
paper,
we
can
post
a
print
and
our
and
our
implementation
is
like
modular,
but
not
glued
together.
A
So
the
part
that
I'm
not
going
to
talk
about
is
how
every
choice
it
was
kind
of
made
here
really
helps
us
build
a
malicious
version
of
this
protocol
with
very
little
overhead,
so
other
approaches
have
have
basically
user
knowledge
as
sort
of
a
heavy
hammer,
and
that
requires
a
pretty
large
sur
knowledge
statement
about
what
you're
doing
what
we're
planning
to
do
is
actually
it's
it's
it's
it's
it's!
It's
surgical
as
I'd
like
to
think
and
built
on
our
work
from
our
ECDSA.
A
We
have
a
nice
way
of
getting
malicious
security
for
multipliers
in
that
case.
So
what
are
the
big
wins?
So
here's
really
how
we
improve
over
this
I'll
present
some
of
the
prior
work,
but
at
the
high
level
we
we're
using
more
efficient
primitives,
in
particular
the
multiplier
and
that
allow
and
in
in
combination
with
this
other
observation
that
allows
us
to
have
fewer
candidate
trials.
A
So
when
you're
producing
RSA
just
like
when
you
do
on
your
SSH
key
gen,
your
computer
is
basically
picking
a
random
number
and
testing,
whether
it's
prime
doing
it
again,
multiplying
in
and
then
producing
that
results.
So
this
process
inherently
requires
sampling.
So
so
we
have
to
do
a
bunch
of
candidates
and
then
we
have
to
try
and
check
if
they
work
and
when
you
do
them
in
the
plain
text
like
ssh-keygen
and
none
of
these
things
that
we're
doing
makes
sense.
A
But
when
you're
thinking
about
a
secure
computation
for
the
same
thing,
actually
using
a
different
algorithm
for
the
same
process
is,
is
it
generally
always
wins
when
it's
something
like
this?
That
has
a
lot
of
algebraic
structure.
So
we
have
some
observations
that
allow
far
fewer
candidate
trials
and
and
finally,
we're
basically
attempting
to
achieve
less
communication
per
trial.
So
the
three
of
those
things
are
basically
what
get
us
improvements
over?
A
What
the
status
quo
work
is,
and
the
major
idea
come
from
two
basic,
very
simple
observations
which
nobody
seems
to
have
used,
but
we
are
using
them
aggressively.
The
first
is
the
Chinese
remainder
theorem,
so
for
our
multiplier
we
use
the
Chinese
remainder
theorem
I'll
show
you
exactly
how
that
works,
but
it
gives
you
a
pretty
good
factor
improvement.
Even
our
own
ECDSA,
we
had
a
threshold
ECDSA,
a
series
of
works
there.
A
We
didn't
use
this
observation
and
that
immediately
gives
you
a
factor
for
improvement
in
communication,
which
is
quite
big
so
now,
given
that
the
moduli
are
much.
Those
are
256-bit
moduli.
Now
that
the
moduli
are
our
thousand
bits,
two
thousand
bits,
then
this
thing
gives
you
like
a
factor
of
16.
The
second
thing
is
more
constructive,
so
you
can
look
at
civic
as
one
way
or
the
other
you
can
either
looking
at
is
building
up
a
candidate
that
satisfies
all
your
constraints
or
you
can
look
at
it.
A
Sort
of
like
the
the
way
politics
are,
you
put
something
out
there
and
everybody
tries
to
tear
it
down
and
so
we're
trying
to
be
constructive
in
our
approach,
and
it
turns
out
that
that
actually
helps
and
I'll
explain
that
sort
of
later
on,
but
that's
the
high-level
idea,
if
you
want
to
keep
that
around
as
we
go
through
this,
so
this
is
so.
This
is
a
very
popular
topic,
starting
from
Binet,
Franklin
and
Frankel.
A
I
forget
the
M,
but
the
Y
is
young,
starting
from
the
like
right
around
the
early
late
90s,
a
lot
of
work,
basically
on
on
how
to
do
this.
These
last
few
right
here,
they
are
actually
closer
to
implement
implementable.
In
fact,
this
one
and
this
one
both
have
implementations
of
their
approaches
and
so
again
like
we're,
making
quite
a
bit
of
progress.
I
will
basically
start
from
what
I
want
to
do
is
start
from
this
right
here,
the
Binet
Franklin
approach.
A
They
lay
out
a
protocol
for
doing
this
and
it's
it's
kind
of
the
protocol
that
everybody
is
kind
of
building
upon,
and
there
are
a
few
different
ideas.
But
this
is
the
basic
idea:
there's
the
protocol
is
in
like
sort
of
three
phases:
we're
gonna
sieve.
Do
some
sort
of
civic
and
different
people
use
different
approaches
for
that
in
order
to
get
some
candidate
P
and
a
candidate
Q
we're
going
to
multiply
so
that
sitting
can
be
very
generic.
In
fact,
you
don't
have
to
do.
A
You
can
just
pick
a
random
P
that
could
be,
you
know
null
saving,
but
you
can
do
some
sort
of
trial
divisions
to
sort
of
speed
things
up
then
you're
going
to
multiply
them
again.
This
is
a
secure
computation,
so,
at
the
end
of
this,
we'll
have
shares
of
n
and
then
we'll
finally
reconstruct
N
and
finally,
we'll
do
some
by
primality
testing
right
here.
We'll
run
this
n
through
sort
of
some
tests
using
like
this
notation
right
here,
bracket,
P
and
bracket
Q
means
share.
A
A
We
build
on
this
approach
and
many
of
the
implementations
all
build
on
this
type
of
approach,
but
just
to
be
sure,
I
wanted
to
I
wanted
to
highlight
some
of
the
other
approaches
that
might
be
floating
around
your
head.
Why
can't
we
do
it
this
way?
Why
can't
we
do
it
that
way?
What's
wrong
with
this
approach,
so,
for
example,
dam
guard
Mickelson
they
have
a.
They
of
course
also
follow
this
same
kind
of
approach.
A
Here,
they're
going
to
create
a
few
candidates,
they're
going
to
do
some
prime
ality
tests
and
then
they're,
going
to
what
I
didn't
mention
here
after
at
the
end.
Here
is
basically
ZK
proof
to
basically
prove
that
the
result,
once
you
have
a
really
good
result,
a
good
end,
then
you
can
basically
prove
that
that
the
run
of
that
instantiation
was
correct
and
if
you
do
their
work
commitments,
if
you
commit
your
inputs
in
the
head
of
time,
then
this
approach
is
the
best
way
to
get
malicious
security
in
our
opinion.
A
So
it's
again
the
same
the
same,
the
same
sort
of
rough
rough
sketch
the
observation
they
make,
which
is
a
very
interesting
one,
and
if
we
can,
this
is
an
open
challenge.
I,
like
the
approach
that
the
previous
speaker
did
about
here's
a
challenge.
If
we
can
get
something
like
this
to
approach
to
work,
then
we
can
get
a
factor
of
left
for
820
improvement
over
what
we
have
so
generally.
A
We
have
some
shares
of
P
and
some
shares
of
Q
and
we
multiply
them
to
get
P
Q
and
we
can
do
by
prime
allottee
when
we
have
this
type
of
thing.
But,
of
course,
when
you
do
this
on
the
plain
text,
what
you
actually
do
is
some
sort
of
Rabin
Miller
test
on
this
P,
and
so
why
can't
we
do
that
in
a
secure
computation?
A
In
fact,
that's
a
question
that
was
answered
by
the
ACS
paper,
a
combination
trooper
the
cns
forgotten,
the
eighth
Alzheimer,
yes,
but
nd
m10
is
an
improvement
of
that
approach
and
here's.
The
reason
why
that's
tough
is
because
this
rabin
miller
requires
you
to
do
a
computation
of
this
form.
A
to
the
P
minus
1,
mod
p
and
the
thing
is
P
is
basically
in
a
sort
of
shared
State,
so
AC
s
was
basically
proposing
using
a
circuit
and
in
fact
one
of
our
very
first
papers
on
militias
two-party,
secure
computation.
A
We
basically
implemented
modular
exponentiation,
this
type
of
thing
and
it's
it's
it's
billions
and
billions
of
gates.
If
you
do
it
using
just
boolean
circuit,
so
you
have
to
do
something
better.
If
you
one
need
to
do
this,
you
know
is
this
is
something
you
have
to
do
several
times
and
so
forth.
Once
maybe
you
could
do
it
three
thousand
times?
It's
not!
So
not
so
clear,
so
they
had
a
very
nice
observation
on
how
you
can
do
this
type
of
thing.
Using
an
approximate
multiply,
an
approximate
base.
A
Right,
no!
No,
if
this
is
it's
so
bullion
circuits-
are
super
super
fast
now
like
in
2011.
We
took
like
maybe
an
hour
or
two
or
something
like
that.
So
today,
they're
much
I
mean
it's
it's
faster,
so
it
could
be
done
in
a
few
in
tens
of
minutes.
Maybe,
but
the
point
is
we
have
to
do
this
Rabin
test
several
thousand
times
in
parallel,
so
I
mean
the
parallelism,
helps
but
yeah
right
right.
A
I'm
actually
like
XKR,
is
the
best
approach
to
that
like.
We
could
actually
do
something
like
this.
This
would
be
a
brute-force
approach,
but
I'm
an
argue.
It's
dominated
by
what
we're
doing,
and
it's
and
you'll
see
it's
dominated
by
this
particular
approach
is
also
dominated,
so
the
whole
approach
was
how
to
try
to
test
P
by
itself
and
then
Q
by
itself
and
then
combine
a
P
and
Q,
and
they
had
a
very
nice
approach.
Using
this
like
a
pro,
you
can
basically
do
modular
reductions,
mod
P
with
some
approximate.
A
You
could
do
an
approximation
that
gets
you
into
a
factor
of
plus
or
minus
four
times:
P,
okay,
and
so,
if
you're
familiar
with
the
paper,
this
will
make
sense.
But
it'll
get
you.
It
gets
you
an
approximate
version
of
what
this
number
is,
and
so
you
only
have
to
check,
let's
say,
roughly
16
possibilities.
Okay,
so
that's
a
great
improvement,
but
it's
still
a
degree
16
polynomial
that
you
need
to
evaluate
as
an
arithmetic
circuit.
Okay.
A
They
showed
that
just
one
test
basically
shows
that
if
it
passes
then
its
prime
with
it
for,
in
the
average
case
for
the
size
of
Prime's,
that
we
care
about
its
its
prime
with
probability
2
to
the
minus
38,
which
is
awesome,
you
don't
have
to
do
a
repetition
of
something
like
the
the
Ben
Franklin
test,
so
they
the
thing
is
to
get
to
like
the
security
parameter
that
we
need.
You
kinda
have
to
repeat
it
like
twice
or
three
times,
and
so
still
you
get
into
several
multiplications
just
to
check.
A
1P
and
you'll
see
that
so
already,
if
you
do
the
math
remember
the
number
16
times
3
is
roughly
48
to
check
1p.
Then
you
have
to
check
another
Q
right
there.
So
that's
kind
of
like
96
multiplications.
Keep
that
number
in
mind.
96,
we're
gonna
have
a
number
lower
than
that
for
our
approach
and
you'll
see
why
this
is
dominated
currently.
So
that's
not
to
say
this
is
what
I
when
when
very
enthusiastic
number
theory
like
math
students
come
into
my
office
and
ask
for
some
problems.
I
tell
them
to
read
this
paper.
A
I
say
there's
room
here:
probably
you
can
like
Whittle
these
things
down
if
you
can
get
it
down
to
like
from
four
possibilities
plus
or
minus
four
to
like
maybe
two
or
three.
If
you
have
a
tighter
analysis,
this
might
become
a
winner.
So
so
there's
there's
approach
here,
I'm
putting
it
out
as
as
a
possible
approach.
Currently,
as
it
stated,
we've
taken
a
different
one
for
these.
For
these
calculations.
A
So
they
do
an
analysis,
the
specific
test
they
do
with
the
other
tests.
They
show
that
on
average
right
so
you're
right,
maybe
what
you're
saying
is
on
average.
It
could
be
something
similar.
It
doesn't
because
so
in
the
now.
In
their
particular
analysis,
they
require
this
divisibility
property
of
P
minus
1,
not
being
divisible,
so
they
requires
us,
they
have
a
specific
divisibility
criteria
and
they
specifically
point
out
it
doesn't
work
for
by
primality
tests.
A
You
know:
okay,
okay
yeah,
so
it's
like
P,
minus
1
is
a
might.
Yeah
I'll
follow
up
with
you
it
with
the
exact
claim
they
make.
I
haven't
verified
I've
just
taken
their
word
for
it
so
yeah,
that's
that's.
That
would
certainly
help
us.
Okay,
yeah
so
has
I
at
all.
They
have
another
approach
to
this
and
I
just
want
to
outline
it.
So
what
they
are
basically
exploiting
is
additive
homomorphic
encryption.
They
are
really
taking
that
and
sort
of
and
getting
great
multiplications
as
a
result
they
require
in
their
implementation.
A
They
require
the
Paille
assumption,
so
this
is
kind
of
doctrinally
different
than
ours.
You
need
to
make
a
stronger
assumption
to
get
this
also
PI
a
is,
is
not
especially
efficient,
so
in
one
particular
so
the
way
their
protocol
works
is
before
these
are
the
three
basic
steps
right.
They
have
to
do
this
key
setup.
This
distributed
key
setup.
This
is
so
they
use
PI
a
as
well
as
elgamal.
Let's
put
that
down
there
as
well,
so
they
have
to
do
a
distributed
key
setup.
That's
kind
of
it's
like
a
messy
thing.
A
So
they're
using
essentially
everybody,
creates
their
own,
their
own
PI
a
key
and
then
they
kind
of
luck.
Threshold
PI,
oh
sorry,
not
threshold,
it's
like
and
everybody
creates
their
own
and
and
they
do
pairwise
so
basically
to
do
multiplications.
They
are
using
this
additive
homomorphism.
So
if
boy,
if
P
and
Q
is
you
know
a
plus
B
times
a
plus
a1
plus
a2
times,
b1
plus
b2,
they
convey
I
can
basically
encrypt
my
share,
give
it
to
you,
you
can
raise
it
and
do
some
summations
and
that
could
basically
work
out.
A
That's
what
they
do
and
I
guess.
That's
all.
I
really
need
to
say
is
that
they're
using
PI
a
to
do
multipliers
and-
and
they
also
have
a
very
careful
malicious
security
argument
based
on
having
el-gamal
ciphertext,
that
sort
of
parallel
that
got
to
run
in
parallel
to
the
entire
computation,
and
then
they
prove
equality
between
these
two,
so
I
just
wanted
to
put
it
out
there.
A
I
think
lwe
will
now
be
a
better
mechanism
for
this,
so
it'll
be
dominated
by
whatever
approach
uses
lwe
but,
as
I
said
in
slide,
2
I
basically
put
that
put
that
concern
aside
so
yeah.
So,
finally,
this
is
the
latest
approach.
This
is
from
last
year,
and
this
is
what
sort
of
initiated
our
look
into
this.
This
is
flop
and
they
basically
do
again
candidate.
They
do
exactly
the
same.
A
You
can
look
through
their
protocol
and
now
basically
parse
it
into
these
into
these
basic
into
bit
into
basic
blocks
like
so
generation,
construction
division
and
prime
allottee
testing,
and
their
big
observation
is
to
go
back
to
a
paper
by
Gilboa
in
the
late
90s,
who
also
considered
the
problem
of
threshold
r
of
RS
a
generation
and
he
created
an
integer
multiplier
from
from
basic
OT
building
blocks.
So
here
is
what
the
primitive
is.
You
have
an
A
and
a
B,
and
you
want
to
multiply
so
party.
One
party
has
a
one
party
SB.
A
You
want
to
multiply
them
so
and
share
results
so
that
essentially,
the
two
two
parties
have
additive
shares
of
the
product.
That's
the
building
block
and
what
what
you
Bo
is
going
to
do
is
to
build
this
out
of
1
out
of
2
ot,
so
remember,
oblivious
transfer
of
essentially
one
party
basically
has
two
inputs
here.
The
other
party
has
a
single
bit
right
here
and
essentially,
if
I
put
0
I
get
the
0
input.
A
If
I
put
1
as
my
input,
I
get
1
as
the
input
and
the
standard
standard
security
properties,
you
only
get
one
and
the
other
party
doesn't
know
which
one
you
picked
so
with
something
like
this.
The
way
you
can
build
a
multiplier
is,
you
can
basically
have
one
of
the
parties
here
basically
put
either
RI
or
B
plus
RI,
and
this
RI
is
basically
a
different
RI
every
time,
so
that
would
be
r1.
This
is
r2
b
plus
r2.
This
would
be
like
RL
and
b
plus
RL.
A
A
Didn't
I
do
that
did
I
we're
good,
okay,
so
oblivious
transfer?
This
is
a
two
party
protocol.
One
party
basically
has
two
inputs:
a
zero
input
and
a
one
input
and
they
put
strings
there.
They
can
put
whatever
they
want
there
and
then
the
other
party
just
has
a
single
bit
input.
It's
a
0
or
a
1
here
and
essentially
the
receiver
party.
They
get
basically
the
they
get.
Essentially
if
their
input
was
0,
they
get
the
0
and
put
if
their
input
was
1.
A
A
So
what
I
want
to
say
here
is
that,
what's
what's
very
cool
is,
if
we
run
it
like
this.
Essentially,
this
party
is
going
to
basically
take
our
I
times
2
to
the
I.
That's
going
to
be
their
share,
so
this
is
going
to
equal
C,
2
and
C.
1
is
just
going
to
be
the
sum
of
si
times
2
to
the
I,
so
this
is
basically
the
multiplier.
A
You
run
L
copies
of
1
out
of
2
OT
with
these
as
inputs
and
these
as
outputs,
and
these
are
your
basic
shares
to
see
why
that
basically
works.
So
imagine
so
I
have
a
here
and
if
my
a
I
was
0,
then
I'm
basically
going
to
get
RI
and
if
my
a
1,
if
I
my
a
I,
is
one
that
I'm
basically
going
to
get
B
plus
RI.
So
this
is
what
si
is
equal
to.
A
A
A
Plus
RI
times
2
to
the
I
okay.
So
over
here.
Basically,
if
you,
when
you
sum
all
of
this
up,
this
party
basically
gets
a
times
B
plus
RI
times,
2
to
the
I
for
all
I
and
the
0
case.
You
get
this
term
in
the
one
case
you
get
this
other
term
and
over
here
remember.
This
person
share
was
basically
RI
times
2
to
the
I.
So
when
you
add
them,
essentially
these
two
terms
cancel
out
and
the
product
is
a
B.
Does
that
make
sense?
A
Ok,
so
the
1-
and
this
is
the
critical
point
here
why
the
CRT
helps
so
to
do
a
K
bit
multiply.
So
we
are
working
that
a
is
in
2
to
the
K
here,
but
we
can.
We
can
work
in
in
in
bigger
ring
sets
and
that's
fine
and
we
can
work
in
such
a
big
large
ring
that
the
inputs
won't
want
to
wrap
around.
So
the
important
point
is
that
if
the
inputs
are
K
bits,
then
we
have
to
do
kayo,
T's,
okay
and,
of
course,
we're
not
going
to
use
oblivious
transfer.
A
We're
just
going
to
use
this
other
very
clever,
primitive,
called,
oblivious
transfer
extension,
which
allows
you
to
do
a
small
seed
number
of
oh
T's
and
then
extend
them
using
Oh.
They
symmetric
primitives.
So
we
basically
only
need
you
know
200
basic
OTS,
and
then
we
can
extend
these
using
just
something
like
a
es
or
sha.
A
So
the
the
downside
of
using
OTE
is
that
each
call
to
this
primitive
basically
requires
either
K
bits
or
Kappa
bits
the
minimum
of
those
two
right
here.
So,
for
example,
if
we
wanted
to
do
thousand
and
twenty
four
bit
multiplications
right
here,
if
these
numbers
are
a
thousand
and
24,
then
then
the
product
is
going
to
basically
be
so.
Essentially,
we
then
need
to
do.
A
We
base
so
k
right
here
is
basically
going
to
be
a
thousand
twenty-four.
It's
actually
gonna
be
2048.
If
we
want
to
keep
the
answer,
if
we
want
to
keep
the
answer,
we're
gonna
have
to
do
2048,
but
forget
that
point
right
here
where,
as
Kappa
the
symmetric
key
security
primitive
with
something
like
a
AES,
is
simply
something
like
128
bits,
so
in
other
words,
to
do
very
large
multiplications
with
this
type
of
technique,
we
unfortunately
have
to
use
these.
A
These
OT
strings
have
to
be
very
big
if
you
just
use
them
as
Gilboa,
basically
states.
So
now
you
can
sort
of
see
where
the
first
sort
of
real
nice
idea
happens
so
just
to
just
to
put
that
into
perspective.
Essentially
we
need
ko
T's
of
size,
K
bits,
and
so
that's
roughly
K
squared
bits
of
communication
for
multiplication
and
for
one
K
bit
multiplication
here.
So
here's
our
first
big
idea
or
small
idea.
It's
just
that.
You
know.
A
A
What
yeah
roughly
128
bits
here,
okay,
and
so
if
we
want
to,
if
we
basically
want
to
do
a
multiplication
like
this,
we
can
just
do
smaller.
Multiplications
like
this.
This
does
not
help
you
in
the
plain
next
model.
It's
not
like
an
improvement
like
carrot,
Suba
or
anything
like
this.
This
only
helps
because
we're
doing
secure,
computation,
multiplications,
so
just
a
so
as
as
Riyadh
said,
this
should
basically
be
a
hundred
and
twenty
eight
bits.
A
A
We
basically
get
K
over
Kappa
bits
of
communication,
and
so
we
basically
saved
a
factor
of
like
over
K
squared
we've.
Basically
Fett
we've
saved
a
factor
of
K
over
Kappa,
okay,
so
in
this
case,
K
is
like
to
2048
and
capped
by
128.
So
there
we
go,
we've
saved
a
factor
of
16
there,
and-
and
that's
that's
why
this
this
approach
wins,
but
it
gets
better.
It's
not
only
this
candidate
trial
division,
so
all
proper
approaches
here.
A
What
they
want
to
do
is
before
spending
the
the
effort
of
multiplying
a
very
large
modulus
with
another,
very
large
modulus.
We
want
to
basically
quickly
sieve
out
the
multiples
of
3,
5,
7,
11,
13,
etc.
All
the
small
Prime's
who
want
to
do
some
sort
of
trial
division
for
okay
and
now.
How
do
our
previous
approaches
basically
do
this?
So
this
paper
right
here
they
use
PI
a
encryption
and
so
what
they
do
is
they
basically
take
their
number
mod?
A
A
It
should
be
random
right
because
I've
taken
a
nonzero
value
and
multiplied
it
by
random
number,
so
I
haven't
really
broken.
Security
I've
basically
opened
a
random
number.
If,
in
fact,
this
number
was
this
distributed,
additive
share
is
divisible
by
three.
Then
you
know
when
we
sum
up
all
of
our
residual.
All
of
our
residues.
Mod
three
would
get
something
zero
when
you
multiply
that
by
a
random
number,
you
get
zero,
you
open
the
zero,
and
you
know
that
your
prime
is
basically
broken
now.
A
The
unfortunate
thing
is
that
requires
one
encryption,
okay
and
decryption
per
Prime,
and
that
needs
to
be
communicated.
Okay,
so
think
about
that
communication
flop.
They
use
something
better.
They
use
one
out
of
k,
ot,
okay,
and
so
this
is
kind
of
how
they
do
it.
They
their
paper
is
in
the
two
party
model,
and
so
again
another
question
is
how
they
extend
it
to
multi-party.
Is
it's
not
exactly
clear,
but
one
one
could
do
with
that.
That
wouldn't
be
the
bottleneck,
but
but
there's
no
reason
to
so.
A
Let
me
explain
so:
P
is
basically
p1
plus
p2
and
let's
say
we
want
to
check
divisibility
by
7
what
they
like
they,
what
they
also
use
and
the
sort
of
the
magic
sauce
of
making
these
things
efficient
is
to
try
to
use
ot
extension
when
you
can,
because
of
AES,
and
so
Alice
is
going
to
compute.
Her
residue
mod
7
Bob
is
gonna
pick
his
residue
mod,
mod,
7
and
Bob
is
gonna
know
here.
Let's
call
these
inputs
0
1,
2,
3,
4,
5,
&
6.
So,
let's
just
say:
Bob
Bob's
residue
was
4.
A
Okay,
so
Bob
would
know
that
if
Alice's
residue
was
3,
that
would
be
bad.
Okay,
so
he's
gonna
put
a
bad
string
there
and
he's
gonna
put
good
strings
everywhere
else,
and
now
the
protocol
is
basically
Alice
does
a
1
out
of
ko
T
on
her
residue
and
if
she
recovers
bad,
she
sends
it
back
to
Bob
and
say
this
is
bad
if
it's
good
well,
all
she's
learned
is
that
it's
good
hasn't
learned
anything
else
about
what
Bob's
residue
was
and
sends
that.
A
Okay,
so
that's
one
problem:
the
other
problem
is
just
the
structure
of
this,
so
their
trial
division
is
going
to
work.
Something
like
this
they're
going
to
pick
some
share
of
P
they're,
going
to
do
one
out
of
three
ot
or
one
out
of
five
ot,
a
one
I
have
seven
ot
one
out
of
11
ot
and
then
one
out
of
let's
say,
let's
say
the
largest
prime,
is
a
thousand.
It's
not
something
roughly
like
that.
A
They're
gonna
do
all
of
those
Oh
T
s
and
then,
if
they
all
succeed,
then
the
candidate
can
basically
go
ahead,
go
ahead
and
time
and
the
problem
is
okay,
let's
say,
for
example,
your
first
one
succeeds.
Your
second
one
succeeds.
Your
third
one
succeeds
and
now
your
fourth
one
basically
fails
right
here.
So
this
means
essentially
all
of
the
work
that
you've
basically
done
in
vetting
this
prime,
this
one
big
P
that
you've
chosen
for
this
particular
approach.
A
You
mean
under
malicious
adversary,
so
I'm
gonna
talk
so
the
pit
the
hole
this
hole
is
basically
about
semi,
honest
approaches
and,
and
yes,
what
one
can
basically
get
around
these
type
of.
So
we
have
a
strategy
for
malicious,
but
I,
don't
wanna
get
into
that.
It's
kind
of
a
more
complicated
thing,
yeah
the
point
that
the
point
is
just
work:
saving
in
the
semi
on
this
case.
A
That's
what
we're
talking
about
here
and
in
this
case
the
observation
is
that
when
you
pick
your
part,
Prime
and
start
testing
on
that
P,
okay,
you
could
end
up
wasting
a
lot
of
you
end
up
wasting
a
lot
of
intermediate
work.
Now,
of
course,
these
intermediate
stops
right
here,
like
one
out
of
40.
Forty
seven,
let's
say
right:
that's
gonna
succeed
with
46
out
of
forty
seven
percent
of
the
chance
right,
but
on
that
roughly
two
percent
of
the
of
the
leftover
you're
wasting
all
of
that
previous
work.
A
So
you
kind
of
you
kind
of
see
how
this
this
work
basically
adds
up
in
this
one,
plus
two
plus
three
plus,
etc
kind
of
kind
of
way.
A
better
approach
is
again
to
think
about
'can't.
So
again
this
was
the
destructive
thing,
pick
a
P
and
tear
it
down.
Instead,
another
approach
is
a
constructive
approach,
so
the
idea
is
that,
in
fact,
you
know
that
you
need
something
that
is
a
you
need
an
large
number
that
is
a
non
zero
residue,
mod
3.
A
So
we
can
basically
toss
some
coins
and
pick
something
mod
3
and
test
mod
3
right.
So
we
could
go
through
some
process
to
pick
just
some
number
in
Z
3.
That
is
a
non
zero
sum
mod
3
right.
So
this
is
some
process
and
it's
going
to
do
a
lot
of
work
because,
for
example,
one
third
of
the
times
that
we
do
this
it's
going
to
fail
right,
but
any
case.
A
A
So
let's
construct
these
numbers
separately
and
then
use
our
CRT
representation.
So
if
we
want
to
basically
get
a
number
right
here,
we
just
extract
one
candidate
from
each
of
these
particular
piggy
banks,
and
now
we
have
a
P,
okay
and
so
now,
there's
basically
no
wasted
test.
So
if
you
recall
over
here
right,
one
third
of
the
tests
are
going
to
fail
just
on
that
first
level
right.
A
But
a
lot
of
the
work
that
you
do
here
is
going
to
fail
because
you
failed
on
the
second
level
or
the
third
level
or
the
fourth
level
or
fifth
level,
etc.
All
of
that
tail
the
tail
weight
of
wasted
work.
Basically,
we
avoid.
So
that's
why
it's
better
to
do
constructive
type
of
sitting
like
this.
Okay
and
now,
if
you
put
the
first
thing,
I
said
with
the
second
thing,
I
said
so
here
we
are
using
the
CRT,
but
let's
apply
the
CRT
again.
A
We
should
basically
pick
residues
that
are
like
pick
numbers
that
are
nonzero
like
that
are
not
smooth
in
n1
and
n2
at
3,
etc,
and
then
pull
them
all
together
and
one
can
basically
write
a
small.
You
can
try
to
be
optimal,
but
you
could
also
just
take
a
shortcut
and
make
a
greedy
algorithm
that
tries
to
balance
these
things,
and
so
these
are
basically
the
these
are
basically
the
small
ends.
A
You
see
three
kind
of
one
you
want
to
put
with
a
bunch
of
larger
ones
and
19
you
can
sort
of
like
balance,
some
of
the
smaller
particular
values
here.
So
there
are
nine
candidates
right
here
and
I'm
I'm
almost
done
with
this
first
set
right
here.
The
last
observation
I
want
to
make
is
that,
in
order
to
pick
a
number,
that's
not
0
mod
mod,
these
end
ones.
Here
generally
the
approach
just
like
this
PI
a
encryption
has
been
select
a
random
P.
I
okay,
that's
we
share
it.
A
Then
we
select
a
random
R
and
multiply
the
two
together
and
then
open
it.
Just
like
we
did
with
the
pi
a
thing
if
it's
0
mod
any
of
the
small
Prime's,
because
now
we're
working
in
n1,
which
is
a
product
of
small
primes,
then
reject
that
number
and
throw
it
away.
Ok,
if
it's
good
keep
that
P
right,
there
then
do
the
same
thing
with
Q
pick
a
Q
pick,
another
n
damar
open
it
and
see
if
it
works,
and
if
it
is
now
we
have
a
P
and
a
Q.
A
We
can
multiply
the
P
and
Q.
So
there's
an
obvious,
optimization
right
here
that
we
don't
need
the
R
right
here
and
the
other
random
R
right
here.
The
better
approach
is
to
select
our
nmp
select
a
random
Q,
since
we
have
to
multiply
them
anyway.
Multiply
them,
and
since
we're
going
to
reveal
n
anyway
go
ahead
and
reveal
them,
and
if
it's
0,
then
you
basically
exclude
that
slot.
Otherwise
you
keep
that
slot.
A
Did
that
make
sense
right,
so
we
basically
get
rid
of
that
approach
right
there.
So
all
in
all
I
told
you.
We
basically
picked
nine
of
these
type
of
things
and
remember
we're
going
to
basically
the
algorithm.
What
we're
going
to
do
is
this
is
going
to
be
the
first
piggy
bank
we're
gonna.
Basically,
this
defines
a
ring
based
on
these
Prime's
right
here.
We're
gonna
basically
randomly
sample
in
this
one.
A
Until
we
get
nonzero
values,
then
we're
going
to
randomly
sample
here
here
and
here
in
fact,
we're
going
to
do
them
all
in
parallel
and
we're
gonna
fill
our
piggy
bank
switch
in
with
enough
candidates.
Ok,
some
of
these
things
are
going
to
take
more
iterations
than
others,
but
we're
gonna
fill
each
piggy
bank
with,
let's
say
50
candidates
and
then
we're
going
to
extract
them
and
take
that
first
Prime
in
etc.
A
In
fact,
in
this
case,
we're
gonna
actually
be
able
to
extract
the
first
n,
ok
and
so
all
in
all,
we
do
the
analysis.
The
number
of
F,
multiple
128
bit
ot
extension
based
multiplications
to
produce
a
candidate,
P
and
Q,
is
basically
14,
ok
and
so
far,
what
we've
done.
We've
taken,
P's
and
Q's,
and
we've
actually
also
produced
the
prefix
of
a
product,
ok
of
P
and
Q.
A
A
14,
for
this
is
for
1024
for
to
1024
numbers
that
multiply
to
a
2048
number
yeah,
so
we
still
have
to
do
a
little
bit
more
work.
That's
the
next
slide
right
here
share
extensions.
So
when
we
have
a
number,
that's
like
this
big
and
when
we
multiplied,
of
course
the
product
is
going
to
be
bigger
and
in
the
CRT
representation
we
have
to
extend
and
make
those
numbers
as
well.
A
I,
basically
said
here's
another
set
of
crimes
that
we
basically
do
that
with,
and
so
the
the
overall
the
overall
work
right
here
is:
we
basically
do
14
operations
for
this
nine
operations.
For
here
this,
this
is
9:00
instead
of
8:00,
because
in
fact
we
also
check
for
divisibility
by
this
set
of
primes
and
that
so
that
that
actually
helps
us
a
little
bit
and
so
the
expected
number
of
multiplications
we
needed
to
do
produce
a
candidate.
That
is
a
that.
A
A
We
haven't
computed
the
public
end,
yet
we've
only
computed
the
first
half
mod,
the
small
ring,
so
what
what
I
was
basic?
What
I
wanted
to
skip
over
this
is
this
step
right
here.
We
take
our
original
shares,
extend
them
like
locally,
extend
them,
sorry,
what
locally
reconstruct
them
and
then
take
the
modular
the
take
the
modulo,
the
second
set
of
primes
and
then
do
multiplications
on
those.
A
A
The
point
is:
we've
already
invested
all
of
this
work
there
so
doing
all
of
that
basically
saves
the
work
of
by
primality
testing
and,
and
that
actually
turns
that
your
protocol
turns
out
to
be,
even
though
people
complain
about
how
you
have
to
do
this
many
repetitions,
it
turns
out
to
be
not
the
bottleneck
of
this
at
all,
and-
and
so
let
me
just
let
me
just
get
into
that
right
there.
It's
this.
This
will
just
be
the
last
slide,
the
last
few
slides.
A
So
our
protocol
basically
consists
of
F
mod
gen,
which
together
does
all
of
those
things
which
is
saving
and
candidate
generation
and
then
by
prime,
which
is
roughly
the
same
idea
that
you
had
there
and
mod
gen.
Only
reply
only
relies
on
FM.
Oh,
that's,
our
optimal
multiplier
and
F
prime
basically
runs
on
relies
on
two
things.
This
is
the
sort
of
group
multiplier
that
that's
that's.
That's
pretty
cheap,
so
in
terms
of
deployability
and
sort
of
like
part
of
this
is
to
build
something.
A
That's
really
easy
to
understand
and
also
like
easy
to
audit,
and
we
only
basically
require
one
cryptographic,
primitive.
That
requires
a
lot
of
care
to
look
at
the
rest
of
it
is
all
gluing
together
and
now
here's
some
here's,
some
performance
numbers.
We
don't
have
all
of
the
parts
glued
together,
because
we're
still
optimizing
certain
parts
of
this,
but
we
did
take
the
current
protocol.
A
I
just
I
just
did
and-
and
we
express
them
in
terms
of
these
operations,
to
get
a
sense
of
how
much
time
would
actually
take,
and
so
we
ran
like
500
runs
and
we
basically
for
each
run
to
foot
fine.
Each
run
basically
says
how
much
it
runs
until
it
actually
outputs
a
value
that
that
succeeds
and
we
counted
how
many
Majin
operations
we
basically
need
and
that
red
line
is
basically
the
average
and
I
think
this
is
somewhere
in
the
3,500.
A
So
we
basically
have
to
generate
about
3,500
candidates.
That
is
that
lines
up
on
average
that
lines
up
perfectly.
With
our
analytical
analysis,
when
we
do
all
of
the
civic
analysis,
we
get
a
prime
with
roughly
1
over
60
and
so
doing
that
twice
is
roughly
1
over
3600,
and
this
is
where
the
DM
approach.
This
is
the
open
problem,
the
DM
approach.
If
we
could
basically
sieve
one
prime
and
then
another
prime
multiply
them
together,
then
of
course
we'd
only
have
to
do
about
120
of
these
mod
generations.
A
A
Well,
DM,
if
you,
if
you
can
basically
so
here
again,
the
problem
is
we
require
the
mutual
coincidence
of
once
that
both
of
these
things
are,
prime,
that
so
we
get
squared.
If
we
could
do
some
sort
of
prime,
if
we
could
basically
like
here's
one
putative
thing
that
doesn't
exactly
work,
maybe
put
10
moduli
together.
Ok,
ten
of
these
like
shots
and
then,
if
they're
10
choose
2
ways
for
us
to
win
now,
because
if
any
to
win
the
whole
modulus
is
secure.
A
Possibly
we
could
use
that
whole
modulus
and
the
DM
approach
to
check
the
primal
attea
and
it
doesn't
that
proach
doesn't
work
out
for
what
I
explained
there.
But
it's
it's
not
it's
not
clear.
That
would
be
the
right
way
because
then
we
basically
do
one
big
multiplication
and
then
get
a
any
choose
two
type
of
operation
to
help
us
help
us
win,
but
even
this
right
here,
I
think
is
in
the
land
of
feasible.
Let
me
show
you
so
mod
Jen.
Is
this
many
by
prime?
A
Is
this
many
I
think
the
average
was
around
eleven
eighty
number
of
operations
but
I
again.
This
is
not
the
this
is
not
the
bottleneck
by
any
means,
and
Gmail
was
that.
Other
thing
here
is
the
real
FMO
FML
is
the
OT
extension
this
characterizes
how
much
work
essentially
ignoring
FML
in
those
g/mol
and
those
other
things
how
much
work
each
party
has
to
do,
and
here
you
can
sort
of
see
the
average,
which
is
roughly
around
75,000.
A
So
this
is
the
number
of
ot
extensions
that
each
said
this
is
a
number
of
calls
to
FML
and,
if
you
think
about
end
parties,
each
party
has
to
do
basically
a
counter
has
to
do
note
to
extension
on
each
of
these
F
moles.
So
this
is
roughly
the
amount
of
work
that
each
party
has
to
do.
Seventy-Five
thousand
ot
extensions,
that's
highly
highly
feasible.
A
A
Right
so
I'll
do
it
right
now.
75,000
is,
let's
just
call
that
a
hundred
thousand
right.
So
that's
like
two
to
the
seventeen
okay
and
we
have
to
do
two
to
the
7o
T's,
okay
and
each
ot
is
2
to
the
7.
So
that's
14,
plus
17,
which
is
2
to
the
31
bits
of
communication.
So
that's
less
than
4
gigabytes
right
of
per
party.
A
A
This
is,
this
is
a
number
of
F
mall
operations,
and
each
FML
operation
requires
each
party
to
do
that.
Much
communication
per
extra
party.
So
it's
yeah.
It's
like
let's
say
it's:
okay,
so
for
a
thousand
parties
it
would
basically
this
is
bits.
So
if
we
do
this
by,
if
we
divide
again
into
bytes,
this
is
two
to
the
twenty
eight
bytes
per
party.
So
what
is
that
that's
two
to
the
30s
billion,
so
this
is
256
megabytes
per
party.
A
A
You
have
to
do
this
in
order
to
prove
why
lwe
so
good
right,
so
I'm,
taking
one
for
the
team,
yeah,
of
course
yeah.
So
in
a
hundred
parties
like
if
divide
that
by
100
and
now
it's
2
gigabytes
per
person
for
120
30
parties
and
well
I'll,
give
you
a
better
sense
of
it
right.
This
is
how
about
is
one
well.
This
is
somehow
this
is
Apple
trying
to
help
me
here.
So
this
is
a
256
built
multiplication
so
to
nifer
it's
two
of
them
actually,
because
the
this
is
from
our.