Skip to main content

Über dieses Buch

Locally computable (NC0) functions are "simple" functions for which every bit of the output can be computed by reading a small number of bits of their input. The study of locally computable cryptography attempts to construct cryptographic functions that achieve this strong notion of simplicity and simultaneously provide a high level of security. Such constructions are highly parallelizable and they can be realized by Boolean circuits of constant depth.

This book establishes, for the first time, the possibility of local implementations for many basic cryptographic primitives such as one-way functions, pseudorandom generators, encryption schemes and digital signatures. It also extends these results to other stronger notions of locality, and addresses a wide variety of fundamental questions about local cryptography. The author's related thesis was honorably mentioned (runner-up) for the ACM Dissertation Award in 2007, and this book includes some expanded sections and proofs, and notes on recent developments.

The book assumes only a minimal background in computational complexity and cryptography and is therefore suitable for graduate students or researchers in related areas who are interested in parallel cryptography. It also introduces general techniques and tools which are likely to interest experts in the area.



Chapter 1. Introduction

This book studies the parallel-time complexity of cryptography. Specifically, we study the possibility of implementing cryptographic tasks by NC 0 functions, namely by functions in which each output bit depends on a constant number of input bits. We provide strong evidence for the possibility of cryptography in NC 0, settling a longstanding open question.
Benny Applebaum

Chapter 2. Preliminaries and Definitions

This chapter presents the basic notation and definitions used in this book. This includes the notions of statistical and computational indistinguishability and some of their properties (Sect. 2.2), as well as definitions and conventions regarding several computational models (Sect. 2.3). We also define the main complexity measures mentioned in this book, namely, output locality, input locality, and algebraic degree, and we investigate some of their simple properties (Sect. 2.4).
Benny Applebaum

Chapter 3. Randomized Encoding of Functions

In this chapter we formally introduce our notion of randomized encoding which will be used as a central tool in subsequent chapters. In Sect. 3.1 we introduce several variants of randomized encoding and in Sect. 3.2 we prove some of their useful properties. Finally, in Sect. 3.3 we discuss other aspects and limitations of randomized encoding such as the necessity of randomness, the expressive power of encoding in NC 0, and the lowest output locality which is sufficient to encode all functions.
Benny Applebaum

Chapter 4. Cryptography in NC 0

In this chapter we show that randomized encoding preserves the security of many cryptographic primitives. We also construct an (information-theoretic) encoding in \(\mathbf{NC}^{0}_{4}\) for any function in NC 1 or even ⊕L/poly. The combination of these results gives a compiler that takes as an input a code of an NC 1 implementation of some cryptographic primitive and generates an \(\mathbf{NC}^{0}_{4}\) implementation of the same primitive.
Benny Applebaum

Chapter 5. Computationally Private Randomizing Polynomials and Their Applications

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.
Benny Applebaum

Chapter 6. One-Way Functions with Optimal Output Locality

In Chap. 4 it was shown that, under relatively mild assumptions, there exist one-way functions (OWFs) in \(\mathbf {NC}^{0}_{4}\). This result is not far from optimal as there is no OWF in \(\mathbf {NC}^{0}_{2}\). In this chapter we partially close this gap by providing an evidence for the existence of OWF in \(\mathbf {NC}^{0}_{3}\). This is done in two steps: (1) we describe a new variant of randomized encoding that allows us to obtain a OWF in \(\mathbf {NC}^{0}_{3}\) from a “robust” OWF which remains hard to invert even when some information on the preimage x is leaked; (2) we show how to construct a robust OWF assuming that a random function of (arbitrarily large) constant locality is one-way. (A similar assumption was previously made by Goldreich in Electron. Colloq. Comput. Complex. 7:090, 2000.)
Benny Applebaum

Chapter 7. On Pseudorandom Generators with Linear Stretch in NC 0

We consider the question of constructing cryptographic pseudorandom generators in NC 0 with large stretch. Our previous constructions of such PRGs were limited to stretching a seed of n bits to n+o(n) bits. This leaves open the existence of a PRG with a linear (let alone superlinear) stretch in NC 0. In this chapter we study this question and obtain the following main results: (1) We show that the existence of a linear-stretch PRG in NC 0 implies non-trivial hardness of approximation results without relying on PCP machinery. In particular, it implies that Max3SAT is hard to approximate to within some multiplicative constant. (2) We construct a linear-stretch PRG in NC 0 under a specific intractability assumption related to the hardness of decoding “sparsely generated” linear codes. Such an assumption was previously conjectured by Alekhnovich (Proc. of 44th FOCS, pp. 298–307, 2003).
Benny Applebaum

Chapter 8. Cryptography with Constant Input Locality

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.
Benny Applebaum


Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.



Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!