@article{1666,
abstract = {Evolution of gene regulation is crucial for our understanding of the phenotypic differences between species, populations and individuals. Sequence-specific binding of transcription factors to the regulatory regions on the DNA is a key regulatory mechanism that determines gene expression and hence heritable phenotypic variation. We use a biophysical model for directional selection on gene expression to estimate the rates of gain and loss of transcription factor binding sites (TFBS) in finite populations under both point and insertion/deletion mutations. Our results show that these rates are typically slow for a single TFBS in an isolated DNA region, unless the selection is extremely strong. These rates decrease drastically with increasing TFBS length or increasingly specific protein-DNA interactions, making the evolution of sites longer than ∼ 10 bp unlikely on typical eukaryotic speciation timescales. Similarly, evolution converges to the stationary distribution of binding sequences very slowly, making the equilibrium assumption questionable. The availability of longer regulatory sequences in which multiple binding sites can evolve simultaneously, the presence of “pre-sites” or partially decayed old sites in the initial sequence, and biophysical cooperativity between transcription factors, can all facilitate gain of TFBS and reconcile theoretical calculations with timescales inferred from comparative genomics.},
author = {Tugrul, Murat and Paixao, Tiago and Barton, Nicholas H and Tkacik, Gasper},
journal = {PLoS Genetics},
number = {11},
publisher = {Public Library of Science},
title = {{Dynamics of transcription factor binding site evolution}},
doi = {10.1371/journal.pgen.1005639},
volume = {11},
year = {2015},
}
@inproceedings{1685,
abstract = {Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε > 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3.
Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest.},
author = {Cohen Addad, Vincent and De Mesmay, Arnaud N},
location = {Patras, Greece},
pages = {386 -- 398},
publisher = {Springer},
title = {{A fixed parameter tractable approximation scheme for the optimal cut graph of a surface}},
doi = {10.1007/978-3-662-48350-3_33},
volume = {9294},
year = {2015},
}
@inproceedings{1647,
abstract = {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.},
author = {Fuchsbauer, Georg and Hanser, Christian and Slamanig, Daniel},
location = {Santa Barbara, CA, United States},
pages = {233 -- 253},
publisher = {Springer},
title = {{Practical round-optimal blind signatures in the standard model}},
doi = {10.1007/978-3-662-48000-7_12},
volume = {9216},
year = {2015},
}
@inproceedings{1654,
abstract = {HMAC and its variant NMAC are the most popular approaches to deriving a MAC (and more generally, a PRF) from a cryptographic hash function. Despite nearly two decades of research, their exact security still remains far from understood in many different contexts. Indeed, recent works have re-surfaced interest for {\em generic} attacks, i.e., attacks that treat the compression function of the underlying hash function as a black box.
Generic security can be proved in a model where the underlying compression function is modeled as a random function -- yet, to date, the question of proving tight, non-trivial bounds on the generic security of HMAC/NMAC even as a PRF remains a challenging open question.
In this paper, we ask the question of whether a small modification to HMAC and NMAC can allow us to exactly characterize the security of the resulting constructions, while only incurring little penalty with respect to efficiency. To this end, we present simple variants of NMAC and HMAC, for which we prove tight bounds on the generic PRF security, expressed in terms of numbers of construction and compression function queries necessary to break the construction. All of our constructions are obtained via a (near) {\em black-box} modification of NMAC and HMAC, which can be interpreted as an initial step of key-dependent message pre-processing.
While our focus is on PRF security, a further attractive feature of our new constructions is that they clearly defeat all recent generic attacks against properties such as state recovery and universal forgery. These exploit properties of the so-called ``functional graph'' which are not directly accessible in our new constructions. },
author = {Gazi, Peter and Pietrzak, Krzysztof Z and Tessaro, Stefano},
location = {Auckland, New Zealand},
pages = {85 -- 109},
publisher = {Springer},
title = {{Generic security of NMAC and HMAC with input whitening}},
doi = {10.1007/978-3-662-48800-3_4},
volume = {9453},
year = {2015},
}
@article{1642,
abstract = {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.},
author = {Fulek, Radoslav and Kynčl, Jan and Malinovič, Igor and Pálvölgyi, Dömötör},
journal = {Electronic Journal of Combinatorics},
number = {4},
publisher = {Electronic Journal of Combinatorics},
title = {{Clustered planarity testing revisited}},
volume = {22},
year = {2015},
}