5 ms·

> The UK government has conceded it will not use controversial powers in the online safety bill to scan messaging apps for harmful content until it is “technica

> The UK government has conceded it will not use controversial powers in the online safety bill to scan messaging apps for harmful content until it is “technically feasible” to do so (...) That would be waiting for a quantum computer and quietly hoping that a) nobody develops a strong enough post-quantum scheme and b) there is still civilization after RSA and ECC are broken? Correct me if I'm wrong.

deleted 3y ago
[deleted]
monero-xmr 3y ago
Quantum computing doesn’t matter. Nothing in the universe can break a one time pad.
- blurbleblurble 3y ago
  Underappreciated fact
- contact9879 3y ago
  Once again, every cryptographic problem reduces to a key distribution problem :)
- phoe-krk 3y ago
  And nothing in the post-quantum universe seems to reliably solve the problem of transmitting a one-time pad.
- maxbond 3y ago
  Is quantum computing relevant to symmetric encryption like OTP? GP was talking about asymmetric encryption. My limited understanding is that quantum computing is a threat to asymmetric encryption. There's also the question of, if you can distribute a key which is at least the same size as your message over a secure channel - why not just distribute your message over that channel in the first place?
  - karmanyaahm 3y ago
    > why not just distribute your message over that channel in the first place Latency? You can hand deliver a password ahead of time, but not messages.
    - ianburrell 3y ago
      One-time pad isn't a password. It is a flash drive or hard drive full of random bits.
      - InitialLastName 3y ago
        The difference between those is just one of scale and storage. You still have to reliably move a chunk of out-of-band information in a way such that it gets to (and only gets to) the person you want to have it.
        ianburrell 3y ago
        The difference between one-time pad and stream cipher is provable, absolute secrecy, and really good secrecy. If don't care about that, there is zero point to one-time pad. Also, it isn't just a "chunk", for one-time pad it has to be the same length as the messages. Which is fine if just short messages but a lot harder if lots of data. If can exchange lots of data, better off using them as keys for stream cipher.
  - aetherson 3y ago
    One-time pads are obviously not a serious widespread cryptography proposal. But the question of, "Why not just send the message instead of the pad" is pretty straightforward: when you have the opportunity to safely deliver the pad, you don't know what the message will be. When you do know what the message will be, you don't have the opportunity to safely deliver the pad.
  - hgomersall 3y ago
    Because with QKD you can distribute a random key knowing that there were no observers but you cannot distribute a message with the same guarantees. Specifically, any given bit exchanged might be observed, but that is detectable so the bit can be discarded. I read some years ago about a non quantum technique to achieve the same based on (I think) noise in a coupled electronic system. I wonder if that has been tested further.
- numpad0 3y ago
  But quantum computing can put the ciphertext in a quantum superposition between solved and unsolved state. Only problem to remain will be simple matter of determining what the plaintext is to be.
- grotorea 3y ago
  Doing some armchair navel gazing cryptanalysis, but isn't that only true if you assume the OTP has access to true randomness? What if the attacker breaks your CSPRNG? Or what if the universe is deterministic and therefore a true RNG is impossible?
  - maxbond 3y ago
    Similarly relaxing in my armchair, a deterministic universe is compatible with a CSPRNG as long as the information required to recover it's internal state is too diffuse to recover, or is outside the light cone of your adversary. Eg, rolling a dice is deterministic, and I imagine an algorithm exists that could recover the value of a dice throw from a recording of the sound of it rolling and it's initial position. But once that sound has turned into heat, and that heat has conducted itself about the walls and into the air, I don't think it's possible to recover the sound. See also: "Is flipping a coin random?" (Numberphile) https://www.youtube.com/watch?v=AYnJv68T3MM https://www.youtube.com/watch?v=AYnJv68T3MM [8m]
    - jamiek88 3y ago
      It’s possible. As in physics says it can be done. But it isn’t technically feasible, probably ever. There’s nothing in the laws of physics that prohibits us turning burned paper smoke back into a document and recover the information.
      - maxbond 3y ago
        I'm not sure physics really does say that. Physicists seem to believe that information is never lost - but that doesn't mean the information can be retrieved. If it's in a fragile state, then the act of measuring it might change it. Eg an electron has both a position and a momentum, but that doesn't mean you can measure it's velocity. When you burn a document, all the matter might be transferred into the smoke, but you've rendered it into a stream of particles which is small enough to be effected by Brownian motion. Reversing the process (figuring out the initial position of each soot particle) involves knowing the position and momentum of the air molecules impacting the soot particles. In principle, you could take the current position and momentum of those particles and extrapolate backwards - but you can't actually measure that, not even in theory.
