Article

Hardness of Computing Individual Bits for One-Way Functions on Elliptic Curves

Authors:

Dimitar JetchevAuthors Info & Claims

Proceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology --- CRYPTO 2012 - Volume 7417

Pages 832 - 849

https://doi.org/10.1007/978-3-642-32009-5_48

Published: 19 August 2012 Publication History

Abstract

We prove that if one can predict any of the bits of the input to an elliptic curve based one-way function over a finite field, then we can invert the function. In particular, our result implies that if one can predict any of the bits of the input to a classical pairing-based one-way function with non-negligible advantage over a random guess then one can efficiently invert this function and thus, solve the Fixed Argument Pairing Inversion problem FAPI-1/FAPI-2. The latter has implications on the security of various pairing-based schemes such as the identity-based encryption scheme of Boneh---Franklin, Hess' identity-based signature scheme, as well as Joux's three-party one-round key agreement protocol. Moreover, if one can solve FAPI-1 and FAPI-2 in polynomial time then one can solve the Computational Diffie---Hellman problem CDH in polynomial time.

Our result implies that all the bits of the functions defined above are hard-to-compute assuming these functions are one-way. The argument is based on a list-decoding technique via discrete Fourier transforms due to Akavia---Goldwasser---Safra as well as an idea due to Boneh---Shparlinski.

References

[1]

Akavia, A.: Learning Noisy Characters, Multiplication Codes, and Cryptographic Hardcore Predicates. Ph.D. thesis, Massachusetts Institute of Technology 2008

Digital Library

[2]

Akavia, A., Goldwasser, S., Safra, S.: Proving Hard-Core Predicates Using List Decoding. In: FOCS, pp. 146---157. IEEE Computer Society 2003

Digital Library

[3]

Alexi, W., Chor, B., Goldreich, O., Schnorr, C.: RSA and Rabin Functions: Certain Parts are as Hard as the Whole. SIAM J. Comput. 172, 194---209 1988

Digital Library

[4]

Blum, M., Micali, S.: How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM J. Comput. 134, 850---864 1984

Digital Library

[5]

Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. In: Kilian ed. {25}, pp. 213---229

Digital Library

[6]

Boneh, D., Shparlinski, I.: On the Unpredictability of Bits of the Elliptic Curve Diffie---Hellman Scheme. In: Kilian ed. {25}, pp. 201---212

Digital Library

[7]

Boneh, D., Venkatesan, R.: Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes. In: Koblitz, N. ed. CRYPTO 1996. LNCS, vol. 1109, pp. 129---142. Springer, Heidelberg 1996

Digital Library

[8]

Boneh, D., Halevi, S., Howgrave-Graham, N.: The Modular Inversion Hidden Number Problem. In: Boyd, C. ed. ASIACRYPT 2001. LNCS, vol. 2248, pp. 36---51. Springer, Heidelberg 2001

Digital Library

[9]

Boneh, D., Venkatesan, R.: Rounding in Lattices and its Cryptographic Applications. In: Saks, M.E. ed. SODA, pp. 675---681. ACM/SIAM 1997

Digital Library

[10]

Duc, A., Jetchev, D.: Hardness of Computing Individual Bits for One-way Functions on Elliptic Curves full version. Cryptology ePrint Archive, Report 2011/329 2011, http://eprint.iacr.org/

[11]

Galbraith, S., Hess, F., Vercauteren, F.: Aspects of Pairing Inversion. IEEE Transactions on Information Theory 5412, 5719---5728 2008

Digital Library

[12]

Galbraith, S.D., Hopkins, H.J., Shparlinski, I.E.: Secure Bilinear Diffie-Hellman Bits. In: Wang, H., Pieprzyk, J., Varadharajan, V. eds. ACISP 2004. LNCS, vol. 3108, pp. 370---378. Springer, Heidelberg 2004

[13]

Goldmann, M., Näslund, M., Russell, A.: Complexity Bounds on General Hard-Core Predicates

