Algebraic solvers for certain lattice-related problems

Jintai Ding

doi:10.1109/ITW.2011.6089489

Algebraic solvers for certain lattice-related problems

Jintai Ding^*

^*Corresponding author for this work

University of Cincinnati

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

2 Citations (Scopus)

Abstract

In this paper, we present a new algorithm to solve algebraically the following lattice-related problems: 1) the small integer solution (SIS) problem under the condition: if the solution is bounded by an integer β in l _∞ norm, which we call a bounded SIS (BSIS) problem, and if the difference between the row dimension n and the column dimension m of the corresponding basis matrix is relatively small with respect the row dimension m; 2) the learning with errors (LWE) problems under the condition: if the errors are bounded the errors do not span the whole prime finite field F _q but a fixed known subset of size D (D < q), which we call a learning with bounded errors (LWBE) problem. We will show that we can solve these problems with polynomial complexity.

Original language	English
Title of host publication	2011 IEEE Information Theory Workshop, ITW 2011
Pages	405-409
Number of pages	5
DOIs	https://doi.org/10.1109/ITW.2011.6089489
Publication status	Published - 2011
Externally published	Yes
Event	2011 IEEE Information Theory Workshop, ITW 2011 - Paraty, Brazil Duration: 16 Oct 2011 → 20 Oct 2011

Publication series

Name	2011 IEEE Information Theory Workshop, ITW 2011

Conference

Conference	2011 IEEE Information Theory Workshop, ITW 2011
Country/Territory	Brazil
City	Paraty
Period	16/10/11 → 20/10/11

Access to Document

10.1109/ITW.2011.6089489

Cite this

@inproceedings{a22a634f292a40a98216c214a2849d0f,

title = "Algebraic solvers for certain lattice-related problems",

abstract = "In this paper, we present a new algorithm to solve algebraically the following lattice-related problems: 1) the small integer solution (SIS) problem under the condition: if the solution is bounded by an integer β in l ∞ norm, which we call a bounded SIS (BSIS) problem, and if the difference between the row dimension n and the column dimension m of the corresponding basis matrix is relatively small with respect the row dimension m; 2) the learning with errors (LWE) problems under the condition: if the errors are bounded the errors do not span the whole prime finite field F q but a fixed known subset of size D (D < q), which we call a learning with bounded errors (LWBE) problem. We will show that we can solve these problems with polynomial complexity.",

author = "Jintai Ding",

year = "2011",

doi = "10.1109/ITW.2011.6089489",

language = "English",

isbn = "9781457704376",

series = "2011 IEEE Information Theory Workshop, ITW 2011",

pages = "405--409",

booktitle = "2011 IEEE Information Theory Workshop, ITW 2011",

note = "2011 IEEE Information Theory Workshop, ITW 2011 ; Conference date: 16-10-2011 Through 20-10-2011",

}

TY - GEN

T1 - Algebraic solvers for certain lattice-related problems

AU - Ding, Jintai

PY - 2011

Y1 - 2011

N2 - In this paper, we present a new algorithm to solve algebraically the following lattice-related problems: 1) the small integer solution (SIS) problem under the condition: if the solution is bounded by an integer β in l ∞ norm, which we call a bounded SIS (BSIS) problem, and if the difference between the row dimension n and the column dimension m of the corresponding basis matrix is relatively small with respect the row dimension m; 2) the learning with errors (LWE) problems under the condition: if the errors are bounded the errors do not span the whole prime finite field F q but a fixed known subset of size D (D < q), which we call a learning with bounded errors (LWBE) problem. We will show that we can solve these problems with polynomial complexity.

AB - In this paper, we present a new algorithm to solve algebraically the following lattice-related problems: 1) the small integer solution (SIS) problem under the condition: if the solution is bounded by an integer β in l ∞ norm, which we call a bounded SIS (BSIS) problem, and if the difference between the row dimension n and the column dimension m of the corresponding basis matrix is relatively small with respect the row dimension m; 2) the learning with errors (LWE) problems under the condition: if the errors are bounded the errors do not span the whole prime finite field F q but a fixed known subset of size D (D < q), which we call a learning with bounded errors (LWBE) problem. We will show that we can solve these problems with polynomial complexity.

UR - http://www.scopus.com/inward/record.url?scp=83655164958&partnerID=8YFLogxK

U2 - 10.1109/ITW.2011.6089489

DO - 10.1109/ITW.2011.6089489

M3 - Conference Proceeding

AN - SCOPUS:83655164958

SN - 9781457704376

T3 - 2011 IEEE Information Theory Workshop, ITW 2011

SP - 405

EP - 409

BT - 2011 IEEE Information Theory Workshop, ITW 2011

T2 - 2011 IEEE Information Theory Workshop, ITW 2011

Y2 - 16 October 2011 through 20 October 2011

ER -

Algebraic solvers for certain lattice-related problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this