Public key encryption was first proposed by Diffie and Hellman [16], and widely popularised with the RSA cryptosystem [37]. Over the years, the security goals of public key encryption have been studied [17, 22], as have adversary models [30, 36], and many public key cryptosystems have been proposed and analysed. It turns out that the security of many of those cryptosystems [16, 18, 22, 29, 34, 35] are based on a common class of mathematical problems, called subgroup membership problems. Cramer and Shoup [10] designed a chosen-ciphertextsecure cryptosystem based on a general subgroup membership problem (generalising their previous work [9]), and provided two new instances. Yamamura and Saito [41] defined a general subgroup membership problem, catalogued several known subgroup membership problems, and designed a private information retrieval system based on a subgroup membership problem. Nieto, Boyd and Dawson [31] designed a cryptosystem based on essentially a symmetric subgroup membership problem (see Section 4.4 and Section 6.1). Chapter 2 and 3 contain certain preliminary discussions necessary for the later work. In Chapter 4, we discuss subgroup membership problems, both abstractly and concrete families. For all of the concrete examples, there is a related problem called the splitting problem. We discuss various elementary reductions, both abstract and for concrete families. In cryptographic applications, a third related problem, called the subgroup discrete logarithm problem, is also interesting, and we discuss this in some detail. We also discuss a variant of the subgroup membership problem where there are two subgroups that are simultaneously hard to distinguish. We prove a useful reduction (Theorem 4.11) for this case. The technique used in the proof is reused throughout the thesis. In Chapter 5, we discuss two homomorphic cryptosystems, based on trapdoor splitting problems. This gives us a uniform description of a number of homomorphic cryptosystems, and allows us to apply the theory and results of Chapter 4 to the security of those cryptosystems. Using the technique of Theorem 4.11, we develop a homomorphic cryptosystem that is not based on a trapdoor problem. This gives us a fairly efficient cryptosystem, with potentially useful properties. We also discuss the security of a homomorphic cryptosystem under a nonstandard assumption. While these results are very weak, they are stronger than results obtained in the generic model. In Chapter 6, we develop two key encapsulation methods. The first can be proven secure against passive attacks, using the same technique as in the proof of Theorem 4.11. The second method can be proven secure against active attacks in the random oracle model, but to do this, we need a certain non-standard assumption. Finally, in Chapter 7 we discuss a small extension to the framework developed by Cramer and Shoup [10], again by essentially reusing the technique used to prove Theorem 4.11. This gives us a cryptosystem that is secure against chosen ciphertext attacks, without recourse to the random oracle model or nonstandard assumptions. The cryptosystem is quite practical, and performs quite well compared to other variants of the Cramer-Shoup cryptosystem.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:ntnu-128 |
| Date | January 2004 |
| Creators | Gjøsteen, Kristian |
| Publisher | Norges teknisk-naturvitenskapelige universitet, Fakultet for informasjonsteknologi, matematikk og elektroteknikk, Fakultet for informasjonsteknologi, matematikk og elektroteknikk |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Doctoral thesis, monograph, info:eu-repo/semantics/doctoralThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Doktoravhandlinger ved NTNU, 1503-8181 ; 2004:69 |
Page generated in 0.0092 seconds