International Association for Cryptologic Research

International Association
for Cryptologic Research


Shaoquan Jiang

Affiliation: University of Waterloo


PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model 📺
Password-based authenticated key exchange (PAKE) allows two parties with a shared password to agree on a session key. In the last decade, the design of PAKE protocols from lattice assumptions has attracted lots of attention. However, existing solutions in the standard model do not have appealing efficiency. In this work, we first introduce a new PAKE framework. We then provide two realizations in the standard model, under the Learning With Errors (LWE) and Ring-LWE assumptions, respectively. Our protocols are much more efficient than previous proposals, thanks to three novel technical ingredients that may be of independent interests. The first ingredient consists of two approximate smooth projective hash (ASPH) functions from LWE, as well as two ASPHs from Ring-LWE. The latter are the first ring-based constructions in the literature, one of which only has a quasi-linear runtime while its function value contains $$varTheta (n)$$ field elements (where n is the degree of the polynomial defining the ring). The second ingredient is a new key conciliation scheme that is approximately rate-optimal and that leads to a very efficient key derivation for PAKE protocols. The third one is a new authentication code that allows to verify a MAC with a noisy key.
Attribute-Based Encryption with Key Cloning Protection
In this work, we consider the problem of key cloning in attribute-based encryption schemes. We introduce a new type of attribute-based encryption scheme, called token-based attribute-based encryption, that provides strong deterrence for key cloning, in the sense that delegation of keys reveals some personal information about the user. We formalize the security requirements for such a scheme in terms of indistinguishability of the ciphertexts and two new security requirements which we call uncloneability and privacy-preserving. We construct a privacy-preserving uncloneable token-based attribute-based encryption scheme based on Cheung and Newport's ciphertext-policy attribute-based encryption scheme and prove the scheme satisfies the above three security requirements. We discuss our results and show directions for future research.
Deniable Authentication on the Internet
Shaoquan Jiang
Deniable authentication is a technique that allows one party to send messages to another while the latter can not prove to a third party the fact of communication. In this paper, we first formalize a natural notion of deniable security and naturally extend the basic authenticator theorem by Bellare et al. \cite{bck98} to the setting of deniable authentication. Of independent interest, this extension is achieved by defining a deniable MT-authenticator via a game. This game is essentially borrowed from the notion of universal composition \cite{can01} although we do not assume any result or background about it. Then we construct two deniable MT-authenticators: uncontrollable random oracle based and the PKI based, both of which are just 3-round protocols. The second construction assumes the receiver owns a secret key. Such a setup assumption is very popular in the real world. (Without this assumption), all the previous protocols do not have a widely satisfiable performance when applied in the Internet-like environment. Finally, as our application, we obtain key exchange protocols that is deniably secure in the real world.
Efficient Primitives from Exponentiation in Zp
Shaoquan Jiang
Since Diffie-Hellman \cite{DH76}, many secure systems, based on discrete logarithm or Diffie-Hellman assumption in $\mathbb{Z}_p$, were introduced in the literature. In this work, we investigate the possibility to construct efficient primitives from exponentiation techniques over $\mathbb{Z}_p$. Consequently, we propose a new pseudorandom generator, where its security is proven under the decisional Diffie-Hellman assumption. Our generator is the most efficient among all generators from $\mathbb{Z}_p^*$ that are provably secure under standard assumptions. If an appropriate precomputation is allowed, our generator can produce $O(\log\log p)$ bits per modular multiplication. This is the best possible result in the literature (even improved by such a precomputation as well). Interestingly, our generator is the first provably secure under a decisional assumption and might be instructive for discovering potentially more efficient generators in the future. Our second result is a new family of universally collision resistant hash family (CRHF). Our CRHF is provably secure under the discrete log assumption and is more efficient than all previous CRHFs that are provably secure under standard assumptions (especially without a random oracle). This result is important, especially when the unproven hash functions (e.g., MD4, MD5, SHA-1) were broken by Wang et al. \cite{W+05,WY05,WYY05}.
Password Based Key Exchange with Mutual Authentication
Shaoquan Jiang Guang Gong
A reasonably efficient password based key exchange (KE) protocol with provable security without random oracle was recently proposed by Katz, {\em et al.} \cite{KOY01} and later by Gennaro and Lindell \cite{GL03}. However, these protocols do not support mutual authentication (MA). The authors explained that this could be achieved by adding an additional flow. But then this protocol turns out to be 4-round. As it is known that a high entropy secret based key exchange protocol with MA\footnote{we do not consider a protocol with a time stamp or a stateful protocol (e.g., a counter based protocol). In other words, we only consider protocols in which a session execution within an entity is independent of its history, and in which the network is asynchronous.} is optimally 3-round (otherwise, at least one entity is not authenticated since a replay attack is applicable), it is quite interesting to ask whether such a protocol in the password setting (without random oracle) is achievable or not. In this paper, we provide an affirmative answer with an efficient construction in the common reference string (CRS) model. Our protocol is even simpler than that of Katz, {\em et al.} Furthermore, we show that our protocol is secure under the DDH assumption ({\em without} random oracle).
Hybrid Broadcast Encryption and Security Analysis
Guang Gong Shaoquan Jiang
A broadcast encryption scheme for stateless receivers is a data distribution method which never updates users' secret information while in order to maintain the security the system efficiency decreases with the number of revoked users. Another method, a rekeying scheme is a data distribution approach where it revokes illegal users in an {\em explicit} and {\em immediate} way whereas it may cause inconvenience for users. A hybrid approach that appropriately combines these two types of mechanisms seems resulting in a good scheme. In this paper, we suggest such a hybrid framework by proposing a rekeying algorithm for subset cover broadcast encryption framework (for stateless receivers) due to Naor et al. Our rekeying algorithm can simultaneously revoke a number of users. A hybrid approach that appropriately combines these two types of mechanisms seems resulting in a good scheme. In this paper, we suggest such a hybrid framework by proposing a rekeying algorithm for subset cover broadcast encryption framework (for stateless receivers) due to Naor et al. Our rekeying algorithm can simultaneously revoke a number of users. As an important contribution, we formally prove that this hybrid framework has a pre-CCA like security, where in addition to pre-CCA power, the adversary is allowed to {\em adaptively} corrupt and revoke users. Finally, we realize the hybrid framework by two secure concrete schemes that are based on complete subtree method and Asano method, respectively.