Des chercheurs montrent comment attaquer un système de cryptographie quantique réputé inviolable.
Ce groupe de recherche, dont j’ai déjà parlé là, présente un nouvel article publié dans la revue Nature : Hacking commercial quantum cryptography systems by tailored bright illumination.

La plupart des systèmes de distribution de clés quantiques (QKD) utilisent des photodiodes à avalanche et sont par conséquent sensibles à ce type d’attaque.
Les sociétés Id Quantique et MagiQ Technologies, qui commercialisent ces solutions, auraient déjà prévu une parade.

L’article de 4 pages est disponible en pdf à cette adresse.

A lire également : La fiabilité de la cryptographie quantique remise en cause.

La cryptographie quantique utilise la physique quantique pour assurer la sécurité de la transmission d’information entre deux personnes. Un des problèmes principaux dans la cryptographie est d’une part de chiffrer l’information à transmettre et d’autre part de partager avec le destinataire la méthode et la clé pour le déchiffrement du message.

Le point faible est très souvent la clé, qui lorsqu’elle est réutilisée plusieurs fois, peut permettre à un espion de découvrir la méthode de chiffrement utilisée. Si la clé est changée lors de chaque échange de message, alors il y a vraiment peu de chance qu’un espion puisse découvrir le message (pour peu que la méthode chiffrement soit quand même suffisament robuste). Le problème se pose alors de transmettre cette clé au destinataire.

Comment transmettre cette clé ? On peut la chiffrer par une autre technique, mais on ne fait que déplacer le problème. Cette autre technique utilisant très probablement une autre clé qu’il faudra bien transmettre.

Ici, la physique quantique offre une solution élégante pour partager une clé entre deux personnes grâce à l’impossibilité pour un espion de dupliquer les informations transmises sans se faire repérer (voir l’impossibilité du clonage quantique). Je vous invite à lire cet article d’Artur Ekert qui explique très simplement comment la clé peut être créée et pourquoi le partage de la clé entre les deux personnes souhaitant communiquer est sécurisé.

Maintenant, tout ça pour dire que finalement, le protocole quantique de transmission de la clé n’est peut-être pas aussi inviolable que l’on pensait.

Un groupe de recherche a présenté une faille dans ce protocole tout à fait utilisable pour récupérer intégralement la clé sans que ni l’expéditeur, ni le destinataire ne soient au courant :

How you can build an eavesdropper for a quantum cryptosystem (présentation)

Les auteurs utilisent les caractéristiques des détecteurs de photons. Ceux-ci peuvent être rendus aveugles (i.e. ne plus détecter aucun photon) s’ils sont noyés sous un flux important de photons. Il devient totalement insensible aux photons envoyés un par un. Le détecteur peut être déclenché à nouveau si un flux plus brillant encore lui est envoyé.

Un espion peut donc utiliser ce système pour déclencher le détecteur sur commande. Ainsi, il peut intercepter les photons envoyés par l’expéditeur et mesurer la clé en utilisant la même configuration de détecteur que le destinataire. Pour chaque bit reçu, l’espion peut déclencher un événement sur le détecteur du destinataire qui ne se rendra pas compte que la clé a été interceptée.

La solution pour contrer l’espion serait de mesurer l’intensité du flux de photons, mais je ne sais pas dans quelle mesure cela pourrait être fait pendant l’émission de la clé sans perturber la transmission.

Un article d’une page résumant le principe : S. Sauge, V. Makarov, and A. Anisimov, “Quantum hacking: how Eve can exploit component imperfections to control yet another of Bob’s single-photon qubit detectors,” presented at CLEO/Europe-EQEC 2009, Munich, Germany, June 14–19, 2009.

L’article plus complet sur arXiv : Controlling passively-quenched single photon detectors by bright light

[0705.4303] Database Manipulation on Quantum Computers

Dans cet article, l’auteur tente de définir les opérations principales de manipulation de données dans les bases de données classique, à savoir les quatre opérations fondamentales du langage SQL :

