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.

The random oracle model (ROM) allows us to opti-mistically reason about security properties of cryptographic hash functions, and has been hugely influential in designing practical cryptosystems. But it is overly optimistic against non-uniform adversaries, and often suggests security properties and security levels unachievable by any real hash function. To reconcile with this discrepancy, Unruh [CRYPTO '07] proposed the auxiliary-input random oracle model (AI-ROM), where a non-uniform attacker additionally gets a bounded amount of advice about the random oracle. Proving security in the AI-ROM is often much more difficult, but a series of works starting with Unruh provided useful technical tools to do so. Although these tools lead to good results in the information-theoretic setting, they are unsatisfactory in the computational setting, where the random oracle is used alongside other computational hardness assumptions. At the most basic level, we did not even know whether it is possible to efficiently simulate random oracle queries given auxiliary input, which has remained as an explicit open problem since the work of Unruh. In this work, we resolve the above open problem and show how to efficiently simulate auxiliary-input random oracles. Moreover, the simulation has low concrete overhead, leading to small losses in exact security. We use it to prove the security of a broad class of computational schemes in the AI-ROM, including the first non-interactive zero-knowledge (NIZK) scheme in the AI-ROM. As a tool of independent interest, we develop a new notion of ultra-secure pseudorandom functions with fast RAM evaluation, which can achieve$2^{\lambda}$security while having sublinear$\mathrm{o}(\lambda)$evaluation time.

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.

3D medical image registration is of great clinical importance. However, supervised learning methods require a large amount of accurately annotated corresponding control points (or morphing), which are very difficult to obtain. Unsupervised learning methods ease the burden of manual annotation by exploiting unlabeled data without supervision. In this article, we propose a new unsupervised learning method using convolutional neural networks under an end-to-end framework, Volume Tweening Network (VTN), for 3D medical image registration. We propose three innovative technical components: (1) An end-to-end cascading scheme that resolves large displacement; (2) An efficient integration of affine registration network; and (3) An additional invertibility loss that encourages backward consistency. Experiments demonstrate that our algorithm is 880x faster (or 3.3x faster without GPU acceleration) than traditional optimization-based methods and achieves state-of-the-art performance in medical image registration.