1
$\begingroup$

Is there such a encryption and decryption mechanism: Given an encryption C = E(K1, M), where K1 is the encryption key and M is plain text, it have to apply decryption with two keys K2 and K3 sequentially to recover M, that is D(K3, D(K2, C)) = M. Given a K1, it is ideal to generate unlimited number of pairs K2 and K3 to ensure distributed trust. The encryption and decryption shall not be too slow for larger amounts of data, thus symmetric cipher is preferred.

Alternatively, is there a way to generate three random number sequences R1(K1), R2(K2), R3(K3) from three keys/seeds K1, K2, K3 such that R1(K1) = R2(K2) XOR R3 (K3)? If so, the above problem can be solved too.

I am aware of Threshold ElGamal or other public key cryptography for multi-party cryptography, but they are too slow, comparing to symmetric cyber such as RC4.


Let me describe the story in another way: Alice uploads her data to a node Bob, later Carol inquires Bob and downloads Alice’s data. Several design considerations:

  1. Alice’s data shall be encrypted while uploading to Bob or being retrieved by Carol;
  2. Either Carol or Bob shall never be able to decrypt Alice’s data alone;
  3. The data may be very large, thus fast encryption and decryption are needed;
  4. Alice may not be always online;
  5. It is acceptable to assume Bob and Carol will not collude, but it would be better if an audit mechanism (such as Blockchain) can be designed to make sure Bob and Carol will not cooperate without Alice's authorization.
$\endgroup$
4
  • 3
    $\begingroup$ Do you require asymmetric encryption, that is K1 public? Can we assume a trusted authority for the making and distribution of K1/K2/K3? Is there any reason why the requirement "encryption and decryption shall not be too slow for larger amounts of data" could not be solved the usual way: by using a random message-unique key to encipher the bulk of the data using a standard fast (authenticated) cipher like AES-GCM; and the multiple-keys thing with K1/K2/K3 (asymmetric or not) protecting the message-unique key? $\endgroup$
    – fgrieu
    Sep 9 at 2:58
  • $\begingroup$ Here K1, K2 and K3 are all secrets. Basically the user 1 encrypt data to E(K1, M), then the decryption shall be done by two parties sequentially D(K3, D(K2, C)) = M. We do not want user 2 see the plain text, and doo not want user 3 to know K1. Here we assume user 2 and 3 do not collude. For public key crypto, my understanding is that it is too slow for large amount of data, right? If it is wrong, we can consider public crypto. $\endgroup$
    – William
    Sep 10 at 13:01
  • $\begingroup$ "For public key crypto, my understanding is that it is too slow for large amount of data, right?". It is generally possible to use a hybrid cryptosystem even when threshold encryption needs to be utilized, that's what fgrieu hinted at (just injecting some terms here :) ) $\endgroup$
    – Maarten Bodewes
    Sep 15 at 8:11
  • $\begingroup$ have you got the complete answer to this question? the one you have posted $\endgroup$ Sep 22 at 5:06
1
$\begingroup$

Alternatively, is there a way to generate three random number sequences R1, R2, R3 from three keys K1, K2, K3 such that R1 XOR R2 XOR R3 = 0?

That part's easy; we can just define:

$$R1 = \text{SHAKE}(K1) \oplus \text{SHAKE}(K2)$$ $$R2 = \text{SHAKE}(K3) \oplus \text{SHAKE}(K1)$$ $$R3 = \text{SHAKE}(K2) \oplus \text{SHAKE}(K3)$$

(where $\text{SHAKE}$ can be, for example, the extensible output function; that is, a function that converts a preimage into an arbitrary length bitstring).

Individually (and pairwise), $R1, R2, R3$ all look random (assuming the keys can't be guessed), however they mutually xor to 0 as you requested.

$\endgroup$
1
  • $\begingroup$ Nice, but user 1 wants to keep K1 secret and not give to user 2 or 3. $\endgroup$
    – William
    Sep 10 at 13:40
0
$\begingroup$

Proposition aimed at 1/2/3/4 of the last section of the question: chained hybrid encryption.

We'll use

  • A fast symmetric authenticated encryption scheme, such as AES-GCM or ChaCha20-Poly1305 with 256-bit secret key, encryption with key $K$ noted $C=E_K(M)$ and decryption $M=D_K(C)$.
  • An asymmetric encryption scheme capable of encrypting 256-bit messages, with encryption noted $C=\mathcal E_P(M)$ and decryption $M=\mathcal D_S(C)$, where $(P,S)$ is a (public, private/secret) key pair. RSAES-OAEP or ECIES will do.

We assume Bob and Carol have generated key pairs $(P_B,S_B)$ and $(P_C,S_C)$, and transmitted public keys $P_B$ and $P_C$ to Alice in a manner insuring integrity and proof of origin (perhaps, by way of digital certificates).

To encrypt towards Carol by proxy of Bob, Alice

  • draws two random 256-bit keys $K_B$ and $K_C$
  • computes $C_B=\mathcal E_{P_B}(K_B)$
  • computes $C_C=\mathcal E_{P_C}(K_C)$
  • computes $C_0=E_{K_B}(C_C)$
  • computes $C_1=E_{K_C}(M)$
  • sends to Bob the message $C=C_B\mathbin\|C_0\mathbin\|C_1$.

Bob receives and stores $C$. When Carol requests the encrypted message, Bob

  • extracts $C_B$, $C_0$ and $C_1$ from $C$
  • computes $K_B=\mathcal D_{S_B}(C_B)$
  • computes $C_C=D_{K_B}(C_0)$
  • forms and sends to Carol $C'=C_C\mathbin\|C_1$.

Carol gets $C'$ and

  • extracts $C_C$ and $C_1$ from $C'$
  • computes $K_C=\mathcal D_{S_C}(C_C)$
  • computes $M=D_{K_C}(C_1)$

Whenever a decryption fails, Bob or Carol abort.

Notice that the bulk message $M$ is encrypted only once, meeting the performance requirement.

We can replace the asymmetric encryption scheme with a symmetric one, $(P_B,S_B)$ with the question's $K_2$ and $(P_C,S_C)$ with the question's $K_3$ (and then as an aside the system can be simplified to get rid of $K_B$). But by going symmetric we loose the benefit of asymmetric cryptography: that Alice needs not keep anything secret, and can't use such secret to try decipher other communication sent to Bob or Carol.

$\endgroup$
2
  • $\begingroup$ fgrieu can you please explain how to get this part of the question. R1(K1) = R2(K2) XOR R3 (K3). this is important to answer. $\endgroup$ Sep 23 at 14:18
  • $\begingroup$ @James Smith: the technique in my answer does not generate random number sequences (or does so in a manner that's built into the encryption schemes used), thus the equation R1(K1) = R2(K2) XOR R3(K3) does not apply to the answer (and is only an option in the question anyway). My $(P_B,P_C)$ is sort of the question's K1, $S_B$ sort of K2, $S_C$ sort of K3. I'm not saying there's a perfect match, only that I think I solve the functional need in 1/2/3/4. $\endgroup$
    – fgrieu
    Sep 23 at 15:10

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.