2
$\begingroup$

Is there any proof that BLAKE (including 2 and 3) is post-quantum secure? We know that as Merkle–Damgård (with proper padding) preserves collapse sha2 is post-quantum secure. I know that the sponge-based winner of the sha3 competition does not have such a proof. Since BLAKE uses neither of these constructions has there been any research as to whether it's construction is post-quantum secure?

$\endgroup$
1
$\begingroup$

There is no proof, there are only advancements. BLAKE2 is not completely MD, it is HAIFA which extends the MD to eliminate the problems and BLAKE3 is a parallel hash.

Quamtum collision attack costs

The best know generic quantum collision is the takes $\mathcal{O}(2^{n/3})$ time due to Brassard–Høyer–Tapp (BHT). It is usually advertised (even by the NIST) with only the time but we have other costs, too. BHT builds a huge table of size $\mathcal{O}(2^{n/3})$ then runs the Grover's algorithm with the cost $\mathcal{O}(2^{n/3})$ and this make a total cost $\mathcal{O}(2^{2n/3})$

None of the variants, including the Ambainis algorithm which has still cost around $\mathcal{O}(2^{2n/3})$, doesn't lower the cost barrier of the classical attack cost $\mathcal{O}(2^{n/2})$

We already know that there is a lower bound on number of queries a generic algorithm mus take $\Omega(2^{n/3})$

So there are no threats from QC that we can see.

Quantum Pre-Images attack cost

Grover's algorithm is the best generic algorithm with $\mathcal{O}$-time and doesn't use much space as the BHT or others. But the sequential evaluation of the hash function is the problem there. Even you evaluate one in a nano-second you can get at most $2^{54}$ in a year and you need $2^{64}$-year to find the pre-images. The other cost is not included. One can run Grover's algorithm in parallel, however, the advantage not the same as the classical one, you will get $\sqrt k$ speed up from $k$ machines.

Therefore if you have 256-bit output, you will be safe from quantum attacks for hash functions.


Collapsibility

Collapsibility is defined by Unruh as a quantum equivalent of collision resistance of hash functions.

Informally, for cryptographic hash functions, collapseability requires an adversary that outputs a hash value together with a superposition of corresponding preimages is not able to tell if the superposition gets measured or not.

The result of Unruh is this

showed that there is a hash function that is collision-resistant and thus can safely be used in a classical commitment scheme, but is not secure when the commitment scheme is used in a quantum setting

so we have a one-way relation;

-Collapsability implies Collision resistance.

Fer showed that

He applied the approach to the Merkle-Damgård and sponge hash construction, proving that they are collapsing if the underlying compression function is.

Gunns and Manning showed that

  1. Binary tree hash of fixed length is collapsing.
  2. Variable Length tree hashing with Domain Separation is collapsing.
$\endgroup$
4
  • $\begingroup$ Do you know if there is any work on proving if HAIFA is collapsing? Alternatively, do you know if the tree hashing mode used with BLAKE3 is collapsing as per cs.ru.nl/~bmennink/pubs/20pqc.pdf ? $\endgroup$
    – augustus
    May 1 at 17:27
  • $\begingroup$ @augustus Added some notes about that. The interesting point will be a real hash function that considered to have collision resistance but fails collapsability. $\endgroup$
    – kelalaka
    May 1 at 22:39
  • $\begingroup$ If I am not mistaken BLAKE3 uses "Variable Length tree hashing with Domain Separation" so as long as the primitive (its modified chacha) is collapsing we can say that BLAKE3 is collapsing but we can't really say anything about whether BLAKE2 is collapsing, right? $\endgroup$
    – augustus
    May 3 at 15:08
  • $\begingroup$ BLAKE3 has built-in XOF ( eXtendibale Output Function). [Domain separation](domain separation) is not a built-in property of hash functions. The authors used it to show that if used in this case the collapsable. $\endgroup$
    – kelalaka
    May 4 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.