Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Truncated and Multiple Differential Cryptanalysis of Reduced Round Midori128 Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Cryptanalysis of Multi-Prime \(\varPhi \)-Hiding Assumption

Authors : Jun Xu, Lei Hu, Santanu Sarkar, Xiaona Zhang, Zhangjie Huang, Liqiang Peng

Published in: Information Security

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In Crypto 2010, Kiltz, O’Neill and Smith used m-prime RSA modulus N with \(m\ge 3\) for constructing lossy RSA. The security of the proposal is based on the Multi-Prime \(\varPhi \)-Hiding Assumption. In this paper, we propose a heuristic algorithm based on the Herrmann-May lattice method (Asiacrypt 2008) to solve the Multi-Prime \(\varPhi \)-Hiding Problem when prime \(e>N^{\frac{2}{3m}}\). Further, by combining with mixed lattice techniques, we give an improved heuristic algorithm to solve this problem when prime \(e>N^{\frac{2}{3m}-\frac{1}{4m^2}}\). These two results are verified by our experiments. Our bounds are better than the existing works.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter MQSAS - A Multivariate Sequential Aggregate Signature Scheme
Appendix
Available only for authorised users
Footnotes
1
There is a minor mistake in proceedings version of Crypto 2010 as reported in [7, Page 97].
 
Literature
1.
Cachin, C., Micali, S., Stadler, M.A.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 402. Springer, Heidelberg (1999)CrossRef
2.
Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997)MathSciNetCrossRefMATH
3.
Gentry, C., Mackenzie, P., Ramzan, Z.: Password authenticated key exchange using hidden smooth subgroups. In: Proceedings of the 12th ACM Conference on Computer and Communications Security CCS 2005, pp. 299–309. ACM, New York (2005)
4.
Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005)CrossRef
5.
6.
Hemenway, B., Ostrovsky, R.: Public-key locally-decodable codes. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 126–143. Springer, Heidelberg (2008)CrossRef
7.
Herrmann, M.: Improved cryptanalysis of the Multi-Prime \(\phi \) - Hiding Assumption. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 92–99. Springer, Heidelberg (2011)CrossRef
8.
Herrmann, M., May, A.: Solving linear equations modulo divisors: on factoring given any bits. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 406–424. Springer, Heidelberg (2008)CrossRef
9.
Howgrave-Graham, N.: Approximate integer common divisors. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, p. 51. Springer, Heidelberg (2001)CrossRef
10.
Kakvi, S.A., Kiltz, E., May, A.: Certifying RSA. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 404–414. Springer, Heidelberg (2012)CrossRef
11.
12.
Kiltz, E., O’Neill, A., Smith, A.: Instantiability of RSA-OAEP under chosen-plaintext attack. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 295–313. Springer, Heidelberg (2010)CrossRef
13.
14.
May, A.: Using LLL-reduction for solving RSA and factorization problems. In: Nguyen, P.Q., Valle, B. (eds.) The LLL Algorithm. Information Security and Cryptography, pp. 315–348. Springer, Heidelberg (2010)
15.
Sarkar, S.: Reduction in lossiness of RSA trapdoor permutation. In: Bogdanov, A., Sanadhya, S. (eds.) SPACE 2012. LNCS, vol. 7644, pp. 144–152. Springer, Heidelberg (2012)CrossRef
16.
Schridde, C., Freisleben, B.: On the validity of the \(\Phi \)-hiding assumption in cryptographic protocols. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 344–354. Springer, Heidelberg (2008)CrossRef
17.
Takayasu, A., Kunihiro, N.: Better lattice constructions for solving multivariate linear equations modulo unknown divisors. In: Boyd, C., Simpson, L. (eds.) ACISP. LNCS, vol. 7959, pp. 118–135. Springer, Heidelberg (2013)CrossRef
18.
Takayasu, A., Kunihiro, N.: Better lattice constructions for solving multivariate linear equations modulo unknown divisors. IEICE Trans. 97–A(6), 1259–1272 (2014)CrossRefMATH
19.
Tosu, K., Kunihiro, N.: Optimal bounds for multi-prime \(\Phi \)-hiding assumption. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol. 7372, pp. 1–14. Springer, Heidelberg (2012)
Metadata
Title
Cryptanalysis of Multi-Prime -Hiding Assumption
Authors
Jun Xu
Lei Hu
Santanu Sarkar
Xiaona Zhang
Zhangjie Huang
Liqiang Peng
Copyright Year
2016
Book
Information Security

Print ISBN: 978-3-319-45870-0

Electronic ISBN: 978-3-319-45871-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-45871-7_26

Premium Partner

    Image Credits