On pairing inversion of the self-bilinear map on unknown order groups

Hyang Sook Lee; Seongan Lim; Ikkwon Yie

doi:10.1007/978-3-319-60080-2_6

On pairing inversion of the self-bilinear map on unknown order groups

Hyang Sook Lee, Seongan Lim, Ikkwon Yie

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

A secure self-bilinear map is attractive since it can be naturally extended to a secure multi-linear map which has versatile applications in cryptography. However, it was known that a self-bilinear map on a cyclic group of a known order cannot be cryptographically secure. In 2014, Yamakawa et al. presented a self-bilinear map, the YYHK pairing, on unknown order groups by using an indistinguishability obfuscator as a building block. In this paper, we prove that the Pairing Inversion (PI) of the YYHK pairing is equivalently hard to the factorization of RSA modulus N as long as iO in the scheme is an indistinguishability obfuscator. First, we prove that the General Pairing Inversion (GPI) of the YYHK pairing e: G×G → G is always solvable. By using the solvability of GPI, we prove that PI and BDHP for the YYHK-pairing e are equivalently hard to CDHP in the cyclic group G. This equivalence concludes that PI for the YYHK-pairing is equivalently hard to the factorization of N.

Original language	English
Title of host publication	Cyber Security Cryptography and Machine Learning - 1st International Conference, CSCML 2017, Proceedings
Editors	Shlomi Dolev, Sachin Lodha
Publisher	Springer Verlag
Pages	86-95
Number of pages	10
ISBN (Print)	9783319600796
DOIs	https://doi.org/10.1007/978-3-319-60080-2_6
State	Published - 2017
Event	1st International Conference on Cyber Security Cryptography and Machine Learning, CSCML 2017 - Beer-Sheva, Israel Duration: 29 Jun 2017 → 30 Jun 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10332 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Conference on Cyber Security Cryptography and Machine Learning, CSCML 2017
Country/Territory	Israel
City	Beer-Sheva
Period	29/06/17 → 30/06/17

Keywords

General Pairing Inversion
Pairing Inversion
Self-bilinear map

Access to Document

10.1007/978-3-319-60080-2_6

Cite this

Lee, H. S., Lim, S., & Yie, I. (2017). On pairing inversion of the self-bilinear map on unknown order groups. In S. Dolev, & S. Lodha (Eds.), Cyber Security Cryptography and Machine Learning - 1st International Conference, CSCML 2017, Proceedings (pp. 86-95). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10332 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-60080-2_6

Lee, Hyang Sook ; Lim, Seongan ; Yie, Ikkwon. / On pairing inversion of the self-bilinear map on unknown order groups. Cyber Security Cryptography and Machine Learning - 1st International Conference, CSCML 2017, Proceedings. editor / Shlomi Dolev ; Sachin Lodha. Springer Verlag, 2017. pp. 86-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e3c683bb7df641459f4eebba03e76080,

title = "On pairing inversion of the self-bilinear map on unknown order groups",

abstract = "A secure self-bilinear map is attractive since it can be naturally extended to a secure multi-linear map which has versatile applications in cryptography. However, it was known that a self-bilinear map on a cyclic group of a known order cannot be cryptographically secure. In 2014, Yamakawa et al. presented a self-bilinear map, the YYHK pairing, on unknown order groups by using an indistinguishability obfuscator as a building block. In this paper, we prove that the Pairing Inversion (PI) of the YYHK pairing is equivalently hard to the factorization of RSA modulus N as long as iO in the scheme is an indistinguishability obfuscator. First, we prove that the General Pairing Inversion (GPI) of the YYHK pairing e: G×G → G is always solvable. By using the solvability of GPI, we prove that PI and BDHP for the YYHK-pairing e are equivalently hard to CDHP in the cyclic group G. This equivalence concludes that PI for the YYHK-pairing is equivalently hard to the factorization of N.",

keywords = "General Pairing Inversion, Pairing Inversion, Self-bilinear map",

author = "Lee, {Hyang Sook} and Seongan Lim and Ikkwon Yie",

note = "Funding Information: We thank the anonymous reviewers for useful comments. Hyang-Sook Lee was supported by Basic Science Research Programs through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2015R1A2A1A15054564). Seongan Lim was also supported by Basic Science Research Programs through the NRF (Grant Number: 2016R1D1A1B01008562). Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; null ; Conference date: 29-06-2017 Through 30-06-2017",

year = "2017",

