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

Abstract

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.

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

BibTeX

@misc{cryptoeprint:2016/567,
      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{https://eprint.iacr.org/2016/567}},
      url = {https://eprint.iacr.org/2016/567}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.