International Journal of Foundations of Computer Science

In 2010, Fan et al. first introduced the concept of anonymous multi-receiver identity-based encryption (AMRIBE). They used the concept of Fujisaki–Okamoto transformation (F.O. transformation) to support their proof in random oracle models. Recently, many works on this topic have been proposed. Most of them adopted Fujisaki–Okamoto transformation to achieve the indistinguishability of encryptions under multi-ID, chosen-ciphertext attacks (IND-MID-CCA) security. However, we find out that these schemes do not gain anonymity against insider attacks. In this manuscript, we use a sequence of games to prove that any AMRIBE scheme will fail to gain anonymity under chosen-ciphertext attacks and chosen-plaintext attacks if the IND-MID-CCA security is proven using Fujisaki–Okamoto transformation.

Signcryption has drawn a lot of attention due to its useful applications in many areas, in particular for applications where the computation and communication resources are constrained, for example, for lightweight devices. The traditional signcryption scheme does not support the homomorphic property. Recent work by Rezaeibagha et al. (Provsec 2017) offered a provably secure homomorphic signcryption scheme, in which for the first time, provided a scheme provably secure under some restriction. In this paper, we show that the homomorphic signcryption can be extended to provably secure broadcast signcryption scheme. We allow the broadcasted signcrypted data items to be aggregated without requiring decryption that is a desirable feature in distributed environments.

We present an access control encryption (ACE) scheme which enjoys advantages over previous works in several aspects. Our scheme ensures not only compact ciphertext size but also small size of keys installed in each user in the ACE system. Besides, to the best of our knowledge, our scheme is the first implementation of ACE with decentralized sanitizers. Comparing to ACE constructions with only one sanitizer, our scheme is more secure and reliable since it does not suffer from the single point failure. Considering the security of our scheme, we present two models catering to the no-read rule and no-write rule security requirements respectively. Additionally, our extended no-write rule model allows the corruption of some sanitizers in the ACE system and thus is stronger than the one for schemes with only one sanitizer. We prove the security of our scheme under the two models.

A cloud storage system which incorporates the deletion and deduplication functionalities will have both security and efficiency advantages over exiting solutions which provide only one of them. However, the security models of secure data deletion and data deduplication functionalities are not compatible with each other, which will cause security and efficiency vulnerability under coercive adversaries. To solve these security and efficiency challenges, we define and construct a scheme, whose security relies on the proper erasure of keys in the wrapped key tree and periodical update of the deduplication encryption keys. Moreover, we enhance the efficiency of the proposed scheme by introducing incremental data update, where only the changed part is encrypted/decrypted and uploaded/downloaded in data updating. Further security analysis shows that the proposed scheme is secure against coercive attack. Finally, the practical implementation shows that our scheme is performance efficient in computation, storage and communication for both the cloud storage server and users.

Graph data structure has been widely used across many application areas, such as web data, social network, and cheminformatics. The main benefit of storing data as graphs is there exists a rich set of graph algorithms and operations that can be used to solve various computing problems, including pattern matching, data mining, and image processing. Among these graph algorithms, the subgraph isomorphism problem is one of the most fundamental algorithms that can be utilized by many higher level applications. The subgraph isomorphism problem is defined as, given two graphs $G$ and $H$, whether $G$ contains a subgraph that is isomorphic to $H$. In this paper, we consider a special case of the subgraph isomorphism problem called the subgraph matching problem, which tests whether $G$ is a subgraph of $H$. We propose a protocol that solve the subgraph matching problem in a privacy-preserving manner. The protocol allows two parties to jointly compute whether one graph is a subgraph of the other, while protecting the private information about the input graphs. The protocol is secure under the semi-honest setting, where each party performs the protocol faithfully.

As the progress of quantum computers, it is desired to propose many more efficient cryptographic constructions with post-quantum security. In the literatures, almost all cryptographic schemes and protocols can be explained and constructed modularly from certain cryptographic primitives, among which an Identity-Based Hash Proof System (IB-HPS) is one of the most basic and important primitives. Therefore, we can utilize IB-HPSs with post-quantum security to present several types of post-quantum secure schemes and protocols. Up until now, all known IB-HPSs with post-quantum security are instantiated based on latticed-based assumptions. However, all these lattice-based IB-HPSs are either in the random oracle model or not efficient enough in the standard model. Hence, it should be of great significance to construct more efficient IB-HPSs from lattices in the standard model.

