Efficient revocable identity-based encryption via subset difference methods

Providing an efficient revocation mechanism for identity-based encryption (IBE) is very important since a user’s credential (or private key) can be expired or revealed. revocable IBE (RIBE) is an extension of IBE that provides an efficient revocation mechanism. Previous RIBE schemes essentially use the complete subtree (CS) scheme of Naor, Naor and Lotspiech (CRYPTO 2001) for key revocation. In this paper, we present a new technique for RIBE that uses the efficient subset difference (SD) scheme of Naor et al. instead of using the CS scheme to improve the size of update keys. Following our new technique, we first propose an efficient RIBE scheme in prime-order bilinear groups by combining the IBE scheme of Boneh and Boyen and the SD scheme and prove its selective security under the standard assumption. Our RIBE scheme is the first RIBE scheme in bilinear groups that has O(r) number of group elements in an update key where r is the number of revoked users. Next, we also propose another RIBE scheme in composite-order bilinear groups and prove its full security under static assumptions. Our RIBE schemes also can be integrated with the layered subset difference scheme of Halevy and Shamir (CRYPTO 2002) to reduce the size of a private key.     

Improved hidden vector encryption with short ciphertexts and tokens

Hidden vector encryption (HVE) is a particular kind of predicate encryption that is an important cryptographic primitive having many applications, and it provides conjunctive equality, subset, and comparison queries on encrypted data. In predicate encryption, a ciphertext is associated with attributes and a token corresponds to a predicate. The token that corresponds to a predicate f can decrypt the ciphertext associated with attributes x if and only if f(x) = 1. Currently, several HVE schemes were proposed where the ciphertext size, the token size, and the decryption cost are proportional to the number of attributes in the ciphertext. In this paper, we construct efficient HVE schemes where the token consists of just four group elements and the decryption only requires four bilinear map computations, independent of the number of attributes in the ciphertext. We first construct an HVE scheme in composite order bilinear groups and prove its selective security under the well-known assumptions. Next, we convert it to use prime order asymmetric bilinear groups where there are no efficiently computable isomorphisms between two groups.     

Shorter identity-based encryption via asymmetric pairings

We present efficient identity-based encryption (IBE) under the symmetric external Diffie–Hellman (SXDH) assumption in bilinear groups; our scheme also achieves anonymity. In our IBE scheme, all parameters have constant numbers of group elements, and are shorter than those of previous constructions based on decisional linear (DLIN) assumption. Our construction uses both dual system encryption (Waters, CRYPTO 2009) and dual pairing vector spaces (Okamoto and Takashima, Pairing 2008; ASIACRYPT 2009). Specifically, we show how to adapt the recent DLIN-based instantiation of Lewko (EUROCRYPT 2012) to the SXDH assumption. To our knowledge, this is the first work to instantiate either dual system encryption or dual pairing vector spaces under the SXDH assumption. Furthermore, our work could be extended to many other functional encryption. In Particular, we show how to instantiate our framework to inner product encryption and key-policy functional encryption. All parameters of our constructions are shorter than those of DLIN-based constructions.     

Leakage-resilient attribute based encryption in prime-order groups via predicate encodings

Recently, leakage-resilient cryptography has become a hot research topic. It seeks to build more robust models of adversarial access to cryptographic algorithms. The main goal is to design a scheme that remains secure even when arbitrary, yet bounded, information about secret key is leaked. In this paper, we present a modular framework for designing leakage-resilient attribute-based encryption (ABE) schemes based on extended predicate encoding. We first extend the predicate encoding to the leakage-resilient predicate encoding; and then, design several leakage-resilient predicate encodings, and finally give a generic construction of leakage-resilient ABE based on the newly proposed encodings. Moreover, we can instantiate our framework in prime order bilinear groups to obtain concrete constructions, and prove their full security under the standard k-Lin assumption in the continual memory leakage model.     

Fully collusion-resistant traitor tracing scheme with shorter ciphertexts

