TY - CHAP AU - Vicente, Sara AU - Vladimir Kolmogorov AU - Rother, Carsten ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2922 T2 - Markov Random Fields for Vision and Image Processing TI - Graph-cut Based Image Segmentation with Connectivity Priors ER - TY - CHAP AU - Kumar, M Pawan AU - Vladimir Kolmogorov AU - Torr, Philip H ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2923 T2 - Markov Random Fields for Vision and Image Processing TI - Analyzing Convex Relaxations for MAP Estimation ER - TY - CHAP AU - Criminisi, Antonio AU - Cross, Geoffrey AU - Blake, Andrew AU - Vladimir Kolmogorov ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2924 T2 - Markov Random Fields for Vision and Image Processing TI - Bilayer Segmentation of Video ER - TY - CHAP AU - Rother, Carsten AU - Vladimir Kolmogorov AU - Boykov, Yuri AU - Blake, Andrew ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2925 T2 - Markov Random Fields for Vision and Image Processing TI - Interactive Foreground Extraction using graph cut ER - TY - CHAP AU - Boykov, Yuri AU - Vladimir Kolmogorov ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2935 T2 - Markov Random Fields for Vision and Image Processing TI - Basic graph cut algorithms ER - TY - JOUR AB - Rapid research progress in genotyping techniques have allowed large genome-wide association studies. Existing methods often focus on determining associations between single loci and a specic phenotype. However, a particular phenotype is usually the result of complex relationships between multiple loci and the environment. In this paper, we describe a two-stage method for detecting epistasis by combining the traditionally used single-locus search with a search for multiway interactions. Our method is based on an extended version of Fisher's exact test. To perform this test, a Markov chain is constructed on the space of multidimensional contingency tables using the elements of a Markov basis as moves. We test our method on simulated data and compare it to a two-stage logistic regression method and to a fully Bayesian method, showing that we are able to detect the interacting loci when other methods fail to do so. Finally, we apply our method to a genome-wide data set consisting of 685 dogs and identify epistasis associated with canine hair length for four pairs of single nucleotide polymorphisms (SNPs). AU - Malaspinas, Anna-Sapfo AU - Caroline Uhler ID - 2961 IS - 1 JF - Journal of Algebraic Statistics TI - Detecting epistasis via Markov bases VL - 2 ER - TY - CONF AB - Traditional statistical methods for the confidentiality protection for statistical databases do not scale well to deal with GWAS (genome-wide association studies) databases and external information on them. The more recent concept of differential privacy, introduced by the cryptographic community, is an approach which provides a rigorous definition of privacy with meaningful privacy guarantees in the presence of arbitrary external information. Building on such notions, we propose new methods to release aggregate GWAS data without compromising an individual's privacy. We present methods for releasing differentially private minor allele frequencies, chi-square statistics and p-values. We compare these approaches on simulated data and on a GWAS study of canine hair length involving 685 dogs. We also propose a privacy-preserving method for finding genome-wide associations based on a differentially private approach to penalized logistic regression. AU - Fienberg, Stephen E AU - Slavkovic, Aleksandra AU - Caroline Uhler ID - 2960 TI - Privacy Preserving GWAS Data Sharing ER - TY - CONF AB - Zero-knowledge proofs of knowledge (ZK-PoK) for discrete logarithms and related problems are indispensable for practical cryptographic protocols. Recently, Camenisch, Kiayias, and Yung provided a specification language (the CKY-language) for such protocols which allows for a modular design and protocol analysis: for every zero-knowledge proof specified in this language, protocol designers are ensured that there exists an efficient protocol which indeed proves the specified statement. However, the protocols resulting from their compilation techniques only satisfy the classical notion of ZK-PoK, which is not retained are when they used as building blocks for higher-level applications or composed with other protocols. This problem can be tackled by moving to the Universal Composability (UC) framework, which guarantees retention of security when composing protocols in arbitrary ways. While there exist generic transformations from $\Sigma$-protocols to UC-secure protocols, these transformation are often too inefficient for practice. In this paper we introduce a specification language akin to the CKY-language and a compiler such that the resulting protocols are UC-secure and efficient. To this end, we propose an extension of the UC-framework addressing the issue that UC-secure zero-knowledge proofs are by definition proofs of knowledge, and state a special composition theorem which allows one to use the weaker -- but more efficient and often sufficient -- notion of proofs of membership in the UC-framework. We believe that our contributions enable the design of practically efficient protocols that are UC-secure and thus themselves can be used as building blocks. AU - Camenisch, Jan AU - Stephan Krenn AU - Shoup, Victor ED - Lee, Dong Hoon ED - Wang, Xiaoyun ID - 2975 TI - A Framework for Practical Universally Composable Zero-Knowledge Protocols VL - 7073 ER - TY - CONF AB - Cryptographic two-party protocols are used ubiquitously in everyday life. While some of these protocols are easy to understand and implement (e.g., key exchange or transmission of encrypted data), many of them are much more complex (e.g., e-banking and e-voting applications, or anonymous authentication and credential systems). For a software engineer without appropriate cryptographic skills the implementation of such protocols is often difficult, time consuming and error-prone. For this reason, a number of compilers supporting programmers have been published in recent years. However, they are either designed for very specific cryptographic primitives (e.g., zero-knowledge proofs of knowledge), or they only offer a very low level of abstraction and thus again demand substantial mathematical and cryptographic skills from the programmer. Finally, some of the existing compilers do not produce executable code, but only metacode which has to be instantiated with mathematical libraries, encryption routines, etc. before it can actually be used. In this paper we present a cryptographically aware compiler which is equally useful to cryptographers who want to benchmark protocols designed on paper, and to programmers who want to implement complex security sensitive protocols without having to understand all subtleties. Our tool offers a high level of abstraction and outputs well-structured and documented Java code. We believe that our compiler can contribute to shortening the development cycles of cryptographic applications and to reducing their error-proneness. AU - Bangerter, Endre AU - Stephan Krenn AU - Seifriz, Martial AU - Ultes-Nitsche, Ulrich ED - Venter, Hein S. ED - Coetzee, Marijke ED - Loock, Marianne ID - 2977 TI - cPLC - A Cryptographic Programming Language and Compiler ER - TY - CONF AB - Side channel attacks on cryptographic systems exploit information gained from physical implementations rather than theoretical weaknesses of a scheme. In recent years, major achievements were made for the class of so called access-driven cache attacks. Such attacks exploit the leakage of the memory locations accessed by a victim process. In this paper we consider the AES block cipher and present an attack which is capable of recovering the full secret key in almost realtime for AES-128, requiring only a very limited number of observed encryptions. Unlike previous attacks, we do not require any information about the plaintext (such as its distribution, etc.). Moreover, for the first time, we also show how the plaintext can be recovered without having access to the ciphertext at all. It is the first working attack on AES implementations using compressed tables. There, no efficient techniques to identify the beginning of AES rounds is known, which is the fundamental assumption underlying previous attacks. We have a fully working implementation of our attack which is able to recover AES keys after observing as little as 100 encryptions. It works against the OpenSSL 0.9.8n implementation of AES on Linux systems. Our spy process does not require any special privileges beyond those of a standard Linux user. A contribution of probably independent interest is a denial of service attack on the task scheduler of current Linux systems (CFS), which allows one to observe (on average) every single memory access of a victim process. AU - Gullasch, David AU - Bangerter, Endre AU - Stephan Krenn ID - 2976 TI - Cache Games - Bringing Access-Based Cache Attacks on AES to Practice ER -