Does any encryption/decryption algorithm supports linear decomposition?

ZKM

8/25/24, 6:29 AM

I am not sure whether "linear decomposition" is appropriate to summary my question: We know that the traditional symmetric encryption/decryption algorithm (like AES, TDES) can be written as:

C = FUN_enc(key, P) P = FUN_dec(key, C)

Where FUN_enc is the encryption function/algorithm, FUN_dec is the decryption function, C is ciphertext, P is plaintext. For AES, FUN_enc and FUN_dec are AES encrypt and decrypt algorithms. Here we only consider the basic ECB mode.

OK, now comes my question: Does one encryption/decryption algorithm exists, that satisfy:

C1 = FUN_enc(key1, P) C2 = FUN_enc(key2, C1) and: C2 = FUN_enc(key3, P)

That is, one encryption can be splited into two individual encryption steps, and also give key1, key2, some algorithm can calculate key3.

One algorithm that can be decomposed to two:

FUN_enc(key, P) = FUN_enc(ke2, FUN_enc(key1, P)) and the algorithm FUN_enc SHALL also as secure as AES.

https://stackoverflow.com/questions/76967037/does-any-encryption-decryption-algorithm-supports-linear-decomposition

1 + 3

aes

block-cipher

symmetric

fgrieu

8/26/24, 2:27 PM

The question is ambiguous. Is it required that for any key1 and key2 we can find key3? That for any key3 we can find key1 and key2? That there is a decryption function? That keys are constant-size? What security properties are desired? The Pohlig-Hellman exponentiation cipher allows what you ask, except it has the property $E_k(XY\bmod P)=E_k(X)E_k(Y)\bmod P$ which often is undesirable. Independently: with keys any size multiple of 256 bit, it's easy to make something AES-256 based such that for any key1 and key2 we can find key3, merely as the concatenation of key1 and key2.

ZKM

8/28/24, 4:05 AM

@fgrieu Oh, sorry. This question has these restrictions: 1. key3 is fixed and can't be changed. so it requires for fixed key3, we can find key1 and key2. 2. key1 and key2 are variables, and have constant-size. I have checked Pohlig-Hellman exponentiation cipher, it is based on prime number exponent, like RSA, but here I don't want to introduce big number operations, I just want some AES like symetric algorithms. And I have read kodlu's anser about does DES form a group, seems that there is no such algorithm.

ZKM

8/28/24, 4:11 AM

This question comes from this application usage: There is a communication chan A --> B --> C, and A has the plaintext message M and encrypt it to M_enc, then send it to B. B encrypt the M_enc with another key and generate M_enc_enc, then send it to C. C has the fixed key3 and can decrypt M_enc_enc to M.

Score:1

Crypto

kodlu

8/25/24, 6:45 AM

This would be a weakness and has been investigated under the name does DES form a group?

See question and answer here. A secure cipher should not have this property.

+ 2

ZKM

8/28/24, 4:12 AM

Yes, seems you are right.

kodlu

8/28/24, 4:24 AM

Okay. You can accept the answer if it's satisfactory

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Does any encryption/decryption algorithm supports linear decomposition?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.