## CryptoDB

### Shengli Liu

#### Publications

Year
Venue
Title
2021
CRYPTO
We construct the first authenticated key exchange protocols that achieve tight security in the standard model. Previous works either relied on techniques that seem to inherently require a random oracle, or achieved only “Multi-Bit-Guess” security, which is not known to compose tightly, for instance, to build a secure channel. Our constructions are generic, based on digital signatures and key encapsulation mechanisms (KEMs). The main technical challenges we resolve is to determine suitable KEM security notions which on the one hand are strong enough to yield tight security, but at the same time weak enough to be efficiently instantiable in the standard model, based on standard techniques such as universal hash proof systems. Digital signature schemes with tight multi-user security in presence of adaptive corruptions are a central building block, which is used in all known constructions of tightly-secure AKE with full forward security. We identify a subtle gap in the security proof of the only previously known efficient standard model scheme by Bader et al. (TCC 2015). We develop a new variant, which yields the currently most efficient signature scheme that achieves this strong security notion without random oracles and based on standard hardness assumptions.
2021
ASIACRYPT
For Key Encapsulation Mechanism (KEM) deployed in a multi-user setting, an adversary may corrupt some users to learn their secret keys, and obtain some encapsulated keys due to careless key managements of users. To resist such attacks, we formalize Enhanced security against Chosen Plaintext/Ciphertext Attack (ECPA/ECCA), which ask the pseudorandomness of unrevealed encapsulated keys under uncorrupted users. This enhanced security for KEM serves well for the security of a class of Authenticated Key Exchange protocols built from KEM. In this paper, we study the achievability of tight ECPA and ECCA security for KEM in the multi-user setting, and present an impossibility result and an optimal security loss factor that can be obtained. The existing meta-reduction technique due to Bader et al. (EUROCRYPT 2016) rules out some KEMs, but many well-known KEMs, e.g., Cramer-Shoup KEM (SIAM J. Comput. 2003), Kurosawa-Desmedt KEM (CRYPTO 2004), run out. To solve this problem, we develop a new technique tool named rank of KEM and a new secret key partitioning strategy for meta-reduction. With this new tool and new strategy, we prove that KEM schemes with polynomially-bounded ranks have no tight ECPA and ECCA security from non-interactive complexity assumptions, and the security loss is at least linear in the number n of users. This impossibility result covers lots of well-known KEMs, including the Cramer-Shoup KEM, Kurosawa-Desmedt KEM and many others. Moreover, we show that the linear security loss is optimal by presenting concrete KEMs with security loss Θ(n). This is justified by a non-trivial security reduction with linear loss factor from ECPA/ECCA security to the traditional multi-challenge CPA/CCA security.
2020
ASIACRYPT
We propose a generic construction of 2-pass authenticated key exchange (AKE) scheme with explicit authentication from key encapsulation mechanism (KEM) and signature (SIG) schemes. We improve the security model due to Gjosteen and Jager [Crypto2018] to a stronger one. In the strong model, if a replayed message is accepted by some user, the authentication of AKE is broken. We define a new security notion named ''IND-mCPA with adaptive reveals'' for KEM. When the underlying KEM has such a security and SIG has unforgeability with adaptive corruptions, our construction of AKE equipped with counters as states is secure in the strong model, and stateless AKE without counter is secure in the traditional model. We also present a KEM possessing tight ''IND-mCPA security with adaptive reveals'' from the Computation Diffie-Hellman assumption in the random oracle model. When the generic construction of AKE is instantiated with the KEM and the available SIG by Gjosteen and Jager [Crypto2018], we obtain the first practical 2-pass AKE with tight security and explicit authentication. In addition, the integration of the tightly IND-mCCA secure KEM (derived from PKE by Han et al. [Crypto2019]) and the tightly secure SIG by Bader et al. [TCC2015] results in the first tightly secure 2-pass AKE with explicit authentication in the standard model.
2019
PKC
Robustly reusable Fuzzy Extractor (rrFE) considers reusability and robustness simultaneously. We present two approaches to the generic construction of rrFE. Both of approaches make use of a secure sketch and universal hash functions. The first approach also employs a special pseudo-random function (PRF), namely unique-input key-shift (ui-ks) secure PRF, and the second uses a key-shift secure auxiliary-input authenticated encryption (AIAE). The ui-ks security of PRF (resp. key-shift security of AIAE), together with the homomorphic properties of secure sketch and universal hash function, guarantees the reusability and robustness of rrFE. Meanwhile, we show two instantiations of the two approaches respectively. The first instantiation results in the first rrFE from the LWE assumption, while the second instantiation results in the first rrFE from the DDH assumption over non-pairing groups.
2019
CRYPTO
We propose the concept of quasi-adaptive hash proof system (QAHPS), where the projection key is allowed to depend on the specific language for which hash values are computed. We formalize leakage-resilient(LR)-ardency for QAHPS by defining two statistical properties, including LR-$\langle \mathscr {L}_0, \mathscr {L}_1 \rangle$-universal and LR-$\langle \mathscr {L}_0, \mathscr {L}_1 \rangle$-key-switching.We provide a generic approach to tightly leakage-resilient CCA (LR-CCA) secure public-key encryption (PKE) from LR-ardent QAHPS. Our approach is reminiscent of the seminal work of Cramer and Shoup (Eurocrypt’02), and employ three QAHPS schemes, one for generating a uniform string to hide the plaintext, and the other two for proving the well-formedness of the ciphertext. The LR-ardency of QAHPS makes possible the tight LR-CCA security. We give instantiations based on the standard k-Linear (k-LIN) assumptions over asymmetric and symmetric pairing groups, respectively, and obtain fully compact PKE with tight LR-CCA security. The security loss is ${{O}}(\log {Q_{{e}}})$ where ${Q_{{e}}}$ denotes the number of encryption queries. Specifically, our tightly LR-CCA secure PKE instantiation from SXDH has only 4 group elements in the public key and 7 group elements in the ciphertext, thus is the most efficient one.
2018
PKC
Selective opening security (SO security) is desirable for public key encryption (PKE) in a multi-user setting. In a selective opening attack, an adversary receives a number of ciphertexts for possibly correlated messages, then it opens a subset of them and gets the corresponding messages together with the randomnesses used in the encryptions. SO security aims at providing security for the unopened ciphertexts. Among the existing simulation-based, selective opening, chosen ciphertext secure (SIM-SO-CCA secure) PKEs, only one (Libert et al. Crypto’17) enjoys tight security, which is reduced to the Non-Uniform LWE assumption. However, their public key and ciphertext are not compact.In this work, we focus on constructing PKE with tight SIM-SO-CCA security based on standard assumptions. We formalize security notions needed for key encapsulation mechanism (KEM) and show how to transform these securities into SIM-SO-CCA security of PKE through a tight security reduction, while the construction of PKE from KEM follows the general framework proposed by Liu and Paterson (PKC’15). We present two KEM constructions with tight securities based on the Matrix Decision Diffie-Hellman assumption. These KEMs in turn lead to two tightly SIM-SO-CCA secure PKE schemes. One of them enjoys not only tight security but also compact public key.
2018
ASIACRYPT
A fuzzy extractor (FE) aims at deriving and reproducing (almost) uniform cryptographic keys from noisy non-uniform sources. To reproduce an identical key R from subsequent readings of a noisy source, it is necessary to eliminate the noises from those readings. To this end, a public helper string P, together with the key R, is produced from the first reading of the source during the initial enrollment phase.In this paper, we consider computational fuzzy extractor. We formalize robustly reusable fuzzy extractor (rrFE) which considers reusability and robustness simultaneously in the Common Reference String (CRS) model. Reusability of rrFE deals with source reuse. It guarantees that the key R output by fuzzy extractor is pseudo-random even if the initial enrollment is applied to the same source several times, generating multiple public helper strings and keys $(P_i,R_i)$. Robustness of rrFE deals with active probabilistic polynomial-time adversaries, who may manipulate the public helper string $P_i$ to affect the reproduction of $R_i$. Any modification of ${P}_i$ by the adversary will be detected by the robustness of rrFE. We show how to construct an rrFE from a Symmetric Key Encapsulation Mechanism (SKEM), a Secure Sketch (SS), an Extractor (Ext), and a Lossy Algebraic Filter (LAF). We characterize the key-shift security notion of SKEM and the homomorphic properties of SS, Ext and LAF, which enable our construction of rrFE to achieve both reusability and robustness.We present an instantiation of SKEM from the DDH assumption. Combined with the LAF by Hofheinz (EuroCrypt 2013), homomorphic SS and Ext, we obtain the first rrFE based on standard assumptions.
2016
ASIACRYPT
2015
PKC
2015
PKC
2014
EUROCRYPT
2014
PKC
2013
PKC
2013
ASIACRYPT
2011
PKC

Eurocrypt 2022
PKC 2015