Leak-proof protocol: is such a thing possible?

Question

Is it possible to design a protocol that by itself guarantees that a malicious implementation cannot leak secret data without breaking the protocol?

Setting:

• Alice and Bob have a pre-shared secret key K. Using this key, Alice encrypts a bunch of plaintexts and sends them to Bob as a collection of files. The plaintexts are short-ish texts in a natural language.
• Each plaintext is encrypted independently of others, and must be decryptable independently. Some sort of authenticated encryption is used.
• Eve receives a copy of the collection. This is the only data she gets (i.e. no timing or other side channels). She does not communicate with Alice (but can have a previous arrangement with her, e.g. pre-share some secret keys). Alice cannot communicate with Eve directly, or otherwise send out any data except as defined by this protocol.
• We want to ensure that Alice cannot manipulate the encryption, without consequences detectable by Bob, in such a way that Eve can obtain information about the secret key. We assume that transmission is 100% reliable, so if Bob can't decrypt some of the files, he will conclude that Alice is a bad actor.
• Also, obviously, we don't want Eve to obtain the plaintexts. It's tolerable if Eve can detect multiple copies of the same plaintext.

---

It seems that any kind of randomness in the protocol has to be excluded.

For example, if we use an encryption scheme with random IV which is prepended to the ciphertext, Alice can just encrypt the secret key K using another secret key known to Eve, Ke, and apply it instead of IV (IV := E(Ke, K)). Instant leak!

If our protocol adds randomness to the plaintext itself (before encryption), Alice still can manipulate the encryption result by choosing the random value. In the worst case she will have to use brute force, changing the random bits until specific bits of the ciphertext assume the values she wants. On average, she will need about 2ⁿ iterations to leak n bits of data. If, say, 1000 encryptions is a small enough number to be unnoticeable on any modern equipment (even "weak" such as a smartphone), then Alice would be able to leak ~10 bits of data per encrypted file.

The next thought I tried is to use deterministic encryption with Synthetic IV based on plaintext (similar to SIV-CTR construct). Besides obvious drawbacks caused by the low entropy of the natural-language plaintexts, this scheme still does not preclude Alice from leaking if she can manipulate plaintexts in a way not obvious to Bob. For example, she can try adding spaces at the ends of text lines, or insert some non-spacing Unicode chars, until she gets desired bit pattern in the ciphertext. (I don't know how to estimate the effort she'll need to leak n bits per ciphertext. Is it still O(2ⁿ), as in previous case?)

The last option seems better than others, because the manipulations are detectable by Bob, at least potentially. But this detection happens outside the domain of the protocol, and is not reliable. Are there other possibilities?

Answer 1

It doesn't work without further restrictions.

For simplification, let's assume Alice encrypts a bunch of files but doesn't have to send all of them to Bob. She can still decide to re-order the files or leave out some.

Then she can encode the secret shared key between Alice and Bob in the least significant bits of the ciphertexts without changing the files. She is only rearranging them so that Eve can extract the key. But if Bob checks the integrity of each message, it holds.

If more files are transmitted than the keylength, this works. Otherwise, more than one bit has to be encoded in less messages. And in order to get enough decryptable ciphertexts more files might have to be encrypted.

Answer 2

Sort-of, like the way you describe. $\:$ (It's still O(2ⁿ), as in previous case.)

For encryption, one could have scrypt be involved, to reduce the leakage rate.
For signatures, one could use a scheme in which each message has at most one valid signature,
so that anyone who knows the public key and sees the output can potentially detect manipulation.

Answer 3

What you want is a protocol where Alice sends a message to Bob without being able to control any ciphertext bits. This would be possible if either

1. The message and encryption are completely deterministic and give Alice no freedom to choose between two ciphertexts, or
2. Alice is unable to predict the ciphertext without sending a message.

The first could be possible if the message space is small enough (e.g. Alice only sends True or False and cannot choose which) and the encryption deterministic (e.g. block cipher in CTR mode with messages using consecutive IVs).

The second would probably require a trusted third party who does the actual encryption and sending. Further, you would have to assume communications between Alice and the TTP are not leaked.

---

For a real-time protocol, with an assumption on Alice's computing power you could be able to lock Alice into only being able to calculate one encryption in time. It would be like a reverse time capsule. All the caveats from Time Capsule cryptography would apply, a well as a few others like that parallelism would be trivial.

An example of such a time-locked protocol could be:

1. Choose a key-derivation function $H_n(K, S)$ that takes $n$ seconds for Alice to compute using all her resources. Have Alice and Bob share two secret keys $K_1$ and $K_2$.
2. Bob sends a random number $R$ to Alice and starts a timer.
3. Alice computes $H_n(K_1, R||M)$ and uses that as the IV for AES encrypting the message $M$ with $K_2$ and sends $IV||E(K_2, IV, M)$ to Bob.
4. Bob verifies that he has received the reply within $t < 2n$ and that the IV matches $H_n(K_1, R||M)$.

Since Alice can calculate neither the IV nor the ciphertext before receiving the random number $R$, she only has time to calculate them once before the time limit, meaning she cannot hide any information in them even by choosing a different message.

This assumes Alice always co-operates and follows the protocol. She can of course hide information if she sends an invalid message or fails to reply to some messages.