AXI hardware accelerator for McEliece on FPGA embedded systems

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025 1477
AXI Ha dwa e Accele a o o McEliece
on FPGA Embedded Sys ems
En ique Can ó-Na a o and Ma iano López-Ga cía
Abs ac —This a icle p esen s a McEliece ha dwa e accele a o
designed o be a ached o an AXI in as uc u e, add essing he
e icien implemen a ion o a lexible pos -quan um c yp op oces-
so on FPGA-based embedded sys ems. The complexi y o he
a i hme ic ci cui s, combined wi h he adap abili y o di e en
applica ions by con igu able pa ame e s and un- ime ep og am-
ming, p esen s challenging issues o in eg a ing he accele a o
in o hese sys ems. The a chi ec u e o he accele a o is based
on an applica ion-speci ic ins uc ion p ocesso , which execu es a
se o cons an - ime ins uc ions om an in e nal egis e ile and
memo ies. The ole o he embedded p ocesso is educed o he
ini ial w i ing o he ins uc ion memo y o he accele a o , he
launching o he equi ed se o ins uc ions and con igu ing he
Di ec Memo y Access con olle o e ie e and s o e da a om
ex e nal memo y. The un- ime p og amming o he accele a o
p o ides high lexibili y in applica ions ha equi es pos -quan um
c yp og aphy. A se o con igu able pa ame e s pe mi s o adap
he secu i y le el o he McEliece enc yp ion-dec yp ion and he
a ea-pe o mance adeo imposed by he a ge de ice. Thus, he
accele a o can be implemen ed om low-cos o high-end FPGAs
by con igu ing he da a-wid h o DMA buses o he pa allelism le el
o he Galois-Field adde -mul iplie . Expe imen al esul s show
he accele a o is sui ed o implemen ing e icien ly he highes
secu i y pa ame e s o he Classic McEliece, achie ing a McEliece
dec yp ion speed-up om x370 o x556 and occupying a small
numbe o esou ces on a low-cos FPGA. In high-end FPGAs,
he accele a o can be con igu ed using highe secu i y pa ame e s
no achie ed in p e ious ela ed c yp op ocesso s, p o iding e en
highe accele a ions.
Index Te ms—Public key c yp osys em, eal- ime and embedded
sys ems, econ igu able ha dwa e.
I. INTRODUCTION
ASYMMETRIC c yp og aphy p o ides con iden iali y on
communica ions by dis ibu ing a public key om a pa -
ne whichisused oenc yp messages omo he pa ies,bu hey
can only be dec yp ed by he pai ed p i a e key. Public key (PK)
c yp og aphy is widely used in online se ices ha ensu e con-
iden iali y, in eg i y, au hen ica ion, o non- epudia ion. How-
e e , algo i hms o quan um compu ing ha e been p oposed o
Manusc ip ecei ed 24 July 2023; e ised 23 July 2024; accep ed 13 Augus
2024. Da e o publica ion 16 Augus 2024; da e o cu en e sion 14 Ma ch
2025. This wo k was suppo ed by MCIN/AEI/ 10.13039/501100011033 un-
de G an PID2019-107274RB-I00. (Co esponding au ho : En ique Can ó-
Na a o.)
En ique Can ó-Na a o is wi h he Elec ics, Elec onic and Au oma ic De-
pa men , Uni e si y Ro i a i Vi gili, 43007 Ta agona, Spain (e-mail: en ique.
can o@u .ca ).
Ma iano López-Ga cía is wi h he Depa men o Elec onics, Uni e si a
Poli écnica de Ca alunya, 08800 Vilano a i la Gel ú, Spain (e-mail: ma iano.
[email p o ec ed]).
Digi al Objec Iden i ie 10.1109/TDSC.2024.3445181
de ea he secu i y o widely used PK algo i hms, such as he
RSA o hose based on Ellip ic-Cu e C yp og aphy (ECC).
Pos -quan um (PQ) algo i hms applied on PK c yp og aphy
a e belie ed o be secu ed agains quan um compu e s. They
can be classi ied in o i e ca ego ies: code-based, la ice-based,
hash-based, based on mul i a ia e-quad a ic-equa ion, o based
on supe singula isogenies o ellip ic cu es. Each ca ego y has
i s ad an ages and d awbacks ha a e unde in es iga ion, bu
gene ally, he complexi y o PQ su e s om e iciency, which
has p omo ed he de elopmen o ha dwa e solu ions o imp o e
he execu ion ime. Code-based c yp og aphy, ep esen ed by
he McEliece and i s a ian s, is well-unde s ood and p o ides
easonably e icien sys ems ha ha e been de eloped.
Many implemen a ions ha e been de eloped o he Classic
McEliece (CMcE), which should no be con used wi h he
o iginal McEliece (McE) om 1978. Despi e he name, he
Classic McEliece is a NIST s anda d candida e o Key Encap-
sula ion Mechanism (KEM), ini ially p oposed in 2017 o he
NIST compe i ion. I is based on he Niede ei e algo i hm,
which is a synd ome-based dual a ian o he McE. The CMcE
eplaces he Reed-Solomon (RS) as he e o -co ec ion mecha-
nism by bina y Goppa codes. Bina y Goppa codes a e belie ed
o be pos -quan um sa e, whe eas RS has been p o en o be
insecu e. The CMcE p o ides an e icien KEM, mainly due
o sho e keys, simple key gene a ion, and synd ome-based
decoding, when compa ed wi h McE. Ne e heless, McE en-
ables la ge plain ex blocks ( housands o bi s) han in Niede -
ei e o CMcE (hund eds o bi s) using he same secu i y
pa ame e s.
P e ious wo ks in ha dwa e implemen a ions o McE a e
qui e sca ce, whe eas de elopmen s on CMcE a e much la ge
due o he p omising esul s o he NIST compe i ion. Mo e-
o e , mos o he p e iously p esen ed sys ems a e s and-alone
c yp op ocesso s on FPGAs buil om e y speci ic and ixed
compu a ional blocks, limi ing hei adap abili y o applica ions
o he han KEM. They usually assume ha keys a e al eady
loaded in o in e nal FPGA memo y, enhancing he p ocessing
speed by pa allel accessing o keys and da a. The connec i i y
wi han embeddedmic op ocesso andex e nalmemo y,pe mi -
ing changes o keys and algo i hms, is no conside ed in hei
a chi ec u e and expe imen al esul s. FPGAs a e widely used
as p o o yping pla o ms o digi al sys ems. A e alida ion,
designs may be po ed o ASIC echnology i high- olume
p oduc ion is jus i iable. Howe e , FPGAs o e he possibili y
o upda ing designs i weaknesses a e disco e ed. Fu he mo e,
pa ially econ igu able FPGAs pe mi he mapping o di e en
© 2024 The Au ho s. This wo k is licensed unde a C ea i e Commons A ibu ion-NonComme cial-NoDe i a i es 4.0 License. Fo mo e in o ma ion, see
h ps://c ea i ecommons.o g/licenses/by-nc-nd/4.0/
1478 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025
accele a o s, sha ing he same ha dwa e esou ces in a ime-
mul iplexed manne .
The p esen wo k p oposes a McE accele a o ha p o ides
in e aces o AXI buses o be in eg a ed in o an FPGA-based
embedded sys em. The accele a o has been designed om
sc a ch using a Ha dwa e Desc ip ion Language (HDL) o make
low-le el a chi ec u al decisions ocused on educing he clock
cycles and ha dwa e esou ces. I p o ides a se o ins uc ions
on bina y ec o s, ma ices, Galois-Field F2melemen s, and
polynomials F2m[Z] o accele a e he s eps ypically used in
McE enc yp ion-dec yp ion. In e nal memo ies a e dedica ed o
he s o ing o bina y ec o s and polynomials ha can be ead
o w i en om an AXI-S eam in e ace.
The con ibu ions a e summa ized as:
1. Ha dwa e accele a o o McEliece ha a aches o he
AXI in as uc u e, add essing limi a ions o p e ious
wo ks by p o iding un- ime p og ammabili y and con-
nec i i y o ex e nal memo y. I is sui able o secu i y-
sensi i e applica ions, no es ic ed o KEM, such as
biome ic ecogni ion.
2. E icien use o ha dwa e esou ces and signi ican pe -
o mance imp o emen s a e achie ed. I p o ides con-
igu able pa ame e s ha allow he selec ion o he
a ea-pe o mance adeo sui ed o he a ge FPGA and
secu i y le els ha o e come p e ious wo ks.
The nex sec ion desc ibes he main ela ed wo ks. Sec ion
III desc ibes an o e iew o he a chi ec u e, in e nal memo ies,
co es, and ins uc ion se o he accele a o . Sec ion IV desc ibes
he McE enc yp ion and dec yp ion ocusing on he p og am-
ming o he accele a o . Expe imen s esul s a e epo ed and
commen ed on in Sec ion V. Finally, conclusions a e p esen ed.
II. PREVIOUS WORKS
Mos publica ions, he c yp op ocesso connec i i y wi h an
embedded mic op ocesso and ex e nal memo y is no consid-
e ed. The e o e, he expe imen al esul s a e heo e ical exe-
cu ion imes, assuming da a and keys a e al eady loaded in
he FPGA. Addi ionally, ha dwa e esou ces used as in e ace
wi h ex e nal busses a e no included. Mos CMcE ha dwa e
implemen a ionsinclude hekeygene a ionsincei is equi edin
KEMc yp osys ems.On hecon a y,McEha dwa eimplemen-
a ions a e de o ed o accele a ing PK enc yp ion-dec yp ion,
elying on an ex e nal sys em o gene a e keys since i is an
in ensi e ask ha uns only once o each o he pa ies and
does no bene i as much om he ha dwa e [1].
The sys em p esen ed in [2] is a Niede ei e c yp op oces-
so , which p o ides high- a e enc yp ion-dec yp ion on Vi ex-6
FPGA, bu secu i y pa ame e s a e limi ed o 80-bi (n=2048,
=27,m=11).In e nalBlockRAM(BRAM)memo ies s o e he
ma ices o keys by ow-wise add essing, compu ing an en i e
ow pe clock cycle o enhance he hypo he ical pe o mance.
The epo ed simula ion esul s show as enc yp ion and dec yp-
ion ake 200 and 14.5·103clock cycles, espec i ely, assuming
ha bo h he public and p i a e keys a e al eady s o ed in he
in e nal BRAMs. Howe e , his is an un ealis ic es since keys
mus be able o change, and he au ho s ecognize ha he e is
an open p oblem wi h he in e ace’s abili y o ans e keys in o
he FPGA memo y a such high a es.
Some wo ks op imize he C-code o so wa e implemen a ion
o he CMcE, such as he McBi s [3],[4] and he speci ic ARM
Co ex-M4 implemen a ion [5]. The au ho s desc ibe se e al al-
e na i es o eplacein e nal algo i hms and o ec o izecalcula-
ions, he eby p o iding e icien execu ion on mic op ocesso s
wi h SIMD ins uc ions.
The ha dwa e CMcE implemen a ions showed in [6],[7],
[8],[9] a e based on algo i hms aken om he p e iously
commen edso wa eop imiza ions.Theyp esen edac yp op o-
cesso buil om e y specialized blocks a ge ed o accele a e
he s eps in ol ed in he KEM applica ion. The a chi ec u es
a e desc ibed in Ve ilog, and hey a e e y e icien in execu ion
ime o CMcE, bu no as much in ha dwa e esou ces. Fo
ins ance, he ime-op imized e sion o he highes secu i y
le el (n=8912, =128, m=13) [8] epo s 123·103LookUp
Tables (LUTs), 190·103Flip-Flops (FFs), 589 BRAMs on a
high-end Vi ex-7, aking 1.28·106clock cycles o gene a e a
key and 6.5·103and 26.2·103clock cycles o enc yp ion and
dec yp ion, espec i ely, assuming da a is no ead o w i en
o ex e nal memo y. The a ea-op imized e sion educes he
numbe o FPGA esou ces o 45·103LUTs and 88·103FFs
bu s ill equi es a la ge numbe o 525 BRAMs. The numbe o
clock cycles is he same o enc yp ion and inc eases o 48.8·103
o dec yp ion. The sys em [9] accele a es he ma ix sys emize
du ing he key gene a ion by p ocessing a po ion o he ma ix.
I is based on he sys emize o [10], bu pe mi ing he ea ly
abo ing when i de ec s ha he ma ix is no sys emizable. The
la ge numbe o BRAMs does no allow i s implemen a ion on
low-cos FPGAs, lacking he lexibili y o be adap able o o he
applica ions di e en han KEM since i does no p o ide ex e -
nal memo y access sha ed wi h an embedded mic op ocesso .
A ha dwa e-so wa e (Hw/Sw) codesign o he CMcE is
p esen ed in [11] on a Zynq-Ul aScale+de ice, a high-end
p og ammable sys em on chip. The algo i hm was desc ibed
by he C-based High-Le el Syn hesis (HLS) o ge he op imal
Hw/Sw pa i ioning based on he execu ion imes. The HLS syn-
hesises he ha dwa e accele a o and AXI in e aces o he em-
bedded mic op ocesso and DMA. The expe imen al esul s a e
epo ed in ela i e alues and pe cen age o FPGA esou ces.
The execu ion ime includes he o e head o ans e ing keys
and da a be ween ex e nal memo y and BRAMs. Fo he highes
secu i y le el (n=8192, =128, m=13) he accele a ion o key
gene a ion eachesx55.2,x3.3 o encodingandx8 o decoding.
The o al numbe o de o ed FPGA esou ces is e y la ge,
aking abou 80% (219·103) o he o al a ailable LUTs, 62%
(340·103) o he FFs, 38% (958) o he DSPs, and 205% (1870)
o BRAMs. Al hough au ho s ecognise ha ully-ha dwa e
implemen a ions can na u ally su pass he p oposed sys em, he
Hw/Sw codesign p o ides an end- o-end KEM implemen a ion
and i has he po en ial o be adap ed o u u e changes.
The CMcE c yp osys em [12] was implemen ed in Spinal-
HDL, imp o ing he execu ion ime and d as ically educing
he ha dwa e esou ces compa ed o he p e iously men ioned
wo k o he same secu i y pa ame e s (n=8192, =128, m=13).
Howe e , i does no p o ide in e aces wi h a mic op ocesso
CANTÓ-NAVARRO AND LÓPEZ-GARCÍA: AXI HARDWARE ACCELERATOR FOR MCELIECE ON FPGA EMBEDDED SYSTEMS 1479
bus and ex e nal memo y, limi ing i s adap abili y. The expe -
imen al esul s epo 1.2·106clock cycles o key gene a ion,
4.5·103and 36.5·103 o enc yp ion and dec yp ion, de o ing
45.7·103LUTs, 39.6·103FFs, 183 BRAMs on a high-end Vi ex
Ul aScale+.
In gene al e ms, HLS imp o es p oduc i i y by a as e
de elopmen cycle by isola ing he de elope om low-le el
de ails and decisions. On he o he hand, ha dwa e desc ip ion
languages (HDL), such as VHDL o Ve ilog, equi e signi ican
ha dwa e design knowledge, bu hey can be a ge ed o p o ide
highe pe o mance on lowe esou ces. I can be ound esea ch
wo ks ha emb ace HLS e sus HDL o ice e sa [13],[14].
The e iciency o he HDL design depends on he skill le el
and de elopmen e o , bu i has he po en ial o c ea e mo e
e icien designs han HLS.
A much smalle numbe o implemen a ions ha e been de-
eloped o he McE enc yp ion-dec yp ion, and mos a e s and-
alone designs. Mo eo e , some o hem eplace he Goppa codes
wi h o he codes o imp o e he implemen a ion e iciency.
The wo k [10] was he i s implemen a ion o McE on FPGA.
I iscomposedo h ee cus omci cui s:keygene a o ,enc yp o ,
and dec yp o based on he Pa e son algo i hm. The secu i y
pa ame e s we e ixed o a low-secu i y le el (n=2048, =50,
m=11) on a high-end Vi ex-5 FPGA, in eg a ed in o a PCI
ca d on a hos pe sonal compu e (PC). The enc yp ion and
dec yp ion ake 0.5 ms and 1.29 ms, espec i ely, including
communica ions wi h he hos PC, achie ing x20 and x42
speedup ac o a 164 MHz when compa ed wi h he so wa e
implemen a ion. The c yp op ocesso consumes a signi ican
amoun o FPGA esou ces: 84% o a ailable slices and 50%
o BRAMs.
Ano he wo k [15] p esen s a ligh weigh McE enc yp o and
dec yp o on FPGA, which eplaces Goppa codes wi h quasi-
cyclic mode a e densi y pa i y-check codes (QC-MDPC). The
secu i y le el p o ided is limi ed o 80-bi , and he heo e ical
enc yp ion-dec yp ion akes 3.4 ms (73.5·103clock cycles) and
23 ms (4.27·106clock cycles), employing jus 64 and 159 slices
on a low-cos Spa an-6 de ice. The au ho s claim QC-MDPC
p o ides a e y e icien enc yp ion-dec yp ion, bu u he
c yp analysis o weakness should be in es iga ed. They also
ecognize encoding and decoding hese codes is e y di e en
om Goppa codes and canno be ai ly compa ed wi h o he
McE ha dwa e sys ems.
The McE dec yp o shown in [1] is scalable om 80-bi o
256-bi secu i y. I was de eloped in VHDL, and i can ope a e,
no only wi h Goppa codes, bu also wi h quasi-dyadic (QD)
Goppa codes. QD-Goppa codes p o ide simple calcula ions,
bu some pa ame e s o hese codes ha e been weakened by
c yp oanalysis. The highes secu i y le el achie ed o Goppa
codes is 128-bi (n=3307, =66, m=12), aking 27·103clock
cycles o dec yp a he highes pe o mance and using 16153
LUTs, 2603 FFs, and 25 BRAMs on a low-cos Spa an-3AN.
The c yp op ocesso canno enc yp and does no p o ide con-
nec i i y o ex e nal memo y, assuming he keys a e al eady
loaded in he FPGA p og amming bi s eam.
A qui e di e en app oach is he Galois-Field (GF) ins uc-
ion se ex ension o RISC-V p ocesso s [16], which suppo s
speci ic compu ing ins uc ions. The expe imen al esul s show
enc yp ion and dec yp ion ake 4.33·106and 44.2·106clock
cycles, espec i ely, educing by 8% and 75% he execu ion ime
o he CMcE (n=3488, =64, m=12) unning on a RISC-V a
25 MHz. Al hough his app oach p o ides high lexibili y o be
used in se e al applica ions, no only o CMcE, i s pe o mance
is a om ha ob ained by he p e ious cus om c yp op oces-
so s.
The p esen wo k p oposes a McE un- ime p og ammable
accele a o ha p o ides AXI buses o in eg a ion in o embed-
ded sys ems. The design was ini ially based on he ha dwa e-
so wa e codesign p esen ed in [17], which uses 77357 LUTs
and 41338 FFs and accele a es dec yp ion by x21 (47.4 ms).
The p esen ed accele a o has been edesigned om sc a ch
in VHDL, pe mi ing be e con ol o ha dwa e esou ces
and equi ed clock cycles o compu a ions. I p o ides a se
o cons an - ime ins uc ions o accele a e compu a ions on
Goppa codes and bina y ec o s and ma ices. The mic op o-
cesso can w i e a un- ime he se o ins uc ions o accele a e
enc yp ion o dec yp ion o he McEliece algo i hm, o e en
o he algo i hms. Mo eo e , he accele a o p o ides a se o
pa ame e s ha allow con igu ing he secu i y le el and he
a ea-pe o mance adeo sui able o he a ge de ice.
The McE accele a o can be used in classical applica ions o
PK c yp osys em, such as he enc yp ion/dec yp ion o mes-
sages, he exchange o session keys, and digi al signa u es.
Mo eo e , PK can also be used in blockchain and biome ic
applica ions. Fo ins ance, he i is-code digi al signa u es based
on RSA[18] o he dis ibu ed biome ic au hen ica ion secu ed
by ECC-based blockchain [19]. A ew wo ks ocus on bio-
me ics using McE c yp osys ems, such as he p o ec ion o
empla es [20] o he non-de ice-cen ic acial au hen ica ion
[21]. In he la e , he au ho s p opose pe o ming he ma ching
in he enc yp ed domain, p o iding quan um esis ance o he
biome ic empla es and ea u ing i e e sibili y, unlinkabili y,
and e ocabili y. The high lexibili y p o ided by he p oposed
McE accele a o makes i sui able o hese applica ions.
III. ARCHITECTURE
The accele a o is an applica ion-speci ic ins uc ion p oces-
so . The se o ins uc ions a e ela ed o he one o he wo
p o ided a i hme ic co es: he polynomial F2m[Z]uni and
he ec o co e, as shown in Fig. 1. The polynomial F2m[Z]
a i hme ic co e is connec ed o a egis e ile o e ie e o sa e
polynomials. The ec o co e de o es an in e nal memo y o
s o e he esul ing bina y ec o om a compu a ion in ol ing a
sou ce ec o o ma ix e ie ed om ex e nal memo y. The
ins uc ions a e s o ed in an in e nal memo y, which can be
p og ammed a un- ime o change he ope a ions launched o
he co es. The accele a o p o ides AXI-S eam in e aces o
ans e da a e icien ly be ween he ex e nal RAM and he in-
e nal memo ies h ough an AXI-DMA. Finally, he Sla e-AXI
in e ace pe mi s he con ol o he accele a o om a mic op o-
cesso , se ing up he AXI-S eam in e aces o e ie e o s o e
da a in o he in e nal memo ies, launching a compu a ion, and
e ie ing he s a us o he co es.
1480 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025
Fig. 1. O e iew o he a chi ec u e. .
The secu i y pa ame e s (nMAX,m, ) o he McEliece a e
con igu ed a syn hesis ime and hey a ec he polynomial co e
and i s egis e s. Indeed, he e o -co ec ion capabili y ( ) can
be any alid alue, and he dimension (m) o he Galois-Field
F2mcan be selec ed om 8 o 15. The code leng h (n)is
p og ammable a un- ime accomplishing n≤nMAX, whe e
nMAX is a con igu able pa ame e ha a ec s he ec o co e
and memo y.
Ano he se o pa ame e s is used o con igu ing he dep h
o he ins uc ion’s memo y (NUM_INST) and he numbe o
polynomial egis e s (NUM_REGS). I is ecommended ha
bo h pa ame e s a e con igu ed as powe s o wo o be e use
o he in e nal memo ies. The de aul alues NUM_INST=256
and NUM_REGS=16 a e enough o implemen ing he McE
enc yp ion and dec yp ion.
Finally, he a ea-pe o mance adeo can be managed by se-
lec ing he app op ia e alues o a se o pa ame e s. The wid h
o he AXI-S eam in e aces (AXIS_WIDTH) is selec able o
32/64/128/256-bi . Depending on he ex e nal DDRx memo-
ies and connec ion wi h he FPGA, a highe AXIS_WIDTH
imp o es he ead/w i e h oughpu bu equi es highe pa -
alleliza ion and esou ces. This pa ame e a ec s he ec o
co e since 64-bi o 256-bi wid h da a om ma ices mus be
aligned in se e al 32-bi wo ds o pe o m p ope ly in pa allel.
Ano he pa ame e is he pa allelism ac o o he Galois-Field
F2madde -mul iplie (GF2MULT_FACTOR), which a ec s he
polynomial co e.
A. Regis e File o Polynomials
The a chi ec u e p o ides a egis e ile o ead polynomial
ope ands and w i e esul s o ins uc ions, elimina ing accesses
o ex e nal DDR memo y o pe o m a compu a ion. Each eg-
is e s o es a polynomial p(Z)∈F2m[Z], which is composed
o +1coe icien s in Galois-Field F2m, ollowing he no a ion
p(Z)=p Z +...+p1Z+p0.The egis e ileisasingle-po
dis ibu ed memo y since i can be e icien ly implemen ed on
LUTs. Fig. 2shows he a chi ec u e o he memo y, which
p o ides a single add ess bus o ead/w i e one o he egis e s.
Fig. 2. Dis ibu ed memo y o he polynomial egis e s.
TABLE I
IRREDUCIBLE POLYNOMIALS IN GALOIS FIELD
The deg ee deg(p(Z)) o a polynomial is he highes index wi h
non-ze o coe icien , and i is compu ed when a polynomial is
ead. The numbe o egis e s is con igu able, and in ou case,
we ook NUM_REGS=16 by de aul , de o ing a single LUT o
s o e one bi o one o he coe icien s o all he egis e s. This
way, all he egis e s sha e he same se o ( +1)·mLUTs.
The egis e s a e named om 0 o 15, pe mi ing polynomial
ins uc ions o ead ope ands and s o e he esul s in any o hese
egis e s. The e a e wo special-pu pose egis e s. The 0 is a
ead-only egis e , which alloca es he ze o polynomial, and i
can be used by he ins uc ions as an inpu ope and o o a oid
s o ing a esul in o he egis e ile. The egis e 15 s o es he
i educible polynomial g(Z)∈F2m[Z], which is used by he
co e when educing a polynomial. The AXI in e aces p o ide
ha e access o he polynomial egis e s om he mic op ocesso
andex e nalmemo y o ead esul so ochange hep i a eg(Z)
a un- ime.
B. Polynomial Co e
The polynomial co e is buil a ound a pa alleled F2madde -
mul iplie . I is composed o +1independen combina ional
F2ma i hme ic ci cui s, mi(y)=op1i(y)·op2i(y)+opxi(y),
0≤y≤ . The educ ion polynomial g(x)∈F2mis ixed ac-
co ding o Table I.
The F2madde -mul iplie can pe o m +1 addi ion-
mul iplica ions a e e y clock cycle by a aching h ee inne
egis e s (po,pq,pb), as depic ed in Fig. 3. Each inne egis e
is buil o a la ge se o ( +1)·m lip- lops (FFs) and s o es all
he F2mcoe icien s o a polynomial F2m[Z]. La ge bi -wid h
CANTÓ-NAVARRO AND LÓPEZ-GARCÍA: AXI HARDWARE ACCELERATOR FOR MCELIECE ON FPGA EMBEDDED SYSTEMS 1481
Fig. 3. O e iew o he polynomial co e..
mul iplexe s connec he polynomial egis e ile, he inne eg-
is e s, and adde -mul iplie in se e al ways, depending on he
unning s a e. The egis e s and mul iplexe s a e con olled by
a Fini e S a e Machine (FSM), which changes he s a es based
on he s a ing mode (encoded in he ins uc ion) and an in e nal
coun e (cn ). The s a and eady po s a e used o handshaking
wi h he ex e nal ci cui y. The numbe o inpu s o he la ge
mul iplexe s has been minimized since each one is composed
o ( +1)·mbi s. The ou pu o he F2madde -mul iplie (m)
is shi ed one coe icien o he le (m<<1) o o he igh
(m>>1) be o e s o ing i in an inne egis e .
An inne egis e pcan be w i en om a polynomial a(Z)∈
F2m[Z], which is ead om he egis e ile in a single clock
cycle, deno ed as p←a(Z). The egis e s can be shi ed one
coe icien o he le o igh , deno ed as p<<1o p>>1
ha a e equi alen o a(Z)·Zo a(Z)·Z−1. Ope a ions o e
polynomials can be accele a ed by he pa alleled F2madde -
mul iplie , and by 1-bi shi ing on egis e s o a oid much mo e
complex ba el shi e s. The s eps ca ied ou on he po,pq,
pb egis e s and he F2madde -mul iplie a e kep as simila as
possible o he di e en ins uc ions o a oid inc emen ing he
numbe o inpu s o mul iplexe s.
Fo ins ance, ins uc ion 8← 7∗ 4+ 12 compu es a
polynomial addi ion-mul iplica ion om h ee egis e s, e u n-
ing he esul in he ou h egis e . Conc e ely, i compu es
(Z)=a(Z)·b(Z)+c(Z)in ou s a es, as depic ed in Fig. 4.
The ins uc ion s a s om an ini ial idle s a e by w i ing he
h ee inne egis e s om polynomials s o ed in he egis e
ile. Due o he single-po egis e ile, po ←c(Z),pq←
a(Z),pb←b(Z) equi e h ee clock cycles. A ou h cycle
is equi ed o s a he ope a ion, deasse ing he eady po
and decoding he ope a ion mode, which is encoded as 01CL
(C=0, L=1) o he modula mul iplica ion and addi ion o
polynomials.
Fig. 4. S a es o he polynomial ope a ion (Z)=a(Z)·b(Z)+c(Z).
In he second s a e, he F2madde -mul iplie pe o ms po +
pb ·pq(0) and he esul is 1-bi shi ed o he igh (m>>1)
be o e s o ing i in o wo egis e s. The pq is igh -shi ed, and
he lowes coe icien o he esul is appended a he le side,
deno ed as pq ←m(0) & (pq 1). Concu en ly, he egis e
po s o es he emaining coe icien s o m, appending he coe -
icien 0 o he le side, acco ding o po ←0&(m1).The
s a e is epea ed +1clock cycles o compu e he no educed
esul (Z). A e comple ing, pq s o es he lowes ( +1)
coe icien s, and po s o es he emaining highes coe icien s a
he igh side. In o he wo ds, {po, pq}= (Z), wi h po( )=0.
The egis e pb emains cons an , excep a he las cycle ha
loads he i educible Goppa polynomial g(Z) om he egis e
ile, deno ed as pb ←g(Z).
The hi d s a e educes (Z)by pe o ming po +pb ·po( ),
adding o he egis e po he mul iplica ion o i s highes co-
e icien po( )wi h g(Z).The esul mis le -shi ed be o e
s o ing i in o po, appending he le size coe icien s o ed in
pq, acco ding o po ←(m1) & pq( ). The e o e, he deg ee
o he esul is educed when po( )=0o he esul is simply
le -shi ed when po( )=0. The educ ion s a e is epea ed
+2 clock cycles, since a he i s cycle po( )=0.A e
comple ing he es o cycles, pq =0and po s o es he esul
(Z)mod g(Z)= (Z)bu le -shi ed as po = (Z)<< 1.
Since po = (Z)<< 1and pq =0, he second s a e is ex-
ecu ed once again o pe o m he igh -shi ing o po, inally
ob aining po = (Z)whe e deg( (Z)) < . The inal s a e
ans e s he ins uc ion esul , which is s o ed in po, o he egis-
e ile and asse s he eady po . The e o e, he o al numbe o
clock cycles de o ed is 5+2·( +2), since 2·( +2)cycles
a e equi ed o he second and hi d s a es and 5 clock cycles
o he ini ial and inal s a es.

