In practice, implementing this simple construction is surprisingly difficult, as the high- and mid-level APIs presented by the most commonly used crypto libraries (e.g. OpenSSL and forks thereof) do not permit one to specify the per-encryption randomness. Thus application developers are forced to piece together low-level functionalities and attend to any associated, security-critical algorithmic choices. Other approaches to hedged PKE present similar problems in practice.
We reconsider the matter of building hedged PKE schemes, and the security notions they aim to achieve. We lift the current best-possible security notion for hedged PKE (IND-CDA) from the CPA setting to the CCA setting, and then show how to achieve it using primitives that are readily available from high-level APIs. We also propose a new security notion, MM-CCA, which generalizes traditional IND-CCA to admit imperfect randomness. Like IND-CCA, and unlike IND-CDA, our notion gives the adversary the public key. We show that MM-CCA is achieved by RSA-OAEP in the random-oracle model; this is significant in practice because RSA-OAEP is directly available from high-level APIs across all libraries we surveyed. We sort out relationships among the various notions, and also develop new results for existing hedged PKE constructions.
Category / Keywords: public-key cryptography / hedged public-key encryption, cryptographic APIs Original Publication (with major differences): IACR-CRYPTO-2017 Date: received 31 May 2017, last revised 21 Aug 2017 Contact author: cjpatton at ufl edu Available format(s): PDF | BibTeX Citation Note: The latest version fixes a bug in Lemma 1 pointed out by Joseph Jaeger. Version: 20170821:202712 (All versions of this report) Short URL: ia.cr/2017/510