@inbook{9245, abstract = {Tissue morphogenesis is driven by mechanical forces triggering cell movements and shape changes. Quantitatively measuring tension within tissues is of great importance for understanding the role of mechanical signals acting on the cell and tissue level during morphogenesis. Here we introduce laser ablation as a useful tool to probe tissue tension within the granulosa layer, an epithelial monolayer of somatic cells that surround the zebrafish female gamete during folliculogenesis. We describe in detail how to isolate follicles, mount samples, perform laser surgery, and analyze the data.}, author = {Xia, Peng and Heisenberg, Carl-Philipp J}, booktitle = {Germline Development in the Zebrafish}, editor = {Dosch, Roland}, isbn = {978-1-0716-0969-9}, issn = {1940-6029}, keywords = {Tissue tension, Morphogenesis, Laser ablation, Zebrafish folliculogenesis, Granulosa cells}, pages = {117--128}, publisher = {Humana Press}, title = {{Quantifying tissue tension in the granulosa layer after laser surgery}}, doi = {10.1007/978-1-0716-0970-5_10}, volume = {2218}, year = {2021}, } @inproceedings{15280, author = {Balazs, Daniel and Cimada da Silva, Jessica and Dunbar, Tyler and Ibáñez, Maria and Hanrath, Tobias}, booktitle = {Proceedings of the Internet NanoGe Conference on Nanocrystals}, location = {Virtual}, publisher = {Fundació de la comunitat valenciana SCITO}, title = {{Controlled reactive assembly of colloidal nanocrystal superlattices: Mechanism and kinetics}}, doi = {10.29363/nanoge.incnc.2021.050}, year = {2021}, } @inproceedings{10410, abstract = {The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.}, author = {Kamath Hosdurg, Chethan and Klein, Karen and Pietrzak, Krzysztof Z and Walter, Michael}, booktitle = {19th International Conference}, isbn = {9-783-0309-0452-4}, issn = {1611-3349}, location = {Raleigh, NC, United States}, pages = {550--581}, publisher = {Springer Nature}, title = {{The cost of adaptivity in security games on graphs}}, doi = {10.1007/978-3-030-90453-1_19}, volume = {13043}, year = {2021}, } @inproceedings{10409, abstract = {We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a SO(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(δwlog(S)) , δ being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity. with only a SO(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(δwlog(S)) , δ being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.}, author = {Kamath Hosdurg, Chethan and Klein, Karen and Pietrzak, Krzysztof Z}, booktitle = {19th International Conference}, isbn = {9-783-0309-0452-4}, issn = {1611-3349}, location = {Raleigh, NC, United States}, pages = {486--517}, publisher = {Springer Nature}, title = {{On treewidth, separators and Yao’s garbling}}, doi = {10.1007/978-3-030-90453-1_17}, volume = {13043 }, year = {2021}, } @inproceedings{10048, abstract = {The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques. }, author = {Kamath Hosdurg, Chethan and Klein, Karen and Pietrzak, Krzysztof Z and Walter, Michael}, booktitle = {19th Theory of Cryptography Conference 2021}, location = {Raleigh, NC, United States}, publisher = {International Association for Cryptologic Research}, title = {{The cost of adaptivity in security games on graphs}}, year = {2021}, } @inproceedings{10044, abstract = {We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(d w log(S)), d being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.}, author = {Kamath Hosdurg, Chethan and Klein, Karen and Pietrzak, Krzysztof Z}, booktitle = {19th Theory of Cryptography Conference 2021}, location = {Raleigh, NC, United States}, publisher = {International Association for Cryptologic Research}, title = {{On treewidth, separators and Yao's garbling}}, year = {2021}, } @article{10674, abstract = {In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner of the game. Such games are central in formal methods since they model the interaction between a non-terminating system and its environment. In bidding games the players bid for the right to move the token: in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Bidding games are known to have a clean and elegant mathematical structure that relies on the ability of the players to submit arbitrarily small bids. Many applications, however, require a fixed granularity for the bids, which can represent, for example, the monetary value expressed in cents. We study, for the first time, the combination of discrete-bidding and infinite-duration games. Our most important result proves that these games form a large determined subclass of concurrent games, where determinacy is the strong property that there always exists exactly one player who can guarantee winning the game. In particular, we show that, in contrast to non-discrete bidding games, the mechanism with which tied bids are resolved plays an important role in discrete-bidding games. We study several natural tie-breaking mechanisms and show that, while some do not admit determinacy, most natural mechanisms imply determinacy for every pair of initial budgets.}, author = {Aghajohari, Milad and Avni, Guy and Henzinger, Thomas A}, issn = {1860-5974}, journal = {Logical Methods in Computer Science}, keywords = {computer science, computer science and game theory, logic in computer science}, number = {1}, pages = {10:1--10:23}, publisher = {EPI Sciences}, title = {{Determinacy in discrete-bidding infinite-duration games}}, doi = {10.23638/LMCS-17(1:10)2021}, volume = {17}, year = {2021}, } @article{10023, abstract = {We study the temporal dissipation of variance and relative entropy for ergodic Markov Chains in continuous time, and compute explicitly the corresponding dissipation rates. These are identified, as is well known, in the case of the variance in terms of an appropriate Hilbertian norm; and in the case of the relative entropy, in terms of a Dirichlet form which morphs into a version of the familiar Fisher information under conditions of detailed balance. Here we obtain trajectorial versions of these results, valid along almost every path of the random motion and most transparent in the backwards direction of time. Martingale arguments and time reversal play crucial roles, as in the recent work of Karatzas, Schachermayer and Tschiderer for conservative diffusions. Extensions are developed to general “convex divergences” and to countable state-spaces. The steepest descent and gradient flow properties for the variance, the relative entropy, and appropriate generalizations, are studied along with their respective geometries under conditions of detailed balance, leading to a very direct proof for the HWI inequality of Otto and Villani in the present context.}, author = {Karatzas, Ioannis and Maas, Jan and Schachermayer, Walter}, issn = {1526-7555}, journal = {Communications in Information and Systems}, keywords = {Markov Chain, relative entropy, time reversal, steepest descent, gradient flow}, number = {4}, pages = {481--536}, publisher = {International Press of Boston}, title = {{Trajectorial dissipation and gradient flow for the relative entropy in Markov chains}}, doi = {10.4310/CIS.2021.v21.n4.a1}, volume = {21}, year = {2021}, } @article{10204, abstract = {Two common representations of close packings of identical spheres consisting of hexagonal layers, called Barlow stackings, appear abundantly in minerals and metals. These motifs, however, occupy an identical portion of space and bear identical first-order topological signatures as measured by persistent homology. Here we present a novel method based on k-fold covers that unambiguously distinguishes between these patterns. Moreover, our approach provides topological evidence that the FCC motif is the more stable of the two in the context of evolving experimental sphere packings during the transition from disordered to an ordered state. We conclude that our approach can be generalised to distinguish between various Barlow stackings manifested in minerals and metals.}, author = {Osang, Georg F and Edelsbrunner, Herbert and Saadatfar, Mohammad}, issn = {1744-6848}, journal = {Soft Matter}, number = {40}, pages = {9107--9115}, publisher = {Royal Society of Chemistry}, title = {{Topological signatures and stability of hexagonal close packing and Barlow stackings}}, doi = {10.1039/d1sm00774b}, volume = {17}, year = {2021}, } @phdthesis{9733, abstract = {This thesis is the result of the research carried out by the author during his PhD at IST Austria between 2017 and 2021. It mainly focuses on the Fröhlich polaron model, specifically to its regime of strong coupling. This model, which is rigorously introduced and discussed in the introduction, has been of great interest in condensed matter physics and field theory for more than eighty years. It is used to describe an electron interacting with the atoms of a solid material (the strength of this interaction is modeled by the presence of a coupling constant α in the Hamiltonian of the system). The particular regime examined here, which is mathematically described by considering the limit α →∞, displays many interesting features related to the emergence of classical behavior, which allows for a simplified effective description of the system under analysis. The properties, the range of validity and a quantitative analysis of the precision of such classical approximations are the main object of the present work. We specify our investigation to the study of the ground state energy of the system, its dynamics and its effective mass. For each of these problems, we provide in the introduction an overview of the previously known results and a detailed account of the original contributions by the author.}, author = {Feliciangeli, Dario}, issn = {2663-337X}, pages = {180}, publisher = {Institute of Science and Technology Austria}, title = {{The polaron at strong coupling}}, doi = {10.15479/at:ista:9733}, year = {2021}, } @article{10222, abstract = {Consider a random set of points on the unit sphere in ℝd, which can be either uniformly sampled or a Poisson point process. Its convex hull is a random inscribed polytope, whose boundary approximates the sphere. We focus on the case d = 3, for which there are elementary proofs and fascinating formulas for metric properties. In particular, we study the fraction of acute facets, the expected intrinsic volumes, the total edge length, and the distance to a fixed point. Finally we generalize the results to the ellipsoid with homeoid density.}, author = {Akopyan, Arseniy and Edelsbrunner, Herbert and Nikitenko, Anton}, issn = {1944-950X}, journal = {Experimental Mathematics}, pages = {1--15}, publisher = {Taylor & Francis}, title = {{The beauty of random polytopes inscribed in the 2-sphere}}, doi = {10.1080/10586458.2021.1980459}, year = {2021}, } @article{9241, abstract = {Volumetric light transport is a pervasive physical phenomenon, and therefore its accurate simulation is important for a broad array of disciplines. While suitable mathematical models for computing the transport are now available, obtaining the necessary material parameters needed to drive such simulations is a challenging task: direct measurements of these parameters from material samples are seldom possible. Building on the inverse scattering paradigm, we present a novel measurement approach which indirectly infers the transport parameters from extrinsic observations of multiple-scattered radiance. The novelty of the proposed approach lies in replacing structured illumination with a structured reflector bonded to the sample, and a robust fitting procedure that largely compensates for potential systematic errors in the calibration of the setup. We show the feasibility of our approach by validating simulations of complex 3D compositions of the measured materials against physical prints, using photo-polymer resins. As presented in this paper, our technique yields colorspace data suitable for accurate appearance reproduction in the area of 3D printing. Beyond that, and without fundamental changes to the basic measurement methodology, it could equally well be used to obtain spectral measurements that are useful for other application areas.}, author = {Elek, Oskar and Zhang, Ran and Sumin, Denis and Myszkowski, Karol and Bickel, Bernd and Wilkie, Alexander and Křivánek, Jaroslav and Weyrich, Tim}, issn = {1094-4087}, journal = {Optics Express}, number = {5}, pages = {7568--7588}, publisher = {Optica Publishing Group}, title = {{Robust and practical measurement of volume transport parameters in solid photo-polymer materials for 3D printing}}, doi = {10.1364/OE.406095}, volume = {29}, year = {2021}, } @inproceedings{10666, abstract = {Adversarial training is an effective method to train deep learning models that are resilient to norm-bounded perturbations, with the cost of nominal performance drop. While adversarial training appears to enhance the robustness and safety of a deep model deployed in open-world decision-critical applications, counterintuitively, it induces undesired behaviors in robot learning settings. In this paper, we show theoretically and experimentally that neural controllers obtained via adversarial training are subjected to three types of defects, namely transient, systematic, and conditional errors. We first generalize adversarial training to a safety-domain optimization scheme allowing for more generic specifications. We then prove that such a learning process tends to cause certain error profiles. We support our theoretical results by a thorough experimental safety analysis in a robot-learning task. Our results suggest that adversarial training is not yet ready for robot learning.}, author = {Lechner, Mathias and Hasani, Ramin and Grosu, Radu and Rus, Daniela and Henzinger, Thomas A}, booktitle = {2021 IEEE International Conference on Robotics and Automation}, isbn = {978-1-7281-9078-5}, issn = {2577-087X}, location = {Xi'an, China}, pages = {4140--4147}, publisher = {IEEE}, title = {{Adversarial training is not ready for robot learning}}, doi = {10.1109/ICRA48506.2021.9561036}, year = {2021}, } @inproceedings{9678, abstract = {We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.}, author = {Brandt, Sebastian and Keller, Barbara and Rybicki, Joel and Suomela, Jukka and Uitto, Jara}, booktitle = {Annual ACM Symposium on Parallelism in Algorithms and Architectures}, isbn = {9781450380706}, location = { Virtual Event, United States}, pages = {129--139}, publisher = {Association for Computing Machinery}, title = {{Efficient load-balancing through distributed token dropping}}, doi = {10.1145/3409964.3461785}, year = {2021}, } @inproceedings{10667, abstract = {Bayesian neural networks (BNNs) place distributions over the weights of a neural network to model uncertainty in the data and the network's prediction. We consider the problem of verifying safety when running a Bayesian neural network policy in a feedback loop with infinite time horizon systems. Compared to the existing sampling-based approaches, which are inapplicable to the infinite time horizon setting, we train a separate deterministic neural network that serves as an infinite time horizon safety certificate. In particular, we show that the certificate network guarantees the safety of the system over a subset of the BNN weight posterior's support. Our method first computes a safe weight set and then alters the BNN's weight posterior to reject samples outside this set. Moreover, we show how to extend our approach to a safe-exploration reinforcement learning setting, in order to avoid unsafe trajectories during the training of the policy. We evaluate our approach on a series of reinforcement learning benchmarks, including non-Lyapunovian safety specifications.}, author = {Lechner, Mathias and Žikelić, Ðorđe and Chatterjee, Krishnendu and Henzinger, Thomas A}, booktitle = {35th Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {Virtual}, publisher = {Neural Information Processing Systems Foundation}, title = {{Infinite time horizon safety of Bayesian neural networks}}, doi = {10.48550/arXiv.2111.03165}, year = {2021}, } @inproceedings{10670, abstract = {Imitation learning enables high-fidelity, vision-based learning of policies within rich, photorealistic environments. However, such techniques often rely on traditional discrete-time neural models and face difficulties in generalizing to domain shifts by failing to account for the causal relationships between the agent and the environment. In this paper, we propose a theoretical and experimental framework for learning causal representations using continuous-time neural networks, specifically over their discrete-time counterparts. We evaluate our method in the context of visual-control learning of drones over a series of complex tasks, ranging from short- and long-term navigation, to chasing static and dynamic objects through photorealistic environments. Our results demonstrate that causal continuous-time deep models can perform robust navigation tasks, where advanced recurrent models fail. These models learn complex causal control representations directly from raw visual inputs and scale to solve a variety of tasks using imitation learning.}, author = {Vorbach, Charles J and Hasani, Ramin and Amini, Alexander and Lechner, Mathias and Rus, Daniela}, booktitle = {35th Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {Virtual}, publisher = {Neural Information Processing Systems Foundation}, title = {{Causal navigation by continuous-time neural networks}}, year = {2021}, } @article{9293, abstract = {We consider planning problems for graphs, Markov Decision Processes (MDPs), and games on graphs in an explicit state space. While graphs represent the most basic planning model, MDPs represent interaction with nature and games on graphs represent interaction with an adversarial environment. We consider two planning problems with k different target sets: (a) the coverage problem asks whether there is a plan for each individual target set; and (b) the sequential target reachability problem asks whether the targets can be reached in a given sequence. For the coverage problem, we present a linear-time algorithm for graphs, and quadratic conditional lower bound for MDPs and games on graphs. For the sequential target problem, we present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs, and a quadratic conditional lower bound for games on graphs. Our results with conditional lower bounds, based on the boolean matrix multiplication (BMM) conjecture and strong exponential time hypothesis (SETH), establish (i) model-separation results showing that for the coverage problem MDPs and games on graphs are harder than graphs, and for the sequential reachability problem games on graphs are harder than MDPs and graphs; and (ii) problem-separation results showing that for MDPs the coverage problem is harder than the sequential target problem.}, author = {Chatterjee, Krishnendu and Dvořák, Wolfgang and Henzinger, Monika H and Svozil, Alexander}, issn = {0004-3702}, journal = {Artificial Intelligence}, number = {8}, publisher = {Elsevier}, title = {{Algorithms and conditional lower bounds for planning problems}}, doi = {10.1016/j.artint.2021.103499}, volume = {297}, year = {2021}, } @inproceedings{9441, abstract = {Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. }, author = {Boissonnat, Jean-Daniel and Kachanovich, Siargey and Wintraecken, Mathijs}, booktitle = {37th International Symposium on Computational Geometry}, isbn = {978-3-95977-184-9}, issn = {1868-8969}, location = {Virtual}, pages = {17:1--17:16}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations}}, doi = {10.4230/LIPIcs.SoCG.2021.17}, volume = {189}, year = {2021}, } @inproceedings{9345, abstract = {Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction.}, author = {Edelsbrunner, Herbert and Heiss, Teresa and Kurlin , Vitaliy and Smith, Philip and Wintraecken, Mathijs}, booktitle = {37th International Symposium on Computational Geometry}, issn = {1868-8969}, location = {Virtual}, pages = {32:1--32:16}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The density fingerprint of a periodic point set}}, doi = {10.4230/LIPIcs.SoCG.2021.32}, volume = {189}, year = {2021}, } @inproceedings{10041, abstract = {Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth δ , the loss in security is at most exponential in δ . The above results all concern the simulation-based notion of security. In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth δ∈N , such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in δ√ . Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation. To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security.}, author = {Kamath Hosdurg, Chethan and Klein, Karen and Pietrzak, Krzysztof Z and Wichs, Daniel}, booktitle = {41st Annual International Cryptology Conference}, isbn = {978-3-030-84244-4}, issn = {1611-3349}, location = {Virtual}, pages = {486--515}, publisher = {Springer Nature}, title = {{Limits on the Adaptive Security of Yao’s Garbling}}, doi = {10.1007/978-3-030-84245-1_17}, volume = {12826}, year = {2021}, }