1
$\begingroup$

Are there any block-cipher modes (or symmetric encryption schemes in general) that are fully-deterministic, meaning same inputs lead to the same outputs (like for all modes with constant IV) and satisfy any notion of security?

ECB would for example accomplish the first but has no security properties at all) And more specifically: are there any schemes as described above that produce indistinguishable blocks in the presence of an eavesdropper? (This is weaker than CPA security)

I know that there exist papers for the public key setting but I could not find anything for the symmetric setting. Also, I don't need anything like 'searchable encryption', I need specifically the described properties above.

I have done research on this topic but could not find anything useful.

|improve this question
$\endgroup$
  • $\begingroup$ With deterministic encryption an attacker will always be able to tell whether two messages are identical. However there are schemes that limit the information leaked to that statement, are you looking for such schemes? $\endgroup$ – SEJPM♦ Mar 31 '18 at 10:04
  • $\begingroup$ Yes, I am looking for a scheme that produces equal cipher texts for equal inputs but indistinguishable cipher texts if just one bit is different. $\endgroup$ – dave4422 Mar 31 '18 at 10:19
2
$\begingroup$

Yes, the most common / secure deterministic encryption is SIV mode, which stands for synthetical IV mode. Here the IV that is used to randomize each message is replaced by an authentication tag (MAC) over the plaintext message. Of course, this means that identical messages will be distinguishable. But if even a single bit of the messages differ then the entire ciphertext will be indistinguishable as the MAC/IV will of course be different.

SIV or GCM-SIV mode are authenticated or AEAD ciphers. So it is also possible to authenticate additional data together with the data to be encrypted. As most authenticated modes they use counter mode (CTR mode) to provide the confidentiality of the message.

As usual, if the plaintext message differs in size then the ciphertext will differ in size as well.

Deterministic, asymmetric encryption exists as well. Here the random value for indeterministic encryption is usually simply replaced by a secure hash over the message.

Closely related are modes of operation such as Bi-IGE (bi-directional infinite garble extension). If any of the bits of the ciphertext is changed then IGE will make sure that all plaintext bits after that will become affected. Bi-IGE will do the same but in both directions - at the cost of using additional operations of the block cipher, of course.

|improve this answer
$\endgroup$
  • $\begingroup$ Is there a published notion of security for what you described as "Of course, this means that identical messages will be distinguishable. But if even a single bit of the messages differ then the entire ciphertext will be indistinguishable as the MAC/IV will of course be different." ? $\endgroup$ – dave4422 Apr 1 '18 at 9:53
  • $\begingroup$ @dave4422 I think this is usually called "nonce misuse resistent authenticated encryption". $\endgroup$ – SEJPM♦ Apr 5 '18 at 8:05

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.