This thesis considers cryptographic systems that use public key encryption (PKE) as a building block in a larger system. We call these cryptosystems and develop a framework for describing such protocols that provides a clear way of describing the role of PKE in the PKE-hybrid protocol. By clarifying and generalizing the role of PKE in such protocols, we are able to state and prove a powerful lemma for proving the security of PK-hybrid protocols. We then show how this lemma can be used in a proof of security for the standard technique of hybrid encryption, substantially simplifying earlier proofs by Cramer and Shoup and by Abe, et al. In addressing these protocols we make improvements to a previously published protocol for Generalized Non-Interactive Oblivious Transfer (GNIOT) due to Gunupudi and Tate, and use our new security framework to correct a subtle error in the original security proof provided for GNIOT.
This thesis considers cryptographic systems that use public key encryption (PKE) as a building block in a larger system. We call these cryptosystems and develop a framework for describing such protocols that provides a clear way of describing the role of PKE in the PKE-hybrid protocol. By clarifying and generalizing the role of PKE in such protocols, we are able to state and prove a powerful lemma for proving the security of PK-hybrid protocols. We then show how this lemma can be used in a proof of security for the standard technique of hybrid encryption, substantially simplifying earlier proofs by Cramer and Shoup and by Abe, et al. In addressing these protocols we make improvements to a previously published protocol for Generalized Non-Interactive Oblivious Transfer (GNIOT) due to Gunupudi and Tate, and use our new security framework to correct a subtle error in the original security proof provided for GNIOT.
Over the past four decades, computational power and algorithmic strategies have advanced tremendously resulting in an enormous increase in the key sizes required for secure cryptosystems such as RSA. At the same time, the electronic devices have grown smaller and portable requiring algorithms running on them to be optimized in size and efficiency while providing security, at least, equivalent to that provided on a typical desktop computer. As a result, the industry is moving towards newer cryptosystems such as ECC and NTRU that are well suited for resource constrained environments. While, ECC claims to provide security equivalent to that of RSA for a fraction of key size, NTRU is inherently suited for embedded systems technology. However, implementation of new cryptosystems requires the development of protocols analogous to those developed using older cryptosystems. In this thesis, we fulfill a part of this requirement by providing protocols for Oblivious Transfer using ECC and NTRU. Oblivious Transfer, in turn, has applications in simultaneous contract signing, digital certified mail, simultaneous exchange of secrets, secure multiparty computations, private information retrieval, etc. Furthermore, we introduce the idea of basing Oblivious Transfer on public-key exchange protocols. The presentation in the thesis uses Diffie-Hellman Key Exchange, but the scheme is generalizable to any cryptosystem that has a public-key exchange strategy. In fact, our proposal may especially be suited for Quantum Cryptography where the security of key exchange protocols has been proven.
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.
We propose a novel paradigm for defining security of cryptographic protocols, called universally composable security. The salient property of universally composable definitions of security is that they guarantee security even when a secure protocol is composed of an arbitrary set of protocols, or more generally when the protocol is used as a component of an arbitrary system. This is an essential property for maintaining security of cryptographic protocols in complex and unpredictable environments such as the Internet. In particular, universally composable definitions guarantee security even when an unbounded number of protocol instances are executed concurrently in an adversarially controlled manner, they guarantee non-malleability with respect to arbitrary protocols, and more. We show how to formulate universally composable definitions of security for practically any cryptographic task. Furthermore, we demonstrate that practically any such definition can be realized using known techniques, as long as only a minority of the participants are corrupted. We then proceed to formulate universally composable definitions of a wide array of cryptographic tasks, including authenticated and secure communication, key-exchange, public-key encryption, signature, commitment, oblivious transfer, zero knowledge and more. We also make initial steps towards studying the realizability of the proposed definitions in various settings.
A hybrid encryption scheme is a public-key encryption system that consists of a public-key part called the key encapsulation mechanism (KEM), and a (symmetric) secret-key part called data encapsulation mechanism (DEM): the public-key part is used to generate a shared secret key between two parties, and the symmetric key part is used to encrypt the message using the generated key. Hybrid encryption schemes are widely used for secure communication over the Internet. In this paper, we initiate the study of hybrid encryption in preprocessing model which assumes access to initial correlated variables by all parties (including the eavesdropper). We define information-theoretic KEM (iKEM) that, together with a (computationally) secure DEM, results in a hybrid encryption scheme in preprocessing model. We define the security of each building block, and prove a composition theorem that guarantees (computational) qe-chosen plaintext (CPA) security of the hybrid encryption system if the iKEM and the DEM satisfy qe-chosen encapculation attack and one-time security, respectively. We show that iKEM can be realized by a one-way SKA (OW-SKA) protocol with a revised security definition. Using an OW-SKA that satisfies this revised definition of security effectively allows the secret key that is generated by the OW-SKA to be used with a one-time symmetric key encryption system such as XORing a pseudorandom string with the message, and provide qe-CPA security for the hybrid encryption system.We discuss our results and directions for future work.
This dissertation includes four contributions concerning secure multiparty computation. The first contribution is a new lossy threshold encryption scheme. This is the first encryption scheme that is both a lossy and a threshold encryption scheme. The second contribution is a new oblivious transfer protocol secure against erasure-free one-sided active adaptive adversaries. The third contribution is a new two-party computation protocol for the evaluation of boolean circuits that is secure against erasure-free one-sided active adaptive adversaries. As a building block of this protocol, a new cut-and-choose oblivious transfer protocol is designed. The fourth contribution is a new multiparty computation protocol for the evaluation of arithmetic circuits that is secure against covert adversaries. Protocols that are part of the second, third and fourth contributions improve the communication complexity, the number of public key encryption operations and the number of exponentiation operations over existing protocols for the same problems that provide the same or higher levels of security.
In this paper we study the relationships among some of the most fundamental primitives and protocols in cryptography: public-key encryption (i.e. trapdoor predicates), oblivious transfer (which is equivalent to general secure multi-party computation), key agreement and trapdoor permutations. Our main results show that public-key encryption and oblivious transfer are incomparable under black-box reductions. These separations are tightly matched by our positive results where a restricted (strong) version of one primitive does imply the other primitive. We also show separations between oblivious transfer and key agreement. Finally, we conclude that neither oblivious transfer nor trapdoor predicates imply trapdoor permutations. Our techniques for showing negative results follow the oracle separations of R. Impagliazzo and S. Rudich (1989).