International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Serge Vaudenay

Publications

Year
Venue
Title
2021
PKC
Beyond Security and Efficiency: On-Demand Ratcheting with Security Awareness 📺
Secure asynchronous two-party communication applies ratcheting to strengthen privacy, in the presence of internal state exposures. Security with ratcheting is provided in two forms: forward security and post-compromise security. There have been several such secure protocols proposed in the last few years. However, they come with a high cost. In this paper, we propose two generic constructions with favorable properties. Concretely, our first construction achieves security awareness. It allows users to detect non-persistent active attacks, to determine which messages are not safe given a potential leakage pattern, and to acknowledge for deliveries. In our second construction, we define a hybrid system formed by combining two protocols: typically, a weakly secure "light" protocol and a strongly secure "heavy" protocol. The design goals of our hybrid construction are, first, to let the sender decide which one to use in order to obtain an efficient protocol with ratchet on demand; and second, to restore the communication between honest participants in the case of a message loss or an active attack. We can apply our generic constructions to any existing protocol.
2021
ASIACRYPT
FAST: Secure and High Performance Format-Preserving Encryption and Tokenization
We propose a new construction for format-preserving encryption. Our design provides the flexibility for use in format-preserving encryption (FPE) and for static table-driven tokenization. Our algorithm is a substitution-permutation network based on random Sboxes. Using pseudorandom generators and pseudorandom functions, we prove a strong adaptive security based on the super-pseudorandom permutation assumption of our core design. We obtain empirical parameters to reach this assumption. We suggest parameters for quantum security. Our design accommodates very small domains, with a radix $a$ from 4 to the Unicode alphabet size and a block length $l$ starting 2. The number of Sbox evaluations per encryption is asymptotically $l^{\frac32}$, which is also the number of bytes we need to generate using AES in CTR mode for each tweak setup. For instance, we tokenize 10 decimal digits using 29 (parallel) AES computations to be done only once, when the tweak changes.
2021
ASIACRYPT
New Attacks on LowMC instances with a Single Plaintext/Ciphertext pair
Cryptanalysis of the LowMC block cipher when the attacker has access to a single known plaintext/ciphertext pair is a mathematically challenging problem. This is because the attacker is unable to employ most of the standard techniques in symmetric cryptography like linear and differential cryptanalysis. This scenario is particularly relevant while arguing the security of the Picnic digital signature scheme in which the plaintext/ciphertext pair generated by the LowMC block cipher serves as the public (verification) key and the corresponding LowMC encryption key also serves as the secret (signing) key of the signature scheme. In the paper by Banik et al. (IACR ToSC 2020:4), the authors used a linearization technique of the LowMC S-box to mount attacks on some instances of the block cipher. In this paper, we first make a more precise complexity analysis of the linearization attack. Then, we show how to perform a 2-stage MITM attack on LowMC. The first stage reduces the key candidates corresponding to a fraction of key bits of the master key. The second MITM stage between this reduced candidate set and the remaining fraction of key bits successfully recovers the master key. We show that the combined computational complexity of both these stages is significantly lower than those reported in the ToSC paper by Banik et al.
2020
TOSC
Swap and Rotate: Lightweight Linear Layers for SPN-based Blockciphers 📺
In CHES 2017, Jean et al. presented a paper on “Bit-Sliding” in which the authors proposed lightweight constructions for SPN based block ciphers like AES, PRESENT and SKINNY. The main idea behind these constructions was to reduce the length of the datapath to 1 bit and to reformulate the linear layer for these ciphers so that they require fewer scan flip-flops (which have built-in multiplexer functionality and so larger in area as compared to a simple flip-flop). In this paper, we develop their idea even further in few separate directions.First, we prove that given an arbitrary linear transformation, it is always possible to construct the linear layer using merely 2 scan flip-flops. This points to an optimistic venue to follow to gain further GE reductions, yet the straightforward application of the techniques in our proof to PRESENT and GIFT leads to inefficient implementations of the linear layer, as reducing ourselves to 2 scan flip-flops setting requires thousands of clock cycles and leads to very high latency.Equipped with the well-established formalism on permutation groups, we explore whether we can reduce the number of clock cycles to a practical level, i.e. few hundreds, by adding few more pairs of scan flip flops. For PRESENT, we show that 4 (resp. 8, 12) scan flip-flops are sufficient to complete the permutation layer in 384 (resp. 256, 128) clock cycles. For GIFT, we show that 4 (resp. 8, 10) scan flip flops correspond to 320 (resp. 192, 128) clock cycles. Finally, in order to provide the best of the two worlds (i.e. circuit area and latency), we push our scan flip-flop choices even further to completely eliminate the latency incurred by the permutation layer, without compromising our stringent GE budget. We show that not only 12 scan flip flops are sufficient to execute PRESENT permutation in 64 clock cycles, but also the same scan flip flops can be used readily in a combined encryption decryption circuit. Our final design of PRESENT and GIFT beat the record of Jean et al. and Banik et al. in both latency and in circuit-size metric. We believe that the techniques presented in our work can also be used at choosing bit-sliding-friendly linear layer permutations for the future SPN-based designs.
2020
ASIACRYPT
Determining the Core Primitive for Optimally Secure Ratcheting 📺
Fatih Balli Paul Rösler Serge Vaudenay
After ratcheting attracted attention mostly due to practical real-world protocols, recently a line of work studied ratcheting as a primitive from a theoretic point of view. Literature in this line, pursuing the strongest security of ratcheting one can hope for, utilized for constructions strong, yet inefficient key-updatable primitives – based on hierarchical identity based encryption (HIBE). As none of these works formally justified utilizing these building blocks, we answer the yet open question under which conditions their use is actually necessary. We revisit these strong notions of ratcheted key exchange (RKE), and propose a more realistic (slightly stronger) security definition. In this security definition, both exposure of participants' local secrets and attacks against executions' randomness are considered. While these two attacks were partially considered in previous work, we are the first to unify them cleanly in a natural game based notion. Our definitions are based on the systematic RKE notion by Poettering and Rösler (CRYPTO 2018). Due to slight (but meaningful) changes to regard attacks against randomness, we are ultimately able to show that, in order to fulfill strong security for RKE, public key cryptography with (independently) updatable key pairs is a necessary building block. Surprisingly, this implication already holds for the simplest RKE variant. Hence, (1) we model optimally secure RKE under randomness manipulation to cover realistic attacks, (2) we (provably) extract the core primitive that is necessary to realize strongly secure RKE, and (3) our results indicate which relaxations in security allow for constructions that only rely on standard public key cryptography.
2020
TOSC
Cryptanalysis of LowMC instances using single plaintext/ciphertext pair
Arguably one of the main applications of the LowMC family ciphers is in the post-quantum signature scheme PICNIC. Although LowMC family ciphers have been studied from a cryptanalytic point of view before, none of these studies were directly concerned with the actual use case of this cipher in PICNIC signature scheme. Due to the design paradigm of PICNIC, an adversary trying to perform a forgery attack on the signature scheme instantiated with LowMC would have access to only a single given plaintext/ciphertext pair, i.e. an adversary would only be able to perform attacks with data complexity 1 in a known-plaintext attack scenario. This restriction makes it impossible to employ classical cryptanalysis methodologies such as differential and linear cryptanalysis. In this paper we introduce two key-recovery attacks, both in known-plaintext model and of data complexity 1 for two variants of LowMC, both instances of the LowMC cryptanalysis challenge.
2019
EUROCRYPT
Misuse Attacks on Post-quantum Cryptosystems 📺
Many post-quantum cryptosystems which have been proposed in the National Institute of Standards and Technology (NIST) standardization process follow the same meta-algorithm, but in different algebras or different encoding methods. They usually propose two constructions, one being weaker and the other requiring a random oracle. We focus on the weak version of nine submissions to NIST. Submitters claim no security when the secret key is used several times. In this paper, we analyze how easy it is to run a key recovery under multiple key reuse. We mount a classical key recovery under plaintext checking attacks (i.e., with a plaintext checking oracle saying if a given ciphertext decrypts well to a given plaintext) and a quantum key recovery under chosen ciphertext attacks. In the latter case, we assume quantum access to the decryption oracle.
2017
CRYPTO
2016
ASIACRYPT
2016
ASIACRYPT
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
FSE
2015
FSE
2015
EUROCRYPT
2015
CRYPTO
2015
ASIACRYPT
2013
FSE
2013
FSE
2012
CRYPTO
2012
FSE
2011
EUROCRYPT
2011
JOFC
2010
EPRINT
The Extended Access Control for Machine Readable Travel Documents
Rafik Chaabouni Serge Vaudenay
Machine Readable travel documents have been rapidly put in place since 2004. The initial standard was made by the ICAO and it has been quickly followed by the Extended Access Control (EAC). In this paper we discuss about the evolution of these standards and more precisely on the evolution of EAC. We intend to give a realistic survey on these standards. We discuss about their problems, such as the inexistence of a clock in the biometric passports and the absence of a switch preventing the lecture of a closed passport. We also look at the issue with retrocompatibility that could be easily solved and the issue with terminal revocation that is harder.
2010
CHES
2009
CHES
2009
EUROCRYPT
2008
ASIACRYPT
2008
JOFC
2007
ASIACRYPT
2006
PKC
2006
EUROCRYPT
2005
CRYPTO
2005
CRYPTO
2004
ASIACRYPT
2004
ASIACRYPT
2004
ASIACRYPT
2004
CRYPTO
2004
PKC
2003
CRYPTO
2003
FSE
2003
PKC
2003
JOFC
2002
EUROCRYPT
2001
JOFC
2000
ASIACRYPT
2000
CHES
2000
FSE
2000
PKC
1999
ASIACRYPT
On the Lai-Massey Scheme
Serge Vaudenay
1999
EUROCRYPT
1999
FSE
1998
CRYPTO
1998
FSE
CS-Cipher
Jacques Stern Serge Vaudenay
1998
JOFC
1997
FSE
1997
JOFC
1996
ASIACRYPT
1996
ASIACRYPT
1996
CRYPTO
Hidden Collisions on DSS
Serge Vaudenay
1996
FSE
1994
EUROCRYPT
1994
EUROCRYPT
1994
EUROCRYPT
1994
FSE
1993
CRYPTO
1993
FSE
1992
CRYPTO

Program Committees

PKC 2020
Asiacrypt 2017
Asiacrypt 2016
FSE 2016
Asiacrypt 2015
FSE 2014
Eurocrypt 2014
FSE 2010
Asiacrypt 2010
Asiacrypt 2009
PKC 2009
FSE 2009
Crypto 2008
PKC 2007
Asiacrypt 2007
CHES 2007
FSE 2007
Asiacrypt 2006
Eurocrypt 2006 (Program chair)
PKC 2005 (Program chair)
FSE 2005
PKC 2004
Crypto 2004
Asiacrypt 2004
FSE 2004
CHES 2004
Eurocrypt 2003
PKC 2003
FSE 2003
Asiacrypt 2002
PKC 2000
Asiacrypt 2000
FSE 2000
FSE 1999
Crypto 1999
FSE 1998 (Program chair)
Eurocrypt 1998
Eurocrypt 1996
Crypto 1995