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. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign. Ideal lattices also form the basis for quantum computer attack resistant cryptography based on the Ring Learning with Errors. These cryptosystems are provably secure under the assumption that the shortest vector problem (SVP) is hard in these ideal lattices. In general terms, ideal lattices are lattices corresponding to ideals in rings of the form for some irreducible polynomial of degree . All of the definitions of ideal lattices from prior work are instances of the following general notion: let be a ring whose additive group is isomorphic to (i.e., it is a free -module of rank ), and let be an additive isomorphism mapping to some lattice in an -dimensional real vector space (e.g., ). The family of ideal lattices for the ring under the embedding is the set of all lattices , where is an ideal in Let be a monic polynomial of degree , and consider the quotient ring . Using the standard set of representatives , and identification of polynomials with vectors, the quotient ring is isomorphic (as an additive group) to the integer lattice , and any ideal defines a corresponding integer sublattice . An ideal lattice is an integer lattice such that for some monic polynomial of degree and ideal . It turns out that the relevant properties of for the resulting function to be collision resistant are: should be irreducible.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (64)

Personnes associées (13)

Unités associées (10)

Concepts associés (4)

Cours associés (3)

Séances de cours associées (32)

Mean value theorems for collections of lattices with a prescribed group of symmetries

Nihar Prakash Gargava

Euclidean lattices are mathematical objects of increasing interest in the fields of cryptography and error-correcting codes. This doctoral thesis is a study on high-dimensional lattices with the motivation to understand how efficient they are in terms of b ...

EPFL2024

Hausdorff dimension of fermions on a random lattice

Mattia Guerino Varrone

Geometric properties of lattice quantum gravity in two dimensions are studied numerically via Monte Carlo on Euclidean Dynamical Triangulations. A new computational method is proposed to simulate gravity coupled with fermions, which allows the study of int ...

Elsevier2024

Solute-strengthening in metal alloys with short-range order

William Curtin, Shankha Nag

Recent surging interest in strengthening of High Entropy Alloys (HEAs) with possible chemical ordering motivates the development of new theory. Here, an existing theory for random alloys that accounts for solute-dislocation and solute–solute interactions i ...

2024

Ring learning with errors key exchange

In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors key exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a quantum computer. This is important because some public key algorithms in use today will be easily broken by a quantum computer if such computers are implemented.

Cryptographie post-quantique

La cryptographie post-quantique est une branche de la cryptographie visant à garantir la sécurité de l'information face à un attaquant disposant d'un calculateur quantique. Cette discipline est distincte de la cryptographie quantique, qui vise à construire des algorithmes cryptographiques utilisant des propriétés physiques, plutôt que mathématiques, pour garantir la sécurité. En l'effet, les algorithmes quantiques de Shor, de Grover et de Simon étendent les capacités par rapport à un attaquant ne disposant que d'un ordinateur classique.

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.

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer s

This advanced course will provide students with the knowledge to tackle the design of privacy-preserving ICT systems. Students will learn about existing technologies to prect privacy, and how to evalu

Ondes topologiques pour des applications de traitement de signaux robustes

Explore les ondes topologiques pour des applications robustes de traitement des signaux, en mettant l'accent sur la résistance aux perturbations et le paradigme de conception des systèmes topologiques.

Réseaux topologiques anomaux : théorie et expérience

Explore la robustesse anormale dans les réseaux topologiques non réciproques, couvrant les états topologiques de Floquet, les réseaux de diffusion unitaire et les implémentations pratiques.

ALL Algorithme MATH-489: Number theory II.c - Cryptography

Couvre l'algorithme LLL pour la réduction des treillis et discute de la constante d'Hermite et du théorème de Minkowski.