Memorization for Good: Encryption with Autoregressive Language Models

We thank the reviewer for their time and effort spent reading and engaging with our work. We’d like to answer your questions as best we can.

You say in page 6: "Other symmetric ciphers like the Data Encryption Standard (National Bureau of Standards, 1977, DES) and the Advanced Encryption Standard (Pub, 1999, AES) do not have this flexibility; the ciphertext is always the same size as the message." How come this is a weakness? Cannot you always artificially increase their ciphertext, if that is needed as a "feature"? Good point; you are correct.

Your security game in page 6 is not clear. What does "encrypt them" in step 2 of your re-framed game is done? which one of m_0 or m_1 is encrypted? Encrypt both $m_0$ and $m_1$ to form a set of examples ${(c_i, m_i)}^t_{i \in \{0, 1\}}$. Then the training set is a set of ciphertexts with binary labels, 0 or 1, indicating which message produced the ciphertext. Since encryption is not deterministic, the ciphertexts will all be different.

We apologize for the typo and will fix it.

in page 7 and 8, you say that "operating on bit sequences" is a factor that limits previous crypto-analysis approaches. But is not it that without loss of generality? As far as I understand, everything can be re-written in zeros and ones. You are again correct. Because existing encryption algorithms operate on bit sequences, existing cryptanalyses also look for bit-level patterns. We could apply them to our ciphertexts, but we think the lack of bit-level operations would make these analyses unlikely to work. We will correct this language in future versions.

We thank the reviewer for their time and effort spent reading and engaging with our work. We’d like to answer your questions as best we can.

Can you provide evidence for why the scheme could be secure? Traditionally, the standard schemes have concrete quantitative assumptions under which one can prove security. We think that we explain the intuition for why SELM is secure in Section 3 (in the paragraph starting “Intuitively…”) and we also provide extensive quantitative experiments in Section 5 (titled Security).

Furthermore, symmetric encryption algorithms are almost never provably secure. AES, DES and other symmetric encryption algorithms are not provably secure.

We thank the reviewer for their time and effort spent reading and engaging with our work. We’d like to answer your questions as best we can.

It seems that the secret key k is used for the generation of projection P_k, but what is the specific generation method of projection from the given k? We use torch.randn, torch.randperm and torch.randint in combination with torch.set_seed to generate the required matrices for a FastFood transform. In a truly secure implementation, you should use cryptographically secure methods of generating random numbers.

What is the size of different subspaces generated from k? The subspace size is the intrinsic dimension $d$, which is a hyperparameter. We discuss the effects of $d$ in Section 4.3

Are projections always orthogonal to each other? No.

If not, is there any possibility of information leaking from subspaces close to each other? We don’t think so, because there’s no way an attacker could know that two subspaces are close to each other.

We thank the reviewer for their time and effort spent reading and engaging with our work. We’d like to answer your questions as best we can.

Can we further improve memorization speed using Prompt engineering strategies? Most likely, yes. We perform some experiments in Appendix B on this and find that the UUID prefix leads to the best memorization speed; we think this is because it “resets” the LM context.

What attack vectors or cryptanalyses are the biggest threats to SELM security? In our experiments, gradient-boosted decision trees do the best on the security game. However, we’re aware that our security experiments are not as rigorous as the decades of attacks on existing algorithms like AES and we expect there to be more attacks that are stronger against SELM.

Can we employ off-the-shelf LLM optimization techniques to reduce the computation burden of the SELM without compromising its security guarantee? Yes! We think that FlashAttention is an example of an LM optimization that was released during this work and would likely lead to improved wall clock memorization speed. This is part of why we’re excited about SELM: we can take advantage of LM optimizations and apply them for free to SELM.

What are the key (potential) backdoors in LLM to undermine the security of SELM? We’re not aware of any backdoors in LLMs that would undermine the security of SELM, but we agree that it’s an interesting area for further work.