nach oben

Journal of Cryptology

Erschienen in:

28.02.2018

On the Tightness of Forward-Secure Signature Reductions

verfasst von: Michel Abdalla, Fabrice Benhamouda, David Pointcheval

Erschienen in: Journal of Cryptology | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we revisit the security of factoring-based signature schemes built via the Fiat–Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the \(\phi \)-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-security setting based on ideas from the Itkis–Reyzin forward-secure signature scheme. Unlike the original Itkis–Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter security reduction. Moreover, we also show that the tighter security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-security setting, as long as the use of stronger security assumptions is deemed acceptable. Finally, we investigate the design of forward-secure signature schemes whose security reductions are fully tight.

Vorheriger Artikel Improved Combinatorial Algorithms for the Inhomogeneous Short Integer Solution Problem

Nächster Artikel Unifying Leakage Models: From Probing Attacks to Noisy Leakage

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

In [15], Bellare, Poettering, and Stebila call these schemes trapdoor and provide a formal definition for it.

We originally called this assumption the strong-\(2^t\)-residuosity in [3]. In this full version, we prefer to use the same name as in [42].

Furthermore, M-SUF-CMA signature schemes with re-randomizable secret keys yield forward-secure signature schemes in the class we consider in our impossibility result, if the secret key is re-randomized before signing.

