4 ms·

It's my understanding that most (all?) public key cryptographic algorithms aren't provably secure, but are conjectured to be. They are reliant on some problem b

It's my understanding that most (all?) public key cryptographic algorithms aren't provably secure, but are conjectured to be. They are reliant on some problem being hard to solve (factoring of large integers, discrete log, etc.). Something like a one time pad is provably secure, however.

egyptiankarim 11y ago
True and fair. I overstated my point. More appropriate to say "provably secure (under practical constraints)", and that's a rather significant caveat.
swordswinger12 11y ago
This is a common misconception. The algorithm itself is provably secure, in the sense that violating the stated security guarantees of the algorithm is equivalent to solving a problem that's considered to be computationally intractable. The only part that isn't 'provable' is the basic assumption that the problem is intractable in the first place.
- ZoF 11y ago
  Didn't you just agree with him but substitute 'hard to solve' with 'computationally intractable'? Yes based on our understanding today these things are computationally expensive (e.g not feasible), but they could theoretically be easy to crack given a mathematical breakthrough. Am I misunderstanding? As the field of mathematics advances there's a chance that current crypto will be broken. Why is this a misconception to point out? Why is it not, on some level, conjecture to say these systems are secure?
  - adenadel 11y ago
    It looks like probably secure is defined in cryptography to mean breaking the algorithm is equivalent to solving the underlying intractable problem [0]. In my mind provably secure meant that the problem was actually intractable (which is not the convention). 0. https://en.wikipedia.org/wiki/Provable_security https://en.wikipedia.org/wiki/Provable_security
    - swordswinger12 11y ago
      That is the conventional meaning of 'provably secure' in every text and research paper on modern cryptography.
  - DigitalJack 11y ago
    All proofs have axioms if you chase them all the way down. Given the axiom that the solving the math in the crypto is intractable, the crypto algorithm is proven secure. But only so long as the axiom holds. For example, quantum computing may break the axiom, and then the proof will be invalidated. It might be more correct to say assumption rather than axiom here.
  - thomasahle 11y ago
    What you are saying was true until this February when this paper came out https://eprint.iacr.org/2016/170 https://eprint.iacr.org/2016/170 It hadn't been implemented yet I'm any practical crypto system that I know of, buy it certainly seems like we are finally going to have actually, provably hard problems to build out security om.
    - LeifCarrotson 11y ago
      I believe you made an unfortunate typo, substituting "probably" when you meant "provably".
      - thomasahle 11y ago
        Even auto correct finds it surprising :-)
    - swordswinger12 11y ago
      The scheme in this paper is in the bounded-storage model...
      - thomasahle 11y ago
        It says you either have to use exponential time or quadratic storage. Schemes based on high memory requirements have actually been sought for a while, since (apparently) memory is considered less scalable than computation.
        swordswinger12 11y ago
        No, I mean your original comment is inaccurate. The paper presents a time-space lower bound for parity learning, but the encryption scheme based on this result is only 'unconditionally secure' in a model where the adversary is restricted to having at most (n^2)/25 bits of storage. This isn't a general-purpose unconditionally secure encryption scheme, which is what your original comment implied.
  - swordswinger12 11y ago
    You're falling victim to the same misconception. It is not a contradiction to say both that a cryptographic scheme is provably secure and that its security relies on a conjecture about the hardness of a computational problem.
    - statictype 11y ago
      If the conjecture turns out to be false, is the scheme still secure? If so - interesting, how does that work? If not - then doesn't that mean it's not probably secure?
      - swordswinger12 11y ago
        Ehhhh.... well, it's complicated. For most cryptosystems, the answer is no, because if you can solve the underlying problem efficiently you can break the security of the scheme as defined. It turns out that this isn't always a 'break' in the sense that most people understand it. For example, a 'break' might just mean the ciphertext is no longer indistinguishable from random noise, but it might be possible to prove meaningful security in a weakened model that doesn't require ciphertexts to look like random noise but, for example, requires that no bits of the plaintext are leaked with high probability. Cryptographers build schemes with very strong, conservative security guarantees for this exact reason.
duaneb 11y ago
Given the breadth of ways to leak information about the private keys--side channel attacks, physical attacks, userspace (allocator, random number generator) this would be extremely difficult (impossible?) to prove.
- stcredzero 11y ago
  It's a well known result that one time pads are provably secure. (Also, no PRNGs are involved.)
  - duaneb 11y ago
    The PRNG is certainly involved in the generation of the one-time pad. You could tell if they used the ascii text of hamlet.
    - rthille 11y ago
      Could be actual random data is used, rather than a PRNG
    - sneak 11y ago
      Using a PRNG to generate an OTP is called a stream cipher, and then it isn't an OTP. :) When using an OTP, you have to use non-pseudorandom values to avoid just being a stream cipher. If you're doing that, you can skip sharing the pad and just share the initial state of the PRNG. If you go to the trouble of sharing the pad, go to the trouble of using random data within it. :)

