Search

Your search keyword '"Marc Fischlin"' showing total 230 results
Start Over Author "Marc Fischlin"
230 results on '"Marc Fischlin"'

201. Robust Multi-property Combiners for Hash Functions Revisited

Author

Anja Lehmann, Krzysztof Pietrzak, Marc Fischlin, and Cryptology

Subjects
Hash function, Pseudorandomness, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Random oracle, Set (abstract data type), 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Cryptographic hash function, 020201 artificial intelligence & image processing, Message authentication code, Perfect hash function, Algorithm, Mathematics
Abstract

A robust multi-property combiner for a set of security properties merges two hash functions such that the resulting function satisfies each of the properties which at least one of the two starting functions has. Fischlin and Lehmann (TCC 2008) recently constructed a combiner which simultaneously preserves collision-resistance, target collision-resistance, message authentication, pseudorandomness and indifferentiability from a random oracle ( IRO ). Their combiner produces outputs of 5nbits, where ndenotes the output length of the underlying hash functions. In this paper we propose improved combiners with shorter outputs. By sacrificing the indifferentiability from random oracles we obtain a combiner which preserves all of the other aforementioned properties but with output length 2nonly. This matches a lower bound for black-box combiners for collision-resistance as the only property, showing that the other properties can be achieved without penalizing the length of the hash values. We then propose a combiner which also preserves the IRO property, slightly increasing the output length to 2n+ i¾?(logn). Finally, we show that a twist on our combiners also makes them robust for one-wayness (but at the price of a fixed input length).

Published
2008
Full Text
View/download PDF

202. A Closer Look at PKI: Security and Efficiency

Author

Bogdan Warinschi, Alexandra Boldyreva, Adriana Palacio, and Marc Fischlin

Subjects
Public key certificate, Computer science, business.industry, Certificate policy, Computer security, computer.software_genre, Encryption, Self-signed certificate, Public-key cryptography, Root certificate, Certificate authority, business, Implicit certificate, computer
Abstract

In this paper we take a closer look at the security and efficiency of public-key encryption and signature schemes in public-key infrastructures (PKI). Unlike traditional analyses which assume an "ideal" implementation of the PKI, we focus on the security of joint constructions that consider the certification authority (CA) and the users, and include a key-registration protocol and the algorithms of an encryption or a signature scheme. We therefore consider significantly broader adversarial capabilities. Our analysis clarifies and validates several crucial aspects such as the amount of trust put in the CA, the necessity and specifics of proofs of possession of secret keys, and the security of the basic primitives in this more complex setting. We also provide constructions for encryption and signature schemes that provably satisfy our strong security definitions and are more efficient than the corresponding traditional constructions that assume a digital certificate issued by the CA must be verified whenever a public key is used. Our results address some important aspects for the design and standardization of PKIs, as targeted for example in the standards project ANSI X9.109.

Published
2007

203. On the Security of OAEP

Author

Marc Fischlin and Alexandra Boldyreva

Subjects
Theoretical computer science, Cryptographic primitive, business.industry, Plaintext, Encryption, business, Padding, Optimal asymmetric encryption padding, Oracle, Random oracle, Standard model (cryptography), Mathematics
Abstract

Currently, the best and only evidence of the security of the OAEP encryption scheme is a proof in the contentious random oracle model. Here we give further arguments in support of the security of OAEP. We first show that partial instantiations, where one of the two random oracles used in OAEP is instantiated by a function family, can be provably secure (still in the random oracle model). For various security statements about OAEP we specify sufficient conditions for the instantiating function families that, in some cases, are realizable through standard cryptographic primitives and, in other cases, may currently not be known to be achievable but appear moderate and plausible. Furthermore, we give the first non-trivial security result about fully instantiated OAEP in the standard model, where both oracles are instantiated simultaneously. Namely, we show that instantiating both random oracles in OAEP by modest functions implies non-malleability under chosen plaintext attacks for random messages. We also discuss the implications, especially of the full instantiation result, to the usage of OAEP for secure hybird encryption (as required in SSL/TLS, for example).

Published
2006

204. Analysis of Random Oracle Instantiation Scenarios for OAEP and Other Practical Schemes

Author

Marc Fischlin and Alexandra Boldyreva

Subjects
Pseudorandom number generator, Theoretical computer science, Computer science, business.industry, Hash function, Cryptography, Encryption, Random oracle, Pseudorandom function family, Digital signature, Hybrid cryptosystem, Verifiable secret sharing, business, Algorithm, Optimal asymmetric encryption padding, Full Domain Hash
Abstract

