3 ms·

A next-word-in-the-sentence prediction engine can’t predict the factor of two insanely large prime numbers… tell me more

dadrian 2mo ago
RSA is asymmetric crypto. This article is about symmetric cryptography. I expect LLMs will advance state of the art in factoring algorithms, considerably.
- what 2mo ago
  Why?
- sghiassy 2mo ago
  Thank you I guess I only know asymmetric cryptography. I should learn more about symmetric… Anyone care to boil it down for me :) Edit: Isn’t this just advanced static analysis of any code base?
  - fluoridation 2mo ago
    Very, very briefly, most symmetric algorithms are block ciphers, meaning that their input are blocks of a fixed length in bits (plus a key), and their output is another block of the same length. Ideally, a block cipher with its key produces a random permutation of the input space into the output space, thus diluting the information and dramatically increasing (ideally maximizing) the entropy; what that means is that whether the input is just zeroes and ones in ASCII or fully random, after encryption it should be indistinguishable.
    - sghiassy 2mo ago
      Thank you I wish I knew more in this domain. It almost sounds like hashing with a salt
      - fluoridation 2mo ago
        It pretty much is, except it's reversible. At the block level it meets the cascading requirement, and you can set it up to expand the output arbitrarily by padding the input with zeroes (thus also turning it into a PRNG).
  - retrac 2mo ago
    A symmetric cipher is: ciphertext = data XOR key. XOR is reversible: plaintext = ciphertext XOR key. If the key is a set of truly random numbers the same size as the ciphertext, then this is a one-time pad, and it is truly secure in the information theory sense. Nothing other than knowing the original randomly selected key values can decode the ciphertext. But of course, it's hard to come up with terabytes of random numbers at the drop of a hat, and to share them securely with the other party. So symmetric ciphers use pseudo-random generation techniques, to iterate through many pseudo-random keys based on one original key. With PRNGs the "randomness" may have patterns and that is the opening for a break in the crypto.
  - volkercraig 2mo ago
    There is already a mathematically secure algorithm for securing a message: One Time Pad. The problem is that OTP requires that the length of the key and the length of message must be the same, which is inconvenient for large amounts of data. So the solution is to find algos that let you use a smaller key, but the side effect is that by pigeonhole principle, your keyspace is smaller than the message space, so it MUST be insecure. The trick is to make it so that it's only insecure enough that it's infeasible to break.
    - tptacek 2mo ago
      It's inconvenient for any amount of data, because it essentially begs the question; if you can securely transmit N bytes of key pad to a counterparty, just use that mechanism to transmit N bytes of plaintext instead.
      - inigyou 2mo ago
        It has the advantage that the key can be sent before the message is known. Think military battlefield. Your commander goes out to war with a CD, and then he can transmit messages like "we encountered the enemy". It would do no good to transmit "we encountered the enemy" before the war started.
- catlifeonmars 2mo ago
  Perhaps, but it’s still trivially easy to increase the difficulty of factorization problems on classical computers, We need a machine that can run Shor’s algorithm before integer factorization is practical and we’re still a long way out f M that.
OJFord 2mo ago
I think the thing most of us missed in dismissing GPT 2-3 as 'next word in sentence predictors' was that recursively this allows something resembling thinking, 'reasoning'. LLMs are capable not just of calculating the most likely next word from a prompt according to a corpus of training text, but of doing so & feeding back into themselves, the most likely word now based not only on the corpus but on the basic prediction, a second (nth) stage of thought. Yes it's all still token prediction, but it's predicting conversation between let's say not experts but capable speakers with all the information at hand. Undergraduates if you like. And such conversation can yield real results.
- sghiassy 2mo ago
  I’m with ya I’ve even heard arguments that prediction is consciousness. But using a Language-Model to break cryptography is still a stretch for me. From the little I know, cryptography uses information theory to make sure that reversing the equation (aka finding the passowrd) is predictably impossible, given current compute standards for the foreseeable future (disregard quantum computer here though :) they’re not LLMs)
  - PlasmaPower 2mo ago
    The oversight in your thinking is that we have no proofs about how much computation is needed to break cryptography. For all we know, it could be possible to break all modern cryptosystems in under a second on a computer from a decade ago with the right algorithms. This is how cryptography has been broken in the past: not just advances in the amount of compute we can do, but exponential speedups in the algorithms to break them. While I agree with the author of this post that modern cryptosystems are very secure and LLMs are not currently near breaking them, I don't think it's unreasonable to consider that if LLMs continue to get exponentially smarter they may make strides in cryptanalysis that we had never considered and break cryptography in unexpected ways. After all, many past cryptography breaks have come from previously unknown methods of cryptanalysis.
    - sghiassy 2mo ago

