# How to backup a secret encrypted by multi parties without revealing the secret?

I'm searching for a way to backup a secret that only the end user knows the information with 2 trusted hosts.

First basic version : Alice encrypt secret using Server A public key Alice encrypt encrypted secret using Server B public key. Alice store this double encrypted secret somewhere safe

To restore : Alice ask server B to decrypt double encrypted secret Alice ask server A to decrypt result Alice get secret ... but server A also !

It could work if : to restore : Alice ask server B to decrypt double encrypted secret Alice encrypt result using a magical encryption mechanism (?) Alice ask server A to decrypt this information (homomorphic ??) Alice receive result and decrypt using a magical decryption mechanism (?) Alice get secret ... and server A got just an encrypted information !

Is an encryption mechanism like this exists ?

Is there an alternative approach to my goal ?

Thanks

• If Alice can encrypt and decrypt then the mechanism doesn't make that much sense to me... If she cannot then the two servers may collude which means there is nothing protecting the secret. – Maarten Bodewes Mar 30 '20 at 22:25
• It's not immediately clear to me what's the end goal in mind. If Alice is able to 'store this double encrypted secret somewhere safe', why couldn't she just store the secret there (and not bother the servers)? – poncho Mar 30 '20 at 22:49
• In fact alice don't have keys to crypt/encrypt for a long time. When I say somewhere safe, safe in a sense that the information won't disappear, but you never known someone can still it. – Alexandre Cognard Mar 31 '20 at 8:23
• So, you want something so that if an adversary can learn Alice's stored value and one of the server's stored value, they still can't recover the secret? BTW: if you answer a comment to a specific person on this site, you should put in @person in your answer (for me, that'd be @poncho); if you do that, that person would be notified that you gave an answer (otherwise, they wouldn't see your reply unless they just happened to look at the question again). – poncho Mar 31 '20 at 9:18
• @poncho it's exactly that. No server it self can recover the secret. and an attacker need to have access to both server to decrypt secret – Alexandre Cognard Mar 31 '20 at 10:28

Is an encryption mechanism like this exists ?

Yes, blinded decryption techniques exist. There are techniques where party A has a key, party B has a ciphertext, and party A decrypts the ciphertext for party B, and A does not learn anything about the plaintext.

One way to do this is with RSA encryption; the normal RSA decryption algorithm (ignoring the depad operation, which is not important here) is to compute $$C^d \bmod N$$, where $$C$$ is the ciphertext, $$N$$ is the modulus and $$d$$ is A's private exponent.

To do a blinded decryption:

• B selects a random value $$R$$, and computes $$C' = R^e C \bmod N$$ (where $$e$$ is A's public exponent); we assume B knows A's public key
• B passes the value $$C'$$ to A, which computes $$P' = C'^d \bmod N = R C^d \bmod N$$.
• A then passes the value $$P'$$ back to B, which computes $$P' R^{-1} \bmod N = R R^{-1} C^d \bmod N = C^d \bmod N$$ (where $$R^{-1}$$ is the multiplicative inverse of $$R$$; computable by the Extended Euclidean algorithm).

B has then learned the decryption of the ciphertext. And, since $$R$$ is a random value, so is $$C'$$ (and so $$A$$ learns nothing about the actual ciphertext or plaintext)

On the other hand, these blinded decryption techniques are probably not the best answer to the problem you're trying to solve - see my other answer about Secret Sharing.

• In fact, it's seems that it's pretty relevant. I need to re-read it carefully. is there any example/libraries that already implement this kind of feature end-to-end, or it's more combining concept/techno together. – Alexandre Cognard Mar 31 '20 at 13:36
• @AlexandreCognard: well, Blinded Decryption is neither new (circa 40 years old) or that obscure, and so I wouldn't be that surprised if a standard library implemented it. I haven't heard specifically that someone had; however that certainly doesn't mean that there's not someone out there. – poncho Mar 31 '20 at 18:06

If the goal is to store the secret on two servers and Alice so that, if Alice had access to both servers, you can recover the secret, but neither server by itself could (even if you could recover Alice's stored value).

If so, this problem is essentially secret sharing. In this case, it can be done fairly easily:

• Alice generates two random strings $$P, Q$$ as long as the secret $$S$$

• Alice gives the value $$P$$ to server 1

• Alice gives the value $$Q$$ to server 2

• Alice stores the value $$P \oplus Q \oplus S$$ (that is, the strings $$P$$, $$Q$$ and $$S$$ exclusive-or'ed together) in her storage

It should be obvious that neither server (even with Alice's stored value) can recover the secret $$S$$; however if Alice can recover the secret if she has access to both.

And, secret sharing can do more than that (using somewhat more sophisticated mechanisms); Alice can share her secret among 5 servers, so that if she has access to any 3 (perhaps two of them crashed), then she could still recover the secret (but all the server's without Alice's stored value could).

• Yes I see this with Shamir's threshold secret sharing scheme. But I don't think that it's what I need – Alexandre Cognard Mar 31 '20 at 13:34