서브메뉴
검색
Lattice Problems: New Lower and Upper Bounds
Lattice Problems: New Lower and Upper Bounds
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202105239
- ISBN
- 9798291569153
- DDC
- 004
- 저자명
- Tang, Yi.
- 서명/저자
- Lattice Problems: New Lower and Upper Bounds
- 발행사항
- [Sl] : University of Michigan, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 115 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-03, Section: B.
- 주기사항
- Advisor: Peikert, Chris.
- 학위논문주기
- Thesis (Ph.D.)--University of Michigan, 2025.
- 초록/해제
- 요약In the upcoming era of quantum computation, those successful classical, number-theoretical public-key cryptosystems that get widely deployed nowadays, such as RSA or ElGamal, all face severe insecurity if the adversary gets access to quantum computers. More urgently, time-insensitive secrets on today's systems are facing immediate threats of the same level due to the "harvest now, decrypt later" attack. The field of post-quantum cryptography aims at building quantum-safe systems to prepare for the future. Among all candidate post-quantum proposals, lattice-based cryptography, which builds cryptosystems based on lattice problems, so far provides the best results in terms of performance, simplicity, and versatility. It is thus important to better understand the complexity of lattice problems.In this thesis, we study a couple of new lower and upper bounds for various lattice problems under various complexity notions. These new results include:1. (Fine-grained hardness/lower bounds.) The fine-grained (exponential-time) complexity studies the precise constant c in the 2nc or 2c·n running time for solving a computational problem, usually based on (variants of) the exponential time hypothesis (ETH) or the strong exponential time hypothesis (SETH).Under this complexity notion, for the bounded distance decoding problem (BDD), we give quantitatively improved bounds on the approximation factor α for which BDDα cannot be solved in 2o(n) or 2c·n time, assuming variants of ETH or SETH, respectively, and for part of our results also assuming a geometric conjecture known as exponential lattice kissing number. For the shortest vector problem (SVP), we show a qualitatively improved result that for some constant approximation factor γ1, SVPγ cannot be solved in 2c·n time, assuming a variant of SETH; previously, only analogous result for non-approximate, exact SVP was known.2. ("Standard" NP-hardness.) The NP-hardness is a classical flag for identifying a computational problem as being hard. For SVP, previously only NP-hardness results under randomized reductions are known (except in corner cases), and whether SVP is "standardly" NP-hard under deterministic reductions is a notoriously longstanding open problem. We propose conjectures about ways to derandomize existing reductions, which would lead to the "standard" NP-hardness of approximate SVP. We also present empirical evidences that support the conjectures.3. (Parallel algorithms/upper bounds.) The parallel complexity/sequentially of a computational problem is crucial for its applications in time-release/timed cryptography. We show logarithmic-depth parallel algorithms for a sequential version of the short integer solution problem (SIS), which is used in a certain proof of sequential work (PoSW) timed-cryptographic protocol. This means that sequential SIS has low parallel complexity, as opposed to its previous conjecture. Moreover, we show a polylogarithmic-depth parallel attack that (almost) breaks that PoSW protocol.
- 일반주제명
- Computer science
- 일반주제명
- Computer engineering
- 일반주제명
- Applied mathematics
- 키워드
- Lattice problems
- 기타저자
- University of Michigan Computer Science & Engineering
- 기본자료저록
- Dissertations Abstracts International. 87-03B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017359943
■00520260202105239
■006m o d
■007cr#unu||||||||
■020 ▼a9798291569153
■035 ▼a(MiAaPQ)AAI32271983
■035 ▼a(MiAaPQ)umichrackham006520
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aTang, Yi.
■24510▼aLattice Problems: New Lower and Upper Bounds
■260 ▼a[Sl]▼bUniversity of Michigan▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a115 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-03, Section: B.
■500 ▼aAdvisor: Peikert, Chris.
■5021 ▼aThesis (Ph.D.)--University of Michigan, 2025.
■520 ▼aIn the upcoming era of quantum computation, those successful classical, number-theoretical public-key cryptosystems that get widely deployed nowadays, such as RSA or ElGamal, all face severe insecurity if the adversary gets access to quantum computers. More urgently, time-insensitive secrets on today's systems are facing immediate threats of the same level due to the "harvest now, decrypt later" attack. The field of post-quantum cryptography aims at building quantum-safe systems to prepare for the future. Among all candidate post-quantum proposals, lattice-based cryptography, which builds cryptosystems based on lattice problems, so far provides the best results in terms of performance, simplicity, and versatility. It is thus important to better understand the complexity of lattice problems.In this thesis, we study a couple of new lower and upper bounds for various lattice problems under various complexity notions. These new results include:1. (Fine-grained hardness/lower bounds.) The fine-grained (exponential-time) complexity studies the precise constant c in the 2nc or 2c·n running time for solving a computational problem, usually based on (variants of) the exponential time hypothesis (ETH) or the strong exponential time hypothesis (SETH).Under this complexity notion, for the bounded distance decoding problem (BDD), we give quantitatively improved bounds on the approximation factor α for which BDDα cannot be solved in 2o(n) or 2c·n time, assuming variants of ETH or SETH, respectively, and for part of our results also assuming a geometric conjecture known as exponential lattice kissing number. For the shortest vector problem (SVP), we show a qualitatively improved result that for some constant approximation factor γ1, SVPγ cannot be solved in 2c·n time, assuming a variant of SETH; previously, only analogous result for non-approximate, exact SVP was known.2. ("Standard" NP-hardness.) The NP-hardness is a classical flag for identifying a computational problem as being hard. For SVP, previously only NP-hardness results under randomized reductions are known (except in corner cases), and whether SVP is "standardly" NP-hard under deterministic reductions is a notoriously longstanding open problem. We propose conjectures about ways to derandomize existing reductions, which would lead to the "standard" NP-hardness of approximate SVP. We also present empirical evidences that support the conjectures.3. (Parallel algorithms/upper bounds.) The parallel complexity/sequentially of a computational problem is crucial for its applications in time-release/timed cryptography. We show logarithmic-depth parallel algorithms for a sequential version of the short integer solution problem (SIS), which is used in a certain proof of sequential work (PoSW) timed-cryptographic protocol. This means that sequential SIS has low parallel complexity, as opposed to its previous conjecture. Moreover, we show a polylogarithmic-depth parallel attack that (almost) breaks that PoSW protocol.
■590 ▼aSchool code: 0127.
■650 4▼aComputer science
■650 4▼aComputer engineering
■650 4▼aApplied mathematics
■653 ▼aComputational complexity
■653 ▼aLattice problems
■653 ▼aFine-grained complexity
■653 ▼aParallel algorithms
■690 ▼a0984
■690 ▼a0464
■690 ▼a0364
■71020▼aUniversity of Michigan▼bComputer Science & Engineering.
■7730 ▼tDissertations Abstracts International▼g87-03B.
■790 ▼a0127
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17359943▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
