@article{10326, abstract = {Strigolactones (SLs) are carotenoid-derived plant hormones that control shoot branching and communications between host plants and symbiotic fungi or root parasitic plants. Extensive studies have identified the key components participating in SL biosynthesis and signalling, whereas the catabolism or deactivation of endogenous SLs in planta remains largely unknown. Here, we report that the Arabidopsis carboxylesterase 15 (AtCXE15) and its orthologues function as efficient hydrolases of SLs. We show that overexpression of AtCXE15 promotes shoot branching by dampening SL-inhibited axillary bud outgrowth. We further demonstrate that AtCXE15 could bind and efficiently hydrolyse SLs both in vitro and in planta. We also provide evidence that AtCXE15 is capable of catalysing hydrolysis of diverse SL analogues and that such CXE15-dependent catabolism of SLs is evolutionarily conserved in seed plants. These results disclose a catalytic mechanism underlying homoeostatic regulation of SLs in plants, which also provides a rational approach to spatial-temporally manipulate the endogenous SLs and thus architecture of crops and ornamental plants.}, author = {Xu, Enjun and Chai, Liang and Zhang, Shiqi and Yu, Ruixue and Zhang, Xixi and Xu, Chongyi and Hu, Yuxin}, issn = {2055-0278}, journal = {Nature Plants}, pages = {1495–1504 }, publisher = {Springer Nature}, title = {{Catabolism of strigolactones by a carboxylesterase}}, doi = {10.1038/s41477-021-01011-y}, volume = {7}, year = {2021}, } @article{10327, abstract = {Composite materials offer numerous advantages in a wide range of applications, including thermoelectrics. Here, semiconductor–metal composites are produced by just blending nanoparticles of a sulfide semiconductor obtained in aqueous solution and at room temperature with a metallic Cu powder. The obtained blend is annealed in a reducing atmosphere and afterward consolidated into dense polycrystalline pellets through spark plasma sintering (SPS). We observe that, during the annealing process, the presence of metallic copper activates a partial reduction of the PbS, resulting in the formation of PbS–Pb–CuxS composites. The presence of metallic lead during the SPS process habilitates the liquid-phase sintering of the composite. Besides, by comparing the transport properties of PbS, the PbS–Pb–CuxS composites, and PbS–CuxS composites obtained by blending PbS and CuxS nanoparticles, we demonstrate that the presence of metallic lead decisively contributes to a strong increase of the charge carrier concentration through spillover of charge carriers enabled by the low work function of lead. The increase in charge carrier concentration translates into much higher electrical conductivities and moderately lower Seebeck coefficients. These properties translate into power factors up to 2.1 mW m–1 K–2 at ambient temperature, well above those of PbS and PbS + CuxS. Additionally, the presence of multiple phases in the final composite results in a notable decrease in the lattice thermal conductivity. Overall, the introduction of metallic copper in the initial blend results in a significant improvement of the thermoelectric performance of PbS, reaching a dimensionless thermoelectric figure of merit ZT = 1.1 at 750 K, which represents about a 400% increase over bare PbS. Besides, an average ZTave = 0.72 in the temperature range 320–773 K is demonstrated.}, author = {Li, Mengyao and Liu, Yu and Zhang, Yu and Han, Xu and Xiao, Ke and Nabahat, Mehran and Arbiol, Jordi and Llorca, Jordi and Ibáñez, Maria and Cabot, Andreu}, issn = {1944-8252}, journal = {ACS Applied Materials and Interfaces}, keywords = {CuxS, PbS, energy conversion, nanocomposite, nanoparticle, solution synthesis, thermoelectric}, number = {43}, pages = {51373–51382}, publisher = {American Chemical Society }, title = {{PbS–Pb–CuxS composites for thermoelectric application}}, doi = {10.1021/acsami.1c15609}, volume = {13}, year = {2021}, } @article{10337, abstract = {The T cell receptor (TCR) pathway receives, processes, and amplifies the signal from pathogenic antigens to the activation of T cells. Although major components in this pathway have been identified, the knowledge on how individual components cooperate to effectively transduce signals remains limited. Phase separation emerges as a biophysical principle in organizing signaling molecules into liquid-like condensates. Here, we report that phospholipase Cγ1 (PLCγ1) promotes phase separation of LAT, a key adaptor protein in the TCR pathway. PLCγ1 directly cross-links LAT through its two SH2 domains. PLCγ1 also protects LAT from dephosphorylation by the phosphatase CD45 and promotes LAT-dependent ERK activation and SLP76 phosphorylation. Intriguingly, a nonmonotonic effect of PLCγ1 on LAT clustering was discovered. Computer simulations, based on patchy particles, revealed how the cluster size is regulated by protein compositions. Together, these results define a critical function of PLCγ1 in promoting phase separation of the LAT complex and TCR signal transduction.}, author = {Zeng, Longhui and Palaia, Ivan and Šarić, Anđela and Su, Xiaolei}, issn = {1540-8140}, journal = {Journal of Cell Biology}, keywords = {cell biology}, number = {6}, publisher = {Rockefeller University Press}, title = {{PLCγ1 promotes phase separation of T cell signaling components}}, doi = {10.1083/jcb.202009154}, volume = {220}, year = {2021}, } @article{10338, abstract = {In the nuclear pore complex, intrinsically disordered proteins (FG Nups), along with their interactions with more globular proteins called nuclear transport receptors (NTRs), are vital to the selectivity of transport into and out of the cell nucleus. Although such interactions can be modeled at different levels of coarse graining, in vitro experimental data have been quantitatively described by minimal models that describe FG Nups as cohesive homogeneous polymers and NTRs as uniformly cohesive spheres, in which the heterogeneous effects have been smeared out. By definition, these minimal models do not account for the explicit heterogeneities in FG Nup sequences, essentially a string of cohesive and noncohesive polymer units, and at the NTR surface. Here, we develop computational and analytical models that do take into account such heterogeneity in a minimal fashion and compare them with experimental data on single-molecule interactions between FG Nups and NTRs. Overall, we find that the heterogeneous nature of FG Nups and NTRs does play a role in determining equilibrium binding properties but is of much greater significance when it comes to unbinding and binding kinetics. Using our models, we predict how binding equilibria and kinetics depend on the distribution of cohesive blocks in the FG Nup sequences and of the binding pockets at the NTR surface, with multivalency playing a key role. Finally, we observe that single-molecule binding kinetics has a rather minor influence on the diffusion of NTRs in polymer melts consisting of FG-Nup-like sequences.}, author = {Davis, Luke K. and Šarić, Anđela and Hoogenboom, Bart W. and Zilman, Anton}, issn = {0006-3495}, journal = {Biophysical Journal}, keywords = {biophysics}, number = {9}, pages = {1565--1577}, publisher = {Elsevier}, title = {{Physical modeling of multivalent interactions in the nuclear pore complex}}, doi = {10.1016/j.bpj.2021.01.039}, volume = {120}, year = {2021}, } @article{10339, abstract = {We study the effects of osmotic shocks on lipid vesicles via coarse-grained molecular dynamics simulations by explicitly considering the solute in the system. We find that depending on their nature (hypo- or hypertonic) such shocks can lead to bursting events or engulfing of external material into inner compartments, among other morphology transformations. We characterize the dynamics of these processes and observe a separation of time scales between the osmotic shock absorption and the shape relaxation. Our work consequently provides an insight into the dynamics of compartmentalization in vesicular systems as a result of osmotic shocks, which can be of interest in the context of early proto-cell development and proto-cell compartmentalisation.}, author = {Vanhille-Campos, Christian and Šarić, Anđela}, issn = {1744-6848}, journal = {Soft Matter}, keywords = {condensed matter physics, general chemistry}, number = {14}, pages = {3798--3806}, publisher = {Royal Society of Chemistry}, title = {{Modelling the dynamics of vesicle reshaping and scission under osmotic shocks}}, doi = {10.1039/d0sm02012e}, volume = {17}, year = {2021}, } @article{10340, abstract = {The cell membrane is an inhomogeneous system composed of phospholipids, sterols, carbohydrates, and proteins that can be directly attached to underlying cytoskeleton. The protein linkers between the membrane and the cytoskeleton are believed to have a profound effect on the mechanical properties of the cell membrane and its ability to reshape. Here, we investigate the role of membrane-cortex linkers on the extrusion of membrane tubes using computer simulations and experiments. In simulations, we find that the force for tube extrusion has a nonlinear dependence on the density of membrane-cortex attachments: at a range of low and intermediate linker densities, the force is not significantly influenced by the presence of the membrane-cortex attachments and resembles that of the bare membrane. For large concentrations of linkers, however, the force substantially increases compared with the bare membrane. In both cases, the linkers provided membrane tubes with increased stability against coalescence. We then pulled tubes from HEK cells using optical tweezers for varying expression levels of the membrane-cortex attachment protein Ezrin. In line with simulations, we observed that overexpression of Ezrin led to an increased extrusion force, while Ezrin depletion had a negligible effect on the force. Our results shed light on the importance of local protein rearrangements for membrane reshaping at nanoscopic scales.}, author = {Paraschiv, Alexandru and Lagny, Thibaut J. and Campos, Christian Vanhille and Coudrier, Evelyne and Bassereau, Patricia and Šarić, Anđela}, issn = {0006-3495}, journal = {Biophysical Journal}, keywords = {biophysics}, number = {4}, pages = {598--606}, publisher = {Cell Press}, title = {{Influence of membrane-cortex linkers on the extrusion of membrane tubes}}, doi = {10.1016/j.bpj.2020.12.028}, volume = {120}, year = {2021}, } @article{10363, abstract = {Erythropoietin enhances oxygen delivery and reduces hypoxia-induced cell death, but its pro-thrombotic activity is problematic for use of erythropoietin in treating hypoxia. We constructed a fusion protein that stimulates red blood cell production and neuroprotection without triggering platelet production, a marker for thrombosis. The protein consists of an anti-glycophorin A nanobody and an erythropoietin mutant (L108A). The mutation reduces activation of erythropoietin receptor homodimers that induce erythropoiesis and thrombosis, but maintains the tissue-protective signaling. The binding of the nanobody element to glycophorin A rescues homodimeric erythropoietin receptor activation on red blood cell precursors. In a cell proliferation assay, the fusion protein is active at 10−14 M, allowing an estimate of the number of receptor–ligand complexes needed for signaling. This fusion protein stimulates erythroid cell proliferation in vitro and in mice, and shows neuroprotective activity in vitro. Our erythropoietin fusion protein presents a novel molecule for treating hypoxia.}, author = {Lee, Jungmin and Vernet, Andyna and Gruber, Nathalie and Kready, Kasia M. and Burrill, Devin R. and Way, Jeffrey C. and Silver, Pamela A.}, issn = {1741-0134}, journal = {Protein Engineering, Design and Selection}, publisher = {Oxford University Press}, title = {{Rational engineering of an erythropoietin fusion protein to treat hypoxia}}, doi = {10.1093/protein/gzab025}, volume = {34}, year = {2021}, } @article{10365, abstract = {The early development of many organisms involves the folding of cell monolayers, but this behaviour is difficult to reproduce in vitro; therefore, both mechanistic causes and effects of local curvature remain unclear. Here we study epithelial cell monolayers on corrugated hydrogels engineered into wavy patterns, examining how concave and convex curvatures affect cellular and nuclear shape. We find that substrate curvature affects monolayer thickness, which is larger in valleys than crests. We show that this feature generically arises in a vertex model, leading to the hypothesis that cells may sense curvature by modifying the thickness of the tissue. We find that local curvature also affects nuclear morphology and positioning, which we explain by extending the vertex model to take into account membrane–nucleus interactions, encoding thickness modulation in changes to nuclear deformation and position. We propose that curvature governs the spatial distribution of yes-associated proteins via nuclear shape and density changes. We show that curvature also induces significant variations in lamins, chromatin condensation and cell proliferation rate in folded epithelial tissues. Together, this work identifies active cell mechanics and nuclear mechanoadaptation as the key players of the mechanistic regulation of epithelia to substrate curvature.}, author = {Luciano, Marine and Xue, Shi-lei and De Vos, Winnok H. and Redondo-Morata, Lorena and Surin, Mathieu and Lafont, Frank and Hannezo, Edouard B and Gabriele, Sylvain}, issn = {1745-2481}, journal = {Nature Physics}, number = {12}, pages = {1382–1390}, publisher = {Springer Nature}, title = {{Cell monolayers sense curvature by exploiting active mechanics and nuclear mechanoadaptation}}, doi = {10.1038/s41567-021-01374-1}, volume = {17}, year = {2021}, } @article{10366, author = {Heisenberg, Carl-Philipp J and Lennon, Ana Maria and Mayor, Roberto and Salbreux, Guillaume}, issn = {2667-2901}, journal = {Cells and Development}, number = {12}, publisher = {Elsevier}, title = {{Special rebranding issue: “Quantitative cell and developmental biology”}}, doi = {10.1016/j.cdev.2021.203758}, volume = {168}, year = {2021}, } @inproceedings{10367, abstract = {How information is created, shared and consumed has changed rapidly in recent decades, in part thanks to new social platforms and technologies on the web. With ever-larger amounts of unstructured and limited labels, organizing and reconciling information from different sources and modalities is a central challenge in machine learning. This cutting-edge tutorial aims to introduce the multimodal entailment task, which can be useful for detecting semantic alignments when a single modality alone does not suffice for a whole content understanding. Starting with a brief overview of natural language processing, computer vision, structured data and neural graph learning, we lay the foundations for the multimodal sections to follow. We then discuss recent multimodal learning literature covering visual, audio and language streams, and explore case studies focusing on tasks which require fine-grained understanding of visual and linguistic semantics question answering, veracity and hatred classification. Finally, we introduce a new dataset for recognizing multimodal entailment, exploring it in a hands-on collaborative section. Overall, this tutorial gives an overview of multimodal learning, introduces a multimodal entailment dataset, and encourages future research in the topic.}, author = {Ilharco, Cesar and Shirazi, Afsaneh and Gopalan, Arjun and Nagrani, Arsha and Bratanič, Blaž and Bregler, Chris and Liu, Christina and Ferreira, Felipe and Barcik, Gabriek and Ilharco, Gabriel and Osang, Georg F and Bulian, Jannis and Frank, Jared and Smaira, Lucas and Cao, Qin and Marino, Ricardo and Patel, Roma and Leung, Thomas and Imbrasaite, Vaiva}, booktitle = {59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, Tutorial Abstracts}, isbn = {9-781-9540-8557-2}, location = {Bangkok, Thailand}, pages = {29--30}, publisher = {Association for Computational Linguistics}, title = {{Recognizing multimodal entailment}}, doi = {10.18653/v1/2021.acl-tutorials.6}, year = {2021}, } @article{10401, abstract = {Theoretical and experimental studies of the interaction between spins and temperature are vital for the development of spin caloritronics, as they dictate the design of future devices. In this work, we propose a two-terminal cold-atom simulator to study that interaction. The proposed quantum simulator consists of strongly interacting atoms that occupy two temperature reservoirs connected by a one-dimensional link. First, we argue that the dynamics in the link can be described using an inhomogeneous Heisenberg spin chain whose couplings are defined by the local temperature. Second, we show the existence of a spin current in a system with a temperature difference by studying the dynamics that follows the spin-flip of an atom in the link. A temperature gradient accelerates the impurity in one direction more than in the other, leading to an overall spin current similar to the spin Seebeck effect.}, author = {Barfknecht, Rafael E. and Foerster, Angela and Zinner, Nikolaj T. and Volosniev, Artem}, issn = {23993650}, journal = {Communications Physics}, number = {1}, publisher = {Springer Nature}, title = {{Generation of spin currents by a temperature gradient in a two-terminal device}}, doi = {10.1038/s42005-021-00753-7}, volume = {4}, year = {2021}, } @article{10402, abstract = {Branching morphogenesis governs the formation of many organs such as lung, kidney, and the neurovascular system. Many studies have explored system-specific molecular and cellular regulatory mechanisms, as well as self-organizing rules underlying branching morphogenesis. However, in addition to local cues, branched tissue growth can also be influenced by global guidance. Here, we develop a theoretical framework for a stochastic self-organized branching process in the presence of external cues. Combining analytical theory with numerical simulations, we predict differential signatures of global vs. local regulatory mechanisms on the branching pattern, such as angle distributions, domain size, and space-filling efficiency. We find that branch alignment follows a generic scaling law determined by the strength of global guidance, while local interactions influence the tissue density but not its overall territory. Finally, using zebrafish innervation as a model system, we test these key features of the model experimentally. Our work thus provides quantitative predictions to disentangle the role of different types of cues in shaping branched structures across scales.}, author = {Ucar, Mehmet C and Kamenev, Dmitrii and Sunadome, Kazunori and Fachet, Dominik C and Lallemend, Francois and Adameyko, Igor and Hadjab, Saida and Hannezo, Edouard B}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Theory of branching morphogenesis by local interactions and global guidance}}, doi = {10.1038/s41467-021-27135-5}, volume = {12}, year = {2021}, } @article{10403, abstract = {Synaptic transmission, connectivity, and dendritic morphology mature in parallel during brain development and are often disrupted in neurodevelopmental disorders. Yet how these changes influence the neuronal computations necessary for normal brain function are not well understood. To identify cellular mechanisms underlying the maturation of synaptic integration in interneurons, we combined patch-clamp recordings of excitatory inputs in mouse cerebellar stellate cells (SCs), three-dimensional reconstruction of SC morphology with excitatory synapse location, and biophysical modeling. We found that postnatal maturation of postsynaptic strength was homogeneously reduced along the somatodendritic axis, but dendritic integration was always sublinear. However, dendritic branching increased without changes in synapse density, leading to a substantial gain in distal inputs. Thus, changes in synapse distribution, rather than dendrite cable properties, are the dominant mechanism underlying the maturation of neuronal computation. These mechanisms favor the emergence of a spatially compartmentalized two-stage integration model promoting location-dependent integration within dendritic subunits.}, author = {Biane, Celia and Rückerl, Florian and Abrahamsson, Therese and Saint-Cloment, Cécile and Mariani, Jean and Shigemoto, Ryuichi and Digregorio, David A. and Sherrard, Rachel M. and Cathala, Laurence}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Developmental emergence of two-stage nonlinear synaptic integration in cerebellar interneurons}}, doi = {10.7554/eLife.65954}, volume = {10}, year = {2021}, } @article{10404, abstract = {While convolutional neural networks (CNNs) have found wide adoption as state-of-the-art models for image-related tasks, their predictions are often highly sensitive to small input perturbations, which the human vision is robust against. This paper presents Perturber, a web-based application that allows users to instantaneously explore how CNN activations and predictions evolve when a 3D input scene is interactively perturbed. Perturber offers a large variety of scene modifications, such as camera controls, lighting and shading effects, background modifications, object morphing, as well as adversarial attacks, to facilitate the discovery of potential vulnerabilities. Fine-tuned model versions can be directly compared for qualitative evaluation of their robustness. Case studies with machine learning experts have shown that Perturber helps users to quickly generate hypotheses about model vulnerabilities and to qualitatively compare model behavior. Using quantitative analyses, we could replicate users’ insights with other CNN architectures and input images, yielding new insights about the vulnerability of adversarially trained models.}, author = {Sietzen, Stefan and Lechner, Mathias and Borowski, Judy and Hasani, Ramin and Waldner, Manuela}, issn = {1467-8659}, journal = {Computer Graphics Forum}, number = {7}, pages = {253--264}, publisher = {Wiley}, title = {{Interactive analysis of CNN robustness}}, doi = {10.1111/cgf.14418}, volume = {40}, year = {2021}, } @article{10406, abstract = {Multicellular organisms develop complex shapes from much simpler, single-celled zygotes through a process commonly called morphogenesis. Morphogenesis involves an interplay between several factors, ranging from the gene regulatory networks determining cell fate and differentiation to the mechanical processes underlying cell and tissue shape changes. Thus, the study of morphogenesis has historically been based on multidisciplinary approaches at the interface of biology with physics and mathematics. Recent technological advances have further improved our ability to study morphogenesis by bridging the gap between the genetic and biophysical factors through the development of new tools for visualizing, analyzing, and perturbing these factors and their biochemical intermediaries. Here, we review how a combination of genetic, microscopic, biophysical, and biochemical approaches has aided our attempts to understand morphogenesis and discuss potential approaches that may be beneficial to such an inquiry in the future.}, author = {Mishra, Nikhil and Heisenberg, Carl-Philipp J}, issn = {1545-2948}, journal = {Annual Review of Genetics}, keywords = {morphogenesis, forward genetics, high-resolution microscopy, biophysics, biochemistry, patterning}, pages = {209--233}, publisher = {Annual Reviews}, title = {{Dissecting organismal morphogenesis by bridging genetics and biophysics}}, doi = {10.1146/annurev-genet-071819-103748}, volume = {55}, year = {2021}, } @inproceedings{10407, abstract = {Digital hardware Trojans are integrated circuits whose implementation differ from the specification in an arbitrary and malicious way. For example, the circuit can differ from its specified input/output behavior after some fixed number of queries (known as “time bombs”) or on some particular input (known as “cheat codes”). To detect such Trojans, countermeasures using multiparty computation (MPC) or verifiable computation (VC) have been proposed. On a high level, to realize a circuit with specification F one has more sophisticated circuits F⋄ manufactured (where F⋄ specifies a MPC or VC of F ), and then embeds these F⋄ ’s into a master circuit which must be trusted but is relatively simple compared to F . Those solutions impose a significant overhead as F⋄ is much more complex than F , also the master circuits are not exactly trivial. In this work, we show that in restricted settings, where F has no evolving state and is queried on independent inputs, we can achieve a relaxed security notion using very simple constructions. In particular, we do not change the specification of the circuit at all (i.e., F=F⋄ ). Moreover the master circuit basically just queries a subset of its manufactured circuits and checks if they’re all the same. The security we achieve guarantees that, if the manufactured circuits are initially tested on up to T inputs, the master circuit will catch Trojans that try to deviate on significantly more than a 1/T fraction of the inputs. This bound is optimal for the type of construction considered, and we provably achieve it using a construction where 12 instantiations of F need to be embedded into the master. We also discuss an extremely simple construction with just 2 instantiations for which we conjecture that it already achieves the optimal bound.}, author = {Chakraborty, Suvradip and Dziembowski, Stefan and Gałązka, Małgorzata and Lizurej, Tomasz and Pietrzak, Krzysztof Z and Yeo, Michelle X}, isbn = {9-783-0309-0452-4}, issn = {1611-3349}, location = {Raleigh, NC, United States}, pages = {397--428}, publisher = {Springer Nature}, title = {{Trojan-resilience without cryptography}}, doi = {10.1007/978-3-030-90453-1_14}, volume = {13043}, year = {2021}, } @inproceedings{10408, abstract = {Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users’ secret keys while the root is the shared group key. For a group of size N, each user just holds log(N) keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting 2log(N) ciphertexts (encrypting each fresh key on the path under the keys of its parents). In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group. We show that in an asymptotic setting (where the number m of groups is fixed while the number N of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution. As our asymptotic “solution” converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a “lattice graph”, which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code. To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.}, author = {Alwen, Joel F and Auerbach, Benedikt and Baig, Mirza Ahad and Cueto Noval, Miguel and Klein, Karen and Pascual Perez, Guillermo and Pietrzak, Krzysztof Z and Walter, Michael}, booktitle = {19th International Conference}, isbn = {9-783-0309-0455-5}, issn = {1611-3349}, location = {Raleigh, NC, United States}, pages = {222--253}, publisher = {Springer Nature}, title = {{Grafting key trees: Efficient key management for overlapping groups}}, doi = {10.1007/978-3-030-90456-2_8}, volume = {13044}, 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{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{10414, abstract = {We consider the almost-sure (a.s.) termination problem for probabilistic programs, which are a stochastic extension of classical imperative programs. Lexicographic ranking functions provide a sound and practical approach for termination of non-probabilistic programs, and their extension to probabilistic programs is achieved via lexicographic ranking supermartingales (LexRSMs). However, LexRSMs introduced in the previous work have a limitation that impedes their automation: all of their components have to be non-negative in all reachable states. This might result in LexRSM not existing even for simple terminating programs. Our contributions are twofold: First, we introduce a generalization of LexRSMs which allows for some components to be negative. This standard feature of non-probabilistic termination proofs was hitherto not known to be sound in the probabilistic setting, as the soundness proof requires a careful analysis of the underlying stochastic process. Second, we present polynomial-time algorithms using our generalized LexRSMs for proving a.s. termination in broad classes of linear-arithmetic programs.}, author = {Chatterjee, Krishnendu and Goharshady, Ehsan Kafshdar and Novotný, Petr and Zárevúcky, Jiří and Zikelic, Dorde}, booktitle = {24th International Symposium on Formal Methods}, isbn = {9-783-0309-0869-0}, issn = {1611-3349}, location = {Virtual}, pages = {619--639}, publisher = {Springer Nature}, title = {{On lexicographic proof rules for probabilistic termination}}, doi = {10.1007/978-3-030-90870-6_33}, volume = {13047}, year = {2021}, }