Results 1881 - 1890 of 23883

We revisit the question of computing on encrypted data, in the following secret-key setting. A client uploads an encryption of a big input X to an untrusted server, and then wishes to make an unbounded number of queries q(X) while hiding q and X from the server and using only its secret key. How efficiently can this be done and under what assumptions?

We present efficient solutions for useful special cases, including matrix-vector products and private information retrieval (PIR), under either the standard Learning Parity with Noise assumption, in a parameter regime not known to imply public-key encryption, or new assumptions related to the hardness of learning a secret linear subspace from noisy samples. The latter assumptions yield efficiency features that are not met by any existing solutions.

Our core idea, inspired by prior works on PIR with preprocessing, is to encode the input X and the queries q using a pair of secret dual codes, while avoiding linear algebra attacks by adding noise.

Based on joint works with Fabrice Benhamouda, Caicai Chen, Shai Halevi, Hugo Krawczyk, Tamer Mour, Tal Rabin, and Alon Rosen

Obfuscation of quantum programs is an emerging research area in cryptography. Previous works have primarily focused on obfuscating quantum programs that implement classical functions. In this talk, I will present recent advances that go beyond this limitation: a new obfuscation scheme capable of handling arbitrary quantum programs that implement unitary transformations, including those with auxiliary quantum states. I will give a high-level overview of the core techniques and discuss where the result might take us next.

Based on joint work with Miryam Huang.

The goal of obfuscating efficient quantum computation is a relatively recently explored frontier in cryptography. This talk will overview the state of quantum obfuscation and explore a couple of core techniques that have been instrumental in developing the first obfuscation schemes for large classes of quantum programs.

Unclonable cryptography is an emerging area in quantum cryptography that leverages the no-cloning principle of quantum mechanics to achieve novel primitives that are impossible to achieve classically. In this talk, I will discuss new variants of program obfuscation that are tailored for designing unclonable cryptographic primitives. In addition, I will also discuss the important role program obfuscation, and in particular indistinguishability obfuscation, has played in expanding the feasibility landscape of unclonable cryptography.

We present a recent approach to construct succinct randomized encodings with close to optimal parameters, assuming the intractability of computational problems related to lattices.

Succinct randomized encodings allow encoding the input $x$ of a time-$t$ uniform computation $M(x)$ in sub-linear time $o(t)$. The resulting encoding $\Tilde{x}$ allows recovering the result of the computation $M(x)$, but hides any other information about $x$. These encodings have powerful applications, including time-lock puzzles, reducing communication in MPC, and bootstrapping advanced encryption schemes.

Until not long ago, the only known constructions were based on indistinguishability obfuscation, and in particular were not based on standard post-quantum assumptions. In terms of efficiency, these constructions' encoding time is $\rm{polylog}(t)$, essentially the best one can hope for. Recently, a new construction was presented based on Circular Learning with Errors, an assumption similar to the one used in fully-homomorphic encryption schemes, and which is widely considered to be post-quantum resistant. However, the encoding efficiency significantly falls behind obfuscation-based scheme and is $\approx \sqrt{t} \cdot s$, where $s$ is the space of the computation.

We construct, under the same assumption, succinct randomized encodings with encoding time $\approx t^{\varepsilon} \cdot s$ for arbitrarily small constant $\varepsilon<1$. Our construction is relatively simple, generic and relies on any laconic function evaluation scheme that satisfies a natural {\em efficiency preservation} property.
Under sub-exponential assumptions, the encoding time can be further reduced to $\approx \sqrt{s}$, but at the account of a huge security loss.

As a corollary, assuming also bounded-space languages that are worst-case hard-to-parallelize, we obtain time-lock puzzles with an arbitrary polynomial gap between encoding and decoding times.
This is a joint work with Nir Bitansky.

Although we have known fully homomorphic encryption (FHE) from circular security assumptions for over a decade, there is still a significant gap in understanding related homomorphic primitives supporting all unrestricted polynomial-size computations. One prominent example is attribute-based encryption (ABE). Previous constructions either only support bounded-depth circuits or require the heavy machinery of indistinguishability obfuscation. In this work, we introduce new lattice-based techniques to overcome this limitation. In this talk, I will introduce the background, explain our new constructions, and discuss interesting open questions. Joint work with Yao-Ching Hsieh and Huijia (Rachel) Lin.

A central line of inquiry in the study of indistinguishability obfuscation (IO) is to minimize the size of the obfuscation. Today we know how to obfuscate programs represented as Turing machines, where the size of the obfuscation grows only with the input size and not with the machine's running time. Jain and Jin [FOCS 2022] showed how to remove the dependency on the input size for functionally equivalent programs where equivalence can be proven in Cook's theory PV, assuming IO for circuits and LWE.

In this work we investigate the limits of the pursuit of succinct obfuscation. We consider the task of obfuscating a program with a large description, most of which can be made public while some portion of the description is secret. We put forth a new notion of \emph{fully succinct IO} where the size of obfuscated program only grows with the size of the program's secret part and not with the public part or with the input size.

Starting with input-succinct IO for PV-equivalent machines, we construct fully succinct IO for the same class of programs. We refer to such an obfuscation as fully succinct pv-IO. Next, we show how to bootstrap our fully succinct pv-IO to achieve full IO security. Our bootstrapping theorems are based on succinct cryptographic primitives with seemingly weaker functionality: either succinct witness encryption or SNARGs for NP with unique proofs. We also require that the correctness of these primitives can be proven in theory PV. We show that these assumptions are sufficient and necessary.

We demonstrate several applications of fully succinct IO and pv-IO:
We give the first IO construction where the size of the obfuscated program is less than twice the size of the original program for a large class of useful programs.
We show how to avoid padding the program before obfuscating it -- a step often necessitated by security analysis -- by replacing the padding with a public random string.
Assuming only fully succinct pv-IO and other standard assumptions, we give the first construction of succinct computational secret sharing for access structures represented by polynomial-size monotone circuits where the share size does not grow with the size of the access structure.

Indistinguishability obfuscation (iO) is a powerful cryptographic primitive and has been quoted as the "swiss army-knife of modern cryptography". Most prior works on iO focused on theoretical feasibility, and paid less attention to the efficiency of the constructions. As a result, almost all prior constructions stopped at achieving polynomial efficiency without worrying about how large the polynomial is. In fact, it has even been conjectured that a polynomial dependence on the input length is necessary. We show that if the two circuits to be obfuscated enjoy a succinct propositional logic proof of equivalence, then we can create obfuscated versions of these programs that are computationally indistinguishable; and importantly, the obfuscated program's efficiency is quasi-linear in the circuit size and proof size. We show that our quasi-linear iO construction also leads to new applications. Specifically, we show how to achieve quasi-linear efficiency for 1) iO for Turing Machines with unbounded inputs, and 2) multi-input functional encryption, also assuming succinct proofs of equivalence.