Information Security and Privacy

We construct a compact public-key encryption with tight CCA security in the multi-user, multi-challenge setting, where the reduction loss is a constant. Our scheme follows the Hofheinz-Jager framework but is compressed in the sense that only one of the underlying two-tier signatures needs to be committed. Considering the virtually unbounded simulations, e.g., \(2^{80}\), the ciphertext size of our scheme decreases to about 256 group elements, whereas the best known solution provided by Blazy et al. required about 625 group elements under the same standard assumptions. In particular, we formalize a new notion called simulatable two-tier signature, which plays a central role in the construction of our tree-based signature and public-key encryption. Combining simulatable two-tier signatures with additional “ephemeral” signatures, we provide a method of constructing commitments to a tree-based signature, where most parts of the tree-based signature can be simulated and sent in the clear. Our method can reduce the length of the commitments and the related proofs of knowledge in previous works by 60%.

In contrast to the conventional all-or-nothing encryption, functional encryption (FE) allows partial revelation of encrypted information based on the keys associated with different functionalities. Extending FE with key delegation ability, hierarchical functional encryption (HFE) enables a secret key holder to delegate a portion of its decryption ability to others and the delegation can be done hierarchically. All HFE schemes in the literature are for general functionalities and not very practical. In this paper, we focus on the functionality of linear transformations (i.e. matrix product evaluation). We refine the definition of HFE and further extend the delegation to accept multiple keys. We also propose a generic HFE construction for linear transformations with IND-CPA security in the standard model from hash proof systems. In addition, we give two instantiations from the DDH and DCR assumptions which to the best of our knowledge are the first practical concrete HFE constructions.

The Learning Parity with Noise (LPN) problem has found many applications in cryptography due to its conjectured post-quantum hardness and simple algebraic structure. Over the years, constructions of different public-key primitives were proposed from LPN, but most of them are based on the LPN assumption with low noise rate rather than constant noise rate. A recent breakthrough was made by Yu and Zhang (Crypto’16), who constructed the first Public-Key Encryption (PKE) from constant-noise LPN. However, the problem of designing a PKE with Key-Dependent Message (KDM) security from constant-noise LPN is still open.

In this paper, we present the first PKE with KDM-security assuming certain sub-exponential hardness of constant-noise LPN, where the number of users is predefined. The technical tool is two types of multi-fold LPN on squared-log entropy, one having independent secrets and the other independent sample subspaces. We establish the hardness of the multi-fold LPN variants on constant-noise LPN. Two squared-logarithmic entropy sources for multi-fold LPN are carefully chosen, so that our PKE is able to achieve correctness and KDM-security simultaneously.

Cryptographic commitments are either unconditionally hiding or unconditionally binding, but cannot be both. As a consequence, the security of commonly used commitment schemes is threatened in the long-term, when adversaries become computationally much more powerful. We improve over this situation by putting forward a new notion of commitment schemes, so called long-term commitment schemes. These schemes allow for long-term protection because they allow to adjust the protection level after the initial commitment. We also present a construction of a long-term commitment scheme. Unfortunately, it seems impossible to prove the security of such a scheme using the traditional commitment binding definition. Therefore, we put forward a new notion of binding commitments, so called extractable-binding commitments, and use this notion to establish a security proof for our proposed long-term commitment scheme.

We propose adaptively secure attribute-based encryption (ABE) schemes for boolean formulas over large universe attributes from the decisional linear (DLIN) assumption, which allow attribute reuse in an available formula without the previously employed redundant multiple encoding technique. Thus our KP-(resp. CP-)ABE has non-redundant ciphertexts (resp. secret keys). For achieving the results, we develop a new encoding method for access policy matrix for ABE, by decoupling linear secret sharing (LSS) into its matrix and randomness, and partially randomizing the LSS shares in simulation. The new techniques are of independent interest and we expect it will find another application than ABE.

