3 ms·

Isn't that a bit like "security through obscurity"? Unless I'm misunderstanding something, the cryptographic algorithm that the AI comes up with isn't guarantee

by pzh 10y ago

Isn't that a bit like "security through obscurity"? Unless I'm misunderstanding something, the cryptographic algorithm that the AI comes up with isn't guaranteed to be based on a provably NP-hard problem, so there aren't any formal guarantees. It would also be very hard to reason about, inspect, and prove correct. Please note that I'm in no way dissing the researchers' work. What they did is pretty cool, but I can't see an obvious way to use these AI-generated algorithms in production systems where you may need to certify their correctness.

paradite 10y ago
You may be right. It was mentioned in the paper: Our chosen network structure is not sufficient to learn general implementations of many of the mathematical concepts underlying modern asymmetric cryptography, such as integer modular arithmetic. We therefore believe that the most likely explanation for this successful training run was that Alice and Bob accidentally obtained some “security by obscurity” (cf. the derivation of asymmetric schemes from symmetric schemes by obfuscation (Barak et al., 2012)). This belief is somewhat reinforced by the fact that the training result was fragile: upon further training of Alice and Bob, Eve was able to decrypt the messages. However, we cannot rule out that the networks trained into some set of hard-to-invert matrix operations resulting in “public-key-like” behavior. Our results suggest that this issue deserves more exploration.
- dgacmu 10y ago
  Note that this was for the public-key formulation. For the secret key formulation, it is mixing in the key, so it's not pure security through obscurity. It may be -- probably is -- relatively poor cryptography, but it's not just doing a transformation of the plaintext without using the key. The public key part is in there mostly because of the formulation, not because we actually had any noteworthy success in training a network to learn pubkey. The result we mentioned was probably an anomaly, but it's an interesting anomaly to dig into more in the future. But, in general, the parent is correct. There are few guarantees about a scheme derived in this way. It's one of the things I think most interesting for future work: Can one formulate "can't be cryptanalyzed by a mathematically sophisticated adversary?" as an adversarial training goal? Certainly, it's solvable for the one-time-pad-like scenario we used, but what about for more general cases that permit key reuse?
  - thomasahle 10y ago
    > Certainly, it's solvable for the one-time-pad-like scenario we used, but what about for more general cases that permit key reuse? Can't you force this simply by making the message a lot longer than the key? If the network can encrypt variable length messages, surely the method must be more advanced than a one time pad.
benkuykendall 10y ago
>> The cryptographic algorithm that the AI comes up with isn't guaranteed to be based on a provably NP-hard problem, so there aren't any formal guarantees. There are no cryptographic schemes, either in theory or in practice, that reduce to NP-hard problems. Instead, they rely on different "cryptographic hardness assumption" including factoring (and related number-theoretic problems) and a variety of so-called "lattice" problems. Are these assumptions as sure as P!=NP? No, they are explicitly stronger. Are they better cryptosystems than this work generates? Almost surely. In you are interested, there are actually some negative results that suggest it would be impossible to do cryptography based on NP-hardness alone. Akavia, Goldreich, Goldwasser, Moshkovitz show this for a restricted class of NP-hard problems in a 2006 paper [http://people.csail.mit.edu/akavia/AGGM.pdf http://people.csail.mit.edu/akavia/AGGM.pdf]. More philosophically, there is a big difference between computational hardness and cryptography: in complexity, we study worst-case hardness, but in cryptography, we need breaking a cipher (for example) to be hard with very high probability. Rather surprisingly, there seems to be a big difference between these two goals.

by pzh 10y ago

paradite 10y ago

You may be right. It was mentioned in the paper: Our chosen network structure is not sufficient to learn general implementations of many of the mathematical concepts underlying modern asymmetric cryptography, such as integer modular arithmetic. We therefore believe that the most likely explanation for this successful training run was that Alice and Bob accidentally obtained some “security by obscurity” (cf. the derivation of asymmetric schemes from symmetric schemes by obfuscation (Barak et al., 2012)). This belief is somewhat reinforced by the fact that the training result was fragile: upon further training of Alice and Bob, Eve was able to decrypt the messages. However, we cannot rule out that the networks trained into some set of hard-to-invert matrix operations resulting in “public-key-like” behavior. Our results suggest that this issue deserves more exploration.

dgacmu 10y ago
Note that this was for the public-key formulation. For the secret key formulation, it is mixing in the key, so it's not pure security through obscurity. It may be -- probably is -- relatively poor cryptography, but it's not just doing a transformation of the plaintext without using the key. The public key part is in there mostly because of the formulation, not because we actually had any noteworthy success in training a network to learn pubkey. The result we mentioned was probably an anomaly, but it's an interesting anomaly to dig into more in the future. But, in general, the parent is correct. There are few guarantees about a scheme derived in this way. It's one of the things I think most interesting for future work: Can one formulate "can't be cryptanalyzed by a mathematically sophisticated adversary?" as an adversarial training goal? Certainly, it's solvable for the one-time-pad-like scenario we used, but what about for more general cases that permit key reuse?
- thomasahle 10y ago
  > Certainly, it's solvable for the one-time-pad-like scenario we used, but what about for more general cases that permit key reuse? Can't you force this simply by making the message a lot longer than the key? If the network can encrypt variable length messages, surely the method must be more advanced than a one time pad.

benkuykendall 10y ago

>> The cryptographic algorithm that the AI comes up with isn't guaranteed to be based on a provably NP-hard problem, so there aren't any formal guarantees. There are no cryptographic schemes, either in theory or in practice, that reduce to NP-hard problems. Instead, they rely on different "cryptographic hardness assumption" including factoring (and related number-theoretic problems) and a variety of so-called "lattice" problems. Are these assumptions as sure as P!=NP? No, they are explicitly stronger. Are they better cryptosystems than this work generates? Almost surely. In you are interested, there are actually some negative results that suggest it would be impossible to do cryptography based on NP-hardness alone. Akavia, Goldreich, Goldwasser, Moshkovitz show this for a restricted class of NP-hard problems in a 2006 paper [http://people.csail.mit.edu/akavia/AGGM.pdf http://people.csail.mit.edu/akavia/AGGM.pdf]. More philosophically, there is a big difference between computational hardness and cryptography: in complexity, we study worst-case hardness, but in cryptography, we need breaking a cipher (for example) to be hard with very high probability. Rather surprisingly, there seems to be a big difference between these two goals.