[14]

Goldreich, O., Levin, L.: A Hard-Core Predicate for all One-Way Functions. In: STOC, pp. 25---32. ACM 1989

Digital Library

[15]

Gonzalez Vasco, M.I., Shparlinski, I.: On the Security of Diffie-Hellman Bits. Electronic Colloquium on Computational Complexity ECCC 745 2000

[16]

Gonzalez Vasco, M.I., Shparlinski, I.: Security of the most significant bits of the shamir message passing scheme. Math. Comput. 71237, 333---342 2002

Digital Library

[17]

Håstad, J., Näslund, M.: The Security of Individual RSA Bits. In: FOCS, pp. 510---521 1998

Digital Library

[18]

Håstad, J., Schrift, A., Shamir, A.: The Discrete Logarithm Modulo a Composite Hides $$On$$ Bits. J. Comput. Syst. Sci. 473, 376---404 1993

Digital Library

[19]

Hess, F.: Efficient Identity Based Signature Schemes Based on Pairings. In: Nyberg, K., Heys, H. eds. SAC 2002. LNCS, vol. 2595, pp. 310---324. Springer, Heidelberg 2003

Digital Library

[20]

Howgrave-Graham, N., Nguyen, P.Q., Shparlinski, I.: Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation. Math. Comput. 72243, 1473---1485 2003

Digital Library

[21]

Jao, D., Miller, S.D., Venkatesan, R.: Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log? In: Roy, B. ed. ASIACRYPT 2005. LNCS, vol. 3788, pp. 21---40. Springer, Heidelberg 2005

Digital Library

[22]

Jetchev, D., Venkatesan, R.: Bits Security of the Elliptic Curve Diffie---Hellman Secret Keys. In: Wagner, D. ed. CRYPTO 2008. LNCS, vol. 5157, pp. 75---92. Springer, Heidelberg 2008

Digital Library

[23]

Joux, A.: A One Round Protocol for Tripartite Diffie---Hellman. In: Bosma, W. ed. ANTS 2000. LNCS, vol. 1838, pp. 385---394. Springer, Heidelberg 2000

Digital Library

[24]

Joux, A.: The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems. In: Fieker, C., Kohel, D.R. eds. ANTS 2002. LNCS, vol. 2369, pp. 20---32. Springer, Heidelberg 2002

Digital Library

[25]

Kilian, J. ed.: CRYPTO 2001. LNCS, vol. 2139. Springer, Heidelberg 2001

[26]

Li, W.-C.W., Näslund, M., Shparlinski, I.E.: Hidden Number Problem with the Trace and Bit Security of XTR and LUC. In: Yung, M. ed. CRYPTO 2002. LNCS, vol. 2442, pp. 433---448. Springer, Heidelberg 2002

Digital Library

[27]

Morillo, P., Rífols, C.: The Security of All Bits Using List Decoding. In: Jarecki, S., Tsudik, G. eds. PKC 2009. LNCS, vol. 5443, pp. 15---33. Springer, Heidelberg 2009

Digital Library

[28]

Nguyen, P.Q., Shparlinski, I.: The Insecurity of the Digital Signature Algorithm with Partially Known Nonces. J. Cryptology 153, 151---176 2002

Digital Library

[29]

Nguyen, P.Q., Shparlinski, I.: The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces. Des. Codes Cryptography 302, 201---217 2003

Digital Library

[30]

Nguyen, P.Q.: The dark side of the hidden number problem: Lattice attacks on DSA. In: Proc. Workshop on Cryptography and Computational Number Theory, pp. 321---330 2001

[31]

Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. ed. EUROCRYPT 1999. LNCS, vol. 1592, pp. 223---238. Springer, Heidelberg 1999

Digital Library

[32]

Rabin, M.: Digitalized signatures and public-key functions as intractable as factorization 1979

[33]

Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 212, 120---126 1978

Digital Library

