Cryptology ePrint Archive: Report 2016/567

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

Takashi Yamakawa; Shota Yamada; Goichiro Hanaoka; 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.

Category / Keywords: factoring assumption, semi-smooth RSA subgroup modulus, lossy trapdoor function, chosen ciphertext security

Original Publication (with major differences): IACR-CRYPTO-2016

Date: received 3 Jun 2016, last revised 6 Sep 2016

Contact author: yamakawa at it k u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Version: 20160907:041826 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]