1
$\begingroup$

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?

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ You beat me by 11 seconds... I'm thinking of putting comment like "working on it" before answering something! $\endgroup$
    – fgrieu
    May 20 at 15:34
  • 1
    $\begingroup$ To get the basic theory, I would request you to check 'Homomorphism' in Groups, a topic in Abstract Algebra. the required condition for homomorphism between two Groups is function f is a homomorphic function ${f:G \mapsto G' }$ such that ${ f(xy)= f(x) f(y)}$, which means you can either operate on x and y first and then apply function or apply function to each element first and then do the operation on result, both should give you same result, and this beautiful concept is used in homomorphic encryption. $\endgroup$
    – SSA
    May 21 at 8:19
11
$\begingroup$

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;

$\endgroup$
3
  • 1
    $\begingroup$ the linked post ("OTP can have perfect secrecy...") doesn't seem to address modifying the message on the fly, what am I missing? $\endgroup$
    – ilkkachu
    Dec 17 '20 at 17:57
  • $\begingroup$ @ilkkachu the link for modification is on the bullet list. It is for the perfect secrecy. $\endgroup$
    – kelalaka
    Dec 17 '20 at 18:12
  • $\begingroup$ Could the downvoter explain the reason! $\endgroup$
    – kelalaka
    Dec 17 '20 at 20:32
10
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It's homorphic although I suspect you mistyped because it has some relation to the even more complicated term you've introduced me to!! $\endgroup$
    – Modal Nest
    Dec 16 '20 at 22:31
  • 3
    $\begingroup$ @ModalNest actually, you're both wrong—the accepted term is homomorphic: three 'o's / no 'e's. $\endgroup$ Dec 17 '20 at 0:21
  • $\begingroup$ If the encryption scheme is not standard one (like GCM, CCM, etc..), and also proven that it is not CCA secure, then I think we can modify the ciphertext. But in standard usage it is not possible. As mentioned by SAI Peregrinus a homomorphic function inherently support this. $\endgroup$
    – SSA
    Dec 17 '20 at 6:32
3
$\begingroup$

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.

$\endgroup$

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.