We enforce that e is co-prime to \(\phi (N)\), while in [45], they enforce instead that \(\phi (N)\) is divisible by another randomly chosen \({\ell _e}\)-bit prime \(e'\). This slightly simplifies proofs, notation, and bounds, but the original assumption could be used as well.

A prime number p is safe if it can be written as \(p=2q+1\), where q is a prime number.

1/2 is just an arbitrary constant. It can be any reasonable constant.

Contrary to the definition of lossiness given in [5, 6], the impersonator \(\mathcal {I}_1\) does not have access to an oracle

https://static-content.springer.com/image/art%3A10.1007%2Fs00145-018-9283-2/MediaObjects/145_2018_9283_IEq346_HTML.gif

https://static-content.springer.com/image/art%3A10.1007%2Fs00145-018-9283-2/MediaObjects/145_2018_9283_IEq347_HTML.gif

. However, we remark that this has no impact on the security definition as the execution of

https://static-content.springer.com/image/art%3A10.1007%2Fs00145-018-9283-2/MediaObjects/145_2018_9283_IEq348_HTML.gif

does not require any secret information.

There is a small difference between the GQ scheme described below and the original one in [34]: in this paper, the distribution of e is assumed to be uniform over \({\ell _e}\)-bit primes, such that e does not divide \(\phi (N)\), while in [34] there was no restriction on e. See also Footnote 11.

We choose e to be co-prime to \(\phi (N)\) in this paper, as this makes the identification scheme response-unique and slightly simplifies the key indistinguishability proof. We point out the distribution of uniform \({\ell _e}\)-bit primes is \( \frac{{\ell _N}+1}{2^{{\ell _e}-1}}\)-close to the distribution of \({\ell _e}\)-bit primes that are co-prime to \(\phi (N)\), according to Proposition B.19. Therefore, up to losing a negligible \(\frac{{\ell _N}+1}{2^{{\ell _e}-1}}\) term in the security reduction, we can also take e to be a \({\ell _e}\)-bit prime.

When e is co-prime with \(\phi (N)\), any element \(U \in {{\mathbb Z}}_N^*\) is an e-residue. However, under the \(\phi \)-hiding assumption, this case is indistinguishable from the case where e divides \(\phi (N)\), in which case only 1 out of e elements of \({{\mathbb Z}}_N^*\) is an e-residue. This is why we simply say that the goal of the identification scheme is to implicitly prove that U is an e-residue.

The test \(Z \in {{\mathbb Z}}_N^*\) can be replaced by the less expensive test \(Z \bmod N \ne 0\), as explained in Sect. 6.2.

However, if we use fixed exponents, we need to rely on a variant of the \(\phi \)-hiding assumption, which uses fixed exponents instead of random ones. That is why we do not consider this solution in this paper.

They can also use a probabilistic algorithm \({\mathsf {isPrime}}''\) with error probability \(\varepsilon ''_p\) so that \(T \cdot ({\ell _e}-1) \cdot \varepsilon ''_p \le 2^{- k -1}\). In that case, in the reduction, we would first replace \({\mathsf {isPrime}}''\) by a deterministic algorithm \({\mathsf {isPrime}}'\) in \({\mathsf {KG}}\) and \({\mathsf {Update}}\). This would just add a term \(2^{- k }\) to the final probability for the adversary to win the original game.

In practice, \({\mathsf {H}}''\) will be implemented using a hash function which is hundred times faster than any primality test.

Actually, a Miller–Rabin test should be a little faster than an exponentiation since we can stop the exponentiation before the end, in some cases.

The factor \(\frac{3}{2}\) comes from the fact that in average, an exponentiation by a \({\ell _e}\)-bit number requires \(\frac{3}{2} {\ell _e}\) multiplications, using the square-and-multiply algorithm.

More precisely, we need e in the \(\phi \)-assumption to be chosen as a power of a small prime number. The distribution of \(N=p_1 p_2\) such that e divides \(p_1\) can be sampled in polynomial time, if we assume the extended Riemann hypothesis (Conjecture 8.4.4 of [18]), exactly as when e is a prime. But to our knowledge, this new variant of the \(\phi \)-hiding has not been analyzed and might actually not hold.

We use \(T\varepsilon \) instead of \(\varepsilon \) because of the way selective security notions are defined, see Remark 2.4 to understand this choice.

The constant 43 comes from \(- \log _2 \varepsilon - \log _2 \delta + 3\) (for our scheme) and \(-\log _2 \varepsilon + \log _2 T + 3\) (for the original IR scheme).

A safe prime p is an odd prime such that \((p-1)/2\) is also prime. This assumption is needed for the security reduction of the IR scheme.

We say that the factorization is n-bit hard if factorizing a given random RSA modulus with constant probability of success (for example, 1/2) takes time at least \(2^n\). As usual when we want to choose parameters, we suppose that the strong RSA problem and the \(\phi \)-hiding problems are as hard as factorization, as the best known algorithms to solve these problems just consist in factorizing the modulus N (for the parameters we have chosen).

As for our variant of the IR scheme, we can use a hash function modeled as a random oracle (in the security proof) to avoid storing the exponents in the keys, as explained in Sect. 5.1.

By factorization, we mean finding any non-trivial factor of N.

\(t_\mathcal {R}\) does not include the time of the forger.

We could use a \((t,q_h,q_s,\varepsilon ')\)-secure scheme with a small enough \(\varepsilon '\). But this would make the proof more complicated.

By best, we mean that, for any fixed period i and key pair \(( pk , sk _1)\), no adversary can win the game with probability greater than \((1-\eta ) \varepsilon \).

This is the case with most currently used schemes.

There are no lossy keys, so it does not make sense to consider response uniqueness for lossy keys, contrary to Theorem 3.1.

M. Abdalla, J.H. An, M. Bellare, C. Namprempre, From identification to signatures via the Fiat–Shamir transform: minimizing assumptions for security and forward-security, in EUROCRYPT 2002. LNCS, vol. 2332 (Springer, Heidelberg, 2002), pp. 418–433

M. Abdalla, J.H. An, M. Bellare, C. Namprempre, From identification to signatures via the Fiat-Shamir transform: Necessary and sufficient conditions for security and forward-security. IEEE Trans. Inf. Theory 54(8), 3631–3646 (2008)MathSciNetCrossRefMATH

M. Abdalla, F. Ben Hamouda, D. Pointcheval, Tighter reductions for forward-secure signature schemes, in PKC 2013. LNCS, vol. 7778 (Springer, Heidelberg, 2013), pp. 292–311

M. Abe, B. David, M. Kohlweiss, R. Nishimaki, M. Ohkubo, Tagged one-time signatures: Tight security and optimal tag size, in PKC 2013. LNCS, vol. 7778 (Springer, Heidelberg, 2013), pp. 312–331

M. Abdalla, P.-A. Fouque, V. Lyubashevsky, M. Tibouchi, Tightly-secure signatures from lossy identification schemes, in EUROCRYPT 2012. LNCS, vol. 7237 (Springer, Heidelberg, 2012), pp. 572–590

M. Abdalla, P.-A. Fouque, V. Lyubashevsky, M. Tibouchi, Tightly-secure signatures from lossy identification schemes. J. Cryptol. 29(3), 597–631 (2016)MathSciNetCrossRefMATH

R. Anderson, Two remarks on public-key cryptology. Manuscript. Relevant material presented by the author in an invited lecture at the 4th ACM Conference on Computer and Communications Security, CCS 1997, Zurich, Switzerland, 1–4 Apr 1997, Sept 2000

D. Boneh, X. Boyen, H. Shacham, Short group signatures, in CRYPTO 2004. LNCS, vol. 3152 (Springer, Heidelberg, 2004), pp. 41–55

F. Benhamouda, J. Herranz, M. Joye, B. Libert, Efficient cryptosystems from \(2^k\)-th power residue symbols. J. Cryptol. 20(2), 519–549 (2017)CrossRefMATH

10.

C. Bader, T. Jager, Y. Li, S. Schäge, On the impossibility of tight cryptographic reductions, in EUROCRYPT 2016, Part II. LNCS, vol. 9666 (Springer, Heidelberg, 2016), pp. 273–304

11.

M. Bellare, S.K. Miner, A forward-secure digital signature scheme, in CRYPTO’99. LNCS, vol. 1666 (Springer, Heidelberg, 1999), pp. 431–448

12.

M. Bellare, S. Micali, R. Ostrovsky, The (true) complexity of statistical zero knowledge, in 22nd ACM STOC (ACM Press, New York, 1990), pp. 494–502

13.

M. Bellare, C. Namprempre, G. Neven, Unrestricted aggregate signatures, in ICALP 2007. LNCS, vol. 4596 (Springer, Heidelberg, 2007), pp. 411–422

14.

N. Bari, B. Pfitzmann, Collision-free accumulators and fail-stop signature schemes without trees, in EUROCRYPT’97. LNCS, vol. 1233 (Springer, Heidelberg, 1997), pp. 480–494

15.

M. Bellare, B. Poettering, D. Stebila, From identification to signatures, tightly: a framework and generic transforms, in ASIACRYPT 2016, Part II. LNCS, vol. 10032 (Springer, Heidelberg, 2016), pp. 435–464

16.

M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in ACM CCS 93 (ACM Press, New York, 1993), pp. 62–73

17.

M. Bellare, P. Rogaway, The security of triple encryption and a framework for code-based game-playing proofs, in EUROCRYPT 2006. LNCS, vol. 4004 (Springer, Heidelberg, 2006), pp. 409–426

18.

E. Bach, J. Shallit, Algorithmic Number Theory. MIT Press, Cambridge (1996)MATH

19.

R. Cramer, I. Damgård, Escure signature schemes based on interactive protocols, in CRYPTO’95. LNCS, vol. 963 (Springer, Heidelberg, 1995), pp. 297–310

20.

J. Camenisch, M. Koprowski, Fine-grained forward-secure signature schemes without random oracles. Discrete Appl. Math. 154(2), 175–188 (2006)MathSciNetCrossRefMATH

21.

C. Cachin, S. Micali, M. Stadler, Computationally private information retrieval with polylogarithmic communication, in EUROCRYPT’99. LNCS, vol. 1592 (Springer, Heidelberg, 1999), pp. 402–414

22.

J.-S. Coron, Optimal security proofs for PSS and other signature schemes, in EUROCRYPT 2002. LNCS, vol. 2332 (Springer, Heidelberg, 2002), pp. 272–287

23.

R. Cramer, Modular design of secure yet practical cryptographic protocols. Ph.D. thesis, CWI and University of Amsterdam, Amsterdam, The Netherlands (Nov 1996)

24.

P. Dusart, Autour de la fonction qui compte le nombre de nombres premiers. Thesis, Université de Limoges (1998)

25.

ECRYPT II yearly report on algorithms and keysizes (2011)

26.

U. Feige, A. Fiat, A. Shamir, Zero-knowledge proofs of identity. J. Cryptol. 1(2), 77–94 (1988)MathSciNetCrossRefMATH

27.

E. Fujisaki, T. Okamoto, Statistical zero knowledge protocols to prove modular polynomial relations, in CRYPTO’97. LNCS, vol. 1294 (Springer, Heidelberg, 1997), pp. 16–30

28.

A. Fiat, A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, in CRYPTO’86. LNCS, vol. 263 (Springer, Heidelberg, 1987), pp. 186–194

29.

S. Garg, R. Bhaskar, S.V. Lokam, Improved bounds on security reductions for discrete log based signatures, in CRYPTO 2008. LNCS, vol. 5157 (Springer, Heidelberg, 2008), pp. 93–107

30.

S. Goldwasser, S. Micali, R.L. Rivest, A “paradoxical” solution to the signature problem (extended abstract), in 25th FOCS (IEEE Computer Society Press, Washington, 1984), pp. 441–448

31.

S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRefMATH

32.

J.A. Garay, P.D. MacKenzie, K. Yang, Strengthening zero-knowledge protocols using signatures. J. Cryptol. 19(2), 169–209 (2006)MathSciNetCrossRefMATH

33.

O. Goldreich, Two remarks concerning the Goldwasser–Micali–Rivest signature scheme, in CRYPTO’86. LNCS, vol. 263 (Springer, Heidelberg, 1987), pp. 104–110

34.

L.C. Guillou, J.-J. Quisquater, A practical zero-knowledge protocol fitted to security microprocessor minimizing both trasmission and memory, in EUROCRYPT’88. LNCS, vol. 330 (Springer, Heidelberg, 1988), pp. 123–128

35.

J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures, in ASIACRYPT 2006. LNCS, vol. 4284 (Springer, Heidelberg, 2006), pp. 444–459

36.

J. Groth, A. Sahai, Efficient non-interactive proof systems for bilinear groups, in EUROCRYPT 2008. LNCS, vol. 4965 (Springer, Heidelberg, 2008), pp. 415–432

37.

K. Haralambiev, Efficient cryptographic primitives for non-interactive zero-knowledge proofs and applications. Ph.D. thesis, New York University (2011)

38.

D. Hofheinz, T. Jager, Tightly secure signatures and public-key encryption, in CRYPTO 2012. LNCS, vol. 7417 (Springer, Heidelberg, 2012), pp. 590–607

39.

S. Hohenberger, B. Waters, Short and stateless signatures from the RSA assumption, in CRYPTO 2009. LNCS, vol. 5677 (Springer, Heidelberg, 2009), pp. 654–670

40.

R. Impagliazzo, M. Naor, Efficient cryptographic schemes provably as secure as subset sum. J. Cryptol. 9(4), 199–216 (1996)MathSciNetCrossRefMATH

41.

G. Itkis, L. Reyzin, Forward-secure signatures with optimal signing and verifying, in CRYPTO 2001. LNCS, vol. 2139 (Springer, Heidelberg, 2001), pp. 332–354

42.

M. Joye, B. Libert, Efficient cryptosystems from \(2^k\)-th power residue symbols, in EUROCRYPT 2013. LNCS, vol. 7881 (Springer, Heidelberg, 2013), pp. 76–92

43.

C.S. Jutla, A. Roy, Shorter quasi-adaptive NIZK proofs for linear subspaces, in ASIACRYPT 2013, Part I. LNCS, vol. 8269 (Springer, Heidelberg, 2013), pp. 1–20

44.

S.A. Kakvi, E. Kiltz, Optimal security proofs for full domain hash, revisited, in EUROCRYPT 2012. LNCS, vol. 7237 (Springer, Heidelberg, 2012), pp. 537–553

45.

E. Kiltz, A. O’Neill, A. Smith, Instantiability of RSA-OAEP under chosen-plaintext attack, in CRYPTO 2010. LNCS, vol. 6223 (Springer, Heidelberg, 2010), pp. 295–313

46.

H. Krawczyk, Simple forward-secure signatures from any signature scheme, in ACM CCS 00 (ACM Press, New York, 2000), pp. 108–115

47.

J. Katz, V. Vaikuntanathan, Signature schemes with bounded leakage resilience, in ASIACRYPT 2009. LNCS, vol. 5912 (Springer, Heidelberg, 2009), pp. 703–720

48.

J. Katz, N. Wang, Efficiency improvements for signature schemes with tight security reductions, in ACM CCS 03 (ACM Press, New York, 2003), pp. 155–164

49.

V. Lyubashevsky, D. Micciancio, Generalized compact Knapsacks are collision resistant, in ICALP 2006, Part II. LNCS, vol. 4052 (Springer, Heidelberg, 2006), pp. 144–155

50.

S. Micali, A secure and efficient digital signature algorithm. Technical Memo MIT/LCS/TM-501b, Massachusetts Institute of Technology, Laboratory for Computer Science, Apr 1994

51.

D. Micciancio, P. Mol, Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions, in CRYPTO 2011. LNCS, vol. 6841 (Springer, Heidelberg, 2011), pp. 465–484

52.

T. Malkin, D. Micciancio, S.K. Miner, Efficient generic forward-secure signatures with an unbounded number of time periods, in EUROCRYPT 2002. LNCS, vol. 2332 (Springer, Heidelberg, 2002), pp. 400–417

53.

S. Micali, L. Reyzin, Improving the exact security of digital signature schemes. J. Cryptol. 15(1), 1–18 (2002)MathSciNetCrossRefMATH

54.

A. Menezes, N. Smart, Security of signature schemes in a multi-user setting. Des. Codes Cryptogr. 33(3), 261–274 (2004)MathSciNetCrossRefMATH

55.

K. Ohta, T. Okamoto, A modification of the Fiat–Shamir scheme, in CRYPTO’88. LNCS, vol. 403 (Springer, Heidelberg, August 1990), pp. 232–243

56.

H. Ong, C.-P. Schnorr, Fast signature generation with a Fiat–Shamir-like scheme, in EUROCRYPT’90. LNCS, vol. 473 (Springer, Heidelberg, 1991), pp. 432–440

57.

P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, in EUROCRYPT’99. LNCS, vol. 1592 (Springer, Heidelberg, 1999), pp. 223–238

58.

C. Peikert, A. Rosen, Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices, in TCC 2006. LNCS, vol. 3876 (Springer, Heidelberg, 2006), pp. 145–166

59.

S. Patel, G.S. Sundaram, An efficient discrete log pseudo random generator, in CRYPTO’98. LNCS, vol. 1462 (Springer, Heidelberg, 1998), pp. 304–317

60.

D. Pointcheval, J. Stern, Security arguments for digital signatures and blind signatures. J. Cryptol. 13(3), 361–396 (2000)CrossRefMATH

61.

P. Paillier, D. Vergnaud, Discrete-log-based signatures may not be equivalent to discrete log, in ASIACRYPT 2005. LNCS, vol. 3788 (Springer, Heidelberg, 2005), pp. 1–20

62.

C.-P. Schnorr, Efficient identification and signatures for smart cards (abstract) (rump session), in EUROCRYPT’89. LNCS, vol. 434 (Springer, Heidelberg, 1990), pp. 688–689

63.

Y. Seurin, On the exact security of Schnorr-type signatures in the random oracle model, in EUROCRYPT 2012. LNCS, vol. 7237 (Springer, Heidelberg, 2012), pp. 554–571

64.

P.C. van Oorschot, M.J. Wiener, On Diffie–Hellman key agreement with short exponents, in EUROCRYPT’96. LNCS, vol. 1070 (Springer, Heidelberg, 1996), pp. 332–343

Titel: On the Tightness of Forward-Secure Signature Reductions
verfasst von: Michel Abdalla
Fabrice Benhamouda
David Pointcheval
Publikationsdatum: 28.02.2018
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 1/2019
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-018-9283-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2019

On the Impossibility of Structure-Preserving Deterministic Primitives

Round-Efficient Black-Box Construction of Composable Multi-Party Computation

Unifying Leakage Models: From Probing Attacks to Noisy Leakage

Multidimensional Linear Cryptanalysis

Improved Combinatorial Algorithms for the Inhomogeneous Short Integer Solution Problem

Premium Partner