In this paper, we propose a new smooth IB-HPS with anonymity based on the Learning with Errors (LWE) assumption in the standard model. This new construction is mainly inspired by a classical identity-based encryption scheme based on LWE due to Agreawal et al. in Eurocrypt 2010. And our innovation is to employ the algorithm SampleGaussian introduced by Gentry et al. and the property of random lattice to simulate the identity secret key with respect to the challenge identity. Compared with other existing IB-HPSs in the standard model, our master public key is quite compact. As a result, our construction has much lower overheads on computation and storage.

Attribute-based encryption (ABE) is an active research area in the public-key cryptography. Among large amount of ABE schemes, the scheme GVW’13 (STOC13) is an well-known candidate for realizing ABE via lattice mechanism, whose security relies on learning with errors (LWE). This ABE scheme has very exquisite structure, and its crucial component lies in using that two-to-one recoding (TOR) algorithm. However, the main shortcoming of GVW’13 is the use of the huge key-size. Therefore, it encourages people to find out some more simplified variants of GVW’13.

In this paper, we first propose three variants of GVW’13 for reducing the size of secret key, which would be the feasible strategies to improve GVW’13 with great possibility. Unfortunately, we can still present three related attacks against these three proposals under the same collusion scenario, respectively.

Most of the existing cryptographic schemes, e.g., key agreement protocol, call for good randomness. Otherwise, the security of these cryptographic schemes cannot be fully guaranteed. Nonce-based cryptosystem is recently introduced to improve the security of public key encryption and digital signature schemes by ensuring security when randomness fails. In this paper, we first investigate the security of key agreement protocols when randomness fails. Then we define the security model for nonce-based key agreement protocols and propose a nonce-based key agreement protocol that protects against bad randomness. The new protocol is proven to be secure in our proposed security model.

The McEliece public key cryptosystem and the Niederreiter public key cryptosystem are the two major branches of the code-based public key cryptosystem. It has been found that the difficult problems relied by these two systems are different from the syndrome decoding problem stated by Berlekamp et al. The Hamming weight of the error vector is fixed and known to the attackers in these two systems, which leading to the disclosure of information, and through which the attacker can implement an effective attack. In this paper, an improved vision of the McEliece public key cryptosystem was given, and a new code-based signature scheme is designed based on the new cryptosystem. As a result, we achieve a more secure variant of McEliece public key cryptosystem and a more secure code-based signature scheme with high security and fast signing speed.

Online social networking applications have become more and more popular in the advance of the technological age. Much of our personal information has been disclosed in social networking activities and privacy-preserving still remains a research challenge in social network. Public key encryption scheme with equality test(PKEET), which is an extension of public key encryption with keyword search (PEKS), seems to be a solution. PKEET enables the tester to check whether two given ciphertexts are derived from the same plaintext. Recently, Zhu et al. proposed a pairing-free public key encryption scheme with equality test based on the traditional public key cryptosystem. However, it suffers from certificates management issue. In this paper, we propose a pairing-free identity-based encryption scheme with authorized equality test(PF-IBEAET). The PF-IBEAET scheme also provides fine-grained authorizations. We prove that the scheme is one way secure against chosen identity and chosen ciphertext attack (OW-ID-CCA) and indistinguishable against chosen-identity and chosen-ciphertext attack (IND-ID-CCA) in the random oracle model (ROM). Performance analysis shows that the scheme achieves a better performance than similar schemes.

As a promising public key cryptographic primitive, hierarchical identity-based encryption (HIBE) introduces key delegation mechanisms into identity-based encryption. However, key leakage and recipient anonymity issues have not been adequately addressed in HIBE. Hence, direct applications of traditional HIBE schemes will violate data security and abuse users’ privacy in practice. In this paper, we propose an anonymous unbounded hierarchical identity-based encryption scheme, which achieves bounded leakage resilience and the hierarchy depth is not limited. Our security proofs based on the dual system encryption technique show that the proposed scheme is capable of resisting key leakage and it realizes recipient anonymity in the standard model. In addition, leakage resilience analysis indicates that our scheme allows the leakage rate of approximate 1/3 no matter the hierarchy depth of identities. Finally, performance comparisons show the practicability of our scheme. In particular, the secret key of our construction is of a fixed-length.