A traitor tracing scheme allows a content distributor to detect at least one of the traitors whose secret key is used to create a pirate decoder. In building efficient traitor tracing schemes, reducing ciphertext size is a significant factor since the traitor tracing scheme must handle a larger number of users. In this paper, we present a fully collusion-resistant traitor tracing scheme where the ciphertext size is 2.8 times shorter and encryption time is 2.6 times faster, compared to the best cases of fully collusion-resistant schemes previously suggested. We can achieve these efficiency results without sacrificing other costs. Also, our scheme supports public tracing and black-box tracing. To achieve our goal, we use asymmetric bilinear maps in prime order groups, and we introduce a new cancellation technique that has the same effect as that in composite order groups.     

Certificateless signature and proxy signature schemes from bilinear pairings

Due to avoiding the inherent escrow of identity-based cryptography and yet not requiring certificates to guarantee the authenticity of public keys, certificateless public key cryptography has received a significant attention. Due to various applications of bilinear pairings in cryptography, numerous pairing-based encryption schemes, signature schemes, and other cryptographic primitives have been proposed. In this paper, a new certificateless signature scheme based on bilinear pairings is presented. The signing algorithm of the proposed scheme is very simple and does not require any pairing computation. Combining our signature scheme with certificateless public key cryptography yields a complete solution of certificateless public key system. As an application of the proposed signature scheme, a certificateless proxy signature scheme is also presented. We analyze both schemes from security point of view.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 1, pp. 95–103, January–March, 2005.     

Lattice-based completely non-malleable public-key encryption in the standard model

An encryption scheme is non-malleable if giving an encryption of a message to an adversary does not increase its chances of producing an encryption of a related message (under a given public key). Fischlin introduced a stronger notion, known as complete non-malleability, which requires attackers to have negligible advantage, even if they are allowed to transform the public key under which the related message is encrypted. Ventre and Visconti later proposed a comparison-based definition of this security notion, which is more in line with the well-studied definitions proposed by Bellare et al. The authors also provide additional feasibility results by proposing two constructions of completely non-malleable schemes, one in the common reference string model using non-interactive zero-knowledge proofs, and another using interactive encryption schemes. Therefore, the only previously known completely non-malleable (and non-interactive) scheme in the standard model, is quite inefficient as it relies on generic NIZK approach. They left the existence of efficient schemes in the common reference string model as an open problem. Recently, two efficient public-key encryption schemes have been proposed by Libert and Yung, and Barbosa and Farshim, both of them are based on pairing identity-based encryption. At ACISP 2011, Sepahi et al. proposed a method to achieve completely non-malleable encryption in the public-key setting using lattices but there is no security proof for the proposed scheme. In this paper we review the mentioned scheme and provide its security proof in the standard model. Our study shows that Sepahi’s scheme will remain secure even for post-quantum world since there are currently no known quantum algorithms for solving lattice problems that perform significantly better than the best known classical (i.e., non-quantum) algorithms.     

Efficient public key encryption with smallest ciphertext expansion from factoring

For public key encryption schemes, adaptive chosen ciphertext security is a widely accepted security notion since it captures a wide range of attacks. SAEP and SAEP+ are asymmetric encryption schemes which were proven to achieve semantic security against adaptive chosen ciphertext attacks. However, the bandwidth for message is essentially worse, that is the ciphertext expansion (the length difference between the ciphertext and the plaintext) is too large. In most of the mobile networks and bandwidth constrained communication systems, it is necessary to securely send as many messages as possible. In this article, we propose two chosen-ciphertext secure asymmetric encryption schemes. The first scheme is a generic asymmetric encryption padding scheme based on trapdoor permutations. The second one is its application to the Rabin-Williams function which has a very fast encryption algorithm. These asymmetric encryption schemes both achieve the optimal bandwidth w.r.t. the ciphertext expansion, namely with the smallest ciphertext expansion. Further, tight security reductions are shown to prove the security of these encryption schemes.     

Polynomial-time key recovery attack on the Faure–Loidreau scheme based on Gabidulin codes

