Enhanced Chosen-Ciphertext Security and Applications: Adam O'Neill, BU

10:00 am on Monday, February 25, 2013
12:00 pm on Monday, February 25, 2013
MCS 137
Recently, there has been interest in randomness-recovering public-key encryption (RR-PKE) (see, e.g., Peikert and Waters, STOC'08), where a receiver efficiently recovers not only the message but also the *random coins* of a sender. We contend that for applications of RR-PKE, the standard definition of chosen-ciphertext security (CCA) should be amended so that the adversary gets access not only to a decryption oracle but also a *randomness recovery* oracle, a new notion we call enhanced chosen-ciphertext (ECCA) security. We show that ECCA-secure RR-PKE can be constructed from adaptive trapdoor functions (ATDFs), as defined and realized by Kiltz et al. (EUROCRYPT 2010). Previously, Kiltz et al. showed how to construct standard CCA-secure PKE from ATDFs, but their construction turns out to be insufficient for ECCA security. Our construction crucially uses the notion of *detectable* CCA security, recently introduced by Hohenberger et al. (EUROCRYPT '12). In fact, we show that a form of ECCA-secure RR-PKE is *equivalent* both to ATDFs and to an extension called tag-based ATDFs, meaning that ATDFs and tag-based ATDFs are themselves equivalent, resolving an open question of Kiltz et al. We then show that ECCA-secure RR-PKE can be used to securely realize an approach to public-key encryption with non-interactive opening (PKENO) originally suggested by Damg{\aa}rd and Thorbek (EUROCRYPT 2007). PKENO, which allows a receiver to non-interactively prove that a ciphertext decrypts to a claimed message, has widespread applications to secure multiparty computation. We obtain new and practical PKENO schemes quite different from those in prior work. Joint work with Dana Dachman-Soled, Georg Fuchsbauer, and Payman Mohassel.