We investigate several previously suggested scenarios of instantiating random oracles (ROs) with “realizable” primitives in cryptographic schemes. As candidates for such “instantiating” primitives we pick perfectly one-way hash functions (POWHFs) and verifiable pseudorandom functions (VPRFs). Our analysis focuses on the most practical encryption schemes such as OAEP and its variant PSS-E and the Fujisaki-Okamoto hybrid encryption scheme. We also consider the RSA Full Domain Hash (FDH) signature scheme. We first show that some previous beliefs about instantiations for some of these schemes are not true. Namely we show that, contrary to Canetti's conjecture, in general one cannot instantiate either one of the two ROs in the OAEP encryption scheme by POWHFs without losing security. We also confirm through the FDH signature scheme that the straightforward instantiation of ROs with VPRFs may result in insecure schemes, in contrast to regular pseudorandom functions which can provably replace ROs (in a well-defined way). But unlike a growing number of papers on negative results about ROs, we bring some good news. We show that one can realize one of the two ROs in a variant of the PSS-E encryption scheme and either one of the two ROs in the Fujisaki-Okamoto hybrid encryption scheme through POWHFs, while preserving the IND-CCA security in both cases (still in the RO model). Although this partial instantiation in form of substituting only one RO does not help to break out of the random oracle model, it yet gives a better understanding of the necessary properties of the primitives and also constitutes a better security heuristic.

Published
2005

205. A Privacy-Friendly Loyalty System Based on Discrete Logarithms over Elliptic Curves

Author

Marc Fischlin, Matthias Enzmann, and Markus Schneider

Subjects
business.industry, Computer science, media_common.quotation_subject, Loyalty, Internet privacy, ComputingMilieux_COMPUTERSANDSOCIETY, Customer relationship management, Computer security, computer.software_genre, business, Electronic funds transfer, computer, media_common
Abstract

Systems for the support of customer relationship management are becoming increasingly attractive for vendors. Loyalty systems provide an interesting possibility for vendors in customer relationship management. This holds for both real world and online vendors. However, beside some potential benefits of a loyalty system, customers may also fear an invasion into their privacy, and may thus refuse to participate in such programs. In this paper, we present a privacy-friendly loyalty system to be used by online vendors to issue loyalty points. The system prevents vendors from exploiting data for the creation of customer profiles by providing unconditional unlinkability of loyalty points with regard to purchases. In the proposed system, we apply the difficulty for the computation of discrete logarithms in a group of prime order to construct a secure and privacy-friendly counter. More precisely, all computations are carried out over special cryptographic groups based on elliptic curves where the decisional Diffie-Hellman problems can be solved easily while the computational Diffie-Hellman is believed to be hard.

Published
2004

206. Topics in Cryptology - CT-RSA 2009 : The Cryptographers' Track at the RSA Conference 2009, San Francisco,CA, USA, April 20-24, 2009, Proceedings

Author

Marc Fischlin and Marc Fischlin

Subjects
Kongress, San Francisco (Calif., 2009), Computer security--Congresses, Cryptography--Congresses, Kryptologie--San Francisco <Calif., 2009>--Kon, Kryptologie
Abstract

This book constitutes the refereed proceedings of the Cryptographers'Track at the RSA Conference 2009, CT-RSA 2009, held in San Francisco, CA, USA in April 2009. The 31 revised full papers presented were carefully reviewed and selected from 93 submissions. The papers are organized in topical sections on identity-based encryption, protocol analysis, two-party protocols, more than signatures, collisions for hash functions, cryptanalysis, alternative encryption, privacy and anonymity, efficiency improvements, multi-party protocols, security of encryption schemes as well as countermeasures and faults.

Published
2009

207. Progressive Verification: The Case of Message Authentication

Author

Marc Fischlin

Subjects
Authentication, Theoretical computer science, Cryptographic primitive, Computer science, business.industry, Hash function, Cryptography, Hash-based message authentication code, Computer security, computer.software_genre, Code generation, Message authentication code, business, computer, Data Authentication Algorithm, Block cipher
Abstract

We introduce the concept of progressive verification for cryptographic primitives like message authentication codes, signatures and identification. This principle overcomes the traditional property that the verifier remains oblivious about the validity of the verified instance until the full verification procedure is completed. Progressive verification basically says that the more work the verifier invests, the better can the verifier approximate the decision.

Published
2003

208. The Cramer-Shoup Strong-RSA Signature Scheme Revisited

Author

Marc Fischlin

Subjects
Public-key cryptography, Theoretical computer science, Merkle signature scheme, business.industry, Computer science, Strong RSA assumption, Cryptography, Group signature, business, Signature (logic), PKCS #1, Random oracle
Abstract

We discuss a modification of the Cramer-Shoup strong-RSA signature scheme. Our proposal also presumes the strong RSA assumption, but allows faster signing and verification and produces signatures of roughly half the size. Then we present a stateful version of our scheme where signing (but not verifying) becomes almost as efficient as with RSA-PSS. We also show how to turn our signature schemes into "lightweight" anonymous yet linkable group identification protocols without random oracles.

Published
2002

209. Lower bounds for the signature size of incremental schemes

Author

Marc Fischlin and Torwick, Ian

