@inproceedings{1672,
abstract = {Composable notions of incoercibility aim to forbid a coercer from using anything beyond the coerced parties’ inputs and outputs to catch them when they try to deceive him. Existing definitions are restricted to weak coercion types, and/or are not universally composable. Furthermore, they often make too strong assumptions on the knowledge of coerced parties—e.g., they assume they known the identities and/or the strategies of other coerced parties, or those of corrupted parties— which makes them unsuitable for applications of incoercibility such as e-voting, where colluding adversarial parties may attempt to coerce honest voters, e.g., by offering them money for a promised vote, and use their own view to check that the voter keeps his end of the bargain. In this work we put forward the first universally composable notion of incoercible multi-party computation, which satisfies the above intuition and does not assume collusions among coerced parties or knowledge of the corrupted set. We define natural notions of UC incoercibility corresponding to standard coercion-types, i.e., receipt-freeness and resistance to full-active coercion. Importantly, our suggested notion has the unique property that it builds on top of the well studied UC framework by Canetti instead of modifying it. This guarantees backwards compatibility, and allows us to inherit results from the rich UC literature. We then present MPC protocols which realize our notions of UC incoercibility given access to an arguably minimal setup—namely honestly generate tamper-proof hardware performing a very simple cryptographic operation—e.g., a smart card. This is, to our knowledge, the first proposed construction of an MPC protocol (for more than two parties) that is incoercibly secure and universally composable, and therefore the first construction of a universally composable receipt-free e-voting protocol.},
author = {Alwen, Joel F and Ostrovsky, Rafail and Zhou, Hongsheng and Zikas, Vassilis},
location = {Santa Barbara, CA, United States},
pages = {763 -- 780},
publisher = {Springer},
title = {{Incoercible multi-party computation and universally composable receipt-free voting}},
doi = {10.1007/978-3-662-48000-7_37},
volume = {9216},
year = {2015},
}
@article{1673,
abstract = {When a new mutant arises in a population, there is a probability it outcompetes the residents and fixes. The structure of the population can affect this fixation probability. Suppressing population structures reduce the difference between two competing variants, while amplifying population structures enhance the difference. Suppressors are ubiquitous and easy to construct, but amplifiers for the large population limit are more elusive and only a few examples have been discovered. Whether or not a population structure is an amplifier of selection depends on the probability distribution for the placement of the invading mutant. First, we prove that there exist only bounded amplifiers for adversarial placement-that is, for arbitrary initial conditions. Next, we show that the Star population structure, which is known to amplify for mutants placed uniformly at random, does not amplify for mutants that arise through reproduction and are therefore placed proportional to the temperatures of the vertices. Finally, we construct population structures that amplify for all mutational events that arise through reproduction, uniformly at random, or through some combination of the two. },
author = {Adlam, Ben and Chatterjee, Krishnendu and Nowak, Martin},
journal = {Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences},
number = {2181},
publisher = {Royal Society of London},
title = {{Amplifiers of selection}},
doi = {10.1098/rspa.2015.0114},
volume = {471},
year = {2015},
}
@article{1674,
abstract = {We consider N × N random matrices of the form H = W + V where W is a real symmetric Wigner matrix and V a random or deterministic, real, diagonal matrix whose entries are independent of W. We assume subexponential decay for the matrix entries of W and we choose V so that the eigenvalues of W and V are typically of the same order. For a large class of diagonal matrices V, we show that the rescaled distribution of the extremal eigenvalues is given by the Tracy-Widom distribution F1 in the limit of large N. Our proofs also apply to the complex Hermitian setting, i.e. when W is a complex Hermitian Wigner matrix.},
author = {Lee, Jioon and Schnelli, Kevin},
journal = {Reviews in Mathematical Physics},
number = {8},
publisher = {World Scientific Publishing},
title = {{Edge universality for deformed Wigner matrices}},
doi = {10.1142/S0129055X1550018X},
volume = {27},
year = {2015},
}
@inproceedings{1675,
abstract = {Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system. In this work, we put forward an alternative concept for PoWs - so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model (with one additional mild assumption required for the proof to go through), using graphs with high “pebbling complexity” and Merkle hash-trees. We discuss some applications, including follow-up work where a decentralized digital currency scheme called Spacecoin is constructed that uses PoS (instead of wasteful PoW like in Bitcoin) to prevent double spending. The main technical contribution of this work is the construction of (directed, loop-free) graphs on N vertices with in-degree O(log logN) such that even if one places Θ(N) pebbles on the nodes of the graph, there’s a constant fraction of nodes that needs Θ(N) steps to be pebbled (where in every step one can put a pebble on a node if all its parents have a pebble).},
author = {Dziembowski, Stefan and Faust, Sebastian and Kolmogorov, Vladimir and Pietrzak, Krzysztof Z},
location = {Santa Barbara, CA, United States},
pages = {585 -- 605},
publisher = {Springer},
title = {{Proofs of space}},
doi = {10.1007/978-3-662-48000-7_29},
volume = {9216},
year = {2015},
}
@article{1676,
author = {Sixt, Michael K and Raz, Erez},
journal = {Current Opinion in Cell Biology},
number = {10},
pages = {4 -- 6},
publisher = {Elsevier},
title = {{Editorial overview: Cell adhesion and migration}},
doi = {10.1016/j.ceb.2015.09.004},
volume = {36},
year = {2015},
}