Paper 2016/567

Adversary-dependent Lossy Trapdoor Function from Hardness of Factoring Semi-smooth RSA Subgroup Moduli

Takashi Yamakawa, Shota Yamada, Goichiro Hanaoka, and Noboru Kunihiro


Lossy trapdoor functions (LTDFs), proposed by Peikert and Waters (STOC'08), are known to have a number of applications in cryptography. They have been constructed based on various assumptions, which include the quadratic residuosity (QR) and decisional composite residuosity (DCR) assumptions, which are factoring-based {\it decision} assumptions. However, there is no known construction of an LTDF based on the factoring assumption or other factoring-related search assumptions. In this paper, we first define a notion of {\it adversary-dependent lossy trapdoor functions} (ad-LTDFs) that is a weaker variant of LTDFs. Then we construct an ad-LTDF based on the hardness of factorizing RSA moduli of a special form called semi-smooth RSA subgroup (SS) moduli proposed by Groth (TCC'05). Moreover, we show that ad-LTDFs can replace LTDFs in many applications. Especially, we obtain the first factoring-based deterministic encryption scheme that satisfies the security notion defined by Boldyreva et al. (CRYPTO'08) without relying on a decision assumption. Besides direct applications of ad-LTDFs, by a similar technique, we construct a chosen ciphertext secure public key encryption scheme whose ciphertext overhead is the shortest among existing schemes based on the factoring assumption w.r.t. SS moduli.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2016
factoring assumptionsemi-smooth RSA subgroup moduluslossy trapdoor functionchosen ciphertext security
Contact author(s)
yamakawa @ it k u-tokyo ac jp
2016-09-07: revised
2016-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Takashi Yamakawa and Shota Yamada and Goichiro Hanaoka and Noboru Kunihiro},
      title = {Adversary-dependent Lossy Trapdoor Function from Hardness of Factoring Semi-smooth RSA Subgroup Moduli},
      howpublished = {Cryptology ePrint Archive, Paper 2016/567},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.