Cryptology ePrint Archive: Report 2016/530

Destroying Steganography via Amalgamation: Kleptographically CPA Secure Public Key Encryption

Alexander Russell and Qiang Tang and Moti Yung and Hong-Sheng Zhou

Abstract: We describe a general technique to protect randomized algorithms against kleptographic attacks. We then apply the technique to construct the first IND-CPA secure public-key encryp- tion scheme in the kleptographic setting. Our scheme preserves IND-CPA security, even when all relevant cryptographic algorithms—including key generation—are subject to adversarial subversion. The scheme requires no trusted parties or re-randomization reverse firewalls. The technique also gives a secure symmetric key encryption scheme that advances the state-of-the- art by permitting adversarial subversion of key generation and, furthermore, requiring no a priori decryptability assumptions.

Designing cryptographic primitives immune to kleptographic subversion is an active area which has led to remarkable new models and techniques; many of these are realizable by systems and can reduce the threat of such strong attacks. The feasibility of public-key encryption that is kleptographically secure in the CPA sense has been open till now.

Category / Keywords: foundations /

Original Publication (with minor differences): ACM CCS 2017

Date: received 29 May 2016, last revised 24 Nov 2017

Contact author: qt44 at cornell edu; hszhou@vcu edu

Available format(s): PDF | BibTeX Citation

Version: 20171125:004559 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]