Top

Published in:

2016 | OriginalPaper | Chapter

Time-Advantage Ratios Under Simple Transformations: Applications in Cryptography

Author : Maciej Skórski

Published in: Cryptography and Information Security in the Balkans

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Security of cryptographic primitives is quantified by bounding the probability \(\epsilon \) that an adversary with certain resources t win the security game. We derive a clear formula showing how the security measured as the worst time-to-success ratio changes under a broad class of reductions. Applications include comparisons of (a) bounds for pseudoentropy chain rules, (b) leakage resilient stream ciphers security, and (c) security of weak pseudorandom functions fed with weak keys.

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 Linear Cryptanalysis and Modified DES with Embedded Parity Check in the S-boxes

next chapter Synchronous Universally Composable Computer Networks

The constant is at least 1 because one cannot increase the security level by black-box reductions.

We consider the security of AES256 as a weak PRF, and not a standard PRF, because of non-uniform attacks which show that no PRF with a k bit key can have \(s/\epsilon \approx 2 ^k\) security [DTT09], at least unless we additionally require \(\epsilon \gg 2^{-k/2}\).

Let us stress that using the same letter Z for the 2nd term in (X, Z) and (Y, Z) means that we require that the marginal distribution Z of (X, Z) and (Y, Z) is the same.

We note that in a more standard notion the entire stream \(X_1,\ldots ,X_{q}\) is indistinguishable from random. This is implied by the notion above by a standard hybrid argument, with a loss of a multiplicative factor of q in the distinguishing advantage.

We consider the security of \(\mathsf {AES256}\) as a weak PRF, and not a standard PRF, because of non-uniform attacks which show that no PRF with a k bit key can have \(s/\epsilon \approx 2 ^k\) security [DTT09], at least unless we additionally require \(\epsilon \gg 2^{-k/2}\).

[ADW10]

Dodis, Y., Alwen, J., Wichs, D.: Survey: leakage resilience and the bounded retrieval model. In: Kurosawa, K. (ed.) ICITS 2009. LNCS, vol. 5973, pp. 1–18. Springer, Heidelberg (2010)CrossRef

[BBKN12]

Barenghi, A., Breveglieri, L., Koren, I., Naccache, D.: Fault injection attacks on cryptographic devices: theory, practice, and countermeasures. Proc. IEEE 100, 3056–3076 (2012)CrossRef

[BL13]

Laanoja, R., Buldas, A.: Security proofs for hash tree time-stamping using hash functions with small output size. In: Boyd, C., Simpson, L. (eds.) ACISP 2013. LNCS, vol. 7959, pp. 235–250. Springer, Heidelberg (2013)CrossRef

[BN10]

Buldas, A., Niitsoo, M.: Optimally tight security proofs for hash-then-publish time-stamping. In: Steinfeld, R., Hawkes, P. (eds.) ACISP 2010. LNCS, vol. 6168, pp. 318–335. Springer, Heidelberg (2010)CrossRef

[BS04]

Buldas, A., Saarepera, M.: On provably secure time-stamping schemes. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 500–514. Springer, Heidelberg (2004)CrossRef

[CKLR11]

Kalai, Y.T., Chung, K.-M., Raz, R., Liu, F.-H.: Memory delegation. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 151–168. Springer, Heidelberg (2011)CrossRef

[DP08]

Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 293–302. IEEE Computer Society, Washington, DC (2008)

[DTT09]

De, A., Trevisan, L., Tulsiani, M.: Non-uniform attacks against one-way functions and PRGs. Electron. Colloquium Comput. Complex. (ECCC) 16, 113 (2009)

[DY13]

Dodis, Y., Yu, Y.: Overcoming weak expectations. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 1–22. Springer, Heidelberg (2013)CrossRef

[FOR15]

Fuller, B., O’Neill, A., Reyzin, L.: A unified approach to deterministic encryption: new constructions and a connection to computational entropy. J. Cryptology 28(3), 671–717 (2015)CrossRefMathSciNetMATH

[FPS12]

Faust, S., Pietrzak, K., Schipper, J.: Practical leakage-resilient symmetric cryptography. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 213–232. Springer, Heidelberg (2012)CrossRef

[GW11]

Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 99–108. ACM, New York (2011)

[HLR07]

Reyzin, L., Lu, C.-J., Hsiao, C.-Y.: Conditional computational entropy, or toward separating pseudoentropy from compressibility. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 169–186. Springer, Heidelberg (2007)CrossRef

[HSH+08]

Alex Halderman, J., Schoen, S.D., Heninger, N., Clarkson, W., Paul, W., Cal, J.A., Feldman, A.J., Felten, E.W.: Least we remember: cold boot attacks on encryption keys. In: USENIX Security Symposium (2008)

[JP14a]

Pietrzak, K., Jetchev, D.: How to fake auxiliary input. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 566–590. Springer, Heidelberg (2014)CrossRef

[JP14b]

Jetchev, D., Pietrzak, K.: How to fake auxiliary input. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 566–590. Springer, Heidelberg (2014)CrossRef

[KJJ99]

Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)CrossRef

[Koc96]

Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)

[LM94]

Luby, M.G., Michael, L.: Pseudorandomness and Cryptographic Applications. Princeton University Press, Princeton (1994)MATH

[Mol10]

Mol, P.: Leakage-resilient cryptography: a survey of recent advances (2010). http://cseweb.ucsd.edu/pmol/Documents/RE.pdf

[MR04]

Micali, S., Reyzin, L.: Physically observable cryptography. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 278–296. Springer, Heidelberg (2004)CrossRef

[Pie]

Pietrzak, K.: Private communication, May

[Pie09]

Pietrzak, K.: A leakage-resilient mode of operation. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 462–482. Springer, Heidelberg (2009)CrossRef

[PS15]

Pietrzak, K., Skórski, M.: The chain rule for HILL pseudoentropy, revisited. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LatinCrypt 2015. LNCS, vol. 9230, pp. 81–98. Springer, Heidelberg (2015)CrossRef

[RTTV08]

Reingold, O., Trevisan, L., Tulsiani, M., Vadhan, S.: Dense subsets of pseudorandom sets. In: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 76–85. IEEE Computer Society, Washington, DC (2008)

[Sko15a]

Skorski, M.: Metric pseudoentropy: characterizations, transformations and applications. In: Lehmann, A., Wolf, S. (eds.) ICITS 2015. LNCS, vol. 9063, pp. 105–122. Springer, Heidelberg (2015)

[Sko15b]

Skorski, M.: Nonuniform indistinguishability and unpredictability hardcore lemmas: new proofs and applications to pseudoentropy. In: Lehmann, A., Wolf, S. (eds.) ICITS 2015. LNCS, vol. 9063, pp. 123–140. Springer, Heidelberg (2015)

[VZ13]

Zheng, C.J., Vadhan, S.: A uniform min-max theorem with applications in cryptography. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 93–110. Springer, Heidelberg (2013)CrossRef

[YS13]

Standaert, F.-X., Yu, Y.: Practical leakage-resilient pseudorandom objects with minimum public randomness. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 223–238. Springer, Heidelberg (2013)CrossRef

[YSPY10]

Yu, Y., Standaert, F.-X., Pereira, O., Yung, M.: Practical leakage-resilient pseudorandom generators. In: Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS 2010, pp. 141–151. ACM, New York (2010)

Title: Time-Advantage Ratios Under Simple Transformations: Applications in Cryptography
Author: Maciej Skórski
Publisher: Springer International Publishing
Book: Cryptography and Information Security in the Balkans
Print ISBN: 978-3-319-29171-0

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

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-29172-7_6

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner