Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

8. Cryptography with Constant Input Locality

verfasst von : Benny Applebaum

Erschienen in: Cryptography in Constant Parallel Time

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

So far we studied the possibility of implementing cryptographic tasks using functions with constant output locality. In this chapter we turn to the dual question of constant input locality. In particular, we ask: Which cryptographic primitives (if any) can be realized by functions in which every bit of the input influences only a constant number of bits of the output? We prove several positive and negative results that together form the following characterization. Essentially, primitives that require some form of non-malleability (e.g., digital signatures) cannot be realized with constant input locality, while primitives that require secrecy (e.g., encryption schemes) can be implemented with constant input locality. Some of our constructions enjoy both constant input locality and constant output locality, giving rise to cryptographic hardware that has constant-depth, constant fan-in and constant fan-out.

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 On Pseudorandom Generators with Linear Stretch in NC 0
Fußnoten
1
Our collections are indexed by a public random key. That is, \(\left \{ G_{z}\right \}_{z\in \{0,1\}^{*}}\) is a collection of PRGs if for every z the function G z expands its input and the pair (z,G z (x)) is pseudorandom for random x and z. In a subsequent work [18], it is shown how to upgrade our results and construct a single PRG with an optimal locality (as opposed to collection). See Remark 8.2.
 
2
We remark that in Chap. 7 one had to rely on a specially made extractor in order to maintain the large stretch of the PRG. In particular, the leftover hashing lemma could not be used there.
 
3
In fact, we may allow ε to decrease with n. In such case, we might get a non-negligible decryption error. This can be fixed (without increasing the rank or the degree of the encryption function) by repeating the encryption with independent fresh randomness. Details omitted.
 
4
The input locality is in+1 since the input locality of the x’s in \(\hat {L}_{z}\) is only 1. See Remark 8.1.
 
5
In more detail, suppose that we have a OWF f:{0,1} n →{0,1} m which is t-to-one, where t=t(n) is computable in polynomial time. Then, the construction of [86] (see also [87]) can be described in two steps: First we define a collection g y,r (x)=(f(x),h y (x),〈x,r〉) where \(\left \{ h_{y}\right \}\) is a collection of pairwise independent hash functions that map n bits to log(t)+2 bits. This function is shown to have large “pseudoentropy”, that is, when y,r and x are randomly chosen, the bit 〈x,r〉 has low entropy given the values of g(x),h y (x),y and r, but it is computationally unpredictable. Then, in the second step we use many instances of g to construct a PRG. That is, we define the function \(G_{w,\vec{y},\vec{r}}(\vec {x})=h'_{w}(g_{y^{(1)},r^{(1)}}(x^{(1)}),\ldots ,g_{y^{(k)},r^{(k)}}(x^{(k)}))\), where \(\left \{ h'_{w}\right \}\) is a collection of pairwise independent hash functions of output length ℓ, and k,ℓ are some explicit functions of n,m and t. Hence, when \(z=(w,\vec {y},\vec{r})\) is fixed, and the hash functions are implemented via affine transformations, \(G_{z}(\vec{x})\) can be written as \(L_{z}(\vec {x},f(x^{(1)}),\ldots,f(x^{k}))\) where L z is an affine function.
 
6
When querying the signing oracle, the adversary chooses only the message and is not allowed to choose the randomness which the oracle uses to produce the signature.
 
7
When the locality in(n) of S k is logarithmic (for every fixed key k), this approach yields an attack that succeeds with probability 1/n Θ(log(n)).
 