Subjects
TheoryofComputation_MISCELLANEOUS, Discrete mathematics, Computational complexity theory, Computer Science::Software Engineering, Substitution (algebra), ComputerApplications_COMPUTERSINOTHERSYSTEMS, Omega, Upper and lower bounds, Signature (logic), Nonlinear Sciences::Adaptation and Self-Organizing Systems, ddc:004, Constant (mathematics), Mathematics, Block (data storage)
Abstract

We show lower bounds for the signature size of incremental schemes which are secure against substitution attacks and support single block replacement. We prove that for documents of n blocks such schemes produce signatures of /spl Omega/(n/sup 1/(2+c)/) bits for any constant c>0. For schemes accessing only a single block resp. A constant number of blocks for each replacement this bound can be raised to /spl Omega/(n) resp. /spl Omega/(/spl radic/n). Additionally, we show that our technique yields a new lower bound for memory checkers.

Published
2002

210. Identification Protocols Secure against Reset Attacks

Author

Silvio Micali, Shafi Goldwasser, Marc Fischlin, and Mihir Bellare

Subjects
Deniable authentication, Computer science, business.industry, Cryptography, Adversary, Computer security, computer.software_genre, Identification (information), Asynchronous communication, Commitment scheme, State (computer science), Smart card, business, computer, Reset (computing)
Abstract

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.

Published
2001

211. Public-Key Cryptography (Dagstuhl Seminar 11391)

Author

Marc Fischlin and Anna Lysyanskaya and Ueli Maurer and Alexander May, Fischlin, Marc, Lysyanskaya, Anna, Maurer, Ueli, May, Alexander, Marc Fischlin and Anna Lysyanskaya and Ueli Maurer and Alexander May, Fischlin, Marc, Lysyanskaya, Anna, Maurer, Ueli, and May, Alexander

Abstract

From September 25th till September 30th, 2011, the Dagstuhl Seminar 11391 about ``Public-Key Cryptography'' took place at Schloss Dagstuhl. The meeting hosted 33 international researchers and incited active discussions about recent developments in this area.

Published
2012
Full Text
View/download PDF

212. Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions

Author

Marc Fischlin

Subjects
Polynomial, Concept class, Theoretical computer science, General Computer Science, business.industry, Computer Science::Information Retrieval, Cryptography, Theoretical Computer Science, Pseudorandom function family, Formal language, business, Equivalence (measure theory), Algorithm, Time complexity, Membership function, Computer Science::Databases, Computer Science(all), Mathematics
Abstract

We assume wlog that every learning algorithm with membership and equivalence queries proceeds in rounds. In each round it puts in parallel a polynomial number of queries and after receiving the answers, it performs internal computations before starting the next round. The query depth is defined by the number of rounds. In this paper we show that, assuming the existence of cryptographic one-way functions, for any fixed polynomial d(n) there exists a concept class that is efficiently and exactly learnable with membership queries in query depth d(n)+1, but cannot be weakly predicted with membership and equivalence queries in depth d(n). Hence, concerning the query depth, efficient learning algorithms for this concept class cannot be parallelized. We also discuss applications to random-self-reductions and coherent sets. Copyright 2001 Elsevier Science B.V. All rights reserved.

Full Text
View/download PDF

213. Authentication in Key-Exchange: Definitions, Relations and Composition

Author

Bogdan Warinschi, Marc Fischlin, and Cyprien Delpech de Saint Guilhem

Subjects
Authentication, Theoretical computer science, Computer science, 020206 networking & telecommunications, 02 engineering and technology, Predicate (mathematical logic), Space (commercial competition), Core (game theory), Secrecy, 0202 electrical engineering, electronic engineering, information engineering, Key (cryptography), 020201 artificial intelligence & image processing, Composition (language), Key exchange
Abstract

We present a systematic approach to define and study authentication notions in authenticated key-exchange protocols. We propose and use a flexible and expressive predicate-based definitional framework. Our definitions capture key and entity authentication, in both implicit and explicit variants, as well as key and entity confirmation, for authenticated key-exchange protocols. In particular, we capture critical notions in the authentication space such as key-compromise impersonation resistance and security against unknown key-share attacks. We first discuss these definitions within the Bellare-Rogaway model and then extend them to Canetti-Krawczyk-style models. We then show two useful applications of our framework. First, we look at the authentication guarantees of three representative protocols to draw several useful lessons for protocol design. The core technical contribution of this paper is then to formally establish that composition of secure implicitly authenticated key-exchange with subsequent confirmation protocols yields explicit authentication guarantees. Without a formal separation of implicit and explicit authentication from secrecy, a proof of this folklore result could not have been established.

Full Text
View/download PDF

217. Improved Differential-Linear Cryptanalysis of 7-Round Chaskey with Partitioning

Author

Gaëtan Leurent, Security, Cryptology and Transmissions (SECRET), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Marc Fischlin, and Jean-Sébastien Coron