• Select : trouver un élément
• Insert : ajouter un élément
• Update : modifier un élément
• Delete : supprimer un élément

L’auteur définit les opérations élémentaires d’un nouveau language de requêtes appelé QQL (Quantum Query Language) censé reproduire le SQL pour une base de données quantique.

Pour avoir un intérêt, la base de données doit se trouver dans un état de superposition quantique. Elle consiste en un registre de qubits, étant le nombre de qubits de stockage (permettant de stocker enregistrements) et étant le nombre de qubits temporaires nécessaires pour les diverses opérations.

L’auteur propose des opérateurs quantiques pour les opérations INSERT, UPDATE qui permettent d’insérer ou de mettre à jour plusieurs enregistrements en même temps. Pour l’opération de DELETE, la question reste encore grandement ouverte et quelques pistes sont proposées. L’opération de SELECT est résolue par l’Oracle quantique (voir l’algorithme de Grover ou sur wikipedia).

Un article plus récent propose également un langage appelé QQL, mais l’accès n’étant pas gratuit, je n’ai pas encore pu le lire (la problématique abordée semble néanmoins différente)…

En informatique, les nombres aléatoires sont plutôt difficiles à obtenir. En fait, il est impossible de créer de vrais nombres aléatoires à partir d’algorithmes fonctionnant sur les ordinateurs classiques. Les algorithmes permettant de générer des nombres dits pseudo-aléatoires sont obligés de se répéter au bout d’un certain temps.
Les nombres aléatoires sont très importants pour divers algorithmes d’optimisation (Monte-Carlo, algorithmes évolutionnaires…), de simulation statistique, cryptographie… Et lorsqu’ils ne sont pas vraiment aléatoires, les résultats peuvent être faussés.
Jusqu’à récemment, il fallait se contenter de générateurs de nombres pseudo-aléatoires. Un des meilleurs algorithmes pour la génération de nombres pseudo-aléatoires est le Mersenne Twister. Cet algorithme n’est par contre pas adapté pour les besoins de la cryptographie.

Depuis 1998, le site http://www.random.org/ propose des services de génération de vrais nombres aléatoires en utilisant les fluctuations atmosphériques. Les nombres aléatoires proviennent donc d’un système chaotique et on sait que ces systèmes ne sont pas prédictibles (contrairement à un générateur de nombres pseudo-aléatoires) même s’ils sont déterministes.

D’un autre côté, la physique quantique permet aussi d’obtenir de vrais nombres aléatoires. Bien que les équations quantiques (Schrödinger ou Dirac) soient déterministes, elles portent sur des amplitudes de probabilités. La physique quantique est donc considérée comme intrinsèquement aléatoire. La société id Quantique, spécialisée dans la cryptographie quantique fournit un vrai générateur de nombres aléatoires depuis 2004. C’est un matériel que l’on peut acheter sous forme d’un composant électronique, d’une carte PCI ou d’un appareil USB externe depuis peu.

Et maintenant, à l’ère du Web 2.0, de l’architecture SOA, je viens de découvrir un nouveau service de génération de nombres aléatoires : Quantum Random Bit Generator Service.
Ce service s’appuie sur un générateur de nombres aléatoires quantique, le QRBG121. Plusieurs clients existent pour appeler ce service : en Java, en C++, en Matlab, Octave…

Suppléments :
On pourra trouver ici différentes implémentations du Mersenne Twister en Java, C++, et bien d’autres langages.

Quelques exercices pour jouer un peu avec les nombres aléatoires (et en particulier, voir comme il est difficile pour nous d’en générer) : Can You Behave Randomly? (Laissez-moi un commentaire si vous faites une séquence aléatoire. Moi, je n’ai pas réussi )

C’est impressionnant comment un simple dessin au tableau peut prendre vie…

Pour connaître l’origine de votre distribution préférée :

linuxdistrotimeline-75.png (PNG Image, 1860×1984 pixels) – Scaled (42%)