1482 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025
The p e ious addi ion-mul iplica ion ins uc ion wo ks o
any inpu polynomials, esul ing in deg( (Z)) < . In he case
o being a(Z)a cons an polynomial, he mode changes o
011L (C=1), which sligh ly changes he execu ion o he s a e
g aph o pe o m as e , depending on he deg(a(Z)). Addi-
ionally, he las educ ion and igh -shi ing can be a oided
i L=0, esul ing in deg( (Z)) ≤ . Fo ins ance, assuming 1
s o es he polynomial a(Z)=1, he educ ion o b(Z), which
is s o ed in 7, can be compu ed by he ins uc ion 5← 1∗
7+ 0, aking 5+2·(deg(a(Z)) + 2)=9 clock cycles since
deg(a(Z)) = 0 and L=1. Ano he example, i 12 s o es c(Z),
he addi ion b(Z)+c(Z)is s o ed in 5(deg( 5) ≤ when
L=0) by execu ing he ins uc ion 5← 1∗ 7+ 12, aking
5+2·(deg(a(Z)) + 1) =7 clock cycles. A inal example is
he ope a ion b(Z)·Zby he ins uc ion 14 ← 2∗ 7+ 0,
assuming 2s o es he cons an polynomial a(Z)=Z, which
akes 5+2·(deg(a(Z)) + 1) = 9 clock cycles since L=0.
Ob iously, he desc ibed p ocedu e o he addi ion-
mul iplica ion could be educed by 2 clock cycles by disabling
he shi ing on mand on he egis e s po,pq a he las cycle o
he second and hi d s a es. Howe e , his solu ion inc emen s
signi ican ly he ha dwa e esou ces due o he addi ional inpu
in e ed on he mul iplexe s o a ach m. Ano he way o educe
clock cycles is by simul aneously w i ing o he h ee inne
egis e s using a h ee-po memo y o he egis e ile. Con-
side ing he pa ame e is a la ge numbe , educing a ew clock
cycles does no ha e a g ea impac on he o e all pe o mance,
al hough i signi ican ly inc emen s he ha dwa e esou ces. The
adi ional way o mul iply and educe a each s ep equi es
a ou h inne egis e s o ing g(Z)du ing all he cycles, and
an addi ional inpu a one o he mul iplexe s. Howe e , he
execu ion ime canno be educed since a single mcan be
pe o med a e e y clock cycle, and he e o e, his solu ion only
p o ides disad an ages.
The ope a ion = oo s(c(Z),N), which is used o ind he
oo s o he polynomial, is sligh ly di e en om o he s because
he esul is a bina y ec o FN
2 ha will be s o ed in he ec o
memo y ( ). The e oloc ci cui depic ed in Fig. 3is a simple
m-bi compa a o a ached o a egis e , which connec s o he
AXI-S eam bus o sha e he same in e ace used o w i e in-
e nal memo ies. Fo ins ance, he ins uc ion oo s( 8,8192)
compu es he oo s o he polynomial s o ed in he egis e 8,
esul ing in an 8192-bi bina y ec o .
A he idle s a e, he ins uc ion ini ializes he inne egis e
po wi h he polynomial c(Z), and loads pq wi h 0 o ini ialize
all i s coe icien s o ze o, as shown in Fig. 5. Then, he in e -
nal FSM egis e max is ini ialized o 8191 o e alua e c(Z)
om Z=0 o Z= 8191. Since he F2madde -mul iplie is
composed o independen a i hme ic blocks, i can concu en ly
compu e +1pa ial e alua ions o c(Z)a each clock cycle.
The coun e cn is he Z ha is going o be e alua ed, equi -
ing ( +1)clock cycles o comple e. As shown in he second
s a e, by igh shi ing pq and w i ing cn a he le side, he
egis e s o espq( )=Z,pq( −1) = Z−1,pq( −2) = Z−
2, ..., pq(0) = Z− . Since pb s o es m>>1wi h pb( )=0
a each clock cycle, he esul s om he F2madde -mul iplie
a e m( )=c +Z·0=c ,m( −1) = c −1+(Z−1) ·c ,
Fig. 5. S a es o he ope a ion = oo s(c(Z),N).
m( −2) = c −2+(Z−2) ·(c −1+(Z−2) ·c ), and so on.
Du ing he i s clock cycles, he m(0) does no p o ide a
alid alue, bu a e his ini ial la ency m(0) = c0+Z·(c1+
Z·(c2+···(Z·c −1+c )···)), which is he e alua ion c(Z)
by he Ho ne ’s me hod. The e alua ions m(0) = c(Z), om
Z=0 o Z=N−1a e ob ained in sequen ial o de , being he
h oughpu o one e alua ion pe clockcycle.The e o e, he o al
compu a ion ime, including he ini ial s a e, is 3+( +1)+N
clock cycles. The e o loc ci cui compa es m(0) wi h 0∈F2m,
esul ing in a single bi , which is se ially s o ed in a shi egis e
o in e ace he AXI-S eam bus ha w i es he ec o memo y.
As i is shown in he p e ious ope a ions, he p ocedu es aken
in he s a es a e e y simila . Mo eo e , all he ins uc ions ha
can be pe o med by he polynomial co e (Table II) ollow a
simila app oach. All o hem euse he h ee inne egis e s
and connec ions o he F2madde -mul iplie h ough he same
mul iplexe s, sa ing FPGA esou ces. The main di e ence is
he s a es ca ied ou by he FSM acco ding o each ins uc ion.
The copy ins uc ion jus copies a egis e in o ano he one.
The di ision a(Z)/b(Z) e u ns wo polynomials accomplish-
ing q(Z)·b(Z)+ (Z)=a(Z). Simila ly, he spli (a(Z)) e-
u ns wo polynomials composed o he e en e(Z)and odd
o(Z)coe icien s. The GF Mul ins uc ion is he Galois Field
F2mmul iplica ion o he composing coe icien s i=ai·
bi(0 ≤i≤ ). These las wo ins uc ions can be used o com-
pu e he a(Z). Finally, he las ins uc ion e u ns by he AXI
in e ace he deg ee o he polynomial s o ed in a egis e .
The polynomial co e de o es a la ge numbe o esou ces o
hepa allel F2madde -mul iplie andi sassocia edmul iplexe s.
The ully pa allelized co e does no i in low-cos de ices
o he la ge secu i y pa ame e s (m, ), bu he co e p o ides
he pa ame e GF2MULT_FACTOR (deno ed as F), which de-
ines he pa allelism ac o . The numbe o pa alleled a i hme ic
ci cui s in he F2madde -mul iplie is educed o ( +1)/F
(F≥2), and he wid h o inpu s o he mul iplexe s depic ed in
Fig. 3is educed o m·( +1)/F. The ins uc ions execu e
he same s a es desc ibed be o e, bu each cycle is di ided in o
Fclock cycles. Each o he inne egis e s a e di ided in o
CANTÓ-NAVARRO AND LÓPEZ-GARCÍA: AXI HARDWARE ACCELERATOR FOR MCELIECE ON FPGA EMBEDDED SYSTEMS 1483
TABLE II
POLYNOMIAL INSTRUCTION SET
Fig. 6. Slices o he inne egis e pb o =256 and F=3.
Fslices o ( +1)/F coe icien s, which a e con inuously
o a ed. Fig. 6shows he slices o he egis e pb o he case
= 256 and F=3. Each slice s o es 86 coe icien s, padding
pb(j)=0when j> . The slice-0 a aches o he op1po o he
F2madde -mul iplie . In he nex clock cycle he esul m1
is s o ed in he slice-2, and he con en s o slices a e o a ed
o pe o m wi h he nex coe icien s, main aining he same
connec i i y wi h he F2madde -mul iplie . A e comple ing
Fig. 7. Vec o memo y.
he Fclock cycles, he inne egis e s s o e he same con en s
as in a single cycle o he ully pa allelized co e. The ob ious
incon enience is he clock cycles needed by he ins uc ions
ca ied ou by he F2madde -mul iplie a e inc emen ed by he
ac o F. Fo ins ance, he ins uc ion o addi ion-mul iplica ion
o polynomials akes 5+F·2·( +2) clock cycles, o he
ins uc ion o inding oo s akes 3+F·( +1+n).
C. Vec o Memo y
The maximum numbe o bi s ha can be alloca ed in he
ec o memo y is a con igu able pa ame e (nMAX), which is
p o ided a syn hesis ime o be implemen ed by using in e nal
BRAMs. Ins uc ions ha use he ec o memo y p o ide he
bi -size o ope ands, such as he code leng h (n)o he code
dimension (k). The bi -size is p og ammable a un- ime, pe -
mi ing he ec o co e o wo k wi h di e en code leng hs ha
accomplish n≤nMAX.
The BRAMs a e con igu ed as a dual po memo y wi h
independen ead and w i e po s, as depic ed in Fig. 7.The
wid h o he po s (deno ed W) ma ches he AXI-S eam wid h
(pa ame e AXIS_WIDTH) o p o ide as e p ocessing wi h
da a e ie ed om ex e nal DDRx RAM.
The memo y is a anged in 2·nMAX/WxW-bi wo ds,
p o iding a o al capaci y o 2·nMAX bi s o enable double-
bu e ing du ing p ocessing.
The co e au oma ically swaps he base add ess o bo h bu e s
be o e s a ing a new ins uc ion ha equi es simul aneous
ead/w i e access o BRAMs. I nMAX is a powe o 2, he
addi ion o ob ain he ex ended add ess is eplaced wi h a simple
bi conca ena ion o he bu e add ess wi h he mos signi ican
bi o he base add ess.
D. Vec o Co e
Table III esumes he ins uc ions p o ided by he co e, which
is depic ed in Fig. 8. All he ins uc ions pe o m a compu a ion
om a bina y ec o e ie ed om he ead bu e , w i ing
he esul ing ec o in he w i e bu e o he same memo y.
The e o e, hese ins uc ions do no speci y he ope a o ,
bu hey equi e speci ying an a gumen N≤nMAX, which is
he numbe o bi s conside ed in he bina y ec o ∈FN
2.
As in he polynomial co e, he p ocedu es ca ied ou by he
s a es o execu e ins uc ions a e e y simila , educing ha dwa e
esou ces.
1484 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025
TABLE III
VECTOR INSTRUCTION SET
Fig. 8. A chi ec u e o he ec o co e ( op) and he addi ion/mul iplica ion
(bo om-le ) and bi -o de ing (bo om- igh ) subci cui s. .
Fo ins ance, he ins uc ions o ec o addi ion ←V+
and o ma ix mul iplica ion ←M· a e e y simila , sha -
ing he same logic o ead da a om ex e nal memo y, 32-bi
alignmen wi h e ie ed da a om BRAMs, and s o age o
pa ial esul s. The esul is empo ally s o ed in a W-bi egis e
(R) be o e w i ing he esul wo d in o BRAM, aking N/W
clock cycles pe ow o pe o m he compu a ion, whe e N
is he numbe o bi s o columns. The alignmen ci cui is
equi ed when he AXI-S eam is la ge han 32-bi o align
da a e ie ed om ex e nal memo y wi h BRAM in o 32-bi
wo ds. The ex e nal DMA mus be p ope ly con igu ed o poin
o he base add ess o Vo M, and he o al numbe o wo ds o
ead om DDRx RAM. The eal execu ion ime is highe han
he heo e ical one since he DMA in oduces wai -s a es be-
ween bu s ansac ions o access da a s o ed in sha ed ex e nal
memo y.
The emaining ins uc ions a e he pe mu a ion (i)←
(P(i)) and he ans o ma ion o Nbi s om o Goppa code
(Z)← o_goppa( ,N). Bo h ins uc ions a e e y simila
since hey basically ead a single bi om a e e y clock
cycle a di e en loca ions, se ially s o ing he esul ing bi s
in o he empo al egis e R. The loca ion index o he bi o
ead om is e ie ed ei he om a pe mu a ion ec o P
s o ed in ex e nal memo y o om he coun e cn o he o he
ins uc ion. The egis e is sequen ially s o ed in BRAM o he
i s ins uc ion, o in one o he egis e s o he polynomial ile
o he las ins uc ion.
The pe mu a ion o by using a ec o P∈FN
232 is equi alen
o he exp ession ·P, whe e P∈FN×N
2is a pe mu a ion
bina y ma ix wi h exac ly one 1 e e y ow and column, bu
i equi es lowe accesses o memo y.
The ins uc ion o ans o m o Goppa code could be exe-
cu ed in a single clock cycle by adding a la ge mul iplexe a he
inpu o he polynomial egis e s. Howe e , he FPGA esou ces
would be g ea ly inc eased, whe eas he o e all pe o mance
o McE dec yp ion is e y sligh ly imp o ed since i is no
equen ly used.
No ice he bene i in he execu ion ime o he ec o addi ion
and ma ix mul iplica ion when W is la ge , bu nei he he
pe mu a ion no he Goppa ans o ma ion. By using simila
p ocedu es in he s a es ca ied ou o all he ins uc ions,
ha dwa e esou ces a e minimized.
IV. MCELIECE
The McEliece (McE) is a code-based PK enc yp ion sys em.
Enc yp ion is simple, bu dec yp ion is a mo e complex since
i in ol es se e al algo i hms based on ope a ions wi h bina y
ma ices, Galois-Field F2mand polynomials F2m[Z].
The key gene a ion, enc yp ion, and dec yp ion desc ibed in
he CMcE di e om he McE. The CMcE is a ecen NIST
s anda d candida e o Key Encapsula ion Mechanism (KEM),
which can e icien ly implemen he key gene a ion and decod-
ing. I is based on a synd ome-based a ian o he McE, which
encodes a message on a -weigh e o s ing ∈Fn
2, enc yp ing
i as he synd ome c=H·e∈Fm
2, since H∈Fm ×n
2is he
pa i y-check ma ix ha is used as he public key.
A. Key Gene a ion
Al hough he p esen ed accele a o is no in ended o key
gene a ion, we p o ide a b ie desc ip ion. A bina y Goppa code
is de ined by a polynomial g(Z)and a se o dis inc elemen s
L om a ini e ield, p o iding a high e o co ec ion capaci y
om a pa i y-check ma ix H[22],[23], which is undis inguish-
able om andom ma ices. The key gene a ion s a s by com-
pu ing a andom i educible Goppa polynomial g(Z)F2m[Z].
Then, he gene a o ma ix G∈Fk×n
2is compu ed o a Goppa
code ha mee s he minimum dis ance c i e ion d≥2 +1.
The gene a o ma ix is pe u ba ed wi h wo andom in e ible
ma ices: he non-singula i y ma ix S∈Fk×k
2and he pe mu a-
ion ma ix P∈Fn×n
2. Finally, he public key Gpub ∈Fk×n
2
is ob ained om he mul iplica ion o he h ee ma ices as
Gpub =S·G·P.
CANTÓ-NAVARRO AND LÓPEZ-GARCÍA: AXI HARDWARE ACCELERATOR FOR MCELIECE ON FPGA EMBEDDED SYSTEMS 1485
Algo i hm 1: Pseudo-C code o Enc yp ion.
Inpu :(Gpub)T∈Fn×k
2,m∈Fk
2,e∈Fn
2( −weigh )
Resul :c∈Fn
2
ins _enc ={mul _M(k); add_V(n);}
McE_LoadVec o (m, k); // ←m
McE_Launch(ins _enc);
DMA_Read((Gpub)T,n,k)// ←(Gpub)T·
DMA_Read(e, 1,n)// ←e+
McE_Sa eVec o (c, n); //c ←
We de eloped he key gene a ion as in he Flexip o ide
lib a y, which uses an auxilia y ec o P1∈Fn
232 o pe mu e he
columns o he pa i y-check ma ix H, helping he sys ema iza-
ion o G. The ansposed pa i y-check ma ix HT∈Fn×m
2is
s o ed as pa o he p i a e key along wi h he ansposed in e se
ma ix (S−1)T, he pe mu a ion ec o s P−1,(P1·P)−1, and
he i educible Goppa polynomial g(Z).
A he s a ing ime, he embedded mic op ocesso w i es
all he ins uc ions ha a e going o be ca ied ou by he
accele a o o enc yp ion and dec yp ion. I also ini ializes he
polynomial egis e s 1=1 F2m[Z], 2=ZF2m[Z],
15 = g(Z)F2m[Z], and 14 = √ZF2m[Z].
B. Enc yp ion
The enc yp ion ans o ms a plain ex m∈Fk
2and a an-
domly gene a ed -weigh e o e∈Fn
2 o a ciphe ex c∈Fn
2
by using he public key ma ix Gpub ∈Fk×n
2, acco ding o:
c=m·Gpub +e=GpubT·m+e(1)
The ins uc ion memo y o he accele a o con ains wo in-
s uc ions o pe o m he enc yp ion, poin ed by ins _enc (Al-
go i hm 1). A e loading he in e nal memo y wi h m, he
mic op ocesso can launch he enc yp ion on he accele a o .
Then, he mic op ocesso con igu es he DMA o he add esses
ha s o e (Gpub)Tand e, and se s he numbe o ows and
columns o s a he eading o da a om ex e nal memo y. A e
comple ing he enc yp ion, s o es he cyphe ex cand w i es
i o ex e nal memo y.
C. Dec yp ion
A e ecei ing he ciphe ex c∈Fn
2, a se o s eps a e ca ied
ou o ge he loca ed e o s εand eco e he plain ex m.The
s eps ollowed a e:
1. c=c·(P1·P)−1
2. ε=Decode(c)
3. y=c+ε
4. y= unca e(y·P1−1,k)
5. m=y·S−1=(S−1)T·y
Since (P1·P)−1=P−1·P−1
1, he i s s ep emo es he
pe mu a ion P om he ciphe ex . No ice he esul ing ec o
c∈Fn
2is no only equi ed in he nex s ep bu also a e he
decoding. The e o e, cis s o ed in ex e nal memo y o la e
use, as shown in Algo i hm 2. The Pa e son algo i hm decodes
Algo i hm 2: Pseudo-C code o Dec yp ion.
Inpu :c∈Fn
2,(P1·P)−1∈Fn
232 ,P1∈Fn
232 ,
(S−1)T∈Fk×k
2
Resul :m∈Fkn
2,ε∈Fn
2
ins _dec1={pe mu e_P(n); }
ins _dec2=
{add_V(n); pe mu e_P(k); mul _M(k); }
McE_LoadVec o (c,n); // ←c
McE_Launch(ins _dec1);
DMA_Read((P1·P)−1,1,n);// ← ·(P1·P)−1
McE_Sa eVec o (c,n); //c←
Pa e son( ); // ←Pa e son( )
McE_Sa eVec o (ε, n); //ε ←
McE_Launch(ins _dec2);
DMA_Read(c,1,n); // ←c+
DMA_Read(P1−1,1,k); // ← unca e( ·P−1,k)
DMA_Read((S−1)T,k,k); // ←(S−1)T·
McE_Sa eVec o (m, k); //m ←
he loca ion o e o s, s o ing hem in o he bina y ec o ε∈Fn
2
o -weigh . Then, he p e iously s o ed c’ is e ie ed om ex-
e nal memo y and added o ε, ob aining y∈Fn
2. The auxilia y
pe mu a ion P1is emo ed om y’, esul ing in he sub ec o
y∈Fk
2. Finally, he ma ix (S−1)T∈Fk×k
2is mul iplied wi h
he sub ec o y∈Fk
2, w i ing he compu ed plain ex m∈Fk
2
in o ex e nal memo y.
1) Pa e son Algo i hm: The commonly used algo i hms o
decoding a e he Pa e son and he Be lekamp-Massey (BM).
The BM is as e and simple , al hough i can co ec up o /2
e o s by de aul . The modi ied BM algo i hm can eco e he
equi ed e o s by he compu a ion o he double-size pa i y
ma ix H(2) and synd ome S(2). The Pa e son algo i hm can
co ec he e o s by ope a ing in bina y Goppa codes and
i has been ho oughly analyzed o side-channel a acks [23].
Howe e , he algo i hm is signi ican ly mo e complex han he
BM, equi ing a la ge a ie y o compu a ions in Galois-Field
F2mand polynomials F2m[Z].
The Pa e son algo i hm compu es he loca ion o e o s om
c∈Fn
2, s o ing hem in o ε∈Fn
2. I is di ided in o six s eps,
s a ing wi h he synd ome calcula ion om he pa i y ma ix
H∈Fm ×n
2.The synd omeis s o edin a egis e ( 4) ope o m
a se o polynomial ope a ions. The E o Loca ion Polynomial
(ELP), deno ed as σ(Z), is ob ained a e wo execu ions o
he Ex ended Euclidean Algo i hm (EEA) and a squa e oo
compu a ion. Finally, he inding o oo s p o ides he loca ions
o he e o s, s o ing hem in a bina y ec o ε∈Fn
2.
1. Sc(Z)=HT·c’
2. 1≡T(Z)·Sc(Z)mod g(Z)(by EEA)
3. R(Z)=T(Z)+Z
4. a(Z)≡b(Z)·R(Z)mod g(Z)(by EEA)
5. σ(Z)=a(Z)2+Z·b(Z)2
6. ε= oo s(σ(Z))
As in he p e ious codes, he mic op ocesso (Algo i hm
3) launches he execu ion o wo se s o ins uc ions on he