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.     

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.     

Chosen ciphertext secure keyed-homomorphic public-key cryptosystems

In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can “freely” perform the operation inevitably means that ciphertexts are malleable, and it is well-known that adaptive chosen ciphertext (CCA) security and the homomorphic property can never be achieved simultaneously. In this paper, we show that CCA security and the homomorphic property can be simultaneously handled in situations that the user(s) who can perform homomorphic operations on encrypted data should be controlled/limited, and propose a new concept of homomorphic public-key encryption, which we call keyed-homomorphic public-key encryption (KH-PKE). By introducing a secret key for homomorphic operations, we can control who is allowed to perform the homomorphic operation. To construct KH-PKE schemes, we introduce a new concept, transitional universal property, and present a practical KH-PKE scheme with multiplicative homomorphic operations from the decisional Diffie-Hellman (DDH) assumption. For \(\ell \)-bit security, our DDH-based KH-PKE scheme yields only \(\ell \)-bit longer ciphertext size than that of the Cramer–Shoup PKE scheme. Finally, we consider an identity-based analogue of KH-PKE, called keyed-homomorphic identity-based encryption and give its concrete construction from the Gentry IBE scheme.     

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.     

Efficient hybrid encryption from ID-based encryption

This paper deals with generic transformations from ID-based key encapsulation mechanisms (IBKEM) to hybrid public-key encryption (PKE). The best generic transformation known until now is by Boneh and Katz and requires roughly 704-bit overhead in the ciphertext. We present new generic transformations that are applicable to partitioned IBKEMs. A partitioned IBKEM is an IBKEM that provides some extra structure. Such IBKEMs are quite natural and in fact nearly all known IBKEMs have this additional property. Our first transformation yields chosen-ciphertext secure PKE schemes from selective-ID secure partitioned IBKEMs with a 256-bit overhead in ciphertext size plus one extra exponentiation in encryption/decryption. As the central tool a Chameleon Hash function is used to map the identities. We also propose other methods to remove the use of Chameleon Hash, which may be of independent technical interest. Applying our transformations to existing IBKEMs we propose a number of novel PKE schemes with different trade-offs. In some concrete instantiations the Chameleon Hash can be made “implicit” which results in improved efficiency by eliminating the additional exponentiation. Since our transformations preserve the public verifiability property of the IBE schemes it is possible to extend our results to build threshold hybrid PKE schemes. We show an analogue generic transformation in the threshold setting and present a concrete scheme which results in the most efficient threshold PKE scheme in the standard model.     

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.     

Breaking a modified substitution–diffusion image cipher based on chaotic standard and logistic maps

Recently, an image encryption scheme based on chaotic standard and logistic maps was proposed by Patidar et al. It was later reported by Rhouma et al. that an equivalent secret key can be reconstructed with only one known/chosen-plaintext and the corresponding ciphertext. Patidar et al. soon modified the original scheme and claimed that the modified scheme is secure against Rhouma et al.’s attack. In this paper, we point out that the modified scheme is still insecure against the same known/chosen-plaintext attack. In addition, some other security defects existing in both the original and the modified schemes are also reported.     

Security of message authentication codes in the presence of key-dependent messages

In recent years, the security of encryption and signature schemes in the presence of key-dependent plaintexts received attention, and progress in understanding such scenarios has been made. In this article we motivate and discuss a setting where an adversary can access tags of a message authentication code (MAC) on key-dependent message inputs, and we propose a way to formalize the security of MACs in the presence of key-dependent messages (KD?EUF). Like signature schemes, MACs have a verification algorithm, and hence the tagging algorithm must be stateful. We present a scheme MAC-ver which offers KD?EUF security and also yields a forward-secure scheme.     

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.     

A multivariate cryptosystem inspired by random linear codes

We introduce a new multivariate encryption scheme inspired by random linear codes. The construction is similar to that of UOV, one of the oldest and most trusted multivariate signature schemes, but with a parameterization nothing like that of UOV. The structure of the scheme admits many generic modifications providing an array of security and performance properties. The scheme also supports an embedding modifier which allows any efficiently invertible multivariate system to be incorporated into the scheme. The product of this methodology is the fastest secure multivariate encryption scheme targeting CCA security at the 128-bit level.     

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.     

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.     

Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem

The new signature scheme presented by the authors in [13] is the first signature scheme based on the discrete logarithm problem that gives message recovery. The purpose of this paper is to show that the message recovery feature is independent of the choice of the signature equation and that all ElGamal-type schemes have variants giving message recovery. For each of the six basic ElGamal-type signature equations five variants are presented with different properties regarding message recovery, length of commitment and strong equivalence. Moreover, the six basic signature schemes have different properties regarding security and implementation. It turns out that the scheme proposed in [13] is the only inversionless scheme whereas the message recovery variant of the DSA requires computing of inverses in both generation and verification of signatures. In general, message recovery variants can be given for ElGamal-type signature schemes over any group with large cyclic subgroup as the multiplicative group of GF(2n) or elliptic curve over a finite field.The present paper also shows how to integrate the DLP-based message recovery schemes with secret session key establishment and ElGamal encryption. In particular, it is shown that with DLP-based schemes the same functionality as with RSA can be obtained. However, the schemes are not as elegant as RSA in the sense that the signature (verification) function cannot at the same time be used as the decipherment (encipherment) function.     

ID-based cryptography using symmetric primitives

A general method for deriving an identity-based public key cryptosystem from a one-way function is described. We construct both ID-based signature schemes and ID-based encryption schemes. We use a general technique which is applied to multi-signature versions of the one-time signature scheme of Lamport and to a public key encryption scheme based on a symmetric block cipher which we present. We make use of one-way functions and block designs with properties related to cover-free families to optimise the efficiency of our schemes.      

An improved signature scheme without using one-way Hash functions

Recently, Chang et al. give a digital signature scheme, where neither one-way hash function nor message redundancy schemes are used, but Zhang et al. has shown that the scheme was forgeable, namely, any one can forge a new signature by the signer’s signature, and give two forgery attacks. To the above attacks, we give an improved signature scheme based on Chang signature scheme and analyze the security of the improved scheme.     

基于MSP秘密共享的（t，n）门限群签名方案

门限群签名是群签名中重要的—类,它是秘钥共享与群签名的有机结合．本文通过文献[5]中的MSP方案（Monotone Span Program）,提出了一种新的门限群签名方案．在本签名方案建立后,只有达到门限的群成员的联合才能生成—个有效的群签名,并且可以方便的加入或删除成员．一旦发生争议,只有群管理员才能确定签名人的身份．该方案能够抵抗合谋攻击：即群中任意一组成员合谋都无法恢复群秘钥k．本方案的安全性基于Gap Diffie-Hellman群上的计算Diffie-Hellmanl可题难解上,因此在计算上是最安全的．     

Inner-product encryption under standard assumptions

Predicate encryption is a generalized notion for public key encryption that enables one to encrypt attributes as well as a message. In this paper, we present a new inner-product encryption (IPE) scheme, as a specialized predicate encryption scheme, whose security relies on the well-known Decision Bilinear Diffie-Hellman (BDH) and Decision Linear assumptions. Our IPE scheme uses prime order groups equipped with a bilinear map and works in both symmetric and asymmetric bilinear maps. Our result is the first construction of IPE under the standard assumptions. Prior to our work, all IPE schemes known to date require non-standard assumptions to prove security, and moreover some of them use composite-order groups. To achieve our goal, we introduce a novel technique for attribute-hiding, which may be of independent interest.     

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.     

A chaotic image encryption scheme owning temp-value feedback

Many round-based chaotic image encryption algorithms employ the permutation–diffusion structure. This structure has been found insecure when the iteration round is equal to one and the secret permutation of some existing schemes can be recovered even a higher round is adopted. In this paper, we present a single round permutation–diffusion chaotic cipher for gray image, in which some temp-value feedback mechanisms are introduced to resist the known attacks. Specifically, we firstly embed the plaintext feedback technique in the permutation process to develop different permutation sequences for different plain-images and then employ plaintext/ciphertext feedback for diffusion to generate equivalent secret key dynamically. Experimental results show that the new scheme owns large key space and can resist the differential attack. It is also efficient.     

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.