Séance de cours

ALL Algorithme

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

MATH-489: Number theory II.d - Cryptography

. ...

Description

Cette séance de cours couvre l'algorithme LLL, qui est utilisé pour la réduction du réseau. Il explique le concept de points symétriques centraux, la condition de Lovasz, l'intuition derrière le changement de base, et l'orthogonalité. L'instructeur discute de la constante d'Hermite, du théorème de Minkowski et du discriminant dans le contexte des treillis de plein rang.

Enseignant·e

Dimitar Petkov Jetchev

Source officielle

Concepts associés (31)

Ideal lattice

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient.

Problème de réseau

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes.

Réseau (géométrie)

En mathématiques, un réseau d'un espace (vectoriel) euclidien est un sous-groupe discret de l’espace, de rang fini n. Par exemple, les vecteurs de Rn à coordonnées entières dans une base forment un réseau de Rn. Cette notion permet de décrire mathématiquement des maillages, comme celui correspondant à la figure 1. thumb|Fig. 1. Un réseau est un ensemble discret disposé dans un espace vectoriel réel de dimension finie de manière régulière, au sens où la différence de deux éléments du réseau est encore élément du réseau.

Suite de polynômes orthogonaux

En mathématiques, une suite de polynômes orthogonaux est une suite infinie de polynômes p0(x), p1(x), p2(x) ... à coefficients réels, dans laquelle chaque pn(x) est de degré n, et telle que les polynômes de la suite sont orthogonaux deux à deux pour un produit scalaire de fonctions donné. Cette notion est utilisée par exemple en cryptologie ou en analyse numérique. Elle permet de résoudre de nombreux problèmes de physique, comme en mécanique des fluides ou en traitement du signal.

Lattice-based cryptography

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers.

Afficher plus

Séances de cours associées (59)

Problème de vecteur le plus proche: cellules de Voronoi

Explore le problème vectoriel le plus proche et les cellules Voronoi dans les algorithmes de réduction de réseau.

ALL Algorithme

Couvre l'algorithme LLL pour réduire les bases de réseau à des formes plus courtes et plus orthogonales par des transformations itératives.

Résoudre les jeux de parité dans la pratique

Explore les aspects pratiques de la résolution des jeux de parité, y compris les stratégies gagnantes, les algorithmes, la complexité, le déterminisme et les approches heuristiques.

Diffusion totale des commandes : notions de base et équivalences consensuelles

Explore la diffusion de la commande totale et son équivalence avec le consensus dans des systèmes fiables.

Connect 4 : Stratégie gagnante

Explique la stratégie gagnante dans Connect Four en vérifiant les combinaisons gagnantes.

Afficher plus

Concepts associés (31)

Ideal lattice

Problème de réseau

Réseau (géométrie)

Suite de polynômes orthogonaux

Lattice-based cryptography

Afficher plus