nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

5. Computationally Private Randomizing Polynomials and Their Applications

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

KI-gestützte Suche

Aus

Abstract

In this chapter, we study the notion of computational randomized encoding (cf. Definition 3.6) which relaxes the privacy property of statistical randomized encoding. We construct a computational encoding in \(\mathbf {NC}^{0}_{4}\) for every polynomial-time computable function, assuming the existence of a one-way function (OWF) in SREN. (The latter assumption is implied by most standard intractability assumptions used in cryptography.) This result is obtained by combining a variant of Yao’s garbled circuit technique with previous “information-theoretic” constructions of randomizing polynomials. We present several applications of computational randomized encoding. In particular, we relax the sufficient assumptions for parallel constructions of cryptographic primitives, obtain new parallel reductions between primitives, and simplify the design of constant-round protocols for multiparty computation.

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 Cryptography in NC 0

Nächstes Kapitel One-Way Functions with Optimal Output Locality

This similarity is not coincidental as both concepts were raised in the context of secure multiparty computation. Indeed, an information theoretic variant of Yao’s garbled circuit technique was already used in [93] to construct low-degree randomized encoding for NC ¹ functions.

Previous presentations of Yao’s garbled circuit relied on primitives that seem less likely to allow an NC ⁰ implementation. Specifically, [25, 115] require linear stretch PRG and [107] requires symmetric encryption that enjoys some additional properties.

This condition is redundant in the case of signatures and commitments, whose existence follows from the existence of a PRG. We will later describe a stronger result for such primitives.

By symmetric encryption we refer to (probabilistic) stateless encryption for multiple messages, where the parties do not maintain any state information other than the key. If parties are allowed to maintain synchronized states, symmetric encryption can be easily reduced in NC ⁰ to a PRG.

Applying the construction to circuits with a bounded fan-out, even linear length would suffice.

Security proofs for variants of this construction were given implicitly in [107, 128, 134] in the context of secure computation. However, they cannot be directly used in our context for different reasons. In particular, the analysis of [107] relies on a special form of symmetric encryption and does not achieve perfect correctness, while that of [128, 134] relies on a linear-stretch PRG.

In fact, each application of the encryption scheme will use some additional random bits. To simplify notation, we keep these random inputs implicit.

Specifically, the encryption is always invoked on messages whose length is bounded by \(\ell(n)\stackrel {\mathrm {def}}{{=}}O(|C_{n}|\cdot k)\), hence we can use ℓ(n)-one-time symmetric encryption.

In some cases, we will need to rely on perfect correctness, which we get “for free” in our main construction. See Table 4.2.

Similarly, assuming a linear-stretch PRG in NC ¹, we can obtain, for every NC function, a (non-adaptive single-oracle) IHS in which the user is in NC ⁰ and the oracle is in NC.

Assuming that factoring is intractable (or, more generally, that there exists a OWF in SREN) it is provably impossible to obtain an NC ⁰ reduction from PRFs to sublinear stretch PRGs or OWFs. See Sect. 4.8.

For concreteness, we refer here only to the case of symmetric encryption, the case of other primitives which are NC ⁰-reducible to a PRF (such as identification schemes and MACs) is analogous.

Similar examples are the NC ¹ transformation of one-to-one OWF to non-interactive commitment scheme (cf. [34]) and of distributionally OWF into standard OWF (cf. [90]).

Actually, for the composition theorem to go through, Definition 5.3 should be augmented by providing players and adversaries with auxiliary inputs. We ignore this technicality here, and note that the results in this section apply (with essentially the same proofs) to the augmented model as well.

To handle randomized functionalities we use the non-interactive secure reduction mentioned above. Now, we can (m−1)-securely reduce f to a single-output functionality by letting each party mask its output f _i with a private randomness. That is, f′((x ₁,r ₁)…,(x _m,r _m))=((f ₁(x ₁)⊕r ₁)∘⋯∘(f ₁(x _m)⊕r _m)). As both reductions are non-interactive the resulting reduction is also non-interactive. Moreover, the circuit size of f′ is linear in the size of the circuit that computes the original function.

