Malleable encryption

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?

• I suggest avoiding the term "homomorphic encryption", because depending on the context, this is used for both "fully homomorphic" or "semi-homomorphic". Fully homomorphic encryption surely would be overkill, additive semi-homomorphic encryption solves your task quite nicely (as long as people play along the rules). – tylo Jul 12 '16 at 16:58

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

• For completeness, there are also other additively homomorphic cryptosystems, e.g. Benaloh and Naccache-Stern. They are quite similar to Paillier, but allow only smaller messages, which shouldn't be a problem with 256 bit messages (N should be a RSA modulus of at least 1024 bit). – tylo Jul 13 '16 at 9:58
• what a wonderful place this site happens to be. thank you kindly for your in-depth reponse MickLH, also thanks tylo for suggesting that a whole family of additivly homomorphic cryptosystems do exist. I have already a couple of solutions to the problem in my mind found a relative crypto toolkit as can be seen, now I wonder if there is any ECC based additivly homomorphic cypher so as to optimise the storage requirements. back to google' – vega4 Jul 13 '16 at 13:22
• – vega4 Jul 13 '16 at 13:26
• I'm investigating mainly EC-Elgamal and Paillier. Any main differences in performance sstrength etc? EC would surely occupy less space. and one final question before I dive deep into the subject; would EC-Elgamal allow for Enc(x) + plaintext(y) to result in Enc(x+y) as is the case with Paillier? – vega4 Jul 13 '16 at 13:54
• also,. we have cyphertext C1. Eve knows the value of C1. Bob adds plantext value to C1 resulting in C2. will Eve be able to get to know the added value? by some differiencing etc – vega4 Jul 13 '16 at 14:33

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.

• Im ready to give up some diffusion of this part of the data is not of a critical importance. the one which is is encrypted with a variant of CP-ABE. but I need also to attach part of data which will be glued together with the CP- aBE encrypted part using the value stored in the cp-abe segment and the fist 256bit value visible in my picture. any third party should be able to add something to this part. f om what I've researched that is exactly partially homomorphic cyphers are supposed to do but if I decide to stick with symmetric cypher for performance reason what would you suggest. thank you – vega4 Jul 11 '16 at 19:05
• I am working on a research project heavily related to cryptography.blockchains various stuff.anyway. I am aware of statistical analisis. again, the requrement is such as follows: there is a prefix in the datagram. Eve is aware of that. lets forget statistical analysis. lets just harden her work as much as possible. but again. other third parties should be able to add imformation to what follows. by multiplication, addition etc. lets allow data to be destroyed but then Bob will detect that thanks to the first 256bit value being wrong. any ideas? – vega4 Jul 11 '16 at 19:10
• what is more statistical analysis is sort of not of great importance here as the values added by third parties can also be considered as random:D – vega4 Jul 11 '16 at 19:24
• please note I was asking for a meallable encryption in the first place. here it is considered to be a feature – vega4 Jul 11 '16 at 19:27
• "what is more statistical analysis is sort of not of great importance here as the values added by third parties can also be considered as random:D" - I would be very careful making this assumption: it is virtually never the case that any meaningful data is "random". – Dan_JH_YK_CC Jul 11 '16 at 19:29

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.