TY - CONF
AB - At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model construction of efficient roundoptimal blind signatures that does not require complexity leveraging. It is conceptually simple and builds on the primitive of structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme and hardness of a version of the DH inversion problem. Blindness under adversarially chosen keys is proven under an interactive variant of the DDH assumption. We propose a variant of their scheme whose blindness can be proven under a non-interactive assumption, namely a variant of the bilinear DDH assumption. We moreover prove its unforgeability assuming only unforgeability of the underlying SPS-EQ but no additional assumptions as needed for the FHS scheme.
AU - Fuchsbauer, Georg
AU - Hanser, Christian
AU - Kamath Hosdurg, Chethan
AU - Slamanig, Daniel
ID - 1225
TI - Practical round-optimal blind signatures in the standard model from weaker assumptions
VL - 9841
ER -
TY - JOUR
AB - Mitochondrial complex I (also known as NADH:ubiquinone oxidoreductase) contributes to cellular energy production by transferring electrons from NADH to ubiquinone coupled to proton translocation across the membrane. It is the largest protein assembly of the respiratory chain with a total mass of 970 kilodaltons. Here we present a nearly complete atomic structure of ovine (Ovis aries) mitochondrial complex I at 3.9 Å resolution, solved by cryo-electron microscopy with cross-linking and mass-spectrometry mapping experiments. All 14 conserved core subunits and 31 mitochondria-specific supernumerary subunits are resolved within the L-shaped molecule. The hydrophilic matrix arm comprises flavin mononucleotide and 8 iron-sulfur clusters involved in electron transfer, and the membrane arm contains 78 transmembrane helices, mostly contributed by antiporter-like subunits involved in proton translocation. Supernumerary subunits form an interlinked, stabilizing shell around the conserved core. Tightly bound lipids (including cardiolipins) further stabilize interactions between the hydrophobic subunits. Subunits with possible regulatory roles contain additional cofactors, NADPH and two phosphopantetheine molecules, which are shown to be involved in inter-subunit interactions. We observe two different conformations of the complex, which may be related to the conformationally driven coupling mechanism and to the active-deactive transition of the enzyme. Our structure provides insight into the mechanism, assembly, maturation and dysfunction of mitochondrial complex I, and allows detailed molecular analysis of disease-causing mutations.
AU - Fiedorczuk, Karol
AU - Letts, James A
AU - Degliesposti, Gianluca
AU - Kaszuba, Karol
AU - Skehel, Mark
AU - Sazanov, Leonid A
ID - 1226
IS - 7625
JF - Nature
TI - Atomic structure of the entire mammalian mitochondrial complex i
VL - 538
ER -
TY - CONF
AB - Many biological systems can be modeled as multiaffine hybrid systems. Due to the nonlinearity of multiaffine systems, it is difficult to verify their properties of interest directly. A common strategy to tackle this problem is to construct and analyze a discrete overapproximation of the original system. However, the conservativeness of a discrete abstraction significantly determines the level of confidence we can have in the properties of the original system. In this paper, in order to reduce the conservativeness of a discrete abstraction, we propose a new method based on a sufficient and necessary decision condition for computing discrete transitions between states in the abstract system. We assume the state space partition of a multiaffine system to be based on a set of multivariate polynomials. Hence, a rectangular partition defined in terms of polynomials of the form (xi − c) is just a simple case of multivariate polynomial partition, and the new decision condition applies naturally. We analyze and demonstrate the improvement of our method over the existing methods using some examples.
AU - Kong, Hui
AU - Bartocci, Ezio
AU - Bogomolov, Sergiy
AU - Grosu, Radu
AU - Henzinger, Thomas A
AU - Jiang, Yu
AU - Schilling, Christian
ID - 1227
TI - Discrete abstraction of multiaffine systems
VL - 9957
ER -
TY - CONF
AB - Witness encryption (WE) was introduced by Garg et al. [GGSW13]. A WE scheme is defined for some NP language L and lets a sender encrypt messages relative to instances x. A ciphertext for x can be decrypted using w witnessing x ∈ L, but hides the message if x ∈ L. Garg et al. construct WE from multilinear maps and give another construction [GGH+13b] using indistinguishability obfuscation (iO) for circuits. Due to the reliance on such heavy tools, WE can cur- rently hardly be implemented on powerful hardware and will unlikely be realizable on constrained devices like smart cards any time soon. We construct a WE scheme where encryption is done by simply computing a Naor-Yung ciphertext (two CPA encryptions and a NIZK proof). To achieve this, our scheme has a setup phase, which outputs public parameters containing an obfuscated circuit (only required for decryption), two encryption keys and a common reference string (used for encryption). This setup need only be run once, and the parame- ters can be used for arbitrary many encryptions. Our scheme can also be turned into a functional WE scheme, where a message is encrypted w.r.t. a statement and a function f, and decryption with a witness w yields f (m, w). Our construction is inspired by the functional encryption scheme by Garg et al. and we prove (selective) security assuming iO and statistically simulation-sound NIZK. We give a construction of the latter in bilinear groups and combining it with ElGamal encryption, our ciphertexts are of size 1.3 kB at a 128-bit security level and can be computed on a smart card.
AU - Abusalah, Hamza M
AU - Fuchsbauer, Georg
AU - Pietrzak, Krzysztof Z
ID - 1229
TI - Offline witness encryption
VL - 9696
ER -
TY - CONF
AB - Concolic testing is a promising method for generating test suites for large programs. However, it suffers from the path-explosion problem and often fails to find tests that cover difficult-to-reach parts of programs. In contrast, model checkers based on counterexample-guided abstraction refinement explore programs exhaustively, while failing to scale on large programs with precision. In this paper, we present a novel method that iteratively combines concolic testing and model checking to find a test suite for a given coverage criterion. If concolic testing fails to cover some test goals, then the model checker refines its program abstraction to prove more paths infeasible, which reduces the search space for concolic testing. We have implemented our method on top of the concolictesting tool Crest and the model checker CpaChecker. We evaluated our tool on a collection of programs and a category of SvComp benchmarks. In our experiments, we observed an improvement in branch coverage compared to Crest from 48% to 63% in the best case, and from 66% to 71% on average.
AU - Daca, Przemyslaw
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
ID - 1230
TI - Abstraction-driven concolic testing
VL - 9583
ER -
TY - CONF
AB - We study the time-and memory-complexities of the problem of computing labels of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The w-bit label of a node is the hash of the labels of its parents, and the hash function is modeled as a random oracle. Specific instances of this problem underlie both proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memory-hard functions like scrypt. As our main tool, we introduce the new notion of a probabilistic parallel entangled pebbling game, a new type of combinatorial pebbling game on a graph, which is closely related to the labeling game on the same graph. As a first application of our framework, we prove that for scrypt, when the underlying hash function is invoked n times, the cumulative memory complexity (CMC) (a notion recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memory-hardness for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for adversaries that can store many natural functions of the labels (e.g., linear combinations), but still not arbitrary functions thereof. We then introduce and study a combinatorial quantity, and show how a sufficiently small upper bound on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary adversaries. We also show that such an upper bound solves the main open problem for proofs-of-space protocols: namely, establishing that the time complexity of computing the label of a random node in a graph on n nodes (given an initial kw-bit state) reduces tightly to the time complexity for black pebbling on the same graph (given an initial k-node pebbling).
AU - Alwen, Joel F
AU - Chen, Binyi
AU - Kamath Hosdurg, Chethan
AU - Kolmogorov, Vladimir
AU - Pietrzak, Krzysztof Z
AU - Tessaro, Stefano
ID - 1231
TI - On the complexity of scrypt and proofs of space in the parallel random oracle model
VL - 9666
ER -
TY - JOUR
AB - Mitochondrial electron transport chain complexes are organized into supercomplexes responsible for carrying out cellular respiration. Here we present three architectures of mammalian (ovine) supercomplexes determined by cryo-electron microscopy. We identify two distinct arrangements of supercomplex CICIII 2 CIV (the respirasome) - a major 'tight' form and a minor 'loose' form (resolved at the resolution of 5.8 Å and 6.7 Å, respectively), which may represent different stages in supercomplex assembly or disassembly. We have also determined an architecture of supercomplex CICIII 2 at 7.8 Å resolution. All observed density can be attributed to the known 80 subunits of the individual complexes, including 132 transmembrane helices. The individual complexes form tight interactions that vary between the architectures, with complex IV subunit COX7a switching contact from complex III to complex I. The arrangement of active sites within the supercomplex may help control reactive oxygen species production. To our knowledge, these are the first complete architectures of the dominant, physiologically relevant state of the electron transport chain.
AU - Letts, James A
AU - Fiedorczuk, Karol
AU - Sazanov, Leonid A
ID - 1232
IS - 7622
JF - Nature
TI - The architecture of respiratory supercomplexes
VL - 537
ER -
TY - CONF
AB - About three decades ago it was realized that implementing private channels between parties which can be adaptively corrupted requires an encryption scheme that is secure against selective opening attacks. Whether standard (IND-CPA) security implies security against selective opening attacks has been a major open question since. The only known reduction from selective opening to IND-CPA security loses an exponential factor. A polynomial reduction is only known for the very special case where the distribution considered in the selective opening security experiment is a product distribution, i.e., the messages are sampled independently from each other. In this paper we give a reduction whose loss is quantified via the dependence graph (where message dependencies correspond to edges) of the underlying message distribution. In particular, for some concrete distributions including Markov distributions, our reduction is polynomial.
AU - Fuchsbauer, Georg
AU - Heuer, Felix
AU - Kiltz, Eike
AU - Pietrzak, Krzysztof Z
ID - 1233
TI - Standard security does imply security against selective opening for markov distributions
VL - 9562
ER -
TY - CONF
AB - We present a new algorithm for the statistical model checking of Markov chains with respect to unbounded temporal properties, including full linear temporal logic. The main idea is that we monitor each simulation run on the fly, in order to detect quickly if a bottom strongly connected component is entered with high probability, in which case the simulation run can be terminated early. As a result, our simulation runs are often much shorter than required by termination bounds that are computed a priori for a desired level of confidence on a large state space. In comparison to previous algorithms for statistical model checking our method is not only faster in many cases but also requires less information about the system, namely, only the minimum transition probability that occurs in the Markov chain. In addition, our method can be generalised to unbounded quantitative properties such as mean-payoff bounds.
AU - Daca, Przemyslaw
AU - Henzinger, Thomas A
AU - Kretinsky, Jan
AU - Petrov, Tatjana
ID - 1234
TI - Faster statistical model checking for unbounded temporal properties
VL - 9636
ER -
TY - CONF
AB - A constrained pseudorandom function (CPRF) F: K×X → Y for a family T of subsets of χ is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a short constrained key kS, which allows to evaluate F(k, ·) on all inputs x ∈ S, while the outputs on all inputs x /∈ S look random even given kS. Abusalah et al. recently constructed the first constrained PRF for inputs of arbitrary length whose sets S are decided by Turing machines. They use their CPRF to build broadcast encryption and the first ID-based non-interactive key exchange for an unbounded number of users. Their constrained keys are obfuscated circuits and are therefore large. In this work we drastically reduce the key size and define a constrained key for a Turing machine M as a short signature on M. For this, we introduce a new signature primitive with constrained signing keys that let one only sign certain messages, while forging a signature on others is hard even when knowing the coins for key generation.
AU - Abusalah, Hamza M
AU - Fuchsbauer, Georg
ID - 1235
TI - Constrained PRFs for unbounded inputs with short keys
VL - 9696
ER -