En général, lorsqu’il y a une relation de plusieurs-à-plusieurs entre deux groupes d’attributs de dimension, il est souhaitable de séparer ces groupes dans deux dimensions distinctes. Cependant, lorsque le nombre de ligne est très petit, il est possible de laisser ces groupes d’attributs dans une superdimension. Une superdimension est un peu une dimension fourre-tout. Cela peut aussi s’avérer utiliser lorsque certains attributs renseignent sur la relation entre ces groupes d’attributs. C’est par exemple le cas pour une superdimension regroupant un lieu d’origine et un lieu de destination. Plutôt que
faire deux vues sur une table lieu, une superdimension combinant l’origine et la destination permet d’ajouter l’information sur la distance…

Concernant la gestion des calendriers par pays, une table Date déportée par pays est une façon de gérer les spécificités d’un pays. Cette table est liée à une dimension conforme Date et à une clé primaire sur le pays.

L’heure peut être traitée comme un simple fait s’il n’y a pas de besoin d’analyser par période plus fine que la journée.

La gestion des fuseaux horaires nécessite de décrire les dates et heures dans un fuseau horaire de référence et dans le fuseau horaire local.

Source : Ralph Kimball et Margy Ross, « Entrepôts de données, guide pratique de modélisation dimensionnelle« , 2ième édition.

Le chapitre 10 propose de réviser un schéma existant. L’exercice est très instructif. Voici les points sur lesquels il faut être attentif :

1. Trouver le niveau de granularité le plus bas, ce qui ne signifie pas la recherche des données les plus détaillées de l’entreprise.
2. Vérifier que tous les faits additifs sont à la granularité définie pour la table de faits. Et éviter les cumuls car non additifs.
3. Granularité des dimensions : chaque dimension associée à une table de faits doit prendre une seule valeur pour chaque ligne de la table de faits. Chaque attribut de la dimension doit prendre une seule valeur par ligne de dimension. Il faut dénormaliser les hiérarchies à l’intérieur de la dimension.
4. Dimension Date. Toujours bien préciser son rôle lorsqu’une table date générique est utilisée.
5. Éviter les colonnes représentant des périodes en dur dans la table de faits. Il vaut mieux avoir 12 lignes et une dimension Mois plutôt que 12 colonnes les représentant.
6. Rechercher les dimensions qui devraient être dégénérées (cas d’une dimension ayant presque autant de ligne que la table de faits).
7. Éviter les codes, utiliser des descriptions.
8. Utiliser des clés artificielles plutôt que les identifiants opérationnels pour toutes les dimensions.
9. Avoir un nombre de dimensions raisonnable, ni trop, ni trop peu.

La géographie peut être standardisée (adresse, point géographique x, y) et partagée en tant que dimension déportée. Il faut cependant vérifier que le partage de cette table ait un intérêt (en diminuant le nombre de lignes par exemple) et que l’utilisation des différentes vues sur cette dimension déportée restent performantes (cela dépendra du SGBD). Les outils de SIG (Système d’Information Géographique) permettent de tirer un meilleur parti de ces données, en particulier en vue d’une représentation sur une carte (des requêtes de type topologiques existent).

Source : Ralph Kimball et Margy Ross, « Entrepôts de données, guide pratique de modélisation dimensionnelle« , 2ième édition.

Ce chapitre se penche sur les services financiers.

Lorsque l’on a peu de dimensions, il faut vérifier que les dimensions suivantes sont présentes.

• L es dimensions causales telles que Promotion, Contrat, Affaires… qui renseignent sur la cause d’un événement.
• Les dimensions de dates multiples ou d’horodatage.
• Les dimensions dégénérées (DD) telles que N° de facture… qui identifient une ligne de la table de faits.
• Les dimensions à jeu de rôles qui apparaissent lorsqu’une dimension est utilisée plusieurs fois.
• Les dimensions d’état telles que l’état d’un compte, qui identifient l’état actuel d’une transaction ou d’un instantané mensuel.
• Les dimensions audit pour suivre l’origine et la qualité des données
• Les dimensions fourre-tout qui regroupent indicateurs et drapeaux corrélés.