Subjects
FEAL, Differential cryptanalysis, Computer science, linear cryptanalysis, Chaskey, 0102 computer and information sciences, 02 engineering and technology, Impossible differential cryptanalysis, Higher-order differential cryptanalysis, 01 natural sciences, addition, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Piling-up lemma, 010201 computation theory & mathematics, partitioning, Linear cryptanalysis, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Integral cryptanalysis, Mod n cryptanalysis, ARX, Algorithm, Block cipher
Abstract

In this work we study the security of Chaskey, a recent lightweight MAC designed by Mouha et al., currently being considered for standardization by ISO/IEC and ITU-T. Chaskey uses an ARX structure very similar to SipHash. We present the first cryptanalysis of Chaskey in the single user setting, with a differential-linear attack against 6 and 7 rounds, hinting that the full version of Chaskey with 8 rounds has a rather small security margin. In response to these attacks, a 12-round version has been proposed by the designers. To improve the complexity of the differential-linear cryptanalysis, we refine a partitioning technique recently proposed by Biham and Carmeli to improve the linear cryptanalysis of addition operations. We also propose an analogue improvement of differential cryptanalysis of addition operations. Roughly speaking, these techniques reduce the data complexity of linear and differential attacks, at the cost of more processing time per data. It can be seen as the analogue for ARX ciphers of partial key guess and partial decryption for SBox-based ciphers. When applied to the differential-linear attack against Chaskey, this partitioning technique greatly reduces the data complexity, and this also results in a reduced time complexity. While a basic differential-linear attack on 7 round takes $$2^{78}$$278 data and time respectively $$2^{35}$$235 for 6 rounds, the improved attack requires only $$2^{48}$$248 data and $$2^{67}$$267 time respectively $$2^{25}$$225 data and $$2^{29}$$229 time for 6 rounds. We also show an application of the partitioning technique to FEAL-8X, and we hope that this technique will lead to a better understanding of the security of ARX designs.

Published
2016

218. Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts

Author

Pierrick, Méaux, Journault, Anthony, Standaert, François-Xavier, Carlet, Claude, Advances in Cryptology - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL), Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Catholique de Louvain = Catholic University of Louvain (UCL), Université Paris 8 Vincennes-Saint-Denis - Département de Mathématiques, Université Paris 8 Vincennes-Saint-Denis (UP8), Laboratoire Analyse, Géométrie et Applications (LAGA), Université Paris 8 Vincennes-Saint-Denis (UP8)-Université Paris 13 (UP13)-Institut Galilée-Centre National de la Recherche Scientifique (CNRS), Marc Fischlin, Jean-Sébastien Coron, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris 8 Vincennes-Saint-Denis (UP8)-Centre National de la Recherche Scientifique (CNRS)-Institut Galilée-Université Paris 13 (UP13), UCL - SST/ICTM/ELEN-Pôle en ingénierie électrique, Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Differential cryptanalysis, Theoretical computer science, Ciphers, Computer science, T-function, Stream cipher attack, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Stream ciphers, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, Ciphertext, 0202 electrical engineering, electronic engineering, information engineering, Fully Homomorphic Encryption (FHE), Correlation attack, Stream cipher, Block size, Key schedule, Computer Science::Cryptography and Security
Abstract

International audience; Symmetric ciphers purposed for Fully Homomorphic Encryption FHE have recently been proposed for two main reasons. First, minimizing the implementation time and memory overheads that are inherent to current FHE schemes. Second, improving the homomorphic capacity, i.e. the amount of operations that one can perform on homomorphic ciphertexts before bootstrapping, which amounts to limit their level of noise. Existing solutions for this purpose suggest a gap between block ciphers and stream ciphers. The first ones typically allow a constant but small homomorphic capacity, due to the iteration of rounds eventually leading to complex Boolean functions hence large noise. The second ones typically allow a larger homomorphic capacity for the first ciphertext blocks, that decreases with the number of ciphertext blocks due to the increasing Boolean complexity of the stream ciphers' output. In this paper, we aim to combine the best of these two worlds, and propose a new stream cipher construction that allows constant and smaller noise. Its main idea is to apply a Boolean filter function to a public bit permutation of a constant key register, so that the Boolean complexity of the stream cipher outputs is constant. We also propose an instantiation of the filter function designed to exploit recent 3rd-generation FHE schemes, where the error growth is quasi-additive when adequately multiplying ciphertexts with the same amount of noise. In order to stimulate further investigation, we then specify a few instances of this stream cipher, for which we provide a preliminary security analysis. We finally highlight the good properties of our stream cipher regarding the other goal of minimizing the time and memory complexity of calculus delegation for 2nd-generation FHE﾿schemes. We conclude the paper with open problems related to the large design space opened by these new constructions.

Published
2016

219. Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems

Author

