Are there any cryptographic algorithms, which lets the user apply some modifications on the encoded data, without decoding it?

Question

I would like to encode some data with a key, and send it to a third party. They don't know the key to decode it, but I would like to make it possible for them to apply some modifications on it. Then they send i back, I can get decode it, and get the result.

For example let the encoded data is the integer 5. I encode it with a key k and it becomes xxxxxx. The user can apply operations to xxxxxx without knowing k, like +5 and *2. After those operaions, the encoded value becomes yyyyyy. If I decode the value with the key k, it should be 20, as if I applied +5 and *2 on the original data 5.

Are there any cryptographic algorithms like that?

Answer 1

Are there any cryptographic algorithms like that?

Yes, those algorithms are known are "homomorphic encryption algorithms"; they are public key encryption algorithms (that is, they have a public key and the private key; with the public key, you can encrypt data; to decrypt data, you need the private key).

In addition to the normal public key encryption functionality, they have the property that (with the public key) someone can perform some operations on the encrypted data; for example, with the encryptions $E_k(A)$ and $E_k(B)$, they might be able to compute the ciphertext $E_k(A+B)$ (without learning what $A$ and $B$ are).

You can learn more about the various flavors of homomorphic encryption algorithms out there; however to address your specific examples of +5 and *2, the obvious answer would be the Paillier cryptosystem, which is a "somewhat" homomorphic system, with the homomorphic operation being addition (modulo a large number; as long as the intermediate values stay under the modulus, we can ignore that). So, to perform a +5 operation on the encrypted value $E_k(A)$, we would take 5, encrypt it with the public key to form $E_k(5)$, and then homomorphically add it to form $E_k(A+5)$. And, to perform a *2 operation on $E_k(A)$, we would just homomorphically add it to itself, forming $E_k(A+A) = E_k(2 \cdot A)$.

Paillier has its limitations (it can't perform any homomorphic operations that can't be expressed as additions); however if you can live with that, it works quite nicely.

Answer 2

Can I modify encrypted data without accessing it? if there is an example appreciate it

• If access means altering the data without decryption as an attacker then the answer is yes for messages without integrity.

  • Take OTP, execute bit flipping attack, done.

  • Take CTR mode, execute bit flipping attack, done.

  • Take CBC, execute bit flipping attack, done.

  • Similarly, take any stream cipher, modify one bit,

    Let $c_i = m_i \oplus x_i$ where $x_i$ is the $i$th bit form the stream cipher then

    $$c_i \oplus 1 = m_i \oplus x_i \oplus 1 = \bar m_i \oplus x_i$$ where the $\bar m_i$ is the bit complement of the bit $m_i$.

  Take CFB, execute bit flipping attack, done

  • and so on...

  These also called the ciphertext malleable.

  Note that the reason for this kind of attack is that they are at most CPA secure ( well OTP can have perfect secrecy with fixed-length messages ) and that doesn't mean that the modifications are detectable. To mitigate this attack one needs at least integrity. The integrity may not be enough, since the attack in some cases reuses some part of the encryption and send it. Therefore, at least we need a Message Authentication Code (MAC), like HMAC, GMAC, CMAC, etc. With MACs, the attacker need also forge the message to execute such attacks on the encryption.

  Note that the bit flipping is the minimum attack. The attacker can modify more than one bit whenever it fits their aim.

• If access means you want to operate on the encrypted data that the answer is yes for a very long time;

  • Textbook RSA is multiplicative so that you can multiply the ciphertext. Let $(n,e)$ be the public modulus with $d$ is the private exponent. Let the ciphertext $c = m^e \bmod n$ and $c' = 2^e \bmod n$ then $$c \cdot c' = m^e \cdot 2^e = (2m)^e \bmod n.$$

    One should keep track of the overflow that is when the modifications exceed the modulus the value will be rounded.

  • ElGamal can be both additive and multiplicative

  • Paillier encryption is additive where the multiplication of the ciphertext is the addition of the plaintext.

  • Goldwasser–Micali where the multiplication of the ciphertext is the x-or of the plaintext.

  • 2DNF enables 1 multiplication and many additions.

  The above was before Gentry's Seminal work; Fully Homomorphic encryption that enables operation of arbitrary operations on the encrypted data. This was envisioned by On data banks and privacy homomorphisms. by Shamir et. al, immediately after RSA.

  The FHE simply having two homomorphic operations on the data so that arbitrary circuits can be computed;

  $$E(a) \boxplus E(b) =E(a \oplus b)$$ $$E(a) \boxtimes E(b) =E(a \times b)$$

  Note that for the plaintext and ciphertext operations different notation is used since the FHE schemes are not restricted to those. Some notable FHE libraries are;

  • HeLib, THFE, GSW, BGV, LTV, FHEW,....

  • There is a post about how these operations handled; Representing a function as FHE circuit

Answer 3

If (and ONLY if) it was encrypted with a special "homomorphic" encryption scheme, then you can do the operations allowed by that scheme. Those are almost never used in practice currently (they're very slow, and an area of active research). This demo is quite good.

More commonly data is encrypted using an "Authenticated Encryption with Associated Data" (AEAD) system. AEADs will prevent ANY modification of the encrypted data.

There are also less secure (not IND-CCA) schemes that don't authenticate. Weak cryptography like that can have its ciphertext modified.

Answer 4

I encode [a secret $x$] with a key k and it becomes xxxxxx. The user can apply operations to xxxxxx without knowing k, like $+5$ and $\times2$. After those operations, the encoded value becomes yyyyyy. If I decode [yyyyyy] with the key k, it should be [ $(x+5)\times2$ ], as if I applied $+5$ and $\times2$ on the original data [ $x$ ].

The Pailler cryptosystem allows something close:

• You won't encode with the same key k that you use to decode, and will need to give the encoding key (called the public key) to the user; you'll keep the decoding key (called the private key) for you.
• $x$, virtual intermediate result and output can only be integers in a range; but that can be a very large one, e.g. $[-2^{3070},2^{3070}]$.

The operations needed in the above example fit the limits of what a user can do:

• Addition (all operands can be secret w.r.t. the user, or not);
• Multiplication by an integer known to the user. This is handled by modular exponentiation, e.g. to compute an encrypted value for $x\times k$ the user compute $y^k\bmod n^2$ where $y$ is the encrypted value for $x$ and $n$ is part of the public key.

Intermediate values will have relatively large size (like, 768 bytes). The system can be rather slow, especially for key generation, initial encryption of $x$ or other secret input to the user, addition of a constant not used before by the user with that public key (more so if that constant needs to be hidden from observers), multiplication by a large integer (multiplying by $k$ requires close to to $1.5\log_2 k$ modular multiplications), and final decryption.

Since the interval is large, using appropriate public scaling conventions on top of the Pailler cryptosystem, it's often possible to workaround the integer limitation.