3
$\begingroup$

When I'm convincing non-believers that crypto is secure, I have a hard time with hash functions and the associated block ciphers.

It is easy to show why RSA is hard to crack: I multiply two small primes and ask people to factorize the product. They find it difficult compared to the multiplication step.

It is easy to show how Vernam cipher is secure: I tell them an Alice and Bob story with a flipping coin as an RNG.

But when it comes to the hashing, I am not even sure I know the underlying mathematical problem. It would be great to have a small intuitive example of that problem for illustration.

If it is indeed the boolean satisfiablity problem then I can at least mention that it is the hardest in the NP class, and if we solve it then P=NP, because many have heard about that.

I can use the argument that greed is innate to human nature and if there is at least one person who knows how to reverse hashes, they will incessantly mine crypto out of thin air and the exchange rate will eventually drop. But it is somewhat shaky I think.

$\endgroup$
3
  • 5
    $\begingroup$ "It is easy to show why RSA is hard to crack: I multiply two small primes and ask people to factorize the product. They find it difficult compared to the multiplication step." That's lie-to-children territory. The hardness of factoring is not known to imply security of RSA. $\endgroup$
    – Maeher
    Nov 10, 2022 at 9:20
  • 3
    $\begingroup$ We can make a relatively convincing lie-to-children about how secure hashes are possible. For even word width $n$, for any $k\in[1,n/2)$, function$$\begin{align}f_k:\{0,1\}^n&→\{0,1\}^n\\u\mathbin\|v\;&↦(((u≪k)⊕(u≫(n-k)))+v)\mathbin\|u\end{align}$$(where $u$ and $v$ are $n/2$-bit bitstrings assimilated to integers modulo $2^{n/2}$) is a bijection. Now fix enough public haphazard $k_0,k_1…k_ℓ$. The function $f_{k_0}∘f_{k_1}∘…∘f_{k_ℓ}$ is an haphazard bijection $g$. Now form$$\begin{align}h:\{0,1\}^n&→\{0,1\}^n\\w\;&↦w⊕g(w)\end{align}$$and we have a "clearly" hard to invert haphazard function. $\endgroup$
    – fgrieu
    Nov 10, 2022 at 10:48
  • 1
    $\begingroup$ SAT is a mathematical problem behind every algorithm in NP. Both the easy ones and the hard ones. $\endgroup$
    – user253751
    Feb 3, 2023 at 20:39

1 Answer 1

4
$\begingroup$

Cryptographic problems should be hard in average. NP-Complete problems such that SAT are supposed to be hard in the worst case. But, for many practical distributions, SAT is not hard in average.

If it is indeed the boolean satisfiability problem then I can at least mention that it is the hardest in the NP class

This sentence is wrong, if we consider a specific distribution on inputs.

To conclude briefly the answer is no. But, if P=NP, then no efficient cryptographic constructions are possible at all (neither symmetric nor asymmetric).

Here efficient means with asymptotic exponential gap between the standard operations (encryption, decryption, signature, etc), and the cryptanalysis.

You can read about the Impagliazzo's Five Worlds, if you want more details about this comparison.

$\endgroup$
8
  • 1
    $\begingroup$ They are not known to be hard in the worst case. They are assumed to be hard in the worst case and mostly known to be easy in the average case. $\endgroup$
    – Maeher
    Nov 10, 2022 at 9:15
  • $\begingroup$ > But, if P=NP, then no cryptographic constructions are possible at all (neither symmetric nor asymmetric). I think that is oversimplified. Even if P=NP, fine-grained separations may be a thing (i.e. it might be possible to get constructions where the legitimate receiver has an advantage over the adversary that is merely polynomial (in some problem size parameter that we handwave in by embedding whatever construction we are looking at into a family of similar constructions that depend on a variable-size security parameter), but nonetheless sufficient for their security needs. $\endgroup$
    – Polytropos
    Nov 10, 2022 at 9:33
  • $\begingroup$ I see why the implications from P=NP hold for computational security but is this also true for perfect and quantum security? $\endgroup$
    – Titanlord
    Nov 10, 2022 at 9:39
  • $\begingroup$ @Polytropos If I write efficient cryptographic constructions, does it seemed to you more correct? $\endgroup$
    – Ievgeni
    Nov 10, 2022 at 10:09
  • 2
    $\begingroup$ The P vs NP question is only relevant in an asymptotic setting. Asymptotically AES is broken anyway. Concrete security is a completely different question. $\endgroup$
    – Maeher
    Nov 10, 2022 at 13:00

Your Answer

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

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