Factoring-based cryptography:
The Hofheinz-Kiltz-Shoup cryptosystem
Johannes Zollmann (University of Bonn)
Thursday, 14 November 2013, 15:00, B-IT 1.25
Security is a crucial property for any cryptographic system. The scientific approach of modern cryptography relates the security property to the difficulty of some well-studied mathematical problem. One of the most famous of such problems is factoring composite numbers. Hofheinz, Kiltz, and Shoup (2011) present a system whose security is provably equivalent to the factoring problem. It is referred to as the Hofheinz-Kiltz-Shoup cryptosystem (HKS). However, the HKS is not a public key encryption scheme for arbitrary data, but rather a key encapsulation mechanism (KEM) for transmitting randomly generated keys. To actually encrypt and decrypt data, a KEM has to be used in combination with a data encapsulation mechanism (DEM). The formalization of KEM/DEM is due to Cramer and Shoup (2004).
We discuss how to get rid of the two common assumptions underlying the HKS construction: the infinitude of Sophie Germain primes and the existence of a second-preimage resistant hash function. For this, we apply the notion of ?safe prime? suggested by von zur Gathen and Shparlinski (2013) to the HKS, making the key generation algorithm of the HKS unconditionally efficient.
Furthermore, we provide three different variations of the HKS, all of them circumventing the hash function requirement of the original HKS. By this, the additional assumption of a second-preimage resistant hash function can be dropped, and the system gets conceptually simpler. With the third variant, we finally present a complete public key encryption scheme secure solely under the factoring assumption and liberated from the KEM/DEM paradigm.