Skip to main content
eScholarship
Open Access Publications from the University of California

UC San Diego

UC San Diego Electronic Theses and Dissertations bannerUC San Diego

On identification, zero-knowledge, and plaintext-aware- encryption

Abstract

This dissertation studies three cryptographic tools: identification schemes -- collections of algorithms that enable a party to identify itself to another without revealing information that would facilitate impersonation; zero-knowledge proofs -- interactive protocols that efficiently demonstrate the validity of an assertion without conveying any additional knowledge; and plaintext- aware encryption schemes -- public-key encryption protocols with the property that the "only'' way to efficiently produce a valid ciphertext is to encrypt a message; hence the creator of a ciphertext must "know" the corresponding plaintext. We first consider two of the most efficient and best-known identification schemes: GQ and Schnorr. The question of whether they can be proved secure against impersonation under active attack had remained open for over ten years. This dissertation provides such a proof for GQ based on the one-more-RSA-inversion assumption, an extension of the usual one-wayness assumption. It also provides such a proof for Schnorr based on a corresponding discrete-logarithm-related assumption. Both results extend to establish security against impersonation under concurrent attack. Next, we falsify an assumption, here called KEA2, underlying the Hada-Tanaka 3-round negligible-error zero-knowledge protocol for NP. Providing such a protocol is a challenging problem that has attracted considerable research effort. The fact that KEA2 is false means that we "lose'' one of the few positive results on this subject. To recover the result, we propose a modification of KEA2. After removing a small bug in the Hada-Tanaka protocol that renders it unsound, we obtain a 3-round, negligible- error zero-knowledge protocol for NP under the discrete- logarithm assumption and our new, suitably modified, assumption. Finally, we address the problem of defining and achieving plaintext-aware encryption in the standard public-key setting. We provide definitions for three notions of increasing strength: PA0, PA1, PA2, chosen so that security against chosen-plaintext attack (IND-CPA) coupled with PA1 implies security against non-adaptive chosen-ciphertext attack (IND-CCA1), and IND-CPA coupled with PA2 implies security against adaptive chosen- ciphertext attack (IND-CCA2). Towards achieving the new notions, we show that a scheme due to Damgard, denoted DEG, and Cramer-Shoup "lite" are both PA0 under Damgard's DHK0 assumption, and PA1 under an extension of DHK0. DEG is thus the most efficient scheme proved IND-CCA1-secure

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View