To protect data security and privacy in cloud storage systems, a common solution is to outsource data in encrypted forms so that the data will remain secure and private even if storage systems are compromised. The encrypted data, however, must be pliable to search and access control. In this paper, we introduce a notion of attribute-based encryption with expressive and authorized keyword search (ABE-EAKS) to support both expressive keyword search and fine-grained access control over encrypted data in the cloud. In ABE-EAKS, every data user is associated with a set of attributes and is issued a private attribute-key corresponding to his/her attribute set, and each data owner encrypts the message using attribute-based encryption and attaches the encrypted message with encrypted keywords related with the message, and then uploads the encrypted message and keywords to the cloud. To access encrypted messages containing certain keywords satisfying a search policy, a data user generates a trapdoor for the search policy using his/her private attribute-key and sends it to the cloud server equipped to the cloud. The cloud server searches over encrypted data stored in the cloud for the encrypted messages containing keywords satisfying the search policy and sends back the results to the data user who then decrypts the returned ciphertexts to obtain the underlying messages. We present a generic construction for ABE-EAKS, formally prove its security, give a concrete construction, and then extend the concrete ABE-EAKS scheme to support user revocation. Also, we implement the proposed ABE-EAKS scheme and its extension and study their performance through experiments.

Identity-based encryption (IBE) has been extensively studied and widely used in various applications since Boneh and Franklin proposed the first practical scheme based on pairing. In that seminal work, it has also been pointed out that providing an efficient revocation mechanism for IBE is essential. Hence, revocable identity-based encryption (RIBE) has been proposed in the literature to offer an efficient revocation mechanism. In contrast to revocation, another issue that will also occur in practice is to combine two or multiple IBE systems into one system, e.g., due to the merge of the departments or companies. However, this issue has not been formally studied in the literature and the naive solution of creating a completely new system is inefficient. In order to efficiently address this problem, in this paper we propose the notion of mergeable and revocable identity-based encryption (MRIBE). Our scheme provides the first solution to efficiently revoke users and merge multiple IBE systems into a single system. The proposed scheme also has several nice features: when two systems are merged, there is no secure channel needed for the purpose of updating user private keys; and the size of the user private key remains unchanged when multiple systems are merged. We also propose a new security model for MRIBE, which is an extension of the security model for RIBE, and prove that the proposed scheme is semantically secure without random oracles.

Testing if two ciphertexts contain the same plaintext is an interesting cryptographic primitive. It is usually referred to as equality test of encrypted data or equality test. One of attractive applications of equality test is for encrypted database systems, where the database server hosts the encrypted databases and users can query if the plaintext embedded in a ciphertext on a database is equal to that in the queried ciphertext without decryption. Although it is not hard to achieve with the pairing-based cryptography, the security against the insider attack (by the database server) is a challenging task. In this paper, we propose a novel equality test scheme aiming to solve the problem. Our scheme adopts the identity-based cryptography. We prove the security of our scheme in the random oracle model.

A revocable identity-based encryption (RIBE) scheme, proposed by Boldyreva et al., provides a revocation functionality for managing a number of users dynamically and efficiently. To capture a realistic scenario, Seo and Emura introduced an additional important security notion, called decryption key exposure resistance (DKER), where an adversary is allowed to query short-term decryption keys. Although several RIBE schemes that satisfy DKER have been proposed, all the lattice-based RIBE schemes, e.g., Chen et al.’s scheme, do not achieve DKER, since they basically do not have the key re-randomization property, which is considered to be an essential requirement for achieving DKER. In particular, in every existing lattice-based RIBE scheme, an adversary can easily recover plaintexts if the adversary is allowed to issue even a single short-term decryption key query. In this paper, we propose a new lattice-based RIBE scheme secure against exposure of a-priori bounded number of decryption keys (for every identity). We believe that this bounded notion is still meaningful and useful from a practical perspective. Technically, to achieve the bounded security without the key re-randomization property, key updates in our scheme are short vectors whose corresponding syndrome vector changes in each time period. For this approach to work correctly and for the scheme to be secure, cover free families play a crucial role in our construction.

