On the smoothing parameter and last minimum of random orthogonal lattices

Elena Kirshanova; Huyen Nguyen; Damien Stehlé; Alexandre Wallet

doi:10.1007/s10623-020-00719-w

On the smoothing parameter and last minimum of random orthogonal lattices

Elena Kirshanova
, Huyen Nguyen
, Damien Stehlé
, Alexandre Wallet

Immanuel Kant Baltic Federal University
ENS Lyon
Institut Universitaire de France
NTT Secure Platform Laboratories

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

6 Citations (Scopus)

Abstract

Let X∈ Zⁿ ^× ^m, with each entry independently and identically distributed from an integer Gaussian distribution. We consider the orthogonal lattice Λ^⊥(X) of X, i.e., the set of vectors v∈ Z^m such that Xv= 0. In this work, we prove probabilistic upper bounds on the smoothing parameter and the (m- n) -th minimum of Λ^⊥(X). These bounds improve and the techniques build upon prior works of Agrawal et al. (Adv Cryptol 2013:97–116, 2013), and of Aggarwal and Regev (Chic J Theor Comput Sci 7:1–11, 2016).

Original language	English
Pages (from-to)	931-950
Number of pages	20
Journal	Designs, Codes, and Cryptography
Volume	88
Issue number	5
DOIs	https://doi.org/10.1007/s10623-020-00719-w
Publication status	Published - 1 May 2020
Externally published	Yes

Keywords

Last minimum
Lattice-based cryptography
Lattices and convex bodies
Random lattices
Smoothing parameter

Access to Document

10.1007/s10623-020-00719-w

Cite this

@article{1a4cef0d766c4612b27e3a1de21edee7,

title = "On the smoothing parameter and last minimum of random orthogonal lattices",

abstract = "Let X∈ Zn {\texttimes} m, with each entry independently and identically distributed from an integer Gaussian distribution. We consider the orthogonal lattice Λ⊥(X) of X, i.e., the set of vectors v∈ Zm such that Xv= 0. In this work, we prove probabilistic upper bounds on the smoothing parameter and the (m- n) -th minimum of Λ⊥(X). These bounds improve and the techniques build upon prior works of Agrawal et al. (Adv Cryptol 2013:97{\textendash}116, 2013), and of Aggarwal and Regev (Chic J Theor Comput Sci 7:1{\textendash}11, 2016).",

keywords = "Last minimum, Lattice-based cryptography, Lattices and convex bodies, Random lattices, Smoothing parameter",

author = "Elena Kirshanova and Huyen Nguyen and Damien Stehl{\'e} and Alexandre Wallet",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2020",

month = may,

day = "1",

doi = "10.1007/s10623-020-00719-w",

language = "English",

volume = "88",

pages = "931--950",

journal = "Designs, Codes, and Cryptography",

issn = "0925-1022",

publisher = "Springer Netherlands",

number = "5",

}

TY - JOUR

T1 - On the smoothing parameter and last minimum of random orthogonal lattices

AU - Kirshanova, Elena

AU - Nguyen, Huyen

AU - Stehlé, Damien

AU - Wallet, Alexandre

PY - 2020/5/1

Y1 - 2020/5/1

N2 - Let X∈ Zn × m, with each entry independently and identically distributed from an integer Gaussian distribution. We consider the orthogonal lattice Λ⊥(X) of X, i.e., the set of vectors v∈ Zm such that Xv= 0. In this work, we prove probabilistic upper bounds on the smoothing parameter and the (m- n) -th minimum of Λ⊥(X). These bounds improve and the techniques build upon prior works of Agrawal et al. (Adv Cryptol 2013:97–116, 2013), and of Aggarwal and Regev (Chic J Theor Comput Sci 7:1–11, 2016).

AB - Let X∈ Zn × m, with each entry independently and identically distributed from an integer Gaussian distribution. We consider the orthogonal lattice Λ⊥(X) of X, i.e., the set of vectors v∈ Zm such that Xv= 0. In this work, we prove probabilistic upper bounds on the smoothing parameter and the (m- n) -th minimum of Λ⊥(X). These bounds improve and the techniques build upon prior works of Agrawal et al. (Adv Cryptol 2013:97–116, 2013), and of Aggarwal and Regev (Chic J Theor Comput Sci 7:1–11, 2016).

KW - Last minimum

KW - Lattice-based cryptography

KW - Lattices and convex bodies

KW - Random lattices

KW - Smoothing parameter

U2 - 10.1007/s10623-020-00719-w

DO - 10.1007/s10623-020-00719-w

M3 - Article

AN - SCOPUS:85078399868

SN - 0925-1022

VL - 88

SP - 931

EP - 950

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

IS - 5

ER -

On the smoothing parameter and last minimum of random orthogonal lattices

Abstract

Keywords

Access to Document

Fingerprint

Cite this