The Ajtai random class of lattices

Thomas W. Cusick

doi:10.1016/S0304-3975(99)00063-8

The Ajtai random class of lattices

Thomas W. Cusick

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Ajtai has recently given a reduction from the problem of approximating a short basis for a lattice in the worst case, to the problem of finding a short lattice vector for a uniformly chosen lattice in a certain random class of lattices. Here we give an explicit formula for the number of lattices of the type used by Ajtai. We also prove some results about the average volume of the fundamental cell of such a lattice.

Original language	English
Pages (from-to)	29-36
Number of pages	8
Journal	Theoretical Computer Science
Volume	226
Issue number	1-2
DOIs	https://doi.org/10.1016/S0304-3975(99)00063-8
State	Published - Sep 17 1999

Keywords

Ajtai random class
Cryptography
Lattice
Provably secure cryptosystem

Access to Document

10.1016/S0304-3975(99)00063-8

Cite this

@article{ba8f48b2f2c848d1a194e6bebc236432,

title = "The Ajtai random class of lattices",

abstract = "Ajtai has recently given a reduction from the problem of approximating a short basis for a lattice in the worst case, to the problem of finding a short lattice vector for a uniformly chosen lattice in a certain random class of lattices. Here we give an explicit formula for the number of lattices of the type used by Ajtai. We also prove some results about the average volume of the fundamental cell of such a lattice.",

keywords = "Ajtai random class, Cryptography, Lattice, Provably secure cryptosystem",

author = "Cusick, \{Thomas W.\}",

year = "1999",

month = sep,

day = "17",

doi = "10.1016/S0304-3975(99)00063-8",

language = "English",

volume = "226",

pages = "29--36",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - The Ajtai random class of lattices

AU - Cusick, Thomas W.

PY - 1999/9/17

Y1 - 1999/9/17

N2 - Ajtai has recently given a reduction from the problem of approximating a short basis for a lattice in the worst case, to the problem of finding a short lattice vector for a uniformly chosen lattice in a certain random class of lattices. Here we give an explicit formula for the number of lattices of the type used by Ajtai. We also prove some results about the average volume of the fundamental cell of such a lattice.

AB - Ajtai has recently given a reduction from the problem of approximating a short basis for a lattice in the worst case, to the problem of finding a short lattice vector for a uniformly chosen lattice in a certain random class of lattices. Here we give an explicit formula for the number of lattices of the type used by Ajtai. We also prove some results about the average volume of the fundamental cell of such a lattice.

KW - Ajtai random class

KW - Cryptography

KW - Lattice

KW - Provably secure cryptosystem

UR - https://www.scopus.com/pages/publications/0347657122

U2 - 10.1016/S0304-3975(99)00063-8

DO - 10.1016/S0304-3975(99)00063-8

M3 - Article

AN - SCOPUS:0347657122

SN - 0304-3975

VL - 226

SP - 29

EP - 36

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

The Ajtai random class of lattices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this