Encryption schemes based on the rank metric lead to small public key sizes of order of few thousands bytes which represents a very attractive feature compared to Hamming metric-based encryption schemes where public key sizes are of order of hundreds of thousands bytes even with additional structures like the cyclicity. The main tool for building public key encryption schemes in rank metric is the McEliece encryption setting used with the family of Gabidulin codes. Since the original scheme proposed in 1991 by Gabidulin, Paramonov and Tretjakov, many systems have been proposed based on different masking techniques for Gabidulin codes. Nevertheless, over the years most of these systems were attacked essentially by the use of an attack proposed by Overbeck. In 2005 Faure and Loidreau designed a rank-metric encryption scheme which was not in the McEliece setting. The scheme is very efficient, with small public keys of size a few kiloBytes and with security closely related to the linearized polynomial reconstruction problem which corresponds to the decoding problem of Gabidulin codes. The structure of the scheme differs considerably from the classical McEliece setting and until our work, the scheme had never been attacked. We show in this article that for a range of parameters, this scheme is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck’s attack on an appropriate public code. As an example we break in a few seconds parameters with 80-bit security claim. Our work also shows that some parameters are not affected by our attack but at the cost of a lost of efficiency for the underlying schemes.     

Image encryption using chaotic coupled map lattices with time-varying delays

In this paper, a novel image encryption scheme using coupled map lattices (CML) with time delay is proposed. By employing discretized tent map to shuffle the positions of image pixels and then using delayed coupled map lattices (DCML) to confuse the relationship between the plain-image and the cipher-image, image encryption algorithms with permutation-diffusion structure are introduced in detail. In the process of generating keystream, the time-varying delay is also embedded in our proposed scheme to enhance the security. Theoretical analysis and computer experiments confirm that the new algorithm possesses high security for practical image encryption.     

Reflections on the security proofs of Boneh-Franklin identity-based encryption scheme

In this paper, we first review the existing proofs of the Boneh-Franklin identity-based encryption scheme (BF-IBE for short), and show how to admit a new proof by slightly modifying the specifications of the hash functions of the original BF-IBE. Compared with prior proofs, our new proof provides a tighter security reduction and minimizes the use of random oracles, thus indicates BF-IBE has better provable security with our new choices of hash functions. The techniques developed in our proof can also be applied to improving security analysis of some other IBE schemes. As an independent technical contribution, we also give a rigorous proof of the Fujisaki-Okamoto (FO) transformation in the case of CPA-to-CCA, which demonstrates the efficiency of the FO-transformation (CPA-to-CCA), in terms of the tightness of security reduction, has long been underestimated. This result can remarkably benefit the security proofs of encryption schemes using the FO-transformation for CPA-to-CCA enhancement.     

Novel generic construction of leakage-resilient PKE scheme with CCA security

Leakage of private state information (e.g. the secret keys) through various leakage attacks (e.g. side channel attacks, cold-boot attacks, etc) has become a serious threat to the security of computer systems in practice. Nowadays, it has become a common requirement that cryptographic schemes should withstand the leakage attacks. Although some research progresses have been made towards designing leakage-resilient cryptographic schemes, there are still some unsolved issues. For example, the computational costs of the existing generic construction of leakage-resilient public-key encryption (PKE) schemes is generally very high. One of the main reasons is that the underlying building blocks, e.g. non-interactive zero-knowledge argument, one-time lossy filter or one-time signature, are computationally expensive. Moreover, the above constructions of PKE with leakage resilience normally require the upper bound of leakage to be fixed. However, in many real-world applications, this requirement cannot provide sufficient protection against various leakage attacks. In order to mitigate the above problems, this paper presents a generic method of designing leakage amplified PKE schemes with leakage resilience and chosen-ciphertext attacks (CCA) security. Firstly, we define a new cryptography primitive, called identity-based hash proof system with two encapsulated key (T-IB-HPS). Then, two generic constructions of leakage-resilient PKE schemes are proposed using T-IB-HPS and message authentication code (MAC). The CCA security of our proposed constructions can be reduced to the security of the underlying T-IB-HPS and MAC. In the proposed generic method, the leakage parameter has an arbitrary length that can be flexibly adjusted according to the specific leakage requirements. In order to demonstrate the practicability of our generic method, two instantiations of T-IB-HPS are introduced. The first instantiation is proved based on the truncated augmented bilinear Diffie–Hellman exponent assumption, and the second instantiation is proved based on the related security assumptions over the composite order bilinear group.

     