We propose a multi-user Symmetric Searchable Encryption (SSE) scheme based on the single-user Oblivious Cross Tags (OXT) protocol (Cash et al., CRYPTO 2013). The scheme allows any user to perform a search query by interacting with the server and any \(\theta -1\) ‘helping’ users, and preserves the privacy of database content against the server even assuming leakage of up to \(\theta -1\) users’ keys to the server (for a threshold parameter \(\theta \)), while hiding the query from the \(\theta -1\) ‘helping users’. To achieve the latter query privacy property, we design a new distributed key-homomorphic pseudorandom function (PRF) that hides the PRF input (search keyword) from the ‘helping’ key share holders. By distributing the utilized keys among the users, the need of constant online presence of the data owner to provide services to the users is eliminated, while providing resilience against user key exposure.

With the rapid development of cloud computing, more and more data owners are motivated to outsource their data to cloud for various benefits. Due to serious privacy concerns, sensitive data should be encrypted before being outsourced to the cloud. However, this results that effective data utilization becomes a very challenging task, such as keyword search over ciphertexts. Although many searchable encryption methods have been proposed, they only support exact keyword search. In our paper, we propose a method which could support both the fuzzy keyword search and access control over ciphertexts. Our proposed method achieves fuzzy keyword search and access control through algorithm design and Ciphertext-Policy Attribute-based Encryption. We present word pattern which can be used to balance the search efficiency and privacy. The experimental results demonstrate the efficiency of our method.

Searchable Encryption (SE) makes it possible for users to outsource an encrypted database and search operations to cloud service providers without leaking the content of data or queries to them. A number of SE schemes have been proposed in the literature; however, most of them leak a significant amount of information that could lead to inference attacks. To minimise information leakage, there are a number of solutions, such as Oblivious Random Access Memory (ORAM) and Private Information Retrieval (PIR). Unfortunately, existing solutions are prohibitively costly and impractical. A practical scheme should support not only a lightweight user client but also a flexible key management mechanism for multi-user access.

In this position paper, we briefly analyse several leakage-based attacks, and identify a set of requirements for a searchable encryption system for cloud database storage to be secure against these attacks while ensuring usability of the system. We also discuss several possible solutions to fulfil the identified requirements.

A cryptanalytic time-memory trade-off is a technique that aims to reduce the time needed to perform an exhaustive search. Such a technique requires large-scale precomputation that is performed once for all and whose result is stored in a fast-access internal memory. When the considered cryptographic problem is overwhelmingly-sized, using an external memory is eventually needed, though. In this paper, we consider the rainbow tables – the most widely spread version of time-memory trade-offs. The objective of our work is to analyze the relevance of storing the precomputed data on an external memory (SSD and HDD) possibly mingled with an internal one (RAM). We provide an analytical evaluation of the performance, followed by an experimental validation, and we state that using SSD or HDD is fully suited to practical cases, which are identified.

In this paper, we study the security of multi-prime RSA with small prime difference and propose two improved factoring attacks. The modulus involved in this variant is the product of r distinct prime factors of same bit-size. Zhang and Takagi (ACISP 2013) showed a Fermat-like factoring attack on multi-prime RSA. In order to improve the previous result, we gather more information about the prime factors to derive r simultaneous modular equations. The first attack is based on combining r equations to solve one multivariate modular equation by a generic lattice approach. Since the equation form is similar to multi-prime \(\varPhi \)-hiding problem, we propose the second attack by applying the optimal linearization technique. We also show that our attacks can achieve better bounds in the experiments.

