TY - JOUR AB - Auxin and cytokinin are key endogenous regulators of plant development. Although cytokinin-mediated modulation of auxin distribution is a developmentally crucial hormonal interaction, its molecular basis is largely unknown. Here we show a direct regulatory link between cytokinin signalling and the auxin transport machinery uncovering a mechanistic framework for cytokinin-auxin cross-talk. We show that the CYTOKININ RESPONSE FACTORS (CRFs), transcription factors downstream of cytokinin perception, transcriptionally control genes encoding PIN-FORMED (PIN) auxin transporters at a specific PIN CYTOKININ RESPONSE ELEMENT (PCRE) domain. Removal of this cis-regulatory element effectively uncouples PIN transcription from the CRF-mediated cytokinin regulation and attenuates plant cytokinin sensitivity. We propose that CRFs represent a missing cross-talk component that fine-tunes auxin transport capacity downstream of cytokinin signalling to control plant development. AU - Šimášková, Mária AU - O'Brien, José AU - Khan-Djamei, Mamoona AU - Van Noorden, Giel AU - Ötvös, Krisztina AU - Vieten, Anne AU - De Clercq, Inge AU - Van Haperen, Johanna AU - Cuesta, Candela AU - Hoyerová, Klára AU - Vanneste, Steffen AU - Marhavy, Peter AU - Wabnik, Krzysztof T AU - Van Breusegem, Frank AU - Nowack, Moritz AU - Murphy, Angus AU - Friml, Jiřĺ AU - Weijers, Dolf AU - Beeckman, Tom AU - Benková, Eva ID - 1640 JF - Nature Communications TI - Cytokinin response factors regulate PIN-FORMED auxin transporters VL - 6 ER - TY - JOUR AB - The Hanani-Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident to at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm. AU - Fulek, Radoslav AU - Kynčl, Jan AU - Malinovič, Igor AU - Pálvölgyi, Dömötör ID - 1642 IS - 4 JF - Electronic Journal of Combinatorics TI - Clustered planarity testing revisited VL - 22 ER - TY - JOUR AB - In this paper the optimal transport and the metamorphosis perspectives are combined. For a pair of given input images geodesic paths in the space of images are defined as minimizers of a resulting path energy. To this end, the underlying Riemannian metric measures the rate of transport cost and the rate of viscous dissipation. Furthermore, the model is capable to deal with strongly varying image contrast and explicitly allows for sources and sinks in the transport equations which are incorporated in the metric related to the metamorphosis approach by Trouvé and Younes. In the non-viscous case with source term existence of geodesic paths is proven in the space of measures. The proposed model is explored on the range from merely optimal transport to strongly dissipative dynamics. For this model a robust and effective variational time discretization of geodesic paths is proposed. This requires to minimize a discrete path energy consisting of a sum of consecutive image matching functionals. These functionals are defined on corresponding pairs of intensity functions and on associated pairwise matching deformations. Existence of time discrete geodesics is demonstrated. Furthermore, a finite element implementation is proposed and applied to instructive test cases and to real images. In the non-viscous case this is compared to the algorithm proposed by Benamou and Brenier including a discretization of the source term. Finally, the model is generalized to define discrete weighted barycentres with applications to textures and objects. AU - Maas, Jan AU - Rumpf, Martin AU - Schönlieb, Carola AU - Simon, Stefan ID - 1639 IS - 6 JF - ESAIM: Mathematical Modelling and Numerical Analysis TI - A generalized model for optimal transport of images including dissipation and density modulation VL - 49 ER - TY - JOUR AB - The mitochondrial respiratory chain, also known as the electron transport chain (ETC), is crucial to life, and energy production in the form of ATP is the main mitochondrial function. Three proton-translocating enzymes of the ETC, namely complexes I, III and IV, generate proton motive force, which in turn drives ATP synthase (complex V). The atomic structures and basic mechanisms of most respiratory complexes have previously been established, with the exception of complex I, the largest complex in the ETC. Recently, the crystal structure of the entire complex I was solved using a bacterial enzyme. The structure provided novel insights into the core architecture of the complex, the electron transfer and proton translocation pathways, as well as the mechanism that couples these two processes. AU - Sazanov, Leonid A ID - 1638 IS - 6 JF - Nature Reviews Molecular Cell Biology TI - A giant molecular proton pump: structure and mechanism of respiratory complex I VL - 16 ER - TY - CONF AB - A pseudorandom function (PRF) is a keyed function F : K × X → Y where, for a random key k ∈ K, the function F(k, ·) is indistinguishable from a uniformly random function, given black-box access. A key-homomorphic PRF has the additional feature that for any keys k, k' and any input x, we have F(k+k', x) = F(k, x)⊕F(k', x) for some group operations +,⊕ on K and Y, respectively. A constrained PRF for a family of setsS ⊆ P(X) has the property that, given any key k and set S ∈ S, one can efficiently compute a “constrained” key kS that enables evaluation of F(k, x) on all inputs x ∈ S, while the values F(k, x) for x /∈ S remain pseudorandom even given kS. In this paper we construct PRFs that are simultaneously constrained and key homomorphic, where the homomorphic property holds even for constrained keys. We first show that the multilinear map-based bit-fixing and circuit-constrained PRFs of Boneh and Waters (Asiacrypt 2013) can be modified to also be keyhomomorphic. We then show that the LWE-based key-homomorphic PRFs of Banerjee and Peikert (Crypto 2014) are essentially already prefix-constrained PRFs, using a (non-obvious) definition of constrained keys and associated group operation. Moreover, the constrained keys themselves are pseudorandom, and the constraining and evaluation functions can all be computed in low depth. As an application of key-homomorphic constrained PRFs,we construct a proxy re-encryption schemewith fine-grained access control. This scheme allows storing encrypted data on an untrusted server, where each file can be encrypted relative to some attributes, so that only parties whose constrained keys match the attributes can decrypt. Moreover, the server can re-key (arbitrary subsets of) the ciphertexts without learning anything about the plaintexts, thus permitting efficient and finegrained revocation. AU - Banerjee, Abishek AU - Fuchsbauer, Georg AU - Peikert, Chris AU - Pietrzak, Krzysztof Z AU - Stevens, Sophie ID - 1646 SN - 978-3-662-46496-0 T2 - 12th Theory of Cryptography Conference TI - Key-homomorphic constrained pseudorandom functions VL - 9015 ER - TY - CONF AB - Generalized Selective Decryption (GSD), introduced by Panjwani [TCC’07], is a game for a symmetric encryption scheme Enc that captures the difficulty of proving adaptive security of certain protocols, most notably the Logical Key Hierarchy (LKH) multicast encryption protocol. In the GSD game there are n keys k1,..., kn, which the adversary may adaptively corrupt (learn); moreover, it can ask for encryptions Encki (kj) of keys under other keys. The adversary’s task is to distinguish keys (which it cannot trivially compute) from random. Proving the hardness of GSD assuming only IND-CPA security of Enc is surprisingly hard. Using “complexity leveraging” loses a factor exponential in n, which makes the proof practically meaningless. We can think of the GSD game as building a graph on n vertices, where we add an edge i → j when the adversary asks for an encryption of kj under ki. If restricted to graphs of depth ℓ, Panjwani gave a reduction that loses only a factor exponential in ℓ (not n). To date, this is the only non-trivial result known for GSD. In this paper we give almost-polynomial reductions for large classes of graphs. Most importantly, we prove the security of the GSD game restricted to trees losing only a quasi-polynomial factor n3 log n+5. Trees are an important special case capturing real-world protocols like the LKH protocol. Our new bound improves upon Panjwani’s on some LKH variants proposed in the literature where the underlying tree is not balanced. Our proof builds on ideas from the “nested hybrids” technique recently introduced by Fuchsbauer et al. [Asiacrypt’14] for proving the adaptive security of constrained PRFs. AU - Fuchsbauer, Georg AU - Jafargholi, Zahra AU - Pietrzak, Krzysztof Z ID - 1648 TI - A quasipolynomial reduction for generalized selective decryption on trees VL - 9215 ER - TY - CONF AB - We extend a commitment scheme based on the learning with errors over rings (RLWE) problem, and present efficient companion zeroknowledge proofs of knowledge. Our scheme maps elements from the ring (or equivalently, n elements from AU - Benhamouda, Fabrice AU - Krenn, Stephan AU - Lyubashevsky, Vadim AU - Pietrzak, Krzysztof Z ID - 1649 TI - Efficient zero-knowledge proofs for commitments from learning with errors over rings VL - 9326 ER - TY - CONF AB - Increasing the computational complexity of evaluating a hash function, both for the honest users as well as for an adversary, is a useful technique employed for example in password-based cryptographic schemes to impede brute-force attacks, and also in so-called proofs of work (used in protocols like Bitcoin) to show that a certain amount of computation was performed by a legitimate user. A natural approach to adjust the complexity of a hash function is to iterate it c times, for some parameter c, in the hope that any query to the scheme requires c evaluations of the underlying hash function. However, results by Dodis et al. (Crypto 2012) imply that plain iteration falls short of achieving this goal, and designing schemes which provably have such a desirable property remained an open problem. This paper formalizes explicitly what it means for a given scheme to amplify the query complexity of a hash function. In the random oracle model, the goal of a secure query-complexity amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability, a random oracle allowing R queries (for the adversary) into one provably allowing only r < R queries. Turned around, this means that making r queries to the scheme requires at least R queries to the actual random oracle. Second, a new scheme, called collision-free iteration, is proposed and proven to achieve c-fold QCA for both the honest parties and the adversary, for any fixed parameter c. AU - Demay, Grégory AU - Gazi, Peter AU - Maurer, Ueli AU - Tackmann, Björn ID - 1644 TI - Query-complexity amplification for random oracles VL - 9063 ER - TY - CONF AB - Round-optimal blind signatures are notoriously hard to construct in the standard model, especially in the malicious-signer model, where blindness must hold under adversarially chosen keys. This is substantiated by several impossibility results. The only construction that can be termed theoretically efficient, by Garg and Gupta (Eurocrypt’14), requires complexity leveraging, inducing an exponential security loss. We present a construction of practically efficient round-optimal blind signatures in the standard model. It is conceptually simple and builds on the recent structure-preserving signatures on equivalence classes (SPSEQ) from Asiacrypt’14. While the traditional notion of blindness follows from standard assumptions, we prove blindness under adversarially chosen keys under an interactive variant of DDH. However, we neither require non-uniform assumptions nor complexity leveraging. We then show how to extend our construction to partially blind signatures and to blind signatures on message vectors, which yield a construction of one-show anonymous credentials à la “anonymous credentials light” (CCS’13) in the standard model. Furthermore, we give the first SPS-EQ construction under noninteractive assumptions and show how SPS-EQ schemes imply conventional structure-preserving signatures, which allows us to apply optimality results for the latter to SPS-EQ. AU - Fuchsbauer, Georg AU - Hanser, Christian AU - Slamanig, Daniel ID - 1647 TI - Practical round-optimal blind signatures in the standard model VL - 9216 ER - TY - CONF AB - Secret-key constructions are often proved secure in a model where one or more underlying components are replaced by an idealized oracle accessible to the attacker. This model gives rise to information-theoretic security analyses, and several advances have been made in this area over the last few years. This paper provides a systematic overview of what is achievable in this model, and how existing works fit into this view. AU - Gazi, Peter AU - Tessaro, Stefano ID - 1645 T2 - 2015 IEEE Information Theory Workshop TI - Secret-key cryptography from ideal primitives: A systematic verview ER -