Literatur
5.
Alekhnovich, M.: More on average case vs approximation complexity. In: Proc. of 44th FOCS, pp. 298–307 (2003)
18.
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography by cellular automata or how fast can complexity emerge in nature? In: ICS, pp. 1–19 (2010)
20.
Applebaum, B., Moses, Y.: Locally computable UOWHF with linear shrinkage. In: Advances in Cryptology: Proc. of EUROCRYPT ’13 (2013)
29.
Bennett, C., Grinstein, C.: Role of irreversibility in stabilizing complex and nonenergodic behavior in locally interacting discrete systems. Phys. Rev. Lett. 55, 657–660 (1985) CrossRef
30.
Berlekamp, E., Conway, J., Guy, R.: Winning Ways for Your Mathematical Plays. Academic Press, New York (1983)
31.
Berlekamp, E.R., McEliece, R.J., van Tilborg, H.C.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978) CrossRefMATH
32.
Blum, A., Furst, M., Kearns, M., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Advances in Cryptology: Proc. of CRYPTO ’93. LNCS, vol. 773, pp. 278–291 (1994) CrossRef
33.
Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506–519 (2003). Preliminary version in Proc. of 32nd STOC, 2000 CrossRefMathSciNet
34.
Blum, M.: Coin flipping by telephone: a protocol for solving impossible problems. SIGACT News 15(1), 23–27 (1983) CrossRef
36.
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13, 850–864 (1984). Preliminary version in FOCS 82 CrossRefMATHMathSciNet
48.
Cook, S.A.: The complexity of theorem-proving procedures. In: Proc. of 3rd STOC, pp. 151–158. ACM, New York (1971)
50.
Cryan, M., Miltersen, P.B.: On pseudorandom generators in NC0. In: Proc. of 26th MFCS (2001)
57.
62.
Feldman, V., Gopalan, P., Khot, S., Ponnuswami, A.K.: New results for learning noisy parities and halfspaces. In: Proc. of 47th FOCS, pp. 563–574 (2006)
65.
69.
Goldreich, O.: Candidate one-way functions based on expander graphs. Electron. Colloq. Comput. Complex. 7, 090 (2000)
70.
Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001) CrossRef
72.
Goldreich, O.: Foundations of Cryptography: Basic Applications. Cambridge University Press, Cambridge (2004) CrossRef
76.
Goldreich, O., Krawczyk, H., Luby, M.: On the existence of pseudorandom generators. SIAM J. Comput. 22(6), 1163–1175 (1993). Preliminary version in Proc. of 29th FOCS, 1988 CrossRefMATHMathSciNet
77.
Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. In: Proc. of 21st STOC, pp. 25–32 (1989)
86.
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999) CrossRefMATHMathSciNet
87.
Holenstein, T.: Pseudorandom generators from one-way functions: a simple construction for any hardness. In: Proc. of 3rd TCC, pp. 443–461 (2006)
88.
Hopper, N.J., Blum, M.: Secure human identification protocols. In: Advances in Cryptology: Proc. of ASIACRYPT ’01. LNCS, vol. 2248, pp. 52–66 (2001)
90.
Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography. In: Proc. of 30th FOCS, pp. 230–235 (1989)
96.
Janwa, H., Moreno, O.: McEliece public key cryptosystems using algebraic-geometric codes. Des. Codes Cryptogr. 8(3), 293–307 (1996) CrossRefMATHMathSciNet
97.
Juels, A., Weis, S.: Authenticating pervasive devices with human protocols. In: Advances in Cryptology: Proc. of CRYPTO ’05, pp. 293–308 (2005)
99.
Katz, J., Shin, J.-S.: Parallel and concurrent security of the HB and HB+ protocols. In: Advances in Cryptology: Proc. of Eurocrypt’06, pp. 73–87 (2006)
100.
Katz, J., Yung, M.: Complete characterization of security notions for probabilistic private-key encryption. In: Proc. of 32nd STOC, pp. 245–254 (2000)
101.
Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R.E., Sellie, L.: On the learnability of discrete distributions. In: Proc. of 26th STOC, pp. 273–282 (1994)
102.
109.
Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Proc. of 9th RANDOM (2005)
110.
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Technical Report DSN PR 42-44, Jet Prop. Lab. (1978)
111.
Moore, E.F. (ed.): Sequential Machines: Selected Papers. Addison-Wesley/Longman, Reading/Harlow (1964) MATH
112.
Mossel, E., Shpilka, A., Trevisan, L.: On ε-biased generators in NC0. In: Proc. of 44th FOCS, pp. 136–145 (2003)
118.
Neumann, J.V.: Theory of Self-Reproducing Automata. University of Illinois Press, Champaign (1966)
121.
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. Int. 43, 425–440 (1991). Preliminary version in Proc. of 20th STOC, 1988 CrossRefMATHMathSciNet
132.
135.
Varshamov, R.R.: Estimate of the number of signals in error correcting codes. Dokl. Akad. Nauk SSSR 117, 739–741 (1957) MATHMathSciNet
136.
Vichniac, G.Y.: Simulating physics with cellular automata. Phys. D, Nonlinear Phenom. 10(1–2), 96–115 (1984) CrossRefMathSciNet
143.
Wolfram, S.: Universality and complexity in cellular automata. Phys. D, Nonlinear Phenom. 10(1–2), 1–35 (1984) CrossRefMathSciNet
144.
Yao, A.C.: Theory and application of trapdoor functions. In: Proc. of 23rd FOCS, pp. 80–91 (1982)
Metadaten
Titel
Cryptography with Constant Input Locality
verfasst von
Benny Applebaum
Copyright-Jahr
2014
Verlag
Springer Berlin Heidelberg
Buch
Cryptography in Constant Parallel Time

Print ISBN: 978-3-642-17366-0

Electronic ISBN: 978-3-642-17367-7

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-642-17367-7_8