VDF (Verifiable Delay Function) and PRP

[preda]

Originally Posted by patnashev

Besides attacks, there are also hardware and software errors. And we're much more likely to see them than an attack.

OK, but I don't consider the danger of HW and SW errors an argument for the "hash hacking". I would need a clear reason for why that hash manipulation is needed or useful. Otherwise it's just black magic with unclear benefit.

Specifically: half of the hashes are even; why is that a problem?

[Prime95]

This is easier to code than I expected! I just created a power=8 proof of M216091 and successfully verified it.

Using 48-bit hashes, the proof construction cost was the equivalent of 15K squarings.
Server-side cost was 2K squarings.

[patnashev]

Do you construct the full exponent for each point or group them?

[Prime95]

Originally Posted by patnashev

Do you construct the full exponent for each point or group them?

They are grouped. A very simple recursive routine does the trick.

[patnashev]

A time for hacking fun.

The random exponent is required to have no divisors <1000 in my code. After disabling this check I was able to "hide" a 321 prime by multiplying the result by 3rd root of unity. Every third certificate passes validation.

***** cert.txt
Certificate RES64: 2C2CCA7B6A1F7703  Time : 4.290 sec.
3*2^2291610+1 is not prime.  Proth RES64: 0000000000000002  Time : 125.660 ms.
***** CERT_DC.TXT
Certificate RES64: 2C2CCA7B6A1F7703  Time : 52.338 sec.
*****

This is because when the random exponent is divisible by 3, the 3rd root of unity turns into 1 and has no effect on the verification process. Generally this works when gcd(random, N-1) != 1.

I strengthened the random to contain no divisors < 10^6. Can also check the gcd, but this doesn't look necessary for Proth numbers.

[preda]

Originally Posted by patnashev

A time for hacking fun.

The random exponent is required to have no divisors <1000 in my code. After disabling this check I was able to "hide" a 321 prime by multiplying the result by 3rd root of unity. Every third certificate passes validation.

***** cert.txt
Certificate RES64: 2C2CCA7B6A1F7703  Time : 4.290 sec.
3*2^2291610+1 is not prime.  Proth RES64: 0000000000000002  Time : 125.660 ms.
***** CERT_DC.TXT
Certificate RES64: 2C2CCA7B6A1F7703  Time : 52.338 sec.
*****

This is because when the random exponent is divisible by 3, the 3rd root of unity turns into 1 and has no effect on the verification process. Generally this works when gcd(random, N-1) != 1.

I strengthened the random to contain no divisors < 10^6. Can also check the gcd, but this doesn't look necessary for Proth numbers.

What do you mean when you say "by multiplying the result by the 3rd root of unitity", what is the "result"?

Why do you use the 3rd root instead of the 2nd root of unity? (I would expect the factor "2" to be the worst in the hash, why not use that?)

How would the attack look for a (small) mersenne number?

[preda]

Originally Posted by Prime95

They are grouped. A very simple recursive routine does the trick.

Grouped -- does that mean that you keep a large number of residues (up to thousands) up in RAM? Or do you R/W temporaries to disk?

[patnashev]

Originally Posted by preda

What do you mean when you say "by multiplying the result by the 3rd root of unitity", what is the "result"?

The y of Pietrzak VDF, the last point that is uploaded along with a proof. But I do the manipulation before calculation of the proof, so all hashes are computed correctly.

Originally Posted by preda

Why do you use the 3rd root instead of the 2nd root of unity?

Because the last point is not the end of the test, there's also a short tail, a few squarings. If I used 2nd root it'd turn into 1 too soon and wouldn't survive until the end of test.

Originally Posted by preda

How would the attack look for a (small) mersenne number?

Find a prime Mersenne number N. Find the smallest factor of N-1 which is not 2. Find root = x^((N-1)/factor) != 1. Multiply the last point by root. Pray that the random exponent has this factor too.

[preda]

Originally Posted by patnashev

The y of Pietrzak VDF, the last point that is uploaded along with a proof. But I do the manipulation before calculation of the proof, so all hashes are computed correctly.
[...]
Find a prime Mersenne number N. Find the smallest factor of N-1 which is not 2. Find root = x^((N-1)/factor) != 1. Multiply the last point by root. Pray that the random exponent has this factor too.

OK it seems I'm a bit slow understanding this, please explain in a bit more detail:

Let's assume N-1 has 3 as a factor.

So you find R3!=1 such that R3^3==1, ok. You multiply Y (the final residue) by R3, this is the "faked result". What do you next?

If you compute the middles in the usual way from the true saved residues, the proof would not verify. -- isn't that so? Even if we say that *all* the random hashes are multiples of 3.

[Prime95]

Originally Posted by preda

Grouped -- does that mean that you keep a large number of residues (up to thousands) up in RAM? Or do you R/W temporaries to disk?

Residues are written to disk as the PRP test progresses. At test end, the residues are read from disk - only one in memory at a time - to produce the proof.

I took "grouped" to mean that we do not raise a residue to the power of a product of hashes (e.g. r0 ^ (h0 * h1 * h2)). My proof-of-concept proof generator is attached. calc_middle is the recursive routine that calculates a Middle value to output.

[Prime95]

Originally Posted by patnashev

The random exponent is required to have no divisors <1000 in my code.

I changed my random exponent to a prime number between 33 and 48 bits. Stole some Rosetta C code for Miller-Rabin test.