- Sohcahtoa82 3y ago
  This isn't the first time I've seen someone on HN act like one-time pads are the solution to all of the problems of cryptography. It's like people read that OTPs are the only encryption method that has been proven to be completely unbreakable (when used correctly) and stop reading there, and then completely miss all the things OTPs don't solve (ie, guaranteeing authenticity), not to mention their massive glaring limitation: How do you transfer the encryption key?
paxys 3y ago
"Strong enough post-quantum schemes" already exist, and every single mainstream communications platform will update to become quantum-proof overnight if/when quantum computers approach that level of capability. Quantum computers cracking encryption is really not a concern on anyone's mind, at least no more than, say, modern processors cracking SHA-1 etc.
- phoe-krk 3y ago
  TIL! Which ones? I've only seen ones that were proclaimed to be secure, only to be broken in some simple/clever ways not much later.
  - mrguyorama 3y ago
    You can basically just make the numbers bigger. Quantum computers aren't magic, and are still limited in what and how they can process within normal informational theories.
  - tux3 3y ago
    There were a lot of pqcrypto candidates, and several of them were indeed thoroughly broken, prey to the fearsome cryptanalyst's laptop left running over a weekend NIST standardized Kyber and Dilithium, and for now at least, they seem to be holding up. I'd still want to do hybrid (ECC+PQ) asymmetric crypto for the time being, but we're (slowly) starting to gain a modicum of confidence in the new standards, enough for deployment
  - sweis 3y ago
    NIST post-quantum standards resulted from a 8+ year process and public competition: https://csrc.nist.gov/projects/post-quantum-cryptography https://csrc.nist.gov/projects/post-quantum-cryptography
toyg 3y ago
Oh no. That "technically feasible" translates to "when the government will be able to pass the practical parts of this legislation without too many people asking too many questions".
jmilosze 3y ago
It's already perfectly feasible to do. Meta/Apple etc. can just deploy a client that decrypts the message, scans it, re-encrypts (with a different key) and sends it to their storage where they can store it forever and decrypt if needed. This way they could even have different clients in different regions still being compatible. It's just that it would suck and would not be secure any more.
xkcd-sucks 3y ago
"I promise I will not stab you until I acquire a knife"

deleted 3y ago

[deleted]

monero-xmr 3y ago

Quantum computing doesn’t matter. Nothing in the universe can break a one time pad.

blurbleblurble 3y ago
Underappreciated fact
contact9879 3y ago
Once again, every cryptographic problem reduces to a key distribution problem :)
phoe-krk 3y ago
And nothing in the post-quantum universe seems to reliably solve the problem of transmitting a one-time pad.
maxbond 3y ago
Is quantum computing relevant to symmetric encryption like OTP? GP was talking about asymmetric encryption. My limited understanding is that quantum computing is a threat to asymmetric encryption. There's also the question of, if you can distribute a key which is at least the same size as your message over a secure channel - why not just distribute your message over that channel in the first place?
- karmanyaahm 3y ago
  > why not just distribute your message over that channel in the first place Latency? You can hand deliver a password ahead of time, but not messages.
  - ianburrell 3y ago
    One-time pad isn't a password. It is a flash drive or hard drive full of random bits.
    - InitialLastName 3y ago
      The difference between those is just one of scale and storage. You still have to reliably move a chunk of out-of-band information in a way such that it gets to (and only gets to) the person you want to have it.
      - ianburrell 3y ago
        The difference between one-time pad and stream cipher is provable, absolute secrecy, and really good secrecy. If don't care about that, there is zero point to one-time pad. Also, it isn't just a "chunk", for one-time pad it has to be the same length as the messages. Which is fine if just short messages but a lot harder if lots of data. If can exchange lots of data, better off using them as keys for stream cipher.
- aetherson 3y ago
  One-time pads are obviously not a serious widespread cryptography proposal. But the question of, "Why not just send the message instead of the pad" is pretty straightforward: when you have the opportunity to safely deliver the pad, you don't know what the message will be. When you do know what the message will be, you don't have the opportunity to safely deliver the pad.