doi = "10.1007/978-3-319-60080-2_6",

language = "English",

isbn = "9783319600796",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "86--95",

editor = "Shlomi Dolev and Sachin Lodha",

booktitle = "Cyber Security Cryptography and Machine Learning - 1st International Conference, CSCML 2017, Proceedings",

}

Lee, HS, Lim, S & Yie, I 2017, On pairing inversion of the self-bilinear map on unknown order groups. in S Dolev & S Lodha (eds), Cyber Security Cryptography and Machine Learning - 1st International Conference, CSCML 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10332 LNCS, Springer Verlag, pp. 86-95, 1st International Conference on Cyber Security Cryptography and Machine Learning, CSCML 2017, Beer-Sheva, Israel, 29/06/17. https://doi.org/10.1007/978-3-319-60080-2_6

On pairing inversion of the self-bilinear map on unknown order groups. / Lee, Hyang Sook; Lim, Seongan; Yie, Ikkwon.

Cyber Security Cryptography and Machine Learning - 1st International Conference, CSCML 2017, Proceedings. ed. / Shlomi Dolev; Sachin Lodha. Springer Verlag, 2017. p. 86-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10332 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On pairing inversion of the self-bilinear map on unknown order groups

AU - Lee, Hyang Sook

AU - Lim, Seongan

AU - Yie, Ikkwon

N1 - Funding Information: We thank the anonymous reviewers for useful comments. Hyang-Sook Lee was supported by Basic Science Research Programs through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2015R1A2A1A15054564). Seongan Lim was also supported by Basic Science Research Programs through the NRF (Grant Number: 2016R1D1A1B01008562). Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - A secure self-bilinear map is attractive since it can be naturally extended to a secure multi-linear map which has versatile applications in cryptography. However, it was known that a self-bilinear map on a cyclic group of a known order cannot be cryptographically secure. In 2014, Yamakawa et al. presented a self-bilinear map, the YYHK pairing, on unknown order groups by using an indistinguishability obfuscator as a building block. In this paper, we prove that the Pairing Inversion (PI) of the YYHK pairing is equivalently hard to the factorization of RSA modulus N as long as iO in the scheme is an indistinguishability obfuscator. First, we prove that the General Pairing Inversion (GPI) of the YYHK pairing e: G×G → G is always solvable. By using the solvability of GPI, we prove that PI and BDHP for the YYHK-pairing e are equivalently hard to CDHP in the cyclic group G. This equivalence concludes that PI for the YYHK-pairing is equivalently hard to the factorization of N.

AB - A secure self-bilinear map is attractive since it can be naturally extended to a secure multi-linear map which has versatile applications in cryptography. However, it was known that a self-bilinear map on a cyclic group of a known order cannot be cryptographically secure. In 2014, Yamakawa et al. presented a self-bilinear map, the YYHK pairing, on unknown order groups by using an indistinguishability obfuscator as a building block. In this paper, we prove that the Pairing Inversion (PI) of the YYHK pairing is equivalently hard to the factorization of RSA modulus N as long as iO in the scheme is an indistinguishability obfuscator. First, we prove that the General Pairing Inversion (GPI) of the YYHK pairing e: G×G → G is always solvable. By using the solvability of GPI, we prove that PI and BDHP for the YYHK-pairing e are equivalently hard to CDHP in the cyclic group G. This equivalence concludes that PI for the YYHK-pairing is equivalently hard to the factorization of N.

KW - General Pairing Inversion

KW - Pairing Inversion

KW - Self-bilinear map

UR - http://www.scopus.com/inward/record.url?scp=85021721167&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-60080-2_6

DO - 10.1007/978-3-319-60080-2_6

M3 - Conference contribution

AN - SCOPUS:85021721167

SN - 9783319600796

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 86

EP - 95

BT - Cyber Security Cryptography and Machine Learning - 1st International Conference, CSCML 2017, Proceedings

A2 - Dolev, Shlomi

A2 - Lodha, Sachin

PB - Springer Verlag

Y2 - 29 June 2017 through 30 June 2017

ER -

Lee HS, Lim S, Yie I. On pairing inversion of the self-bilinear map on unknown order groups. In Dolev S, Lodha S, editors, Cyber Security Cryptography and Machine Learning - 1st International Conference, CSCML 2017, Proceedings. Springer Verlag. 2017. p. 86-95. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-60080-2_6

On pairing inversion of the self-bilinear map on unknown order groups

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this