International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Jee Hea An

Publications

Year
Venue
Title
2003
EUROCRYPT
2003
EPRINT
Concealment and its Applications to Authenticated Encryption
Yevgeniy Dodis Jee Hea An
We introduce a new cryptographic primitive we call **concealment**, which is related, but quite different from the notion of commitment. A concealment is a publicly known randomized transformation, which, on input m, outputs a *hider* h and a *binder* b. Together, h and b allow one to recover m, but separately, (1) the hider h reveals "no information" about m, while (2) the binder b can be "meaningfully opened" by at most one hider h. While setting b=m, h=empty is a trivial concealment, the challenge is to make |b|<<|m|, which we call a "non-trivial" concealment. We show that non-trivial concealments are equivalent to the existence of collision-resistant hash functions. Moreover, our construction of concealments is extremely simple, optimal, and yet very general, giving rise to a multitude of efficient implementations. We show that concealments have natural and important applications in the area of **authenticated encryption**. Specifically, let AE be an authenticated encryption scheme (either public- or symmetric-key) designed to work on short messages. We show that concealments are **exactly** the right abstraction allowing one to use AE for encrypting long messages. Namely, to encrypt long m, one uses a concealment scheme to get h and b, and outputs authenticated ciphertext (AE(b),h). More surprisingly, the above paradigm leads to a very simple and general solution to the problem of **remotely keyed (authenticated) encryption** (RKAE). In this problem, one wishes to split the task of high-bandwidth authenticated encryption between a secure, but low-bandwidth/computationally limited device, and an insecure, but computationally powerful host. We give formal definitions for RKAE, which we believe are simpler and more natural than all the previous definitions. We then show that our composition paradigm satisfies our (very strong) definition. Namely, for authenticated encryption, the host simply sends a short value b to the device (which stores the actual secret key for AE), gets back AE(b), and outputs (AE(b),h) (authenticated decryption is similar). Finally, we also observe that several previous RKAE proposals are all special examples of our general paradigm.
2002
EUROCRYPT
2002
EUROCRYPT
2002
EPRINT
From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security
The Fiat-Shamir paradigm for transforming identification schemes into signature schemes has been popular since its introduction because it yields efficient signature schemes, and has been receiving renewed interest of late as the main tool in deriving forward-secure signature schemes. We find minimal (meaning necessary and sufficient) conditions on the identification scheme to ensure security of the signature scheme in the random oracle model, in both the usual and the forward-secure cases. Specifically we show that the signature scheme is secure (resp. forward-secure) against chosen-message attacks in the random oracle model if and only if the underlying identification scheme is secure (resp. forward-secure) against impersonation under passive (i.e.. eavesdropping only) attacks, and has its commitments drawn at random from a large space. An extension is proven incorporating a random seed into the Fiat-Shamir transform so that the commitment space assumption may be removed.
2002
EPRINT
On the Security of Joint Signature and Encryption
We formally study the notion of a joint signature and encryption in the public-key setting. We refer to this primitive as {\em signcryption}, adapting the terminology of Zheng [Zhe97]. We present wo definitions for the security of signcryption depending on whether the adversary is an outsider or a legal user of the system. We then examine generic sequential composition methods of building signcryption from a signature and encryption scheme. Contrary to what recent results in the symmetric setting [BN00,Kra01] might lead one to expect, we show that classical ``encrypt-then-sign'' (EtS) and ``sign-then-encrypt'' (StE) methods are both {\em secure} composition methods in the public-key setting. We also present a new composition method which we call ``commit-then-encrypt-and-sign'' (CtE&S). Unlike the generic sequential composition methods, CtE&S applies the expensive signature and encryption operations {\em in parallel}, which could imply a gain in efficiency over the StE and EtS schemes. We also show that the new CtE&S method elegantly combines with the recent ``hash-sign-switch'' technique of Shamir and Tauman [ST01], leading to efficient {\em on-line/off-line} signcryption. Finally and of independent interest, we discuss the {\em definitional} inadequacy of the standard notion of chosen ciphertext (CAA) security. Motivated by our applications to signcryption, we show that the notion of CAA-security is syntactically ill-defined, and leads to artificial examples of ``secure'' encryption schemes which do not meet the formal definition of CCA-security. We suggest a natural and very slight relaxation of CAA-security, which we call generalized CCA-security (gCCA). We show that gCCA-security suffices for all known uses of CCA-secure encryption, while no longer suffering from the definitional shortcomings of the latter.
2001
EUROCRYPT
2001
EPRINT
Authenticated Encryption in the Public-Key Setting: Security Notions and Analyses
Jee Hea An
This paper addresses the security of authenticated encryption schemes in the public key setting. We present two new notions of authenticity that are stronger than the integrity notions given in the symmetric setting \cite{bn00}. We also show that chosen-ciphertext attack security (IND-CCA) in the public key setting is not obtained in general from the combination of chosen-plaintext security (IND-CPA) and integrity of ciphertext (INT-CTXT), which is in contrast to the results shown in the symmetric setting \cite{ky00,bn00}. We provide security analyses of authenticated encryption schemes constructed by combining a given public key encryption scheme and a given digital signature scheme in a ``generic'' manner ---namely, Encrypt-and-Sign, Sign-then-Encrypt, and Encrypt-then-Sign--- and show that none of them, in general, provide security under all notions defined in this paper. We then present a scheme called {\em ESSR} that meets all security notions defined here. We also give security analyses on an efficient Diffie-Hellman based scheme called {\em DHETM}, which can be thought of as a transform of the encryption scheme ``DHIES'' \cite{abr01} into an {\em authenticated} encryption scheme in the public key setting.
1999
CRYPTO

Program Committees

Crypto 2004
Asiacrypt 2004