Providing Single Sign-On (SSO) between SPs and enabling SPs to share user personal attributes are critical for both users to benefit from a seamless access to their services, and SPs to realize new business opportunities. Today, however, the users have several independent, partial identities spread over different SPs. Providing SSO and attribute sharing requires that links (federations) are established between (partial) identities. In Liberty and SAML, the links between identities are stored and managed at the network side by the IdPs (network-side identity federation). This model prevents the SPs from mass-correlating the partial identities they have, but the users must fully trust the IdPs. In this paper, we propose a complementary approach where the users have a full control of the links between the partial identities. This client-side identity federation approach relies on the introduction of a new cryptographic tool, called invariable partially blind signature scheme, that may be of independent interest.
We describe the first polynomial time chosen-plaintext total break of the NICE family of cryptosystems based on ideal arithmetic in imaginary quadratic orders, introduced in the late 90's by Hartmann, Paulus and Takagi.The singular interest of these encryption schemes is their natural quadratic decryption time procedure that consists essentially in applying Euclide's algorithm. The only current specific cryptanalysis of these schemes is Jaulmes and Joux's chosen-ciphertext attack to recover the secret key. Originally, Hartmann et al. claimed that the security against a total break attack relies only on the difficulty of factoring the public discriminant $\Delta_q=-pq^2$, although the public key was also composed of a specific element of the class group of the order of discriminant $\Delta_q$, which is crucial to reach the quadratic decryption complexity. In this talk, we will propose a drastic cryptanalysis which factor $\Delta_q$, only given this element. This polynomial time attack suggests that there is no hope to get a quadratic decryption from imaginary quadratic field-based cryptography.
This is a joint work with Fabien Laguillaumie.
In 1998, Blaze, Bleumer and Strauss put forth a cryptographic primitive, termed proxy re-encryption, where a semi-trusted proxy is given some piece of information that enables the re-encryption of ciphertexts from one key to another. Unidirectional schemes only allow translating from the delegator to the delegatee and not in the opposite direction. In all constructions described so far, although colluding proxies and delegatees cannot expose the delegator's long term secret, they can derive and disclose sub-keys that suffice to open all translatable ciphertexts sent to the delegator. They can also generate new re-encryption keys for receivers that are not trusted by the delegator.
In this paper, we propose traceable proxy re-encryption systems, where proxies that leak their re-encryption key can be identified by the delegator. The primitive does not preclude illegal transfers of delegation but rather strives to deter them. We give security definitions for this new primitive and a construction meeting the formalized requirements. This construction is fairly efficient, with ciphertexts that have logarithmic size in the number of delegations, but uses a non-black-box tracing algorithm. We discuss how to provide the scheme with a black box tracing mechanism at the expense of longer ciphertexts.
(joint work with Benoît Libert)
Lattice reduction algorithms such as LLL and its floating-point variants have a very wide range of applications in computational mathematics and in computer science: polynomial factorization, cryptology, integer linear programming, etc. It can occur that the lattice to be reduced has a dimension which is small with respect to the dimension of the space in which it lies. This happens within LLL itself. We describe a randomized algorithm specifically designed for such rectangular matrices. It computes bases satisfying, with very high probability, properties similar to those returned by LLL. It significantly decreases the complexity dependence in the dimension of the embedding space. Our technique mainly consists in randomly projecting the lattice on a lower dimensional space, by using two different distributions of random matrices.
Ce n'est pas parce qu'un schéma cryptographique est prouvé sûr sur le papier qu'il garantit une sécurité satisfaisante en pratique. L'attaque par relais est l'exemple même de faiblesse qui n'est saisie par aucun modèle cryptographique. Cette attaque de type man-in-the-middle passif consiste à relayer le signal de très bas niveau lors d'une procédure d'authentification, à l'insu du prouveur. Cette attaque prend toute son ampleur dans le monde de la RFID où la présence du prouveur à proximité du vérifieur est un accord implicite à participer au protocole. Nous verrons dans cet exposé les différentes formes d'attaques par relais, la faisabilité de leur mise en oeuvre et les contre-mesures cryptographiques qui peuvent être envisagées.
The nonlinearity profile of a Boolean function (i.e. the sequence of its minimum Hamming distances $nl_r(f)$ to all functions of algebraic degrees at most $r$, for $r\geq 1$) is a cryptographic criterion whose role against attacks on stream and block ciphers has been illustrated by many papers. It plays also a role in coding theory, since it is related to the covering radii of Reed-Muller codes. We recall what is known on this parameter, we introduce a method for lower bounding its values and we deduce bounds on the higher order nonlinearities of the multiplicative inverse functions (used in the S-boxes of the AES).
En prévision de leur déploiement massif, la conception de systèmes RFID prenant en compte l'intégrité des données et le respect de la vie privée des personnes est un challenge important pour les années à venir. De nombreux travaux ont déjà vu le jour dans ce domaine avec l'apparition de nombreux schémas, la cryptanalyse de certains d'entre eux et une volonté forte de modéliser les propriétés de sécurité.
Pour obtenir le niveau de sécurité souhaité tout en respectant les contraintes "physiques" des étiquettes RFID (restrictions en termes de capacités de calcul et de mémoire), plusieurs systèmes utilise une infrastructure à clé secrète. Une manière d'assurer l'intraçabilité de l'utilisateur est alors de partager une clé secrète entre l'étiquette RFID et la base de données et de régulièrement mettre à jour cette clé. Cependant, dans certaines constructions, il est possible de frauder le système en désynchronisant les données contenues dans la base de données centrale de celles embarquées dans les étiquettes.
Dans cet exposé je présenterai, dans un premier temps, les propriétés de sécurité requises pour ce type de protocoles et donnerai une méthodologie permettant de quantifier précisément l'impact de ces désynchronisations. En deuxième partie, j'appliquerai cette nouvelle modélisation à divers systèmes existants. Enfin je présenterai un nouveau protocole répondant au mieux aux contraintes sus-mentionnées et je donnerai les grandes lignes des preuves de sécurité.
La monnaie électronique (ou e-cash) est une solution de paiement électronique qui peut être comparée à la monnaie classique. Les schémas d'e-cash proposés dans la littérature tentent généralement de reproduire électroniquement les principales propriétés de la monnaie classique. En particulier, on peut considérer qu'un système d'e-cash devrait protéger la vie privée des utilisateurs lors d'un achat. La principale différence entre l'e-cash et les autres solutions de paiement électronique est que les pièces électroniques sont stockées sur un support (e.g. une carte à puce ou un disque dur personnelle) qui est contrôlé par l'utilisateur. Depuis l'introduction par Chaum de la monnaie électronique inconditionnellement anonyme, les systèmes d'e-cash ont été largement étudiés. Dans cet exposé, nous présenterons des travaux récents qui concernent principalement l'efficacité des protocoles, et nous discuterons la possibilité de transférer une pièce qui est considérée comme étant une caractéristique importante de la monnaie classique.
Dans cet exposé nous analysons la sécurité d'une proposition récente de fonction de hachage fondée sur des calculs de produits de matrices $2 times 2$ à coefficients dans un corps fini. Nous montrons comment trouver des collisions pour cette fonction de hachage en temps polynomial et proposons une réparation possible.