Séminaire Cryptographie 2011/2012
Pour recevoir par e-mail les annonces de ce séminaire, vous pouvez vous inscrire sur la mailing list crypto.Pour aller directement au prochain séminaire
- Programme du premier trimestre 2011/2012
- Jeudi 8 septembre 2011: Yevgeniy Dodis
- Vendredi 23 septembre 2011: Soutenance de thèse de Mehdi Tibouchi
- Lundi 26 septembre 2011: Soutenance de thèse de Charles Bouillaguet
- Jeudi 29 septembre 2011: Orr Dunkelman
- Jeudi 13 octobre 2011: Takashi Nishide
- Jeudi 13 octobre 2011: Vincent Cheval
- Jeudi 24 novembre 2011: Soutenance d'habilitation à diriger des recherches de Michel Abdalla
- Jeudi 24 novembre 2011: Kenny Paterson
- Jeudi 24 novembre 2011: Ronald Cramer
- Programme du second trimestre 2011/2012
- Programme du troisième trimestre 2011/2012
Programme du premier trimestre 2011/2012
TOP
Jeudi 8 septembre 2011: Yevgeniy Dodis
New York University10h30 dans l'Amphi Evariste Galois - NIR
Leftover Hash Lemma, Revisited
- Abstract
- The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two drawbacks:
(1) Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are e-close to uniform, one must set v \leq m - 2*log(1/e), meaning that the entropy loss L = m-v \geq 2*log(1/e).
(2) Large Seed Length: the seed length n of universal hash function required by the LHL must be linear in the length of the source.
Quite surprisingly, we show that both limitations of the LHL --- large entropy loss and large seed --- can often be overcome (or, at least, mitigated) in various quite general scenarios. First, we show that entropy loss could be reduced to L=log(1/e) for the setting of deriving secret keys for a wide range of cryptographic applications, including all "unpredictability" applications (signatures, MACs, etc.) and also some prominent "indistinguishability" applications, including chosen plaintext (or ciphertext) attack secure (public- or symmetric-key) encryption schemes. Specifically, the security of these schemes gracefully degrades from e to at most e + sqrt(e * 2^{-L}). (Notice that, unlike standard LHL, this bound is meaningful even for negative entropy loss, when we extract more bits than the the min-entropy we have!)
Second, we study the soundness of the natural expand-then-extract approach, where one uses a pseudorandom generator (PRG) to expand a short "input seed" S into a longer "output seed" S', and then use the resulting S' as the seed required by the LHL (or, more generally, any randomness extractor). Unfortunately, we show that, in general, expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a "small" (logarithmic in the security of the PRG) number of bits; or (2) in minicrypt. Implication (2) suggests that the sample-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security!
TOP
Vendredi 23 septembre 2011: Soutenance de thèse de Mehdi Tibouchi
ENS & Univ. Luxembourg16 heures dans l'Amphi Évariste Galois - NIR
Hachage vers les courbes elliptiques et cryptanalyse de schémas RSA.
Jury :- Jean-Sébastien Coron - Université du Luxembourg (co-directeur)
- Pierre-Alain Fouque - ENS
- Pierrick Gaudry - CNRS/LORIA (rapporteur)
- Jean-François Mestre - Université Paris 7
- David Naccache - Université Paris II/ENS (co-directeur)
- Tatsuaki Okamoto - NTT Laboratories
- Igor Shparlinski - Macquarie University (rapporteur)
- Jacques Stern - ENS
Résumé : Cette thèse comporte deux parties distinctes, consacrées aux deux versants de la cryptologie: construction et analyse. Les travaux de construction, d'une part, concernent la cryptographie à base de courbes algébriques, et plus particulièrement le problème de l'encodage et du hachage à valeurs dans les courbes elliptiques. Nous avons notamment étudié certaines propriétés quantitatives de diverses fonctions d'encodage vers les courbes et obtenu une construction satisfaisante de fonctions de hachage à partir de ces encodages. Ces résultats utilisent principalement des méthodes d'arithmétique des corps de fonctions, de géométrie des courbes et des surfaces, et de sommes de caractères. Toujours en cryptographie à base de courbes elliptiques, nous avons également travaillé sur une question d'implémentation: l'obtention de formules d'addition et de doublement sûres et efficaces. Les travaux de cryptanalyse, d'autre part, ont porté sur divers cryptosystèmes fondés sur RSA, principalement des schémas de chiffrement et de signature. Nous avons en particulier obtenu et mis en œuvre des attaques sur des fonctions de remplissage (paddings) normalisées et d'usage encore répandu, comme ISO/IEC 9796-2 pour les signatures et PKCS#1 v1.5 pour le chiffrement. Nous nous sommes également intéressé aux attaques physiques par fautes sur les signatures RSA utilisant les restes chinois, et avons proposé une meilleure attaque sur les schémas RSA utilisant de petits sous-groupes. Les outils employés vont des techniques de calcul d'indice ou de réduction de réseaux à l'algorithmique efficace des polynômes de grand degré.
Abstract: This thesis consists of two independent parts, devoted to both aspects of cryptology: construction and analysis. Contributions to cryptography proper, on the one hand, address open questions in algebraic curve-based cryptography, particularly the problem of encoding and hashing to elliptic curves. We derive some quantitative results on curve-valued encoding functions, and give a satisfactory construction of hash functions based on those encodings, using a range of mathematical techniques from function field arithmetic, the algebraic geometry of curves and surfaces, and character sums. We also worked on a more implementation-related problem in elliptic curve cryptography, namely the construction of fast addition and doubling formulas. Our cryptanalytic work, on the other hand, focuses on RSA-based cryptosystems—mostly encryption and signature schemes. We have obtained and carried out new attacks on standardized padding schemes that remain in widespread use, including ISO/IEC 9796-2 for signatures and PKCS#1 v1.5 for encryption. We also propose new physical fault attacks on RSA signature schemes using the Chinese Remainder Theorem, and a stronger attack on RSA schemes relying on small hidden-order subgroups. The tools involved include index calculus, lattice reduction techniques and efficient arithmetic of large degree polynomials.
TOP
Lundi 26 septembre 2011: Soutenance de thèse de Charles Bouillaguet
ENS15 heures en Salle U ou V (Passage Rouge - Niveau -2)
Etudes d'hypothèses algorithmiques et analyse de primitives cryptographiques
Jury :- Hubert Comon-Lundh
- Joan Daemen (rapporteurs)
- Arnaud Durand
- Pierre-Alain Fouque (responsable scientifique)
- Henri Gilbert (rapporteurs)
- Ludovic Perret
- Vincent Rijmen
- Jacques Stern
Résumé : La cryptanalyse, anciennement l'art de déchiffrer les codes secrets, est aujourd'hui comprise dans un sens plus large, qui consiste à trouver toute sorte de défauts, des plus légers jusqu'au plus graves, dans des constructions cryptographiques. Cette thèse s'articule en trois partie, chacune consacrée à une famille de primitives cryptographiques. Les fonctions de hachage sont généralement des constructions itérées, où une brique de base est utilisée de façon répétée, conformément à mode opératoire. En 2004, 2005 et 2006, l'apparition d'attaques génériques, visant spécialement le mode opératoire de Merkle-Damgard, le plus répandu, a suscité des propositions de modes opératoires alternatifs. Les attaques génériques exploitent principalement le fait que l'état interne des fonctions de hachage a la même taille que leur sortie, ce qui permet de trouver et d'exploiter des collisions internes. Nos résultats tendent à montrer que cette difficulté est difficile à lever, car nous parvenons à monter des attaques en seconde préimage contre des tentatives, parfois exotiques, de ``réparer'' la construction de Merkle-Damgard. Dans une deuxième partie, nous nous intéressons à la cryptanalyse de l'AES, le système de chiffrement par bloc le plus répandu. Nous nous plaçons dans un modèle assez restrictif où la quantité de paires clair/chiffré disponible pour l'attaquant est très faible. Cela nous condamne à étudier des versions fortement réduites de l'AES, mais cela rend les attaques obtenues plus facilement réutilisables dans d'autres contextes. Nous avons construit des outils automatiques pour nous assister dans la recherche d'attaques par test d'hypothèses partielles et d'attaques par le milieu. Ces outils ont découverts des attaques surprenantes, qui sont plus efficaces que celles qui avaient été trouvées manuellement par d'autres chercheurs. Nous obtenons ainsi la meilleure attaque connue contre la fonction d'authentification Pelican-MAC et contre le système de chiffrement par flot LEX. La dernière partie de cette thèse est consacrée à la cryptanalyse de schémas multivariés, c'est-à-dire reposant explicitement sur la difficulté de résoudre des systèmes polynomiaux en plusieurs variables. Certains de ces schémas reposent aussi sur une autre hypothèse algorithmiques, la difficulté problème de l'Equivalence Linéaire de Polynômes (PLE). En combinant des outils de l'algèbre linéaire et de la géométrie algébrique avec des techniques statistiques et combinatoires, nous construisons de nouveaux algorithmes plus efficace pour PLE. Ceci montre qu'un schéma dont la sécurité reposerait sur PLE ne peut pas exhiber un niveau de sécurité optimal. Ces algorithmes permettent également de casser en pratique la variante ``sous-corps'' de HFE.
Abstract: Cryptanalysis, formerly known as the art of deciphering secret codes, is now understood in a broader sense: it consists in finding flaws of all kinds, either harmless or severe, in cryptographic constructions. This thesis is made of three parts, devoted to the study of different families of cryptographic primitives. Hash functions are usually iterated constructions, where a building block is used in a repeated way, as specified by a mode of operation. In 2004, 2005 and 2006, the discovery of several generic attacks, targeting the ubiquitous Merkle-Damgard mode of operation, prompted researchers to design alternative modes of operations. Generic attacks exploit the fact that the internal state of the hash functions has the same size as the digests. This allows the attackers to find internal collisions and exploit them. Our results tend to show that this problem is difficult to avoid in general: in the first part of this thesis, we describe several generic second preimage attacks against proposals to repair or patch the Merkle-Damgard construction in order to precisely avoid generic attacks. In the second part, we focus on the cryptanalysis of the AES, the most popular block cipher. We consider a somewhat restrictive attack model where the attacker only has access to very few plaintext/ciphertext pairs. We are thus condemned to attack only highly reduced version of the full cipher, but the attacks we find in this model can sometimes be reused in other contexts. We have built software tools to assist us in finding guess-and-determine as well as meet-in-the-middle attacks. These tools found surprising attacks that are more efficient than those found manually by other cryptanalysts. For instance, we find the best known attacks against the Message Authentication Code Pelican-MAC, and against the stream cipher LEX. The last part of this thesis is devoted to the cryptanalysis of multivariate schemes. This label covers all the schemes whose security explicitly relies on the hardness of solving systems of polynomial equations in several unknowns. Some multivariate scheme also rely on another hardness assumption, namely the hardness of the Polynomial Linear Equivalence (PLE) problem. We build new algorithms to solve PLE problems by combining tools from linear algebra and algebraic geometry with combinatorial and statistical techniques. Our algorithms show that a multivariate scheme relying on the hardness of PLE cannot exhibit an optimal security level. These algorithms also allow to break in practice the ``subfield'' variant of HFE.
TOP
Jeudi 29 septembre 2011: Orr Dunkelman
University of Haifa, Israel10h30 dans l'Amphi Evariste Galois - NIR
A Somewhat Historic View of Lightweight Cryptography
- Abstract
- Lightweight cryptographic primitives, such as block ciphers, stream ciphers, and hash functions that fit constrained environments are continuously being devised. As more and more lightweight primitives are suggested, more and more of them are found to fail in providing their security goals, as cryptanalytic results such as meet in the middle attacks are developed.
In the talk, we shall discuss recent advances in the development of these primitives, as well as the recent advances in breaking them, and the implications of these advances on the field of design and cryptanalysis of lightweight encryption schemes.
TOP
Jeudi 13 octobre 2011: Takashi Nishide
Kyushu University, Japan10h00 dans l'Amphi Evariste Galois - NIR
Recent Development of Attribute-based Encryption
- Abstract
- Attribute-based encryption (ABE) was first proposed by Sahai and Waters at Eurocrypt 2005 and a lot of subsequent constructions were proposed with more advanced functionalities. ABE is a kind of generalization of identity-based encryption (IBE) and can realize one-to-many encryption such that one ciphertext can be decrypted by multiple decryptors if the condition associated with a ciphertext coincides with that of a secret key. Therefore, it is a promising tool for realizing fine-grained access control mechanism in a large system. In this talk, we will see some of ABE concepts and their mathematical constructions.
Jeudi 13 octobre 2011: Vincent Cheval
ENS Cachan11h00 dans l'Amphi Evariste Galois - NIR
A decision procedure for trace equivalence
- Abstract
- We consider security properties of cryptographic protocols that can be modeled using the notion of trace equivalence. The notion of equivalence is crucial when specifying privacy-type properties, like anonymity, vote-privacy, and unlinkability. In this paper, we give a calculus that is close to the applied pi calculus and that allows one to capture most existing protocols that rely on classical cryptographic primitives. First, we propose a symbolic semantics for our calculus relying on constraint systems to represent infinite sets of possible traces, and we reduce the decidability of trace equivalence to deciding a notion of symbolic equivalence between sets of constraint systems. Second, we develop an algorithm allow- ing us to decide whether two sets of constraint systems are in symbolic equivalence or not.
TOP
Jeudi 24 novembre 2011: Soutenance d'habilitation à diriger des recherches de Michel Abdalla
ENS10 heures dans l'Amphi Évariste Galois - NIR
Limiter le besoin de tiers de confiance en cryptographie
Jury :- Jean-Sébastien Coron - Université du Luxembourg (rapporteur)
- Ronald Cramer - CWI
- Marc Fischlin - Université de Darmstadt
- Antoine Joux - DGA-UVSQ (rapporteur)
- Kenny Paterson - Royal Holloway, University of London (rapporteur)
- David Pointcheval (directeur)
- Nigel Smart - Université de Bristol
- Jacques Stern - ENS
Résumé : Les tiers de confiance sont essentiels aux communications sécurisées. Par exemple, dans une infrastructure de gestion de clés, l’autorité de certification est la clé de voute de l’authentification en garantissant le lien entre une identité et une clé publique. Une carte à puce se doit, pour sa part, d’assurer la confidentialité et l’intégrité des données secrètes lorsqu’elle sert de stockage de données cryptographiques. En effet, si ces garanties sont mises en défaut dans l’une de ces situations, alors la sécurité globale du système peut en être affectée. Plusieurs approches permettent de réduire l’importance des tiers de confiance, telles qu’accroître la difficulté de recouvrer la clé secrète, en la distribuant parmi plusieurs entités, ou limiter l’impact d’une fuite d’information secrète, comme dans les cryptosystèmes « intrusion-resilient » ou « forward-secure ». Dans cette thèse, nous considérons deux méthodes complémentaires. La première méthode consiste à utiliser des mots de passe, ou des clés secrètes de faible entropie, qui n'ont pas besoin d'être stockés dans un dispositif cryptographique sécurisé. Malgré la faible entropie du secret, de tels protocoles peuvent fournir un niveau d'assurance satisfaisant pour la plupart des applications. On considère en particulier la mise en accord de clés. La deuxième méthode limite le besoin de garantie de la part des tiers de confiance en utilisant un cryptosystème basé sur l'identité, dans lequel la clé publique d'un utilisateur peut être une chaîne de caractères arbitraire, telle qu’une adresse email. Comme ces systèmes fournissent une résistance aux collusions, ils peuvent aussi être utilisés pour réduire les dommages causés par l'exposition de clés secrètes en générant des secrets indépendants pour chaque période de temps ou pour chaque périphérique/entité. Par ailleurs, ces systèmes basés sur l'identité permettent aux utilisateurs d'avoir un contrôle plus fin sur les capacités de déchiffrement des tiers, en limitant les conséquences liées à un mauvais usage.
Abstract: Trusted parties are fundamental for the establishment of secure communication among users. Such is the case, for example, when establishing a trusted relationship between users and certain public information in a public-key infrastructure for public-key encryption and signature schemes or when storing high-entropy secret keys in a cryptographic device. Clearly, if the trusted party misbehaves in either of these situations, then the overall security of the scheme or protocol in which we are interested can be adversely affected. There are several ways in which one can try to reduce the amount of trust in third parties, such as making the task of recovering the secret key harder for the adversary, as in distributed cryptosystems or minimizing the damage caused by secret-key exposures, as in forward-secure and intrusion-resilient cryptosystems. In this thesis, we consider two additional methods. The first one, which goes by the name of password-based key exchange, is to assume that the secret keys used in authenticated key exchange protocols have low entropy and do not need to be stored in a cryptographic device. In spite of the low entropy of secret keys, such protocols can still provide a level of assurance which may be sufficient for most applications. The second method for reducing the amount of trust in third parties is to use an identity-based cryptosystem, in which the public key of a user can be an arbitrary string such as an email address. As identity-based cryptosystems provide collusion resistance, they can also be used to lessen the damage caused by secret-key exposures by generating independent secret keys for different time periods or devices. Moreover, identity-based cryptosystems can allow users to have a more fine-grained control over the decryption capabilities of third parties, further limiting the harmful consequences due to their misbehavior.
TOP
Jeudi 24 novembre 2011: Kenny Paterson
Royal Holloway, University of London14h00 dans l'Amphi Evariste Galois - NIR
Tag Size Does Matter: Attacks and Proofs for the TLS Record Protocol
- Abstract
- We analyze the security of the TLS Record Protocol, a MAC-then-Encode-then-Encrypt (MEE) scheme whose design targets confidentiality and integrity for application layer communications on the Internet.
Our main results are twofold. First, we describe a new distinguishing attack against TLS when variable length padding and short (truncated) MACs are used. This combination will arise when standardized TLS 1.2 extensions (RFC 6066) are implemented. Second, we show that when tags are longer, the TLS Record Protocol meets a new length-hiding authenticated encryption security notion that is stronger than IND-CCA security.
Jeudi 24 novembre 2011: Ronald Cramer
CWI15h00 dans l'Amphi Evariste Galois - NIR
The Arithmetic Codex
- Abstract
- We define the notion of an arithmetic codex (or codex, for short), and as a special case, arithmetic secret sharing. This notion encompasses as well as generalizes, in a single mathematical framework, all known types of specialized secret sharing schemes from the area of secure multi-party computation, i.e., the so-called (strongly) multiplicative linear secret sharing schemes. These schemes were first studied as an abstract primitive by Cramer, Damgård, and Maurer in the late 1990s. They showed that the “Fundamental Theorem of Information-Theoretically Secure Multi-Party Computation,” the landmark 1988 result by Ben-Or, Goldwasser, and Wigderson and, independently at the same time by Chaum, Crépeau, Damgård, admits a proof that uses this primitive as a blackbox: it is possible to bootstrap, in a blackbox fashion, from this primitive a set of atomic sub-protocols upon which general secure computation can be based. They also showed when and how multiplicative schemes (but not strongly multiplicative ones) reduce to ordinary ones and gave applications to security against non-threshold adversaries.
In 2006, Chen and Cramer showed an “asymptotically good” version of the Fundamental Theorem, where the size of the network is unbounded and where an adversary corrupts a constant fraction of the network, yet the information rate of the secret sharing primitive is constant. Their result relies on a careful choice of algebraic geometric codes, in combination with the earlier work of Cramer, Damgård, and Maurer.
In 2007 this asymptotic result turned out to have a surprising application in two-party cryptography, through the work of Ishai, Kushilevitz, Ostrovsky and Sahai (“Multi-Party Computation in the Head”). This first application was to zero knowledge for circuit satisfiability, but soon after other applications to secure two-party computation and information theory (correlation extractors) followed.
Our notion of arithmetic secret sharing is not merely a unification for its own sake. First, it casts these schemes in terms of a dedicated “representation” of K-algebras, thereby bringing the relevant mathematical structure to the surface. Second, it identifies novel types of special secret sharing schemes. And, third, there are novel cryptographic applications.
Besides presenting some elementary examples and giving an overview of the basic theory and the main applications, we discuss a construction of arithmetic secret sharing schemes based on a novel algebraic-geometric paradigm that we also introduce.
Programme du second trimestre 2011/2012
TOP
Jeudi 19 janvier 2012: Benoît Libert
UCL10h00 dans l'Amphi Evariste Galois - NIR
Non-Interactive CCA-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions
- Abstract
- In threshold cryptography, private keys are divided into n shares, each one of which is given to a different server in order to avoid single points of failure. In the case of threshold public-key encryption, at least t out of n servers need to contribute to the decryption process. A threshold primitive is said robust if no coalition of t malicious servers can prevent remaining honest servers from successfully completing private key operations. So far, most practical non-interactive threshold cryptosystems, where no interactive conversation is required among decryption servers, were only proved secure against static corruptions. In the adaptive corruption scenario (where the adversary can corrupt servers at any time, based on its complete view), almost all existing robust threshold encryption schemes that also resist chosen-ciphertext attacks require some interaction in the decryption phase. In this work, we describe several constructions of adaptively secure, robust and fully non-interactive threshold cryptosystems with chosen-ciphertext security. These schemes stem from a new framework based on hash proof systems with publicly verifiable proofs. All instantiations rely on well-studied assumptions in bilinear groups.
Jeudi 19 janvier 2012: Oumar Diao
Univ. Rennes 111h00 dans l'Amphi Evariste Galois - NIR
Arithmétique efficace sur les modèles de Kummer de petite dimension
- Abstract
- Le modèle de Kummer d'une variété abélienne A est par définition le quotient de A par le morphisme -1. Dans cet exposé, on s'intéresse aux modèles de Kummer issue de Jacobiennes de courbes hyperelliptiques de genre ≤ 2. Sur le corps C des nombres complexes, on obtient une arithmétique efficace grâce à la théorie générale des fonctions thêta.
Grâce à la théorie des nombres p-adiques, les résultats valables en C restent valables en caractéristique impaire. En caractéristique deux, un changement de coordonnées de thêta adéquat permet d'obtenir des formules efficaces sur les modèles ordinaires à partir des formules obtenues en C.
Cependant, le changement de coordonnées précédent n'est pas valable pour les modèles non-ordinaires. Pour étudier ces modèles là, nous utiliserons des techniques de "déformations" qui consistent à considérer une famille de jacobiennes sur un anneau des séries formelles, telle que la fibre générique soit ordinaire et la fibre spéciale soit la jacobienne (non-ordinaire) considérée. Il s'agit alors de montrer que les formules sur la fibre générique s'étendent à tout le modèle et permettent d'avoir des formules efficaces sur les jacobiennes non-ordinaires.
TOP
Jeudi 26 janvier 2012: Igor Shparlinski
Macquarie Univ., Australia10h30 dans l'Amphi Evariste Galois - NIR
On the Distribution of Atkin and Elkies Primes
- Abstract
- Given an elliptic curve E over a finite field Fq of q elements, we say that an odd prime l not dividing q is an Elkies prime for E if tE2 - 4q is a square modulo l, where tE = q+1 - #E(Fq) and #E(Fq) is the number of Fq-rational points on E; otherwise l is called an Atkin prime.
We show that there are asymptotically the same number of Atkin and Elkies primes l < L on average over all curves E over Fq, provided that L >= (log q)ε for any fixed ε>0 and a sufficiently large q. We use this result to design and analyse a fast algorithm to generate random elliptic curves with #E(Fp) prime, where p varies uniformly over primes in a given interval [x,2x].
TOP
Lundi 27 février 2012: Christian Schaffner
University of Amsterdam & CWI10h30 en salle W
Random Oracles in a Quantum World
- Abstract
- The interest in post-quantum cryptography - classical systems that remain secure in the presence of a quantum adversary - has generated elegant proposals for new cryptosystems. Some of these systems are set in the random oracle model and are proven secure relative to adversaries that have classical access to the random oracle. We argue that to prove post-quantum security one needs to prove security in the quantum-accessible random oracle model where the adversary can query the random oracle with quantum states. We begin by separating the classical and quantum-accessible random oracle models by presenting a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when the adversary can make quantum oracle queries. We then set out to develop generic conditions under which a classical random oracle proof implies security in the quantum-accessible random oracle model. We introduce the concept of a history-free reduction which is a category of classical random oracle reductions that basically determine oracle answers independently of the history of previous queries, and we prove that such reductions imply security in the quantum model. We then show that certain post-quantum proposals, including ones based on lattices, can be proven secure using history-free reductions and are therefore post-quantum secure. We conclude with a rich set of open problems in this area.
TOP
Jeudi 22 Mars 2012: Dario Fiore
NYU10h30 dans l'Amphi Evariste Galois - NIR
Vector Commitments and their Applications
- Abstract
- We introduce a new primitive that we call Vector Commitment (VC, for short). Informally, VCs allow to commit to an ordered sequence of q values (m1, ..., mq) (i.e., a vector) in such a way that one can later open the commitment at specific positions (e.g., prove that mi is the i-th committed message). For security, Vector Commitments are required to satisfy a notion that we call position binding which states that an adversary should not be able to open a commitment to two different values at the same position. Moreover, what makes our primitive interesting is that we require VCs to be concise, i.e. the size of the commitment string and of its openings has to be independent of the vector length.
We show two realizations of VCs based on standard and well established assumptions, such as RSA, and Computational Diffie-Hellman (in bilinear groups).
Next, we turn our attention to applications and we show that Vector Commitments turn out to be useful in a variety of contexts, as they allow for compact and efficient solutions which significantly improve previous works either in terms of efficiency of the resulting solutions, or in terms of "quality" of the underlying assumption, or both. These applications include: Verifiable Databases with Efficient Updates, Updatable Zero-Knowledge Databases, and Universal Dynamic Accumulators.
Programme du troisième trimestre 2011/2012
TOPVendredi 4 mai 2012: Soutenance d'habilitation à diriger des recherches de Karthikeyan BhargavanINRIA11 heures en salle WTowards the Automated Verification of Cryptographic Protocol ImplementationsAbstract: In recent years, the emergence of effective protocol analyzers and expressive cryptographic models have enabled the proof of large cryptographic protocols, such as Transport Layer Security (TLS) and Kerberos, in abstract but increasingly precise models. A criticism of such proofs is that they provide a false sense of security, since their models do not cover low-level implementation details and may miss entire classes of attacks that rely, for example, on message formats or error handling. Indeed, attacks on mainstream protocol implementations, such as the OpenSSL implementation of TLS, continue to be found despite years of expert review and formal proofs. We present a line of research that aims to address this gap between formal models and implementations of cryptographic protocols. Our goal is to prove the security of running code, accounting for their concrete details, under precise cryptographic assumptions, and against realistic attackers. The challenge is that protocol implementations are large programs that do far more than simply use cryptographic constructions: they implement complex state machines, they process flexible message formats, and they provide an abstract API to application code. We identify and formalize a subset of the programming language F# that is well-suited for programming and specifying protocols. Programs (and adversaries) written in this subset can be interpreted both concretely (for execution) and symbolically (for verification). We describe two verification techniques, one relying on model extraction and a specialized cryptographic protocol analyzer, and another on a type system and an general-purpose first-order logic prover. We evaluate these techniques by verifying a series of protocol implementations, including TLS and Web Services Security. We thus present the first security verification results for interoperable implementations of mainstream cryptographic protocols. |
TOP
Jeudi 10 Mai 2012: Nuttapong Attrapadung
Research Center for Information Security, AIST, Japan et ENS10h30 dans l'Amphi Evariste Galois - NIR
Verifiable Predicate Encryption and Its Applications
- Abstract
- In this work, we focus on verifiability of predicate encryption. A verifiable predicate encryption scheme guarantees that all legitimate receivers of a ciphertext will obtain the same message upon decryption. While verifiability of predicate encryption might be a desirable property by itself, we furthermore show that this property enables interesting applications.
Specifically, we provide two applications of verifiable predicate encryption. Firstly, we show that for a large class of verifiable predicate encryption schemes, it is always possible to convert a chosen-plaintext secure scheme into a chosen-ciphertext secure one. Secondly, we show that a verifiable predicate encryption scheme allows the construction of a deniable predicate authentication scheme. This primitive enables a user to authenticate a message to a verifier using a private key satisfying a specified relation while at the same time allowing the user to deny ever having interacted with the verifier. This scheme furthermore guarantees the anonymity of the user in the sense that the verifier will learn nothing about the user's private key except that it satisfies the specified relation.
Lastly, we show that many currently known predicate encryption schemes already provide verifiability, and furthermore demonstrate that many predicate encryption schemes which do not provide verifiability, can be easily converted into schemes providing verifiability.
Our results not only highlight that verifiability is a very useful property of predicate encryption, but also show that efficient and practical schemes with this property can be obtained relatively easily.
Webmaster: webdi![[@]](pub/ressources/commercial_at.png)
di![[.]](pub/ressources/full_stop.png)
ensfr.
diensfr.