Modern cryptography relies on the intractability of computational problems. We present an approach to build cryptography from a new source of hardness: proving mathematical theorems. Unprovability results are abundant in mathematics and theoretical computer science, yet to our knowledge, they have not been used as a resource for cryptography.

Abstract. Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [C. Gentry, STOC ’09, ACM, New York, 2009, pp. 169–178; Z. Brakerski and V. Vaikuntanathan, FOCS ’11, IEEE Computer Society, Los Alamitos, CA, 2011, pp. 97–106], 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). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [S. Gorbunov, V. Vaikuntanathan, and H. Wee, STOC ’13, ACM, New York, 2013, pp. 545–554; D. Boneh et al., Eurocrypt ’14, Springer, Berlin, 2014, pp. 533–556], only accommodate circuits up to a predetermined depth, akin to leveled homomorphic encryption. In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth. Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes. So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation. An interesting question that has remained open for over a decade is whether the circular security assumptions enabling FHE can similarly benefit ABE. In this work, we introduce new lattice-based techniques to overcome the depth-dependency limitations: relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size; based on the evasive circular LWE assumption, a stronger variant of the recently proposed evasive LWE assumption [H. Wee, Eurocrypt ’22, Springer, Cham, Switzerland, 2022, pp. 217–241; R. Tsabary, Crypto ’22, Springer, Cham, Switzerland, 2022, pp. 535–559], we construct full-fledged ABE and predicate encryption (PE) schemes for circuits of unbounded depth and size. Our LFE, 1-key FE, and reusable garbling schemes achieve almost optimal succinctness (up to polynomial factors in the security parameter). Their ciphertexts and input encodings have sizes linear in the input length, while function digest, secret keys, and garbled circuits have constant sizes independent of circuit parameters (for Boolean outputs). In fact, this gives the first constant-size garbled circuits without relying on indistinguishability obfuscation. Our ABE and PE schemes offer short components, with master public key and ciphertext sizes linear in the attribute length and secret key being constant size.

Hamiltonian simulation is one of the most important problems in the field of quantum computing. There have been extended efforts on designing algorithms for faster simulation, and the evolution time T for the simulation greatly affect algorithm runtime as expected. While there are some specific types of Hamiltonians that can be fast-forwarded, i.e., simulated within time o(T), for some large classes of Hamiltonians (e.g., all local/sparse Hamiltonians), existing simulation algorithms require running time at least linear in the evolution time T. On the other hand, while there exist lower bounds of Ω(T) circuit size for some large classes of Hamiltonian, these lower bounds do not rule out the possibilities of Hamiltonian simulation with large but "low-depth" circuits by running things in parallel. As a result, physical systems with system size scaling with T can potentially do a fast-forwarding simulation. Therefore, it is intriguing whether we can achieve fast Hamiltonian simulation with the power of parallelism. In this work, we give a negative result for the above open problem in various settings. In the oracle model, we prove that there are time-independent sparse Hamiltonians that cannot be simulated via an oracle circuit of depth o(T). In the plain model, relying on the random oracle heuristic, we show that there exist time-independent local Hamiltonians and time-dependent geometrically local Hamiltonians on n qubits that cannot be simulated via an oracle circuit of depth o(T/n^c), where the Hamiltonians act on n qubits, and c is a constant. Lastly, we generalize the above results and show that any simulators that are geometrically local Hamiltonians cannot do the simulation much faster than parallel quantum algorithms.

Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, FOCS ’10; Brakerski-Vaikuntanathan, STOC ’11], 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). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov-Vaikuntanathan-Wee, STOC ’13; Boneh et al., Eurocrypt ’14], only accommodate circuits up to all predetermined depth, akin to leveled homomorphic encryption. In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth. Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes. So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation. Intriguingly, for over a decade, it has remained unclear whether the circular security assumptions empowering FHE can similarly benefit ABE. In this work, we introduce new lattice-based techniques to overcome the depth-dependency limitations: •Relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size.•Based on the evasive circular LWE assumption, a stronger variant of the recently proposed evasive LWE assumption [Wee, Eurocrypt ’22; Tsabary, Crypto ’22], we construct a full-fledged ABE scheme for circuits of unbounded depth and size. Our constructions eliminate the multiplicative overheads polynomial in depth from previous constructions. Our LFE, 1key FE, and reusable garbling schemes achieve almost optimal succinctness. Their ciphertexts and input encodings are proportional in length to the input, while function digest, secret keys, and garbled circuits maintain a constant size independent of circuit parameters. Our ABE schemes offer short components, with master public key and ciphertext sizes linear in the attribute length and secret key being constant-size.