A new secured transmission scheme based on chaotic synchronization via smooth adaptive unknown-input observers

We present a new scheme for the secured transmission of information based on master–slave synchronization of chaotic systems, using unknown-input observers. Our approach improves upon state-of-the-art schemes by being compatible with information of relatively large amplitude while improving security against intruders through an intricate encryption system. In addition, our approach is robust to channel noise. The main idea is to separate the encryption and synchronization operations by using two cascaded chaotic systems in the transmitter. Technically, the scheme is based on smooth adaptive unknown-input observers; these have the advantage to estimate the (master) states and to reconstruct the unknown inputs simultaneously. The performance of the communication system is illustrated in numerical simulation.     

The relation and transformation between hierarchical inner product encryption and spatial encryption

Hierarchical inner product encryption (HIPE) and spatial encryption (SE) are two important classes of functional encryption that have numerous applications. Although HIPE and SE both involve some notion of linear algebra, the former works in vectors while the latter is based on (affine) spaces. Moreover, they currently possess different properties in terms of security, anonymity (payload/attribute-hiding) and ciphertext sizes, for example. In this paper, we formally study the relation between HIPE and SE. In our work, we discover some interesting and novel property-preserving transformation techniques that enable generic construction of an SE scheme from an HIPE scheme, and vice versa.     

Efficient discrete logarithm based multi-signature scheme in the plain public key model

In this paper, we provide a new multi-signature scheme that is proven secure in the plain public key model. Our scheme is practical and efficient according to computational costs, signature size and security assumptions. At first, our scheme matches the single ordinary discrete logarithm based signature scheme in terms of signing time, verification time and signature size. Secondly, our scheme requires only two rounds of interactions and each signer needs nothing more than a certified public key to produce the signature, meaning that our scheme is compatible with existing PKIs. Thirdly, our scheme has been proven secure in the random oracle model under standard discrete logarithm (DL) assumption. It outperforms a newly proposed multi-signature scheme by Bagherzandi, Cheon and Jarecki (BCJ scheme) in terms of both computational costs and signature size.     

Paillier-based publicly verifiable (non-interactive) secret sharing

A verifiable secret sharing is a secret sharing scheme with an untrusted dealer that allows participants to verify validity of their own shares. A publicly verifiable secret sharing (PVSS) scheme is a verifiable secret sharing scheme that allows a third party to verify correctness of the distributed shares. We propose an efficient non-interactive PVSS scheme using Paillier additively homomorphic encryption system, and analyze its security in a model that we define in line with the classic semantic-security definition and offering stronger security compared to the previous models. We reduce security of our PVSS scheme to the well studied decisional composite residuosity assumption in this model.     

Spatial encryption supporting non-monotone access structure

We investigate a variant of spatial encryption (SE) we call ciphertext-policy SE (CP-SE), which combines the properties of SE and those from ciphertext-policy attribute-based encryption (CP-ABE). The resulting primitive supports non-monotone access structure. In CP-SE, the decryptability of a ciphertext depends on whether or not the required attribute vectors are in the same affine space that also corresponds to the decryption key. This gives rise to many new applications, for example, SE supporting negation, hierarchical ABE and forward-secure ABE. In this paper, we present techniques for generic construction of CP-SE from ciphertext-policy inner product encryption (CP-IPE). Our techniques are property-preserving in the sense that if the CP-IPE scheme from which we derive our CP-SE scheme is fully secure, for example, then so is the resulting CP-SE scheme. Moreover, interestingly, we show that it is possible to perform transformation of the opposite direction, that is, how to construct a CP-IPE scheme given a CP-SE scheme.     

