Title:
SECURE AND FAST BIT UNPACKING FOR DILITHIUM
Document Type and Number:
WIPO Patent Application WO/2024/094770
Kind Code:
A1
Abstract:
The disclosure relates to a cryptographic device and to a method to improve the security of the cryptographic device white minimizing the deceleration of the cryptographic device due to improving the security of the cryptographic device. The cryptographic device comprises at least one electronic chip to carry out a Dilihium operation involving a vector y of polynomials yi with coefficients yi,j. The method comprises the cryptographic device generating the vector y from a random seed and unpacking the vector y from a bit string. The method further comprises the cryptographic device reusing the random seed to randomly shuffle the unpacking of the vector y, thereby further securing the Dilihium operation while sparing a random number generation.
More Like This:
Inventors:
FAUGÈRE JEAN-CHARLES (FR)
ADOMNICAI ALEXANDRE (FR)
ADOMNICAI ALEXANDRE (FR)
Application Number:
PCT/EP2023/080500
Publication Date:
May 10, 2024
Filing Date:
November 01, 2023
Export Citation:
Assignee:
CRYPTONEXT SAS (FR)
International Classes:
H04L9/30; H04L9/00; H04L9/32
Attorney, Agent or Firm:
WLODARCZYK, Lukasz (avocats9, boulevard Saint-Germain Paris, FR)
Download PDF:
Claims:
| C L AI M S 1. A m e th o d to im p ro v e th e s e c u rity o f a c ry p to g ra p h ic d e v ic e (S C ) w h ile m i nim iz in g th e d e c el er ati o n o f th e c ry p to g ra p h ic d e v ic e d u e to im p ro v in g th e s e c u rity o f th e c ry p to g ra p h ic d e v ic e , t h e c ry p to g ra p h ic d e v ic e c o m p ris in g a t le a s t o n e e le c tro n ic c h ip (IC C ) to c arr y o u t a D ilith i um o p e ra tio n in v o lv in g a v e ct or y of p ol y n o mi al s y i (y 1 , y 2 , y 3 , y 4 ) wit h c o effi ci e nt s y i,j (y 1 ,1 , y 1 ,2 , … y 1 ,256 , … y 4 ,256 ), w h e re in th e m e th o d c o m p ris e s t h e c ry p to g ra p h ic d e v ic e g e n e ra tin g th e v e c to r y fro m a ra n d o m s e e d a n d u n p a c k in g th e v e c to r y fro m a b it s trin g , w h e re in th e m e th o d fu rth e r c o m p ris e s t h e c ry p to g ra p h ic d e v ic e r e u si n g t h e r a nd o m s e e d t o ra n d o ml y s h u ffle t h e u np a c ki n g of th e v e c to r y , t h er eb y furt h er s e c u ri n g t h e Dilit hi u m o p er ati o n w hil e s p a rin g a ra n d o m n u m b e r g e n e ra tio n . 2. T h e m e th o d o f c la im 1 , w h e re in th e D ilith iu m o p e ra tio n c o m p ris e s c o m p u tin g a D ilith iu m d ig ita l s ig n a tu re o f t h e f or m z = y + c s 1. 3. T h e m e th o d o f c la im 1 or 2 , c o m p ris in g th e c ry p to g ra p h ic d e v i ce re u si n g t h e r a nd o m s e e d t o ra n d o ml y s h u ffle t h e u n p a c ki n g o f th e v e c to r y b y c h a n g in g th e or d er in w h ic h t h e p ol y n o mi al s y i wit hi n t h e v e ct or y a re p ro c e s s e d . 4. T h e m e th o d a c c or di n g to a n y pr e vi o u s c la im , c o m p ris in g th e c ry p to g ra p h ic d e v i ce re u s i n g t h e r an d o m s e e d t o ra n d o ml y s h u ffle t h e u n p a c ki n g o f th e v e c to r y b y c h a n g in g th e or d er in w h ic h p ol y n o mi al s c o e ffi cie nt s y i,j wit hi n e a c h p ol y n o mi al y i of t h e v e ct or y ar e pr o c e s s e d . 5. T h e m e th o d a c c or di n g to a n y pr e vi o u s c la im , c o m p ris in g s e c uri n g a t le a s t o n e o th e r D ilith iu m o p e ra tio n b y u s in g d iffe re n t p a rts o f th e ra n d o m s e e d fo r e a c h D ilith iu m o p e ra tio n . 6. T h e m e th o d a c c or di n g to a n y pr e vi o u s c la im , c o m p ris in g th e c ry p to g ra p h ic d e v i ce s h u fflin g o rd e re d e le m e n ts id e n tifie d b y a n in d e x i, b y re p la c in g th e in d e x i b y a n o th e r in d e x j, w h e re th e ot h er i n d e x j is e q u al t o t h e e x cl u si v e or of t he i n d e x i wit h in fo rm a tio n d e riv e d fro m t h e r a nd o m s e e d . 7. T h e m e th o d a c c o r di n g to a n y o f c la im s 1 to 5 , c o m p ris in g th e c ry p to g ra p h ic d e v ic e s h u fflin g o rd e re d e le m e n ts id e n tifie d b y a n in d e x i, b y re p la c in g th e in d e x i b y a n o th e r in d e x j, w h e re th e ot h er i n d e x j is e q u al t o t h e it h it erati o n o f a li n e ar c o n gr u e nti al g e n er at or i n itiali z e d b a s e d o n t h e r a n d o m s e e d . 8. A c ry p to g ra p h ic d e v ic e ( S C) c o m p ris in g a t le a s t o n e e le c tro n ic c h ip (I C C) to c arr y o u t a D ilith i um o p e ra tio n in v o lv in g a v e ct or y of p ol y n o mi al s y i (y 1 , y 2 , y 3 , y 4 ) wit h c o effi ci e nt s y i,j (y 1 ,1 , y 1 ,2 , … y 1 ,256 , … y 4 ,256 ), t h e c ry p to g ra p h ic d e v ic e b e in g a rra n g e d to g e n e ra te th e v e c to r y fro m a ra n d o m s e e d a n d to u n p a c k th e v e c to r y fro m a b it s trin g , w h e re in th e c ry p to g ra p h ic d e v ic e is fu rth e r a rra n g e d to r e u se t h e r a nd o m s e e d t o ra n d o ml y s h u ffle th e u n p a c ki n g of th e v e c to r y , t h er eb y furt h er s e c ur i n g t h e Dilit hi u m o p er ati o n w hil e s p a rin g a ra n d o m n u m b e r g e n e ra tio n . 9. T h e c ry p to g ra p h ic d e v ic e o f c la im 8 , w h e re in th e D ilith iu m o p e ra tio n c o m p ris e s c o m p u tin g a D ilith iu m d ig ita l s ig n a tu re o f t h e f or m z = y + c s 1. 10. T h e c ry p to g ra p h ic d e v ic e o f c la im 8 or 9 , w h er e in th e c ry p to g ra p h ic d e v ic e is a rra n g e d to re u s e t h e r a nd o m s e e d t o ra n d o ml y s h u ffle t h e u n p a c ki n g o f th e v e c to r y b y c h a n g in g th e or d er in w h ic h t h e p ol y n o mi al s y i wit hi n t h e v e ct or y a re p ro c e s s e d . 11. T h e c ry p to g ra p h ic d e v ic e o f a n y o f c la im s 8 t o 10 , w h er e in th e c ry p to g ra p h ic d e v i c e is a rra n g e d to re u s e t h e r a nd o m s e e d t o ra n d o ml y s h u ffle t h e u n p a c ki n g o f th e v e c to r y b y c h a n g in g th e or d er in w h ic h p ol y n o mi al s c o e ffi ci e nt s y i,j wit hi n e a c h p o l y n o mial y i of t he v e ct or y ar e pr o c e s s e d . 12. T h e c ry p to g ra p h ic d e v ic e o f a n y o f c la im s 8 t o 11 , w h er e in th e c ry p to g ra p h ic d e v i c e is a rra n g e d to s e c ur e a t le a s t o n e o th e r D ilith iu m o p e ra tio n b y u s in g d iffe re n t p a rts o f th e ra n d o m s e e d fo r e a c h D ilith iu m o p e ra tio n . 13. T h e c ry p to g ra p h ic d e v ic e o f a n y o f c la im s 8 t o 12 , w h er e in th e c ry p to g ra p h ic d e v i ce is a rra n g e d to s h u ffle o rd e re d e le m e n ts id e n tifie d b y a n in d e x i, b y re p la c in g th e in d e x i b y a n o th e r in d e x j, w h e re th e ot h er i n d e x j is e q u al t o t h e e x cl u si v e or of t he i n d e x i wi t h in fo rm a tio n d e riv e d fro m t h e r a n d o m s e ed . 14. T h e c ry p to g ra p h ic d e v ic e o f a n y o f c la im s 8 t o 12 , w h er e in th e c ry p to g ra p h ic d e v i c e is a rra n g e d to s h u ffle o rd e re d e le m e n ts id e n tifie d b y a n in d e x i, b y re p la c in g th e in d e x i b y a n o th e r in d e x j, w h e re th e ot h er i n d e x j is e q u al t o t h e it h it erati o n o f a li n e ar c o n gr u e nti al g e n er at or i niti ali z e d b a s e d o n t h e r a n d o m s e ed . 15. A c o m p ut er pr o gr a m c o m pri si n g a s e q u e n c e of i n str u cti o n s i m pl e m e nti n g t h e st e p s of t h e m et h o d of a n y of cl ai m s 1 t o 7 w h e n e x e c ut e d b y a pr o c e s s o r. 16. A n o n -tr a n sit or y c o m p ut er-r e a d a bl e st or a g e m e di u m c o m pri si n g a c o m p ut er pr o gr a m a c c or di n g t o cl ai m 15. |
Description:
S E C U R E A N D F A S T BI T U N P A C KI N G F O R DI LI T HI U M T h e di s cl o s ur e r el at e s t o p o st q u a nt u m cr y pt o gr a p h y, m or e s p e cifi c all y t o th e D ilith iu m s c h e m e w h ic h h a s b e e n s e le c te d b y th e N IS T in 2022 a s o n e o f th e p o s s ib le s c h e m e s to a d d re s s t h e q u a n tu m c o m p u tin g th re a t. A s y m m e tric c ry p to g ra p h y (a .k .a . p u b lic k e y c ry p to g ra p h y ) w a s in v e n te d in th e 1970 s . It c o n s is ts in re p la c in g ( or co m pl e m e nti n g) tr a diti o n al s e cr et k e y s b y k e y p a ir s c o m p o s e d of a p u bli c k e y a n d a priv at e k e y. E a c h e ntit y k e e p s it s pri v at e k e y f or it se lf, w hi c h a v oi d s s h ari n g it w ith a n y b o d y e ls e . T h e p u b lic k e y , h o w e v e r, c a n b e s h a re d w ith a n y b o d y . T h is is a g re a t a d v a n ta g e o v e r s e c re t k e y c ry p to g ra p h y . In d e e d , s h a rin g a s e c re t k e y w ith a n o th e r e n tity m e a n s th a t e a c h e n tity n e e d s to h a v e a d iffe re n t s e c re t k e y fo r e v e ry o th e r e n tity w ith w h ic h it in te n d s to c o m m u n ic a te . F aili n g t o d o s o w o ul d m e a n t h at m ulti pl e e ntiti e s c o ul d d e cr y pt c o nfi d e nti al d at a s e nt t o o nl y o n e of t h e m ( d u e t o th e s a m e s e cr et k e y b e i n g s h a re d ), w hic h i s n ot s a f e. T h is in tu rn s m a y le a d to s e v e re k e y m a n a g e m e n t is s u e s (d u e to th e n u m b e r o f s e c re t k e y s in v o lv e d to a v oi d t hi s diffi c ult y ). B y c o n tra s t, w ith a s y m m e tric c ry p to g ra p h y e a c h e n tity m a y o n ly n e e d a s little a s o n e k e y p a ir ( s ev er al k e y p a irs m a y b e n e e d e d s o m e ti m es, f o r r e as o n s t h at a re n ot i m m e diat el y r el ev a nt t o t h e p re s e n t d is c lo s u re ). A p u b lic k e y c a n “u n d o ” w h a t a c o rre s p o n d in g p riv a te k e y h a s “d o n e ”, a n d vi c e v er s a. S o , f or e x a m pl e, a g iv e n e n tity c a n s ig n a d o c u m e n t b y a p p ly in g its p riv a te k e y to it. N o o th e r e n tity c a n d o th a t, b y la c k o f a c c e s s to th e p riv a te k e y . B u t a n y e n tity c a n v e rify th a t th e s ig n a tu re is c o rre c t, b y c h e c k in g it w ith th e p u b lic k e y o f th e e n tity th a t p re te n d s to h a v e s ig n e d (a s th is p u b lic k e y i s p u bli c ly a v a ila b le ). C o n v er s el y, a n e ntit y c a n s h ar e a s e cr et (e .g . a s e c re t k e y ) wit h a r e ci pi e nt b y a p p l yi n g th e p u bli c k e y of t h e r ec i pi e nt t o t he s e cr et . O nl y t h e r ec ip ie n t c a n th e n e x tra c t th e s e c re t, b y a p p ly in g its p riv a te k e y . T h e m o st wi d e s pr e a d p u bli c k e y cr y pt o gr a p h y s ol uti o n i s c a lle d R S A. R S A is u s e d to e n c ry p t e m a il c o m m u n ic a ti o n s, to s e c u re tra n s a c tio n s o n w e b s ite s (b a n k tra n s a c ti o n s, et c.) , t o a ut h e nti c at e t o t hir d p arti e s , et c. T h e s e c urit y of R S A i s b a s e d o n t h e a s s u m pti o n t h at it i s h ar d t o f a ct or t h e pr o d u ct of la rg e p rim e n u m b er s. T h is h a s n e v e r b e e n p ro v e n , b u t n o b o d y e v e r m a n a g e d to s o lv e th is p ro b le m , a t le a st p u b lic ly , w ith in re a s o n a b le tim e a n d c o s t, a n d fo r re a s o n a b ly si z e d pri m e n u m b er s . F or a p pr o xi m at el y 25 y e ar s , t h er e ha s b e e n i nt e n s e r e s e ar c h i n t he fie ld o f q u a n tu m c o m p u tin g . T h e a d v e n t o f q u a n tu m c o m p uti n g is s till n o t c e rt ain . T h e d at e w h e n a firs t u s a b le q u a nt u m c o m p u te r c o u ld b e c o m e a v a ila b le is e v e n le s s c e rta i n. H o w e v e r, it i s m or e a n d m or e li k ely th a t q u a n tu m c o m p u te r c o u ld b e c o m e a re a lity in th e n e ar f ut ur e . Q u a nt u m c o m p uti n g i s ex p e ct e d t o b e a bl e to e a sil y f a ct or t h e pr o d u ct of la rg e p rim e n u m b er s . C u rre n tly d e p lo y e d (p re -q u a n tu m ) s o lu tio n s u s e d to s e c u re th e In te rn e t o r o ffli ne a c tiv itie s w o u ld n o t re s is t. It h a s th er e fo re b e c o m e u rg e n t to d e s ig n n e w c ry p to g ra p h ic s c h e m e s th at w o u ld re s is t q u a nt u m c o m p uti n g. D ilit hi u m i s o n e of t h e m a n d w a s s el e ct e d b y t h e NI S T i n Jul y 2022 aft er a s el e cti o n pr o c e s s t h at h a d st art e d b a c k i n 2016. D ilith iu m p ro v id e s a di git al si g n at ur e s c h e m e , i.e . a to o l fo r a n e n tity to c e rtify d a ta to b e s e n t to a re c ip ie n t a n d to le t th e re c ip ie n t v e rify th a t s a id d a ta w e r e n ot alt er e d a n d w er e i n d e e d c ertifi e d (si g n e d) b y t h e e ntit y. A di git al si g n at ur e s c h e m e i s a c oll e cti o n of t hr e e t o ol s : 1. A k e y g e n er ati o n to o l, G e n er at e, w hi c h g e n er at e s a p u bli c (v erifi c ati o n ) k e y a n d a pri v at e (si g ni n g ) k e y ; 2. A si g ni n g to o l, Si g n, w hi c h t a k e s t h e pri v at e si g ni n g k e y, a m e s s a g e, a n d o u t p ut s a si g n at ur e of t h e m e s s a ge ; 3. A v erifi c ati o n t o ol, V erif y, w hi c h t a k e s t h e p u bli c (v erifi c ati o n ) k e y, t h e si g n at ur e a n d t h e m e ss a g e, a n d o ut p ut s a v al u e st ati n g w h et h er t h e si g n at ur e i s v ali d or n o t. I n t h e c o nt e xt of si g n at ur e s c h e m e s, att a c k er s ar e i nter e st e d i n Si g n a n d G e n er at e t o ol s t o r e c o v er t h e pri v at e k e y ( V erif y m a ni p ul at e s t h e p u bli c k e y o nl y ). In Dilit hi u m, t h e p u bli c k e y c o n si st s of a m atri x ( w hi c h i s ty pi c a lly re fe rre d to a s “A ”) a n d a v e ct or ( w hi c h i s ty pi c a lly re fe rre d to a s “t”). T h e p riv a te k e y is fo rm e d wit h tw o v e c to rs (ty p ic all y re fe rre d t o a s “s 1 “ a n d “s 2 ”). T h e p u b lic a n d p riv a te k e y s a re lin k e d b y th e fo rm u la t = A s 1 + s 2. Q u a nt u m c o m p ut er s c a n n ot r etri e v e s 1 a n d s 2 fr o m A a n d t (t hi s i s c all e d t h e M L W E pr o bl e m , w hi c h q u a nt u m c o m p ut er s c a n’t sol v e ). T h e s p e c ific a tio n o f D ilith iu m (C R Y S T A L S -Dilit hi u m , Al g orit h m S p e cifi c ati o n s a n d S u p p orti n g D o c u m e nt ati o n , S hi B ai, L é o D u c a s, Ei k e Kilt z, T a n cr è d e L e p oi nt, V a di m L y u b a s h e v s k y, P et er S c h w a b e, Gr e g or S eil er a n d D a mi e n St e hl é , O ct o b er 1, 2 020 ) p ro v id e s th e fo llo wi n g p s e u d o c o d e fo r th e S ig n a n d G e n e ra te to o ls (im a g e e x tra c te d fro m F ig u re 4 , p a g e 13 ): T h e k e y p a ir g e n e ra tio n w o rk s a s fo llo w s : L in e 01 : g e n e ra ti o n o f a 256 -b it ra n d o m n u m b e r (p ar a m et er ζ ). L i n e 02: p s e u d or a n d o m g e n er ati o n of t h r ee 256 -bit p a r a m et er s (ρ, ς , K ) b y u si n g a f u ncti o n H, w hi c h i s a h a s h f u n cti o n fe d w ith th e 256 -b it ra n d o m n u m b e r ζ o f lin e 01 a s a s e e d . H i s i n f a ct t h e S H A K E -256 f u n cti on , wh ic h c a n g e n e ra te a n a rb itra rily lo n g o u tp u t. S H A K E -256 m u s t b e fe d w ith a ra n d o m s e e d to n o t p ro d u c e th e s a m e p s e u d o ra n d o m s e q u e n c e e a c h t i m e it i s c all e d. Li n e 03: p s e u d or a n d o m g e n er a ti o n of t h e pri v at e k e y ( v e ct or s s 1 a n d s 2 ), a g a in w ith t h e S H A K E -256 fu n c tio n o p e ra te d o n p a ra m e te r ς (2 n d p a ra m e te r g e n e ra te d in lin e 02 ). L in e 04 : th e m a trix A is g e n e rat e d b y e x p a n d in g p a ra m e te r ρ (1 s t p a ra m e te r g e n e ra te d in lin e 02 ). T h e m atri x A i s o nl y n e e d e d f or m ulti pli c ati o n. H e n c e, f or t h e s a k e of f a st er i m pl e m e nt ati o n s, t h e e x p a n si o n f u n cti o n E x p a n d A d o e s n ot o ut p ut t h e a ct u al m atri x b ut t he N T T d o m ai n r e pr e s e nt ati o n  of A . N T T (a c ro n y m fo r N u m b er -t h e or eti c tr a n sf or m) is a di s cr et e F o uri er tr a n sf or m f or fi nit e fi el d s u s e fu l to o p tim iz e m u ltip lic a tio n s . L in e 05 : c o m p u te t = A s 1 + s 2 (a d v a nt a g e o u sl y , A s 1 is c o m p u te d w ith th e e q u iv a le n t b u t fa s te r f or m ul a A s 1 = N T T -1 ( N T T (s 1 ))). L i n e 06: a g ai n f or o pti miz ati o n p ur p o s e s , t i s d e c o m p o s e d i n hi g h or d er p art t 1 a n d l ow o r d er p art (f orm e d o f d bit s ) t0 , i. e. t = t1 2 d + t0. P ar a m et e r t1 i s u s e d a s t h e p u bli c k e y i n st e a d of u si n g t. Li n e 06 c o m p u t e s t0 a n d t1. L in e 07 : th is lin e g e n e ra te s 384 p s e u d or a n d o m b its (p a ra m e te r tr) w ith f u n cti o n C R H (a c olli si o n re si st a nt h a s h f u n cti o n - for t hi s p ur p o s e 384 bit s of t h e o ut p ut of S H A K E-256 ar e u s e d ). Li n e 08: fi n al ly, o pti mi z e d v er si o n s o f t h e p u bli c a n d pri v at e ke y s a re o u tp u t. T h e s ig n a tu re w o rk s a s fo llo w s (t h ere ar e t w o p o s si bl e i m pl e m e nt ati o n s, d et er mi ni sti c or r a n d o mi z e d) : L i n e 09: a s i n lin e 04 o f t h e k e y g en er ati o n, th e m a trix A is “r est o r ed ” (it’s lik e a d e c o m p re s s io n ) b y e x p a n d in g p a ra m e te r ρ (w h ic h is m u c h m o re c o m p a c t). A s in lin e 04 a n d fo r th e s a m e re a s o n s , t h e e x p a n si o n f u n cti o n E x p a n d A a d v a nt a g e o u sl y d o e s n ot o ut p ut t h e a ct u al m atri x b ut t h e N T T d o m ai n r e pr e s e nt ati o n  of A . L in e 10 : th is lin e g e n e ra te s 384 p s e u d or a n d o m b its (p a ra m e te r μ ) w ith f u n cti o n C R H (s e e lin e 07 a b o v e ). L in e 11 in itia liz e s p a ra m e te rs κ a n d (z, h ) w ith c o n s ta n t v a lu e s . L in e 12 g e n e ra te s 384 b its (p a ra m e te r ρ′ ). I n t h e d et er mi ni sti c i m pl e m e nt ati o n, g e n er at e t h e m a s p s e u d or a n d o m bit s w ith f u n cti o n CR H (s e e lin e 07 a b o v e ). In th e ra n d o m iz e d im p le m e n ta tio n , d ra w a ra n d o m n u m b e r w ith a ra n d o m n u m b e r g e n e ra to r. T h e d iffer e n c e is : th e d e te rm in is tic im p le m e n ta tio n w ill a lw a y s o u tp u t th e s a m e 384 b its fo r a g iv e n k e y a n d m e s s a g e t o b e si g n e d, w hil e t h e r a n do m i z e d i m pl e m e nt ati o n will o ut p ut diff er e n t v alu e s e a c h ti m e. A s a c o n s e q u e n c e , th e s a m e m e s s a g e will n ot h a v e t h e s a m e s ig n a tu re w h e n s ig n e d s e v e ra l ti m e s w ith th e ra n d o m iz e d im p le m e n ta tio n . L in e 13 s ta rts a lo o p fo r c o m p u tin g th e s ig n a tu re . In d e e d , th e si g n at ur e c o m p u ta tio n d o e s n o t n e c e s s aril y s u c c e e d im m e d i at el y. It h a s to b e r e p e a te d s o lo n g a s it is n ot s a tis fa c t ory , a s w ill b e s e e n . A t t h at st ag e, a n o p tim iz e d im p le m e n ta tio n w o u ld p r ec o m p ut e ŝ 1 = N T T (s 1 ), ŝ 2 = N T T (s 2 ), a nd 0 = N T T (t0 ). L in e 14 g e n e ra te s p s e u d or a n d o m v e c to r y b a s e d in p a rtic u la r o n p s e u d or a n d o m p ar a m et er ρ′ ( se e li n e 12 ). T h e f u n cti o n E x p a n d M a s k c o m p ut e s e a c h of t h e l c o effi ci e nt s o f y , w hi c h ar e p ol y n o mi als , i n d e p e n d e ntl y. F or t h e i t h p ol y n o mi al , 0 ≤ i< l, it a b s or bs t h e 48 b yt e s o f ρ ′ c o n c at e n at e d wit h t h e 2 b yt e s r e pr e s e nti n g κ + i i n littl e e n di a n b yt e or d er i nt o S H A K E-256. L in e 15 c o m p u te s w = A y . T h is c a n b e o pti mi z e d b y c o m p u tin g , in s te a d o f th e n aï v e A y , w = N T T − 1 ( N T T( y)) . L i n e 16 t a k es a d v a nt a g e of t h e f a ct th a t w c a n b e writt e n i n a c a n o ni c al w a y a s w = w 1 2 γ 2 + w 0 w h er e |w 0 | ≤ γ 2. A c c or di n gl y , it p r e p ar e s f or o pti mi z i n g c o m p ut ati o n s w ith w b y c o m p uti n g w 1. L in e s 17 c o m p u te s 256 -b it p s e u d or a n d o m v a lu e w ith fu n c tio n H (S H A K E -256) . Li n e 18 : c o m p ut e c fr o m wit h t h e S a m pl eI n B all r o uti n e , w hi c h a b s or b s t h e 32 b yt e s of i nt o S H A K E-256. T hr o u g h o ut it s o p er ati o n s t h is r o uti n e s q u e e z e s S H A K E -256 i n or d er t o o bt ai n a str e a m of r a n d o m b yt e s of v ari a bl e l e n gt h. T h e fir st τ bit s i n t h e fir st 8 b yt e s of t hi s r a n d o m s tr e a m ar e i nt er pr et e d a s τ ra n d o m si g n bit s s i ∈ { 0, 1}, i = 0, … , τ − 1. T h e r e m ai ni n g 64 − τ bit s ar e di s c ar d e d . F o r o pti mi z ati o n p u r po s e s, c c a n b e st or e d i n N T T r e pr e s e nt ati o n a s ĉ = N T T( c) . Li n e 19 : c o m p u te t h e te n ta tiv e s ig n a tu re c o m p o n e n t z = y + c s 1. F o r o p tim iz a tio n p u rp o s e s , c o m p ut e c s 1 a s N T T − 1 (ĉ ŝ 1 ). L i n e 20 : c o mp ut e p ar a m et er r 0 w hi c h i s u s e d t o a s s e s s w het h er t h e t e nt ativ e si g n at ur e c o m p o n e n t z (f or m er li n e) i s s af e or w h et h er it n e e d s t o b e r e cal c u l at e d. N . B. th is c o m p u ta tio n o f r0 in v o lv e s c s 2 , b u t fo r o p tim iz a tio n p u rp o s e s , c s 2 c a n b e c o m p u te d a s N T T − 1 (ĉ ŝ 2 ). L in e 21 : c h e c k if th e s ig n a tu re c o m p o n e n t z is u n s a fe . If s o , s e t th e p ro p e r p a ra m e te rs to c o nti n u e l o o pi n g u ntil a pr o p er si g n at ur e i s c al c ul at e d. L i n e 22: if t h e si g n at ur e c o m p o n e n t z i s p ot e nti all y s af e, j um p t o n e xt li n e s t o c arr y o ut fu rth e r te s ts . L in e 23 : c o m p u te a v a lu e h th a t m a y b e in d ic a tiv e o f th e fa c t th a t th e s ig n a tu re c o m p o n e n t z is u n s a fe . N . B. th is c o m p u ta tio n o f h in v o lv e s c t0 , b u t fo r o p tim iz a tio n p u rp o s e s , c t0 c a n b e c o m p u te d a s N T T − 1 (ĉ 0 ). L i n e 24 : c h e c k w h et h er i n vi e w of c t0 a n d h, t h e si g n at ur e i s u n s af e. If s o , s e t th e p ro p e r p a ra m e te rs to c o nti n u e l o o pi n g u ntil a pr o p er si g n at ur e i s c al c ul at e d. L in e 25 : in c re m e n t κ in c a s e it is n e e d e d fo r lo o p in g fu rth e r in v ie w o f o b ta i ni n g a b ett er si g n at ur e. Li n e 26 : t hi s li n e i s r e a c h ed o n l y aft er l o o pi n g i s o v er a n d a pr o p er si g n at ur e c o m p o n e n t z h a s b e e n o b ta in e d . L in e 26 re tu rn s th e s ig n a tu re . T h e a b o v e c a n b e si m plifi e d a s f oll o w s. T o si g n a m e s s a g e wit h pri v at e k e y s 1 , s2 : 1. S a m pl e y a s a r a n d o m v e ct or of p ol y n o mi al s wit h u nif or m c o effi ci e nt s ; 2. C o m p ut e c = H ( m e s s a g e, A y) w h er e H i s a h a s h f u n cti o n a n d A i s p a rt o f t h e p u bli c k e y; 3. C o m p ut e z = y + c s 1 ; 4. If z h a s c o effi ci e nt s i n a s m all i nt er v al, t h e n g o b a c k t o st e p 1 (r ej e cti o n s a m pli n g); 5. R et u r n t h e si g n at ur e σ = ( z, c). A si g n at ur e s c h e m e th a t is t h e ore ti c all y s e c ur e c a n still b e d ef e at e d w h e n i m pl e m e nt e d i n t h e r e al w orl d . In d e e d , p h y si c al p h e n o m e n a o n t h e c o m p uti n g pl atf or m im p le m e n tin g th e s ig n a tu re s c h e m e c a n l e a d t o si d e -c h a n n el le a k a g e s ( e. g. e x e c uti o n ti mi n g, p o w er c o n s u m pti o n, el e ctr o m a g n eti c e m a n ati o n s) t h at c a n d is c lo s e i nf or m ati o n a b o ut t h e d at a b ei n g m a ni p ul at e d . Dilit hi u m is s u p p o s e d t o b e pr ot e ct a bl e a g ai n st ti mi n g att a c ks . B ut it i s still v ul n er a bl e t o p o w er or el e ctr o m a g n eti c l e a k ag e . A Diff er e nti al P o w er A n al y si s ( D P A) att a c k c o u ld t ar g et t h e i nt er m e di at e pr o d u ct c s 1 t o r e c o v er t h e pri v at e k e y. T h e c o n v er si o n of s 1 i nt o t h e N T T d o m ai n f or effi ci e nt p ol y n o mi al m ulti pli c ati o n c s 1 al s o c o n stit ut e s a n att a c k p at h . H o w e v e r, c o u n te rm e a s u re s h a v e alr e a d y b e e n pr o p o s e d a g ai n st t h e a b o v e. M or e r e c e ntl y, a n e w att a c k a g ai n st Dilit hi u m h a s b e e n p u bli s h e d (S o u n d e s M ar z o u g ui et al. , Pr ofili n g Si d e -C h a n n el Att a c k s o n Dilit hi u m : A S m all Bit -Fi d dli n g L e a k Br e a k s It All , Cr y pt ol o g y e Pr i nt Ar c hi v e, R e p ort 2022/ 106. 2022 ). It c o n si st s i n i d e ntif yi n g s o m e n ull c o effi ci e nt s i n v e c to r y . V e c to r y i s u s e d t o b uil d t h e si g n at ur e c o m p o n e nt z = y + c s 1. W h e n th e i th c o e ffic ie n t y i = 0 , w e h a v e z i = ( c s 1 )i, w h ic h gi v e s a li n e ar r el ati o n o n t h e c o rre s p o n d i n g c o eff i ci e nt of s 1. A li n e ar s y st e m i n v ol vi n g t h e pri v at e k e y s1 c a n t h e n b e s ol v e d , if t h e n u m b er of e q u ati o n s i s s uffi ci e nt . In Dilit hi u m 2 , p ol y n o mi al c o effi ci e nt s i n y a re d efi n e d o n w = 18 bit s (w = 20 b it s f or Dilit hi u m 3/ 5). In t hi s c a s e, a c o effi ci e nt i s n ul l wit h a p r o b a bilit y of 1/ 2 18 . T h er e ar e 256 c o e ffi ci ent s p er p ol y n o mi al a n d L = 4 p ol y n o mi al s i n y . Si n c e y h a s t o b e pi c k e d r a n d o ml y, t h e i m pl e m e nt er ty pi c all y ra n d o m l y g e n er a t es 18 * 256 * 4 bi ts a n d th e n h a s t o u n p a c k th is r a n d o m stri n g i nt o 2564 c o effi c i e nt s of 18 bit s e a c h . U n fo rtu n a te ly , if o n e h a n dl e s e a c h p ol y n o mi al s e q u e nti all y (fr o m 1 t o 4 ) a n d e a c h c o effi ci e nt s e q u e nti all y (fr o m 1 t o 256), a s i s t h e c a s e b y d ef a ult, a n att a c k i s p o s si bl e. In o th e r w o rd s , w h ile D ilith iu m is m a th e m a tic a lly s e c u re (to th e b e s t o f th e c u rre n t k n o w le d g e ), r e al im p le m e n ta ti on s o f D ilith iu m c a n b e ta rg e te d for e x a m pl e b y s id e c h a n n e l a tta c k s . L e v eli n g Dilit hi u m a g ai n st L e a k a g e , R e vi sit e d S e n siti vit y A n al y si s a n d I m pr o v e d I m pl e m e nt ati o n s , M eli s s a A z o u a o ui , Oli vi er Br o n c h ai n , G a ët a n C a s si er s, Cl é m e nt H off m a n n , Y uli a K u z o v k o v a , J o o st R e n e s, T o bi a s S c h n ei d er, M ar k u s S c h ö n a u er , Fr a n ç oi s- X a vi er St a n d a ert a n d C hri sti n e v a n Vr e d e n d a a , Cr y pt ol o g y e Pri nt Ar c hi v e , 23 o ct o b er 2022, a n al y z e s w e a k n e s s e s i n i nt er m e di at e c o m p ut ati o n s of Dilit hi u m a n d w a y s t o o v er c o m e t h e m. H o w e v e r, im p le m e nti n g c o u nt er m e a s ur e s a g ai n st si d e c h a n n el att a c k s c a n c o n s u m e r e s o u rc e s a n d n ot o nl y c o m p l e xif y th e d e s i g n of t h e s c h e m e b ut al s o l e a d t o sl o wi n g d o w n t h e si g ni n g t o o l s u b st a nti all y, w hi c h i s a pr ob le m . T h e in v e n tio n a im s a t im p ro v in g th e sit u ati o n. A c c or di n g t o o n e a s p e ct of t h e i n v e nti o n, a m et h o d i s pr o p os e d t o i m pr o v e t h e s e c urit y of a cr y pt o gr ap hi c d e vi c e w hil e mi ni mi zi n g t h e d e c el er ati o n of t h e cr y pt o gr a p hi c d e vi c e d u e t o i m pr o vi n g t h e s e c urit y of t h e cr y pt o gr a p hi c d e vi c e . T h e cr y pt o gr a p hi c d e vi c e c o m pri s e s at l e a st o n e el e ctr o ni c c hi p t o c arr y o ut a Dilit hi u m o p er ati o n i n v ol vi n g a v e ct or y of p ol y n o mi al s y i wi t h c o effi ci e nt s y i,j. T h e m et h o d c o m pri s e s t h e cr y pt o gr a p hi c d e vi c e g e n e r ati n g t h e v e ct or y fr o m a r a n d o m s e e d a n d u n p a c ki n g t h e v e ct or y fro m a bit stri n g . T h e m et h o d f urt h er c o m pri s e s t h e cr y pt o gr a p hi c d e vi c e r e u si n g t h e r a n d o m s e e d t o ra n d o ml y s h uffl e t h e u n p a c ki n g of t h e v e ct or y . T h is i s a d v a nt a g e o u s a s it f urt h er s e c ure s t h e Dilit hi u m o p er ati o n w hil e s p ari n g a r a n d o m n u m b er g e n er ati o n. A c c o rd in g to a n o th e r a s p e c t of t h e in v e n tio n , a cr y pt o gr a p hi c d e vi c e c o m pri s e s at l e a st o n e el e ctr o ni c c hi p t o c arr y o u t a Dilit hi u m o p er ati o n i n v ol vi n g a v e ct or y of p ol y n o mi al s y i wit h c o effi ci e nt s y i,j. Th e cr y pt o gr a p hi c d e vi c e i s arr a n g e d t o g e n er at e t h e v e ct or y fr o m a r a n d o m s e e d a n d t o u n p a c k t h e v e ct or y fr o m a bit stri n g. T h e cr y pt o gr a p hi c d e vi c e i s f urt h er arr a n g e d t o r e u s e t h e r a n d o m s e e d t o r a n d o ml y s h uffl e t h e u n p a c ki n g of t h e v e ct or y . T h is i s a d v a nt a g e o u s a s it f urt h er s e c ure s t h e Dilit hi u m o p er ati o n w hil e s p ari n g a r a n d o m n u m b er g e n er ati o n. Ot h er a s p e ct s, p ur p o s e s a n d a d v a nt a g e s of t h e i n v e nti o n will b e c o m e a p p ar e nt i n a n o n -li miti n g m a n n er u p o n r e a di n g t h e d e s cri pti o n of s om e of it s e m b o di m e nt s. T h e i n v e nti o n will al s o b e b ett er u n d er st o o d b y r ef e rri n g t o t h e dr a wi n g s, i n w hi c h: - Fi g ur e 1 ill u str at e s a c r y pt o gr a phi c d e vi c e a c c or di n g t o a n e m b o di m e nt of t h e i n v e nti o n; - Fi g ur e 2 ill u str at e s t h e ar c hit e ct ur e of a c r y pt o gr a phi c d e vi c e a c c or di n g t o a n e m b o di m e nt of t h e i n v e nti o n; - Fi g ur e 3 ill u str at e s a si m plifi e d m et h o d a c c or di n g t o a n e m b o di m e n t o f t h e i n v e nti o n; - Fi g ur e 4 ill u str at e s a s h u fflin g a c c o rd in g to a n e m b o d im e n t o f th e in v e n tio n . Fi g ur e 1 s h o w s a n el e ctr o ni c c h ip IC C a c c or di n g t o o n e e m b o di m e nt of t h e i n v e nti o n, e m b e d d e d i n a cr y pt o gr a p hi c d e vi c e ( a s m art c ar d S C ). T h e e le c tro n ic c h ip is fo r e x a m p le a m ic ro c o n tro lle r w ith a d e d ic at e d c ry p to p ro c e s s o r. A lte rn a tiv e ly , it is a g e n e ric m ic ro c o n tro lle r. Fi g ur e 2 s h o w s a n ar c hi t e ct ur e of a n el e ctr o ni c c hi p I C C of t h e s m art c ar d S C a c c or di n g t o Fi g ur e 1. T h e I C C c hi p i n cl u d e s a m ic ro pr o c e s s or M P, a m e m or y M E M, a n d a n i n p ut -o ut p ut a d a p te r I O. Th e s e diff er e nt c o m p o n e nt s ar e s c h e m ati c all y r e pr e s e nt e d a s di s cr et e c o m p o n e nt s fi x e d o n a P C B ( n ot s h o w n) a n d c o n n e ct e d t o e a c h ot h er b y a b u s (n ot s h o w n ). B ut t h e s e diff er e nt c o m p o n e nt s c a n b e ( a n d ar e i n pr a cti c e, i n t h e c a s e of s m art c ar d s) i nt e gr at e d o n t h e s a m e c hi p, c ut fr o m t h e s a me w af er , a n d in s e rte d i n a s m artc ar d m o d ul e. T h e m e m or y M E M m a y b e f or e x a m pl e Fl a s h or E E P R O M . T h e m e m o ry M E M m a y s to re a c o m p ut er pr o g r a m w hi c h , w h e n e x e c ut e d b y th e e le c tro n ic c h ip , c a u s e s a mi cr o p ro c e s s o r o f th e e le c tro n ic c h ip to c arr y o ut a m et h o d a c c o rd i n g t o th e in v e n tio n . Fi g ur e 3 d e pi ct s a m et h o d a c c o r di n g t o an e m b o di m e n t o f t h e i n v e nti o n, in w hi c h k n o w n st e p s a r e n o t d et ail e d . T o s e c ur el y a n d q u i c kl y si g n (w ith a s eri e s o f 7 m a in st e p s , re fe rre d to a s S IG N ) a m e s s a g e wit h pri v at e k e y s 1 , s2 : 1. A t s te p S A M P L E _ Y , s a m pl e (i.e . g e n e ra te ) y a s a r a n d o m v e ct or of p ol y n o mi al s wit h u nif or m c o effi ci e nt s (y b e in g re p re s e n te d b y a s trin g o f b its ); 2. A t s te p R E T R I E V E _ S E E D, r e c o v er p a r a m et er ρ′ u s e d a s a s e e d t o g e n er a t e s a m pl e y ( s e e li n e s 12 a n d 14 of F i g ur e 4, p a g e 13 of Dilit hi u m s p e cifi c ati o n , d is c u s s e d a b o v e ); 3. A t s te p S H U F F _ U N P A C K _ Y , u n p a c k y a s a r a n d o m v e ct or of p ol y n o mi al s wit h u nif or m c o effi ci e nt s b y s h u fflin g th e s trin g o f b its to a v o id si d e c h a n n el at t ac k s , an d b y u s i n g t h e s e e d ρ′ (th e re b y a c c e le ra tin g th e p ro c e d u re a s c o m p a re d to g e n e ra tin g a n e w ra n d o m n u m b e r) t o c o nfi g ur e t h e s h u ffli n g; 4. A t s te p C O M P _ A _ Y , c o m p ut e c = H( m e s s a g e, A y) w h er e H i s a h a s h f u n cti o n a n d A i s p art of t h e p u bli c k e y; 5. A t s te p C O M P _ Y _ C S 1 , c o m p ut e z = y + c s 1 ; 6. A t s te p C H K , c h e c k if z h a s c o effi ci e nt s i n a s m all i nt er v al, a n d if t hi s i s t h e c a s e g o b a c k t o st e p S A M P L E _ Y (r ej e cti o n s a m pli n g); 7. O th e rw is e , a t s te p O U T P U T _ S IG , ret ur n t h e si g n at ur e σ = ( z, c). Fi g ur e 4 d e pi ct s a s h uffli n g a c c or di n g t o a n e m b o di m e n t o f t h e i n v e nti o n in w hi c h S T R _ b d e n o te s a stri n g of bit s r e pr e s e nti n g v e ct or y. A s c a n b e s e e n fr o m t h e fi g ur e, t h e str i n g of bit s i s a c o nti g u o u s s eri e s of 18432 bit s i. e. 2304 b y te s , c o rre s p o n di n g t o th e to ta l n u m b er of c o e ffi ci e nt s (4 *256 s in c e th e re a re 4 p o ly n o mi al s w ith 256 c o e ffi ci e nt s e a c h ), m u ltip lie d b y 18 (e a c h c o e ffi ci e nt re q u irin g 18 b its in th e e x a m p le c o n s id e re d ). T h e firs t b it is d e n o te d b 1 , t h e 8 t h i s d e n ot e d b8 , t h e 9 t h b 9 , a nd s o o n. Si mil a rl y, t h e fir st b yt e i s d e n ot e d B 1 (a n d c o rre s p o n d s to b its b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 ), t h e s e c o n d b yt e i s de n ot e d B 2 (a n d c o rre s p o n d s to b its b 9 b 10 b 11 b 12 b 13 b 14 b 15 b 16 ), t h e thir d o n e B 3 (i.e. b its b 17 b 18 b 19 b 20 b 21 b 22 b 23 b 24 ) a n d s o o n. O d d b y te s (1 s t , 3 rd , 5 th , 7 th e tc .) a re g ra y e d o u t w h ile e v e n b y te s (2 n d , 4 th , 6 th e tc .) re m ai n w hit e , s o t h at t h e s u c c e s si o n of b yt e s i s m or e vi si bl e . E a c h b it o f e a c h b y te is re p re s e n te d b y a little b o x (w ith d o tte d lin e s a ro u n d ) w ith a d ig it in s id e . T h e d ig it d o e s n o t re p re s e n t th e v a lu e o f th e b it b u t its p o s itio n in th e b y te (1 fo r 1 s t p o s itio n , 2 fo r 2 n d p o s itio n , a n d u p to 8 fo r 8 th p o s itio n) . T h e a im o f th e s h u fflin g is to re c o n s tru c t a u s a b le re p re s e n t ati o n of th e p o ly n o m ia ls y 1 , y 2 , y 3 a n d y 4 , a n d to d o s o in a ra n d o m o rd e r to p re v e n t a n a tta c k e r fro m s p y in g a n d fin d in g re le v a n t in fo rm a tio n in th e p ro c e s s . T h e c o e ffici e nt s o f p o ly n o mi al y 1 a re d e n o te d y 1 ,1 , y 1 ,2 , y 1 ,3 , … y 1 ,256. S i mil arly, th e c o e ffici e nt s o f p o ly n o mi al y 2 a re d e n o te d y 2 ,1 , y 2 ,2 , y 2 ,3 , … y 2 ,256 , th e c o e ffici e nt s o f p o ly n o mi al y 3 a re d e n o te d y 3 ,1 , y 3 ,2 , y 3 ,3 , … y 3 ,256 , a n d th e c o e ffici e nt s o f p o ly n o mi al y 4 a re d e n o te d y 4 ,1 , y 4 ,2 , y 4 ,3 , … y 4 ,256. O d d c o ef fi ci ent s (y 1 , 1, y 1, 3 , y 2, 1 , y 2, 3 , y 3, 1 , y 3, 3 , y4, 1 , y 4, 3 ) o f t h e p ol y n o mi al s a re g ra y e d o u t w h ile e v e n c o ef fici e nt s (y 1 ,2 , y 1, 256 , y 2, 2 , y 2, 256 , y 3, 2 , y 3, 256 , y4, 2 , y 4, 256 ) re m ai n w hit e , s o t h at t h e s u c c e s si o n of c o ef fi ci ent s i s m or e vi si bl e. T h e bit s of t h e c o e ffi ci e nt s of t h e p ol y n o mi al s ar e n u m b e re d fro m 1 to 18 , h o w e v e r s in c e th e re is n o ro o m fo r tw o d ig its , n u m b e rs fro m 10 to 18 h a v e b e e n re p la c e d b y di gi t s 0 t o 8, pri nt e d i n it ali c s a n d up s i d e d o w n t o di s ti n g ui s h t h e m. E a c h b it o f e a c h c o e ffi ci e nt is re p re s e n te d b y a little b o x (w ith d o tte d lin e s a ro u n d ) w ith a d ig it in s id e . T h e d ig it d o e s n o t re p re s e n t th e v a lu e o f th e b it b u t its p o s itio n in th e c o e ffi ci e nt (1 fo r 1 s t p o s itio n , 2 fo r 2 n d p o s itio n , e tc ., b e in g re m in d e d t h at u p s id e d o w n d ig its 0 to 8 re p re s e n t b its n u m b e r 10 to n u m b e r 18 ). In th e illu s tra te d s h u fflin g , b its b 1 to b 18 a re ra n d o m ly a ffe c te d to a c o e ffic ie n t (i n thi s e x a m pl e, t o c o effi c i e nt y 1 ,2 ) o f a p o ly n o mi al (i n thi s e x a m pl e , p o ly n o mi al y 1 ). T h is m e a n s th a t, b a s e d o n th e ra n d o m n u m b e r u s e d fo r th e p u rp o s e o f ra n d o m ly a ffe c tin g b its to c o e ffic ie n ts in t h e e x a m p le o f F ig u re 4 , th e v a lu e o f th e 1 s t b it o f c o e ffic ie n t y 1 ,2 is e q u a l to th e v a lu e o f b 1 , th e v a lu e o f th e 2 n d b it o f c o e ffic ie n t y 1 ,2 is e q u a l to th e v a lu e o f b 2 , a n d s o o n u p to th e v a lu e o f th e 18 th b it o f c o e ffic ie n t y 1 ,2 w h ic h is e q u a l to th e v a lu e o f b 18. S im ila rly , in t hi s e x a m pl e b its b 19 to b 36 a re ra n d o m ly a ffe c te d to a c o e ffic ie n t (i n thi s e x a m pl e t o c o effi c i e nt y 4 ,2 ) o f a p o ly n o mi al (h e re y 4 ), b its b 37 to b 54 a re ra n d o m ly a ffe c te d to a c o e ffic ie n t (h e re y 1 ,3 ) o f a p o ly n o mi al (h e re y 1 ), a n d b its b 55 to b 72 a re ra n d o m ly a ffe c te d to a c o e ffic ie n t (h e re y 2 ,256 ) o f a p o ly n o mi al (h e re y 2 ). Of c o u rs e , t his i s o n ly a n e x a m pl e a n d a s h u ffli n g a c c or d i n g t o t h e pr e s e n t d e s cri p ti on c o ul d , i n a n ot h er e m b o di m e nt, pi c k a n y 18 bit s fro m th e s tri n g of b it s (n o t e v e n n e c e s s a rily 18 c o n tig u o u s b its ) for a n y 18 -b it c o e ffi ci e nt of a n y p o ly n o mi al . A s c a n b e s e e n fr o m Fi g ur e 4, t h e u n p a c ki n g r e q uir e s e xtr a cti n g bit s fr o m a t le a s t 3 diff er e nt b yt e s fr o m t h e stri n g of bit s S T R _ b i n or d er t o r e c o n stit ut e 18 -bit c o eff i cie nt s. F or e x a m pl e, in t h e e x a m p l e of F i gur e 4, it i s n e c e ss ar y t o e xtr a ct t h e l a st 6 bit s of b yt e B 3, t h e e n tire 8 b its o f b y te B 4 , a n d th e firs t 4 b its o f b y te B 5 , in o rd er t o fo rm c o e ffi ci e nt y 4 ,2. It w o u ld b e v e ry in c o n v e n ie n t, e a c h ti m e a g iv e n c o e ffi ci e nt ne e d s t o b e u s e d i n a c al c u lati o n , to h a v e to d e te rm in e w h ic h b its o f w h ic h b y te s o f th e s trin g o f b its S T R _ b to e x tra c t a n d c o n c a te n a te in o rd e r to re c o n s tru c t s u c h c o e ffic ie n t, a n d th e n to p ro c e e d wit h s u c h r e c o nstr u c ti on , b ef or e m o v in g o n w ith th e d e s ire d c a lc u la tio n . H e n c e t h e pr eli mi n ar y u n p a c ki n g. U n p a c ki n g i s al s o oft e n u s e ful d u e t o t h e f a ct t h at th e s tri n g o f bit s S T R _ b is a t le a s t a s c o m p a c t a n d ty p ic a lly m o re c o m p a c t th a n th e u n p a c k e d v e c to r. W h ile th e c o e ffi ci e nts o f e a c h p o ly n o mi al h a v e b e e n re p re s e nt e d o n F ig u re 4 a s if th e y w e re c o n tig u o u s , th is is n o t n e c e s s a rily tru e . T h e re is n o s u c h th in g a s a n 18 -b it re g is te r in c o n v e n tio n a l pr o c e s s or s . A n d t h er e i s t y pi c all y n o w a y t o a d dr e s s m e m or y b y bl o c k s of 18 bit s. S o , i n pr a cti c e, f or e x a m pl e i n a 64 -bit ar c hit e ct ur e ( w hi c h i s t he p re v a le n t ar c hit e ct ur e fo r c u rre n t p e rs o n a l c o m p u te rs in p a rtic u la r), e a c h c o e ffic ie n t c o u ld b e s to re d o n 64 b its (o n ly 18 o f w h ic h w o u ld b e u s e fu l), b e c a u s e it’s m u c h fa s te r a n d s im p le r to h a n d le it th is w a y . H o w e v e r, fo r p e rm a n e nt s t or a g e p ur po s e (or f or tr a n s mi s si o n ov er a n et w or k ) it i s b e s t t o n ot c o n s u m e n o n -v ol a til e m e m or y u s e l e s sl y ( or t o w a st e t el e c o m b a n d wi dt h ) a n d to u s e a c o m p a c t re p re s e n ta tio n (th e s trin g o f b its S T R _ b ). T h is is a n o th e r ju s tific ati o n f or th e u n p a c k in g . It s h o ul d b e n ot ed t h at , in th e ra n d o m iz e d m o d e o f D ilith iu m , t h e s h uffl i n g of t h e u n p a c ki n g c a n b e vi e w e d , su b s t a nti all y, a s a n i m pl e m e nt ati o n a s p e c t (i.e . a s n ot aff e cti n g t h e o ut c o m e of t h e Dilit hi u m o p er ati o n ). C o n s id e rin g th e e x a m p le o f F ig u re 4 , thi s m a y s e e m c o u n te rin tu itiv e . In d e e d , F ig u re 4 s h o w s th a t th e o rd e r o f th e c o e ffic ie n ts in y is n o t th e s a m e a s it w o u ld h a v e b e e n w ith o u t th e s h u fflin g . H o w e v e r, w h ile it is c o rr ect t o s a y t h at th e s h u ffli n g s h o w n o n Fi g u r e 4 i s e q ui v al e nt t o h a vi n g g e n er at e d t h e r a n d o m n u mb er s u s e d t o b uil d t h e c o e ffi ci e nt s i n a diff er e nt or d er, t hi s i s i m m at eri al fr om a Dilit hi u m c o m p ut a ti o n sta n d p o in t (w h a t m a tte rs is th a t a ra n d o m s o u rc e b e u s e d , b u t t h e a c tu a l v a lu e s o f t h e ra n d o m n u m b e rs is n o t im p ort a n t s o lo n g a s th e y a re ra n d o m ). T h e o rd e r in w h ic h ra n d o m n u m b e rs a re p ic k e d fro m a p o o l o f ra n d o m n u m b e rs to b e a ffe c te d to g iv e n c o e ffi ci e nt s o f v e c to r y (i.e . th e in itia liz a tio n o f v e c to r y c o e ffic ie n ts ) d o e s n o t c h a n g e th e n a tu r e of t he D ilith iu m o p e r ati o n. In th e e n d a ll c o e ffic ie n ts a re d e e m e d ra n d o m a n y w a y . T h e p oi nt of t h e s h uffli n g i s to m a k e s ur e t h at w hil e u n p a c ki n g t a k e s pl a c e, n o u s ef ul i nf or m ati o n m a y b e r etri e v e d b y s p y in g (a n d h e re , th e o rd e r o f th e c o e ffic ie n ts o b v io u s ly m a tte rs ). In t h e d et er mi ni st i c m o d e of Dilit hi u m, if t h e s h uffli n g of Fi g ur e 4 i s i n clu d e d, it c a n b e d et e ct e d . It i s t h er ef or e n ot f or m all y a m er e i m pl e m e nt ati o n a s p e ct, a s it aff e ct s t h e o u t c om e of t h e c o m p ut ati o n in a v is ib le m a n n e r. A c c or di n g t o t h e i n v ent i o n, a p o s si b l e sh uffli n g (w hi c h i s v ari a nt of t h e o n e s h o w n o n F ig u re 4 ) is p ro v id e d th a t c a n b e fo rm a lly c la s s ifie d a s a p u re im p le m e n ta tio n a s p e c t. S u c h s h u fflin g k e e p s th e e x a c t o rd e r o f th e ra n d o m n u m b e rs g e n e ra te d fo r v e c to r y c o e ffic ie n ts . T h e s h u fflin g ta k e s p la c e a t a tim e le v e l, a s o p p o s e d to a s p a c e le v e l. In o th e r w o rd s , th e c o e ffic ie n ts a re k e pt (“g e o g ra p h ic a lly ”) in th e ir o rig in a l p o si ti o n (w hi c h is u n c h a n g e d) . F or e x a m pl e , bit s 1 t o 18 of t h e stri n g of bit s S T R _ b m a y al w a y s c orr e s p o n d to c o effi ci e nt y 1, 1 of p ol y n o mi al y 1 , bit s 19 to 36 of th e stri n g of bit s S T R _ b m a y al w a y s c orr e s p o n d to c o effi ci e nt y 1, 2 of p ol y n o mi al y 1 , a n d s o o n. H o w e v er , c o e ffic ie n ts ar e p ro c e s s e d i n a r a n d o m f a s hio n (ti m e wi s e). T h a t i s t o s a y t h at t h e s h uffli n g ra n d o m ly s e le c ts a n d e x tra c ts a c e rta in c o e ffici e n t fro m th e s trin g o f b its (e .g . y 3 ,27 ) a n d c o p ie s it to th e e x p e c te d ta rg e t (c o e ffic ie n t y 3 ,27 s to ra g e ), th e n ra n d o m ly s el e c t s a n d e x tra c ts a n ot h er c o e ffici e nt fro m th e s trin g o f b its (e .g . y 4 ,93 ) a n d c o p ie s it to th e e x p e c te d ta rg e t (c o e ffic ie n t y 4 ,93 s to ra g e ) a n d c o nti n u e s u ntil all c o effi c i e nt s h a v e b e e n e x tra c te d a n d c o p ie d . T h i s alter n ati v e s h uffli n g m a y b e a d v a n ta g e o u s fo r d e te rm in is tic D ilith iu m , fo r w h ic h n o t c h a n g in g th e o rd e r o f th e c o e ffic ie nt s a llo w s c o m p ly in g w ith N IS T te s t v e c to rs . T h e p o te n tia l n o n -c o m p lia n c e o f t h e s h u fflin g o f F ig u re 4 (w ith N IS T te s t v e c to rs ) is n o t a n is s u e fro m a s e c u rity s ta n d p o in t b u t m a y r e q uir e e x pl a n a ti on s a n d / or t we a k s t o re a s s ur e e ntit i e s r elyi n g o n NI S T t e st v e ct or s w h e n a s s e s s in g a p a rtic u la r D ilith iu m im p le m e n ta tio n . A lth o u g h a t th e p re s e n t s ta g e , th e re s e e m s to b e n o p ra c tic a l d iffe re n c e b e tw e e n t h e s e c u rity o f th e tw o s h u fflin g m e th o d s a b o v e , th e s h u fflin g o f F ig u re 4 m a y b e m or e ro b u s t (fr o m a th e or et i c al p er s p e cti v e) t h an t he v ari a nt . T h e r e i s n o diff er e n c e s o l o n g a s t h e r a n d o m s o ur c e u s e d f or g e n e r ati ng t h e st ri n g of bit s is r o bu st i n t h e fir st pl a c e. If at a n y ti m e, h o w e ve r, s o m e w e a k n e s s e s w e re d is c o v e re d in th is ra n d o m s o u rc e , th e s h u fflin g o f F ig u re 4 w o u ld a d d a n o th e r la y e r o f ra n d o m n e s s b y c h a n g in g th e o rd e r o f th e c o e ffic ie n ts , w h ic h m a y re n d e r th e m m o re ro b u s t. A c c o r di n g t o a firs t e m b o di m e nt, a m et h o d i s pr op o s e d t o i m pr o v e t h e s e c urit y of a cr y pt o gr a p hi c d e vi c e w hil e mi ni mi zi n g t h e d e c el er ati o n of t h e cr y pt o gr a p hi c d e vi c e d u e t o i m pr o vi n g t h e s e c urit y of t he cr y pt o gr a p hi c d e vi c e . Im p ro v in g th e s e c u rity re q u ire s ta k in g e x tra s te p s , i.e . re d u c e d p e rfo rm a n c e (in te rm s o f s p e e d ). H o w e v e r, b y re u s in g a lr e a d y a v a ila b le in fo rm a tio n , th e m e th o d i s a bl e t o li mit t h e p erf or m an c e re d u c tio n , a s will b e s e e n b e l o w. T h e c r ypt o gr a p hi c d e vi c e c o m pri s e s at l e a st o n e el e ctr o ni c c hi p ( e. g. pro c e s s or c o re , o r s e t o f p ro c e s s o r c o re s ) to c arr y o ut a Dilit hi u m o p er ati o n i n v ol vi n g a v e ct or y of p ol y n o mi al s y i wit h c o effi ci e nt s y i,j. A c c or d i n g t o a pr ef erre d e m b o di m e nt, s a id D ilit hiu m i s a d et er m i ni sti c Dilit hi u m (a s o p p o s e d t o a r a n d o miz e d Di lit hi um) . T h e m et h o d c o m pri s e s t h e cr y pt o gr a p hi c d e vi c e g e n er a ti n g t h e v e ct or y fr o m a r a n d o m s e e d (a t th a t s ta g e , t he v e c t or i s i n t he f or m of a bit stri n g , i. e. t h e v ari o u s p art s of t h e v e ct or ar e n ot e a sil y a c c e s si bl e a s a c c e s s t o t h e s e p art s r eq uir e s u n p a c ki n g). T h e m et h o d c o m pri s e s t h e cr y pt o gr a p hi c d e vi c e u n p a c ki n g t h e v e ct or y fr o m t h e bit stri n g . H o w e v e r, th is is n o t a s ta n d a rd u n p a c k in g (w h i c h w o ul d b e w e a k , fro m a s id e c h a n n e l a tta c k s ta n d p o in t). In s te a d , th e m et h o d f urt h er c o m pri s e s t h e cr y pt o g r a p hi c d e vi c e r e u si n g t h e r a n d o m s e e d (th a t w a s u s e d to g e n e ra te y ) t o ra n d o ml y s h uf fl e t h e u n p a c ki n g of v e ct or y, t h er e b y f urt h er s e c uri n g t h e Dilit hi u m o p er a ti o n w hil e s p ari n g a r a n d o m n u m b er g e n er ati o n . T h e ra n d o m s e e d i s p r ef er a bl y t h e p ar a m et er ρ′ o f th e D ilith iu m s p e c ific a tio n a s ill u str at e d i n Fi g ur e 3 ( a n d a c c o m p a n yi n g d e s cri pt i o n). In st e a d o f usi n g ρ′ (o r m o re g e n e ra lly th e s e e d ) d ire c tly , it i s al s o p o s si bl e t o u s e d at a g e n er at e d f r o m ρ′ (or fr om a n y ot h e r a p pr o p ri at e s e e d) s u c h a s t h e st rin g of b its o f lin e 14 o f th e D ilith iu m s p e c ifi c ati on p s e u d o c o d e u s e d to g e n e ra te v e c to r y (d is c u s s e d a b o v e ). F o r e x a m p le , if 10 b its a re n e e d e d fo r th e s e e d , th e firs t 10 b it s of p a ra m e te r ρ′ (o r o f a s trin g o f b its g e n e ra te d fro m ρ′ ) c a n b e u s e d a s a s e e d fo r th e s h u fflin g . F ro m a n att a c k e r’ s sta n d p o i nt, t o e n s ur e t h e c orr e ct n e s s of t h e li n e ar s y st e m ( a n d fo r t h e att a c k t o b e eff e cti v e), it i s n e c e s s ar y t o k n o w w hi c h c o effi ci e nts of w hi c h p ol y n o mi al a re n ull . H o w e v e r, b y u n p a c ki n g t h e c o effi ci e nt s i n a r a n d o m or d er at e a c h e x e c uti o n , th e in v e n tio n pr e v e nt s a n att a c k er fr o m b uil d i n g a c orr e ct lin e a r s y st e m (si n c e t he att a c k er h a s n o i nf or m ati o n a b o u t t h e e x e c uti o n or d er ). It is p a rtic u la rly a d v a n ta g e o u s to re u s e a s e e d a n d th e re fo re n o t re q u ire a n e w ra n d o m n u m b e r g e n e ra tio n , e s p e c iall y in th e c a s e o f a d et e rm in is tic a s o p p o s e d to ra n d o m iz e d im p le m e n ta tio n . I nd e e d, th e s ig n a tu re s c h e m e th e n d o e s n ot e v e n re q u ire a ra n d o m n u m b er g e n er at or f or co m p uti n g si g n at ur e s (w h ic h d o e s n o t m e a n th a t a d e te rm ini sti c D ilit hi um d e vi c e i s pr e v e nt e d fr o m h a vi n g a r a n d o m n u m b e r ge n e ra t or – t hi s r em ai n s a p o s si bi lit y). D e te rm ini sti c D ilit hi um st ill d o e s r e q uir e a r a n d o m n u m b er g e n er at or f or g e n er ati n g a k e y p a ir, b ut t h e k e y p air g e n er a ti o n t as k c a n s o m eti m e s b e h a n dl e d b y a d iffe re n t d e v ic e . F o r e x a m pl e, k e y g e n e r ati o n m a y b e c a rrie d o u t in a n H S M (h a rd w a re s e c u rity m o d u le ), i.e . s o m e p o w e rfu l p ie c e o f c ry p to g ra p h ic e q u ip m e n t th a t c a n b e k e p t in s e c u re p re m is e s (it is lik e a s e rv e r b u t w ith c ry p to g ra p h ic a c c e le ra tio n a n d v e ry h ig h p h y s ic a l a n d lo g ic a l s e c urit y i m pl e m e nt e d ). G e n e r at e d k e y p air s c a n t h e n b e s e nt t o d e vi c e s t h at w ill be u si n g t h em to a ut h e nt ic at e or s i g n wit h t h e r es p e cti v e k e y p a ir i n q u e sti o n . S u c h d e v i c es m a y b e s m a ll t o k e ns s u c h a s a p er s o n a l s e c uri t y d e v ic e s (c ry p to g ra p h ic s m a rt c a rd s , U S B s e c u rity to k e n s , Io T d e v ic e s w ith s e c u rity re q u ire m e n ts , e tc .). E a c h k e y p a ir c a n b e s e n t ( e. g. fr om s u c h H S M ) to a r e s p e cti v e d e v ic e s e c ur e l y, e. g. i n e n cr y p t e d f or m, o v er a n et w or k, or t h e r e s pe cti v e d e vi c e s m a y b e c o n fi g ure d o n s e c u r e pr e mi s e s (s u c h a s a s e c u r e f act or y w h er e t h e k e y s c o ul d b e lo a d e d w ith o u t a n y ris k o f b e in g h a c k e d ) b e f or e b ei n g pr o v i d e d to t he e n d u s e rs . A s e c u re fa c to ry is o n e th a t p u ts in p la c e a c c e s s c o n tro l to p re v e n t u n a u th o riz e d th ird p a rtie s o n s ite , a n d h a s p ro c e s s e s in pl a c e to p ro te c t its a c tiv iti e s fr o m p ot e nti al h a c k er s . In th is c a s e (a b s e n c e o f a ra n d o m n u m b e r g e n e ra to r i n t h e d e v i c e i mpl e m e n tin g th e d e te rm ini sti c D ilit hi um a c c o rd in g to th e in v e n tio n ), th e re is n o t o n ly a n a c c el er ati o n d u e to th e a b s e n c e of n e e d to g e n e ra te a ra n d o m n u m b e r (g e n e ra tin g c ry p to g ra p h ic a lly s e c u re ra n d o m n u m b e rs is a c o m p le x a n d l o n g ta s k ), b u t a ls o a n o p tim iz a tio n if th e ra n d o m n u m b er g e n e r at or c a n b e di s p e n s e d wit h alt o g et h er ( a si d e fr o m not b e in g u s e d ), le a di n g t o a s m a ll er el e ctr o ni c c hi p , l e s s p ow e r co n s u m pti o n, et c . It i s n ot ed th at b y a b s e n c e o f ra n d o m n u m b e r g e n e ra to r, it is to b e u n d er st o o d th a t th e re is n o c ry p to g ra p h ic a lly s u ita b le ra n d o m n u m b e r g e n e ra to r. T h e re c a n b e , h o w e v e r, a n d th e re ty p ic a lly is , a p s e u d o ra n d o m g e n e ra to r, s u c h a s a lin e a r c o n gr u e nti al g e n e ra to r. S u c h g e n er at or s c a n q ui c k ly a n d e a si l y g e n e r at e s e q u e n c e s of n u m b er s w hi c h , t o a h u m a n , l o o k li k e r a n d o m. S u c h s e q u e n c e s h a v e m at h e m ati c al pr o p er ti e s r e n de rin g th e m p re d ic ta b le b y a p ro p e rly c o n fig u re d m a c h in e a n d a re n o t s u ita b le fo r o th e rw is e u n p ro te c te d s e n s itiv e c ry p to g ra p h ic o p e ra tio n s . T h e a b s e n c e of a c tu al g e n e ra tio n o f a ra n d o m n u m b e r in th e c o n te x t o f th e s h uf fli n g of t h e u n p a c k i n g o p er ati o n of v ec t or y d uri n g a Dilit hi u m o p er ati o n is , a lo n e , a d v a n ta g e o u s (i.e . e v e n if a ro b u s t ra n d o m n u m b e r g e n e ra to r is p re s e n t in th e el e ctr o ni c c h ip a n d p o s s ib ly u s e d fo r o th e r p u rp o s e s ). H ar d w ar e r a n d o m n u m b er g en er at or s (“H R N G ”) u s u all y g e n er at e a c ry p to g ra p h ic a lly s e c u re r a n d o m w or d i n a f e w d o z e n s of cl o c k c y cl e s w hil e s oft w ar e cr y pt o gr a p h i c all y s e c ur e p s e u do r a n d o m n u m b er g e n er at or s ( “C S P R N G ”) t y pi c all y r e q uir e h u n dr e d s t o t h o u s a n d s o f cl o c k c y cl e s to g e n e ra te th e s a m e s iz e o f ra n d o m w o rd . F or i n st a n c e, t h e H R N G o f t h e S T M 32 F 407 mi cr o c o ntr oll er g u ar a nt e e s a n e w 32 -bit r a n d o m w or d e v er y 40 cl o c k c y cl e s w hil e ar c 4r a n d o m (a C S P R N G b a s e d o n C h a C h a 20 ) r e q uir e s ar o u n d 600 c lo c k c y cl e s t o g e n erat e a 32 -b it ra n d o m w o r d. T h e l att er i s b a s e d o n ar c 4r a n d o m fro m O p e n B S D 7.2, 53 r d r el e a s e, O ct o b er 20, 2022. T h e ar c 4r a n d o m C S P R N G h a s b e e n p ro v id e d b y O p e n B S D fo r y e a rs b u t h a s e v o lv e d o v e r tim e . It is p a rt of a C li br ar y ( s t dli b) a n d i s a s e c ur e a lt er n ati v e t o t he d ef a u lt r a n d f un cti o n of t hi s li br ar y ( w hi c h i s a w e a k b ut f a st p s e u d or a n d o m g e n er at or). H R N G s a re n o t a lw a y s a v a ila bl e o n a g iv e n d e vi c e , b u t w h e n t h e y ar e n ot, a C S P R N G mi g ht b e a v ail a bl e (al t h ou g h t h e y mi g ht b e v er y sl o w) . In a d d itio n , e v e n H R N G s a re s o m e tim e s m u c h s lo w e r th a n s ta te d a b o v e , a n d c a n e v e n b e b lo c k e d a t tim e s . F o r e x a m p le , a H R N G m a y r el y o n o utsi d e i n p ut s ( s u c h a s m o u s e m o v e m e nt s b y a h u m a n u s er , o r a n a l y si s of t i mi n g of k e y s p r e s s e d b y a h u m a n u s er of a c o m p ut er k e y b o ar d ). T hi s i s c o m m o n o n p er s o n al c o m p ut e rs , but l e s s s o i n e m b e d de d d e vi c e s. I n s u c h a c a s e, w h e n s o m e s of t w ar e a p pli c ati o n r e q uir e s a l ot of r a n d o m n u m b e r s, sit u ati o n s m a y ari s e w h er e t h er e i s n ot e n o u g h i n p ut ( e. g. t h e u s er di dn ’t m o v e th e m o u s e e n o u g h o r d id n ’t p re s s e n o u g h k e y b o a rd k e y s ). In s u c h a c a s e th e H R N G is s u s p e n d e d u n til m or e in p u t is re c e iv e d . U n til th e n , th e w h o le p ro c e s s in g is s ta lle d . T h is k in d o f is s u e s c a n n o t h a p p e n w ith th e in v e n tio n , at l e a st n ot f or t h e u n p a c ki n g st e p, si n c e t h e u n p ac ki n g rel i e s o n alr e a d y a v ail a bl e r a n d o m n e s s. R e u s in g ra n d o m n u m b e rs in c ry p to g ra p hi c al g orit h m s i s u s u all y n ot r e co m m e n d e d . In t h e c o nt e xt of t h i s d e s cr i ptio n t ho u g h , th e r an d o m s e e d is D ilit hi u m r a n d o m n e s s (i. e. ra n d o m n u m b e r s aff e cti n g t h e o u tp u t o f th e c o m p ut a tio n o f a D ilit hi u m o p e ra tio n ) o r d e riv e d fro m D ilith iu m ra n d o m n e s s . A c c o rd in g to th e in v e n tio n , th e ra n d o m s e e d c a n b e r e u s e d in d e te rm in is tic o r ra n d o m iz e d D ilith iu m , t o c a rry o u t a s h u fflin g , w h e th e r it is th e s h u fflin g o f F ig u re 4 o r a n a lte rn a tiv e s h u fflin g s er v in g m e re i m pl e m e nt ati o n p ur p o s e s ( a s in t he alt er n ati v e d et ail e d i n t h e d e s cri pt i o n of Fi g ur e 4) . S er v in g im p l e m e ntati o n p ur p o s e s is to b e u n d e rs to o d a s m e a n in g th a t D ilith iu m ra n d o m n e s s is re u s e d to a ffe c t th e m a n n e r in w h ic h th e D ilith iu m c o m p u ta tio n is c a rrie d o u t ( a s o p p o s e d t o its o u tc o m e ). S u c h r e u s e h a s b e e n a s s e s s e d t o b e s o u n d w h e n a p pli e d t o t h e s h uffli n g c o u nt erm e a s ur e (in c lu d in g th e o n e o f F ig ur e 4) . It is n o te d th a t fo r a D ilith iu m s ig n a tu re , t h e r a n d o m s e e d c h a n g e s at e a c h si g n at ur e o p er ati o n a n d i s d e e m e d u n pr e di ct a bl e b y a n att a c k er h a v in g n o i nf or m ati o n a b o ut t h e pri v at e k e y . A c c o rd in g to a s e c o n d e m b o d im e n t, t h e Dilit hi u m o per ati o n o f th e m et h o d o f th e firs t e m b o d im e n t c o m pri s e s c o m p uti n g a Dilit hi u m di git al si g n at ur e of t h e f or m z = y + c s 1. H o w e v er, ot h er o p er ati o n s c a n al s o b e pr ot e c t e d b y t h e i n v e nti o n, f or e x am pl e t h e c o m p ut a tio n of A y m a y b e c arri e d o ut b y s h uffli n g th e u n p a c k in g o f y , s im ila r to w h a t h a s b e e n d e s c rib e d fo r th e c o m p u ta tio n o f z = y + c s 1. A c c or di n g t o a t hir d e m b o d i m e nt, th e m et h o d of t h e fir st or s e c o n d e m b o d im e nt c o m pri s e s t h e cr y pt o gr a p hi c d e vi c e r e u sin g t h e r a n d o m s e e d t o r a n d o ml y s h uffl e t h e u n pa c ki n g of t h e v e ct or y b y c h a n gi n g t h e or d er i n w hi c h t h e p ol y n o mi al s yi wit hi n t h e v e ct or y ar e pr o c e s s e d. A c c o rd in g ly , th e m e th o d m a y s ta rt fro m a p o ly n o m ia l (s e le c te d ra n d o m ly ) o th er t h a n y 1 , a n d th e n e x t o n e , u p to th e fo u rth p o ly n o mi al ( w h e n t h er e ar e f o ur p ol y n o mi al s), is e a c h tim e c h o s e n r a n d o ml y. It i s b e st t o n ot o nly c h a n g e t h e or d er of t h e p ol y n o m i al s b ut t o s h uffl e a s m u c h a s p o s s ib le . T h is , h o w e v e r, re q u ire s m o re p ro c e s s in g . A c c o rd in g to a fo u rth e m b o d im e n t, th e m et h o d a c c or di n g t o a n y o f t h e firs t t o thir d e m b o di m e nt s c o m pri s e s t h e cr y pt o gr a p hi c d e vi c e r e u si n g t h e r a n d o m s e e d t o r a n d o ml y s h uffl e t h e u n p a c ki n g of t h e v e ct or y b y c h a n gi n g t h e or d er i n w hi c h p ol y n o mi al s c o effi ci e nt s yi,j wit hi n e a c h p ol y n o mi al y i of t h e v e ct or y ar e pr o c e s s e d. A c c o rd in g ly , th e o rd e r o f t h e c o e ffic ie n ts o f a g iv e n p o ly n o m ia l is n o t th e d e fa u lt o rd e r s u c h a s y 1 ,1 , y 1 ,2 , y 1 ,3 , e tc . b u t a ra n d o m o rd e r. It i s b e st t o n ot o nly c h a n g e t h e or d er of t h e c o effi c i e nt s b ut t o s h uffl e a s m u c h a s p o s s ib le . T h is , h o w e v e r, re q u ire s m o re p ro c e s s in g . O n e p r ef err e d e m b o di m e nt c o n si st s i n c o m bi ni n g t h e t hir d a n d f o ur t h e m b o di m e nt s to s h u ffle n o t o n ly th e p o ly n o m ia ls b u t a ls o th e ir c o e ffi ci e nt s. A c c or di n g t o a fifth e m b o d im e n t, th e m et h o d a c c or di n g t o a n y o f th e firs t to f o urt h e m b o di m e n t s c o m pri s e s s e c uri n g at l e a st o n e o t h er Dilit hi u m o p er ati o n b y u si n g diff er e nt p art s of t h e r a n d o m s e e d (o r, a lte rn a tiv e ly d iffe re n t p a rts o f d a ta d e riv e d fro m th e ra n d o m s e e d ) f or e a ch Dilit hi u m o p er ati o n. F o r e x a m pl e , th e m e th o d m a y s e c u re o n th e o n e h a n d th e c o m p u ta tio n o f A y , o n th e o th e r h a n d th e c o m p u ta tio n o f z = y + c s 1 , a n d m a y u n p a c k y tw ic e , o n c e fo r th e firs t o p e ra tio n a n d a n o th e r tim e fo r th e s e c o n d o p e r ati o n, i n w hi c h c a s e it i s a d v a nt a g e o us t o u s e a di ff er e nt s h uff li n g e a c h ti m e . T hi s c a n b e a c hi e v ed b y u si n g diff er e nt p art s of t h e r a nd o m s e e d . F o r e x a m p le , th e ra n d o m s e e d ρ′ illu s tra te d in lin e 12 o f F i g ur e 4, p a g e 13 of Dilit hi u m s p e cifi c ati o n (d is c u s s e d a b o v e ) is a 384 -b it s e e d , w hil e a s little a s 10 b its m a y b e e n o u g h fo r s o m e s h u fflin g . It mi g ht s e e m od d, at fir st, t o u n p a c k t h e v e ct or y twi c e i n st e a d of m er el y u n p a c ki n g it o n c e f or all a n d u si n g it s e v e ra l ti m e s if n e e d e d . H o w e v e r, c e rta in d e v ic e s (c e rta in Io T d e v ic e s , c e rta in s m a rt c a rd s , c e rta in re s o u rc e c o n s tra in e d to k e n s ) h a v e s o little m e m o ry th a t th e y c a n n o t m a in ta in th e u n p a c k e d v e c to r y in m e m o ry w h ile c a rry in g o u t o th e r ta s k s w h ic h re q u ire s o m e m e m o ry to o . I n s u c h i n s t a n c e s, i n w hi c h s e v er al u n p a c ki n g o p er ati o n s ar e n e e d e d, it is a d v a nt a g e o u s t o pr ot e ct t h e m a s s ta te d a b o v e in o rd e r to a v o id fa c ilita tin g a n att a c k th a t w o u ld h a v e b e e n b a s e d o n a s a m e s h u fflin g b e in g c a rrie d o u t tw ic e (e n a b lin g p o s s ib ly re le v a n t c o m p a ris o n s , s ta tis tic s e tc .). A c c or di n g t o a si xt h e m b o d im e n t, th e m e t h o d a c c or di n g t o a n y o f th e firs t to fifth e m b o di m e n t s c o m pri s e s th e cr y pt o gr a p hi c d e vi c e s h uffli n g o r d er e d el e m e nt s i d e ntifi e d b y a n i n d e x i (t o b e u n d er st o o d a s: a t l e a st o n e i n d e x), b y r e pl a cin g t h e i n d e x i (o r in d e x e s ) b y a n ot h er i n d e x j (o r in d e x e s ), w h er e t h e ot h er i n d e x j (o r in d e x e s ) i s e q u al t o t h e “e x cl u si v e or ” of t h e i n d e x i (o r in d e x e s ) wit h inf or m a ti o n d eri v e d fr o m t h e r a n d o m s e e d. T h e i nf or m a ti on d e ri ve d s h o u l d h a ve t h e s a m e n u m b e r of bit s a s t h e in d e x (e s) . T h e in fo rm a tio n d e riv e d m a y b e a ll o f th e ra n d o m s e e d if t h e i n de x h a s t h e s a m e si z e a s t h e r a n d om s e e d , p art of th e ra n d o m s e e d it if it i s s h orte r, o r, a lte rn a tiv e ly , in fo rm a tio n c o m p u te d fro m th e ra n d o m s e e d . T hi s i s a d v a nt a g e o u s c o m p ar e d t o a s ol uti o n w hi c h w o u l d r el y f or e x a mpl e o n t h e Fi s h er -Y at e s te c h n iq u e . T h e latt er h a s a si g nifi c a nt i m p a ct o n p er f or m a n c e si n c e it r e q uir e s a s m a n y r a n d o m n u m b er s a s th e re a re o p er ati o n s t o s h uffl e (le t’s r ef er to th is n u m b e r a s n ), a n d m a n y m e m or y a c c e s s e s ( 4 n l o a d s a n d 2 n s t or e s). T h a t s a id , Fi s h er -Y at e s m ig h t b e a d v a n ta g e o u s a t tim e s , b e c a u s e it is a b le to g e n e ra te a g re a te r n u m b er o f p e rm u ta tio n s (a n d is th e re fo re h a rd e r to p re d ic t b y a n a tta c k e r). A c c o rd in g to a n alt er n a ti v e e m b o di m e nt of th e i n v e nti o n, w h e n a n e xi s ti n g s o ur c e of ra n d o m n e s s h a s pr o v i d ed e n o u g h r eu s a bl e r a n d o m d a ta b ef o re h a n d , wit h o ut h a vi n g t o g e n er at e a n y f urt h er r a n d o mn e s s f or Fi s c h er - Y at e s t o o p er at e, Fi s c h er -Y at e s i s u s e d. T h e si xt h e m b o d i m e nt w or k s w h e n n i s a p o w er of 2 (th e F is c h e r-Y a te s a lte rn a tiv e d o e s n o t h a v e th is c o n s tra in t). M or e s p e c ifi c all y, t he p ar t of t he r a nd o m s e e d t o b e X O R e d wit h th e i n d e x m u st h a v e t h e s a m e n u m b er of bi t s a s t h e n u m b er of b it s r e qu ir ed t o e n c o d e th e i n d e x. U n d er t hi s c o n diti o n, th e s h uff li n g i s e xtr e m el y f a st a n d r e quir e s littl e r e s o ur c e s. H o w e v e r, s u c h s h uffli n g o nl y p er mit s n p er m u t ati o n s o ut of n! (i. e. n*(n -1)*( n -2)* … * 3 * 2 p o s s ib le p er m ut ati o n s ), w h ic h is a rg u a b ly le s s s e c u re (le s s u n p re d ic ta bl e ). F o r e x a m p le , l et’s c o n s id e r a s trin g o f b its of L × N × n bit s, fro m w h ic h it is d e s ire d to u n p a c k L p ol y n o mi al s y 0 … y L − 1 w ith N n -bit c o effi ci e nt s e a c h . F o r D ilith iu m 2 , w e m a y h a v e L = 4, N = 256 a n d n = 18 (18 b its p e r c o e ffic i e nt). It is p o s si bl e t o a r bitr arily s el e ct l o g ( 4 × 256) = 10 bit s of th e stri n g o f bit s a s a p a r am et er r ( e. g. t h e fir st 10 bit s of th e stri n g o f bit s ), o r to u s e 10 b it s fro m t h e s e e d u s e d to g e n e ra te y . T h e n , th e m e th o d m a y u n p a c k c o effi ci e nt y (i⊕ r)/ N,(i⊕ r)% N , w h e re (i⊕ r)/ N d e s ig n a te s th e in te g e r d iv is io n o f i X O R r b y N , a n d (i⊕ r) % N d e s ig n a te s th e re m a in d e r (m o d u lo ) o f th e in te g e r d iv is io n o f i X O R r b y N . T h er e ar e 2 10 = 1024 diff er e nt p o s si biliti e s f or t h e or d er i n w hi c h t h e c o effi ci e nt s a r e s h uffl e d, wit h o ut r e q uiri n g a r a n d o m n u m b er. A c c or di n g t o a s e v e n th e m b o d im e n t, th e m et h o d a c c or di n g t o a n y o f th e firs t to fifth e m b o di m e n t s c o m pri s e s t h e cr y pt o gr a p hi c d e vi c e s h uffli n g or d er e d el e m e nt s i d e ntifi e d b y a n i n d e x i (t o b e u n d er st o o d a s: a t l e a st o n e i n d e x), b y r e pl a ci n g t h e i n d e x i (o r in d e x e s ) b y a n ot h er i n d e x j (o r in d e x e s ), w h er e t h e ot h er i n d e x j (o r in d e x e s ) i s e q u al t o t h e i t h it er ati on of a li n e ar c o n gr u e nti al g e n er at or ( L C G) i niti ali z e d b a s e d o n th e ra n d o m s e e d , i.e . wit h a ll o r p art of t h e r a n d o m s ee d (o r a n u m b e r d e riv e d th e re fro m ). A n L C G i s d efi n e d b y X n + 1 = ( a X n + c) m o d m w h er e X 0 r ef er s t o t h e i niti al st at e (c a n u s e a ra n d o m s e e d fo r X 0 a s p ro p o s e d h e re ). A c c o rd in g to a firs t o p tio n , p a ra m e te r m is s e t to b e a p o w e r o f 2 , p a ra m e te r a c a n b e a n y o bt ai n e d b y pi c ki n g a′ ∈ [ 0, m /4 − 1] (w h ic h c a n b e a c h ie v e b y u s in g th e a lre a d y d is c u s s e d ra n d o m s e e d ρ′ o f th e Dilit hi u m s p e cifi c ati o n , e. g. b y c o m p ut i n g ρ′ % (m/ 4 ), w h er e % r efer s t o t h e m o d ul o o p e r at or) a n d c o m p uti n g a = 4 a′ + 1. P a ra m e te r c c a n b e a n y o d d n u m b er . T h is firs t o p tio n a llo w s fo r m 3 /8 p e rm u ta tio n s . A c c o rd in g to a s e c o n d o p tio n , c i s c h o s e n t o b e r el ati v el y pri m e t o m, a s u c h t h at 2 a − 1 i s di vi si bl e b y all pri m e f a ct or s of m a n d 3 a − 1 i s di vi si bl e b y 4 if m i s di vi si bl e b y 4. A c c o rd in g to a n e ig h th e m b o d im e n t, a cr y pt o gr a p hi c d e vi c e c o m pri s e s at l e a st o n e el e ctr o ni c c hi p t o c arry o ut a Dilit hi u m o p er ati o n i n v ol vi n g a v e ct or y of p ol y n o mi al s y i wit h c o effi ci e nt s y i,j. T h e cr y pt o gr a p hi c d e vi c e i s arr a n g e d t o g e n er at e t h e v e ct or y fr o m a r a n d o m s e e d a n d t o u n p a c k t h e v e ct or y fr o m a bit stri n g . T h e cr y pt o gr a p hi c d e vi c e i s f urt h er arr a n g e d t o r e u s e t h e r a n d o m s e e d t o r a n d o ml y s h uffl e t h e u n p a c ki n g of t h e v e ct or y, t h er e b y f urt h er s e c uri n g t h e Dilit hi u m o p er ati o n w hil e s p ari n g a r a n d o m n u m b er g e n er ati o n. R e m ar k s m a d e w it h r es p e ct t o t h e fir st e m b o di m e nt e q u all y a ppl y t o t h e ei g ht h e m b o d im e n t. A c c o rd in g to a n in th e m b o d im e n t, t h e Dilit hi u m o p er ati o n o f th e cr y pt o gr a p hi c d e vi c e o f th e e ig h th e m b o di m e n t c o m pri s e s c o m p uti n g a Dilit hi u m di git al si g n at ur e of t h e f or m z = y + c s 1. R e m ar k s m a d e wit h r e s p e ct t o t h e s e c o n d e m b o di m e nt e q u all y a p pl y t o t h e n in th e m b o d im e n t. A c c o rd in g to a t e nt h e m b o d im e n t, th e cr y pt o gr a p hi c d e vi c e a c c or di n g t o t h e ei ght h or n in th e m b o di m e n t s i s arr a n g e d t o r e us e t h e r a n d o m s e e d t o r a n d o ml y s h uffle t h e u n p a c ki n g of t h e v e ct or y b y c h a n gi n g t he or d er i n w hi c h t h e p ol y n o mi al s yi wit hi n t h e v e ct or y ar e pr o c e s s e d. R e m ar k s m a d e wit h r e s p e ct t o t h e th ird e m b o di m e nt e q u all y a p pl y t o t h e te n th e m b o d im e n t. A c c o rd in g to a n el e v e nt h e m b o d im e n t, th e cr y pt o gr a p hi c d e vi c e a c c or di n g t o a n y of t h e ei ght h t o t e nt h e m b o d i me n t s i s arr a n g e d t o r e u s e t h e r a n d o m s e e d t o r a n d o ml y s h uffl e th e u n p a c ki n g of t h e v e ct or y b y c h a n gi n g t h e or d er i n w hi c h p ol y n o mi al s c o effi ci e nt s yi,j wit hi n e a c h p ol y n o mi al y i of t h e v e ct or y a r e pr oc e s s e d. R e m ar k s m a d e wit h r e s p e ct t o t h e fo u rth e m b o di m e nt e q u all y a p pl y t o t h e e le v e n th e m b o d im e n t. A c c o rd in g to a t w elft h e m b o d im e n t, th e cr y pt o gr a p hi c d e vi c e a c c or di n g t o a n y of t h e ei ght h t o el e v e nt h e m b o d i me n t s i s arr a n g e d t o s e c ur e at l e a st o ne ot h e r Dilit hi u m o p erati o n b y u si n g diff er e nt p art s of t h e r a n d o m s e e d f or e a c h Dilit hi u m o p er ati o n. R e m ar k s m a d e wit h r e s p e ct t o t h e fifth e m b o di m e nt e q u all y a p pl y t o t h e t w elft h e m b o d im e n t. A c c o rd in g to a th irte e n th e m b o d im e n t, th e cr y pt o gr a p hi c d e vi c e a c c or di n g t o a n y of t h e ei ght h t o t w elft h e m b o d im e n ts i s arr a n g e d t o s h uffl e or d er e d el e m e nt s i d e ntifi e d b y a n i n d e x i, b y r e pl a ci n g t h e i n d e x i b y a n ot h er i n d e x j, w h er e t h e ot h er i n d e x j i s e q u al t o t h e e x cl u si v e or of t h e i n d e x i wit h in fo rm a tio n d e riv e d fro m t h e r a n d om s e e d . R e m ar k s m a d e wit h r e s p e ct t o t h e si xt h e m b o di m e nt e q u all y a p pl y t o t h e th irte e n th e m b o d im e n t. A c c o rd in g to a fo u rte e n th e m b o d im e n t, th e cr y pt o gr a p hi c d e vi c e a c c or di n g t o a n y of t h e ei gh t h t o t w elft h e m b o d im e n ts i s arr a n g e d t o s h uffl e or d er e d el e m e nt s i d e ntifi e d b y a n i n d e x i, b y r e pl a ci n g t h e i n d e x i b y a n ot h er i n d e x j, w h er e t h e ot h er i n d e x j i s e q u al t o t h e i t h it erati o n of a li n e ar c o n gr u e nti al g e n er at or i niti ali z e d b a s e d o n t h e r a n d o m s e e d. R e m ar k s m a d e wit h r e s p e ct t o t h e s e v e n t h e m b o di m e n t e q u all y a p pl y t o t h e fo u rte e n th e m b o d im e n t. A c c or di n g t o a fift ee nt h e m b o di m e nt, a c o m p ut er pr o gr a m c o m pri s e s a s e q u e n c e of i n str u cti o n s i m pl e m e nti n g t h e st e p s of t h e m et h o d a c c or di n g t o o n e of t h e fir st t o s e v e n th e m b o di m e nt s w h e n e x e c ut e d b y a pr o c e s s or. T h i s pr o gr a m i s writt e n, f or e x a m pl e, i n a s s e m bl y l a n g u a g e, or i n C l a n g u a g e. S u c h l o w-l e v el l a n g u a g e s ar e a d v a nt a g e o u s i n t h at t h e y all o w fi n e o pti mi z ati o n a n d all o w c o u nt er m e a s ur e s t o b e i m pl e m e nt e d m or e effi ci e nt l y. Hi g h er l e v el l a n g ua g e s m a y b e p o s si bl e b ut g e n er all y d e gr a d e p erf or m a n c e a n d d o n ot n e c e s s aril y all o w f or effi ci e nt c o u nt er m e a s ur e s. A c c or di n g t o a si xt e e n t h e m b o di m e nt, a n o n -tr a n sit or y c o m p ut er- r e a d a bl e st or a g e m e diu m c o m pri s e s a c o m p ut er pr o gr a m a c c or di n g t o t h e fift e en th e m b o di m e nt. T hi s s t or a g e m e di u m i s, f or e x a m pl e, a m e m or y all o wi n g p er m a n e nt st or a g e. T h e m e m or y m a y b e r e writ a bl e ( Fl a s h, E E P R O M, b att er y pr ot e ct e d R A M, or e v e n m a g n eti c or o pti c al m e di a) or n o n -re writ a bl e ( R O M, et c.). S u c h a st or a g e m e di u m c a n b e i nt e gr at e d i nt o a s m art c a r d, U S B k e y , or a n y c o m p ut er, s u c h a s a s m art p h o n e . T h e i n v e nti o n i s n ot li mit e d t o t h e e m b o di m e nt s d e s cri b e d a b o v e a s m e re e x a m pl e s. It e xt e n d s t o ot h er v ari a nt s. F o r e x a m pl e , w h ile c e rta in illu s tra ti o n s h a v e b e e n pr o vi d e d f or Dilit hi u m2 ( a n d a s s o ci at e d 18 -b it c o e ffi ci e nt s f or p ol y n o mi al s ), t h e i nv e n ti o n o p er at e s j u st a s w ell wit h ot h er v ersi o n s s u c h a s Dilit hi u m 3/ 5 ( a n d a s s o ci a t e d 20-bit c o effi ci e nt s f or p ol y n o mial s ) w hi c h c a n b e p re fe rre d fo r s e c u rity re a s o n s (m o re ro b u s t d u e to lar g er s iz e s ). T h e el e ctr o ni c c h ip (o r c h ip s ) c o nt e m pl at e d m a y e a c h b e a n y s uit a bl e el e ctr o ni c cir c uit, f or e x a m pl e a d e di c at e d el e ctr o ni c cir c uit (w h ic h m a y c o m pri s e h ar d wir e d l o gi c t o c a rr y o ut t he cl ai m e d m et h o d s wit h o u t t he n e e d f or a p ro c e s s o r a n d p o s s ib ly a t a h ig h e r s p e e d ), a n F P G A, a n A SI C, a mi cr o c o ntr oll er, a D S P, or a cir c uit c o m pri si n g a pr o c e s s or a n d a m e m or y, t h e m e m or y st ori n g a s uit a bl e c o m p ut er pr o gr a m. W h ile th e c ry p to g ra p h ic d e v ic e m a y b e a s m a rtc a rd , it c o u ld a ls o b e a T P M (tru s te d p la tfo rm m o d u le ) fo u n d o n c o m p u te r m o th e rb o a rd s (o fte n d e riv e d fr o m s m a rtc a rd te c h n o l o g y, s o m e tim e s e v e n a re g u la r s m a rtc a rd c h ip w ith e x tra fe a tu r es ). T h e cr y pt o g r a p hi c d ev i c e c o ul d al s o b e a r eg u la r p ro c e s s o r o f a s er v e r, or of a p er s o n a l c o m p u t er o r s m a rtp h o n e o r Io T d e v ic e , a rra n g e d to c a rry o u t c ry p to g ra p h ic ta s k s , p o s s ib ly c o m b in e d w ith o th e r cir c uit s (s u c h a s a B IO S o r U E F I el e ctr o ni c c o m p o n e nt s , s to rin g s p e c ific p ro g ra m s fo r t h e p u rp o s e o f c a rry i n g o ut t h e cl ai m e d m et ho d s) . U s a bl e m e m ori e s ar e n ot li mi t e d t o t h e e x a m pl e s gi v e n f or ill u str ati v e p ur p o s e s o nl y, b ut c o v er a n y f u n cti o n all y e q ui v al e nt t y p e of m e m or y. T h e e m b o di m e nt s d e s cri b e d i n c o n n e cti o n w it h t h e m et h o d s a c c or di n g to t h e i n ve nti o n c a n b e tr a n s p o s e d t o cr y pt o gr a p hi c d e vi c e s , a s w ell a s t o c o m p ut er pr o gr a m s a n d st or a g e m e di a a c c or di n g t o t h e i n v e nti o n, a n d vi c e v er s a.