19.

Applebaum, B., Ishai, Y., Kushilevitz, E.: How to garble arithmetic circuits. In: Proc. of 52nd FOCS, pp. 120–129 (2011)

25.

Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: Proc. of 22nd STOC, pp. 503–513 (1990)

26.

Bellare, M., Yung, M.: Certifying permutations: noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptol. 9(3), 149–166 (1996). Preliminary version in Proc. of CRYPTO ’92 CrossRefMATHMathSciNet

27.

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. of 20th STOC, pp. 1–10 (1988)

34.

Blum, M.: Coin flipping by telephone: a protocol for solving impossible problems. SIGACT News 15(1), 23–27 (1983) CrossRef

41.

Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000) CrossRefMATHMathSciNet

42.

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: Proc. of 42nd FOCS, pp. 136–145 (2001)

45.

Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: Proc. of 20th STOC, pp. 11–19 (1988)

49.

Cramer, R., Fehr, S., Ishai, Y., Kushilevitz, E.: Efficient multi-party computation over rings. In: Advances in Cryptology: Proc. of EUROCRYPT ’03, pp. 596–613 (2003) CrossRef

52.

Damgård, I., Ishai, Y.: Scalable secure multiparty computation. In: Advances in Cryptology: Proc. of CRYPTO ’06, pp. 501–520 (2006)

59.

Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1–28 (2000). Preliminary version in Proc. of 31st FOCS, 1990 CrossRefMathSciNet

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

74.

Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33, 792–807 (1986) CrossRefMathSciNet

75.

Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptol. 9(2), 167–189 (1996) CrossRefMATHMathSciNet

78.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game (extended abstract). In: Proc. of 19th STOC, pp. 218–229 (1987)

80.

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984). Preliminary version in Proc. of STOC ’82 CrossRefMATHMathSciNet

83.

Haitner, I., Reingold, O., Vadhan, S.P.: Efficiency improvements in constructing pseudorandom generators from one-way functions. In: Proc. of 42nd STOC, pp. 437–446 (2010)

90.

Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography. In: Proc. of 30th FOCS, pp. 230–235 (1989)

92.

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: Proc. of 41st FOCS, pp. 294–304 (2000)

93.

Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Proc. of 29th ICALP, pp. 244–256 (2002)

107.

Lindell, Y., Pinkas, B.: A proof of Yao’s protocol for secure two-party computation. Electron. Colloq. Comput. Complex. 11, 063 (2004)

108.

Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform, and learnability. J. ACM 40(3), 607–620 (1993). Preliminary version in Proc. of 30th FOCS, 1989 MATHMathSciNet

114.

Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4, 151–158 (1991) MATHMathSciNet

115.

Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: Proc. of 1st ACM Conference on Electronic Commerce, pp. 129–139 (1999) CrossRef

116.

Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. J. Comput. Syst. Sci. Int. 58(2), 336–375 (1999) CrossRefMATHMathSciNet

117.

Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. J. ACM 51(2), 231–262 (2004). Preliminary version in Proc. of 38th FOCS, 1997 MATHMathSciNet

126.

Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Proc. of 1st TCC ’04. LNCS, vol. 2951, pp. 1–20 (2004)

128.

Rogaway, P.: The round complexity of secure protocols. PhD thesis, MIT (1991)

130.

Shannon, C.E.: Communication theory of secrecy systems. Bell Syst. Tech. J. 28(4), 656–715 (1949) CrossRefMATHMathSciNet

134.

Tate, S.R., Xu, K.: On garbled circuits and constant round secure function evaluation. CoPS Lab Technical Report 2003-02, University of North Texas (2003)

138.

Viola, E.: On constructing parallel pseudorandom generators from one-way functions. In: Proc. of 20th Conference on Computational Complexity (CCC), pp. 183–197 (2005)

145.

Yao, A.C.: How to generate and exchange secrets. In: Proc. of 27th FOCS, pp. 162–167 (1986)

Titel: Computationally Private Randomizing Polynomials and Their Applications
verfasst von: Benny Applebaum
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_5

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