Nicolas Gama, Xiang Xie, Malika Izabachène, Phong Q. Nguyen, Laboratoire de Mathématiques de Versailles (LMV), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Combination of approaches to the security of infinite states systems (CASSIS), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)-Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique de l'école normale supérieure (LIENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Huawei Technologies [Shanghaï], Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Inria Nancy - Grand Est, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Inpher, Département d'Architectures, Conception et Logiciels Embarqués-LIST (DACLE-LIST), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Japanese French Laboratory for Informatics (JFLI), Centre National de la Recherche Scientifique (CNRS)-The University of Tokyo (UTokyo)-Université Pierre et Marie Curie - Paris 6 (UPMC)-National Institute of Informatics (NII), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), IACR, Marc Fischlin, Jean-Sébastien Coron, Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), National Institute of Informatics (NII)-Université Pierre et Marie Curie - Paris 6 (UPMC)-The University of Tokyo (UTokyo)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
Discrete mathematics, Noise Overhead, Generalization, Random Lattice, 010102 general mathematics, Integer lattice, Finite Abelian Group, Homomorphic encryption, 0102 computer and information sciences, Short Base, 01 natural sciences, Average-case Reductions, Combinatorics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, Lattice (order), Lattice-based cryptography, 0101 mathematics, Abelian group, Lattice reduction, [MATH]Mathematics [math], Boolean function, Mathematics
Abstract

In lattice cryptography, worst-case to average-case reductions rely on two problems: Ajtai's SIS and Regev's LWE, which both refer to a very small class of random lattices related to the group $$G=\mathbb {Z}_q^n$$G=Zqn. We generalize worst-case to average-case reductions to all integer lattices of sufficiently large determinant, by allowing G to be any sufficiently large finite abelian group. Our maini¾?tool is a novel generalization of lattice reduction, which we call structural lattice reduction: given a finite abelian group G and a lattice L, it finds a short basis of some lattice $$\bar{L}$$Li¾? such that $$L \subseteq \bar{L}$$L⊆Li¾? and $$\bar{L}/L \simeq G$$Li¾?/Li¾?G. Our group generalizations of SIS and LWE allow us to abstract lattice cryptography, yet preserve worst-case assumptions: as an illustration, we provide a somewhat conceptually simpler generalization of the Alperin-Sheriff-Peikert variant of the Gentry-Sahai-Waters homomorphic scheme. We introduce homomorphic mux gates, which allows us to homomorphically evaluate any boolean function with a noise overhead proportional to the square root of its number of variables, and bootstrap the full scheme using only a linear noise overhead.

Published
2016

220. Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields

Author

Aurore Guillevic, François Morain, Pierrick Gaudry, Razvan Barbulescu, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Geometry, arithmetic, algorithms, codes and encryption (GRACE), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Cryptology, Arithmetic: Hardware and Software (CARAMEL), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Elisabeth Oswald and Marc Fischlin, ANR-12-BS02-0001,CATREL,Cribles: Améliorations Théoriques et Résolution Effective du Logarithme Discret.(2012), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Logarithm, 020206 networking & telecommunications, Field (mathematics), 010103 numerical & computational mathematics, 02 engineering and technology, Discrete logarithm computation, 01 natural sciences, Baby-step giant-step, Prime (order theory), General number field sieve, Combinatorics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Finite field, Discrete logarithm, NFS, 0202 electrical engineering, electronic engineering, information engineering, XTR, 0101 mathematics, public-key cryptography, Mathematics
Abstract

International audience; The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF$(p^n)$ where $n$ is a small integer greater than 1. Though less studied than the small characteristic case or the prime field case, the difficulty of this problem is at the heart of security evaluations for torus-based and pairing-based cryptography. The best known method for solving this problem is the Number Field Sieve (NFS). A key ingredient in this algorithm is the ability to find good polynomials that define the extension fields used in NFS. We design two new methods for this task, modifying the asymptotic complexity and paving the way for record-breaking computations. We exemplify these results with the computation of discrete logarithms over a field GF$(p^2)$ whose cardinality is 180 digits (595 bits) long.

Published
2015

221. The Sum Can Be Weaker Than Each Part

Author

Gaëtan Leurent, Lei Wang, Security, Cryptology and Transmissions (SECRET), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Nanyang Technological University [Singapour], Elisabeth Oswald, and Marc Fischlin

Subjects
Hash function, XOR combiner, SWIFFT, Hash functions, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, MDC-2, 01 natural sciences, K-independent hashing, Combinatorics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Collision resistance, Fowler–Noll–Vo hash function, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Security of cryptographic hash functions, combiners, preimage attack, Algorithm, Double hashing, Mathematics
Abstract

