CryptoDB

Qiang Tang

Publications

Year
Venue
Title
2021
CRYPTO
We initiate the study of witness authenticating NIZK proof systems (waNIZKs), in which one can use a witness $w$ of a statement $x$ to identify whether a valid proof for $x$ is indeed generated using $w$. Such a new identification functionality enables more diverse applications, and it also puts new requirements on soundness that: (1) no adversary can generate a valid proof that will not be identified by any witness; (2) or forge a proof using her valid witness to frame others. To work around the obvious obstacle towards conventional zero-knowledgeness, we define entropic zero-knowledgeness that requires the proof to leak no partial information, if the witness has sufficient computational entropy. We give a formal treatment of this new primitive. The modeling turns out to be quite involved and multiple subtle points arise and particular cares are required. We present general constructions from standard assumptions. We also demonstrate three applications in non-malleable (perfect one-way) hash, group signatures with verifier-local revocations and plaintext-checkable public-key encryption. Our waNIZK provides a new tool to advance the state of the art in all these applications.
2021
ASIACRYPT
In this work, we introduce the notion of hierarchical integrated signature and encryption (HISE), wherein a single public key is used for both signature and encryption, and one can derive a secret key used only for decryption from the signing key, which enables secure delegation of decryption capability. HISE enjoys the benefit of key reuse, and admits individual key escrow. We present two generic constructions of HISE. One is from (constrained) identity-based encryption. The other is from uniform one-way function, public-key encryption, and general-purpose public-coin zero-knowledge proof of knowledge. To further attain global key escrow, we take a little detour to revisit global escrow PKE, an object both of independent interest and with many applications. We formalize the syntax and security model of global escrow PKE, and provide two generic constructions. The first embodies a generic approach to compile any PKE into one with global escrow property. The second establishes a connection between three-party non-interactive key exchange and global escrow PKE. Combining the results developed above, we obtain HISE schemes that support both individual and global key escrow. We instantiate our generic constructions of (global escrow) HISE and implement all the resulting concrete schemes for 128-bit security. Our schemes have performance that is comparable to the best Cartesian product combined public-key scheme, and exhibit advantages in terms of richer functionality and public key reuse. As a byproduct, we obtain a new global escrow PKE scheme that outperforms the best prior work in speed by several orders of magnitude, which might be of independent interest.
2020
ASIACRYPT
Updatable encryption (UE) is an attractive primitive, which allows the secret key of the outsourced encrypted data to be updated to a fresh one periodically. Several elegant works exist studying various security properties. We notice several major issues in existing security models of (ciphertext dependent) updatable encryption, in particular, integrity and CCA security. The adversary in the models is only allowed to request the server to re-encrypt {\em honestly} generated ciphertext, while in practice, an attacker could try to inject arbitrary ciphertexts into the server as she wishes. Those malformed ciphertext could be updated and leveraged by the adversary and cause serious security issues. In this paper, we fill the gap and strengthen the security definitions in multiple aspects: most importantly our integrity and CCA security models remove the restriction in previous models and achieve standard notions of integrity and CCA security in the setting of updatable encryption. Along the way, we refine the security model to capture post-compromise security and enhance the re-encryption indistinguishability to the CCA style. Guided by the new models, we provide a novel construction \recrypt, which satisfies our strengthened security definitions. The technical building block of homomorphic hash from a group may be of independent interests. We also study the relations among security notions; and a bit surprisingly, the folklore result in authenticated encryption that IND-CPA plus ciphertext integrity imply IND-CCA security does {\em not} hold for ciphertext dependent updatable encryption.
2019
PKC
We study how to construct secure digital signature schemes in the presence of kleptographic attacks. Our work utilizes an offline watchdog to clip the power of subversions via only one-time black-box testing of the implementation. Previous results essentially rely on an online watchdog which requires the collection of all communicating transcripts (or active re-randomization of messages).We first give a simple but generic construction, without random oracles, in the partial-subversion model in which key generation and signing algorithms can be subverted. Then, we give the first digital signature scheme in the complete-subversion model in which all cryptographic algorithms can be subverted. This construction is based on the full-domain hash. Along the way, we enhance the recent result of Russell et al.  (CRYPTO 2018) about correcting a subverted random oracle.
2018
CRYPTO
The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes, and can often act as an effective bridge between theory and practice. In this paper, we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes.We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a negligible fraction of inputs—into a construction that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., with adversaries who may subvert the implementation of cryptographic algorithms but undetectable via blackbox testing) to use random oracles as a trusted black box, in spite of not trusting the implementation. Our analysis relies on a general rejection re-sampling lemma which is a tool of possible independent interest.
2018
PKC
We put forth a new notion of distributed public key functional encryption. In such a functional encryption scheme, the secret key for a function f will be split into shares $\mathsf {sk}_i^f$ skif. Given a ciphertext $\mathsf {ct}$ ct that encrypts a message x, a secret key share $\mathsf {sk}_i^f$ skif, one can evaluate and obtain a shared value $y_i$ yi. Adding all the shares up can recover the actual value of f(x), while partial shares reveal nothing about the plaintext. More importantly, this new model allows us to establish function privacy which was not possible in the setting of regular public key functional encryption. We formalize such notion and construct such a scheme from any public key functional encryption scheme together with learning with error assumption.We then consider the problem of hosting services in the untrusted cloud. Boneh, Gupta, Mironov, and Sahai (Eurocrypt 2014) first studied such application and gave a construction based on indistinguishability obfuscation. Their construction had the restriction that the number of corrupted clients has to be bounded and known. They left an open problem how to remove such restriction. We resolve this problem by applying our function private (distributed) public key functional encryption to the setting of hosting service in multiple clouds. Furthermore, our construction provides a much simpler and more flexible paradigm which is of both conceptual and practical interests.Along the way, we strengthen and simplify the security notions of the underlying primitives, including function secret sharing.
2016
EUROCRYPT
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2010
EPRINT
Two-party key establishment has been a very fruitful research area in cryptography, with many security models and numerous protocols proposed. In this paper, we take another look at the YAK protocol and the HMQV protocols and present some extended analysis. Motivated by our analysis, we reflect on the security properties that are desired by two-party key establishment protocols, and their formalizations. In particular, we take into account the interface between a key establishment protocol and the applications which may invoke it, and emphasize the concept of session and the usage of session identifier. Moreover, we show how to design a two-party key establishment protocol to achieve both key authentication and entity authentication properties in our security model.
2007
EPRINT
In this paper we investigate the security properties of three versions of the WAI protocol in Chinese WLAN implementation plan. We first revisit the security analysis that has been done to the version 1 and 2. we show that the security proof given by Li, Moon, and Ma is incorrect and the alternative protocol EWAP of Zhang and Ma is insecure. We further analyse the third version of the WAI protocol and prove its security in the Canetti-Krawczyk model. In addition, we also provide some practical security analysis of this version.
2007
EPRINT
Unknown Key-Share (UKS) resilience is a basic security attribute in authenticated key agreement protocols, whereby two entities A and B should not be able to be coerced into sharing a key between them when in fact either A or B thinks that s/he is sharing the key with another entity C. In this paper we revisit some definitions of this attribute, the existing UKS attacks and the method of proving this attribute in the Bellare-Rogaway (BR) model in the literature. We propose a new UKS attack, which coerces two entities A and B into sharing a key with each other but in fact A thinks that she is sharing the key with another entity C and B thinks that he is sharing the key with another entity D, where C and D might or might not be the same entity. We call this attack a Bilateral Unknown Key-Share(BUKS) attack and refer to the existing UKS attacks, which are against one entity only, as a Unilateral UKS (UUKS) attack. We demonstrate that a few well-known authenticated key agreement protocols, some of which have been proved holding the UUKS resilience property, are vulnerable to the BUKS attack. We then explore a gap between the traditional BR-type proof of UUKS resilience and a BUKS adversary's behaviour, and extend the BR model to cover the BUKS resilience attribute. Finally we provide a simple countermeasure to prevent a key agreement protocol from BUKS attacks.
2006
EPRINT
In this paper we show that the group key agreement protocol proposed by Tseng suffers from a number of serious security vulnerabilities.
2006
EPRINT
In this paper we investigate a security model for Timed-Release Encryption schemes with Pre-Open Capability (TRE-PC schemes) proposed by Hwang, Yum, and Lee. Firstly, we show that the HYL model possesses a number of defects and fails to model some potentially practical security vulnerabilities faced by TRE-PC schemes. Secondly, we propose a new security model for TRE-PC schemes which models the securities against four kinds of attacker and avoids the defects of the HYL model. We also work out the complete relations among the security notions defined in the new model. Thirdly, we introduce the notion of TRE-PC-KEM, which is a special type of KEM, and show a way to construct a TRE-PC scheme using a TRE-PC-KEM and a DEM. Finally, we propose an instantiation of a TRE-PC-KEM and prove its security.
2005
EPRINT
In this paper we analyse an anonymous wireless authentication and conference key distribution scheme which is also designed to provide mobile participants with user identification privacy during the conference call. The proposed scheme consists of three sub-protocols: the Call Set-Up Authentication Protocol, the Hand-Off Authentication Protocol, and the Anonymous Conference Call Protocol. We show that the proposed scheme suffers from a number of security vulnerabilities.
2005
EPRINT
Two identification schemes based on the Maurer-Yacobi ID-based cryptosystem are analysed and shown to suffer from serious security problems.
2005
EPRINT
In this paper we analyse a password-based authenticated key establishment protocol due to Laih, Ding and Huang, which enables a user to authenticate himself to a server and negotiate a shared session key. This protocol is also designed to guarantee that a human being is actually involved in an ongoing protocol execution. However we show that the protocol suffers from offline dictionary attacks. We propose an enhanced password-based authenticated key establishment protocol which is secure against offline dictionary attacks, and that possesses an additional feature guaranteeing that a user is involved in each protocol execution.
2005
EPRINT
In this paper we show that two potential security vulnerabilities exist in the strong password-only authenticated key exchange scheme due to Jablon. Two standardised schemes based on Jablon's scheme, namely the first password-based key agreement mechanism in ISO/IEC FCD 11770-4 and the scheme BPKAS-SPEKE in IEEE P1363.2 also suffer from one or both of these security vulnerabilities. We further show that other password-based key agreement mechanisms, including those in ISO/IEC FCD 11770-4 and IEEE P1363.2, also suffer from these two security vulnerabilities. Finally, we propose means to remove these security vulnerabilities.
2005
EPRINT
In this paper we demonstrate the existence of a number of weaknesses in a leakage-resilient authenticated key transport (RSA-AKE) protocol due to Shin, Kobara and Imai.
2005
EPRINT
In this paper we analyse the security of two authenticated group key agreement schemes based on the group key agreement protocol of Burmester and Desmedt. One scheme was proposed by Burmester and Desmedt, and uses a separate authentication scheme to achieve authentication among the participants. We show that this scheme suffers from a number of security vulnerabilities. The other scheme was generated using the general protocol compiler of Katz and Yung. We show that in some circumstances, even if key confirmation is implemented, this scheme still suffers from insider attacks (which are not covered by the security model used by Katz and Yung).
2005
EPRINT
In this paper we show that the password-based Diffie-Hellman key exchange protocols due to Byun and Lee suffer from dictionary attacks.
2005
EPRINT
In most of the existing identity-based key agreement schemes, it is usually assumed that either the communicated parties know each other's identifier before the protocol starts or their identifiers are transferred along with the protocol messages. However, these schemes are not suitable for use in many real-world applications aimed to achieve unilateral identity privacy, which means that one communicating party does not want to expose his identifier to an outsider while his partner cannot know his identifier in advance. In this paper, we propose an efficient identity-based two-party key agreement scheme with unilateral identity privacy using pairing, and formally analyze its security in a modified Bellare-Rogaway key agreement security model.
2005
EPRINT
In this paper we propose two compilers which are designed to transform a group key exchange protocol secure against any passive adversary into an authenticated group key exchange protocol with key confirmation which is secure against any passive adversary, active adversary, or malicious insider. We show that the first proposed compiler gives protocols that are more efficient than those produced by the compiler of Katz and Yung. The second proposed compiler further reduces the computational complexity of the output protocols by using a Trusted Third Party (TTP). We moreover show that, although the protocols produced by the novel compilers have lower computational complexity than the protocols produced by the Katz-Yung compiler, the protocols nevertheless achieve key confirmation, unlike the protocols output by the Katz-Yung compiler.
2004
EPRINT
In this paper we analyse three improved authenticated group key agreement schemes, all of which are based on the conference key distribution systems proposed by Burmester and Desmedt. We show that all the schemes suffer from a type of impersonation attack, although these schemes are claimed to be secure.

Asiacrypt 2020
PKC 2019
Asiacrypt 2019
PKC 2018
Asiacrypt 2018