Ces dimensions peuvent être ajoutées au modèle sans rien perturber. Elles ne modifient pas les clés des dimensions existantes ni les faits mesurés, ni le grain de la table de faits.

En fait, « tout attribut descriptif ayant une seule valeur pour différentes mesures de la table de faits est susceptible d’être ajouté à une dimension existante ou de devenir lui-même une dimension. »

Les banques étudient les relations entre les comptes et les foyers. Pour cela elles peuvent utiliser des algorithmes complexes de rapprochement. Pour autant, les comptes et les foyers sont séparés en deux dimensions distinctes (car ils sont variables mais leur variation n’est pas trop corrélée). La relation entre comptes et foyers passe donc par la table de faits, ce qui évite de gérer l’évolution de ces dimensions avec l’approche de type 2.

Pour traiter les dimensions à valeurs multiples, il faut utiliser une table passerelle pour relier les diverses valeurs d’attribut à la dimension. Par exemple, un compte bancaire peut avoir un ou plusieurs titulaires. La dimension client est liée à la dimension compte par l’intermédiaire d’une table passerelle. Le compte lui est lié à la table de faits. La dimension client évoluant rapidement, il est nécessaire de créer des mini-dimensions qui regroupent des attributs corrélés (notation mensuelle de crédit, données démographiques…). Pour éviter un trop grand nombre de lignes dans les mini-dimensions, il est conseillé d’utiliser des plages de valeurs d’attributs. Dans certains cas, on peut conserver la valeur exacte de l’attribut dans la table de faits.

Pour créer des plages de valeurs d’attributs, on peut employer une table définissant ces plages avec : une clé pour le groupe de plages, une clé pour l’ordre de tri du groupe, le nom du groupe, le nom de la plage de valeurs, la valeur inférieure et la valeur supérieure. La jointure avec la table de faits est double (ex. : FAITS.solde >= PLAGE.valeur_inférieure AND FAITS.solde < PLAGE.valeur_supérieure).

Lorsque l’on veut analyser des produits différents ; il est nécessaire d’avoir une table de faits centrale permettant l’analyse indépendamment des produits (à partir de leurs caractéristiques communes) et des tables de faits sur mesure pour analyser les faits selon les attributs spécifiques à des produits particuliers. On peut utiliser une table déportée de la dimension produit pour stocker les attributs spécifiques et laisser les attributs communs à tous les produits dans la dimension produit.

Source : Ralph Kimball et Margy Ross, « Entrepôts de données, guide pratique de modélisation dimensionnelle« , 2ième édition.

La compagnie canadienne D-Wave a fait beaucoup de bruit en février dernier en présentant une démonstration de son ordinateur quantique appelé Orion. La présentation est disponible en pdf ici. Le processeur est composé de 16 qubits et la compagnie prévoit de passer à 1024 qubits fin 2008.

Geordie Rose, un des fondateurs de D-Wave, explique dans les colonnes de Physics World que Orion n’est pas en fait un ordinateur complètement quantique. Il est construit selon la théorie des ordinateurs quantiques adiabatiques (adiabatic quantum computers). Une des limitations de cette technologie est l’impossibilité de simuler des systèmes quantiques.

Il indique également qu’un ordinateur quantique ne saura probablement pas résoudre des problèmes NP-difficiles exponentiellement plus vite qu’un ordinateur classique.  Selon lui, le gain en vitesse pourra n’être que quadratique, ce qui serait déjà une grande avancée pour certains problèmes.

Contrairement à ce que prédisait une grande partie des chercheurs, il se pourrait bien qu’on n’attende pas 2050 pour assister à une petite révolution dans le monde des ordinateurs… D’autant plus que les algorithmes quantiques actuellement connus concernent des domaines très importants comme la cryptographie et la recherche d’information dans des bases de données.