5 ms·

"if modern cryptography is broken": this statement has many interpretations. In the context of the OP paper, approximately solving the t-bounded Kolmogorov com

by abhv 5y ago

"if modern cryptography is broken": this statement has many interpretations. In the context of the OP paper, approximately solving the t-bounded Kolmogorov complexity (in a precise technical sense described in that paper) is akin to breaking one-way functions. A method to breaking one-way functions would in fact break all of the cryptographic schemes (enc, signatures, prgs, hashing, zero-knowledge, mpc, bitcoin...) that rely on computational assumptions that we know. There is then no hope for doing things like we do on the internet today. A secondary interpretation relates to breaking a specific widespread cryptosystem like ECDSA or Ed25519 (which can both be broken with suitably large generic circuit quantum computers). In this context, maybe some important things break, but in principle, we can rebuild them using lattice-based schemes or something else.

l33t2328 5y ago
Hashing would be generally be fine. AES would still be totally okay.
- thiagoharry 5y ago
  No and no. If a hash function is not an one-way function, it cannot be collision-resistant. And the security in AES assumes that it is an one-way function. Otherwise, anyone could decrypt reversing the function.
  - l33t2328 5y ago
    You have some slight misunderstanding. AES does not need to be a one way function. It’s trivial to compute the preimage of a ciphertext. Just choose any key and decrypt it.
- mdoms 5y ago
  I'm a layperson, but isn't hashing the quintessential one way function? (at least for industry software engineers).
  - denton-scratch 5y ago
    /me also layman. Hash functions are irreversible; a potentially-infinite number of inputs all map to the same output. I think the one-way functions referred to are what used to be called trap-door functions. They're not irreversible, like hash functions; they're computationally hard to reverse, unless you happen to know the key to open the trap-door.
    - jasperry 5y ago
      One-way functions are definitely not trap-door functions, they are a weaker assumption. But you can get all symmetric cryptography out of a one-way function; it doesn't have to be reversible. For instance, you can use a hash function to encrypt, by XORing its output with a plaintext, using it as a stream cipher.
    - Banana699 5y ago
      >Hash functions are irreversible; a potentially-infinite number of inputs all map to the same output. I don't think that's pre-image resistance, or else extremely trivial "Hash functions" like - Line up the input string into a matrix of n columns, XOR every column into a single bit, output the resulting n-bit hash. Would be pre-image resistant, but it's obviously not. Given an n-bit hash I can trivially generate a message that hashes to it. Generally, there are at least 3 notions of irreversiblity that might get confused: - Non-bijectivity : That just means the set of images is smaller than the set of pre-images, so it's impossible (in general) to tell what input produced a given image. If F(x) == 1 for all x in X, it's impossible to tell which x was evaluated in order to get a 1. This is what you described, and it's - by itself - useless security-wise. - One-way functions : Given x, its reasonably efficient to calculate y = F(x). But given y = F(x), it's prohibitively expensive to recover x = F^-1(y). The function is easy to compute in one direction, and practically impossible in the other. The inverse might very will exist, maybe even infinite inverses exist for every y, but you would need the computational resources of a thousand thousand universe working for a thousand thousand epoch to even get close to finding a single one. - Trap-door functions : They are special one-way functions that have the property that : given a special piece of information about x or y (an inequality, a prime factor,....), x = F^-1(y) suddenly becomes much easier to compute, maybe even as easy as y = F(x).

by abhv 5y ago

l33t2328 5y ago

Hashing would be generally be fine. AES would still be totally okay.

thiagoharry 5y ago
No and no. If a hash function is not an one-way function, it cannot be collision-resistant. And the security in AES assumes that it is an one-way function. Otherwise, anyone could decrypt reversing the function.
- l33t2328 5y ago
  You have some slight misunderstanding. AES does not need to be a one way function. It’s trivial to compute the preimage of a ciphertext. Just choose any key and decrypt it.
mdoms 5y ago
I'm a layperson, but isn't hashing the quintessential one way function? (at least for industry software engineers).
- denton-scratch 5y ago
  /me also layman. Hash functions are irreversible; a potentially-infinite number of inputs all map to the same output. I think the one-way functions referred to are what used to be called trap-door functions. They're not irreversible, like hash functions; they're computationally hard to reverse, unless you happen to know the key to open the trap-door.
  - jasperry 5y ago
    One-way functions are definitely not trap-door functions, they are a weaker assumption. But you can get all symmetric cryptography out of a one-way function; it doesn't have to be reversible. For instance, you can use a hash function to encrypt, by XORing its output with a plaintext, using it as a stream cipher.
  - Banana699 5y ago
    >Hash functions are irreversible; a potentially-infinite number of inputs all map to the same output. I don't think that's pre-image resistance, or else extremely trivial "Hash functions" like - Line up the input string into a matrix of n columns, XOR every column into a single bit, output the resulting n-bit hash. Would be pre-image resistant, but it's obviously not. Given an n-bit hash I can trivially generate a message that hashes to it. Generally, there are at least 3 notions of irreversiblity that might get confused: - Non-bijectivity : That just means the set of images is smaller than the set of pre-images, so it's impossible (in general) to tell what input produced a given image. If F(x) == 1 for all x in X, it's impossible to tell which x was evaluated in order to get a 1. This is what you described, and it's - by itself - useless security-wise. - One-way functions : Given x, its reasonably efficient to calculate y = F(x). But given y = F(x), it's prohibitively expensive to recover x = F^-1(y). The function is easy to compute in one direction, and practically impossible in the other. The inverse might very will exist, maybe even infinite inverses exist for every y, but you would need the computational resources of a thousand thousand universe working for a thousand thousand epoch to even get close to finding a single one. - Trap-door functions : They are special one-way functions that have the property that : given a special piece of information about x or y (an inequality, a prime factor,....), x = F^-1(y) suddenly becomes much easier to compute, maybe even as easy as y = F(x).