Provable certificateless generalized signcryption scheme

Generalized signcryption can adaptively work as an encryption scheme, a signature scheme or a signcryption scheme with only one algorithm. It is very suitable for storage-constrained environments. In this paper, we introduce a formal security model for certificateless generalized signcryption schemes secure against the malicious-but-passive key generation center attacks and propose a novel scheme. Our scheme is proved to be IND-CCA2 secure under the GBDH assumption and CDH assumption and existentially unforgeable under the GDH’ assumption and CDH assumption in random oracle model. Furthermore, performance analysis shows the proposed scheme is efficient and practical.     

Tightly CCA-secure identity-based encryption with ciphertext pseudorandomness

Affine message authentication code (MAC) and delegatable affine MAC turn out to be useful tools for constructing identity-based encryption (IBE) and hierarchical IBE (HIBE), as shown in Blazy, Kiltz and Pan’s (BKP) creative work in CRYPTO (2014). An important result obtained by BKP is IBE of tight PR-ID-CPA security, i.e., tight IND-ID-CPA security together with ciphertext pseudorandomness (PR). However, the problem of designing tightly PR-ID-CCA2 secure IBE remains open. We note that the CHK transformation does not preserve ciphertext pseudorandomness when converting IND-ID-CPA secure 2-level HIBE to IND-ID-CCA2 secure IBE. In this paper, we solve this problem with a new approach. We introduce a new concept called De-randomized delegatable affine MAC and define for it weak APR-CMA security. We construct such a MAC with a tight security reduction to the Matrix DDH assumption, which includes the k-Linear and DDH assumptions. We present a paradigm for constructing PR-ID-CCA2 secure IBE, which enjoys both ciphertext pseudorandomness and IND-ID-CCA2 security, from De-randomized delegatable affine MAC and Chameleon hashing. The security reduction is tightness preserving. It provides another approach to IND-ID-CCA2 security besides the CHK transformation. By instantiating the paradigm with our specific De-randomized delegatable affine MAC, we obtain the first IBE of tight PR-ID-CCA2 security from the Matrix DDH assumption over pairing groups of prime order. Our IBE also serves as the first tightly IND-ID-CCA2 secure IBE with anonymous recipient (ANON-ID-CCA2) from the Matrix DDH assumption. Our IBE further implies the first tightly IND-ID-CCA2 secure extractable IBE based on the Matrix DDH assumption. The latter can be used to get IBE of simulation-based selective opening CCA2 (SIM-SO-CCA2) security (due to Lai et al. in EUROCRYPT, 2014). The tight security of our IBE leads to a tighter reduction of the SIM-SO-CCA2 security.     

Group homomorphic encryption: characterizations, impossibility results, and applications

We give a complete characterization both in terms of security and design of all currently existing group homomorphic encryption schemes, i.e., existing encryption schemes with a group homomorphic decryption function such as ElGamal and Paillier. To this end, we formalize and identify the basic underlying structure of all existing schemes and say that such schemes are of shift-type. Then, we construct an abstract scheme that represents all shift-type schemes (i.e., every scheme occurs as an instantiation of the abstract scheme) and prove its IND-CCA1 (resp. IND-CPA) security equivalent to the hardness of an abstract problem called Splitting Oracle-Assisted Subgroup Membership Problem (SOAP) (resp. Subgroup Membership Problem, SMP). Roughly, SOAP asks for solving an SMP instance, i.e., for deciding whether a given ciphertext is an encryption of the neutral element of the ciphertext group, while allowing access to a certain oracle beforehand. Our results allow for contributing to a variety of open problems such as the IND-CCA1 security of Paillier’s scheme, or the use of linear codes in group homomorphic encryption. Furthermore, we design a new cryptosystem which provides features that are unique up to now: Its IND-CPA security is based on the k-linear problem introduced by Shacham, and Hofheinz and Kiltz, while its IND-CCA1 security is based on a new k-problem that we prove to have the same progressive property, namely that if the k-instance is easy in the generic group model, the (k+1)-instance is still hard.