A Two-Party Combined Cryptographic Scheme and Its Application

In this paper, we extend Haber and Pinkas’ notion of combined (cryptographic) scheme to the twoparty setting, which is shown to be a useful tool in some real-world application which we name the “2-boss problem”. In a two-party combined scheme, a single public key associated with two independent private keys and one escrow decryption key is provided. Any ciphertext encrypted under the public key can be simultaneously decrypted by the three keys. Meanwhile, the two private keys can also be used as signing keys to achieve non-repudiation service. We provide formal security definitions for two-party combined schemes, and present a simple and efficient scheme. Our construction is derived from bilinear pairings, and the security is based on the Bilinear Diffie-Hellman (BDH) assumption.