MarriageTheoremのこと

_ 週末の発熱の影響でさすがにちょっとふらふらする。こういう日に限って午前中から会議というのも間が悪いものである。

_ IACR ePrint 2013/572まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文：More Efficient Cryptosystems From k-th Power Residues, Zhenfu Cao and Xiaolei Dong and Licheng Wang and Jun Shao, http://eprint.iacr.org/2013/569

At Eurocrypt 2013, Joye and Libert proposed a method for constructing public key cryptosystems (PKCs) and lossy trapdoor functions (LTDFs) from $(2^\alpha)^{th}$-power residue symbols. Their work can be viewed as non-trivial extensions of the well-known PKC scheme due to Goldwasser and Micali, and the LTDF scheme due to Freeman et al., respectively. In this paper, we will demonstrate that this kind of work can be extended \emph{more generally}: all related constructions can work for any $k^{th}$ residues if $k$ only contains small prime factors, instead of $(2^\alpha)^{th}$-power residues only. The resultant PKCs and LTDFs are more efficient than that from Joye-Libert method in terms of decryption speed with the same message length.