International audience; In this paper we study the security of summing the outputs of two independent hash functions, in an effort to increase the security of the resulting design, or to hedge against the failure of one of the hash functions. The exclusive-or (XOR) combiner H1(M)⊕H2(M) is one of the two most classical combiners, together with the concatenation combiner H1(M) H2(M). While the security of the concatenation of two hash functions is well understood since Joux's seminal work on multicollisions, the security of the sum of two hash functions has been much less studied. The XOR combiner is well known as a good PRF and MAC combiner, and is used in practice in TLS versions 1.0 and 1.1. In a hash function setting, Hoch and Shamir have shown that if the compression functions are modeled as random oracles, or even weak random oracles (i.e. they can easily be inverted – in particular H1 and H2 offer no security), H1 ⊕ H2 is indifferentiable from a random oracle up to the birthday bound. In this work, we focus on the preimage resistance of the sum of two narrow-pipe n-bit hash functions, following the Merkle-Damgård or HAIFA structure (the internal state size and the output size are both n bits). We show a rather surprising result: the sum of two such hash functions, e.g. SHA-512 ⊕ Whirlpool, can never provide n-bit security for preimage resistance. More precisely, we present a generic preimage attack with a complexity of O(2 5n/6). While it is already known that the XOR combiner is not preserving for preimage resistance (i.e. there might be some instantiations where the hash functions are secure but the sum is not), our result is much stronger: for any narrow-pipe functions, the sum is not preimage resistant. Besides, we also provide concrete preimage attacks on the XOR combiner (and the concatenation combiner) when one or both of the compression functions are weak; this complements Hoch and Shamir's proof by showing its tightness for preimage resistance. Of independent interests, one of our main technical contributions is a novel structure to control simultaneously the behavior of independent hash computations which share the same input message. We hope that breaking the pairwise relationship between their internal states will have applications in related settings.

Published
2015

222. Disjunctions for Hash Proof Systems: New Constructions and Applications

Author