- hgomersall 3y ago
  Because with QKD you can distribute a random key knowing that there were no observers but you cannot distribute a message with the same guarantees. Specifically, any given bit exchanged might be observed, but that is detectable so the bit can be discarded. I read some years ago about a non quantum technique to achieve the same based on (I think) noise in a coupled electronic system. I wonder if that has been tested further.
numpad0 3y ago
But quantum computing can put the ciphertext in a quantum superposition between solved and unsolved state. Only problem to remain will be simple matter of determining what the plaintext is to be.
grotorea 3y ago
Doing some armchair navel gazing cryptanalysis, but isn't that only true if you assume the OTP has access to true randomness? What if the attacker breaks your CSPRNG? Or what if the universe is deterministic and therefore a true RNG is impossible?
- maxbond 3y ago
  Similarly relaxing in my armchair, a deterministic universe is compatible with a CSPRNG as long as the information required to recover it's internal state is too diffuse to recover, or is outside the light cone of your adversary. Eg, rolling a dice is deterministic, and I imagine an algorithm exists that could recover the value of a dice throw from a recording of the sound of it rolling and it's initial position. But once that sound has turned into heat, and that heat has conducted itself about the walls and into the air, I don't think it's possible to recover the sound. See also: "Is flipping a coin random?" (Numberphile) https://www.youtube.com/watch?v=AYnJv68T3MM https://www.youtube.com/watch?v=AYnJv68T3MM [8m]
  - jamiek88 3y ago
    It’s possible. As in physics says it can be done. But it isn’t technically feasible, probably ever. There’s nothing in the laws of physics that prohibits us turning burned paper smoke back into a document and recover the information.
    - maxbond 3y ago
      I'm not sure physics really does say that. Physicists seem to believe that information is never lost - but that doesn't mean the information can be retrieved. If it's in a fragile state, then the act of measuring it might change it. Eg an electron has both a position and a momentum, but that doesn't mean you can measure it's velocity. When you burn a document, all the matter might be transferred into the smoke, but you've rendered it into a stream of particles which is small enough to be effected by Brownian motion. Reversing the process (figuring out the initial position of each soot particle) involves knowing the position and momentum of the air molecules impacting the soot particles. In principle, you could take the current position and momentum of those particles and extrapolate backwards - but you can't actually measure that, not even in theory.
Sohcahtoa82 3y ago
This isn't the first time I've seen someone on HN act like one-time pads are the solution to all of the problems of cryptography. It's like people read that OTPs are the only encryption method that has been proven to be completely unbreakable (when used correctly) and stop reading there, and then completely miss all the things OTPs don't solve (ie, guaranteeing authenticity), not to mention their massive glaring limitation: How do you transfer the encryption key?

paxys 3y ago

"Strong enough post-quantum schemes" already exist, and every single mainstream communications platform will update to become quantum-proof overnight if/when quantum computers approach that level of capability. Quantum computers cracking encryption is really not a concern on anyone's mind, at least no more than, say, modern processors cracking SHA-1 etc.

phoe-krk 3y ago
TIL! Which ones? I've only seen ones that were proclaimed to be secure, only to be broken in some simple/clever ways not much later.
- mrguyorama 3y ago
  You can basically just make the numbers bigger. Quantum computers aren't magic, and are still limited in what and how they can process within normal informational theories.
- tux3 3y ago
  There were a lot of pqcrypto candidates, and several of them were indeed thoroughly broken, prey to the fearsome cryptanalyst's laptop left running over a weekend NIST standardized Kyber and Dilithium, and for now at least, they seem to be holding up. I'd still want to do hybrid (ECC+PQ) asymmetric crypto for the time being, but we're (slowly) starting to gain a modicum of confidence in the new standards, enough for deployment
- sweis 3y ago
  NIST post-quantum standards resulted from a 8+ year process and public competition: https://csrc.nist.gov/projects/post-quantum-cryptography https://csrc.nist.gov/projects/post-quantum-cryptography

toyg 3y ago

Oh no. That "technically feasible" translates to "when the government will be able to pass the practical parts of this legislation without too many people asking too many questions".

jmilosze 3y ago

It's already perfectly feasible to do. Meta/Apple etc. can just deploy a client that decrypts the message, scans it, re-encrypts (with a different key) and sends it to their storage where they can store it forever and decrypt if needed. This way they could even have different clients in different regions still being compatible. It's just that it would suck and would not be secure any more.

xkcd-sucks 3y ago

"I promise I will not stab you until I acquire a knife"