nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Simulating Auxiliary Inputs, Revisited

verfasst von : Maciej Skórski

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

For any pair (X, Z) of correlated random variables we can think of Z as a randomized function of X. If the domain of Z is small, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as simulating auxiliary inputs. This idea of simulating auxiliary information turns out to be a very usefull tool, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results:

(a)

We present a novel boosting algorithm for constructing the simulator. This boosting proof is of independent interest, as it shows how to handle “negative mass” issues when constructing probability measures by shifting distinguishers in descent algorithms. Our technique essentially fixes the flaw in the TCC’14 paper “How to Fake Auxiliary Inputs”.

(b)

The complexity of our simulator is better than in previous works, including results derived from the uniform min-max theorem due to Vadhan and Zheng. To achieve \((s,\epsilon )\)-indistinguishability we need the complexity \(O\left( s\cdot 2^{5\ell }\epsilon ^{-2}\right) \) in time/circuit size, which improve previous bounds by a factor of \(\epsilon ^{-2}\). In particular, with we get meaningful provable security for the EUROCRYPT’09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like \(\mathsf {AES256}\).

Our boosting technique utilizes a two-step approach. In the first step we shift the current result (as in gradient or sub-gradient descent algorithms) and in the separate step we fix the biggest non-negative mass constraint violation (if applicable).

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

Vorheriges Kapitel Leakage Resilient One-Way Functions: The Auxiliary-Input Setting

Nächstes Kapitel Pseudoentropy: Lower-Bounds for Chain Rules and Transformations

Nur mit Berechtigung zugänglich

Indeed, consider the simplest case \(\mathcal {Z} = \{0,1\}\), define X to be uniform over \(\mathcal {X}=\{0,1\}^n\), and take \(Z=f(X)\) where f is a function which is 0.5-hard to predict by circuits exponential in n, Then (X, h(X)) and (X, Z) are at least \(\frac{1}{4}\)-away in total variation.

If two distributions can be distinguished by a randomized circuit, we can fix a specific choice of coins to achieve at least the same advantage.

We briefly sketch the idea of the proof: note first that it is easy to construct a simulator for every single distinguisher. Having realized that, we can use the min-max theorem to switch the quantifiers and get one simulator for all distinguishers.

This is a direct consequence of the fact that we want \(\ell \) to fit poly-preserving reductions.

The oracle evaluates the distance of the given candidate solution and the simulated distribution, answering with a distiguisher if the distance is smaller than required.

As we already mentioned, we can assume that \(\textsc {D}\) is deterministic without loss of generality. Then all the terms in the equation are well-defined.

By definition, it requires computing the average of \(\textsc {D}(x,\cdot )\) over \(2^{\ell }\) elements.

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}\).

This is a standard assumption in indistinguishability proofs. We can always extend the class by adding \(-\textsc {D}\) for every \(\textsc {D}\in \mathcal {D}\), which increases the complexity only by 1.

The RAM model.

It’s not possible to extend the result from [TTV09] directly, the issue is that the constraint on the marginal distribution are not preserved. That’s why [JP14] and this paper require much more extra work.

Or cam be concluded from the parallelogram identity \((x+y)^2 + (x-y)^2 = x^2+y^2\).

[BL13]

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

[CLP15]

Chung, K.-M., Lui, E., Pass, R.: From weak to strong zero-knowledge and applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 66–92. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46494-6_4

[DP08]

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

[DP10]

Dodis, Y., Pietrzak, K.: Leakage-resilient pseudorandom functions and side-channel attacks on Feistel networks. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 21–40. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14623-7_2 CrossRef

[DTT09]

De, A., Trevisan, L., Tulsiani, M.: Non-uniform attacks against one-way functions and prgs. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 16, p. 113 (2009)

[FK99]

Frieze, A.M., Kannan, R.: Quick approximation to matrices and applications. Combinatorica 19(2), 175–220 (1999)MathSciNetCrossRefMATH

[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). doi:10.1007/978-3-642-33027-8_13 CrossRef

[FR12]

Fuller, B., Reyzin, L.: Computational entropy and information leakage. Cryptology ePrint Archive, report 2012/466 (2012). http://eprint.iacr.org/

[GW11]

Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) STOC, pp. 99–108. ACM (2011)

[Imp95]

Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: 36th Annual Symposium on Foundations of Computer Science, pp. 538–545. IEEE (1995)

[JP14]

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

[LM94]

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

[Pie09]

Pietrzak, K.: A leakage-resilient mode of operation. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 462–482. Springer, Heidelberg (2009). doi:10.1007/978-3-642-01001-9_27 CrossRef

[Pie15]

Pietrzak, K.: Private communication, May 2015

[RTTV08]

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

[Skó15]

Skórski, M.: Time-advantage ratios under simple transformations: applications in cryptography. Cryptography and Information Security in the Balkans - Second International Conference, BalkanCryptSec: Koper, Slovenia, 3–4 September 2015. Revised Selected Papers, pp. 79–91 (2015)

[TTV09]

Trevisan, L., Tulsiani, M., Vadhan, S.: Regularity, boosting, and efficiently simulating every high-entropy distribution. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, Washington, DC, USA, CCC 2009, pp. 126–136. IEEE Computer Society (2009)

[VZ13]

Vadhan, S., Zheng, C.J.: A uniform min-max theorem with applications in cryptography. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 93–110. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40041-4_6 CrossRef

[YS13]

Yu, Y., Standaert, F.-X.: 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). doi:10.1007/978-3-642-36095-4_15 CrossRef

Titel: Simulating Auxiliary Inputs, Revisited
verfasst von: Maciej Skórski
Verlag: Springer Berlin Heidelberg
Buch: Theory of Cryptography
Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-53641-4_7

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"

Premium Partner