I nd o ne s ia n J o urna l o f   E lect rica l En g ineering   a nd   Co m pu t er   Science   Vo l.   3 8 ,   No .   2 ,  Ma y   20 2 5 ,   p p .   732 ~ 7 4 3   I SS N:  2 502 - 4 7 52 ,   DOI : 1 0 . 1 1 5 9 1 /ijee cs .v 3 8 . i 2 . pp 732 - 7 4 3           732     J o ur na l ho m ep a g e :  h ttp : //ij ee cs . ia esco r e. co m   An   ef ficien t  ha rd wa re impleme nta tion o f  num ber  th eo retic   trans form for  CR YSTAL S - K y ber  po st - qua ntum  cry ptog ra phy       T ra ng   H o a ng ,   T u Dinh Anh  Duo ng ,   T hin h Q ua ng   Do   F a c u l t y   o f   E l e c t r i c a l - El e c t r o n i c s ,   H o   C h i   M i n h   C i t y   U n i v e r s i t y   o f   T e c h n o l o g y ,   V i e t n a m N a t i o n a l   U n i v e r s i t y   H o   C h i   M i n h   C i t y ,     H o   C h i   M i n h   C i t y ,   V i e t n a m       Art icle  I nfo     AB S T RAC T   A r ticle  his to r y:   R ec eiv ed   Mar   17 ,   2 0 2 4   R ev is ed   Oct   25 ,  202 4   Acc ep ted   No v   11 ,   2 0 2 4       CRYST ALS - Ky b e r   wa s   c h o se n   to   be   th e   sta n d a rd ize d   k e y   e n c a p su latio n   m e c h a n ism s  (KEM s)  o u t  o f  t h e   fin a li sts  in   th e   t h ir d   ro u n d   o f  t h e   Na ti o n a l  In stit u te  o f  S ta n d a rd s  a n d   Tec h n o lo g y   (NIS T)  p o st - q u a n t u m   c ry p to g ra p h y   (P QC)   sta n d a rd iza ti o n   p r o g ra m .   S i n c e   th e   n u m b e r  t h e o re ti c   tran sfo rm     (NTT )  wa s  u se d   t o   re d u c e   t h e   c o m p u tatio n a l  c o m p lex it y   o f  p o ly n o m ial   m u lt ip li c a ti o n ,   i t  h a s  a lwa y s  b e e n   a   c ru c ial  a rit h m e ti c   c o m p o n e n t  in   CRYST ALS - Ky b e r  d e sig n .   I n   t h i s  p a p e r,   a   sim p le   a n d   e fficie n t  a r c h it e c tu re   fo r  NTT   is  p re se n ted   wh e re   we   e a sily   a rc h iv e d   t h e   f u n c ti o n a li t y   o f   p o l y n o m ial  m u lt i p li c a ti o n   wit h   e fficie n t  c o m p u tatio n   ti m e .   O n ly   8 5 7   Lo o k - Up   Tab les   a n d   7 4 4   fl ip - fl o p s  we re   u ti li z e d   in   o u r  NTT  d e si g n ,   w h ich   c o n siste d   o f   two   p ro c e ss in g   e lem e n ts  (P Es)  a n d   tw o   b u tt e rfl y   c o re s  with in   e a c h   P E.   K ey w o r d s :   C R Y STAL S - Ky b er   Har d war e  im p lem en tatio n   Nu m b er   th e o r etic  tr an s f o r m   Po ly n o m ial  m u ltip licatio n   Po s t - q u an tu m   cr y p to g r ap h y   T h is i s  a n   o p e n   a c c e ss   a rticle   u n d e r th e   CC B Y - SA   li c e n se .     C o r r e s p o nd ing   A uth o r :   T r an g   Ho a n g   Facu lty   o f   E lectr ical - E lectr o n ics,  Ho   C h i M in h   C ity   Un iv er s ity   o f   T ec h n o lo g y   Vietn am   Natio n al  Un iv er s ity   Ho   C h i M in h   C ity   2 6 8   L y   T h u o n g   Kiet,   Dis tr ict  1 0 ,   Ho   C h i M in h   C ity ,   Vietn am   E m ail :  h o an g tr a n g @ h cm u t.e d u . v n       1.   I NT RO D UCT I O N   Sin ce   th e  ap p licatio n   o f   Sh o r ’ s   alg o r ith m ,   class ical  p u b lic - k ey   cr y p t o g r ap h y   p r o to c o ls   h av e  b ec o m e   in cr ea s in g ly   v u ln er a b le  to   q u an tu m   co m p u ter   attac k s   [ 1 ] .   C R Y STAL S - Ky b er   is   o n e  o f   th e  f in alis ts   in   th e   th ir d   r o u n d   o f   p o s t - q u an t u m   c r y p to g r ap h y   ( PQC )   alg o r it h m   ev alu atio n   b y   t h e  Natio n al   I n s titu te  o f   Stan d a r d s   an d   T ec h n o lo g y   ( N I ST) ,   a  c o m p etitio n   to   d eter m in e  v ar io u s   alg o r ith m s   to   with s tan d   atta ck s   f r o m   q u a n tu m   co m p u ter s .   Sp ec if ically ,   th e   a lg o r ith m   is   a   lattice - b ased   c r y p to s y s tem   b ased   o n   th e   m o d u le  lear n i n g - with - er r o r s   p r o b lem   ( ML E ) .   I n   J u ly   2 0 2 2 ,   C R YSTA L S - Ky b er   was  s elec ted   as  th e  s t an d ar d   Pu b lic - Key   E n cr y p tio n /Key   E n ca p s u latio n   Me ch an is m   [ 2 ] .     C R Y STAL S - Ky b er   an d   o th er   lattice - b ased   cr y p to s y s tem s   ex ten s iv ely   r ely   o n   p o ly n o m ial   m u ltip licatio n .   I t  s er v es  as  th e  p r im ar y   o p er atio n ,   b u t  its   im p lem en tatio n   m ig h t  b e  co m p u tatio n ally   in ten s iv e,   ca u s in g   a  b o ttlen ec k   [ 3 ] .   T o   o v er co m e   th is   is s u e,   an   alg o r ith m   b ased   o n   n u m b er   th eo r eti c  tr an s f o r m   ( NT T )   f o r   p o ly n o m ial  m u ltip licatio n   h as  b ee n   u s ed .   T h is   alg o r ith m   is   a  ty p ica l  m eth o d   f o r   ca l cu latin g   p o ly n o m ial  m u ltip licatio n   with   less   co m p lex   o p er atio n s ,   th e r eb y   d ec r ea s in g   th e  co m p u tatio n al  b u r d en   o f   lattice - b ased   cr y p to s y s tem s .   B y   ap p ly in g   t h e  NT T - b ased   p o l y n o m ial  m u ltip licatio n   m eth o d ,   t h e  p er f o r m an ce   o f   lattice - b ased   cr y p to s y s tem s   ca n   b e   s ig n if ican tly   en h a n ce d ,   m ak in g   th em   m o r e  a p p licab le   an d   ef f ec tiv e  in   a   r a n g e   o f   co n tex ts .   Op tim izin g   th e   co m p lex ity   o f   h ar d war e  ac ce ler at o r s   is   o n e  o f   th e  m o s t  cr itical  f ac to r s   in   s elec tin g   an   o p tim al  h ar d war e  d esig n   a p p r o ac h   f o r   s ch em es.  Fo r   th e  p u r p o s e  o f   v alid atin g   th e  ef f i ca cy   o f   a  s p ec if ied   d esig n   ap p r o ac h ,   b en c h m ar k s   s h o u ld   b e  ex ec u te d   o n   a  v ar ie ty   o f   im p lem en tatio n   p latf o r m s .   Desp ite  th e  f ac t   th at  s o f twar e - im p lem en ted   d esig n s   p r o v id e  in tu itiv e  a n d   u s er - f r ien d l y   in ter f ac es,  th e ir   p er f o r m an ce   is   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2 5 0 2 - 4 7 52       A n   efficien t h a r d w a r e  imp leme n ta tio n   o f  n u mb er th eo r etic  t r a n s fo r m  fo r   … ( Tr a n g   Ho a n g )   733   ty p ically   in f er i o r   to   th at  o f   o th er   p latf o r m s   [ 4 ] .   A  h y b r i d   d esig n   o f   s o f twar e   an d   h a r d war e  was  u s ed   to   im p r o v e   th e  p er f o r m an ce   wh ile  r etain in g   t h e  f lex i b ilit y   o f   th e  d esig n   with   s o f twar e  o n ly .   Alth o u g h   th e   d esig n s   im p lem en ted   o n   b o t h   p latf o r m s   wo u ld   b e  f lex ib le  a n d   d esig n - tim e  e f f icien t,  th ey   d id   n o t  p r o v i d e  th e   s am e  lev el  o f   p er f o r m an ce   as  th e  p u r e   h ar d war e  d es ig n .   I n   c o n tr ast,  h ar d war e  im p lem en tatio n   is   ch ar ac ter ized   b y   th e  c o m p lex i ty   o f   its   alg o r ith m s   a n d   th e  la ck   o f   b asic  u n its   wr itten   in   h a r d war e  d escr ip ti o n   lan g u ag es,  p o s in g   a  ch alle n g e  to   d esig n er s   w h o   a r e  task ed   w ith   cr ea tin g   th e  h ar d war e   f o r   c o m p lex   alg o r ith m s   u s in g   b asic  lo g ic  g ates.  I n   r etu r n ,   p u r e  h ar d war e  im p lem en tatio n s   wo u ld   o f f er   d esig n er s   th e  b est   p er f o r m an ce .   T h e  h a r d war e  d esig n   e n co m p ass es  a  d iv er s e  ar r ay   o f   d e v ices  with   v ar y in g   s p ec if icatio n s ,   d esig n   co n s tr ain ts ,   an d   im p lem en tati o n   s ettin g s .   T h ese  f ac to r s   m ak e  it  d if f icu lt  to   f air ly   co m p ar e  th e  h ar d war e   im p lem en tatio n s   o f   v ar i o u s   d esig n s .   Ap p licatio n - s p ec if ic  in teg r ated   cir cu it  ( ASI C )   an d   f ield - p r o g r am m a b le  g ate  ar r ay   ( FP GA)   ar e  t h e  t wo   p r im ar y   ar c h itectu r es  u s ed   f o r   h a r d war e  im p lem en ta tio n ,   an d   th e y   ar e   f r eq u e n tly   em p lo y e d   in   r esear ch   an al y s is   an d   d ev elo p m en t.   T h e  NI ST   r ec o m m e n d s   t h e  u s e  o f   Xilin x   Ar tix - 7  FP GA  f o r   h ar d war e  im p lem e n tatio n   in   o r d er   to   co m p ar e  th e  d esig n   with   g r ea ter   p r ec is io n   [ 5 ] .   ASI C   r esu lts ,   o n   th e  o t h er   h a n d ,   ar e  h ig h l y   d ep en d e n t  o n   t h e  tech n o lo g y   l ib r ar y   an d   s y s tem   co n f i g u r ati o n s   u s ed   d u r in g   th e   im p lem en tatio n   p r o ce s s .   T h is   m ak es it d if f icu lt to   co m p ar e  d esig n s   to   o th er s ,   as th e  im p le m en tatio n   d etails o f   d if f er en t   p r o jects  ca n   v ar y   s ig n if ican tly .   Desp ite  th ese  o b s tacle s ,   ASI C s   co n tin u e  t o   b e  an   im p o r ta n t  an d   wid ely   em p lo y ed   to o l  in   th e  f ield   o f   h ar d wa r e  d esig n ,   esp ec ially   f o r   lar g e - s ca le  an d   co m p lex   s y s tem s   th at   r eq u ir e  a   h ig h   d eg r ee   o f   p r ec i s io n   an d   d ep e n d ab ilit y   [ 6 ] .   Fo r   ex am p le,   B an er jee  et   a l.   [ 6 ]   p r esen ted   a   l attice  cr y p to g r ap h y   p r o ce s s o r   with   co n f ig u r ab le  p ar am eter s   th at   h ad   an   NT T   b lo ck   ac ce ler ate d   b y   a  s in g le - p o r t   R AM - b ased   m em o r y   ar ch ite ctu r e  o n   an   ASI C   th at  aim ed   to   o p tim ize  r eso u r ce s ,   b u t   th eir   d esig n   was   in ef f icien t,  esp ec ially   in   ter m s   o f   f r eq u e n cy   an d   laten cy .   Mo r eo v er ,   a  lo w - p o wer   an d   r eso u r ce - ef f icien t  NT T   ASI C   d esig n   was   p r esen ted   in   [ 7 ] .   Alth o u g h   th e  ar ea   an d   p o wer   r esu lts   wer e  g o o d ,   th e  d esig n   d id   n o t  o f f er   a   g o o d   tr a d e - o f f   b etwe en   tim in g   an d   r eso u r ce   ef f icien c y .   So n g   et  a l.   [ 8 ]   also   p r o p o s ed   o n e  o f   th e  q u ic k est  an d   m o s t  en er g y - e f f icien t  NT T s   o n   ASI C ,   b u t  with   o p aq u e  r eso u r ce s ,   wh ich   co u l d   b e  in ter p r eted   as  a  tr ad e - o f f   b etwe en   r eso u r ce s ,   tim in g ,   an d   p o wer .   T h e  co m p ar is o n s   o n   th e  FP GA  s id e  d id   n o t  lo o k   g o o d   eith er ,   wh er ea s   d esig n er s   u s e d   d if f e r en t  FP GA  f am ilie s   an d   th er e  wer e  u s u ally   co n f licts   b etwe en   th r ee   asp ec ts :  r eso u r ce s ,   tim in g ,   an d   p o wer .   Fritzm an n   et  a l.   [ 9 ] ,   R I SQ - V,   a  tig h tly   c o u p le d   R I SC - V  ac ce ler ato r   f o r   b o th   ASI C   an d   Xilin x   Z y n q - 7 0 0 0   FP GA  was  p r o p o s ed .   Kar ab u lu t  an d   Ay s u   [ 1 0 ]   also   cr ea te d   a   r eso u r ce - o p tim ized   R I SC - V  NT T   c o r e   o n   a  Xilin x   Vir tex - 7   FP GA,   alb eit   with   h ig h   tim in g   laten cy .   I n   [ 4 ]   an d   [ 11 ] ,   Xilin x   Ar tix - 7   was  u s ed   as  th e  im p lem en tatio n   p latf o r m   f o r   th e  NT T   d esig n ;  h o wev er ,   th e   NT T   d esig n   in tr o d u ce d   in   [ 4 ]   was  m o r e   tim in g - ef f icien t   th an   th at  i n   [ 1 1 ]   d u e   to   th e   d o u b le   n u m b er   o f   b u t ter f ly   co r es,  r esu ltin g   in   a   h i g h er   f r eq u en cy   an d   lo wer   laten cy .   T h e  f r e q u en c y   r esu lts   f o r   [ 9 ]   an d   [ 1 0 ]   wer e  n u ll.  On   th e  o th er   h a n d ,   th e  d e s ig n er s   o m itted   th e  r eso u r ce   r esu lts   in   [ 4 ]   an d   [ 11 ] ,   m ak in g   it d i f f icu lt t o   co m p a r e  th e  d esig n   a p p r o ac h .   Me n tio n in g   FP GA  r eso u r ce s ,   th e  n u m b er   o f   lo o k - u p   tab les ( L UT s )   an d   f lip   f lo p s   ( FF s )   u s e d   in   [ 6 ]   is   en o r m o u s   d u e  to   th e  lar g e  n u m b er   o f   m u ltip lier s ,   wh er ea s   d esig n er   co u ld   u s e  th e  d ig ital  s ig n al  p r o ce s s in g   ( DSP)  m o d u l e  in   th e  FP GA  f o r   in teg er   m u ltip lier   to   r e d u c e  th e  n u m b er   o f   L UT s   an d   D FF s   th at  m ig h t  b e  u s ed .   T h is   m ay   also   b alan ce   th e  FP GA  r eso u r ce s   to   co n s e r v e  th em   f o r   o th er   lo g ic  c o m p o n en ts   with in   th e   C R Y STAL S - Ky b er   h ar d war e.   T h e  NT T   h ar d war e  d escr ib ed   in   [ 4 ]   u tili z ed   o n ly   o n e  b lo ck   R AM   ( B R AM )   f o r   s to r in g   p o ly n o m ials ,   r esu ltin g   in   a  d esig n   with   a  h ig h   laten c y .   I n   s u m m ar y ,   at   th e  m o m en t ,   m o s t  s tu d ies  o n   NT T   h a r d war e  im p lem e n tatio n   h a v e  th eir   o wn   wea k n ess es  th at  co u ld   b e   ad d r ess ed   f o r   b etter   p er f o r m an ce .   All  th e  af o r em en tio n ed   f ac to r s   led   u s   to   d esig n   a   Xilin x   Ar tix - 7   FP GA  an d   ASI C   NT T   with   b alan ce d   f r e q u en cy ,   laten c y ,   an d   p o wer   e f f i cien cy .   Ou r   d esig n   also   u tili ze d   th e  FP GA  r eso u r ce   b y   in co r p o r atin g   th e  DSP  an d   B R AM   u n it,  wh ich   p r ev en ted   th e  ex ce s s iv e   u s e  o f   L UT   a n d   FF   an d   th e   r i s k   o f   FP GA  r eso u r ce   o v er - u tili za tio n   wh en   i n teg r atin g   th e  NT T   d esig n   in to   th e   co m p lete  C R YSTA L S - Ky b er   h ar d war e  d esig n .   Sp ec if ically ,   th e  u s e  o f   DSP  in   o u r   FP GA  r esu lted   in   a   3 3 %   r ed u ctio n   in   th e   n u m b er   o f   L UT s   an d   DFF  u s ed .   Mo r e o v er ,   we  u s ed   th r e e  B R AM s   p er   b u tter f ly   co r e  to   s to r e   p o ly n o m ials   an d   twid d le  f ac t o r s ,   allo win g   o u r   b u tter f ly   c o r es  to   o p er ate  in   p ar allel  an d   r ed u cin g   laten c y   b y   6 4 . 5 % r elativ e  to   [ 4 ] .   C o n tr ib u tio n   o f   th is   wo r k :   Po ly n o m ial  m u ltip licatio n   ar it h m etic  is   o n e  o f   th e  m o s t  im p o r tan t  co m p o n e n ts   o f   th e  C R YSTA L S   Ky b er   h ar d war e   im p lem en tati o n   s in ce   it   h as  a  s ig n i f ican t  i m p ac t  o n   th e   laten cy   an d   ef f i cien cy   o f   th e   d esig n   [ 1 2 ] – [ 1 7 ] .   B y   u tili zin g   th e  N T T   co r e   to   ap p l y   NT T - b ased   p o ly n o m ial   m u ltip licatio n ,   we  m ay   lo wer   t h e  o p er atio n   co m p le x ity   an d   b o o s t th r o u g h p u t w h ile  co n s u m in g   f ewe r   r eso u r ce s .   T h is   p ap er   p r esen ts   a  r eso u r ce - ef f icien t  NT T   h ar d war e   d esig n   with   a   b alan ce   o f   f r eq u en c y ,   laten cy ,   an d   p o wer .   I n   c o m p ar is o n   with   o th er   wo r k s   th at  h an d le  NT T   in   h ar d war e  im p lem en tatio n ,   we  wo u ld   lik e  to   p r o v e  o u r   ef f icien c y   u p o n   o u ts tan d in g   wo r k in g   f r eq u e n cy ,   im p r o v e d   tim in g   o p er atio n ,   an d   less   r eso u r ce   co s t  ( L UT   an d   FF )   lead in g   to   p o wer   o p tim izatio n .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4 7 52   In d o n esian   J   E lec   E n g   &   C o m p   Sci ,  Vo l.  3 8 ,   No .   2 ,  May   20 2 5 :   7 3 2 - 7 4 3   734   −   Pu r e  h ar d wa r e  im p lem e n tatio n   with   b alan ce d   b e n ef its :  W e  p r o p o s ed   a  p u r e  h ar d war e   ca p ab le  o f   h an d lin g   NT T   an d   I NT T   ( I n v e r s e  NT T )   o p e r atio n s   f o r   th e   C R YST AL S - Ky b er   PQC   alg o r ith m   with   a  b alan ce   o f   r eso u r ce s   an d   p er f o r m a n ce .   B y   o p tim izin g   th e   r eso u r ce s   o n   th e   FP GA  f o r   th e   p r o ce s s in g   u n its   an d   m an ag in g   th e  m e m o r y   ac ce s s   ef f icien tly ,   we  h av e  b ee n   ab le   to   r ed u ce   th e  o v er all  s ize  an d   m em o r y   u s ag e   with o u t slo win g   d o w n   th e  p e r f o r m an ce .   −   Stan d ar d   b en ch m a r k   f o r   f u t u r e  v er if icatio n :   B y   im p lem e n tin g   o n   b o th   FP GA  ( Xilin x   Ar t ix - 7 )   a n d   ASI C   ( T SMC   6 5 n m   tech n o lo g y ) ,   w e  o f f e r   o u r   d esig n   as  a  s tan d a r d   b e n ch m ar k   f o r   o th er   r esear ch er s   to   clea r ly   ev alu ate  th e  NT T   an d   I NT T   p ar ts   in   th eir   C R YSTA LS - Ky b er   h ar d war e   d esig n s .   T h is   aim s   to   an aly ze   th e   ad v an tag es  an d   d is ad v an tag e s   o f   ea ch   d esig n   r atio n ale  f o r   C R YST AL S - Ky b er   h ar d wa r e,   wh ich   h elp s   d esig n er s   s o o n   d ete r m in e  an d   d ev elo p   t h e  m o s t su itab le  h ar d war e  d esig n   ap p r o ac h   o f   t h eir   o wn .   −   Ou ts tan d in g   p er f o r m a n ce   in   c o m p ar is o n   to   p r ev i o u s   s tu d ies:   Ou r   r esu lts   o n   Xilin x   Ar tix - 7   m ad e  u s e  o f   th e  DSPs   an d   B R A Ms  o f   th e  FP GA  s o   th at  th e  n u m b er   o f   L UT s   an d   FF s   lo g ic  was  s m al l  in   co m p ar is o n   to   [ 9 ] ,   [ 6 ] ,   an d   th e  co m p u tati o n   tim e  was  r ed u ce d   co m p ar ed   to   [ 4 ] ,   [ 1 1 ] .   B y   u tili zin g   e f f icien t  m em o r y   ac ce s s ,   o u r   ASI C   r esu lts   o u tp er f o r m e d   o th e r   NT T   h ar d war e  d esig n s   in   [ 6 ] ,   [ 7 ] .   T h e  r em ain d er   o f   th is   p ap er   is   o r g an ized   as f o llo ws:     −   Sectio n   2   ex p lain s   th e  m ath e m atica l  f o u n d atio n s   o f   th e  NT T   an d   I NT T   alg o r ith m s   in   C R YSTA L S - Ky b e r ,   wh ich   co n tain s   a  n u m b e r   o f   al g o r ith m s   in   p s eu d o co d e  f o r m s   an d   th eir   d escr ip tio n s   in   d etail.     −   I n   Sectio n   3 ,   we  d escr ib e  o u r   s tr ateg y   f o r   h ar d war e  d esig n   an d   th e  o v e r all  m o d u le  ar c h itectu r e,   wh er e  m ajo r   co m p o n e n ts   ar e  d e p ic ted ,   in clu d i n g   th e   p o ly n o m i al  m u ltip licatio n s ,   b u tter f l y   u n its ,   m em o r y   ad d r ess   co n tr o ls   an d   th e  o v er a ll d esig n   co n tain in g   th em .     −   T h e  f in d in g s   an d   co m p ar is o n s   with   o th er   d esig n s   ar e  an al y ze d   in   Sectio n   4 .   Mo s t  o f   th e  r esu lts   wer e   o b tain ed   f r o m   th e   s y n th esis   an d   im p lem en tatio n   p r o ce s s es  s in ce   th e  d esig n   was  b ase d   o n   h a r d war e.   Par allel  im p lem en tatio n   o n   FP GA  an d   ASI C   w as   ex ec u ted   f o r   m u tu al  d is cu s s io n s   as  we ll  as  co m p ar is o n   to   o th er   wo r k   f o r   ef f icien cy .     −   T h e  co n clu s io n   o f   th is   wo r k   is   p r esen ted   in   th e  f in al  s ec tio n ,   wh er e  th e  s tu d y   is   s u m m ar ized ,   an d   s o m e   im p licatio n s   ca n   b e  s tated .       2.   B ACK G RO UND   2 . 1 .     NT T - ba s ed  po ly no m ia l m ultiplica t io n   E f f icien t  p o l y n o m ial  m u ltip licatio n ,   esp ec ially   f o r   lar g e   d e g r ee s ,   is   f u n d a m en tal  in   e n cr y p tio n   a n d   lattice - b ased   cr y p to g r a p h y   b u t   ca n   b e  tim e - co n s u m in g   th o u g h .   I n   Ky b er ,   p o ly n o m ials   ar e  d ef in ed   in   th e  r in g     ℤ [ ] / ( + 1 ) .  T h e  o p er atio n   tak es  p o ly n o m ials   ( ) = ∑ ( ) − 1 = 0   an d   ( ) = ∑ ( ) − 1 = 0   as  in p u ts   an d   r etu r n   th e  o u tp u t  p o ly n o m ia l  ( ) = ∑ ( ) − 1 = 0   as  m u ltip licatio n   o u tp u t.   As  u s u al,   th e  tech n iq u e  f o r   m u ltip ly in g   two   p o ly n o m ials   h as a   ( 2 )   co m p lex ity ,   wh ic h   lead s   to   s lo w  p r o ce s s in g   tim e  wh en   d ea lin g   with   lar g e - d eg r ee   p o ly n o m ials .   NT T   is   u s ed   to   s p ee d   u p   th is   o p er atio n   s in ce   NT T   p er f o r m s   it  with   ( .   )     co m p lex ity .   T h e  r esu ltan t  p o ly n o m ial  ( )   ca n   b e  f u r th er   r ed u ce d   with   n eg at iv e  wr ap p e d   co n v o lu tio n   tech n iq u e  s h o wn   with in   Alg o r ith m   1 ,   w h er ea s ,   th e  r ed u ctio n   p o ly n o m ial,   ( ) = ( + 1 )   an d   ≡ 1   (    2 ) .  T h is   tech n iq u e  h en ce   d ir ec tly   r ed u ce s   th e  d eg r ee   o f   th e  r esu ltin g   p o ly n o m ial   ( )   to   d eg r ee   − 1 ,   wh ich   is   ac co m p lis h ed   b y   m u ltip ly in g   t h e  co ef f icien ts   o f   th e  in p u t a n d   o u tp u t p o ly n o m ials   b y   th e  p o wer   o f         an d   − 1   ,   r esp ec tiv ely ,   wh er e    is   a   p r im itiv e  2 - th   r o o t  o f   u n ity   in     s atis f y in g   2 ≡ 1 (    )   an d   ∀ < 2 ,  ≠ 1   (    ) ,   wh en   ≡ 1   (    2 )   [ 1 8 ] .     Alg o r ith m   1 .   NT T - b ased   Po ly n o m ial  Mu ltip licatio n   with   n e g ativ e  wr ap p e d   co n v o lu tio n   ( NW T )   [ 1 6 ]     Input:   ( ) , ( ) ∈ [ ] / ( + 1 )   Input:   Primitive   2 - th root of unity  ∈   Output:   ( ) = ( ) × ( ) , ( ) ∈ [ ] / ( + 1 )   1   ̂ = ( 0 , 1 , . . . , − 1 ) ⊙ ( 1 , 1 , 2 , . . . , − 1 )   2   ̂ = ( 0 , 1 , . . . , − 1 ) ⊙ ( 1 , 1 , 2 , . . . , − 1 )   3   ̅ =  ( ̂ )   4   ̅ =  ( ̂ )   5   ̅ = ̅ ⊙ ̅   6   ̂ =  ( ̅ )   7   ( ) = ( ̂ 0 , ̂ 1 , . . . , ̂ − 1 ) ⊙ ( 1 , − 1 , − 2 , . . . , − ( − 1 ) )   8   return   ( )     2 . 2 .    Num ber  t heo re t ic  t ra ns f o rm a t io n   A n   ( − 1 )   d eg r ee   p o ly n o m ial  ( ) = ∑ − 1 = 0   is   tr an s f o r m ed   in to   NT T   d o m a in   as  ̅ ( ) = ∑ − 1 = 0   b y   u s in g   a   n - p t  f o r war d   N T T   o p e r atio n .   T h e   co ef f icien t  o f   ̅ ( )   in   NT T   d o m ai n   is   = Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2 5 0 2 - 4 7 52       A n   efficien t h a r d w a r e  imp leme n ta tio n   o f  n u mb er th eo r etic  t r a n s fo r m  fo r   … ( Tr a n g   Ho a n g )   735   ∑  − 1 = 0   o v er     ℤ   f o r   = 0 , 1 , . . . , − 1 .  Af ter   p o in twis e  m u ltip ly in g   ̅ ( )   an d   ̅ ( )   in   NT T   d o m ai n ,   a n   n - p o in t  I NNT   is   u s ed   to   tr an s f o r m   th e  r esu lt  b ac k   to   th e  p o ly n o m ial  d o m ain   with     = − 1 ∑ −  − 1 = 0   in   ℤ .  Mo r eo v er ,   NT T   an d   I NT T   r e g u lar ly   u s e  th e   twid d le  f ac t o r ,   ∈ ℤ   an d   its   m o d u lar   in v e r s e,   − 1 ∈ ℤ   as  in p u t.  I t  is   a  p r im itiv e  - th   r o o t  o f   u n ity   in   ℤ   an d   th e  co n d itio n s   ≡ 1   ( mod   )   an d   ∀ < , ≠   1   ( mod   ) ,   wh er e  ≡ 1   (    ) .   I n   th is   s tu d y ,   th e  iter ativ e   NT T   ( Alg o r ith m   2 )   an d   I N NT   ( Alg o r ith m   3 ) ,   wh ich   u tili ze   th e  Gen tlem an - San d e  b u tter f ly   p h en o m e n o n ,   wer e  ap p lied .   T h e  NT T   an d   I NT T   alg o r it h m s   tr an s f o r m   th e  p o ly n o m ial  f r o m   n o r m al  o r d e r   to   b it - r e v er s ed   o r d er   a n d   v i c e  v er s a.   T h e  b it - r ev er s al  o p er atio n   o n   ( − 1 ) - b it   in teg er   k ,   wh e r e  =         is   ex ec u ted   b y   th e    ( , − 1 )   o p er atio n   in   Alg o r ith m   3   [ 1 8 ] .   I n   a d d itio n ,   th e   co ef f icien ts   o f   th e  o u tp u t  p o ly n o m ial  m u s t a lway s   b e  m u ltip lied   b y   ( 1 / )        in   th e  I NT T   o p e r atio n   s in ce   th e  b it  r e v er s io n ,   as  s h o wn   i n   s tep s   1 9 - 2 1   o f   Alg o r ith m   3 .   Alg o r ith m   2   ca n   also   b e   f u r th er   m o d if ie d   to   im p lem en t  th e  I NT T   o p e r atio n   b y   s u b s titu tin g     with   − 1   an d   h av in g   t h e  o u tp u t  p o ly n o m ial   co ef f icien ts   d iv id ed   b y    in   .     Alg o r ith m   2 .   I ter ativ e  NT T   Al g o r ith m   [ 1 4 ]   Input:  ( ) ∈ [ ] / ( + 1 )   in normal order   Input:  ∈ , = 2   Output:  ̅ ( ) =  ( ) ∈ [ ] / ( + 1 )   in bit - reversed order   1   f or     from 1 by 1 to    do   2   |       = 2 −   3   |       for     from 0 by 1 to  2 − 1 − 1   do   4   |      |       for     from 0 by 1 to  − 1   do   5   |      |      |      ← 2 ∙ ∙ +                     6   |      |      |      ← 2 ∙ ∙ + +   7   |      |      |      ← 2 − 1 ∙   8   |      |      |      ← [ ]   9   |      |      |      ← [ ]   10   |      |      |      ←         11   |      |      |      ← ( + )        12   |      |      |      ← ( − ) ∙        13   |      |      |      [ ] ←   14   |      |      |     [ ] ←   15   |      |       end   for     16   |       end   for   17   end   for   18   return       Alg o r ith m   3 .   I ter ativ e  I NT T   Alg o r ith m   [ 1 4 ]   Input:  ̅ ( ) ∈ [ ] / ( + 1 )   in bit - reversed order   Input:  − 1 ∈ , = 2   Output:  ( ) =  ( ) ∈ [ ] / ( + 1 )   in normal order   1   = 1   2     =   3   while   > 1   do   4   |      for     from 0 by 1 to  − 1   do   5   |      |        = 0     6   |      |       for     from    by  2 ∙   to  ( − 2 )   do   7   |      |      |       ← [ ]                     8   |      |      |       ← [ + ]   9   |      |      |       ← ( + )        10   |      |      |       ← ( − ) ∙ −  ( , − 1 )        11   |      |      |       [ ] ←   12   |      |      |       [ + ] ←   13   |      |      |       = + 1   14   |      |       end   for      15   |      end   for   16   |         = 2 ∙   17   |           = / 2   18   end   while   19   for     from 0 by 1 to  − 1   do            20   |         [ ] ← [ ] ∙ ( 1 / )   (    )   21   end   for       22   return         Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4 7 52   In d o n esian   J   E lec   E n g   &   C o m p   Sci ,  Vo l.  3 8 ,   No .   2 ,  May   20 2 5 :   7 3 2 - 7 4 3   736   3.   DE S I G N  RAT I O NA L E   I n   th is   s ec tio n ,   o u r   h ar d war e  d esig n   ap p r o ac h   a n d   th e   o v er all  ar ch itectu r e  o f   th e  m ain   m o d u les  ar e   g iv en .   As  d escr ib ed   i n   Sectio n   3 . 1 ,   th e   m u ltip lier   u s in g   M o n tg o m e r y ' s   m o d u lar   alg o r ith m   at  th e   wo r d   lev el   p er f o r m s   th e  m o d u lar   m u ltip l icatio n   in   o u r   h ar d war e .   T h e  p r im ar y   ar ith m e tic  o p e r atio n   in   NT T   an d   I NT T   alg o r ith m s   is   th e  b u tter f ly   o p e r atio n ;  W e  d escr ib e  o u r   p r o ce s s in g   elem en ts   h ar d war e  with   th e  b u tter f l y   u n it  in   Sectio n   3 . 2 .   I n   Sectio n   3 . 3 ,   o u r   ef f icien t  m e m o r y   an d   its   a d d r ess   g en er ato r   ar e  g i v en ,   w h ich   en h a n ce s   th e  p er f o r m an ce   o f   o u r   d esig n .   Sectio n   3 . 4   d escr ib es  th e  o v er all  s tr u ctu r e.   T h e  p r o p o s ed   ar ch itectu r e  ca n   b e  im p lem en ted   u s in g   eith er   FP GA  o r   ASI C   tech n o lo g y .     3 . 1 .     NT T - ba s ed  po ly no m ia l m ultiplica t io n   Mo d u lar   m u ltip lier   is   o n e  o f   th e  m o s t  ess en tial  co m p o n en t s   in   NT T   s y s tem .   T h e  af o r e m en tio n ed   co m p o n en t  in v o l v es  two   d if f er en t  b lo ck s :  a  DSP - b ased   in teg er   m u ltip licatio n   u n it   an d   a  wo r d - lev el   Mo n tg o m er y   m o d u lar   r ed u ctio n   u n it.  B o th   b lo c k s   ar e  in d e p en d en t  o f   th e  o th er .   T h e  Mo n tg o m er y   [ 1 8 ]   an d   B ar r ett  alg o r ith m s   [ 6 ]   a r e  th e  m o s t c o m m o n   o n es u s ed   in   m o d u lar   r e d u ctio n ,   an d   th ey   ar e   d esig n ed   to   ac h iev e  ef f icien cy .   Fo r   th is   d esig n ,   we  d ec id ed   to   b u ild   a  Mo n tg o m e r y   r ed u ctio n   u n it,  s in ce   th e  alg o r ith m   u s es  f ewe r   co m p o n en ts ,   an d   p r o ce s s es  th r o u g h   f ewe r   s tag es  in   co m p ar is o n   to   B ar r ett’ s ;  th er ef o r e,   it  ca n   b e  h ar d war e   im p lem en ted   in to   s m aller   d esig n s   in   ter m s   o f   ar ea ,   as  well  a s   ca n   wo r k   in   lar g er   f r eq u en ci es.  T h e  u n it  h en ce   ca n   b e   u s ed   f o r   th e  w o r d - lev el  Mo n tg o m e r y   m o d u lar   r ed u ctio n   o p er atio n   f o r   m o d u lu s - s atis f y in g     ≡ 1   (    2 ) .   As  s h o wn   in   Fig u r e  1 ,   th e   DSP  u n it  o f   th e  FP GA  is   u tili z ed   f o r   t h e  in teg er   m u ltip lier   u n it  to   cu t   d o wn   o n   th e  n u m b er   o f   L UT s   an d   FF s .   Mo r eo v er ,   th e  in teg e r   m u ltip licatio n   u n it  th at  h as  b ee n   p r o p o s ed   u s ed   p ip elin in g   tech n iq u e  to   en s u r e  th at  th e  p r o d u ct  o f   th e  m u ltip licatio n   is   s y n ch r o n ized   wi th   th e  s y s tem .   T h e  o u tp u t  o f   th e   m u ltip lier ,   h o w ev er ,   n ee d s   to   h a v e  its   b it  len g th   b r o u g h t  d o wn   to   m atch   t h at  o f   t h e  m o d u lu s ,   wh ich   we  ca ll  th e  r ed u ctio n   o p er atio n .   T h e  Mo n t g o m er y   m o d u lar   wo r d - lev el  alg o r ith m   o f   th at  o p er atio n   is   p r o v id e d   in   Alg o r ith m   4 .   An y   NT T   p r im e  ,   p o s s ess in g   th e  ≡ 1   (    2 )   p r o p er t y   wh en   th e  n e g ativ e  wr ap p ed   c o n v o lu tio n   m eth o d   is   ap p lied ,   ca n   b e  wr itten   as  = ∙ 2 + 1 ;  an d   b y   h ar n ess in g   th is   p r o p er t y ,   a  Mo n tg o m er y   r ed u ctio n   o p e r atio n   ca n   b e  p er f o r m ed   at  th e   wo r d   lev el  with   th e  wo r d   s ize  = ( 2 ) .   T h is   p r o p er t y   allo ws  th e  r ed u ctio n   o p er atio n   to   b e  h an d le d   in   m u ltip le  s tag es,  r ath er   th an   r u n n i n g   it  all  at  o n ce .   T o  p er f o r m   th e   m o d u lar   r e d u cti o n   o p er atio n   o n   a  - b it  m o d u lu s ,   = /   iter atio n s   ar e  also   r eq u i r ed .   T h e   Mo n tg o m er y   m o d u lar   r ed u ct io n   co n s tan t,  wh ic h   was  p r e v io u s ly   wr itten   as  = − − 1      2 ) ,   is   n o w   wr itten   as  − 1      2 .   T h is   ch a n g e   m ak e s   it  p o s s ib le  to   u s e  a   s im p le   two ’ s   co m p lem en t  o p er atio n   in s tead   o f   a   m u ltip licatio n   o p er atio n   ∙ ∙   (    2 )   in   th e  Mo n tg o m er y   s ch em e,   a s   d em o n s tr ated   i n   Step   6   o f   Alg o r ith m   4 .   I n   ea ch   NT T   c o m p o n e n t  o f   C R YSTA L S - Ky b er ,   a  f ix e d   m o d u lu s   = 3329   is   u s ed   [ 1 9 ] ,   wh ile   th e  p ar am eter s     = 128   an d   = 12 ,    ca n   b e  wr itten   as  ∙ 2 8 + 1 ,   with   wo r d   s ize  = 8 .   So ,   we  n ee d   = 12 / 8 = 2   iter atio n s   f o r   th e   alg o r ith m   t o   wo r k .   − 1   ca n   b e  ca lcu lated   a s   − 1 = 2 = 13 2 = 169   in   C R Y STAL S - Ky b er .           Fig u r e  1 .  12 - b it  m o n tg o m er y   m o d u lar   m u ltip lier       Alg o r ith m   4 .   W o r d - L e v el  Mo n tg o m er y   R ed u ctio n   Alg o r ith m   f o r   NT T - f r ien d ly   m o d u lu s   [ 2 0 ]   [ 2 1 ]   I np ut:   = ∙   ( a  2 - b it p o s itiv e  in teg er )   I np ut:     ( a  - b it m o d u l u s ) ,   = ∙ 2 + 1   I np ut:   = ( 2 )     ( wo r d   s ize)   O utput :    = ∙ − 1   (    )   wh er e  = 2 ∙   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2 5 0 2 - 4 7 52       A n   efficien t h a r d w a r e  imp leme n ta tio n   o f  n u mb er th eo r etic  t r a n s fo r m  fo r   … ( Tr a n g   Ho a n g )   737   1   ← /   2   ←   3   f o r     f r o m   0   to     do   4   |          1 ← > >   5   |          1 ←   (    2 )     6   |          2 ←  ′           1   7   |           ← 2 [ − 1 ]   ∨   1 [ − 1 ]         8   |          ← 1 + ( ∙   2 [ − 1 : 0 ] ) +    9   end   f o r     10   4 ← −   11   if   ( 4 < 0 )   t hen    =   else    = 4   12   r etu r n        As  ca n   b e  s ee n   in   S tep   8   o f   Alg o r ith m   4 ,   th e  wo r d - lev el  M o n tg o m e r y   m o d u lar   r ed u ctio n   alg o r ith m   m ak es  u s e  o f   a  n u m b e r   o f   m u ltip ly   an d   ac cu m u late  ( M AC )   o p er atio n   u n it s ,   wh ich   is   r esp o n s ib le  f o r   p er f o r m in g   th e  X  · Y  +Z +Cin   o p er atio n .   Fig u r e  2   d ep icts   th e  h ar d war e  ar ch itectu r e  th at  wa s   d ev elo p ed   f o r   th e   wo r d - lev el  Mo n tg o m er y   m o d u lar   r ed u ctio n   alg o r ith m .   T h is   ar ch itectu r e  in clu d es two   Mo d u lo   R ed u ctio n   s u b - b lo ck s .   T h e  f ir s t  Mo d u lo   R e d u ctio n   s u b - b lo ck   p e r f o r m s   a  r ed u ctio n   th at  tak es  th e  2 4 - b it  in p u t  d ata  P  an d   tr an s f o r m s   it  i n to   th e   1 6 - b it  i n ter m ed iate  d ata   P _ r ed [ 1 ] .   Af te r   th at,   th e  d ata  is   r e d u ce d   b y   t h e  s ec o n d   Mo d u lo   R ed u ctio n   s u b - b lo ck   f o r   a   s ec o n d   tim e  in   o r d er   to   o b tain   th e  1 4 - b it  d ata   P _ r ed [ 2 ] .   B y   u tili zin g   a  s u b tr ac to r   an d   a  m u ltip lex e r ,   th e  m o d u l ar   v alu e  o f   P _ r ed [ 2 ]   is   o b tain ed ,   wh ich   is   also   th e  o u tp u t  o f   th e   Mo n tg o m er y   m o d u lar   r ed u ctio n   alg o r ith m   a t th e  wo r d   lev el.   T o   b e  m o r e  s p ec if ic,   t h e  Mo d u lo   R ed u ct io n   Su b ’ s   p r o p o s ed   h ar d war e  is   s h o wn   in   Fig u r e  2 ,   wh ich   is   th e  h ar d wa r e  im p lem e n tatio n   f o r   Step   4   to   Step   8   o f   Alg o r it h m   4 .   T h e  m - b it  in p u t d ata  T 1   is   d iv id ed   i n to   two   p ar ts :  T 2 L   =   T 1 [ 7 :0 ]   ( 8   last   b its )   an d   T 2 H_ t   =  T 1 [ m :8 ]   ( th e   r est)  d u e  to   th e   wo r d   s ize  w =8   o f   th e   Mo n tg o m er y   r e d u ctio n   alg o r ith m .   On e  a d d er   is   also   u s ed   to   ca lcu late  th e  m u lt  t,   ca r r y   t,  a n d   T 2 H   t,  th er e f o r e   th e  r ed u ctio n   r esu lt C   t c an   b e  o b tain ed .             Fig u r e  2 .  Mo d u lar   r ed u ctio n   s u b - u n it h ar d war e       3 . 2 .     B utt er f ly   un it   Af ter   we  h ad   co m p le ted   a n   ef f ec tiv e  im p lem en tatio n   f o r   th e   m o d u lar   ar ith m etic,   th e   co n s t r u ctio n   o f   th e  h ar d war e  f o r   th e  b u tter f ly   u n its   was  co n ce n tr ated .   T h ese  b u tter f ly   u n its   m ak e  u s e  o f   m o d u lar   o p er atio n s   an d   ar e   lo ca ted   with in   th e   PE s   ( p r o ce s s in g   elem e n ts ) .   T h e   b u tter f ly   o p er atio n   is   c o n d u cted   b y   th e   PEs,  ea ch   o f   wh ich   r ec eiv e s   o n e  twid d le  f ac to r   an d   two   co ef f icien ts   as  in p u ts .   E ac h   PE  th en   g en er ate s   two   r esu ltin g   co ef f icien ts ,   wh ich   ar e   r ef e r r ed   to   as  th e   o d d   ( O)   a n d   ev e n   ( E )   co e f f icien ts ,   as  o u tp u ts .   As  ca n   b e  s ee n   in   Fig u r e  3 ,   th e   p r o p o s ed   PE  m o d u le  to   im p lem en t  th e   b u tter f ly   o p e r atio n   co n s is ts   o f   o n e  m o d u lar   a d d er ,   o n e   m o d u lar   s u b tr ac to r ,   a n d   o n e   m o d u lar   m u ltip lier .   I n   ea ch   P E ,   th r ee   d u al - p o r t   B R AM s   ar e  u s ed   f o r   n ec ess ar y   d ata  s to r a g e .   On e  o f   th em   is   ca lled   th e  twid d le  f ac to r   B R A M  ( T W   B R AM ) ,   wh ile   th e  o th er   two   ar e  ca lled   th e   in p u t a n d   in ter m ed iate  c o ef f ic ien t BR AM   ( b o th   ar e  ca lled   D AT A  B R A M) .     T h e   ev en   co ef f icien t  o u tp u t  o f   th e  PE  is   th e  o u tp u t  o f   th e  m o d u lar   a d d er ,   wh ile  th e  o d d   co ef f icien t  o u tp u t  o f   t h e  PE  is   th e   o u t p u t  o f   th e   m o d u lar   s u b tr ac to r   an d   m u ltip lier ,   as  s h o wn   in   s tep s   11 - 1 2   o f   Alg o r ith m   2 .   T o   m ain tain   s y n c h r o n izati o n   b etwe en   th e  o u tp u t   o f   th e   o d d   an d   e v en   co ef f icien ts ,   ad d itio n al  f lip - f l o p s   wer e  in s er ted   at  th e  m o d u lar   a d d er   h ar d war e  o u tp u t.  Fo r   a n   - p o in t  NT T   o p er atio n ,   th e   m a x im u m   n u m b e r   o f   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4 7 52   In d o n esian   J   E lec   E n g   &   C o m p   Sci ,  Vo l.  3 8 ,   No .   2 ,  May   20 2 5 :   7 3 2 - 7 4 3   738   p r o ce s s in g   u n its   th at  ca n   b e  i n clu d ed   in   th e   d esig n   is   eq u al   to   / 2 ,   an d   t h e  n u m b er   o f   p r o ce s s in g   u n its   m u s t  b e  a  p o wer   o f   2 .   I n   th e  d esig n   th at  we  h av e  p r o p o s ed ,   we  m ak e  u s e  o f   2   PEs,  wh ich   in d icate s   th at  th e  NT T   o p er atio n   is   ca r r ied   o u t  th r o u g h   two   b u tter f ly   u n its .   T h e  wh o le  h ar d wa r e  d esig n   f o r   a   ty p ical  PE,   wh ich   co n tain s   a  b u tter f l y   u n it,  is   d e m o n s tr ated   in   Fig u r e  3 .   B y   ass ig n in g   th e  v alu e  0   to   th e  in p u t  s ig n al  in 0 ,   t h e  f ir s t  m u ltip lican d   to   th e  in p u t  s ig n al  i n 1 ,   an d   th e   s ec o n d   m u ltip lican d   to   th e  in p u t  s ig n al  in   m u lt,  it  is   p o s s i b le  to   u tili ze   th e  b u tter f ly   h ar d war e  to   h an d le  a   m o d u lar   m u ltip l icatio n   o p e r atio n ,   as  illu s tr ated   in   Fig u r e  3 .   Her e,   we  r ef er r ed   to   th e  2 - in p u t  b u tter f ly   u n it  as   an   NT T 2   u n it.  T o   c o m p u te   th e  m o d u lar   a d d itio n   an d   s u b tr ac tio n   o f   th e   two   d ata   s ets,  th e  NT T 2   u n it   p r o ce s s es  two   s ets   o f   1 2 - b it  in p u t  d ata  ca lled   in 0   an d   in 1 .   T h e  m o d u la r   s u m   is   s y n ch r o n iz ed   af ter   it  is   p ass ed   th r o u g h   a  s h if t  r eg is ter ,  an d   t h en   th e  v alu e  is   u s ed   as  th e   ev en   in d e x   o u tp u t  o f   th e   NT T 2   d ev ice.   F o r   th e   m o d u lar   m u ltip lier   u n it  to   p r o d u ce   th e  1 2 - b it  o u tp u t  d ata  MO Do u t,  its   in p u ts   co n s is t  o f   th e  r esu lt  o f   th e   m o d u lar   s u b tr ac tio n ,   th e   m o d u lo   ,   an d   th e   in p u t  d ata  MU L in ,   an d   o n e  DFF is   u s ed   to   s y n ch r o n ize  th is   s ig n al  to   o b tain   th e   o d d   in d e x   o u t p u t  o f   th e  NT T 2 .           Fig u r e  3 .   Pro ce s s in g   E lem e n t  an d   B u tter f ly   Un it h a r d war e       3 . 3 .     M emo ry   a cc ess   a nd   a dd re s s   g ener a t o r   I n   C R YSTA L S - Ky b er ’ s   NT T   &   I NT T   h ar d wa r e,   ac ce s s in g   th e  m em o r y   n ee d s   to   b e  im p lem en ted   well  an d   o r d er l y   to   av o i d   b o ttl en ec k   p r o b lem s   [ 2 2 ] – [ 2 5 ] .   T h e  I ter ativ e  NT T ,   wh ich   is   illu s tr ated   in   Alg o r ith m   2 ,   co n s is ts   o f     s tag es,  an d   th er e  ar e   / 2   b u tter f ly   o p er atio n s   u s ed   in   ea ch   s tag e.   Ad d itio n ally ,   th e  r ea d   ad d r ess   p atter n   f o r   th e  in p u t   co ef f icien ts   v ar ies  f r o m   s tag e  to   s tag e.   T h e  ca lcu latio n   o f   th e  in d ex   o cc u r s   b etwe en   Step s   5   an d   6   o f   Alg o r ith m   2   in   th e  NT T   p r o c ess in g   f lo w.   T o   h av e  co n tr o l  o v er   th e  B R AM s   p r esen tin g   i n   ea ch   PE,   a n   a d d r ess   g en er ato r   is   r eq u i r ed .   T h is   u n it  g r an ts   th e   NT T   b lo ck   th e   ab ilit y   to   r ea d   th e   in p u t  c o ef f icien ts   f o r   th e  p r o ce s s   o f   th e   cu r r en t  NT T   s tag e,   an d   it  also   g r a n ts   th e  NT T   b lo ck   th e   ab ilit y   t o   s to r e  th e  o u tp u t  c o ef f icien ts   i n   th e  a p p r o p r iate  in d ex   o r d e r   f o r   th e   s u b s eq u e n t  NT T   s tag e s .   T h e  s tate  d iag r am   f o r   th e   ad d r ess   g en er ato r   ca n   b e  s ee n   in   Fig u r e   4 ,   w h ich   is   a  f in ite - s tate  m ac h in e,   s u it ab le  f o r   h ar d war e   im p lem en tatio n .   T h er e  ar e   th r ee   s tates  in   th e   ad d r ess   g en er at or :  I DL E ,   NT T ,   an d   W AI T   s tate.   I n   NT T   s tate,   r ea d   ad d r ess es  f o r   th e   in p u t  c o ef f i cien ts   an d   th e  c o r r esp o n d in g   twid d le  f ac to r ,   ,   ar e  g en er ate d   f o r   th e  PEs  to   p er f o r m   NT T   p r o ce s s in g .   T h e   wr ite  ad d r ess es  ar e  also   g en er ated   to   s to r e  th e  NT T   o u tp u t   co ef f icie n ts   in   th e   B R AM s ,   th ese  co ef f icien ts   ar e  th en   u s ed   as  in p u ts   f o r   th e  n ex t  NT T   s tag e.   T h er e  ar e  7   s tag es  in   a  1 2 8 - p t  NT T ,   s o   th e  NT T   s tate  ( STA T E   1 )   is   iter ated   7   tim es  to   g et  th e  f in al  NT T   r esu lt,  as  s h o wn   in   Step   1   o f   Alg o r ith m   2 .   T h e   s tates  b etwe en   th ese   NT T   s tates  ar e  ca lled   W AI T   s tates.  T h ese  s tates   s ta r t  af ter   c o m p letin g   th e  g en er atio n   o f   th e  r ea d   ad d r ess es  an d   en d   wh en   all  th e  o u tp u t  co ef f icien ts   ar e  s to r ed   in   th e  B R AM s   with   th e  g en er ated   wr ite  ad d r ess es.  T h e  n ex t  NT T   s tag e  p r o ce s s   ca n   s tar t  o n ly   if   t h e  cu r r en t  W AI T   s tate  f in is h es.   Af ter   7   W AI T   s tates,  wh ich   co r r esp o n d   to   7   r esp ec tiv e  NT T   s tates,  th e  s y s tem   ca n   tr a n s it  f r o m   th e  f in a l   W AI T   s tate  b ac k   to   I DL E   s tate  f o r   th e   n ex t N T T   p r o ce s s .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2 5 0 2 - 4 7 52       A n   efficien t h a r d w a r e  imp leme n ta tio n   o f  n u mb er th eo r etic  t r a n s fo r m  fo r   … ( Tr a n g   Ho a n g )   739       Fig u r e  4 .   Ad d r ess   Gen er ato r   s tate  d iag r am       3 . 4 .     O v er a ll desi g n   Du e  to   th e   p r o p er t y   th at   an   - p t  NT T   o p er atio n   ca n   b e   im p lem en ted   b y   two   ( / 2 ) - p t  NT T   o p er atio n ,   we  ca n   im p lem e n t  C R YSTA L S - Ky b er ’ s   2 5 6 - p t   NT T   o p er atio n   b y   u s in g   tw o   s ep ar ated   class ic  128 - p t  NT T ,   o f   wh ich   alg o r it h m   is   s h o wn   in   Alg o r ith m   2   ( Fig u r e  5 ) .   T h ese  two   NT T s   w ill  g ath er   th eir   d ata   allo ca ted   in   th e  B R A MS,   wh er e  d ata  in   an d   o u t  o f   th e   NT T   b lo ck   ar e  s to r ed .   An   ad d r e s s   g en er ato r   is   also   r eq u ir ed   to   in s tr u ct  th e  B R AM S to   o u tp u t t h e  co r r ec t in f o r m atio n   f o r   ea ch   NT T   r esp ec tiv el y .   B ef o r e  s tar tin g   th e  NT T /I NT T   o p er atio n ,   th e  h ar d war e  s to r es  twid d le  f ac to r s   ( f o r   NT T   o p er atio n ) ,   m o d u lar   in v er s e  twid d le  f ac to r s   ( f o r   I NNT   o p e r atio n ) ,   an d   t h e  in p u t   co ef f icien ts   in to   th e  B R AM s   o f   ea ch   PE.   T h e  twid d le  f ac to r   an d   its   m o d u lar   in v e r s e  v alu es  ar e  s to r ed   i n   2   B R AM ,   wh ile  th e  in p u t  co ef f icien ts   ar e   s to r ed   in   4   B R AM S:  2   B R A Ms  f o r   th e  f ir s t  PE  an d   2   B R AM s   f o r   th e  s ec o n d   PE.   Af ter   th e  NT T 2   o p er atio n ,   th e  o u t p u t  c o ef f icien ts   at   th e  cu r r en t   s tag e  ar e   th en   s to r ed   b ac k   to   th e   s am e  4   B R AM s   t o   b e   u s ed   as  in p u t   co ef f i cien ts   o f   t h e  n e x t  s tag e.   T h is   d ata  s to r in g   p r o ce s s   is   h an d led   at   th e  to p   lev el  u s in g   th e  g en e r ated   r ea d   an d   wr ite  ad d r ess es  f r o m   th e   a d d r ess   g en er ato r   as  m en tio n ed   ab o v e.   Af ter   f i n is h in g   7   NT T   s tag es,  th e  DOUT   B L OC K  u n it  wo u ld   s et  th e   d o n e  s ig n al  to   h ig h   t o   in d icate   t h e  co m p letio n   o f   NT T / I NT T   o p er atio n ,   w h ile  also   p ass in g   th e  o u tp u t  c o ef f icien ts   d ata  th r o u g h   th e   d o u t  s ig n al.   Fig u r e   5   s h o ws  o u r   p r o p o s ed   NT T   o v er all  d esig n   s tr u ctu r e.           Fig u r e  5 .   NT T   t o p   o v er all  ar c h itectu r e       4.   E XP E R I M E N T A L   RE SUL T S   AND   CO M P AR I SO N    4 . 1 .     E x perim ent a l scena rio   Ou r   h ar d war e  d esig n   was w r itten   in   Ver ilo g   Har d war e  Desc r ip tio n   L an g u ag e,   th e  m o s t c o m m o n   o n e   f o r   h ar d war e  im p lem en t at i o n   in   th e  m ea n tim e.   On   th e  o th er   h an d ,   o u r   d esig n   was  s y n th esized   an d   im p lem en ted   u s in g   Xilin x   Viv ad o   to o ls ,   o n   th e  Xilin x   A r tix - 7   FP GA  o f   n am e   x c 7 a1 2 tcp g 2 3 8 - 3 ,   s p ec if ically .   I n   p ar allel,   th e  d esig n   was  als o   s y n th esized   an d   p o s t - s y n th e s is   v er if ied   u s in g   Sy n o p s y s   D esig n   C o m p iler   an d   Sy n o p s y s   Fo r m ality   to o ls   with   th e  T SMC   6 5 n m   lib r ar y ,   as  a  m eth o d   f o r   co m p ar is o n .   T h e  NT T   s o f twar e  f o r   th e  r ef er e n ce   m o d el   was  wr itten   in   Py th o n   an d   b ased   o n   th e  NI ST  s u b m is s io n s ’   r e f er en c e  C   s o u r ce   co d e   o f   th e  C R YSTA L S Ky b er   d ev el o p in g   team .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4 7 52   In d o n esian   J   E lec   E n g   &   C o m p   Sci ,  Vo l.  3 8 ,   No .   2 ,  May   20 2 5 :   7 3 2 - 7 4 3   740   4. 2 .    E x perim ent a l scena rio   Ou r   p r o p o s ed   d esig n   was  s y n th esized   with   t h e  C R YST AL S - Ky b er   p a r am eter s   o f   q =3 3 2 9   an d   n =2 5 6 .   T h er e   wer e   2   P E s   u s ed   in   o u r   d esig n   an d   each   of   th o s e   h ad   2   b u tter f ly   u n its .   T h e   s y n th esis   r esu lt   u s in g   Sy n o p s y s   Desig n   C o m p iler   to o ls   with   T SMC   6 5 n m   te ch n o lo g y   lib r a r y   is   s h o wn   in   T ab le  1 .   On e  o f   th e  m o s t  cr u cial  an d   p r ec io u s   f ac to r s   o f   th e  s y n th esi ze d   d esig n   was  its   m ax im u m   f r eq u e n cy   to   wo r k   p r o p e r ly .   T h e   v alu e   o f   o u r   d esig n   was  ap p r o x i m ately   4 9 7   MH z,   wh ic h   o u t weig h s   m o s t  o f   th e   cr y p to s y s tem s   at   th e  cu r r en t  tim e.   T h e  v alu e  was  m ea s u r ed   b y   ch a n g in g   th e  f r eq u en c y   v alu e  in   th e  s d c   ( Sy n o p s y s   Desig n   C o n s tr ain ts )   f ile  an d   r e - r u n   th e   s y n th esis   p r o ce s s   u n til  we  g o t  th e  lar g e s t  v alu e  p o s s ib le  to   f u lf ill  th e  s etu p   an d   h o ld   co n s tr ain ts .   Me an wh ile,   o n   th e  a r ea   s id e,   th e  g ate  co u n t  v alu e  o f   o u r   d esig n   o n   th e   T SMC   6 5 n m   lib r ar y   was  ar o u n d   4 7 2 K   with   m o s t  o f   th e  u s ed   a r ea   f o r   n o n - co m b in ati o n al  lo g ic  ( 6 4 . 8 %),   wh ile  th e  co m b in atio n al  lo g ic  ac co u n ted   f o r   3 5 . 2 % o f   th e  t o tal  ar ea .   Fro m   an o th e r   p er s p ec tiv e,   T a b le  2   r ep o r ts   th e  s y n th esis   an d   im p lem e n tatio n   r esu lts   u s in g   Xilin x   Viv ad o   to o ls .   wh ich   r esu lted   in   an   ar ea - f r ien d l y   NT T   d esig n   with   a  r elativ ely   h ig h   f r eq u en cy   o f   1 0 2   MH z.   T h e  v alu e   was  m o d er ately   l o wer   th an   th e  v alu e  o f   4 9 7   MH z  m en tio n e d   a b o v e ,   wh ich   ca n   b e  e x p lain ed   b y   th e   f ac t  th at  th e  h ar d war e   o p tio n s   f o r   FP GA  ar e   m u ch   m o r e  h in d er ed   in   co m p ar is o n   t o   th at  f o r   ASI C .   I n   c o n tr ast,  th e  n u m b er   o f   L UT s   u s ed   in   th e  im p lem en tatio n   d esig n   was  m u ch   less   in   co m p ar is o n   to   th e  s y n th esis   d esig n ,   s in ce   th e  b etter   p h y s ical  o p ti m izatio n   an d   f u ll  im p lem e n ta tio n   wo r k   o f   th e   FP GA.   Ad d itio n ally ,   th e  d esig n   o n ly   u s ed   4 . 6 5 %  o f   th e  to tal  am o u n t  o f   u s ab le  r eg is ter   an d   th er e  was  n o   latch   g en er ated   in   o u r   d esig n .   T h is   ca n   b e  s ee n   as a n   o p tim is t r esu lt in   th e  ar ea   a n d   ti m in g   ef f ic ien cy       T ab le  1 .   Sy n t h esis   R esu lt o n   ASI C   Li b r a r y   TSM C 6 5 n m   F r e q u e n c y   ( M H z )   4 9 7   A r e a   ( µ m 2 )   To t a l   9 0 6 1 1 3 . 7 4 7 2   C o m b i n a t i o n a l   3 1 9 1 0 0 . 1 5 9 8   B u f / I n v   6 3 8 9 . 7 5 9 9 7   N o n c o m b i n a t i o n a l   5 8 7 0 1 3 . 5 8 7 4       T ab le  2 .   Sy n t h esis   an d   I m p le m en tatio n   r esu lts   o n   FP GA   D e si g n   S y n t h e si s   I mp l e me n t a t i o n   F r e q u e n c y   ( M H z )   1 0 2   1 0 2   R e s o u r c e s   LU T   8 7 2   8 5 7   R EG   7 4 4   7 4 4   D S P   6   6   B R A M   3   3       4 . 3 .   Co m pa riso n t o   prio r  wo rk   T ab le  3   an d   Fig u r e  6   co m p ar e   th e  r esu lts   in   o u r   wo r k   an d   p r ev io u s   wo r k s .   T h e  r elatio n s h i p   b etwe en   th e  n u m b er   o f   b u tter f l y   u n its   u s ed   in   th e  d esig n   an d   im p le m en tatio n   tim in g   r esu lts   ar e  s h o wn   in   T ab le  3   an d   Fig u r e  6 ( a) .   T h e  m o r e  b u tter f ly   u n its   th er e  wer e,   th e   m o r e   wo r k   was  s h ar ed   f o r   ea ch   b u tter f ly   u n it,  w h ich   h en ce   d e cr ea s ed   th e   NT T /I N T T   p r o ce s s in g   tim e  an d   in c r ea s ed   th e  m a x im u m   wo r k in g   f r eq u en cy   o f   th e  im p lem en tatio n   d esig n .   Usi n g   two   o f   th ese  u n its ,   it  ca n   b e  s ee n   th at  o u r   wo r k s   f ar   s u r p ass ed   [ 1 1 ] ,   wh ich   o n ly   h ad   o n e,   in   ter m s   o f   o p er atin g   f r eq u en c y   as we ll a s   laten cy .   Ou r   h ar d war e  d esig n ’ s   r eso u r ce   ef f icien cy   ca n   b e   af f ir m ed   b y   th e   co m p a r ativ e   an aly s is   o f   r eso u r ce   u tili za tio n   am o n g   th e   d esig n s   f ea tu r ed   in   T ab le  3   a n d     Fig u r e  6 ( b ) .   T h is   ac h iev em e n t  was  a  r esu lt  o f   th e   s tr ateg ic  o p tim izatio n   o f   FP GA  D SP   f o r   ca lc u latin g   o p er atio n s   an d   th e  r e d u ct io n   o f   n ec ess ar y   B R AM   b lo ck s   f o r   m em o r y   o n es.  R eg ar d i n g   th e  tim in g   an d   p er f o r m an ce ,   th e  m ax im u m   f r eq u en cy   o f   o u r   wo r k   was  1 0 2   MH z,   wh ich   is   r elativ ely   m e d iu m   co m p a r ed   to   o th er   wo r k   ( 5 9 ,   1 5 5 ,   an d   1 6 1   MH z) .   Ho wev er ,   b y   g en e r atin g   th e  r ea d   a n d   wr ite  ad d r ess   e f f icien tly   ac ce s s in g   th e  m em o r y ,   th e   laten cy   o f   o u r   d esig n   was  m u ch   s m aller   th an   o th e r   s tu d ies  in   [ 1 1 ] ,   [ 4 ] ,   an d   [ 6 ] ,   with   th e   r esp ec tiv e  f ig u r es b ei n g   6 . 8 6 ,   1 1 6 . 6 1 ,   1 1 . 8 3 ,   an d   3 . 1 8   m icr o s ec o n d s .     Ou r   ASI C   d esig n ,   as  s h o wn   in   T ab le  4 ,   b y   u tili zin g   c o h er en t   d esig n   s ch em es  an d   p ip elin in g ,   ac h iev ed   a  f r eq u e n cy   o f   4 9 7   MH z,   an d   f ar   s u r p ass ed   th e  NT T   h ar d war e  d esig n s   in   [ 6 ]   an d   [ 7 ] .   Ho wev er ,   th is   o p tim izatio n   ca m e  at  th e  co s t  o f   a  h ig h   g ate  co u n t  o f   4 7 2 K  s in ce   th e  tr ad e - o f f   b etwe en   ar ea   an d   tim in g   p r o p er ties .   Ou r   d esig n ’ s   ar c h itectu r e  th o u g h   r esu lted   in   a  r elativ ely   s m all  laten cy   o f   ju s t  6 8 6   an d   an   in s ig n if ican t  p r o ce s s in g   tim e  o f   1 . 3 8   m icr o s ec o n d s   f o r   t h e  NT T   o p er atio n .   T h is   laten cy   an d   o p er atio n   tim e   ar e  n o tab l y   lo wer   th an   o th er   wo r k s   s u ch   as  [ 6 ]   a n d   [ 7 ] ,   p r i m ar ily   d u e   to   o u r   well - p lan n e d   m em o r y   r ea d   a n d   wr ite  s ch em e  th at   em p lo y ed   th e  ad d r ess   g en er at o r   b lo ck .   D esp ite  o u r   d esig n ’ s   r elativ ely   s m all  laten cy   f o r   th e   NT T   o p er atio n ,   th at  s am e  v a lu e  was  lar g er   th an   th at  o f   [ 8 ]   ( 0 . 5   m icr o s ec o n d s ) ,   wh ich   was  ac h iev ed   b y   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esian   J   E lec  E n g   &   C o m p   Sci     I SS N:   2 5 0 2 - 4 7 52       A n   efficien t h a r d w a r e  imp leme n ta tio n   o f  n u mb er th eo r etic  t r a n s fo r m  fo r   … ( Tr a n g   Ho a n g )   741   u tili zin g   a  s ig n if ica n t  n u m b er   o f   r eso u r ce s   ( ar ea )   in   t h e  s y n th esized   d esig n .   Nev er th eles s ,   o u r   d esig n   s tr u ck   an   o v er all  b alan ce   b etwe en   ar ea   an d   tim in g   wh en   c o m p ar ed   to   o th er   wo r k s   b y   h a v in g   an   o u ts tan d i n g   p er f o r m an ce   o n   ASI C ,   with o u t  u s in g   u p   a  lar g e  n u m b e r   o f   r eso u r ce s ,   r en d e r in g   it  a  b r ig h ter   s o lu tio n   f o r   d esig n s   th at  o r ien t p e r f o r m an c e  o n   ASI C   p latf o r m .       T ab le  3 .   C o m p a r is o n   o f   im p le m en tatio n   r esu lts   f o r   NT T   d es ig n   ( q = 3 3 2 9 )   o n   FP GA   W o r k   [ 9 ]   [ 1 0 ]   [ 1 1 ]   [ 4 ]   [ 6 ]   O u r s   P l a t f o r m   Zy n q   7 0 0 0   V i r t e x   7   A r t i x   7   A r t i x   7   A r t i x   7   A r t i x   7   B u t t e r f l y   2   1   1   2   2   2   N TT/ I N TT  l a t e n c y   [ C C s]   1 9 3 5 / 1 9 3 0   4 3 7 5 6 / -   6 8 6 8 / 6 3 6 7   1 8 3 4 / -   5 1 2 / 5 7 6   6 8 6 / 8 4 2   F r e q   [ M H z ]   -   -   59   1 5 5   1 6 1   1 0 2   Ti me   [ u s]   -   -   1 1 6 . 6 1   1 1 . 8 3   3 . 1 8   6 . 8 6   LU Ts   2 9 0 8   4 1 7   -   -   1 7 3 7   5 8 7   FFs   1 7 0   4 6 2   -   -   1 1 6 7   7 4 4   D S P s   9   0   -   -   2   6   B R A M s   0   0   -   -   3   3         ( a)       ( b )     Fig u r e  6 .   C o m p a r is o n   o f   NT T   im p lem en tatio n   o n   FP GA  r eg ar d in g   ( a)   tim in g s   an d   ( b )   r eso u r ce s       T ab le  4 .   C o m p a r is o n   o f   s y n th esis   r esu lts   f o r   NT T   d esig n   ( q =3 3 2 9 )   ASI C   f lo w   W o r k   P l a t f o r m   n   q   N TT  l a t e n c y   ( C C s)   F r e q   ( M H z )   Ti me   ( u s)   G a t e   c o u n t   [ 6 ]   4 0 n m  C M O S   2 5 6   13   1 2 8 9   72   17   1 0 6 K   [ 8 ]   4 0 n m  C M O S   2 5 6   13   1 6 0   3 0 0   0 . 5   -   [ 7 ]   U M C   6 5   nm   2 5 6   13   2 0 5 6   25   82   1 4 K   O u r s   TSM C   6 5   nm   2 5 6   12   6 8 6   4 9 7   1 . 3 8   4 7 2 K       Evaluation Warning : The document was created with Spire.PDF for Python.