@article{1479, abstract = {Most entropy notions H(.) like Shannon or min-entropy satisfy a chain rule stating that for random variables X,Z, and A we have H(X|Z,A)≥H(X|Z)−|A|. That is, by conditioning on A the entropy of X can decrease by at most the bitlength |A| of A. Such chain rules are known to hold for some computational entropy notions like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption, and memory delegation. These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: we construct joint distributions (X,Z,A), where A is a distribution over a single bit, such that the HILL entropy H HILL (X|Z) is large but H HILL (X|Z,A) is basically zero. Our counterexample just makes the minimal assumption that NP⊈P/poly. Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable. Finally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object.}, author = {Krenn, Stephan and Pietrzak, Krzysztof Z and Wadia, Akshay and Wichs, Daniel}, journal = {Computational Complexity}, number = {3}, pages = {567 -- 605}, publisher = {Springer}, title = {{A counterexample to the chain rule for conditional HILL entropy}}, doi = {10.1007/s00037-015-0120-9}, volume = {25}, year = {2016}, } @inproceedings{2940, abstract = {A chain rule for an entropy notion H(.) states that the entropy H(X) of a variable X decreases by at most l if conditioned on an l-bit string A, i.e., H(X|A)>= H(X)-l. More generally, it satisfies a chain rule for conditional entropy if H(X|Y,A)>= H(X|Y)-l. All natural information theoretic entropy notions we are aware of (like Shannon or min-entropy) satisfy some kind of chain rule for conditional entropy. Moreover, many computational entropy notions (like Yao entropy, unpredictability entropy and several variants of HILL entropy) satisfy the chain rule for conditional entropy, though here not only the quantity decreases by l, but also the quality of the entropy decreases exponentially in l. However, for the standard notion of conditional HILL entropy (the computational equivalent of min-entropy) the existence of such a rule was unknown so far. In this paper, we prove that for conditional HILL entropy no meaningful chain rule exists, assuming the existence of one-way permutations: there exist distributions X,Y,A, where A is a distribution over a single bit, but $H(X|Y)>>H(X|Y,A)$, even if we simultaneously allow for a massive degradation in the quality of the entropy. The idea underlying our construction is based on a surprising connection between the chain rule for HILL entropy and deniable encryption. }, author = {Krenn, Stephan and Pietrzak, Krzysztof Z and Wadia, Akshay}, editor = {Sahai, Amit}, location = {Tokyo, Japan}, pages = {23 -- 39}, publisher = {Springer}, title = {{A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it}}, doi = {10.1007/978-3-642-36594-2_2}, volume = {7785}, year = {2013}, } @inproceedings{2973, abstract = {Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multiparty computation. Currently, first applications that critically rely on ZK-PoKs are being deployed in the real world. The most prominent example is Direct Anonymous Attestation (DAA), which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic Trusted Platform Module (TPM) chip. Implementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are, loosely speaking, significantly more complex than standard crypto primitives, such as encryption and signature schemes. As a result, implementation cycles of ZK-PoK are time-consuming and error-prone, in particular for developers with minor or no cryptographic skills. In this paper we report on our ongoing and future research vision with the goal to bring ZK-PoK to practice by making them accessible to crypto and security engineers. To this end we are developing compilers and related tools that support and partially automate the design, implementation, verification and secure implementation of ZK-PoK protocols.}, author = {Bangerter, Endre and Barzan, Stefania and Stephan Krenn and Sadeghi, Ahmad-Reza and Schneider, Thomas and Tsay, Joe-Kai}, editor = {Christianson, Bruce and Malcolm, James A. and Matyas, Vashek and Roe, Michael}, pages = {51 -- 62}, publisher = {Springer}, title = {{Bringing Zero-Knowledge Proofs of Knowledge to Practice}}, doi = {10.1007/978-3-642-36213-2_9}, volume = {7028}, year = {2013}, } @inproceedings{2259, abstract = {The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen at EUROCRYPT ’12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors. As a tool in the reduction, we show that there is a “lossy mode” for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient min-entropy, and very simple constructions of deterministic encryption, lossy trapdoor functions and reusable extractors. Our approach is inspired by a technique of Goldwasser et al. from ICS ’10, which implicitly showed the existence of a “lossy mode” for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio. }, author = {Alwen, Joel F and Krenn, Stephan and Pietrzak, Krzysztof Z and Wichs, Daniel}, location = {Santa Barbara, CA, United States}, number = {1}, pages = {57 -- 74}, publisher = {Springer}, title = {{Learning with rounding, revisited: New reduction properties and applications}}, doi = {10.1007/978-3-642-40041-4_4}, volume = {8042}, year = {2013}, } @inproceedings{2937, abstract = {Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system.}, author = {Almeida, José and Barbosa, Manuel and Bangerter, Endre and Barthe, Gilles and Krenn, Stephan and Béguelin, Santiago}, booktitle = {Proceedings of the 2012 ACM conference on Computer and communications security}, location = {Raleigh, NC, USA}, pages = {488 -- 500}, publisher = {ACM}, title = {{Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols}}, doi = {10.1145/2382196.2382249}, year = {2012}, } @inproceedings{2974, abstract = {We construct a perfectly binding string commitment scheme whose security is based on the learning parity with noise (LPN) assumption, or equivalently, the hardness of decoding random linear codes. Our scheme not only allows for a simple and efficient zero-knowledge proof of knowledge for committed values (essentially a Σ-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages m_0,...,m_u, are such that m_0=C(m_1,...,m_u) for any circuit C. To get soundness which is exponentially small in a security parameter t, and when the zero-knowledge property relies on the LPN problem with secrets of length l, our 3 round protocol has communication complexity O(t|C|l log(l)) and computational complexity of O(t|C|l) bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors.}, author = {Jain, Abhishek and Krenn, Stephan and Pietrzak, Krzysztof Z and Tentes, Aris}, editor = {Wang, Xiaoyun and Sako, Kazue}, location = {Beijing, China}, pages = {663 -- 680}, publisher = {Springer}, title = {{Commitments and efficient zero knowledge proofs from learning parity with noise}}, doi = {10.1007/978-3-642-34961-4_40}, volume = {7658}, year = {2012}, } @inproceedings{2975, abstract = {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.}, author = {Camenisch, Jan and Stephan Krenn and Shoup, Victor}, editor = {Lee, Dong Hoon and Wang, Xiaoyun}, pages = {449 -- 467}, publisher = {Springer}, title = {{A Framework for Practical Universally Composable Zero-Knowledge Protocols}}, doi = {10.1007/978-3-642-25385-0}, volume = {7073}, year = {2011}, } @inproceedings{2976, abstract = {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.}, author = {Gullasch, David and Bangerter, Endre and Stephan Krenn}, pages = {490 -- 505}, publisher = {IEEE}, title = {{Cache Games - Bringing Access-Based Cache Attacks on AES to Practice}}, doi = {10.1109/SP.2011.22}, year = {2011}, } @inproceedings{2977, abstract = {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.}, author = {Bangerter, Endre and Stephan Krenn and Seifriz, Martial and Ultes-Nitsche, Ulrich}, editor = {Venter, Hein S. and Coetzee, Marijke and Loock, Marianne}, publisher = {IEEE}, title = {{cPLC - A Cryptographic Programming Language and Compiler}}, doi = {10.1109/ISSA.2011.6027533}, year = {2011}, } @inproceedings{2978, abstract = {Efficient zero-knowledge proofs of knowledge for group homomorphisms are essential for numerous systems in applied cryptography. Especially, Σ-protocols for proving knowledge of discrete logarithms in known and hidden order groups are of prime importance. Yet, while these proofs can be performed very efficiently within groups of known order, for hidden order groups the respective proofs are far less efficient. This paper shows strong evidence that this efficiency gap cannot be bridged. Namely, while there are efficient protocols allowing a prover to cheat only with negligibly small probability in the case of known order groups, we provide strong evidence that for hidden order groups this probability is bounded below by 1/2 for all efficient Σ-protocols not using common reference strings or the like. We prove our results for a comprehensive class of Σ-protocols in the generic group model, and further strengthen them by investigating certain instantiations in the plain model.}, author = {Bangerter, Endre and Camenisch, Jan and Stephan Krenn}, editor = {Micciancio, Daniele}, pages = {553 -- 571}, publisher = {Springer}, title = {{Efficiency Limitations for Σ-Protocols for Group Homomorphisms}}, doi = {10.1007/978-3-642-11799-2}, volume = {5978}, year = {2010}, } @inproceedings{2979, abstract = {Zero-knowledge proofs of knowledge (ZK-PoK) are important building blocks for numerous cryptographic applications. Although ZK-PoK have a high potential impact, their real world deployment is typically hindered by their significant complexity compared to other (non-interactive) crypto primitives. Moreover, their design and implementation are time-consuming and error-prone. We contribute to overcoming these challenges as follows: We present a comprehensive specification language and a compiler for ZK-PoK protocols based on Σ-protocols. The compiler allows the fully automatic translation of an abstract description of a proof goal into an executable implementation. Moreover, the compiler overcomes various restrictions of previous approaches, e.g., it supports the important class of exponentiation homomorphisms with hidden-order co-domain, needed for privacy-preserving applications such as DAA. Finally, our compiler is certifying, in the sense that it automatically produces a formal proof of the soundness of the compiled protocol for a large class of protocols using the Isabelle/HOL theorem prover. }, author = {Almeida, José Bacelar and Bangerter, Endre and Barbosa, Manuel and Stephan Krenn and Sadeghi, Ahmad-Reza and Schneider, Thomas}, editor = {Gritzalis, Dimitris and Preneel, Bart and Theoharidou, Marianthi}, pages = {151 -- 167}, publisher = {Springer}, title = {{A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols}}, doi = {10.1007/978-3-642-15497-3}, volume = {6345}, year = {2010}, } @inproceedings{2980, abstract = {Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multi-party computation (SMPC). Currently, first applications that essentially rely on ZK-PoKs are being deployed in the real world. The most prominent example is the Direct Anonymous Attestation (DAA) protocol, which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic chip Trusted Platform Module (TPM). Implementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are significantly more complex than standard crypto primitives (e.g., encryption and signature schemes). As a result, the design-implementation cycles of ZK-PoK are time-consuming and error-prone. To overcome this, we present a compiler with corresponding languages for the automatic generation of sound and efficient ZK-PoK based on Σ-protocols. The protocol designer using our compiler formulates the goal of a ZK-PoK proof in a high-level protocol specification language, which abstracts away unnecessary technicalities from the designer. The compiler then automatically generates the protocol implementation in Java code; alternatively, the compiler can output a description of the protocol in LaTeX which can be used for documentation or verification.}, author = {Bangerter, Endre and Briner, Thomas and Henecka, Wilko and Stephan Krenn and Sadeghi, Ahmad-Reza and Schneider, Thomas}, editor = {Martinelli, Fabio and Preneel, Bart}, pages = {67 -- 82}, publisher = {Springer}, title = {{Automatic Generation of Sigma-Protocols}}, doi = {10.1007/978-3-642-16441-5}, volume = {6391}, year = {2010}, }