The goal of leakage-resilient cryptography is to construct cryptographic algorithms that are secure even if the adversary obtains side-channel information from the real world implementation of these algorithms. Most of the prior works on leakage-resilient cryptography consider leakage models where the adversary has access to the leakage oracle before the challenge-ciphertext is generated (before-the-fact leakage). In this model, there are generic compilers that transform any leakage-resilient CPA-secure public key encryption (PKE) scheme to its CCA-2 variant using Naor-Yung type of transformations. In this work, we give an efficient generic compiler for transforming a leakage-resilient CPA-secure PKE to leakage-resilient CCA-2 secure PKE in presence of after-the-fact split-state (bounded) memory leakage model, where the adversary has access to the leakage oracle even after the challenge phase. The salient feature of our transformation is that the leakage rate (defined as the ratio of the amount of leakage to the size of secret key) of the transformed after-the-fact CCA-2 secure PKE is same as the leakage rate of the underlying after-the-fact CPA-secure PKE, which is \(1-o(1)\).

HIGHT is a lightweight block cipher with 64-bit block length and 128-bit security, and it is based on the ARX-based generalized Feistel network. HIGHT became a standard encryption algorithm in South Korea and also is internationally standardized by ISO/ICE 18033-3. Therefore, many third-party cryptanalysis against HIGHT have been proposed. Especially, impossible differential and integral attacks are applied to reduced-round HIGHT, and the current best attack under the single-key setting is 27 rounds using the impossible differential attack. In this paper, we propose an improved integral attack against HIGHT. We first propose new 19-round integral characteristics by using the propagation of the division property, and they are improved by two rounds compared with previous integral characteristics. Finally, we can attack 28-round HIGHT by appending 9-round key recovery. Moreover, we can attack 29-round HIGHT if the full code book is used, and it improves by two rounds compared with previous best attack.

In Asiacrypt 2016, Simpira v2 was proposed as a family of efficient permutations. It combines the AES round function with the Generalized Feistel Scheme (GFS) to construct permutations with arbitrarily large size which is a multiple of 128-bit. In this paper, we study the security of Simpira-3, the 3-block instance of Simpira v2. By applying the truncated differential analysis, we construct 8-round and 9-round distinguishers for Simpira-3 with complexity 2 and \( 2^{22} \) respectively. Then, we apply the impossible differential analysis to construct a 9-round impossible differential. Using this impossible differential, we can launch 9- and 10-round partial key recovery attacks on Simpira-3-based block cipher. Lastly, we present a boomerang distinguisher for 10-round Simpira-3 with practical complexity \( 2^{23} \). To the best of our knowledge, this is the first cryptanalysis results on Simpira-3. Our analysis will not affect the security of Simpira.

Advanced Encryption Standard (AES), published by NIST, is widely used in data encryption algorithms, hash functions, authentication encryption schemes and so on. Studying distinguishing attacks on (reduced round) AES can help designers and cryptanalysts to evaluate the security of target ciphers. Since integral attack is one of the most powerful tool in the field of symmetric ciphers, in this paper, we evaluate the security of AES by integral cryptanalysis. Firstly we put forward a new statistical integral distinguisher with multiple structures on input and integral properties on output, which enables us to reduce the data complexity comparing to the traditional integral distinguishers under multiple structures. As illustrations, we propose a secret-key distinguisher on 5-round AES with secret S-box under chosen-ciphertext mode. Its data, time and memory complexities are \(2^{114.32}\) chosen ciphertexts, \(2^{110}\) encryptions and \(2^{33.32}\) blocks. This is the best integral distinguisher on AES with secret S-box under secret-key setting so far. Then we present improved known-key distinguishers on 8-round and full 10-round AES-128 with reduced complexities based on Gilbert’s work at ASIACRYPT’14. These distinguishers are the best ones according to the time complexity. Moreover, the proposed statistical integral model could be used to proceed known-key distinguishing attacks on other AES-like ciphers.

We revise their definitional framework, and present a new construction eliminating these shortcomings. In contrast to Camenisch et al.’s construction, ours requires only standard building blocks instead of chameleon hashes with ephemeral trapdoors. This makes this, now even stronger, primitive more attractive for practical use. We underpin the practical efficiency of our scheme by concrete benchmarks of a prototype implementation.