[34]

Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairings. In: Proceedings of SCIS 2000, Okinawa, Japan 2000

[35]

Schnorr, C.: Security of Allmost ALL Discrete Log Bits. Electronic Colloquium on Computational Complexity ECCC 533 1998

[36]

Schrift, A., Shamir, A.: The Discrete Log is Very Discreet. In: STOC, pp. 405---415. ACM 1990

Digital Library

[37]

Shparlinski, I.E.: On the Generalised Hidden Number Problem and Bit Security of XTR. In: Bozta, S., Sphparlinski, I. eds. AAECC 2001. LNCS, vol. 2227, pp. 268---277. Springer, Heidelberg 2001

Digital Library

[38]

Shparlinski, I.,Winterhof, A.: A hidden number problem in small subgroups. Math. Comput. 74252, 2073---2080 2005

[39]

Smart, N.P.: Identity-based authenticated key agreement protocol based on weil pairing. Electronics Letters 3813, 630---632 2002

Cited By

Wang MZhan TZhang H(2022)Bit Security of the CDH Problems over Finite FieldsSelected Areas in Cryptography – SAC 201510.1007/978-3-319-31301-6_25(441-461)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-31301-6_25
Lv KRen SQin W(2016)The Security of Individual Bit for XTRInformation and Communications Security10.1007/978-3-319-50011-9_7(87-98)Online publication date: 29-Nov-2016
https://dl.acm.org/doi/10.1007/978-3-319-50011-9_7
Chang SHong HLee ELee H(2013)Pairing Inversion via Non-degenerate Auxiliary Pairings6th International Conference on Pairing-Based Cryptography --- Pairing 2013 - Volume 836510.1007/978-3-319-04873-4_5(77-96)Online publication date: 22-Nov-2013
https://dl.acm.org/doi/10.1007/978-3-319-04873-4_5

Hardness of Computing Individual Bits for One-Way Functions on Elliptic Curves

Recommendations

Convertible Authenticated Encryption Scheme Without Using Conventional One-Way Function

An authenticated encryption allows the designated recipient to verify the authenticity while recovering the message. To protect the recipient's benefit in case of a later dispute, a convertible authenticated encryption scheme allows the recipient to ...
A provably secure and efficient authentication scheme for access control in mobile pay-TV systems

To guarantee the secure access by authorized subscribers in mobile pay-TV systems, user authentication is required. User authentication is a security mechanism used to verify the identity of a legal subscriber. In 2012, Yeh and Tsaur proposed an ...
An improved one-to-many authentication scheme based on bilinear pairings with provable security for mobile pay-TV systems

In 2012, Wang and Qin proposed an authentication mechanism in order to get access control for mobile pay-TV organization to enhance the Sun and Leu's technique. Wang and Qin declared that their technique satisfies the security expectations or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology --- CRYPTO 2012 - Volume 7417

August 2012

886 pages

ISBN:9783642320088

Editors:
Reihaneh Safavi-Naini
Department of Computer Science, University of Calgary, Calgary, Canada
,
Ran Canetti
Department of Computer Science, University of Boston, Boston, USA

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 19 August 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang MZhan TZhang H(2022)Bit Security of the CDH Problems over Finite FieldsSelected Areas in Cryptography – SAC 201510.1007/978-3-319-31301-6_25(441-461)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-31301-6_25
Lv KRen SQin W(2016)The Security of Individual Bit for XTRInformation and Communications Security10.1007/978-3-319-50011-9_7(87-98)Online publication date: 29-Nov-2016
https://dl.acm.org/doi/10.1007/978-3-319-50011-9_7
Chang SHong HLee ELee H(2013)Pairing Inversion via Non-degenerate Auxiliary Pairings6th International Conference on Pairing-Based Cryptography --- Pairing 2013 - Volume 836510.1007/978-3-319-04873-4_5(77-96)Online publication date: 22-Nov-2013
https://dl.acm.org/doi/10.1007/978-3-319-04873-4_5

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents