I'm brainstorming some different ways of making deterministic encryption more secure. I want to use deterministic encryption to preserve searchability over the keywords in a document set. However, I know that frequency analysis is always a concern when preserving searchability in this way.

The strategy I came up with basically still does deterministic encryption (with SIV mode), except instead of just one IV I use ten different ones.* When I encrypt a keyword I choose a random number modulo ten and use that to index into the array of IVs. I then append the index to the ciphertext so it can be decrypted.

To search, you just encrypt the keyword with all ten possible IVs and make a big OR query with all ten ciphertexts.

I don't know a lot about frequency analysis, so I'm not sure how much (if any) additional security this provides compared to regular deterministic encryption. Anyone have any ideas?

My intuition is that for small document sets with relatively few keywords this does provide nontrivial protection against frequency analysis. But I also think the security might not scale to very large data sets.

*In practice the 'IV' here will be additional input to the first step of SIV.

  • 2
    $\begingroup$ When you’re asking two very related questions that handle the same stuff, you might want to inter-link them: How feasible is word-level frequency analysis over English (or any language)? $\endgroup$
    – cHiMp
    Aug 6 '14 at 16:05
  • $\begingroup$ Apologies for forgetting to link the two together, but I do not think an answer to the other question constitutes an answer to this one. $\endgroup$
    – pg1989
    Aug 6 '14 at 17:52
  • $\begingroup$ Also - can the downvoter explain? I think this is a reasonably well-articulated question that is not too open-ended. $\endgroup$
    – pg1989
    Aug 6 '14 at 17:59
  • 1
    $\begingroup$ As a heuristic, sure, it will be better than doing nothing. But it would still be really easy to give up some vital information. Few keywords does not seem to make the situation better (to me), but actually worse. Imagine that you have two records with a very sensitive keyword, and that keyword alone. The chance that they will use the same IV, revealing the very sensitive correlation, is 1 in 10. That is astoundingly high for cryptographic applications. Your security only scales linearly with the number of IVs, which in general is very bad. $\endgroup$ Aug 6 '14 at 20:23

Such a scheme would have two effects against an attacker trying to analyze the frequency of words and word combinations:

  1. They would need more samples to differentiate between two tokens at the same level of confidence.
  2. For two different tokens with similar frequency they would no longer know that the words differ.

The first means you are making the problem like that of breaking a smaller data set. Larger collections of ciphertext are still breakable. You could correct for this by making the number of different IVs depend on the total plaintext size to be encrypted, but then you make searches even slower.

The second may even be more of a problem for an attacker. The less likely options can occur at almost the same frequency – e.g. in letters there is a significant difference between the frequency of 'e' and 't', but 'j' and 'x' are almost equally uncommon. That means even if you can deduce one token from context, you've only solved e.g. one twentieth part of the problem.

Are these insurmountable problems? No. The fix may patch some leaks, but the encryption remains much less secure than non-deterministic, semantically secure encryption.

Trying to extend your tweak, it might be better to use a non-uniform distribution for the different IVs. For example, illustrating only two IVs with letters, if the probability was $\frac{1}{3}$ for one and $\frac{2}{3}$ for the other, the frequency of 'e' with the first IV would become about equal to that of 'n' with the other.

Again, I emphasize that you should only encrypt information like this if you are OK with an attacker learning nontrivial facts about the plaintext.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.