3
$\begingroup$

I came across a company that relies on hashing, similar to block chain technology. They explicitly stated in their white paper that hash based cryptographic schemes are inherently post-quantum schemes.

Counter to this, is an article co-authored by Schneier (linked in blog post) that lends support to the idea of Grover's algorithm enabling cryptanalysis of "Keyless Signature Infrastructure" (KSI). Is the position that KSI is inherently a PQC scheme tenable simply because no conventional device is known to have broken it?

It seems like this argument is sleight of hand, given it does not rely on a security reduction of an NP-Hard problem which as I understand is essential to any PQC scheme. Is their use of a modified blockchain method actually post-quantum secure?

Improve this question
$\endgroup$
2
  • $\begingroup$ Are you sure you are linking to the correct article? Currently it points to an article about SHA-1 from 2005 where QC is not mentioned at all. The link to KSI is just that, a link to KSI, nothing particular about the cryptanalysis it seems. $\endgroup$
    – Maarten Bodewes ♦
    Jul 3, 2016 at 7:54
  • 1
    $\begingroup$ I re-read the comments and did some more research. It looks like P=NP is at the heart of this, but since this specific example was focused on block-chain technology in the context of a product, I feel Tylo answered it best. Thank you everyone for your responses. $\endgroup$
    – floor cat
    Jul 8, 2016 at 3:09

3 Answers 3

Reset to default
1
$\begingroup$

Blockchains seem to be a common buzzword these days. And more often than not it is used by people, who don't understand the actual concept in detail. For example, that blockchains are based on assumptions about the distribution of processing power. And when you use it outside the context of bitcoins, you still need an incentive for many people to contribute, so that no party can get close to 50% of the parallel computation power. If that assumption does not hold, there is no security guarantee.

Concerning the KSI construction: I couldn't find any actual description of their algorithms, no cryptanalysis, no formal argument about their security claims. As mephisto already stated in his answer, you need either the random oracle model (hash functions are as secure as truly random functions) or that there is no polynomial QC algorithm for breaking their hash functions. Under the assumption that quantum computers (with poly many qbits) exist, the claim of the RO model might not be reasonable. And for the second assumption: Just if we don't know an algorithm exists does not mean there isn't one.

Regarding the Schneier quote, maybe you meant the quote from Applied Cryptography about ciphers based on hash functions? In short: It might work, it might not. Hashes and encryption have different security definitions, which are just different. (see this answer). The same would apply here: Don't use a construction to try to achieve a different security definition.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I like this response. For this company to actually deliver on what they offer, they need to boost sales. I can picture the marketing going along the lines of promising PQ security, but silently hoping they buy the product so the company can actually meet that standard. $\endgroup$
    – floor cat
    Jul 8, 2016 at 3:07
  • 1
    $\begingroup$ @floorcat Regarding post quantum security, there was somethnig interesting on the Google security blog a few days ago: Experimenting with Post-Quantum Cryptography. (with "New Hope") $\endgroup$
    – tylo
    Jul 11, 2016 at 9:33
2
$\begingroup$

I would just like to know on what basis they can say it is PQC without any NP problem reduction.

I believe that the point you're making is assuming that a Quantum Computer could solve any problem in NP that's not actually NP-complete quickly (or, at least, in polynomial time). That's not known to be true; Quantum Computers would be able to solve some problems (such as factorization) in polynomial time, if $P \ne NP$, there's a whole range of problems in NP that's neither P nor NP-complete.

Improve this answer
$\endgroup$
2
  • $\begingroup$ No, actually the point I'm making is that NP-Hard problems and NP-Complete are required by NIST for any proposed PQC, so why not use a reduction of one if you claim your scheme is PQ-secure? $\endgroup$
    – floor cat
    Jul 8, 2016 at 2:59
  • $\begingroup$ NIST certainly does not require proposed PQ crypto to be NP-hard, only "hard for quantum." In fact, no provably NP-hard cryptosystem has ever been proposed (though many falsely claim or imply such a property). $\endgroup$
    – Chris Peikert
    Jul 10, 2016 at 0:06
0
$\begingroup$

First, the name keyless signature infrastructure is inherently misleading as this actually has nothing to do with real digital signatures, it is rather some kind of time-stamping service.

Now, to answer your actual question: These KSI constructions are solely based on the security of cryptographic hash functions. They do not make use of any other hardness assumption. This is actually the same situation as for hash-based signature schemes. Now, why are such schemes considered "post-quantum" or "quantum-secure"?

First, we know that the best generic quantum attacks against hash functions still have exponential runtime. To be more specific: If we assume the hash function behaves like a random function then Grover's algorithm and its variants are provably optimal and find collisions in $O(2^{n/3})$ and (second-)preimages in $O(2^{n/2})$ for $n$-bit hash functions.

Second, we assume that there are no (quantum or classical) attacks against "engineered" hash functions like SHA2, SHA3, or Blake that perform significantly better than the generic attacks. Of course, this is actually an assumption.

However, in general it seems likely that we will not get cryptographic schemes solely based on $NP$-complete problems (see Yehuda's answer to this question). The other post-quantum candidate schemes just start from some $NP$-complete problem but then select the parameters for that problem differently and/or make use of additional assumptions (like the security of a hash function).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't see how P/=/NP disqualifies the utility of any proven reduction of a problem that can't be solved in polynomial time for any computational device. I followed the link you gave and downloaded the paper they cited. Why would a problem that is NP-Hard not remain NP-Hard for a quantum computer? It seems that if the problem is NP-Hard, then any computational device can't solve the problem in polynomial time. $\endgroup$
    – floor cat
    Jul 8, 2016 at 3:05
  • $\begingroup$ I did not say that NP-Hard problems are not hard for a quantum computer. What I say is that the problems used for cryptography are mostly not NP-Hard. For example in lattice-based crypto people use the approximate versions of SVP and CVP with approximation factors that are bigger than those for which we got NP-Completeness. Other schemes might use NP-complete problems but require additional assumptions like the security of a hash function or a commitment scheme.... $\endgroup$
    – mephisto
    Jul 8, 2016 at 11:32
  • $\begingroup$ I also didn't say that reductionist proofs are useless. Just for hash functions people don't use functions that have a reduction from some intractability assumption as these functions tend to be much slower than the engineered ones. $\endgroup$
    – mephisto
    Jul 8, 2016 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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