dadrian 2mo ago

RSA is asymmetric crypto. This article is about symmetric cryptography. I expect LLMs will advance state of the art in factoring algorithms, considerably.

what 2mo ago
Why?
sghiassy 2mo ago
Thank you I guess I only know asymmetric cryptography. I should learn more about symmetric… Anyone care to boil it down for me :) Edit: Isn’t this just advanced static analysis of any code base?
- fluoridation 2mo ago
  Very, very briefly, most symmetric algorithms are block ciphers, meaning that their input are blocks of a fixed length in bits (plus a key), and their output is another block of the same length. Ideally, a block cipher with its key produces a random permutation of the input space into the output space, thus diluting the information and dramatically increasing (ideally maximizing) the entropy; what that means is that whether the input is just zeroes and ones in ASCII or fully random, after encryption it should be indistinguishable.
  - sghiassy 2mo ago
    Thank you I wish I knew more in this domain. It almost sounds like hashing with a salt
    - fluoridation 2mo ago
      It pretty much is, except it's reversible. At the block level it meets the cascading requirement, and you can set it up to expand the output arbitrarily by padding the input with zeroes (thus also turning it into a PRNG).
- retrac 2mo ago
  A symmetric cipher is: ciphertext = data XOR key. XOR is reversible: plaintext = ciphertext XOR key. If the key is a set of truly random numbers the same size as the ciphertext, then this is a one-time pad, and it is truly secure in the information theory sense. Nothing other than knowing the original randomly selected key values can decode the ciphertext. But of course, it's hard to come up with terabytes of random numbers at the drop of a hat, and to share them securely with the other party. So symmetric ciphers use pseudo-random generation techniques, to iterate through many pseudo-random keys based on one original key. With PRNGs the "randomness" may have patterns and that is the opening for a break in the crypto.
- volkercraig 2mo ago
  There is already a mathematically secure algorithm for securing a message: One Time Pad. The problem is that OTP requires that the length of the key and the length of message must be the same, which is inconvenient for large amounts of data. So the solution is to find algos that let you use a smaller key, but the side effect is that by pigeonhole principle, your keyspace is smaller than the message space, so it MUST be insecure. The trick is to make it so that it's only insecure enough that it's infeasible to break.
  - tptacek 2mo ago
    It's inconvenient for any amount of data, because it essentially begs the question; if you can securely transmit N bytes of key pad to a counterparty, just use that mechanism to transmit N bytes of plaintext instead.
    - inigyou 2mo ago
      It has the advantage that the key can be sent before the message is known. Think military battlefield. Your commander goes out to war with a CD, and then he can transmit messages like "we encountered the enemy". It would do no good to transmit "we encountered the enemy" before the war started.
catlifeonmars 2mo ago
Perhaps, but it’s still trivially easy to increase the difficulty of factorization problems on classical computers, We need a machine that can run Shor’s algorithm before integer factorization is practical and we’re still a long way out f M that.

OJFord 2mo ago

I think the thing most of us missed in dismissing GPT 2-3 as 'next word in sentence predictors' was that recursively this allows something resembling thinking, 'reasoning'. LLMs are capable not just of calculating the most likely next word from a prompt according to a corpus of training text, but of doing so & feeding back into themselves, the most likely word now based not only on the corpus but on the basic prediction, a second (nth) stage of thought. Yes it's all still token prediction, but it's predicting conversation between let's say not experts but capable speakers with all the information at hand. Undergraduates if you like. And such conversation can yield real results.

sghiassy 2mo ago
I’m with ya I’ve even heard arguments that prediction is consciousness. But using a Language-Model to break cryptography is still a stretch for me. From the little I know, cryptography uses information theory to make sure that reversing the equation (aka finding the passowrd) is predictably impossible, given current compute standards for the foreseeable future (disregard quantum computer here though :) they’re not LLMs)
- PlasmaPower 2mo ago
  The oversight in your thinking is that we have no proofs about how much computation is needed to break cryptography. For all we know, it could be possible to break all modern cryptosystems in under a second on a computer from a decade ago with the right algorithms. This is how cryptography has been broken in the past: not just advances in the amount of compute we can do, but exponential speedups in the algorithms to break them. While I agree with the author of this post that modern cryptosystems are very secure and LLMs are not currently near breaking them, I don't think it's unreasonable to consider that if LLMs continue to get exponentially smarter they may make strides in cryptanalysis that we had never considered and break cryptography in unexpected ways. After all, many past cryptography breaks have come from previously unknown methods of cryptanalysis.
  - sghiassy 2mo ago