Results 1931 - 1940 of 23898

A wiretap coding scheme for a pair of noisy channels (ChB, ChE) enables Alice to reliably communicate a message to Bob by sending its encoding over ChB, while hiding the message from an adversary Eve who obtains the same encoding over ChE.

A necessary condition for the feasibility of wiretap coding is that ChB is not a degradation of ChE, namely Eve cannot simulate Bob’s view. While insufficient in the information-theoretic setting, a recent work of Ishai, Korb, Lou, and Sahai (Crypto 2022) showed that the nondegradation condition is sufficient in the computational setting, assuming idealized flavors of obfuscation. The question of basing a similar feasibility result on standard cryptographic assumptions was left open, even in simple special cases.

In this work, we settle the question for all discrete memoryless channels where the (common) input alphabet of ChB and ChE is binary, and with arbitrary finite output alphabet, under standard (sub-exponential) hardness assumptions: namely those assumptions that imply indistinguishability obfuscation (Jain-Lin-Sahai 2021, 2022), and injective PRGs. In particular, this establishes the feasibility of computational wiretap coding when ChB is a binary symmetric channel with crossover probability p and ChE is a binary erasure channel with erasure probability e, where e > 2p.

On the information-theoretic side, our result builds on a new polytope characterization of channel degradation for pairs of binary-input channels, which may be of independent interest.

In this talk, I'll discuss new techniques for constructing cryptographic objects using indistinguishability obfuscation (iO). As a taste, our techniques enable us to construct
- public-key encryption with optimal hardness guarantees, and
- one-way functions with optimal direct product hardness (i.e., simultaneously solving independent instances scales according to the naive bound).

A key theme in our work is to combine iO with complexity-theoretic assumptions that go beyond P \neq NP. For instance, some of our results assume the co-non-deterministic hardness of SAT.

We also prove results of interest to complexity theory. For example, we use obfuscation to give a reduction from non-deterministically solving UNSAT to a solving a direct product version of Search-SAT.

This is joint work with Alex Lombardi.

We explore the possibility of obtaining general-purpose obfuscation for all circuits by way of making only simple, local, functionality preserving random perturbations in the circuit structure. Towards this goal, we use the additional structure provided by reversible circuits, but no additional algebraic structure. Our approach is rooted in statistical mechanics and can be thought of as locally “thermalizing” a circuit while preserving its functionality.

We analyze the security of this approach in two steps. First, we provide arguments towards its security for a relatively simple task: obfuscating random circuits of bounded length. Next we show how to construct fully-fledged obfuscators for all (unbounded length) circuits given an obfuscator for bounded-length, random reversible circuits. Here security is proven under a new assumption regarding the pseudorandomness of sufficiently-long random reversible circuits.

Our specific candidate obfuscators are very simple and relatively efficient: the obfuscated version of an n-wire, m-gate (reversible) circuit with security parameter κ has n wires and poly(n,κ)*m gates. We hope that our initial exploration will motivate further study of this alternative path to program obfuscation (and, hence, cryptography in general).

Joint work with Claudio Chamon, Eduardo R. Mucciolo, and Andrei E. Ruckenstein.

Abstract not available.

At least since the initial public proposal of public-key cryptography based on computational hardness assumptions (Diffie and Hellman, 1976), cryptographers have contemplated the possibility of a “one-way compiler” that translates computer programs into “unintelligible” ones that compute the same function. This vision has been formalized in the notion of indistinguishability obfuscation (iO), which over the past decade has emerged as a powerful and versatile tool for enabling a wide range of goals both within and beyond cryptography. In this talk, we will outline milestones in the conceptual and technical development of iO, and the tortuous decade-long journey toward its realization. We will convey the high-level ideas behind the recent constructions based on three well-studied hardness assumptions, as well as explore the emerging frontier: latest efforts to realize iO from simple-to-state assumptions over integer lattices. These advances form a robust foundation for obfuscation and raise intriguing open questions for future work. Together, they chart our ongoing expedition toward Obfustopia - a long-envisioned land where general-purpose obfuscation becomes both theoretically sound and practically attainable.