International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Marc Fischlin

Affiliation: TU Darmstadt

Publications

Year
Venue
Title
2021
PKC
Single-to-Multi-Theorem Transformations for Non-Interactive Statistical Zero-Knowledge 📺
Marc Fischlin Felix Rohrbach
Non-interactive zero-knowledge proofs or arguments allow a prover to show validity of a statement without further interaction. For non-trivial statements such protocols require a setup assumption in form of a common random or reference string (CRS). Generally, the CRS can only be used for one statement (single-theorem zero-knowledge) such that a fresh CRS would need to be generated for each proof. Fortunately, Feige, Lapidot and Shamir (FOCS 1990) presented a transformation for any non-interactive zero-knowledge proof system that allows the CRS to be reused any polynomial number of times (multi-theorem zero-knowledge). This FLS transformation, however, is only known to work for either computational zero-knowledge or requires a structured, non-uniform common reference string. In this paper we present FLS-like transformations that work for non-interactive statistical zero-knowledge arguments in the common random string model. They allow to go from single-theorem to multi-theorem zero-knowledge and also preserve soundness, for both properties in the adaptive and non-adaptive case. Our first transformation is based on the general assumption that one-way permutations exist, while our second transformation uses lattice-based assumptions. Additionally, we define different possible soundness notions for non-interactive arguments and discuss their relationships.
2020
EUROCRYPT
Signatures from Sequential-OR Proofs 📺
OR-proofs enable a prover to show that it knows the witness for one of many statements, or that one out of many statements is true. OR-proofs are a remarkably versatile tool, used to strengthen security properties, design group and ring signature schemes, and achieve tight security. The common technique to build OR-proofs is based on an approach introduced by Cramer, Damgaard, and Schoenmakers (CRYPTO'94), where the prover splits the verifier's challenge into random shares and computes proofs for each statement in parallel. In this work we study a different, less investigated OR-proof technique, highlighted by Abe, Ohkubo, and Suzuki (ASIACRYPT'02). The difference is that the prover now computes the individual proofs sequentially. We show that such sequential OR-proofs yield signature schemes which can be proved secure in the non-programmable random oracle model. We complement this positive result with a black-box impossibility proof, showing that the same is unlikely to be the case for signatures derived from traditional OR-proofs. We finally argue that sequential-OR signature schemes can be proved secure in the quantum random oracle model, albeit with very loose bounds and by programming the random oracle.
2020
ASIACRYPT
Security Reductions for White-Box Key-Storage in Mobile Payments 📺
The goal of white-box cryptography is to provide security even when the cryptographic implementation is executed in adversarially controlled environments. White-box implementations nowadays appear in commercial products such as mobile payment applications, e.g., those certified by Mastercard. Interestingly, there, white-box cryptography is championed as a tool for secure storage of payment tokens, and importantly, the white-boxed storage functionality is bound to a hardware functionality to prevent code-lifting attacks. In this paper, we show that the approach of using hardware-binding and obfuscation for secure storage is conceptually sound. Following security specifications by Mastercard and also EMVCo, we first define security for a white-box key derivation functions (WKDF) that is bound to a hardware functionality. WKDFs with hardware-binding model a secure storage functionality, as the WKDFs in turn can be used to derive encryption keys for secure storage. We then provide a proof-of-concept construction of WKDFs based on pseudorandom functions (PRF) and obfuscation. To show that our use of cryptographic primitives is sound, we perform a cryptographic analysis and reduce the security of our WKDF to the cryptographic assumptions of indistinguishability obfuscation and PRF-security. The hardware-functionality that our WKDF is bound to is a PRF-like functionality. Obfuscation helps us to hide the secret key used for the verification, essentially emulating a signature functionality as is provided by the Android key store. We rigorously define the required security properties of a hardware-bound white-box payment application (WPAY) for generating and encrypting valid payment requests. We construct a WPAY, which uses a WKDF as a secure building block. We thereby show that a WKDF can be securely combined with any secure symmetric encryption scheme, including those based on standard ciphers such as AES.
2018
ASIACRYPT
Simulatable Channels: Extended Security that is Universally Composable and Easier to Prove
Jean Paul Degabriele Marc Fischlin
Ever since the foundational work of Goldwasser and Micali, simulation has proven to be a powerful and versatile construct for formulating security in various areas of cryptography. However security definitions based on simulation are generally harder to work with than game based definitions, often resulting in more complicated proofs. In this work we challenge this viewpoint by proposing new simulation-based security definitions for secure channels that in many cases lead to simpler proofs of security. We are particularly interested in definitions of secure channels which reflect real-world requirements, such as, protecting against the replay and reordering of ciphertexts, accounting for leakage from the decryption of invalid ciphertexts, and retaining security in the presence of ciphertext fragmentation. Furthermore we show that our proposed notion of channel simulatability implies a secure channel functionality that is universally composable. To the best of our knowledge, we are the first to study universally composable secure channels supporting these extended security goals. We conclude, by showing that the Dropbear implementation of SSH-CTR is channel simulatable in the presence of ciphertext fragmentation, and therefore also realises a universally composable secure channel. This is intended, in part, to highlight the merits of our approach over prior ones in admitting simpler security proofs in comparable settings.
2017
CRYPTO
2016
CRYPTO
2016
PKC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
PKC
2015
CRYPTO
2014
JOFC
2013
ASIACRYPT
2013
ASIACRYPT
2013
EUROCRYPT
2013
EUROCRYPT
2011
JOFC
2011
CRYPTO
2011
CRYPTO
2011
ASIACRYPT
2011
ASIACRYPT
2010
TCC
2010
PKC
2010
PKC
2010
ASIACRYPT
2010
EUROCRYPT
2010
EPRINT
Random Oracles in a Quantum World
Once quantum computers reach maturity most of today’s traditional cryptographic schemes based on RSA or discrete logarithms become vulnerable to quantum-based attacks. Hence, schemes which are more likely to resist quantum attacks like lattice-based systems or code-based primitives have recently gained significant attention. Interestingly, a vast number of such schemes also deploy random oracles, which have mainly be analyzed in the classical setting. Here we revisit the random oracle model in cryptography in light of quantum attackers. We show that there are protocols using quantum-immune primitives and random oracles, such that the protocols are secure in the classical world, but insecure if a quantum attacker can access the random oracle via quantum states. We discuss that most of the proof techniques related to the random oracle model in the classical case cannot be transferred immediately to the quantum case. Yet, we show that “quantum random oracles” can nonetheless be used to show for example that the basic Bellare-Rogaway encryption scheme is quantum-immune against plaintext attacks (assuming quantum-immune primitives).
2009
EPRINT
Foundations of Non-Malleable Hash and One-Way Functions
Non-malleability is an interesting and useful property which ensures that a cryptographic protocol preserves the independence of the underlying values: given for example an encryption Enc(m) of some unknown message m, it should be hard to transform this ciphertext into some encryption Enc(m*) of a related message m*. This notion has been studied extensively for primitives like encryption, commitments and zero-knowledge. Non-malleability of one-way functions and hash functions has surfaced as a crucial property in several recent results, but it has not undergone a comprehensive treatment so far. In this paper we initiate the study of such non-malleable functions. We start with the design of an appropriate security definition. We then show that non-malleability for hash and one-way functions can be achieved, via a theoretical construction that uses perfectly one-way hash functions and simulation-sound non-interactive zero-knowledge proofs of knowledge (NIZKPoK). We also discuss the complexity of non-malleable hash and one-way functions. Specifically, we give a black-box based separation of non-malleable functions from one-way permutations (which our construction bypasses due to the 'non-black-box' NIZKPoK). We exemplify the usefulness of our definition in cryptographic applications by showing that non-malleability is necessary and sufficient to securely replace one of the two random oracles in the IND-CCA encryption scheme by Bellare and Rogaway, and to improve the security of client-server puzzles.
2009
ASIACRYPT
2009
PKC
2009
PKC
2009
JOFC
2008
TCC
2008
EPRINT
Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles
We strengthen the foundations of deterministic public-key encryption via definitional equivalences and standard-model constructs based on general assumptions. Specifically we consider seven notions of privacy for deterministic encryption, including six forms of semantic security and an indistinguishability notion, and show them all equivalent. We then present a deterministic scheme for the secure encryption of uniformly and independently distributed messages based solely on the existence of trapdoor one-way permutations. We show a generalization of the construction that allows secure deterministic encryption of independent high-entropy messages. Finally we show relations between deterministic and standard (randomized) encryption.
2008
CRYPTO
2007
CRYPTO
2007
PKC
2007
PKC
2006
ASIACRYPT
2006
CRYPTO
2005
CRYPTO
2005
CRYPTO
2003
PKC
2002
EPRINT
The Cramer-Shoup Strong-RSA Signature Scheme Revisited
Marc Fischlin
We discuss a modification of the Cramer-Shoup strong-RSA signature scheme. Our proposal also presumes the strong RSA assumption (and a collision-intractable hash function for long messages), but -without loss in performance- the size of a signature is almost halved compared to the original scheme. We also show how to turn the signature scheme into a "lightweight" anonymous (but linkable) group identification protocol without random oracles.
2001
CRYPTO
2001
EUROCRYPT
2001
EPRINT
Universally Composable Commitments
Ran Canetti Marc Fischlin
We propose a new security measure for commitment protocols, called /universally composable/ (UC) Commitment. The measure guarantees that commitment protocols behave like an "ideal commitment service," even when concurrently composed with an arbitrary set of protocols. This is a strong guarantee: it implies that security is maintained even when an unbounded number of copies of the scheme are running concurrently, it implies non-malleability (not only with respect to other copies of the same protocol but even with respect to other protocols), it provides resilience to selective decommitment, and more. Unfortunately two-party UC commitment protocols do not exist in the plain model. However, we construct two-party UC commitment protocols, based on general complexity assumptions, in the /common reference string model/ where all parties have access to a common string taken from a predetermined distribution. The protocols are non-interactive, in the sense that both the commitment and the opening phases consist of a single message from the committer to the receiver.
2000
ASIACRYPT
2000
CRYPTO
2000
EPRINT
Implications of the Nontriviality of Entropy Approximation
Marc Fischlin
The paper was withdrawn because it contained a fatal flaw.
2000
EPRINT
Identification Protocols Secure Against Reset Attacks
We provide identification protocols that are secure even when the adversary can reset the internal state and/or randomization source of the user identifying itself, and when executed in an asynchronous environment like the Internet that gives the adversary concurrent access to instances of the user. These protocols are suitable for use by devices (like smartcards) which when under adversary control may not be able to reliably maintain their internal state between invocations.
1999
EUROCRYPT
1997
EUROCRYPT

Program Committees

PKC 2020
TCC 2019
TCC 2018
Crypto 2018
Eurocrypt 2016
Eurocrypt 2015
Asiacrypt 2014
TCC 2014
PKC 2013
Asiacrypt 2012
Crypto 2012
PKC 2012
Eurocrypt 2012
PKC 2011
Asiacrypt 2010
PKC 2010
TCC 2009
Eurocrypt 2009
Crypto 2009
TCC 2008
Eurocrypt 2007
Eurocrypt 2005
PKC 2004
PKC 2002