International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Shouhuai Xu

Publications

Year
Venue
Title
2014
EPRINT
2005
EPRINT
Flexible Framework for Secret Handshakes (Multi-Party Anonymous and Un-observable Authentication)
Gene Tsudik Shouhuai Xu
In the society increasingly concerned with the erosion of privacy, privacy-preserving techniques are becoming very important. This motivates research in cryptographic techniques offering built-in privacy. A secret handshake is a protocol whereby participants establish a secure, anonymous and unobservable communication channel only if they are members of the same group. This type of ``private" authentication is a valuable tool in the arsenal of privacy-preserving cryptographic techniques. Prior research focused on 2-party secret handshakes with one-time credentials. This paper breaks new ground on two accounts: (1) it shows how to obtain secure and efficient secret handshakes with reusable credentials, and (2) it represents the first treatment of group (or {\em multi-party}) secret handshakes, thus providing a natural extension to the secret handshake technology. An interesting new issue encountered in multi-party secret handshakes is the need to ensure that all parties are indeed distinct. (This is a real challenge since the parties cannot expose their identities.) We tackle this and other challenging issues in constructing GCD -- a flexible framework for secret handshakes. The proposed framework lends itself to many practical instantiations and offers several novel and appealing features such as self-distinction and strong anonymity with reusable credentials. In addition to describing the motivation and step-by-step construction of the framework, this paper provides a thorough security analysis and illustrates two concrete framework instantiations.
2003
ASIACRYPT
2003
PKC
2003
EPRINT
Accumulating Composites and Improved Group Signing
Gene Tsudik Shouhuai Xu
Constructing practical and provably secure group signature schemes has been a very active research topic in recent years. A group signature can be viewed as a digital signature with certain extra properties. Notably, anyone can verify that a signature is generated by a legitimate group member, while the actual signer can only be identified (and linked) by a designated entity called a group manager. Currently, the most efficient group signature scheme available is due to Camenisch and Lysyanskaya \cite{CL02}. It is obtained by integrating a novel dynamic accumulator with the scheme by Ateniese, et al. \cite{ACJT00}. In this paper, we construct a dynamic accumulator that accumulates \emph{composites}, as opposed to previous accumulators that accumulated \emph{primes}. We also present an efficient method for proving knowledge of factorization of a committed value. Based on these (and other) techniques we design a novel provably secure group signature scheme. It operates in the \emph{common auxiliary string} model and offers two important benefits: 1) the {\sf Join} process is very efficient: a new member computes only a single exponentiation, and 2) the (unoptimized) cost of generating a group signature is 17 exponentiations which is appreciably less than the state-of-the-art.
2002
EUROCRYPT
2002
EPRINT
Key-Insulated Public-Key Cryptosystems
Cryptographic computations (decryption, signature generation, etc.) are often performed on a relatively insecure device (e.g., a mobile device or an Internet-connected host) which cannot be trusted to maintain secrecy of the private key. We propose and investigate the notion of \emph{key-insulated security} whose goal is to minimize the damage caused by secret-key exposures. In our model, the secret key(s) stored on the insecure device are refreshed at discrete time periods via interaction with a physically-secure --- but computationally-limited --- device which stores a ``master key''. All cryptographic computations are still done on the insecure device, and the public key remains unchanged. In a (t, N)-key-insulated scheme, an adversary who compromises the insecure device and obtains secret keys for up to t periods of his choice is unable to violate the security of the cryptosystem for \emph{any} of the remaining N-t periods. Furthermore, the scheme remains secure (for \emph{all} time periods) against an adversary who compromises \emph{only} the physically-secure device. We notice that key-insulated schemes significantly improve the security guarantee of forward-secure schemes [A97,BM99], in which exposure of the secret key at even a single time period (necessarily) compromises the security of the system for all future time periods. This improvement is achieved with minimal cost: infrequent key updates with a (possibly untrusted) secure device. We focus primarily on key-insulated public-key encryption. We construct a (t,N)-key-insulated encryption scheme based on any (standard) public-key encryption scheme, and give a more efficient construction based on the DDH assumption. The latter construction is then extended to achieve chosen-ciphertext security.