egyptiankarim 11y ago

True and fair. I overstated my point. More appropriate to say "provably secure (under practical constraints)", and that's a rather significant caveat.

swordswinger12 11y ago

This is a common misconception. The algorithm itself is provably secure, in the sense that violating the stated security guarantees of the algorithm is equivalent to solving a problem that's considered to be computationally intractable. The only part that isn't 'provable' is the basic assumption that the problem is intractable in the first place.

ZoF 11y ago
Didn't you just agree with him but substitute 'hard to solve' with 'computationally intractable'? Yes based on our understanding today these things are computationally expensive (e.g not feasible), but they could theoretically be easy to crack given a mathematical breakthrough. Am I misunderstanding? As the field of mathematics advances there's a chance that current crypto will be broken. Why is this a misconception to point out? Why is it not, on some level, conjecture to say these systems are secure?
- adenadel 11y ago
  It looks like probably secure is defined in cryptography to mean breaking the algorithm is equivalent to solving the underlying intractable problem [0]. In my mind provably secure meant that the problem was actually intractable (which is not the convention). 0. https://en.wikipedia.org/wiki/Provable_security https://en.wikipedia.org/wiki/Provable_security
  - swordswinger12 11y ago
    That is the conventional meaning of 'provably secure' in every text and research paper on modern cryptography.
- DigitalJack 11y ago
  All proofs have axioms if you chase them all the way down. Given the axiom that the solving the math in the crypto is intractable, the crypto algorithm is proven secure. But only so long as the axiom holds. For example, quantum computing may break the axiom, and then the proof will be invalidated. It might be more correct to say assumption rather than axiom here.
- thomasahle 11y ago
  What you are saying was true until this February when this paper came out https://eprint.iacr.org/2016/170 https://eprint.iacr.org/2016/170 It hadn't been implemented yet I'm any practical crypto system that I know of, buy it certainly seems like we are finally going to have actually, provably hard problems to build out security om.
  - LeifCarrotson 11y ago
    I believe you made an unfortunate typo, substituting "probably" when you meant "provably".
    - thomasahle 11y ago
      Even auto correct finds it surprising :-)
  - swordswinger12 11y ago
    The scheme in this paper is in the bounded-storage model...
    - thomasahle 11y ago
      It says you either have to use exponential time or quadratic storage. Schemes based on high memory requirements have actually been sought for a while, since (apparently) memory is considered less scalable than computation.
      - swordswinger12 11y ago
        No, I mean your original comment is inaccurate. The paper presents a time-space lower bound for parity learning, but the encryption scheme based on this result is only 'unconditionally secure' in a model where the adversary is restricted to having at most (n^2)/25 bits of storage. This isn't a general-purpose unconditionally secure encryption scheme, which is what your original comment implied.
- swordswinger12 11y ago
  You're falling victim to the same misconception. It is not a contradiction to say both that a cryptographic scheme is provably secure and that its security relies on a conjecture about the hardness of a computational problem.
  - statictype 11y ago
    If the conjecture turns out to be false, is the scheme still secure? If so - interesting, how does that work? If not - then doesn't that mean it's not probably secure?
    - swordswinger12 11y ago
      Ehhhh.... well, it's complicated. For most cryptosystems, the answer is no, because if you can solve the underlying problem efficiently you can break the security of the scheme as defined. It turns out that this isn't always a 'break' in the sense that most people understand it. For example, a 'break' might just mean the ciphertext is no longer indistinguishable from random noise, but it might be possible to prove meaningful security in a weakened model that doesn't require ciphertexts to look like random noise but, for example, requires that no bits of the plaintext are leaked with high probability. Cryptographers build schemes with very strong, conservative security guarantees for this exact reason.

duaneb 11y ago

Given the breadth of ways to leak information about the private keys--side channel attacks, physical attacks, userspace (allocator, random number generator) this would be extremely difficult (impossible?) to prove.

stcredzero 11y ago
It's a well known result that one time pads are provably secure. (Also, no PRNGs are involved.)
- duaneb 11y ago
  The PRNG is certainly involved in the generation of the one-time pad. You could tell if they used the ascii text of hamlet.
  - rthille 11y ago
    Could be actual random data is used, rather than a PRNG
  - sneak 11y ago
    Using a PRNG to generate an OTP is called a stream cipher, and then it isn't an OTP. :) When using an OTP, you have to use non-pseudorandom values to avoid just being a stream cipher. If you're doing that, you can skip sharing the pad and just share the initial state of the PRNG. If you go to the trouble of sharing the pad, go to the trouble of using random data within it. :)