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.