Results 1851 - 1860 of 23856
In this talk, we will construct somewhat homomorphic encryption from the sparse learning-parities-with-noise problem, along with an assumption that implies linearly homomorphic encryption (e.g., the decisional Diffie-Hellman or decisional composite residuosity assumptions). The resulting schemes support an a-priori bounded number of homomorphic operations: o(\log \lambda) multiplications followed by poly(\lambda) additions, where \lambda is a security parameter. This gives the first constructions of somewhat homomorphic encryption for the class of bounded-degree polynomials that do not rely on lattice assumptions or bilinear maps. Moreover, our schemes are conceptually simple: much as in Gentry, Sahai, and Waters’ fully homomorphic encryption scheme and in Dao, Ishai, Jain, and Lin’s homomorphic secret-sharing scheme, ciphertexts in our scheme are matrices, homomorphic addition is matrix addition, and homomorphic multiplication is matrix multiplication.
Joint work with Henry Corrigan-Gibbs, Yael Kalai, and Vinod Vaikuntanathan (published at EUROCRYPT 2025).
Phillip Gibbons is a Professor in the Computer Science Department and in the Electrical & Computer Engineering Department at Carnegie Mellon University (CMU). He received his Ph.D. in Computer Science from the University of California at Berkeley. Prior to...
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.