San Ling

I&C Journal 2022 Journal Article

A new framework for deniable secure key exchange

• Shaoquan Jiang
• Yeow Meng Chee
• San Ling
• Huaxiong Wang
• Chaoping Xing

A deniable secure key exchange protocol allows two parties to agree on a common secret while achieving two seemingly contradictory functionalities: authentication and deniability. The former requires each party to confirm the identity of the other while the latter requires any attacker (e. g. , participant or eavesdropper) be unable to prove to a third party an honest party's participation. Designing an efficient secure key exchange with deniability is a challenging problem. In this paper, we first formalize the deniability model by requiring information theoretic deniability with an eavesdropping attack. The information theoretic deniability has the advantage that it can hold forever without any computational assumption. An eavesdropping attack (Di Raimondo et al. , CCS'06) allows an attacker to apply eavesdropped transcripts into an active attack session. This gives an attacker more power to make the victim undeniable as he does not know the randomness of the transcript. We then propose an efficient, provably deniable secure framework of key exchange. Our deniability holds non-adaptively in the eavesdropping model. However, if we consider a model without an eavesdropping attack (which is practical in many scenarios), then our framework is proven adaptively deniable. This is important since no previous key exchange protocols can satisfy our adaptive and information theoretical deniability. We give a concrete realization for our framework that is more efficient than SKEME (Krawczyk, NDSS'96).

TCS Journal 2021 Journal Article

Adaptive oblivious transfer with access control from lattice assumptions

• Benoît Libert
• San Ling
• Fabrice Mouhartem
• Khoa Nguyen
• Huaxiong Wang

Adaptive oblivious transfer (OT) is a protocol where a sender initially commits to a database { M i } i = 1 N. Then, a receiver can query the sender up to k times with private indexes ρ 1, …, ρ k so as to obtain M ρ 1, …, M ρ k and nothing else. Moreover, for each i ∈ [ k ], the receiver's choice ρ i may depend on previously obtained messages { M ρ j } j < i. Oblivious transfer with access control (OT-AC) is a flavor of adaptive OT where database records are protected by distinct access control policies that specify which credentials a receiver should obtain in order to access each M i. So far, all known OT-AC protocols only support access policies made of conjunctions or rely on ad hoc assumptions in pairing-friendly groups (or both). In this paper, we provide an OT-AC protocol where access policies may consist of any branching program of polynomial length, which is sufficient to realize any access policy in NC1. The security of our protocol is proved under the Learning-with-Errors ( LWE ) and Short-Integer-Solution ( SIS ) assumptions. As a result of independent interest, we provide protocols for proving the correct evaluation of a committed branching program on a committed input.

SODA Conference 2019 Conference Paper

Binary Robust Positioning Patterns with Low Redundancy and Efficient Locating Algorithms

• Yeow Meng Chee
• Duc Tu Dao
• Han Mao Kiah
• San Ling
• Hengjia Wei

TCS Journal 2019 Journal Article

Lattice-based group signatures: Achieving full dynamicity (and deniability) with ease

• San Ling
• Khoa Nguyen
• Huaxiong Wang
• Yanhong Xu

Lattice-based group signature is an active research topic in recent years. Since the pioneering work by Gordon et al. (2010) [20], eight other schemes have been proposed, providing various improvements in terms of security, efficiency and functionality. However, most of the existing constructions work only in the static setting where the group population is fixed at the setup phase. The only two exceptions are the schemes by Langlois et al. (2014) [27] that handles user revocations (but new users cannot join), and by Libert et al. (2016) [28, 29] which addresses the orthogonal problem of dynamic user enrollments (but users cannot be revoked). In this work, we provide the first lattice-based group signature that offers full dynamicity (i. e. , users have the flexibility in joining and leaving the group), and thus, resolve a prominent open problem posed by previous works. Moreover, we achieve this non-trivial feat in a relatively simple manner. Starting with Libert et al. 's fully static construction (2016) [30] - which is arguably the most efficient lattice-based group signature to date, we introduce simple-but-insightful tweaks that allow to upgrade it directly into the fully dynamic setting. More startlingly, our scheme even produces slightly shorter signatures than the former, thanks to an adaptation of a technique proposed by Ling et al. (2013) [35], allowing to prove inequalities in zero-knowledge. The scheme satisfies the strong security requirements of Bootle et al. 's model (2016) [7], under the Short Integer Solution (SIS) and the Learning With Errors (LWE) assumptions. Furthermore, we demonstrate how to equip the obtained group signature scheme with the deniability functionality in a simple way. This attractive functionality, put forward by Ishida et al. (2016) [22], enables the tracing authority to provide an evidence that a given user is not the owner of a signature in question. In the process, we design a zero-knowledge protocol for proving that a given LWE ciphertext does not decrypt to a particular message.

TCS Journal 2019 Journal Article

Zero-knowledge arguments for matrix–vector relations and lattice-based group encryption

• Benoît Libert
• San Ling
• Fabrice Mouhartem
• Khoa Nguyen
• Huaxiong Wang

Group encryption ( GE ) is the natural encryption analogue of group signatures in that it allows verifiably encrypting messages for some anonymous member of a group while providing evidence that the receiver is a properly certified group member. Should the need arise, an opening authority is capable of identifying the receiver of any ciphertext. As introduced by Kiayias, Tsiounis and Yung (Asiacrypt'07), GE is motivated by applications in the context of oblivious retriever storage systems, anonymous third parties and hierarchical group signatures. This paper provides the first realization of group encryption under lattice assumptions. Our construction is proved secure in the standard model (assuming interaction in the proving phase) under the Learning-With-Errors ( LWE ) and Short-Integer-Solution ( SIS ) assumptions. As a crucial component of our system, we describe a new zero-knowledge argument system allowing to demonstrate that a given ciphertext is a valid encryption under some hidden but certified public key, which incurs to prove quadratic statements about LWE relations. Specifically, our protocol allows arguing knowledge of witnesses consisting of X ∈ Z q m × n, s ∈ Z q n and a small-norm e ∈ Z m which underlie a public vector b = X ⋅ s + e ∈ Z q m while simultaneously proving that the matrix X ∈ Z q m × n has been correctly certified. We believe our proof system to be useful in other applications involving zero-knowledge proofs in the lattice setting.

TCS Journal 2018 Journal Article

A lattice-based group signature scheme with verifier-local revocation

• San Ling
• Khoa Nguyen
• Adeline Roux-Langlois
• Huaxiong Wang

Support of membership revocation is a desirable functionality for any group signature scheme. Among the known revocation approaches, verifier-local revocation (VLR) seems to be the most flexible one, because it only requires the verifiers to possess some up-to-date revocation information, but not the signers. All of the contemporary VLR group signatures operate in the bilinear map setting, and all of them will be insecure once quantum computers become a reality. In this work, we introduce the first lattice-based VLR group signature, and thus, the first such scheme that is believed to be quantum-resistant. In comparison with existing lattice-based group signatures, our scheme has several noticeable advantages: support of membership revocation, logarithmic-size signatures, and milder hardness assumptions. Moreover, our construction works without relying on public-key encryption schemes, which is an intriguing feature for group signatures.

TCS Journal 2016 Journal Article

Analysis of Gong et al.'s CCA2-secure homomorphic encryption

• Hyung Tae Lee
• San Ling
• Huaxiong Wang

It is a well-known result that homomorphic encryption is not secure against adaptive chosen ciphertext attacks (CCA2) because of its malleable property. Very recently, however, Gong et al. proposed a construction asserted to be a CCA2-secure additively homomorphic encryption (AHE) scheme; in their construction, the adversary is not able to obtain a correct answer when querying the decryption oracle on a ciphertext obtained by modifying the challenge ciphertext (Theoretical Computer Science, 2016). Because their construction is very similar to Paillier's AHE, it appeared to support an additively homomorphic property, though they did not specify an evaluation algorithm for the scheme in their paper. In this paper, we present a simple CCA2 attack on their construction by re-randomizing the challenge ciphertext. Furthermore, we look into an additively homomorphic property of their construction. To do this, we first consider a typical candidate for an addition algorithm on ciphertexts, as provided for previous AHE constructions, and establish that it does not function correctly. Subsequently, we provide plausible evidence for the hardness of achieving an additively homomorphic property with their construction. According to our analysis, it seems hard to preserve an additively homomorphic property of their construction without any modification. In addition, as a minor contribution, we point out a flaw in the decryption algorithm of their construction and present a rectified algorithm for correct decryption.

TCS Journal 2012 Journal Article

Threshold changeable secret sharing schemes revisited

• Zhifang Zhang
• Yeow Meng Chee
• San Ling
• Mulan Liu
• Huaxiong Wang

This paper studies the methods for changing thresholds in the absence of secure channels after the setup of threshold secret sharing schemes. First, we construct a perfect ( t, n ) threshold scheme that is threshold changeable to t ′ > t, which is optimal with respect to the share size. This improves the scheme of Wang and Wong by relaxing the requirement from q ≥ n + v to q > n with the secret-domain F q v. But these threshold changeable schemes along with most previously known schemes turn out to be insecure under the collusion attack of players holding initial shares. By adding a broadcast enforcement term we enhance the model with collusion security and N options of threshold change. Then we construct a computationally secure scheme under the enhanced model, which involves much shorter shares and broadcast messages than the perfect schemes. Finally, we discuss how to realize the enrollment and disenrollment of players, and particularly, how to deal with L-fold changes of access polices.

TCS Journal 2000 Journal Article

Secret-sharing with a class of ternary codes

• Cunsheng Ding
• David R Kohel
• San Ling

Secret-sharing is an important topic of cryptography and has applications in information security. One approach to the construction of secret-sharing schemes is based on error-correcting codes. In this paper, we describe a secret-sharing scheme based on a class of ternary codes (Ding et al. IEEE Trans. Inform. Theory IT-46 (2000) 280–284). We determine the access structure and prove properties of the secret-sharing scheme.

TCS Journal 1999 Journal Article

Attack on RSA-type cryptosystems based on singular cubic curves over Z/nZ

• Seng Kiat Chua
• Ka Hin Leung
• San Ling

Several RSA-type cryptosystems based on singular cubic curves have been proposed in recent years (cf. Koyama, Lecture notes in Computer Science, vol. 921, Springer, Berlin, 1995, pp. 329–339; Kuwakado, IEICE Trans. Fund. E78-A (1995) 27–33; Koyama, IEICE Trans. Fund. E77-A (1994) 1309–1318). We show that these schemes are equivalent and demonstrate that they are insecure if a linear relation is known between two plaintexts.