SCIS 2022
2022 Symposium on
Cryptography and Information Security
Osaka, Japan & Online, Jan. 18 – 21, 2022
The Institute of Electronics,
Information and Communication Engineers

Copyright c 2022 The Institute of Electronics,
Information and Communication Engineers

Lossy Trapdoor function の幾つかの亜種について
On some variants of lossy trapdoor function
星野 文学 ∗Fumitaka Hoshino

キーワード Lossy Trapdoor function, Dual Projective Hashing, Universal Projective Hashing, Lossy Trap-

door Relation[3] C. Peikert and B. Waters, “Lossy trapdoor functions
and their applications,” SIAM J. Comput., vol.40, no.6,
pp.1803–1844, 2011. doi:10.1137/080733954.
[4] B. Hemenway and R. Ostrovsky, “Building lossy trapdoor
functions from lossy encryption,” Advances in Cryptology ASIACRYPT 2013 - 19th International Conference on theTheory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings,Part II, ed. K. Sako and P. Sarkar, Lecture Notes in Computer Science, vol.8270, pp.241–260, Springer, 2013. doi:
10.1007/978-3-642-42045-0\_13.
[5] B. Hemenway and R. Ostrovsky, “Building lossy trapdoor
functions from lossy encryption,” IACR Cryptol. ePrintArch., p.156, 2015. URL: http://eprint.iacr.org/2015/156.
[6] H. Xue, X. Lu, B. Li, and Y. Liu, “Lossy trapdoor relation and its applications to lossy encryption and adaptive trapdoor relation,” Provable Security - 8th International Conference, ProvSec 2014, Hong Kong, China, October 9-10, 2014. Proceedings, ed. S.S.M. Chow, J.K. Liu,L.C.K. Hui, and S. Yiu, Lecture Notes in Computer Science, vol.8782, pp.162–177, Springer, 2014. doi:10.1007/978-3-319-12475-9\_12.
[7] H. Xue, Y. Liu, X. Lu, and B. Li, “Lossy projective hashing and its applications,” Progress in Cryptology - INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Bangalore, India, December 6-9, 2015, Proceedings, ed. A. Biryukov and V. Goyal, Lecture Notes in
Computer Science, vol.9462, pp.64–84, Springer, 2015. doi:
10.1007/978-3-319-26617-6\_4.
[8] Z. Zhang, Y. Chen, S.S.M. Chow, G. Hanaoka, Z. Cao, andY. Zhao, “All-but-one dual projective hashing and its applications,” Applied Cryptography and Network Security - 12thInternational Conference, ACNS 2014, Lausanne, Switzerland, June 10-13, 2014. Proceedings, ed. I. Boureanu, P. Owesarski, and S. Vaudenay, Lecture Notes in Computer Science, vol.8479, pp.181–198, Springer, 2014. doi:10.1007/978-3-319-07536-5\_12.
[9] R. Cramer and V. Shoup, “Universal hash proofs and aparadigm for adaptive chosen ciphertext secure public-key encryption,” Advances in Cryptology—EUROCRYPTO 2002,ed. L. Knudsen, LNCS, vol.2332, pp.45–64, Springer-Verlag,2002.

あらましλ ∈ N をセキュリティパラメタとすると lossy trapdoor function とは次の確率的多項式時間アルゴリズムの組 (Gen, Eval, Invert) である.
$Gen : 1λ , b 7→ (s, t) where t = ⊥ if b = 1.
$

Eval : s, x 7→ fs (x) where
fs is injective if b = 0, and lossy if b = 1.
$

Invert : t, fs (x) 7→ x if b = 0.
ここで, 関数 fs の定義域を X とすると, b = 0 のと き |fs (X)|/|X| = 1 (即 ち 単 射) b = 1 の と き|fs (X)|/|X| ∼ O(2−λ ) でかつ {s|(s, t) ← Gen(1λ , 0)}の分布と {s|(s, t) ← Gen(1λ , 1)} の分布が λ に関して計算量的に識別不能とする. Peikert と Waters は STOC
2008 において lossy trapdoor function の概念を提唱し, その具体的構成と応用を提案した [1–3]. その後
lossy trapdoor function の構成法や拡張および応用などに関して様々な研究が行われている [4–8]. 本発表ではLossy Trapdoor function の幾つかの亜種について考察を行う.

参考文献[1] C. Peikert and B. Waters, “Lossy trapdoor functions andtheir applications,” IACR Cryptol. ePrint Arch., p.279, 2007.
URL: http://eprint.iacr.org/2007/279.
[2] C. Peikert and B. Waters, “Lossy trapdoor functions andtheir applications,” Proceedings of the 40th Annual ACM
Symposium on Theory of Computing, Victoria, British
Columbia, Canada, May 17-20, 2008, ed. C. Dwork,
pp.187–196, ACM, 2008. doi:10.1145/1374376.1374406.
∗

長崎県立大学, 〒851-2195 長崎県西彼杵郡長与町まなび野 1-1-1,
University of Nagasaki, 1-1-1 Manabino, Nagayo-cho, NishiSonogi-gun, Nagasaki 851-2195, JAPAN, hoshino@sun.ac.jp1