Fabrice Benhamouda, Michel Abdalla, David Pointcheval, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL), Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), IACR, European Project: 339563,EC:FP7:ERC,ERC-2013-ADG,CRYPTOCLOUD(2014), Département d'informatique de l'École normale supérieure (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Elisabeth Oswald, Marc Fischlin, ANR-12-INSE-0014,SIMPATIC,SIM et théorie des couplages pour la sécurité de l'information et des communications(2012), and European Project: 288349,EC:FP7:ICT,FP7-ICT-2011-EU-Brazil,SECFUNET(2011)

Subjects
Non-interactive zero-knowledge proof, Zero-knowledge password proof, Theoretical computer science, Hash proof system, Hash function, Group password authenticated key exchange, Linearly homomorphic signature, Authenticated Key Exchange, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Rainbow table, SHA-2, Hash chain, Cryptographic hash function, Threshold encryption, Structure preserving primitive, Double hashing, Mathematics
Abstract

International audience; Hash Proof Systems were first introduced by Cramer and Shoup (Eurocrypt’02) as a tool to construct efficient chosen-ciphertext-secure encryption schemes. Since then, they have found many other applications, including password authenticated key exchange, oblivious transfer, and zero-knowledge arguments. One of the aspects that makes hash proof systems so interesting and powerful is that they can be seen as implicit proofs of membership for certain languages. As a result, by extending the family of languages that they can handle, one often obtains new applications or new ways to understand existing schemes. In this paper, we show how to construct hash proof systems for the disjunction of languages defined generically over cyclic, bilinear, and multilinear groups. Among other applications, this enables us to construct the most efficient one-time simulation-sound (quasi-adaptive) non-interactive zero-knowledge arguments for linear languages over cyclic groups, the first one-round group password-authenticated key exchange without random oracles, the most efficient threshold structure-preserving chosen-ciphertext-secure encryption scheme, and the most efficient one-round password authenticated key exchange in the UC framework.

Published
2014

223. Universal Security; From bits and mips to pools, lakes - and beyond

Author

Lenstra, Arjen, Kleinjung, Thorsten, Thomé, Emmanuel, Laboratory for Cryptologic Algorithms (LACAL), Ecole Polytechnique Fédérale de Lausanne (EPFL), Cryptology, Arithmetic: Hardware and Software (CARAMEL), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Marc Fischlin and Stefan Katzenbeisser, Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract

Humoristic; International audience; The relation between cryptographic key lengths and security depends on the cryptosystem used. This leads to confusion and to insecure parameter choices. In this note a universal security measure is proposed that puts all cryptographic primitives on the same footing, thereby making it easier to get comparable security across the board.

Published
2013

224. From Selective to Full Security: Semi-Generic Transformations in the Standard Model

Author

Michel Abdalla, Vadim Lyubashevsky, Dario Fiore, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Institute IMDEA Software [Madrid], Marc Fischlin and Johannes Buchmann and Mark Manulis, Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Scheme (programming language), Theoretical computer science, business.industry, Hash function, 0102 computer and information sciences, 02 engineering and technology, Encryption, 01 natural sciences, Identity (music), Random oracle, Memory leak, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Transformation (function), 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, business, computer, Mathematics, computer.programming_language, Standard model (cryptography)
Abstract

International audience; In this paper, we propose an efficient, standard model, semigeneric transformation of selective-secure (Hierarchical) Identity-Based Encryption schemes into fully secure ones. The main step is a procedure that uses admissible hash functions (whose existence is implied by collision-resistant hash functions) to convert any selective-secure wildcarded identity-based encryption (WIBE) scheme into a fully secure (H)IBE scheme. Since building a selective-secureWIBE, especially with a selective-secure HIBE already in hand, is usually much less involved than directly building a fully secure HIBE, this transform already significantly simplifies the latter task. This black-box transformation easily extends to schemes secure in the Continual Memory Leakage (CML) model of Brakerski et al. (FOCS 2010), which allows us obtain a new fully secure IBE in that model. We furthermore show that if a selective-secure HIBE scheme satisfies a particular security notion, then it can be generically transformed into a selective-secure WIBE. We demonstrate that several current schemes already fit this new definition, while some others that do not obviously satisfy it can still be easily modified into a selective-secure WIBE.

Published
2012

225. Password-Based Authenticated Key Exchange

Author

David Pointcheval, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Marc Fischlin and Johannes Buchmann and Mark Manulis, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
Password, 0303 health sciences, Authentication, Encrypted key exchange, Dictionary attack, Strong key, Computer science, Group setting, 02 engineering and technology, Computer security, computer.software_genre, Authenticated Key Exchange, 03 medical and health sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, computer, 030304 developmental biology
Abstract

International audience; Authenticated Key Exchange protocols enable several parties to establish a shared cryptographically strong key over an insecure network using various authentication means, such as strong cryptographic keys or short (i.e., low-entropy) common secrets. The latter example is definitely the most interesting in practice, since no additional device is required, but just a human-memorable password, for authenticating the players. After the seminal work by Bellovin and Merritt, many settings and security notions have been defined, and many protocols have been proposed, in the two-user setting and in the group setting.

Published
2012

226. Generating Provable Primes Efficiently on Embedded Devices

Author

Benoit Feix, Christophe Clavier, Pascal Paillier, Loïc Thierry, DMI (XLIM-DMI), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Cryptoexperts, CryptoExperts, Marc Fischlin, Johannes Buchmann, and Mark Manulis

Subjects
Modular exponentiation, Theoretical computer science, business.industry, Prime number, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Constructive, Public-key cryptography, Embedded software, Embedded system, 0202 electrical engineering, electronic engineering, information engineering, Entropy (information theory), 020201 artificial intelligence & image processing, Smart card, 0101 mathematics, business, Provable prime, Mathematics
Abstract

ISBN : 978-3-642-30056-1; International audience; This paper introduces new techniques to generate provable prime numbers efficiently on embedded devices such as smartcards, based on variants of Pocklington's and the Brillhart-Lehmer-Selfridge-Tuckerman-Wagstaff theorems. We introduce two new generators that, combined with cryptoprocessor-specific optimizations, open the way to efficient and tamper-resistant on-board generation of provable primes. We also report practical results from our implementations. Both our theoretical and experimental results show that constructive methods can generate provable primes essentially as efficiently as state-of-the-art generators for probable primes based on Fermat and Miller-Rabin pseudo-tests. We evaluate the output entropy of our two generators and provide techniques to ensure a high level of resistance against physical attacks. This paper intends to provide practitioners with the first practical solutions for fast and secure generation of provable primes in embedded security devices.

Published
2012

227. Ring-LWE in Polynomial Rings

Author

Léo Ducas, Alain Durmus, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Marc Fischlin, Johannes Buchmann, Mark Manulis, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
Discrete mathematics, Polynomial, Ring (mathematics), Modulo, Polynomial ring, 010102 general mathematics, Order (ring theory), 0102 computer and information sciences, 01 natural sciences, Combinatorics, Reduction (complexity), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Transformation (function), 010201 computation theory & mathematics, Fractional ideal, 0101 mathematics, Mathematics
Abstract

International audience; The Ring-LWE problem, introduced by Lyubashevsky, Peikert, and Regev (Eurocrypt 2010), has been steadily finding many uses in numerous cryptographic applications. Still, the Ring-LWE problem defined in [LPR10] involves the fractional ideal R ∨, the dual of the ring R , which is the source of many theoretical and implementation technicalities. Until now, getting rid of R ∨, required some relatively complex transformation that substantially increase the magnitude of the error polynomial and the practical complexity to sample it. It is only for rings R =ℤ[X ]/(X n +1) where n a power of 2, that this transformation is simple and benign.In this work we show that by applying a different, and much simpler transformation, one can transfer the results from [LPR10] into an "easy-to-use" Ring-LWE setting (i.e. without the dual ring R ∨), with only a very slight increase in the magnitude of the noise coefficients. Additionally, we show that creating the correct noise distribution can also be simplified by generating a Gaussian distribution over a particular extension ring of R , and then performing a reduction modulo f (X ). In essence, our results show that one does not need to resort to using any algebraic structure that is more complicated than polynomial rings in order to fully utilize the hardness of the Ring-LWE problem as a building block for cryptographic applications.

Published
2012

228. Fault Attacks on RSA Public Keys: Left-To-Right Implementations are also Vulnerable

Author

Jean-Guillaume Dumas, Cécile Canovas, Louis Goubin, Alexandre Berzati, Commissariat à l'énergie atomique et aux énergies alternatives - Laboratoire d'Electronique et de Technologie de l'Information (CEA-LETI), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), Centre National de la Recherche Scientifique (CNRS)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), Calculs Algébriques et Systèmes Dynamiques (CASYS), Laboratoire Jean Kuntzmann (LJK), Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF), Marc Fischlin, Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS), and Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Exponentiation, Computer Science - Cryptography and Security, 02 engineering and technology, Computer security, computer.software_genre, Fault (power engineering), number theory, Public-key cryptography, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Factorization, RSA, 0202 electrical engineering, electronic engineering, information engineering, Cryptosystem, "Left-To-Right" exponentiation, Left-To-Right" exponentiation, Mathematics, business.industry, Prime number, 16. Peace & justice, fault attacks, 020202 computer hardware & architecture, Finite field, 020201 artificial intelligence & image processing, Fault model, business, computer, Cryptography and Security (cs.CR)
Abstract

International audience; After attacking the RSA by injecting fault and corresponding countermeasures, works appear now about the need for protecting RSA public elements against fault attacks. We provide here an extension of a recent attack based on the public modulus corruption. The difficulty to decompose the "Left-To-Right" exponentiation into partial multiplications is overcome by modifying the public modulus to a number with known factorization. This fault model is justified here by a complete study of faulty prime numbers with a fixed size. The good success rate of this attack combined with its practicability raises the question of using faults for changing algebraic properties of finite field based cryptosystems.

Published
2009

229. Adaptive-ID Secure Revocable Identity-Based Encryption

Author

Benoît Libert, Damien Vergnaud, Microelectronics laboratory (UCL Crypto Group), Université Catholique de Louvain = Catholic University of Louvain (UCL), Laboratoire d'informatique de l'école normale supérieure (LIENS), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Marc Fischlin, ANR-07-TCOM-0013,PACE,Pairings and Advances in Cryptology for E-cash(2007), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
Provable security, Public key certificate, Revocation, Computer science, business.industry, 020206 networking & telecommunications, Identity-based encryption, 0102 computer and information sciences, 02 engineering and technology, 16. Peace & justice, Computer security, computer.software_genre, Encryption, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, Probabilistic encryption, 0202 electrical engineering, electronic engineering, information engineering, Key (cryptography), Identity (object-oriented programming), 56-bit encryption, business, computer
Abstract

International audience; Identity-Based Encryption (IBE) offers an interesting alternative to PKI-enabled encryption as it eliminates the need for digital certificates. While revocation has been thoroughly studied in PKIs, few revocation mechanisms are known in the IBE setting. Until quite recently, the most convenient one was to augment identities with period numbers at encryption. All non-revoked receivers were thus forced to obtain a new decryption key at discrete time intervals, which places a significant burden on the authority. A more efficient method was suggested by Boldyreva, Goyal and Kumar at CCS'08. In their revocable IBE scheme, key updates have logarithmic (instead of linear in the original method) complexity for the trusted authority. Unfortunately, security could only be proved in the selective-ID setting where adversaries have to declare which identity will be their prey at the very beginning of the attack game. In this work, we describe an adaptive-ID secure revocable IBE scheme and thus solve a problem left open by Boldyreva et al..

Published
2009

230. Inferring Sequences Produced by Nonlinear Pseudorandom Number Generators Using Coppersmith's Methods

Author

Jean-Christophe Zapalowicz, Aurélie Bauer, Damien Vergnaud, Laboratoire de cryptographie de l'ANSSI (LCR), Agence nationale de la sécurité des systèmes d'information (ANSSI), Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Marc Fischlin, Johannes Buchmann & Mark Manulis, European Project: 216676,EC:FP7:ICT,FP7-ICT-2007-1,ECRYPT II(2008), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Discrete mathematics, Pseudorandom number generator, Euclidean lattice, Initial Seed, Unravelled linearization, medicine.medical_treatment, people.profession, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, Nonlinear system, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, medicine, LLL algorithm, Coppersmith’s techniques, 020201 artificial intelligence & image processing, Pseudorandom generators for polynomials, Algebraic number, Coppersmith, people, Mathematics, Nonlinear Pseudorandom number generators
Abstract

Number-theoretic pseudorandom generators work by iterating an algebraic map F (public or private) over a residue ring ℤN on a secret random initial seed value v 0 ∈ℤN to compute values $v_{n+1} = F(v_n) \bmod{N}$ for n ∈ℕ. They output some consecutive bits of the state value v n at each iteration and their efficiency and security are thus strongly related to the number of output bits. In 2005, Blackburn, Gomez-Perez, Gutierrez and Shparlinski proposed a deep analysis on the security of such generators. In this paper, we revisit the security of number-theoretic generators by proposing better attacks based on Coppersmith's techniques for finding small roots on polynomial equations. Using intricate constructions, we are able to significantly improve the security bounds obtained by Blackburn et al. .

Catalog

Books, media, physical & digital resources
See catalog results