TY - JOUR
AB - 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.
AU - Krenn, Stephan
AU - Pietrzak, Krzysztof Z
AU - Wadia, Akshay
AU - Wichs, Daniel
ID - 1479
IS - 3
JF - Computational Complexity
TI - A counterexample to the chain rule for conditional HILL entropy
VL - 25
ER -
TY - CONF
AB - 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.
AU - Alwen, Joel F
AU - Krenn, Stephan
AU - Pietrzak, Krzysztof Z
AU - Wichs, Daniel
ID - 2259
IS - 1
TI - Learning with rounding, revisited: New reduction properties and applications
VL - 8042
ER -
TY - CONF
AB - 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.
AU - Krenn, Stephan
AU - Pietrzak, Krzysztof Z
AU - Wadia, Akshay
ED - Sahai, Amit
ID - 2940
TI - A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it
VL - 7785
ER -
TY - CONF
AB - 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.
AU - Bangerter, Endre
AU - Barzan, Stefania
AU - Stephan Krenn
AU - Sadeghi, Ahmad-Reza
AU - Schneider, Thomas
AU - Tsay, Joe-Kai
ED - Christianson, Bruce
ED - Malcolm, James A.
ED - Matyas, Vashek
ED - Roe, Michael
ID - 2973
TI - Bringing Zero-Knowledge Proofs of Knowledge to Practice
VL - 7028
ER -
TY - CONF
AB - 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.
AU - Almeida, José
AU - Barbosa, Manuel
AU - Bangerter, Endre
AU - Barthe, Gilles
AU - Krenn, Stephan
AU - Béguelin, Santiago
ID - 2937
T2 - Proceedings of the 2012 ACM conference on Computer and communications security
TI - Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols
ER -
TY - CONF
AB - 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.
AU - Jain, Abhishek
AU - Krenn, Stephan
AU - Pietrzak, Krzysztof Z
AU - Tentes, Aris
ED - Wang, Xiaoyun
ED - Sako, Kazue
ID - 2974
TI - Commitments and efficient zero knowledge proofs from learning parity with noise
VL - 7658
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 - 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 -
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 - 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.
AU - Bangerter, Endre
AU - Camenisch, Jan
AU - Stephan Krenn
ED - Micciancio, Daniele
ID - 2978
TI - Efficiency Limitations for Σ-Protocols for Group Homomorphisms
VL - 5978
ER -
TY - CONF
AB - 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.
AU - Almeida, José Bacelar
AU - Bangerter, Endre
AU - Barbosa, Manuel
AU - Stephan Krenn
AU - Sadeghi, Ahmad-Reza
AU - Schneider, Thomas
ED - Gritzalis, Dimitris
ED - Preneel, Bart
ED - Theoharidou, Marianthi
ID - 2979
TI - A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols
VL - 6345
ER -
TY - CONF
AB - 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.
AU - Bangerter, Endre
AU - Briner, Thomas
AU - Henecka, Wilko
AU - Stephan Krenn
AU - Sadeghi, Ahmad-Reza
AU - Schneider, Thomas
ED - Martinelli, Fabio
ED - Preneel, Bart
ID - 2980
TI - Automatic Generation of Sigma-Protocols
VL - 6391
ER -