In CCS'04, Diament etc al. presented special kind of public key encryption called Dual Receiver Encryption (DRE).In DRE, sender encrypts the plaintext using public keys of two independent receivers.Both independent receivers can decrypt the ciphertext into the same plaintext using their own private keys.This new cryptography primitive has applications in construction of complete nonmalleability and plaintext-awareness public key encryption, for a secure management of data that is to be disseminated to distributed processors, for ubiquitous and mobile computing applications.Daode Zhang et.al. constructed lattice-based IB-DRE scheme which is secure against stronger security notion i.e. adaptive-ID.We present hierarchical identity based dual encryption (HIB-DRE) scheme under LWE assumption.To the best of our knowledge, this gives the first provably secure HIB-DRE scheme in the lattice based setting.Independent work by Naccache[1] and Chatterjee -Sarkar[2] presented a variant of Waters's identity based encryption scheme to reduce Public Parameters.They have considered an identity of l-bits as l chunks where size of each chunk is l/l .This reduces the Public Parameter (PP) size from l to l n × m matrices.This idea was named as blocking technique [3].We have used blocking technique to reduce the size of PP.Daode Zhang et.al.[4] presented adaptive secure IB-DRE scheme.This scheme[4] contains l + 1, n × m matrices as PPs, where l denotes the number of the bits in identity.Using blocking technique we have reduced the size of PP by around factor β .Because of this the size of prime number q in field Z q is increased by 2 β which results in increase in computation cost.We have shown that compared to Daode Zhang et.al.scheme the size of the PP can be decreased approximately by 80% and the time complexity is increased by only 1.40% for a suitably chosen β .
In CCS'04, Diament etc al. presented special kind of public key encryption called Dual Receiver Encryption (DRE).In DRE, sender encrypts the plaintext using public keys of two independent receivers.Both independent receivers can decrypt the ciphertext into the same plaintext using their own private keys.This new cryptography primitive has applications in construction of complete nonmalleability and plaintext-awareness public key encryption, for a secure management of data that is to be disseminated to distributed processors, for ubiquitous and mobile computing applications.Daode Zhang et.al. constructed lattice-based IB-DRE scheme which is secure against stronger security notion i.e. adaptive-ID.We present hierarchical identity based dual encryption (HIB-DRE) scheme under LWE assumption.To the best of our knowledge, this gives the first provably secure HIB-DRE scheme in the lattice based setting.Independent work by Naccache[1] and Chatterjee -Sarkar[2] presented a variant of Waters's identity based encryption scheme to reduce Public Parameters.They have considered an identity of l-bits as l chunks where size of each chunk is l/l .This reduces the Public Parameter (PP) size from l to l n × m matrices.This idea was named as blocking technique [3].We have used blocking technique to reduce the size of PP.Daode Zhang et.al.[4] presented adaptive secure IB-DRE scheme.This scheme[4] contains l + 1, n × m matrices as PPs, where l denotes the number of the bits in identity.Using blocking technique we have reduced the size of PP by around factor β .Because of this the size of prime number q in field Z q is increased by 2 β which results in increase in computation cost.We have shown that compared to Daode Zhang et.al.scheme the size of the PP can be decreased approximately by 80% and the time complexity is increased by only 1.40% for a suitably chosen β .
Dual receiver encryption (DRE), being originally conceived at CCS 2004 as a proof technique, enables a ciphertext to be decrypted to the same plaintext by two different but dual receivers and becomes popular recently due to itself useful application potentials such secure outsourcing, trusted third party supervising, client puzzling, etc. Identity-based DRE (IB-DRE) further combines the bilateral advantages/facilities of DRE and identity-based encryption (IBE). Most previous constructions of IB-DRE are based on bilinear pairings, and thus suffers from known quantum algorithmic attacks. It is interesting to build IB-DRE schemes based on the well-known post quantum platforms, such as lattices. At ACISP 2018, Zhang et al. gave the first lattice-based construction of IB-DRE, and the main part of the public parameter in this scheme consists of 2 n + 2 matrices where n is the bit-length of arbitrary identity. In this paper, by introducing an injective map and a homomorphic computation technique due to Yamada at EUROCRYPT 2016, we propose another lattice-based construction of IB-DRE in an even efficient manner: The main part of the public parameters consists only of 2 p n 1 p + 2 matrices of the same dimensions, where p ( ≥ 2 ) is a flexible constant. The larger the p and n, the more observable of our proposal. Typically, when p = 2 and n = 284 according to the suggestion given by Peikert et al., the size of public parameters in our proposal is reduced to merely 12% of Zhang et al.’s method. In addition, to lighten the pressure of key generation center, we extend our lattice-based IB-DRE scheme to hierarchical scenario. Finally, both the IB-DRE scheme and the HIB-DRE scheme are proved to be indistinguishable against adaptively chosen identity and plaintext attacks (IND-ID-CPA).
Dual receiver encryption (DRE) is an important cryptographic primitive introduced by Diament et al. at CCS’04, which allows two independent receivers to decrypt a same ciphertext to obtain the same plaintext. This primitive is quite useful in designing combined public key cryptosystems and denial of service attack-resilient protocols. In this paper, we obtain some results as follows. Using weak lattice-based programmable hash functions (wLPHF) with high min-entropy (Crypto’16), we give a generic IND-CCA secure DRE construction in the standard model. Furthermore, we get a concrete DRE scheme by instantiating a concrete wLPHF with high min-entropy. For DRE notion in the identity-based setting, identity-based DRE (IB-DRE), basing on lattice-based programmable hash functions (LPHF) with high min-entropy, we give a framework of IND-ID-CPA secure IB-DRE construction in the standard model. When instantiating with concrete LPHFs with high min-entropy, we obtain five concrete IB-DRE schemes.
Using lattice basis delegation in a fixed dimension, we propose an efficient lattice-based hierarchical identity based encryption (HIBE) scheme in the standard model whose public key size is only ( dm 2 + mn ) log q bits and whose message-ciphertext expansion factor is only log q , where d is the maximum hierarchical depth and ( n , m , q ) are public parameters. In our construction, a novel public key assignment rule is used to averagely assign one random and public matrix to two identity bits, which implies that d random public matrices are enough to build the proposed HIBE scheme in the standard model, compared with the case in which 2 d such public matrices are needed in the scheme proposed at Crypto 2010 whose public key size is (2 dm 2 + mn + m ) log q . To reduce the message-ciphertext expansion factor of the proposed scheme to log q , the encryption algorithm of this scheme is built based on Gentry’s encryption scheme, by which m 2 bits of plaintext are encrypted into m 2 log q bits of ciphertext by a one time encryption operation. Hence, the presented scheme has some advantages with respect to not only the public key size but also the message-ciphertext expansion factor. Based on the hardness of the learning with errors problem, we demonstrate that the scheme is secure under selective identity and chosen plaintext attacks.
Identity-based encryption (IBE), and its hierarchical extension (HIBE), are interesting cryptographic primitives that aim at the implicit authentication on the users' public keys by using users' identities directly. During the past several decades, numerous elegant pairing-based (H)IBE schemes were proposed. However, most pairing-related security assumptions suffer from known quantum algorithmic attacks. Therefore, the construction of lattice-based (H)IBE became one of the hot directions in recent years. In the setting of most existing lattice-based (H)IBE schemes, each bit of a user's identity is always associated with a parameter matrix. This always leads to drastic but unfavorable increases in the sizes of the system public parameters. To overcome this issue, we propose a flexible trade-off mechanism between the size of the public parameters and the involved computational cost using the blocking technique. More specifically, we divide an identity into l' segments and associate each segment with a matrix, while increasing the lattice modulo slightly for maintaining the same security level. As a result, for the setting of 160-bit identities, we show that the size of the public parameters can be reduced by almost 89.7% (resp. 93.8%) while increasing the computational cost by merely 5.2% (resp. 12.25%) when l' is a set of 16 (resp. 8). Finally, our IBE scheme is extended to an HIBE scheme, and both of them are proved to achieve the indistinguishability of ciphertexts against adaptively chosen identity and chosen plaintext attack (IND-ID-CPA) in the standard model, assuming that the well-known ring learning with error (RLWE) problem over the involved ideal lattices is intractable, even in the post-quantum era.
The invention of public-key cryptography (PKC) by Diffie and Hellman in 1976 is one of two milestones marking the beginning of modern cryptography. The security of a PKC system requires that it should be infeasible to compute the private key from a given public key, which in turn is typically guaranteed by the difficulty in solving some cryptographic-friendly mathematical problems. Among those problems, the integer factorization and discrete logarithm problems play pivotal roles in the development of public-key cryptography. In particular, the assumption that there is no polynomial time (classical) algorithm that solves the above two problems constitutes the basis for the security of almost all currently used public-key cryptosystems, such as RSA and ElGamal. However, Shor [1] found an efficient quantum solving algorithm for the integer factorization and discrete logarithm problems in 1994, which would destroy the security basis for most real deployed PKC systems if large-scale quantum computers become available. The rapid development of quantum technology in recent years suggests that we are getting closer to the quantum crisis of current PKC systems. As a response to the quantum crisis, the research community has made many efforts to post-quantum cryptography (PQC) that are believed to resist quantum computer attacks. Lattice-based cryptography is one of the main directions in this area, and has become the most promising PQC candidate for standardization. The research of lattice-based cryptography dates back to the seminal work of Ajtai [2], which first based the security of cryptographic primitives on the difficulty of solving some lattice problems such as the approximate shortest vector problem and the closest vector problem. After more than two decades of development, lattice-based cryptography has gained substantial progress. In theory, we have witnessed the construction of many powerful cryptographic primitives that were not known before. In practice, the public key size of lattice-based cryptosystems has been significantly reduced from several gigabytes to a few kilobytes. For current applications and standardization, key exchanges, public-key encryptions (PKEs) and signatures are the most desired lattice-based cryptosystems, where the first two are often used to ensure information secrecy, while the last provides information authentication. Note that public-key encryptions are equivalent to two-round key exchanges, also known as the key encapsulation mechanism (KEM). In the following, we focus on lattice-based PKEs/KEMs. The design principle of lattice-based PKEs/KEMs follows two approaches: a trapdoor one-way function and an approximate commutative one-way function. In the first approach, a trapdoor one-way function f and its trapdoor f−1 are generated as the public key and private key. A plaintext m is encrypted as c = f(m), and the ciphertext is decrypted as m = f−1(c). The NTRU scheme and its variants follow such an approach. In the second approach, an approximate commutative function fs and a random input a are generated, the public key is (a, b = fs(a)) and the private key is s. A plaintext m is encrypted as c1 = gr(a), c2 = gr(b) + E(m), where r is a random element, g is an approximate commutative one-way function and E is the encoding of an error-correction code. The ciphertext (c1, c2) is decrypted as m = D(c2 − fs(c1)), where D is the decoding of an error-correction code. The correctness of decryption is guaranteed by the approximate commutative property (gr(b) = gr(fs(a)) ≈ fs(gr(a)) = fs(c1)) and the error-correction code. Learning with errors (LWE) problem-based PKE/KEM schemes and their variants follow such an approach. The standardization of PQC has received substantial support from national funding agencies, such as the European Union projects PQCrypto and SAFEcrypto. The USA National Institute of Standard and Technology (NIST) started the post-quantum standardization project in 2012, organized a worldwide ‘competition’ in 2016 and plans to deliver draft standards before 2024. After two rounds of evaluation, seven schemes were accepted as the round-three candidates on 22 July 2020, of which five are lattice-based schemes. In 2017, the International organization for standardization started a study project of post-quantum cryptography named SD8. Most LWE-based PKE schemes such as Kyber and LAC follow the Lindner-Peikert framework [3] up to the choices of ring structure, noise distribution and parameters. As the size of noise in lattice-based PKEs/EKMs is typically larger than the lower bits of the ciphertext, many schemes often artificially drop a few lower bits to optimize the practical performance without significantly increasing the final decryption noise. Kyber [4] is one of the most promising PKE/KEM candidates in the NIST PQC standardization, whose security is provably based on the difficulty of so-called module LWE (MLWE) problems. The use of MLWE allowed Kyber to obtain additional flexibility and security advantages, while keeping the same efficiency as those based on the ring-LWE problems. The strategy of dropping some lower bits is used to compress both the public-key and ciphertext sizes. For a targeted 128-bit quantum security, the public-key and ciphertext sizes of Kyber is around a single kilobyte. LAC [5] uses several techniques to reduce the modulus as small as possible: it uses a byte-level modulus, embeds powerful error-correcting codes to maximize the noise-modulus rate, provides a different style of modulus to avoid potential attacks for special polynomial ring structures and optimizes the polynomial multiplication algorithm of the bit-level secret and noise. Based on these techniques, LAC reduces the public key to 544–1056 bytes and the ciphertext to 664–1464 bytes. Meanwhile, it achieves similar computational performance compared with NTT technique schemes. By observing the asymmetries in lattice-based cryptosystems, Zhang and Yu et al. [6] proposed asymmetric MLWE and asymmetric MSIS problems, which yield further size-optimized KEMs and signature schemes to those from standard counterparts. Compared to the seven NIST round-three candidates at Category III security, their KEM scheme has parameters (public key + ciphertext size) smaller than Classic McEliece, CRYSTALS-Kyber, NTRU and Saber; their signature scheme has parameters (public key + signature size) smaller than CRYSTALS-Dilithium and Rainbow, but slightly larger than FALCON, where CRYSTALS-Kyber, NTRU, Saber, CRYSTALS-Dilithium and FALCON are lattice-based schemes. One important application of lattice-based PKEs/KEMs is to build authenticated key exchange (AKE), which could provide additional authentication to the established session key. There are several generic ways to construct AKE from lattice-based PKEs/KEMs. In the PKE setting, Xue and Lu et al. [7] proposed a more compact KEM-based framework via a new primitive named ‘2-key KEM’, which shares some item between different ciphertexts. In the only password setting, Zhang and Yu [8] presented a two-round PAKE framework from the splittable-PKEs that can be instantiated from lattices. The only known AKE that does not rely on lattice-based PKEs/KEMs was given in Ref. [9], which has two-round messages and provides implicit authentication. This work was supported by the National Natural Science Foundation of China (6197239 to X.L.; 62022018 and 61932019 to J.Z.) and the National Key Research and Development Program of China (2018YFB0804105 to J.Z.). Conflict of interest statement. None declared.
Threshold public key encryption is a cryptographic primitive where a secret key of an organization is distributed among special members called decryption servers (insiders) and a certain threshold number of insiders must cooperate to decrypt any ciphertext. Threshold public key encryption with an additional randomized algorithm Tsplit is called resplittable threshold public key encryption (RTPKE). Cryptographic primitive RTPKE was introduced by Hanaoka et al. [Generic construction of chosen ciphertext secure proxy re-encryption, in CT-RSA, San Francisco, CA, USA, LNCS, O. Dunkelman, ed., Springer-Verlag, Heidelberg, 2012, pp. 349–364] in a generic construction of chosen ciphertext attack secure proxy re-encryption scheme. In MIST 2013 conference Singh et al. [Lattice based efficient threshold public key encryption scheme, J. Wirel. Mob. Netw. Ubiquitous Comput. Dependable Appl. (JoWUA) 4(4) (2013), pp. 93–107] presented lattice-based RTPKE scheme based on Regev's LWE [On lattices, learning with errors, random linear codes, and cryptography, in STOC, Baltimore, MD, USA, H.N. Gabow and R. Fagin, eds., ACM, University of Wales, Cardiff, 2005, pp. 84–93] assumption. In this paper, we propose lattice-based RTPKE scheme in the identity-based setting.