MARC

 008260126s2025        us                              c    eng  d
■001000017359919
■00520260202105236
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798291567876
■035    ▼a(MiAaPQ)AAI32271947
■035    ▼a(MiAaPQ)umichrackham006230
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a510
■1001  ▼aVeliche  Hostetler,  Alexandra.
■24510▼aCodes  &  Lattices:  Computational  Complexity  and  Constructions
■260    ▼a[Sl]▼bUniversity  of  Michigan▼c2025
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2025
■300    ▼a121  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-02,  Section:  A.
■500    ▼aAdvisor:  Cheraghchi,  Mahdi.
■5021  ▼aThesis  (Ph.D.)--University  of  Michigan,  2025.
■520    ▼aLinear  codes  and  point  lattices  are  two  mathematical  objects  that  play  a  fundamental  role  in  many  areas  of  computer  science.  In  cryptography  the  computational  hardness  of  problems  for  codes  and  lattices  is  used  as  a  security  assumption  for  most  cryptographic  schemes  proposed  to  be  post-quantum.  Understanding  the  complexity  of  these  problems,  and  how  techniques  for  codes  and  lattices  are  related,  is  crucial  for  understanding  the  security  of  the  corresponding  cryptosystems.  With  this  motivation,  we  explore  both  the  computational  complexity  and  algorithmic  sides  of  coding  problems  and  lattice  problems.We  study  the  computational  complexity  of  two  key  problems  relevant  to  cryptography:  Learning  With  Errors  (LWE)  and  Code  Equivalence  (CE).  For  problems  like  LWE,  we  introduce  an  alternative  measure  of  computational  hardness:  the  maximum  success  probability  achievable  by  any  probabilistic  polynomial-time  algorithm.  This  more  accurately  models  the  security  goals  of  cryptosystems  based  on  these  problems.  Under  this  new  perspective,  we  study  the  worst-case  to  average-case  hardness  of  LWE  and  prove  a  tight  Turing  reduction  from  the  Bounded  Distance  Decoding  (BDD)  problem  to  both  search  and  decision  variants  of  LWE.  Our  reduction  improves  previous  reductions  by  using  only  a  few  oracle  calls  and  explicitly  quantifying  the  loss  in  success  probability.  The  CE  problem  has  several  variants,  including  Permutation  (PCE),  Signed  Permutation  (SPCE),  and  Linear  (LCE)  Code  Equivalence.  We  prove  polynomial-time  Karp  reductions  from  PCE  to  both  LCE  and  SPCE.  Along  with  a  known  Karp  reduction  from  SPCE  to  the  Lattice  Isomorphism  Problem  (LIP),  our  second  result  implies  a  reduction  from  PCE  to  LIP.On  the  algorithmic  side,  we  use  lattices  and  Fourier  analytic  techniques  to  construct  an  algorithm  that  list-decodes  Generalized  Reed-Solomon  (GRS)  codes  from  worst-case  or  average-case  errors  over  any  ℓp  (quasi)norm  where  0    p  =  2.  This  is  based  on  the  Guruswami-Sudan  soft-decision  decoding  algorithm.  Our  algorithm  generalizes  previous  algorithms  for  the  ℓ2  and  ℓ1  norms  and  achieves  a  better  rate-(decoding)  distance  trade-off  than  these  algorithms.  We  also  discuss  lattice  list-decoding  capacity  bounds  for  general  norms  and  construct  lattices  with  high  density  -  which  achieve  the  Minkowski  bound  -  using  Construction  D  applied  to  random  linear  codes.
■590    ▼aSchool  code:  0127.
■650  4▼aMathematics
■650  4▼aComputer  science
■650  4▼aInformation  science
■653    ▼aLattices
■653    ▼aLinear  codes
■653    ▼aLearning  With  Errors
■653    ▼aBounded  Distance  Decoding
■653    ▼aList  decoding
■690    ▼a0984
■690    ▼a0405
■690    ▼a0723
■71020▼aUniversity  of  Michigan▼bComputer  Science  &  Engineering.
■7730  ▼tDissertations  Abstracts  International▼g87-02A.
■790    ▼a0127
■791    ▼aPh.D.
■792    ▼a2025
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17359919▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서