Elliptic curve-based VDFs

Sharding
,
1

I have been going through the VDFs readings list posted by Justin Drake. Here’s a link: https://notes.ethereum.org/52JZtwErThe9KmN6TNd1lg#

I noticed that most of the VDFs constructions so far are based on RSA groups or integer ideals. As a lot of in-use cryptography make heavy use of elliptic curve, would it be good idea to try to build a VDF based on elliptic curves?

1 Like
2

If you can find a way how to, sure.

The challenge with elliptic curves is that they have a known group order, so the repeated squaring constructions are trivially short-circuitable.

3 Likes
3

So it is a bit late to the party but here it is :slight_smile:

4 Likes
4

RSA can be expressed as a bilinear pairing of two mod-prime groups . So I think there should be a way to do to an elliptic VDF by using a pairing of two elliptic curves …

5

Looks like some people are already working on this

1 Like
6

well is the paper I linked above :stuck_out_tongue:

1 Like
7

Personally I’m way more interested in post-quantum VDFs than in elliptic curve ones, but :woman_shrugging:

2 Likes
9

We need post-quantum key exchanges right now because future quantum computers might break messages encrypted today.

We’d prefer post-quantum signatures be deployed at the moment a quantum computer comes online. We only push for post-quantum signatures sooner because deployment takes ages. Also, there is a good case that quantum annoying signatures suffice for at least some time after a quantum computer comes online. And quantum annoying signatures might help prove a quantum computer exists in secret.

There is a much stronger argument that deployed VDFs need only be quantum annoying at the moment a quantum computer comes online. In essence, we expect that

  • the first quantum computers should be too expensive and slow for an attack,
  • VDFs are already vulnerable to super-conducting computing, ASICs, better ASICs, etc., which demands more robust usage from deployments.

Both Wesolowski’s and Pietrzak’s VDFs are already quantum annoying, if using the prefered class group instantiation where you hash to p. Also the isogenies VDF is quantum annoying. Among the serious VDF proposals, only the RSA VDF is not quantum annoying.

We should eventually devise a real post-quantum VDF that is compact , but we’re looking pretty good right now.

In this vein, VRFs are like signatures in that quantum annoying suffices for now, but we do want a post-quantum VRF eventually. It’s true hash chaining like RANDAO gives a VRF with singleton domain, except these suck and real VRFs have so many uses in consensus algorithms. I suppose hash-based signatures and zkSTARKs should both provide VRFs but they’re both too large for consensus protocols. It’s dubious if lattice-based techniques can ever yield a compact VRF. Isogenies seem like our best bet for a post-quantum VRF that is both compact and flexible. I’m super happy the construction in @asanso 's paper gives a quantum annoying VRF .

2 Likes
10

Nice analysis . @burdges any chance you can put a link for @asonnino VRF’s quantum annoying VRF paper ?

11

oops! I miss-typed your name there @asanso, I only meant the same BLS-like verification equation from your paper gives a quantum annoying VRF:

e_X(\psi(G_1), H(m)) = e_Y(G_1, \phi(H(m)))

1 Like