►
From YouTube: Verifiable Delay Functions - Dan Boneh
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
Great
okay,
excellent
yeah,
so
this
is
a
there's,
a
pretty
diverse
group,
so
so,
let's
see
so
right,
so
all
mathematicians
to
cryptographers
to
hardware
folks,
it's
a
pretty
pretty
broad
area,
so
I
guess
just
to
kick
things
off.
What
I'll
do
is
maybe
just
kind
of
give
an
overview
of
what
vdf
Saar
just
to
make
sure
everybody's
on
the
same
page
I.
A
Imagine
it's
gonna
be
stuff
that
many
of
you
already
know,
but
I
think
it's
good
to
just
make
sure
everybody
knows
what
it
is,
we're
talking
about
and
then
we'll
dive
into
the
details
and
the
subsequent
talks.
Okay,
good.
So
the
goal
of
a
vdf
is
basically
to
slow
things
down
yeah.
This
is
kind
of
what
Joe
taught
me,
and
so
the
question
is:
how
do
we
slow
things
down
verifiably?
So,
let's
define
what
is
a
vdf
again.
I
won't
give
very
precise
definitions.
A
A
A
function
is
supposed
to
take
T
steps
to
evaluate,
and
the
point
is
it
should
take
these
tips
to
evaluate,
even
if
the
adversary-
or
you
know,
even
the
honest
parties
have
unbounded
as
too
much
have
polynomial
parallelism.
So
if,
even
if
you
have
polynomial
processor
put
many
processors,
you
shouldn't
be
able
to
speed
up
the
evaluation,
and
the
point
is
once
you
have
computed
that
you've
you've
spent
the
T
steps
to
value
the
function.
A
It's
easy
to
verify
that
the
output
was
computed
correctly,
okay,
so
it's
a
little
bit
more
precisely
so
there
are
three
algorithms
to
set
up
the
vowel
and
the
verify
algorithms
so
set
up,
will
take
a
security,
parameter,
lambda
a
time
bound,
T
and
will
produce
the
public
parameter
as
P
P,
which
we'll
talk
about
more
about
the
setup
procedure
later
in
the
day.
This
might
involve
these
multi-party
computation
steps
and
so
on.
A
So
that's
the
setup
once
we've
done
set
up
the
evaluation
algorithm
takes
the
public
parameters
and
an
input
X,
and
it
produces
an
output
Y
as
well
as
a
proof,
and
this
evaluation
is
the
same
thing.
That's
supposed
to
take.
T
steps,
even
if
you
have
a
parallel
computer,
okay,
so
parallelism
does
not
speed
up
the
evaluation
as
the
points
and
there's
a
verification
algorithm
that
takes
the
public
parameters.
The
input
X,
the
ALPA
Y
and
the
proof,
and
quickly
very
quickly,
says
whether
Y
is
a
correct
value,
is
a
correct
evaluation
of
the
vdf.
A
So
that's
syntactically
syntactically.
What
a
vdf
is
so
now,
let's
talk
a
little
bit
about
the
security
properties,
so
there
are
sort
of
two
security
properties,
the
first
one.
Well
one
is
I
guess
still
a
syntactic
requirement
is
uniqueness.
It's
crucial
that
these
things
are
unique.
So
what
is
uniqueness
mean
so
given
a
particular
value?
X,
there
should
only
be
one
Y
that
convinces
the
verifier
in
particular.
A
A
Okay,
if
there's
Y,
pi
and
Y
Prime,
you
just
shouldn't
be
able
to
convince
the
verifier
that
there
are
two
valid
Y's.
So
that's
the
uniqueness
property
and
the
more
important
property
is
this,
this
sequentiality
property,
which
is
even
if
the
adversary,
has
a
parallel
machine,
so
polynomial
e-mini
processors.
A
C
A
Kind
of
the
so
we
call
this
epsilon
sequence
yeah.
Obviously,
it's
parameterize,
this
properties,
parameterize
by
Epsilon
and
we'd
like
to
achieve
epsilon
sequentiality
for
the
smallest
possible
value
of
Epsilon,
all
right,
that's
as
formal,
that's
as
formal
as
I'm
gonna
get
yeah,
so
hope
this
is
clear
enough
for
everybody.
So
what
do
we
need
these
things?
For
so,
let's
see
so
let
me
start
with
a
picture
that
I
stole
also
from
one
of
Joe's
slides,
which
is
this
lottery
question,
so
you
want
to
generate
verifiable
randomness
in
the
real
world,
and
why
is
this?
A
What
is
it
so?
The
point
here
is
that
you
notice
only
three
balls
came
out
of
the
little
vats,
but
all
five
numbers
are
already
displayed
on
the
bottom,
so
so
clearly,
clearly
clearly
something
went
wrong
in
this
in
this
video.
So
this
is
not
very
convincing
that
the
randomness
is
unpredictable
and
the
question
is:
is
there
a
way
to
verifiably
generates
randomness?
Okay,
so
so,
let's
see
a
broken
way
to
generate
randomness,
so
this
is
kind
of
crypto
101.
A
So
if
you
want
to
generate
have
n
parties
generates
a
random
value
which
is
kind
of
the
main
blockchain
application.
I
guess
the
beacon
chain
is
kind
of
has
a
random
as
beacon
in
it,
which
is
why
it's
called
a
beacon
chain.
So
here's
a
dumb
way
to
do
a
beacon
chain
to
general
randomness,
which
nobody
should
use
yeah.
So
we
have
our
participants,
everybody
posts,
a
random
value
to
the
bulletin
board
and
the
output
is
just
the
XOR
of
all
the
posted
random
values
yeah.
A
So
this
looks
like
it's
random,
but
of
course
it's
completely
broken
and
the
reason
it's
broken
is
because
the
last
participant
Zoey
can
just
choose
her
RZ
so
that
the
output
comes
out
to
be
whatever
she
wants.
Okay,
so
everybody
knows
this.
So
there
are
a
lot
of
solutions
to
a
lot
of
attempts
at
fixing
this
problem,
you're
a
forest
all
familiar
with,
commit
and
reveal,
or
everybody
commits,
and
then
some
people
ruin.
A
Everybody
reveals
the
problem
with
commit
and
reveal
is
that
people
might
refuse
to
reveal-
and
you
can't
it's
kind
of
people-
keep
asking
me
this.
Why?
Why
can't?
If
someone
iike
refuses
to
reveal,
why
can't
you
just
ignore
their
commitment
and
only
XOR
the
the
values
that
that
that
that
of
the
people
that
actually
open
the
commitment-
and
the
answer
is
that's
insecure?
A
You
can't
just
reveal
you
can't
just
ignore
the
values
that
were
not
open,
because
if
20
people
collude,
they
could
choose
not
to
open
any
subset
any
subset
of
20
of
them
and
in
doing
so
they
basically
get
to
they
get
to
to
the
20
possibilities
for
controlling
the
final
output
yeah
so
committing
to
reveal.
That
is
insecure.
If
you
just
ignore
the
values
that
were
not,
there
were
not
opened.
Yeah.
A
So
four
bits
flippin,
we
know
the
four
yeah.
This
is
the
different
story:
4-bit
flipping.
We
know
this
is
not
possible
in
a
fixed
number
of
rounds,
but
this
is
not
a
bit
flipping.
This
is
just
randomness
yeah,
so
randomness
you
can
do
in
in
constant
rounds.
Yeah,
okay,
but
anyhow
this
is
not
commit,
so
there
other
product
committed
reveals
it
requires
multiple.
These.
These
two
rounds
are
problematic.
A
We'd
like
to
do
things
in
just
a
single
round
yeah
just
like
here,
yeah
you
just
post
it
you
just
post
and
you're
done,
and
nobody
needs
to
come
back
and
do
anything
else
to
get
the
randomness
that's
kind
of
the
goal
yeah.
So
this
basic
mechanism
doesn't
work,
and
so
the
question
is
what
to
do,
and
so
there's
this
beautiful,
beautiful
idea
that
says
what
we
would
do
is
basically
what
we
did
before.
Except
now
you
know.
A
Obviously
we
would
hatch
the
outputs
that
everybody
contributed,
so
this
by
itself
is
not
enough
to
ensure
randomness,
because
again,
Zoe
still
has
a
lot
of
control
over
what
the
final
output
is.
She's,
the
last
one
to
contribute.
She
can
just
try
lots
of
our
Z's
until
the
hash
comes
out
to
be
something
that
she
likes,
but
instead
what
we're
gonna
do
is
we're
gonna
introduce
another.
No
another
video
yeah
there
you
go
just
as
I
said
it.
A
We're
gonna,
introduce
another
and
we're
gonna
introduce
a
vdf
and
the
output
will
be
the
output
that
comes
out
of
a
computation.
So
you
notice
there's
no
need
for
anyone
to
come
back
the
vdf
kind
of
guarantees,
the
properties
that
we
need.
So,
let's
think
through
why
this
is
a
good
idea.
Why
does
this
work?
Why
does
this
produce
an
by
a
simple
randomness?
Well,
so,
first
of
all,
let's
just
talk
about
mechanically
how
this
works.
So
we'll
say
everybody
starts
start
submitting
your
your
randomness
at
noon
and
then
at
noon
at
12:10,
whoever
submitted.
A
That's
that
those
are
the
people
that
participate
in
the
protocol
and
then
the
vdf
daily
is
gonna,
be
more
than
10
minutes
yeah.
Let's
just
say
it's
20
minutes
or
something
so
now
the
sequence
she
ality
property
of
the
vdf,
ensure
zowie
can't
try
lots
of
possible
inputs
of
the
protocol
because
she
can't
compute
the
output
of
the
vdf
yeah.
So
she
contributes.
She
contributes
something
to
the
VDS
and
she
has
no
idea
what
the
output
is.
This
is
gonna
take
her
more
than
10
minutes
to
compute
the
output.
A
A
If
the
vdf
time
bound
is
set
to
20
minutes,
it
really
needs
to
be
the
case
that
in
ten
minutes
she
cannot
predict
the
outputs,
yeah
and
I
guess
that's
kind
of
where
we
need
all
the
hardware
help.
So
you
guys
looked
into
kind
of
all
the
fancy
gallium
arsenide
technologies
that
could
come
into
play
here
right.
It's
not
it's
not
just
ASIC!
You
can
imagine,
there's
a
lot
of
money.
Gonna
be
at
stake
here,
so
you
know
with
enough
money.
You
can
spend
a
lot
of
research
on
building
faster
VLSI
with
with
fancy
technologies.
A
Thanks
faster,
so
instead,
so
if
ten,
if
I
the
example
here
instead
of
10
minutes,
it
would
be
so
if
it
takes
10
minutes
to
submit,
then
you
would
want
it
to
take
a
thousand
minutes
to
break
the
vdf
to
scale
down
to
whatever
parameters
you
want.
10
minutes.
1000
minutes
is
the
honest
part,
yeah
yeah,
exactly
what
I
mean,
so
the
honest
party
will
take
a
thousand
minutes
in
this
example.
C
A
A
Yes,
yes,
absolutely
absolutely
absolutely
yeah
yeah!
So
Justin
was
saying
that,
if
you're
in
would
likely
set
the
parameter
for
the
vdf
to
be
100
X,
so
if
you
want
so,
if
what
is
it,
if
the,
if
you
need
a
delay
of
10
minutes,
you
would
set
the
parameter
to
be
100
X
10
times
10
minutes.
For
the
honest
guys.
A
That's
the
protocol
yeah,
that's
a
property
of
the
protocol,
yeah
yeah,
so
yeah,
so
we're
good,
yeah,
all
right,
very
good,
so
sequentially
basically
ensures
that
Alice
can't
buy.
Zoey
can't
buy
us
the
output
because
she
doesn't.
She
can't
choose
an
RZ
and
just
try
things
out,
because
it
takes
her
more
than
10
minutes
to
cook
to
calculate
and
uniqueness
basically
ensures
that
yeah.
There's
no
ambiguity
about
the
output.
A
Yeah!
There's!
No
ambiguity
about
the
output!
So
once
once
the
output
is
produced,
people
can't
go
back
and
say:
oh
no,
the
randomness
should
have
been
something
else.
The
proof
actually
guarantees
that
the
output
is
unique
and
it's
very
interesting
again.
Joe
makes
this
really
nice
point
that
if
you
remove
any
one
of
these
requirements,
then
constructing
vdf
becomes
easy.
That's
really
the
combination
of
all
these
requirements,
the
sequentiality
and
uniqueness
that
makes
vdf
construction
difficult.
Ok!
So
that's
what
that's
why
they're
so
useful,
and
this
is
what
we're
trying
to
construct.
A
A
Know
then,
there's
this
very
paper
on
the
proof
of
sequential
work
that
I
just
uses
just
uses
depth
robust
graphs,
no,
it's
a,
but
it
doesn't
require
any
fancy
techniques,
it's
just
having
just
hash
functions
and
therefore
bus
graphs.
That's
it
yes,
that's
easy,
no,
easy,
meaning!
No
known
techniques.
A
Okay,
fair
enough
I
wasn't
saying:
I
was
saying
that
these
are
known
techniques.
We
don't
need.
We
don't
need
to
have
multiple
vdf
workshops.
If
we
remove
uniqueness,
we
already
know
how
to
do
video.
So
if
we
remove
uniqueness,
that's
right.
That's
right!
That's
right!
That's
all
I
was
saying
all
right.
Good
gotta,
be
gotta,
be
careful
with
my
words
in
this
crowd,
all
right,
ok,
good!
So
right!
So
now,
let's
walk
through
a
couple
of
a
couple
of
constructions.
A
So
the
first
construction
is,
you
know
if
we
had
Hardware
enclaves,
then
constructing
vdf
is
actually
quite
easy.
Basically,
so
what
is
a
hardware
claves?
We
can
store
cryptographic
keys
inside
of
the
in
clave
and
then
we
use
that
and
clave.
We
use
those
keys
to
basically
generate
the
vdf.
So
what
we
would
do
the
public
parameters
would
be
the
signature
for
for
a
public
key
scheme.
Yes,
a
PK
is
public
and
then,
when
an
input
comes
in
the
the
end,
clave
enforces
a
time
delay
and
when
it's
done
it
produces.
A
You
know
some
Mac
some
some
PRF
of
the
input
X
and
then
it
also
signs
the
outputs
and
the
signature
guarantee
that
the
vdf
was
computed
correctly
by
the
hardware
and,
of
course
a
PRF
is
unpredictable.
So
that's
all
that's
really
all
that
we
need
yeah.
So
if
we
had
a
hardware
in
clave,
then
vdf
constructions
are
quite
easy.
But
of
course,
if
you
ever
steal
the
H
max
secret
key,
then
all
the
vdf
guarantees
go
out
the
window
yeah,
because
now
anyone
can
compute
the
vdf
instantly.
A
C
A
If
there's
a
lot
of
money
writing
on
the
security
of
these
consensus
protocols
with
enough
money,
any
hardware
and
clave
can
be
can
be
broken.
That's
my
position.
It's
fine
to
use
it
to
protect
data
so
for
privacy.
It's
fine
to
use
enclaves
for
consensus
where
the
we're
breaking
consensus
means
loss
of
money.
That's
where
it
becomes
dangerous
to
use
to
use
enclaves.
Ok,
good!
So
that's
that's
problem!
Number!
One!
That's
something
any
comment!
Anyone
want
to
comment
on
that.
Is
there
general
agreement
about
this
or.
C
A
Okay,
I
see
I,
see
all
right
fair
enough,
but
at
least
the
main
points
seems
like
there's
consensus
on
the
main
points:
yeah
all
right
good.
So
the
next
approach
is
to
use
to
try
build
a
vdf
from
a
hash
function
and
that
what
you
could
do
is
you
basically
kind
of
use.
A
Do
the
vdf
in
the
most
natural
way,
which
is
the
public
parameters,
will
be
a
parameters
for
a
snark
and
then
the
vdf
is
just
defined
as
a
hash
chain,
where,
presumably
you
know
excel
evaluating
sha-256
repeatedly
is
going
to
take
time
T,
even
if
you
have
a
parallel
computer.
The
question
is:
how
do
you
verify
that
the
Apple
was
computed
correctly
and
that's
where
the
snart's
come
in
and
so
I
guess
we
it's
not
so
easy
turns
out
to
get
this
to
work
correctly.
A
So
the
proof
pi
would
be
a
snark
that
the
hash
gene
was
computed
correctly.
It's
not
so
easy
to
get
that
right
because
computing,
the
snark
takes
more
time
than
computing
the
chain.
So
you
have
to
do
something
to
counteract
that
and
it
turns
out
so
so.
There's
a
paper
I
guess
me
and
Joe
and
Benedict
and
Ben
Ben
fish.
Let's
show
how
to
kind
of
do
this,
how
they
kind
of
do
this?
Well,
so
that
you
can
generate
the
proof
well
fast
enough
yeah.
A
So
the
verification,
basically
would
just
be
verification
of
a
snort
proof
and
I
do
I
did
want
to
mention
that
we
also
had
these
ideas
for
using
building
vdf
form
permutation
polynomials
that
somehow
that
really
hasn't
taken
off
yet,
but
maybe
I'll
just
mention
that
as
a
possible
direction
for
future
vdf.
So
a
permutation
polynomial
is
a
polynomial,
that's
a
permutation
on
the
finite
field,
yeah.
So
in
other
words,
it's
a
polynomial
defined
over
a
finite
field
and
such
that
for
any
two
points
x
and
y
in
the
field.
A
The
polynomial
f
of
x
is
not
going
to
be
equal
to
f
of
y
yeah,
so
it's
a
permutation
of
the
field
and
then
the
the
property
that
this
uses,
the
property
that
this
construction
uses
is
the
fact
that
finding
roots
of
a
polynomial,
so
the
input
X,
is
going
to
be
the
image
of
the
polynomial
and
the
value
of
the
vdf.
Would
be
would
be
a
value
of
the
polynomial
I
so
that
f
of
y
is
equal
to
X?
A
A
In
other
words,
we
want
to
find
the
roots
of
the
polynomial
F
minus
X,
yeah
F,
minus
X
will
be
zero
at
the
point
y
and
the
question
is:
can
we
find
a
root
of
that
polynomial
because
it's
a
permutation
polynomial?
We
know
that
there
is
a
unique
such
roots
and
if
the
polynomial
is
easy
to
evaluate
like
it's
a
sparse
polynomial,
then
checking
that
the
roots
was
computed
correctly
is
is
easy.
A
C
A
A
So
it's
another
valid
direction
for
does
that
make
sense
it's
another
valid
direction
for
constructing
PDFs,
but
the
chat,
the
research
challenge
is:
are
there
good,
permutation
polynomials
that
a
are
easy
to
evaluate
so
there's
sparse,
polynomials
or
they
have
short
straight-line
programs
and
the
best
way
to
find
a
root
of
the
polynomial
is
via
GCD
computation
and
there's
no
other
shortcuts?
Okay,
so
that's
that's
another
approach.
A
Just
keep
that
in
mind
and
then
the
third
approach
was
it
was
actually
the
most
exciting
I
think
and
that's
I
think
the
direction
we're
all
headed
in
is
basically
these
algebraic
constructions,
and
so
the
algebraic
construction
starts
from
a
group
from
a
finite
cyclic
group
yeah.
So
this
is
the
group
1
G
G
square,
G
cubed,
and
then
the
assumption
is
that
the
group
has
unknown
order.
So
nobody
knows
what
the
order
of
the
group
is.
A
A
Take
your
input,
X
hash
it
on
to
the
group
and
then
raise
the
result
to
the
power
of
T
two
to
the
T,
and
that
inherently
requires
T
squarings
yeah.
So
this
is
kind
of
again.
This
has
been
used
many
times
before
in
cryptography
for
the.
What
is
it
for
proofs
of
time,
proofs
of
time
and
time
lock
time
block
puzzles
what
is
it
Rivest
Shamir,
not
Rivest,
Shamir
and
wagner
yeah
RSW.
So
this
this
kind
of
function
has
been
used
quite
a
bit.
The
problem
has
always
been.
A
A
Really,
these
are
really
beautiful
protocols
that
allow
you
to
quickly
verify
that
the
function
was
was
computed
correctly
I'll
mention
you
can
read
the
papers
to
see
how
the
protocols
work,
I,
guess,
yeah
I,
guess
we
wrote
a
survey
paper
on
this.
That
kind
of
describes
the
two
schemes
together
in
one
place.
If
you
want
to
see
that
and
I
guess
we're
even
going
to
hear
later
today
about
hybrid
schemes,
that
kind
of
combine
the
two
proofs
to
maybe
make
the
proof
generation
a
little
faster
than
what
we
have
today.
A
So
you
Benjamin
you're
gonna
talk
about
that
cool
all
right,
so
that's
kind
of
the
algebraic
construction.
There's
one
issue
here,
which
is
you
notice,
I,
said
the
complexity.
Assumption
is
that
the
group
has
unknown
order
again,
I'm
being
a
little
vague.
Will
here
exactly
what
the
complexity
assumption
later
is
later
on.
So
let
me
talk
a
little
bit
about
what
does
this
mean
that
the
group
has
unknown
order?
First
of
all,
why
do
we
need
the
group
to
have
unknown
order?
A
Well,
if
the
group
has
known
order
suppose
there
was
no
order
order,
D,
then
evaluation
becomes
trivial.
It
what
I
will
do
is
I
will
just
compute
two
to
the
T
mod
D
that
takes
very
little
time
to
to
the
team
ID
and
then
it
will
just
raise
H
of
X
to
that
power.
But
now
that's
a
very
small
power.
So
if
I
knew
the
order
of
the
group,
I
could
accelerate
the
evaluations
from
T
squarings
to
basically
almost
logarithmic
time
in
T
from
T
squarings
to
log
T
work
yeah.
A
So
that's
kind
of
the
that's
why
we
have
to
have
this
group.
This
group
has
to
have
unknown
order.
So
the
challenge,
then,
is:
how
do
we
generate
groups
of
unknown
order
yeah?
So
nobody
should
know
the
order
of
the
group
and,
like
I
said
this
is
crucial
for
vdf
security.
Vdf
would
simply
be
insecure
if
we
could
compute
the
order
of
the
group.
So
what
are
the
candidate
groups
of
unknown
order
that
we
have
so
the
first
one?
A
Everybody
knows
this
is
the
RSA
group
right,
so
you
generates
two
integers
P
and
Q
multiply
them
and
the
order
of
the
group
is
unknown
unless
you
can
factor
the
modulus
all
right.
So
the
issue
here
is
anyone
who
knows
the
factorization
will
know
the
order
of
the
group
and
we'll
break
the
vdf.
So
we
have
to
be
able
to
construct
this
n
in
a
way
that
nobody
knows
the
factorization.
So
this
for
efficiency.
This
requires
a
trusted
set
up.
I'll
mention
that
I
guess
at
some
point.
A
It's
too
big,
that's
I,
think
it's
33
to
40000
I,
wouldn't,
okay.
We
can
talk
about
whether
it's
safe
to
go
below
that,
but
it
would
still
need
to
be
quite
large.
If
you
choose
a
random
number,
it
would
need
to
be
quite
large
for
the
factorization
to
be
unknown.
So
it's
for
efficiency
purposes,
we'd
like
to
generate
a
random
RSA,
modulus,
presumably
2,000
bits
or
4,000
bits
for
which
nobody
knows
the
factorization
yeah.
A
A
That's
right:
that's
right!
Actually
yeah,
okay!
Well,
we
can
talk
about
that
later,
but
anyhow,
so
so
so
the
problem
with
this
group
is
that
we
need
to
have
this
trusted
set
up,
and
so
the
way
this
would
work
and
I
guess
we're
gonna
have
a
whole
breakout
session
on
this.
We're
gonna
run
the
questions.
How
do
you
generate
run
a
protocol
that
generates
an
RSA
modulus,
so
everybody's
convinced
that
the
modulus
is
in
fact
a
product
of
two
large
primes
and
nobody
knows
the
factorization
yeah.
C
C
A
That
will
give
you
the
evaluation
of
the
vdf
at
H
of
X
3.
So
the
hash
function
needs
to
be
resistant
to
these
multiplicative
collisions
and
as
long
as
that's
fine,
we're
good,
yeah
and
so
256
bits.
That's
on
the
border
of.
What's
what's
secure
there,
so
I'd
suggest
hashing
to
more
then
256
bits,
but
in
principle
it's
only
this
kind
of
multiplicative
collisions
that
we
need
to
worry
about.
A
Yeah
know
that
okay,
absolutely
right
absolutely
right.
So
let
me
explain
what
let
me.
Let
me
just
repeat
that,
so
the
issue
is
so
there's
another
attack,
it's
not
just
multiplicative
collisions.
So
imagine.
Imagine
H
of
X
mapped
to
a
number
that
happened
to
be
a
product
of
only
small
primes
yeah
so
happens
to
be
only
3
times,
5
times
7.
A
Let's
just
say
this
3
times
5
times
7
you
can
pre-compute
the
vdf
at
3
at
5
and
at
7,
and
that
would
let
you
quickly
evaluate
the
vdf
at
a
number
that
the
number
H
of
X
that
happens
to
be
a
product
of
small
Prime's.
So
it's
important
that
H
of
X
not
be
only
a
part
of
the
small
Prime's,
because
that
would
enable
enable
pre-computation
and
so
yeah.
So
the
answer
is
no,
so
the
answer
is
256.
Bits
is
definitely
not
enough
yeah,
so
you
would
need
to
avoid
these
smoothness
attacks.
C
A
That's
okay:
we
know
how
to
do
that.
So
just
you
know,
use
a
hash
function
that
outputs
outputs
more
more
than
256
bits.
It's
a
good
point.
Thanks
mention
all
right,
good,
all
right,
so
groups
of
unknown
order.
So
we
talked
about
RSA.
So
the
issue
is
we
have
to
have
this
trusted
setup
procedure,
the
other
group
that
has
unknown
order.
This
is
kind
of
a
magical
group.
It's
called
a
class
group
of
an
imaginary
quadratic
order.
I
want
to
find
what
that
is.
A
But
what's
but
the
amazing
thing
about
this
is
this
group
is
specified
by
a
prime.
So
literally
you
just
choose
a
prime
that
happens
to
be
3,
mod,
4
and
then
boom.
You
have
a
group
defined
by
this
prime,
and
the
amazing
thing
is:
if
the
prime
is
large
enough,
let's
say
a
thousand
bits:
nobody
knows
how
to
calculate
the
order
of
that
group
yeah.
It's
just
the
best
algorithm
that
we
have
for
calculating.
A
The
order
of
the
group
essentially
runs
in
sub
exponential
time,
so
we
actually
can't
run
the
algorithm
to
calculate
the
order
of
the
group.
So
this
is
kind
of
a
remarkable
group
in
that
you
pick
a
prime,
you
get
a
group
of
unknown
order
and
you
can
use
it
for
a
vdf,
the
problem
with
it.
So
the
benefit
is
that
there
is
no
set
up.
A
The
problem
is
it
that
the
operation
in
a
class
group
is
relatively
slower
than
in
an
RSA
group
and
yeah,
and
to
be
honest,
we
actually
don't
know
how
much
slower
so
I
talked
to
Bram
yesterday,
and
he
was
telling
me
that
or
two
days
ago
he
was
telling
me
that
they
from
the
competition
that
they
ran.
It
looks
like
now
the
implementations
they
have
are
actually
much
better
than
their
initial
implementations.
So
maybe
now
the
relation
between
RSA
operations
and
class
group
operations
it
used
to
be
like
a
factor
of
20.
A
A
A
I
know
I,
don't
totally
agree
so
so
actually
the
real
question
is
yeah,
absolutely
so
how
parallel?
How
parallelizable
is
the
group
operation
and
obviously
we'd?
Like
the
group
operation
we'd
like
to
understand,
we
like
to
basically
extract
all
the
parallelism
that
we
can
as
a
group
operation
so
that
we
we
know
how
long
the
bad
guys
would
have
to
run.
A
No,
that's
the
class
groups
are
they
have
been
proposed
in
crypto,
I
guess
in
the
mid-1990s,
but
they
have
never
been
deployed,
so
this
is
kind
of
virgin
territory.
Yeah,
there's
a
lot
I
think
it's
interesting,
yeah,
there's
a
lot
of
a
lot
of
interesting
work
to
do
here,
but
there's
work
to
do
for
RSA.
I
totally
agree,
there's
a
lot
more,
that's
known,
yeah!
The
interesting
thing
is
because
it's
so
easy
to
generate
these
groups.
You
can
actually
switch
groups.
A
Every
couple
of
minutes
just
generate
a
new
primer,
every
few
minutes
and
not
a
lot.
That
means
that
in
the
RSA
case,
we
have
to
generate
the
parameters
to
be
large
enough
to
not
be
breakable
in
50
years.
Yeah
for
class
groups
we
just
have
to
generate
a
parameter,
is
large
enough
to
not
be
broken
in
like
a
minute
or
if
you
generate
a
new
one,
every
ten
minutes
not
to
be
broken
every
ten
minutes.
A
A
No
class
groups
computing
the
size
of
a
class
group.
This
is
a
very
fundamental
question
in
an
algebraic
number
theory.
So
there
are
a
lot
of
people
who
worked
on
trying
to
come
up
with
better
algorithms
for
computing
class
groups.
The
best
algorithms
right
now
are
kind
of
index,
calculus,
tights,
algorithm
type,
algorithms.
They
run
in
time.
L,
1/2
or,
as
factoring
runs
in
time,
l
one-third.
A
C
A
It's
a
very
it's
a
very
fundamental
problem
in
number
theory:
yeah
yeah.
This
is
why
so
there's
two
benefits
right.
So
a
the
problem
seems
to
be
harder.
So,
even
even
if
we
had
to
be
secure
for
30
years,
it
looks
like
a
2,000
bit.
Modulus
is
sufficient
for
4
class
groups,
whereas
4000
bits
are
needed
for
RSA,
but
the
other
benefit,
of
course
is
we
can
switch
very
quickly,
so
we
can
shrink
the
parameters
even
more
yeah
and
well
yeah,
so
we'll
need
to
come
up
with
a
number.
A
So
Chia
is
gonna,
be
using
this
yeah.
So
we're
gonna
need
to
come
up
with
a
number
to
to
to
say
what
is
the
right
modulus
size
to
use
here?
Okay,
so
let
me
end
up.
Let
me
end
here
just
with
a
couple
of
open
problems,
so,
first
of
all,
I
don't
know
that
there
are
not
other
groups.
So
this
is
a
question
for
the
mathematicians.
There
could
be
other
groups
of
unknown
order
right,
so
we
have
two
examples
and
they
each
problematic
for
different
reasons.
A
Yeah
one
has
a
slow
group,
operation
or
I
should
say.
Parallelizable
group
operation
potentially
and
the
other
one
has
a
trusted
setup,
and
so
you
know
there
could
be
other
groups
of
unknown
order.
So
you
know
please.
This
is
a
wonderful
question.
Think
about
yeah,
and
maybe
we
can
have
a
larger
variety
to
choose
from
the
other
problem.
Is
that
all
these
algebraic
vdf
construction
is
actually
not
post
quantum
secure
I,
don't
know.
If
we
need
to
worry
about
that
now,
you
know
my
calculation.
Is
it's
30
years
away.
So
we'll
worry
about
it.
A
You
know
in
the
future,
but
why
is
it?
Why
is
it
not
post
Quantum
secure
and
the
answer
is
Shor's
algorithm
for
factoring?
Actually
it's
good
at
finding
periods
of
funk.
Sorry,
it's
good.
It's
good
at
finding
the
order
of
a
group,
so
no
group
of
unknown
order
is
gonna,
be
secure
against
the
quantum
attack.
So
the
whole
algebraic
approach
in
some
sense
is
inherently
not
post
quantum
secure.
And
so
the
question
is,
you
know:
is
there
a
way
to
do
post
quantum
secure,
vdf
efficiently?
A
We
can
go
back
to
the
hash
based
systems,
but
those
require
you
know
these
recursive
snarks
and
so
on.
The
question
is:
is
there
a
clean,
very
clean
and
simple
vdf
that
also
will
remain
secure
in
the
presence
of
a
quantum
computer?
Wait.
So
that's
what
I
wanted
to
say
and
I
guess
I'll
stop
here.
So
thank
you.