Malleable encryption

Question

What I would like to achieve is the following:

Alice sends to Bob the encryption of a datagram that has the following format:

| 256-bit number | SomeLongArrayOfZeroes |

Bob knows the decryption key.

But before the datagram reaches Bob, there are some intermediaries which I would like to be able to add some additional 256-bit numbers. These third parties should not be able to read the first 256-bit number which was included by Alice. Let's also assume that these third parties know which portions of the ciphertext they have to modify in order to not modify data inserted by other parties.

I was researching homomorphic encryption but it looks like an overkill for this purpose. There's no need for two ciphertexts to interact with each other. I just need to be able to add additional data to already encrypted ciphertext which already contains some information without imposing damage to it. Assuming the other parties will follow some rules so as not to damage the prefix. A third party should not be able to decrypt information added by the other third party.

In the end, Bob should be able to decrypt the message using the key provided by Alice.

Any suggestions? I was thinking about some kind of a stream cipher. What are the possible solutions?

Answer 1

Several cryptosystems possess this partially homomorphic property. Notable examples include Benaloh, and Naccache-Stern which generalizes it, as well as Damgård–Jurik which generalizes the Paillier cryptosystem.

A worked example of the latter scheme:

The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$. From this we can see that given two ciphertexts we have: $$E(m_0)\cdot E(m_1) = (g^{m_0}\cdot {r_0}^n) \cdot (g^{m_1}\cdot {r_1}^n) \mod n^2$$ $$E(m_0)\cdot E(m_1) = g^{m_0 + m_1}\cdot {(r_0 \cdot r_1)}^n \mod n^2$$ $$E(m_0)\cdot E(m_1) = E(m_0 + m_1) \mod n^2$$

So we can compute the encryption of the addition of two plaintexts from only the ciphertexts, without revealing them, by simply multiplying the ciphertexts.

Additionally, if we know the value of $m_1$ then we can avoid using the encryption primitive and directly compute as follows: $$E(m_0)\cdot g^{m_1} = (g^{m_0}\cdot {r_0}^n) \cdot g^{m_1} \mod n^2$$ $$E(m_0)\cdot g^{m_1} = g^{m_0 + m_1}\cdot {r_0}^n \mod n^2$$ $$E(m_0)\cdot g^{m_1} = E(m_0 + m_1) \mod n^2$$

Now, by viewing multiplication as repeated addition, we can extend the homomorphic property to multiply by a constant, by implementing repeated ciphertext multiplication using exponentiation: $$E(m_0)^{m_1} = (g^{m_0}\cdot {r_0}^n)^{m_1} \mod n^2$$ $$E(m_0)^{m_1} = g^{m_0 \cdot m_1}\cdot {({r_0}^{m_1})}^n \mod n^2$$ $$E(m_0)^{m_1} = E(m_0 \cdot m_1) \mod n^2$$

EDIT: Thanks tylo for specific examples

Answer 2

Could you describe the key distribution scheme?

If you want symmetric encryption, then your requirement that the intermediaries cannot decrypt anything precludes them all from having the same key, so would it be the case that everyone has a different key, and Bob has all the keys?

Or is asymmetric encryption what you had in mind?

There is a fundamental problem I see with his approach: any good encryption scheme should implement good diffusion (mixing all the information from all parts of the plaintext around so that it's evenly spread-out in the ciphertext) to prevent statistical analysis. In trying to preserve the first n-bits from one encryption to another, I can't think of a way to do to do this without compromising diffusion.

Even of you had some mechanism so that the intermediaries could undo the diffusion before adding their part, this mechanism would by necessity be part of the system, and so [by Kerckhoffs's Principals] you must assume that Eve can do the same, again defeating diffusion and opening your cipher-up to statistical attacks.

So, if it's a practical problem you're trying to solve, rather than trying to invent a new cypher with this property, I would just concatenate individually-encrypted ciphertexts.

Answer 3

TLDR; just encrypt the first 256 bits and leave the rest unencrypted

| 256-bit number | SomeLongArrayOfZeroes |

Is it important that Alice sends exactly encryption of (256 bit + some long array of zeros)? i.e., can Alice just encrypt 256 bits, and just send bunch of 0's as a place holder after the 256 bits of ciphertext? (in this case, 0's are not included in the encryption, thus Bob doesn't need them for decryption)

if no, Encrypt only using first 256 bits, the third parties can append additional data after the first 256 bits in some predefined fixed length.

if yes, you can define it so that the third party can only append to the existing ciphertext with some predefined fixed length.

• Else (if length is an issue)
  1. encrypt only the first 256 bits, and instead of appending 0's, append a hash of the some form of first 256 bits (plaintext or encrypted; this can be decided based on third party's needs)
  2. Third party should use XOR operation to XOR their data with the hash generated from the first step.
     If Bob wants to decrypt, he first decrypts first 256 bits, and then use it to obtain the hash (or hash the encrypted 256 bits), xor with the rest of the appended data to obtain third party's data. This can be repeated for predefined length for each additional third party data.