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 ha rd wa re impleme nta tion o 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 (KEM s)  o u o t h e   fin a li sts  in   th e   t h ir d   ro u n d   o t h e   Na ti o n a In stit u te  o S ta n d a rd 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 t h e o re ti c   tran sfo rm     (NTT wa u se d   t o   re d u c e   t h e   c o m p u tatio n a c o m p lex it y   o p o ly n o m ial   m u lt ip li c a ti o n ,   i h a a lwa y b e e n   a   c ru c ial  a rit h m e ti c   c o m p o n e n in   CRYST ALS - Ky b e d e sig n .   I n   t h i p a p e r,   a   sim p le   a n d   e fficie n a r c h it e c tu re   fo 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 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 we re   u ti li z e d   in   o u 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 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 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 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 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 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 o f   th 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 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) ,   c o m p etitio n   to   d eter m in 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 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 s er v es  as  th p r im ar y   o p er atio n ,   b u its   im p lem en tatio n   m ig h b co m p u tatio n ally   in ten s iv e,   ca u s in g   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 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   ty p ica 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 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 NT T - b ased   p o l y n o m ial  m u ltip licatio n   m eth o d ,   t h 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 a p p licab le   an d   ef f ec tiv 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 ac ce ler at o r s   is   o n o f   th m o s cr itical  f ac to r s   in   s elec tin g   an   o p tim al  h ar d war d esig n   a p p r o ac h   f o r   s ch em es.  Fo r   th p u r p o s o f   v alid atin g   th ef f i ca cy   o f   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 ex ec u te d   o n   v ar ie ty   o f   im p lem en tatio n   p latf o r m s .   Desp ite  th f ac t   th at  s o f twar e - im p lem en ted   d esig n s   p r o v id in tu itiv 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 imp leme n ta tio n   o n u mb er th eo r etic  t r a n s fo r 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 ] .   h y b r i d   d esig n   o f   s o f twar e   an d   h a r d war was  u s ed   to   im p r o v e   th p er f o r m an ce   wh ile  r etain in g   t h f lex i b ilit y   o f   th d esig n   with   s o f twar 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 f lex ib le  a n d   d esig n - tim e f f icien t,  th ey   d id   n o p r o v i d th e   s am lev el  o f   p er f o r m an ce   as  th p u r e   h ar d war d es ig n .   I n   c o n tr ast,  h ar d war im p lem en tatio n   is   ch ar ac ter ized   b y   th c o m p lex i ty   o f   its   alg o r ith m s   a n d   th la ck   o f   b asic  u n its   wr itten   in   h a r d war d escr ip ti o n   lan g u ag es,  p o s in g   ch alle n g to   d esig n er s   w h o   a r task ed   w ith   cr ea tin g   th 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 h ar d war im p lem en tatio n s   wo u ld   o f f er   d esig n er s   th b est   p er f o r m an ce .   T h h a r d war d esig n   e n co m p ass es  d iv er s 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 it  d if f icu lt  to   f air ly   co m p ar th 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 t h t wo   p r im ar y   ar c h itectu r es  u s ed   f o r   h a r d war 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 NI ST   r ec o m m e n d s   t h u s o f   Xilin x   Ar tix - FP GA  f o r   h ar d war im p lem e n tatio n   in   o r d er   to   co m p ar th d esig n   with   g r ea ter   p r ec is io n   [ 5 ] .   ASI C   r esu lts ,   o n   th o t h er   h a n d ,   ar h ig h l y   d ep en d e n o n   t h 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 d esig n s   to   o th er s ,   as th 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 t o   b an   im p o r ta n an d   wid ely   em p lo y ed   to o in   th f ield   o f   h ar d wa r 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 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   s in g le - p o r t   R AM - b ased   m em o r y   ar ch ite ctu r 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 ,   lo w - p o wer   an d   r eso u r ce - ef f icien NT T   ASI C   d esig n   was   p r esen ted   in   [ 7 ] .   Alth o u g h   th ar ea   an d   p o wer   r esu lts   wer g o o d ,   th d esig n   d id   n o 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 o f   th q u ic k est  an d   m o s en er g y - e f f icien NT T s   o n   ASI C ,   b u with   o p aq u r eso u r ce s ,   wh ich   co u l d   b in ter p r eted   as  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 co m p ar is o n s   o n   th FP GA  s id d id   n o 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 FP GA  f am ilie s   an d   th er wer 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,   tig h tly   c o u p le d   R I SC - 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 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 - NT T   c o r e   o n   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 im p lem en tatio n   p latf o r m   f o r   th 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 f r e q u en c y   r esu lts   f o r   [ 9 ]   an d   [ 1 0 ]   wer n u ll.  On   th o th er   h a n d ,   th d e s ig n er s   o m itted   th 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 th 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 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 to   th lar g 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 th d ig ital  s ig n al  p r o ce s s in g   ( DSP)  m o d u l in   th FP GA  f o r   in teg er   m u ltip lier   to   r e d u c th n u m b er   o f   L UT s   an d   D FF s   th at  m ig h b u s ed .   T h is   m ay   also   b alan ce   th FP GA  r eso u r ce s   to   co n s e r v 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 NT T   h ar d war d escr ib ed   in   [ 4 ]   u tili z ed   o n ly   o n 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   d esig n   with   h ig h   laten c y .   I n   s u m m ar y ,   at   th m o m en t ,   m o s s tu d ies  o n   NT T   h a r d war im p lem e n tatio n   h a v 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 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 FP GA  r eso u r ce   b y   in co r p o r atin g   th DSP  an d   B R AM   u n it,  wh ich   p r ev en ted   th ex ce s s iv e   u s 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 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 d esig n .   Sp ec if ically ,   th u s 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 B R AM s   p er   b u tter f ly   co r 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 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 o f   th m o s im p o r tan co m p o n e n ts   o f   th 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  s ig n i f ican i m p ac 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 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 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   r eso u r ce - ef f icien 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 im p lem en tatio n ,   we  wo u ld   lik to   p r o v 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 ( 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 h ar d wa r im p lem e n tatio n   with   b alan ce d   b e n ef its W p r o p o s ed   p u r 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 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   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 m e m o r y   ac ce s s   ef f icien tly ,   we  h av b ee n   ab le   to   r ed u ce   th 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 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 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 o f f e r   o u r   d esig n   as  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 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 an d   d ev elo p   t h m o s t su itab le  h ar d war 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 u s o f   th DSPs   an d   B R A Ms  o f   th FP GA  s o   th at  th n u m b er   o f   L UT s   an d   FF s   lo g ic  was  s m al in   co m p ar is o n   to   [ 9 ] ,   [ 6 ] ,   an d   th co m p u tati o n   tim 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 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 d esig n s   in   [ 6 ] ,   [ 7 ] .   T h 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 m ath e m atica f o u n d atio n s   o f   th 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   n u m b e r   o f   al g o r ith m s   in   p s eu d o co d 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 o u r   s tr ateg y   f o r   h ar d war d esig n   an d   th o v e r all  m o d u le  ar c h itectu r e,   wh er m ajo r   co m p o n e n ts   ar 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 o v er a ll d esig n   co n tain in g   th em .       T h 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 an al y ze d   in   Sectio n   4 .   Mo s o f   th 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 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 co n clu s io n   o f   th is   wo r k   is   p r esen ted   in   th f in al  s ec tio n ,   wh er th 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 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 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 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 d ef in ed   in   th r in g     [ ] / ( + 1 ) T h 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 o u tp u p o ly n o m ia ( ) = ( ) 1 = 0   as  m u ltip licatio n   o u tp u t.   As  u s u al,   th tech n iq u 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 p r o ce s s in g   tim 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 r esu ltan p o ly n o m ial  ( )   ca n   b f u r th er   r ed u ce d   with   n eg at iv wr ap p e d   co n v o lu tio n   tech n iq u s h o wn   with in   Alg o r ith m   1 ,   w h er ea s ,   th r ed u ctio n   p o ly n o m ial,   ( ) = ( + 1 )   an d   1   (    2 ) T h is   tech n iq u h en ce   d ir ec tly   r ed u ce s   th d eg r ee   o f   th 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 co ef f icien ts   o f   th in p u t a n d   o u tp u t p o ly n o m ials   b y   th p o wer   o f         an d   1   ,   r esp ec tiv ely ,   wh er   is   a   p r im itiv 2 - th   r o o 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 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 f o r war d   N T T   o p e r atio n .   T h e   co ef f icien 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 imp leme n ta tio n   o n u mb er th eo r etic  t r a n s fo r 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 m u ltip ly in g   ̅ ( )   an d   ̅ ( )   in   NT T   d o m ai n ,   a n   n - p o in I NNT   is   u s ed   to   tr an s f o r m   th r esu lt  b ac k   to   th 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 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 is   p r im itiv - th   r o o o f   u n ity   in     an d   th co n d itio n s   1   ( mod   )   an d   < ,   1   ( mod   ) ,   wh er 1   (    ) .   I n   th is   s tu d y ,   th 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 Gen tlem an - San d b u tter f ly   p h en o m e n o n ,   wer ap p lied .   T h NT T   an d   I NT T   alg o r it h m s   tr an s f o r m   th 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 v er s a.   T h b it - r ev er s al  o p er atio n   o n   ( 1 ) - b it   in teg er   k ,   wh e r =         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 o u tp u p o ly n o m ial  m u s t a lway s   b m u ltip lied   b y   ( 1 / )        in   th I NT T   o p e r atio n   s in ce   th 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 th 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 o u tp u p o ly n o m ial   co ef f icien ts   d iv id ed   b   in   .     Alg o r ith m   2 .   I ter ativ 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 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 RAT I O NA L E   I n   th is   s ec tio n ,   o u r   h ar d war d esig n   ap p r o ac h   a n d   th e   o v er all  ar ch itectu r o f   th 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 m o d u lar   m u ltip l icatio n   in   o u r   h ar d war e .   T h 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 b u tter f ly   o p e r atio n W d escr ib o u r   p r o ce s s in g   elem en ts   h ar d war with   th 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 m e m o r y   an d   its   a d d r ess   g en er ato r   ar g i v en ,   w h ich   en h a n ce s   th 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 o v er all  s tr u ctu r e.   T h p r o p o s ed   ar ch itectu r ca n   b 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 o f   th m o s ess en tial  co m p o n en t s   in   NT T   s y s tem .   T h af o r e m en tio n ed   co m p o n en in v o l v es  two   d if f er en b lo ck s DSP - b ased   in teg er   m u ltip licatio n   u n it   an d   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 in d e p en d en o f   th o th er .   T h Mo n tg o m er y   [ 1 8 ]   an d   B ar r ett  alg o r ith m s   [ 6 ]   a r th 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 ef f icien cy .   Fo r   th is   d esig n ,   we  d ec id ed   to   b u ild   Mo n tg o m e r y   r ed u ctio n   u n it,  s in ce   th 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 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 u n it  h en ce   ca n   b e   u s ed   f o r   th 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 1 ,   th e   DSP  u n it  o f   th FP GA  is   u tili z ed   f o r   t h in teg er   m u ltip lier   u n it  to   cu t   d o wn   o n   th n u m b er   o f   L UT s   an d   FF s .   Mo r eo v er ,   th 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 to   en s u r th at  th p r o d u ct  o f   th m u ltip licatio n   is   s y n ch r o n ized   wi th   th s y s tem .   T h o u tp u o f   th e   m u ltip lier ,   h o w ev er ,   n ee d s   to   h a v its   b it  len g th   b r o u g h d o wn   to   m atch   t h at  o f   t h m o d u lu s ,   wh ich   we  ca ll  th r ed u ctio n   o p er atio n .   T h 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 ,   p o s s ess in g   th 1   (    2 )   p r o p er t y   wh en   th n e g ativ wr ap p ed   c o n v o lu tio n   m eth o d   is   ap p lied ,   ca n   b wr itten   as  = 2 + 1 an d   b y   h ar n ess in g   th is   p r o p er t y ,   Mo n tg o m er y   r ed u ctio n   o p e r atio n   ca n   b p er f o r m ed   at  th e   wo r d   lev el  with   th wo r d   s ize  = ( 2 ) .   T h is   p r o p er t y   allo ws  th r ed u ctio n   o p er atio n   to   b 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 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   - b it  m o d u lu s ,   = /   iter atio n s   ar 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 a   s im p le   two s   co m p lem en o p er atio n   in s tead   o f   a   m u ltip licatio n   o p er atio n     (    2 )   in   th 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 o f   C R YSTA L S - Ky b er ,   f ix e d   m o d u lu s   = 3329   is   u s ed   [ 1 9 ] ,   wh ile   th p ar am eter s     = 128   an d   = 12   ca n   b 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 ca lcu lated   a s   1 = 2 = 13 2 = 169   in   C R Y STAL S - Ky b er .           Fig u r 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:   =   ( 2 - b it p o s itiv in teg er )   I np ut:     ( - 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 = 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 imp leme n ta tio n   o n u mb er th eo r etic  t r a n s fo r 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 s ee n   in   S tep   8   o f   Alg o r ith m   4 ,   th 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 o f   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 · +Z +Cin   o p er atio n .   Fig u r 2   d ep icts   th h ar d war ar ch itectu r 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 in clu d es two   Mo d u lo   R ed u ctio n   s u b - b lo ck s .   T h f ir s Mo d u lo   R e d u ctio n   s u b - b lo ck   p e r f o r m s   r ed u ctio n   th at  tak es  th 2 4 - b it  in p u d ata  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 d ata  is   r e d u ce d   b y   t h 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 in   o r d er   to   o b tain   th 1 4 - b it  d ata   P _ r ed [ 2 ] .   B y   u tili zin g   s u b tr ac to r   an d   m u ltip lex e r ,   th m o d u l ar   v alu o f   P _ r ed [ 2 ]   is   o b tain ed ,   wh ich   is   also   th o u tp u 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 wo r d   lev el.   T o   b m o r s p ec if ic,   t h Mo d u lo   R ed u ct io n   Su b s   p r o p o s ed   h ar d war is   s h o wn   in   Fig u r 2 ,   wh ich   is   th h ar d wa r 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 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 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 a d d er   is   also   u s ed   to   ca lcu late  th m u lt  t,   ca r r y   t,  a n d   T 2 H   t,  th er e f o r e   th r ed u ctio n   r esu lt C   t c an   b o b tain ed .             Fig u r 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 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 h ar d war f o r   th 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 u s 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 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 s ee n   in   Fig u r 3 ,   th e   p r o p o s ed   PE  m o d u le  to   im p lem en th e   b u tter f ly   o p e r atio n   co n s is ts   o f   o n 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 u s ed   f o r   n ec ess ar y   d ata  s to r a g e .   On o f   th em   is   ca lled   th twid d le  f ac to r   B R A ( T W   B R AM ) ,   wh ile   th o th er   two   ar 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 ca lled   D AT B R A M) .     T h e   ev en   co ef f icien o u tp u o f   th PE  is   th o u tp u o f   th m o d u lar   a d d er ,   wh ile  th o d d   co ef f icien o u tp u o f   t h PE  is   th e   o u t p u 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 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 in s er ted   at  th m o d u lar   a d d er   h ar d war o u tp u t.  Fo r   a n   - p o in 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 i n clu d ed   in   th e   d esig n   is   eq u al   to   / 2 ,   an d   t h n u m b er   o f   p r o ce s s in g   u n its   m u s b p o wer   o f   2 .   I n   th d esig n   th at  we  h av p r o p o s ed ,   we  m ak u s o f   2   PEs,  wh ich   in d icate s   th at  th NT T   o p er atio n   is   ca r r ied   o u th r o u g h   two   b u tter f ly   u n its .   T h wh o le  h ar d wa r d esig n   f o r   a   ty p ical  PE,   wh ich   co n tain s   b u tter f l y   u n it,  is   d e m o n s tr ated   in   Fig u r 3 .   B y   ass ig n in g   th v alu 0   to   th in p u s ig n al  in 0 ,   t h f ir s m u ltip lican d   to   th in p u s ig n al  i n 1 ,   an d   th e   s ec o n d   m u ltip lican d   to   th in p u s ig n al  in   m u lt,  it  is   p o s s i b le  to   u tili ze   th b u tter f ly   h ar d war 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 3 .   Her e,   we  r ef er r ed   to   th 2 - in p u 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 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 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 d ata  ca lled   in 0   an d   in 1 .   T h 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   s h if r eg is ter an d   t h en   th v alu is   u s ed   as  th e   ev en   in d e x   o u tp u 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 1 2 - b it  o u tp u d ata  MO Do u t,  its   in p u ts   co n s is o f   th 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 d ata  MU L in ,   an d   o n 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 o f   th NT T 2 .           Fig u r 3 .   Pro ce s s in g   E lem e n 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 m em o r y   n ee d s   to   b 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 I ter ativ 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 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 r ea d   ad d r ess   p atter n   f o r   th in p u t   co ef f icien ts   v ar ies  f r o m   s tag to   s tag e.   T h ca lcu latio n   o f   th 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 NT T   p r o c ess in g   f lo w.   T o   h av co n tr o o v er   th 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 c o ef f icien ts   f o r   th p r o ce s s   o f   th e   cu r r en NT T   s tag e,   an d   it  also   g r a n ts   th NT T   b lo ck   th e   ab ilit y   t o   s to r th o u tp u c o ef f icien ts   i n   th 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 NT T   s tag e s .   T h s tate  d iag r am   f o r   th e   ad d r ess   g en er ato r   ca n   b s ee n   in   Fig u r e   4 ,   w h ich   is   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 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 c o ef f i cien ts   an d   th c o r r esp o n d in g   twid d le  f ac to r ,   ,   ar g en er ate d   f o r   th 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 also   g en er ated   to   s to r th 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 th en   u s ed   as  in p u ts   f o r   th n ex NT T   s tag e.   T h er ar 7   s tag es  in   1 2 8 - p NT T ,   s o   th NT T   s tate  ( STA T E   1 )   is   iter ated   7   tim es  to   g et  th 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 ca lled   W AI T   s tates.  T h ese  s tates   s ta r af ter   c o m p letin g   th g en er atio n   o f   th r ea d   ad d r ess es  an d   en d   wh en   all  th o u tp u co ef f icien ts   ar s to r ed   in   th B R AM s   with   th g en er ated   wr ite  ad d r ess es.  T h n ex NT T   s tag p r o ce s s   ca n   s tar o n ly   if   t h cu r r en 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 NT T   s tates,  th s y s tem   ca n   tr a n s it  f r o m   th 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 imp leme n ta tio n   o n u mb er th eo r etic  t r a n s fo r fo r   … ( Tr a n g   Ho a n g )   739       Fig u r 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 to   th e   p r o p er t y   th at   an   - p NT T   o p er atio n   ca n   b e   im p lem en ted   b y   two   ( / 2 ) - p NT T   o p er atio n ,   we  ca n   im p lem e n 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 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 5 ) .   T h ese  two   NT T s   w ill  g ath er   th eir   d ata   allo ca ted   in   th B R A MS,   wh er d ata  in   an d   o u o f   th e   NT T   b lo ck   ar 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 B R AM S to   o u tp u t t h 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 s tar tin g   th NT T /I NT T   o p er atio n ,   th h ar d war 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 twid d le  f ac to r s   ( f o r   I NNT   o p e r atio n ) ,   an d   t h in p u t   co ef f icien ts   in to   th B R AM s   o f   ea ch   PE.   T h twid d le  f ac to r   an d   its   m o d u lar   in v e r s v alu es  ar s to r ed   i n   2   B R AM ,   wh ile  th in p u 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 f ir s PE  an d   2   B R AM s   f o r   th s ec o n d   PE.   Af ter   th NT T 2   o p er atio n ,   th o u t p u c o ef f icien ts   at   th cu r r en t   s tag ar e   th en   s to r ed   b ac k   to   th e   s am 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 n e x 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 to p   lev el  u s in g   th 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 DOUT   B L OC u n it  wo u ld   s et  th e   d o n s ig n al  to   h ig h   t o   in d icate   t h 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 o u tp u c o ef f icien ts   d ata  th r o u g h   th e   d o u 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 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   4 . 1 .     E x perim ent a l scena rio   Ou r   h ar d war d esig n   was w r itten   in   Ver ilo g   Har d war Desc r ip tio n   L an g u ag e,   th m o s t c o m m o n   o n e   f o r   h ar d war im p lem en t at i o n   in   th m ea n tim e.   On   th 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 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 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 T SMC   6 5 n m   lib r ar y ,   as  m eth o d   f o r   co m p ar is o n .   T h NT T   s o f twar f o r   th 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 NI ST  s u b m is s io n s   r e f er en c C   s o u r ce   co d e   o f   th 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 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 o f   th m o s cr u cial  an d   p r ec io u s   f ac to r s   o f   th 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 o f   th e   cr y p to s y s tem s   at   th cu r r en tim e.   T h v alu was  m ea s u r ed   b y   ch a n g in g   th f r eq u en c y   v alu in   th 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 th lar g e s v alu p o s s ib le  to   f u lf ill  th s etu p   an d   h o ld   co n s tr ain ts .   Me an wh ile,   o n   th a r ea   s id e,   th g ate  co u n v alu 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 o f   th 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 co m b in atio n al  lo g ic  ac co u n ted   f o r   3 5 . 2 % o f   th 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 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   r elativ ely   h ig h   f r eq u en cy   o f   1 0 2   MH z.   T h v alu e   was  m o d er ately   l o wer   th an   th v alu o f   4 9 7   MH m en tio n e d   a b o v e ,   wh ich   ca n   b e x p lain ed   b y   th e   f ac th at  th h ar d war e   o p tio n s   f o r   FP GA  ar e   m u ch   m o r 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 n u m b er   o f   L UT s   u s ed   in   th im p lem en tatio n   d esig n   was  m u ch   less   in   co m p ar is o n   to   th s y n th esis   d esig n ,   s in ce   th 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 d esig n   o n ly   u s ed   4 . 6 5 o f   th to tal  am o u n o f   u s ab le  r eg is ter   an d   th er was  n o   latch   g en er ated   in   o u r   d esig n .   T h is   ca n   b s ee n   as a n   o p tim is t r esu lt in   th 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 wo rk   T ab le  3   an d   Fig u r 6   co m p ar e   th r esu lts   in   o u r   wo r k   an d   p r ev io u s   wo r k s .   T h r elatio n s h i p   b etwe en   th n u m b er   o f   b u tter f l y   u n its   u s ed   in   th d esig n   an d   im p le m en tatio n   tim in g   r esu lts   ar s h o wn   in   T ab le  3   an d   Fig u r 6 ( a) .   T h m o r b u tter f ly   u n its   th er 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 an d   in c r ea s ed   th m a x im u m   wo r k in g   f r eq u en cy   o f   th im p lem en tatio n   d esig n .   Usi n g   two   o f   th ese  u n its ,   it  ca n   b 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 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 6 ( b ) .   T h is   ac h iev em e n was  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 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 tim in g   an d   p er f o r m an ce ,   th 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 r ea d   a n d   wr ite  ad d r ess   e f f icien tly   ac ce s s in g   th 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 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   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 NT T   h ar d war d esig n s   in   [ 6 ]   an d   [ 7 ] .   Ho wev er ,   th is   o p tim izatio n   ca m at  th co s o f   h ig h   g ate  co u n o f   4 7 2 s in ce   th 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 th o u g h   r esu lted   in   r elativ ely   s m all  laten cy   o f   ju s 6 8 6   an d   an   in s ig n if ican p r o ce s s in g   tim o f   1 . 3 8   m icr o s ec o n d s   f o r   t h NT T   o p er atio n .   T h is   laten cy   an d   o p er atio n   tim e   ar 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 th at   em p lo y ed   th 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 v a lu 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 imp leme n ta tio n   o n u mb er th eo r etic  t r a n s fo r fo r   … ( Tr a n g   Ho a n g )   741   u tili zin g   s ig n if ica n n u m b er   o f   r eso u r ce s   ( ar ea )   in   t h 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 u s in g   u p   lar g n u m b e r   o f   r eso u r ce s ,   r en d e r in g   it  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 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 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 C M O S   2 5 6   13   1 2 8 9   72   17   1 0 6 K   [ 8 ]   4 0 n 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.