VDF (Verifiable Delay Function) and PRP

[Uncwilly]

Originally Posted by chalsall

Sweet! So risk eliminated at no (or very little) computational cost (if I'm understanding correctly).

1 more thing to document for a paper.

[Prime95]

Originally Posted by chalsall

Sweet! So risk eliminated at no (or very little) computational cost (if I'm understanding correctly).

You understand correctly. The downside is the burden falls on the one resource that is most limited -- the server. For most proofs it requires an extra 100 to 1000 multiplications. This morning I had to increase from 2 queues doing proof processing to 3. The server has 24 cores, so I suppose we're still OK.

I do have other options to reduce server workload -- namely, decreasing the hash size from 64 to 48 bits. This would save about 300 multiplications per proof. It's still early in evaluating how well the server is coping. So, no changes for now.

[Uncle Lumpy]

Originally Posted by Prime95

You understand correctly. The downside is the burden falls on the one resource that is most limited -- the server. For most proofs it requires an extra 100 to 1000 multiplications. This morning I had to increase from 2 queues doing proof processing to 3. The server has 24 cores, so I suppose we're still OK.

I do have other options to reduce server workload -- namely, decreasing the hash size from 64 to 48 bits. This would save about 300 multiplications per proof. It's still early in evaluating how well the server is coping. So, no changes for now.

Would it be possible (without too much work) to distribute the "server" portion of this among several volunteer machines? I realize it might take a specialty "pipe" to the Internet and such so I'm just sort of thinking out loud. Please ignore if this has already been discussed or if this is a totally inane question.

I believe the FAH folks had to do something like this when they were getting crushed by participation requests for COVID-19 work.

Lumpy

[Prime95]

Originally Posted by Uncle Lumpy

Would it be possible (without too much work) to distribute the "server" portion of this among several volunteer machines?

In short, no. The server's work is pretty modest -- about 2000 multiplications. But, the key benefit it provides is security. Part of it's work makes it impossible to fake a certification -- even if you have the complete original proof file. If this critical step were farmed out then faking certifications would be easy -- all you would need to do is collude with the person who did the farmed out server work.

Right now, the biggest weakness in the whole proof scheme is someone infiltrating the server's SQL database. Of course, if someone did that they could wreak all kinds of havoc.

[LaurV]

Originally Posted by Prime95

The attack involves multiplying the final Fermat PRP result (for a prime this is one) by a root-of-unity. Minus one is one such possible root.

Wait a moment, if you got a prime, then there are no other roots of unity except 1 and -1, which is (in the non-modular world) either 1, or 2^p-2, and this is easy to spot without any squaring. Or not?

For example, 2^13-1=8191 has only two roots of unity, respective 1 and -1=8190 (in the modular world). Squaring any of them (mod 8191) you get 1, and there are no other numbers with this property. But 2^11-1=2047, because it has 2 prime factors, it has 4 such roots, 1, 622, -622=1425, and -1=2046. Squaring any of these (mod 2047) you get 1.

Similar for higher roots.

It seems to me there is no way to "game" the system here, if the system is aware of it, it can kick you in the butt with a simple calculus.

[retina]

Originally Posted by LaurV

Wait a moment, if you got a prime, then there are no other roots of unity except 1 and -1 ...

90³ = 1 mod 8191

[patnashev]

There are only two square roots of unity. A single squaring is enough to turn them into 1. But phi(N)=N-1 can be divisible by 3, so there could be three cubic roots of unity. Raising to 3rd power is enough to burn them too. Generally, you need to find all small divisors of N-1 and raise the result to those powers to detect the attack. The limit can be selected depending on the number being tested. It's trivial to have all N-1 divisors <2^64 of Proth numbers. But you need to actually look for N-1 divisors of c=-1 numbers, so it's practical to select lower limit like 2^24 or 2^32.

[patnashev]

And it's not enough to only consider prime factors, their powers are important too.
1477³ != 1 (mod 8191)
1477⁹ = 1 (mod 8191)

All 9th roots of unity mod 8191: {1, 90, 1477, 1874, 2723, 4840, 6128, 7531, 8100} Six of them are primitive roots (do not become 1 sooner).

[retina]

Originally Posted by patnashev

And it's not enough to only consider prime factors, their powers are important too.

And any composite power also.

1510² != 1 (mod 8191)
1510⁵ != 1 (mod 8191)
1510¹⁰ = 1 (mod 8191)

[patnashev]

Yes, that's why we're talking about divisors of N-1. But composite powers are dealt with automatically when you compute the "security" exponent.

[patnashev]

Security exponent for 8191 is 2 * 3 * 3 * 5 * 7 * 13