Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

My question is based on the following situation:

Bob and Alice work for a company that expects them to exchange data encrypted. They could do so using regular public-key cryptography, but Joe (their boss) wants to be part of the procedure to ensure nothing is encrypted or decrypted without his knowledge. Therefore, Joe wants to use his own key as an (let's just call it) "control-key" like this:

  • When Alice wants to send Bob an encrypted message, she has to use Bob's public key and Joe’s key to encrypt message to Bob. On the other side, Bob can not decrypt the message using his private key alone… he also needs Joe’s key too to do that.
  • Same the other way around: when Bob wants to send Alice an encrypted message, he has to use Alice's public key and Joe’s key to encrypt message to Alice. On the other side, Alice can not decrypt the message using her private key alone… she also needs Joe’s key too to do that.
  • Joe himself doesn't care if he can encrypt or decrypt anything using his key alone. He simply wants his key to be part of the procedure (read: cryptographic calculations) whenever Bob or Alice want to exchange data using their public and private keys, so that - without Joe's key ontop of it - encryption and decryption will merely produce garbage.

I am aware that I could try to create a crypto-strategy that might work around some problems to achieve something like this. One way would be splitting the problem by "combining cryptos",using a simple crypto for Joe's key to pre-encrypt and post-decrypt the data AND a public-key crypto for Alice and Bob. But that somehow feels like "rolling my own crypto" and that's the last thing I would like to end up with, so…

Does any public key crypto support and/or allow a 3rd party "control-key" like Joe's?

EDIT

  • While it initially seemed to be a hint towards a potential solution, I don't think "Shamir's Secret Sharing Scheme" or the newer DFT-based (Discrete Fourier Transform) "Threshold Secret Sharing Schemes" will be of any help here after diving into related papers from 1979 to today. To be more exact, I have some security considerations related to schemes based on Shamir's Scheme after reading papers like "On Cheating Immune Secret Sharing" (http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/download/189/582). Sure, I could work around pitfalls of original weaknesses and - when done - combine it with something like AES, but that would pretty much be "rolling my own crypto-remix". Also, I don't want Alice or Bob to know or to influence each-others keys (or - in Shamir's case - "secrets"). That's why I asked for options based on public-key crypto.

EDIT 2

As some comments show my question isn't quickly understood, let me try to explain the model a bit different: think of it as your average public-key crypto... with the exception that not 2 parties, but 3 parties are involved with their public/private key-set.

Theoretically, what I'm looking for would go like this:

  • Alice sends Bob some Crypto Data. To encrypt that data, Alise uses both Bob’s public key and Joe’s public key. As a result, the Crypto-Data can only be decrypted using both Bob’s and Joe’s private key, as the encryption procedure used Alice's and Joe's public keys.
  • Alice receives some Crypto Data from Bob. To decrypt that data, Alice uses her own private key and she needs Joe to enter/provide his private key “on location”. The Crypto-Data can only be decrypted using both Alice’s and Joe’s private keys, as the encryption procedure used Alice's and Joe's public keys.

As for parts of the comments asking for the infosec part of the model (like safeguarding against the use of subliminal channels etc.)… I regarded that to be a bit out of scope of crypto.SE and I want to prevent the question to become too broad. Therefore, I am assuming (for simplicity's sake) that Joe can make sure that he controls Bob, Alice, or both during either the encryption and/or decryption procedure and is able to make sure his key is used together with another one (either Bob's or Alice's, depending on which side needs it for encryption and/or decryption). I see no need to make things more complicated as I can always start to worry about infosec attack vectors and individual implementation issues arising out of individual circumstances at a later time. Currently, I need to know if such a crypto exists in the first place!

share|improve this question
1  
Probably Shamir's threshold sharing? –  rath Jul 23 '13 at 5:57
    
@rath Interesting pointer, thanks. Gotta dive into that but it surely looks promising at first sight. –  e-sushi Jul 23 '13 at 6:02
1  
I don't get your model. What is going to prevent Alice and Bob from using a subliminal channel to bypass Joe's control ? [Or just from using an independent mean of communication]. Could you explain more precisely what Joe really wants to control and what would be an attack of his control from Alice and Bob (assuming they don't want to collaborate) ? –  minar Jul 23 '13 at 9:47
add comment

1 Answer 1

up vote 3 down vote accepted

A threshold cryptosystem is what you are looking for. Note that this is different from threshold secret sharing. In a threshold cryptosystem, there is one public key and $n$ private keys. To encrypt a message, the sender simply uses the public key as usual. To decrypt, the $n$ parties compute a partial decryption which they send to any party authorized to learn the plaintext. The authorized parties combine the partial decryptions to get the plaintext.

Note the big difference with Shamir. The secret decryption key is never actually reconstructed.

So in your case, there is a public key for Alice and a public key for Bob. There are two private keys for Alice's public key. One which she has, one which Joe has. Same for Bob's public key. For Bob to send a message to Alice, he uses Alice's public key to encrypt the message and sends it to Alice and Joe. Joe computes a partial decryption and sends it to Alice. Alice uses this along with her private key to decrypt.

For more, see UTD Paillier Threshold Encyption. RSA and ElGamal variants also exist though I don't know of any implementations.

Other options Another option might be proxy reencryption, but I am not very familiar with it.

A third option you have is multiparty computation. Using MPC, Alice could encrypt a message to Bob using regular AES. She then secret shares the key with Bob and Joe. Bob and Joe run a 2-party secure MPC protocol using their shares of the decryption key and the ciphertext on the AES decryption function. The output is the plaintext. If going with a garbled circuit approach, have Joe generate the GC and Bob run it. Then only Bob gets the output. This framework can probably do what you are looking for (though you might need to modify it slightly since the key is secret shared).

share|improve this answer
    
The secret decryption key would not be reconstructed with Shamir either. $\:$ –  Ricky Demer Jul 23 '13 at 11:52
    
@RickyDemer, all the use cases I'm familiar with for Shamir is you share a secret with $n$ parties, then you reconstruct the secret later. What use case are you talking about? –  mikeazo Jul 23 '13 at 11:58
    
I'm talking about encrypting each share, so that the "partial decryptions" will be the shares of the plaintext. –  Ricky Demer Jul 23 '13 at 12:02
    
@RickyDemer, I see. –  mikeazo Jul 23 '13 at 12:03
    
Thanks for those links — more to read for me. Hmmm… @Rath already pointed into the "threshold crypto" direction. Since "two make a crowd", something tells me you guys may be correct after all. Gonna fetch some lunch, dive into the provided links, read some related papers, and then I'll be back with an up-vote as soon as SE allows me to vote again (11h as I'm writing this). Until then: let me already say "thanks" for your answer (and edit). Much appreciated! –  e-sushi Jul 23 '13 at 12:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.