Depósi o de in es igación de la Uni e sidad de Se illa
h ps://idus.us.es/
“This is an Accep ed Manusc ip o an a icle published by Else ie in In e ne
o Things (The Ne he lands) on Ma ch 2020, a ailable
a : h ps://doi.o g/10.1016/j.io .2019.100057 ”
PUF-de i ed IoT iden i ies in a
ze o-knowledge p o ocol o blockchain
Miguel ´
Angel P ada-Delgado, Iluminada Ba u one
Ins i u o de Mic oelec ´onica de Se illa, IMSE, CNM (Uni e sidad de Se illa, CSIC)
Se ille, Spain
Ge o Di mann, Jens Jeli o, And eas Kind
IBM Resea ch – Zu ich, Swi ze land
Abs ac
As he in e ne o hings mo es in o inc easingly sensi i e domains, connec ed
de ices need o be secu ed agains da a manipula ion and coun e ei ing. Whe e
he unde lying business p ocesses in ol e mul iple independen pa ies, a block-
chain pla o m can p o ide a common sou ce o u h. I changes o he common
s a e depend on IoT de ices, he au hen ici y and in eg i y o he IoT inpu mus
be ensu ed. Employing a blockchain pla o m o au hen ica ing de ices makes
he p ocess independen o he de ice manu ac u e .
This pape shows how c yp og aphic keys de i ed om a de ice’s physical
inge p in can be employed in a ze o-knowledge p o ocol o au hen ica e a
de ice. As he keys a e egene a ed a boo ime a he han s o ed, he app oach
does no need an expensi e secu e elemen . An e icien implemen a ion enables
e en ligh weigh de ices o p o e hei iden i y and sign messages. Expe imen al
esul s demons a e he obus ness o he app oach.
Keywo ds: PUF, IoT, blockchain, ze o-knowledge p oo , au hen ica ion,
mic ocon olle , SRAM
1. In oduc ion
The numbe o objec s wi h embedded mic ocon olle s (MCUs) connec ed
o he in e ne o hings (IoT) is inc easing apidly [1]—also in he sa e y-
P ep in submi ed o In e ne o Things May 12, 2019
and secu i y-c i ical medical, ene gy and au omo i e indus ies. The use o dis-
ibu ed ledge echnology in combina ion wi h IoT de ices has gained a lo o 5
a en ion no only in he inancial sec o bu in many indus ies as a means o
inc ease us and isibili y, e.g. along complex supply chains o mo e accu-
a e goods acing, coun e ei de ec ion [2, 3] and in o ma ion e i ica ion [4].
Complex manu ac u ing lines and dis ibu ion sys ems can be secu ely moni-
o ed and documen ed such ha downs eam business p ocesses can alida e10
he p o enance o p oduc s. This back- o-bi h aceabili y is c i ical and o en
e en manda o y, e.g. in he ai line indus y o li e-limi ed pa s [5] o in he
pha ma sec o o p esc ip ion medicine [6]. Likewise, ups eam business p o-
cesses can de e mine he ecipien s o goods, o ins ance in case o a p oduc
ecall.15
Blockchains le e age c yp og aphy, dis ibu ed p o ocols, and p i acy-enabling
echniques (e.g. ze o-knowledge p o ocols, h eshold-signa u e schemes) o en-
able us and o con ol isibili y o he in o ma ion in mul i-pa y en i on-
men s [7]. In his ega d, i is o c ucial impo ance he p i acy p o ec ion in
blockchain-based IoT sys ems om issues caused due o in o ma ion leakage20
[8]. A blockchain alone, howe e , is o en insu icien o p o e p oduc o iginal-
i y o p o ide an unin e up ed and indispu able chain o cus ody h oughou
he p oduc li e-cycle because i canno gua an ee he uniqueness o a physical
en i y.
In addi ion, an IoT connec ion is commonly used o moni o o con ol an25
objec connec ed o he blockchain. This connec ion wi h physical de ices is
necessa y, bu i opens he doo o new a ack ec o s such as he injec ion o
ha dwa e ulne abili ies by a malicious i mwa e upda e [9]. Fo secu i y, c yp-
og aphic p o ocols au hen ica e he objec s wi h keys o passwo ds con igu ed
by he manu ac u e 1. Au hen ica ion also add esses coun e ei p oduc s and30
ake eplacemen pa s which a e becoming mo e sophis ica ed and p esen a
majo p oblem o many indus ies [10].
1By manu ac u e we e e o he in eg a o a he han he p oduce o he MCU chip.
2
Hence, an IoT-enabled home appliance such as a washing machine whose
con olle boa d ea u es a ne wo k connec ion mus be secu e, no only o p o-
ec i sel om a acks bu o p o ec also he ne wo k o which i is connec ed.35
In he p oduc ion p ocess, he manu ac u e con igu es he con olle wi h a
c yp og aphic key and s o e he coun e pa key in a da abase.2Once sold and
deployed in he ield, he machine may equi e se ices o e ed by he manu-
ac u e . To au hen ica e he machine, he manu ac u e sends a challenge ha
he machine mus answe employing i s sec e key. The manu ac u e e i ies40
he esponse using he coun e pa key. Beyond au hen ica ion, he sec e key
may also be used o signing da a sen by he machine, e.g., senso eadings,
a es ing om which machine hey o igina e.
In MCUs, he sec e key mus be s o ed in a way ha is no accessible
om he ou side o make hem impossible o copy in o a coun e ei . The se-45
cu e elemen s ha p o ide such s o age [11], howe e , add signi ican cos and,
consequen ly, ew con olle s ha e hem.
In his pape , an al e na i e au hen ica ion app oach in which an MCU gen-
e a es a sec e key in e nally is in oduced, exploi ing manu ac u ing a iabili y
as a physical unclonable unc ion (PUF). As he key is gene a ed by he de-50
ice i sel , manu ac u e s sa e he expense o a secu e en i onmen o ex e nal
key gene a ion. In p oduc ion, once chips a e loaded wi h a i mwa e, i is only
necessa y o un an in e nal cha ac e iza ion and pass on he esul ing public
key, mask and helpe da a o be s o ed o au hen ica ion and eco e y. Fu he
ex e nal memo y access is p e en ed, e.g., by blowing he JTAG secu i y use.55
As he sec e key is egene a ed (wi h he same esul each ime) a he han
s o ed in non- ola ile memo y, i is e y ha d o clone and he cos o a secu e
elemen can be sa ed.
The case o such IoT de ices is s eng hened u he in combina ion wi h a
dis ibu ed ledge , o blockchain. Fi s o all, he immu abili y and dis ibu ed60
2In asymme ic c yp og aphy, he de ice is con igu ed wi h a p i a e key and he manu-
ac u e s o es he public key; in symme ic c yp og aphy, bo h hold he same sec e key.
3
us p o ided by a blockchain can make he de ice au hen ica ion independen
o he manu ac u e . Secondly, a business p ocess implemen ed in chaincode ha
elies on IoT inpu s can alida e de ice signa u es o ensu e he au hen ici y
and in eg i y o hose inpu s.
Replacing he cen al da abase ope a ed by a manu ac u e wi h a blockchain65
makes he sys em independen o he manu ac u e . The chaincode will s ill al-
low only he manu ac u e o c ea e new machine en ies on he dis ibu ed
ledge bu as he ledge con en is dis ibu ed o all pa icipan s (mul iple man-
u ac u e s, e aile s, owne s, e c.) he manu ac u e is elie ed o adminis e ing
he sys em and gua an eeing i s a ailabili y. A cen al da abase would go o line70
when he manu ac u e goes ou o business whe eas a blockchain can su i e.
Gi en he secu i y disad an ages o symme ic au hen ica ion schemes (keep-
ing a da abase o keys o au hen ica e wi h he isk o being hacked o los , he
isk o cloning, and ba ie s o hi d-pa y au hen ica ion, among o he s) ou
app oach ins ead uses public-key c yp og aphy based on lea ning pa i y wi h75
noise (LPN) p oblems, and in pa icula ze o-knowledge (ZK) p o ocols o u -
he simpli y he managemen o de ice public keys. The blockchain may make
he public keys gene a ed by each de ice a ailable o anyone o use in hei
own au hen ica ion sys em.
As o he second aspec , e en a low-cos de ice can p e en manipula ion80
o i s communica ion wi h a blockchain by signing i s messages wi h ou PUF-
de i ed keys, making he p oposal sui able o any esou ces-limi ed de ice con-
nec ed o he blockchain [9]. The chain code, in u n, can also alida e he
de ice signa u es o ensu e da a in eg i y and au hen ici y, ex ending he us
he blockchain p o ides in o he IoT de ice.85
This pape p oposes using an SRAM-based PUF o gene a e c yp og aphic
keys ha a e employed in a ze o-knowledge p oo o au hen ica e an IoT de ice.
We p esen an e icien implemen a ion in an MCU and show ha e en low-cos
de ices can pe o m he equi ed compu a ional asks su icien ly as . Expe -
imen al esul s demons a e ha ou app oach is obus agains empe a u e90
a ia ions and ha collisions o de ice iden i ies a e unlikely.
4

This pape is s uc u ed as ollows. Sec ion 2 e iews ela ed wo k in digi al
and physical us on he blockchain as well as PUFs using LPN p oblems o
unde s and PUFs, ZK p oo s o knowledge, and exac LPN (xLPN) p oblems.
Sec ion 3 desc ibes ou p oposal o use PUFs in c yp osys ems based on xLPN95
p oblems. An e icien implemen a ion o he p oposal on an MCU is desc ibed in
Sec ion 4. Expe imen al esul s o he implemen a ion a e p esen ed in Sec ion 5.
Finally, conclusions and u u e wo k a e gi en in Sec ion 6.
2. P elimina ies
2.1. Ex ension o us in o physical p oduc s100
An ex ension o he blockchain-p o ided us beyond he digi al in o he
physical domain is equi ed o eliably de e mine p oduc o iginali y o o accu-
a ely ace he mo emen o goods. The physical objec s mus be unequi ocally
ied o hei associa ed digi al eco ds. Typically, a unique iden i ie (UID) is
used o link a physical objec o a digi al eco d. The iden i ie can be unique in105
he sense ha i ep esen s an indi idual objec , o i can mo e b oadly iden i y
a class o objec s by model, ba ch, p oduc ion si e, manu ac u e o simila [12].
A UID is ypically a ached as a ag, p in ed o embossed on he objec o i s
packaging. Such iden i ie s, howe e , can o en easily be cloned o ans e ed o
a ake objec . Hence, an iden i ie alone canno uniquely and secu ely iden i y,110
i.e., au hen ica e an objec .
A b oad a ie y o concep s and solu ions has been s udied and in oduced o
iden i y objec s secu ely and uniquely. The concep s include ha d- o-clone elec-
onic ags [13], embedded secu i y ea u es such as hose ound in bankno es,
all he way o physical inge p in s o he objec s hemsel es. Such inge p in s115
ypically esul om uncon ollable ma e ial o manu ac u ing a iabili ies and
a e well s udied in he con ex o PUFs [14, 15]. Examples include he s uc u e
o lea he , he imp in o p oduc ion-line ools, o he doping in semiconduc o s.
The a iabili y may be a common p oduc ion side-e ec (in insic) o speci i-
cally in oduced (ex insic), o ins ance by adding special pa icles [16] o colo 120
5
codes [17] o medical p oduc s.
2.2. PUFs and compu a ionally ha d p oblems
The e m PUF was used o he i s ime o cha ac e ize he physical mi-
c os uc u e in oduced by andom a ia ions o a manu ac u ing p ocess, pa -
icula ly o he CMOS ab ica ion p ocess [18, 19]. The unique a ia ions be-125
ween CMOS componen s a e exploi ed by a ha dwa e PUF o gene a e unique,
componen -speci ic esponses o iden ical challenges. Howe e , since PUF e-
sponses change sligh ly om one measu emen o ano he , he use o a uzzy
ex ac o was p oposed o help econs uc ing a cons an and unique esponse
linked o he physical cha ac e is ics o a PUF [20].130
Recen ly, he use o lea ning wi h e o (LWE) p oblems was p oposed [21]
in a LWE-based lossless compu a ional uzzy ex ac o as a way o p o ec
sec e in o ma ion in a compu a ionally secu e manne . In a e y simila way,
[22, 23] used lea ning pa i y wi h noise (LPN) o c ea e a compu a ional uzzy
ex ac o and c yp og aphically-secu e PUF. Tha p oposal uses an LPN-based135
challenge- esponse p o ocol oge he wi h a symme ic key (ob usca ed by he
compu a ional uzzy ex ac o ) o au hen ica e he PUF. Despi e he in e es ing
ad an ages o compu a ional uzzy ex ac o s, hei use is ou side he scope o
his wo k, and we will use only adi ional uzzy ex ac o s o simplici y.
2.3. Physical unclonable unc ions p ope ies and me ics140
The e is always una oidable a iabili y du ing he manu ac u ing p ocess o
any de ice. In his con ex , a PUF is a physically e alua ed unc ion ha exploi s
he andom a iabili y unin en ionally in oduced in he de ice p oduc ion. Be-
cause o he uncon ollable na u e o hese a ia ions, hey a e impossible o
clone and he esponses o a challenge can iden i y di e en de ices uniquely,145
like inge p in s.
To be conside ed as a PUF, he ollowing p ope ies mus be sa is ied [15]:
•Rep oducibili y: The esponse o a PUF o a gi en challenge mus be he
same o e ime.
6
•Uniqueness: The esponses o di e en PUFs o a gi en challenge mus be150
e y di e en .
•Unp edic abili y: I di e en challenges a e p o ided o a PUF, i s e-
sponses mus be comple ely di e en and unp edic able.
As PUF esponses a e ypically digi al hese p ope ies a e commonly e al-
ua ed using he Hamming dis ance (HD) [24] which ep esen s he pe cen age
o di e en bi s be ween PUF esponses as ollows:
HD( i, gj) = 1
L
L−1
X
b=0
i[b]⊕gj[b] (1)
whe e iand gj ep esen he esponse o a PUF o he challenge iand g o
he challenge j, espec i ely; Lis he leng h o he esponse ec o in bi s and155
bis a bi posi ion in he esponse ec o , and ’⊕’ deno es bi wise XOR.
I is he esponse o a PUF a a ime = 1 o a gi en challenge i, and g
is he esponse o his PUF a ime = 2 o he same challenge (i=j) hen
Equa ion 1 yields he in a-de ice Hamming dis ance (in a-HD), e alua ing he
ep oducibili y o he PUF esponses by i s e o , which ideally should be 0. I ,160
in con as , gis he esponse o his PUF a = 1 o a di e en challenge (i6=j)
hen Equa ion 1 e alua es he unp edic abili y o he PUF esponses by hei
simila i y, wi h an ideal alue o 50%. Finally, i gis he esponse o ano he
PUF a any ime o he same challenge, hen Equa ion 1 gi es he in e -de ice
Hamming dis ance (in e -HD) and e alua es he uniqueness o he PUFs by he165
simila i y o hei esponses, whose ideal alue is 50%.
Ano he me ic ha can be used o e alua e he PUF p ope ies is he min-
imum en opy [24]. I gi es he pe cen age o andomness in a se o sequences
wi h he ollowing equa ion:
Hmin (pmax) = 1
L
L−1
X
b=0
−log2(pmax [b]) (2)
whe e pmax [b] ep esen s he maximum p obabili y o aking logic alue 0 o 1
obse ed a he b h bi o he PUF esponse.
7
I pmax [b] is calcula ed in a single PUF using esponses o e ime o he
same challenge, hen Equa ion 2 e alua es he ep oducibili y and he minimum170
en opy should ideally be 0. I he esponses a e gene a ed using di e en chal-
lenges, hen i e alua es he unp edic abili y and he minimum en opy should
ideally be 100%. Finally, i he esponses a e ob ained om di e en PUFs, hen
he p ope y e alua ed is he uniqueness, and he minimum en opy should ide-
ally be 100%.175
2.4. Fuzzy ex ac o s
PUF esponses will be e y simila bu no exac ly he same o successi e
gene a ions. The e o e, an e o -co ec ing code (ECC) has o be implemen ed
o econs uc a s able esponse. Fuzzy ex ac o s [25] ha e been widely used in
PUFs oge he wi h a so -decision helpe -da a algo i hm [20]. The PUF quali y180
can be u he imp o ed by condi ioning esponses o elimina e uns able bi s and
bias.
To do his, he algo i hm desc ibed in [26, 27] i s akes mul iple esponses
om a PUF and compa es hem o de ec which bi s o he esponse a e s able
and which bi s a e uns able. This esul is exp essed as masks o s able and185
uns able bi s. Conside ing only he s able bi s inc eases he ep oducibili y o
he PUF esponses. The masks a e used o c ea e unique iden i ie s o keys om
s able bi s, and andom seeds om uns able bi s.
The s able bi s selec ed om he PUF esponse may be biased owa ds ei he
1 o 0 and he e o e mus be condi ioned be o e being used in a c yp og aphic190
algo i hm. In [26], he pai -ou pu on Neumann algo i hm (2O-VN) is in o-
duced o debiasing. I c ea es ano he mask ha , combined wi h he mask o
s able bi s, esul s in a selec ion mask. The bi sequence ob ained a e ap-
plying he selec ion mask is a PUF esponse wi h highe ep oducibili y and
unp edic abili y, hus sui able o c yp og aphy.195
The ope a ion o uzzy ex ac o s can be di ided in o wo phases: egis a ion
and gene a ion. The egis a ion phase akes he debiased s ing o he PUF, D,
and combines i wi h an n- imes epe i ion o a sec e key s,C=REPEAT(s, n),
8
Subsec ion 2.6, he de ice needs he sec e e o , e, o calcula e C2. Since he
de ice s o es i s public key (o i is p o ided om he ou side a e i is powe ed
up), i can compu e e=A·s⊕y. Besides, his e o can be e i ied as easily as
coun ing he numbe o bi s wi h alue ’1’ o he ec o ob ained, i.e., calcula ing350
i s Hamming weigh . As explained in [29], i he e we e a single w ong bi in
s, he ec o eob ained would look like a uni o m andom a iable, and he
p obabili y ha i s weigh we e equal o wwould be negligible hanks o he
ha dness o he xLPN p oblem. This allows he de ice no only o e i y he
co ec ness o he e o bu also o de ec i be o e exchanging any message in355
he ZK p o ocol.
4. E icien implemen a ion on a mic ocon olle
4.1. Ha dwa e pla o m
One o he main challenges o many c yp og aphic algo i hms is he an-
si ion om heo e ical desc ip ion o implemen a ion, especially when i comes360
o making e icien use o ha dwa e esou ces. We used SRAM PUFs o com-
me cial mic ocon olle s [26] o ob ain he in insic iden i y o elec onic de ices
and es i s sui abili y as sec e s o he ZK p oo s de ailed in Sec ion 3. The
in e ac i e ze o-knowledge p oo s make i impossible o ans e he us , and
so he iden i y canno be coun e ei ed.365
While he p o ocol is gene ic and simple enough o wo k in any mic ocon-
olle , he ideal de ice should ha e enough pe sis en memo y o s o e cha ac-
e iza ion da a (such as ma ix A) o a oid ecalcula ing i o e e y i e a ion
o ecei ing i om he e i ie . I is also ecommended o ha e c yp og aphic
accele a o s a ailable in low powe mic ocon olle s o simpli y he design, all370
wi hou ha ing o d aw upon mo e expensi e high- equency p ocesso s o DSPs.
We ha e implemen ed ou app oach on a Texas Ins umen s (TI) Launch-
PadTM de elopmen ki wi h a 16-bi RISC MSP430FR5994 mic ocon olle a
16 MHz. In addi ion, we designed a command-line in e ace (CLI) in MAT-
LABTM o in e ac wi h he mic ocon olle ia a se ial po . In his se up,375
15

he mic ocon olle ac s as p o e while he CLI ac s as a e i ie and sends
challenges in o de o e i y he ZK p oo s.
The mic ocon olle has 8 KB o SRAM, 256 KB o e oelec ic andom-
access memo y (FRAM) and uses a lib a y ha implemen s he NIST s anda d
o he coun e -mode de e minis ic andom bi gene a o (CTR-DRBG) [35] us-380
ing i s AES ha dwa e accele a o . I also has a low-ene gy accele a o o signal
p ocessing, se e al ul a-low-powe modes, and up o ou eUSCI po s (TI’s
enhanced uni e sal se ial communica ion in e ace). We used all hese cha ac-
e is ics o simpli y he de elopmen o ou p oo o concep .
Rega ding he use o PUFs, he de ice sel -cha ac e iza ion is mo e esou ce-385
demanding han he e i ica ion s ep. Howe e , his p ocess is ca ied ou only a
he egis a ion phase o he uzzy ex ac o and can be ully au oma ed wi hin
he de ice. Wi h espec o he ZK p o ocol, he asks ha equi e he highes
compu a ional powe a e he mul iplica ion o ma ices and he gene a ion o
andom numbe s. The implemen a ion o all hese algo i hms and he pa icula 390
solu ions p oposed a e p esen ed in he ollowing.
4.2. Sel -cha ac e iza ion
While many TI mic ocon olle s a e low powe , hose o he FRAM amily
ea u e ul a-low-powe modes. They can shu down pa s o he sys em on a
chip (SoC) in a con olled way, powe ing down anscei e s and pe iphe als,395
clocks and he SRAM.
We use he ul a-low-powe mode LPM 3.5 and he eal- ime clock o powe
cycle he p ocesso a e a p ede ined ime o e ase he in o ma ion s o ed in
SRAM and all egis e s. A e each powe cycle, he SRAM s a -up alues
ep esen he PUF esponses used in he uzzy ex ac o , as de ailed in Subsec-400
ion 2.4. The FRAM, which is non- ola ile, is employed o s o e he mul iple
measu emen s o PUF esponses needed o gene a e he bi -selec ion mask.
4.3. Ma ix and ec o ope a ions in xLPN
Ma ix and ec o mul iplica ions a e compu a ionally cos ly ope a ions. In
he p o ocol employed, hey a e equi ed o gene a e he public key in he o m405
16
y=A·s⊕e, o calcula e he pe ec ly binding commi men (as de ailed in
Subsec ion 2.6), and o gene a e he commi men messages o he p oo s (as
de ailed in Subsec ion 2.7).
As discussed in [29], xLPN ope a ions ha e a simila complexi y o decoding
andom linea codes. Thanks o wo king wi h bina y ec o p oduc s and XOR410
sums, he ope a ions a e equi alen o pe o ming linea combina ions o ec o s.
The bina y ec o sin he ope a ion y=A·s⊕eindica es which columns o A
should pa icipa e in he calcula ion o he pa i y sum along wi h he ec o e.
Only he columns ha a e mul iplied by a non-ze o alue a ec he esul . One
way o combine he ec o p oduc s is employing XOR sums, educing he xLPN415
p oduc o linea combina ions o he columns o A ha a e mul iplied by non-
ze o elemen s o s. Figu e 2 shows an example in which he non-ze o elemen s o s
a e {0,2,3}, and he e o e ycan be calcula ed as y=A(:,0)⊕A(:,2)⊕A(:,3)⊕e.
𝒚 = 𝑨 ∙ 𝒔 ⨁ 𝒆
𝑘 𝑘
ℓ
+
𝑛
𝑘
ℓ+ 𝑛
10101
10001
10110
10011
00100
11010
10001
00101
11001
01100
1
0
1
1
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
1
1
1
0
Figu e 2: Linea combina ions o Acolumns wi h noise e.
When his ope a ion is used o calcula e he commi men s, he claimed in-
17
o ma ion mus be compac ed o he size o s, which is analogous o gene a ing420
mul iple p oduc s o ma ix Awi h pieces o he claim, and hen add an e o e.
In o he wo ds, when used o calcula ing Com(m) = A·( ||m)⊕ewi h m∈ In,
i o example he claim mhad size k=O(n) = β·nins ead o size n, and i
could be desc ibed as m= [m1, m2, ..., mβ], hen:
Com(m) =
β
M
i=1
[A·( i||mi)] ⊕e=A· ||
β
M
i=1
[mi]!⊕e
o eR
← Ik
w, i
R
← I`, and Lβ
i=1 i= . In his equa ion, he message o 425
leng h βn is compac ed using XOR ope a ions in o a message o leng h n, and
only a single xLPN ope a ion is equi ed o calcula e he commi men o his
claim. This comp ession is e y use ul especially o he commi men o he
andom pe mu a ion which helps o educe he size om k·log2(k) o n.
4.4. Va ian s o he de e minis ic andom bi gene a o 430
The p o ocol equi es andom ec o s om a uni o m dis ibu ion in mul iple
s eps. We gene a e hem using he mic ocon olle ’s AES ha dwa e accele a o
in he NIST app o ed CTR-DRBG mode4. O he pa s o he algo i hm, such
as he weigh ed e o s o he andom ec o pe mu a ions, equi e andom se-
quences o a di e en na u e. The algo i hms used o adap he andom numbe 435
gene a o o ul ill hese p o ocol equi emen s a e desc ibed in he ollowing.
4.4.1. Weigh ed uni o m andom bi gene a o
The CTR-DRBG unc ions a e used o gene a e a weigh ed uni o m dis i-
bu ion. The sequences needed by he xLPN p oblem should ha e a Hamming
weigh no o won a e age bu exac ly equal o w. To achie e his, he imple-440
men ed algo i hm s a s om an all-ze os ec o o kelemen s deno ed as 0k.
Since he esul ing ec o mus ha e a cons an weigh , i means ha w=bτke
ones a e inse ed in he sequence o ze os. The posi ions in which he wones a e
4Al e na i ely, a C implemen a ion o he AES algo i hm can be used o a p ocesso
wi hou such an accele a o .
18
in oduced ollow a uni o m dis ibu ion o andom alues in he ange [0, k −1]
p o ided by he CTR-DRBG. I a andom posi ion is epea ed, i is disca ded,445
and a new posi ion is gene a ed un il wones a e inse ed. Figu e 3 shows he
diag am ha desc ibes he algo i hm.
2
Fo ha
eason,
ou
modi ica ion o e he Knu h Shu le algo i hm pe o ms a modulo ope a ion, bu only using powe s o 2
𝑤
[0,𝑘 − 1]
0𝑘→
1𝑤
Figu e 3: Weigh ed andom numbe gene a o using CTR-DRBG.
4.4.2. Random pe mu a ion gene a ion
Ins ead o gene a ing andom posi ions by ial and e o o all elemen s o a
ec o , we de eloped and implemen ed a a ian o he Knu h shu le algo i hm.450
The o iginal algo i hm s a s wi h any pe mu a ion ( o example, he iden i y
pe mu a ion) w i en o a s ing π[ ] o size k. Then, i poin s o posi ions
0 h ough k−2 using an index a iable i(assuming he ec o elemen s a e
indexed 0 o k−1). Fo each posi ion o i, he algo i hm swaps he elemen in
ha posi ion wi h a andomly chosen elemen be ween and including posi ions455
iand k−1 ( he end o he ec o ).
The e a e some issues ega ding he andom numbe gene a ion in he ange
i o k–1. The CTR-DRBG o he chosen mic ocon olle always p oduces a
128-bi ou pu , so he ou pu is pos -p ocessed o ma ch he in e al [i, k–1].
19
Applying echniques such as modulo ope a o o he ou pu o he RNG will no 460
gene a e he uni o m ou pu in he desi ed ange bu a biased s ing in which
he lowe pa o he ange has a highe p obabili y o occu ence.
[𝑘 − 𝑥,𝑘 − 1]
M andom numbe s (posi ions)
0
𝑘 ze os bi s ing
𝑘 bi s wi h exac ly
⌊𝑘 × 𝜏⌉ weigh
1
⌊𝑘 × 𝜏⌉ one bi s
𝑚𝑜𝑑(𝑥)+𝑘 − 𝑥
[0,2128 − 1]
Figu e 4: Random pe mu a ion gene a o based on he Knu h shu le.
To add ess his p oblem, ou modi ica ion o he Knu h shu le algo i hm,
shown in Figu e 4, pe o ms a modulo ope a ion using only powe s o 2 (which
is equi alen o elimina ing he leas signi ican bi s). Wi h his change i gen-465
e a es andom numbe s in he ange [0, x −1] o x= 2n, making he Knu h
shu le algo i hm mo e e icien while main aining a p obabili y o occu ence
ha ollows he uni o m dis ibu ion. Besides, kmus be a powe o wo so ha
he absence o bias is also sa is ied when educing he ange o andom numbe s
om [0,2128 −1] o [0, k−1]. I is wo h no ing ha modulo 2nope a ions can be470
implemen ed by shi ing a egis e by nbi s. This g ea ly simpli ies compu ing
on any de ice wi h limi ed esou ces.
20

The modi ied Knu h shu le algo i hm o andom pe mu a ions is summa-
ized in algo i hm 1. The p obabili y o epea ing a andom posi ion will be
always in he ange (0,0.5) wi h his modi ica ion. Wi h he o iginal imple-475
men a ion (wi hou applying modulo) he p obabili y o epea ing a andom
posi ion ends o (1 −1/k) when i ends o k. Gi en ha each i e a ion o he
ZK p o ocol equi es pe mu a ions, his imp o emen subs an ially inc eases he
pe o mance o ou implemen a ion.
Algo i hm 1 Random pe mu a ion gene a o based on he Knu h shu le
p ocedu e Gene a e a andom pe mu a ion, π∈ Sk
Ini ialize a iables:
π←[0,1,2,3, ..., k −2, k −1]
i←0
while i < k:
x←2dlog2(k−i)e
p←CTR-DRBG[0,2128 −1] mod (x)+k−x
i p≥i hen
swap(π[i], π[p])
i←i+ 1
5. Expe imen al esul s480
This sec ion de ails he expe imen al esul s as well as he p o ocol imple-
men a ion. P o ec ion o he de ice agains side-channel a acks is beyond he
scope o his wo k. To p e en some o hese a acks, such as di e en ial powe
analysis (DPA), he sys em should be buil in such a way ha i is impossible
o ex ac any in o ma ion om he ou side, e.g., by measu ing elec omagne ic485
adia ion. Conside ing a acks ia he JTAG po , he secu i y uses should
be blown once he de ice is pu in o p oduc ion. These coun e measu es a e
conside ed s anda d in he indus y when dealing wi h secu e sys ems.
We an he expe imen s on 10 TI LaunchPadsTM wi h MSP430FR5994 mi-
21
c ocon olle s. In o al we ook 120 eadings o he comple e SRAM (8 KB)490
o each mic ocon olle a 3 di e en empe a u es, wi h he de ice powe ed
o be ween measu emen s o wo seconds by LPM 3.5.5This numbe o mea-
su emen s and ope a ing condi ions ha e p o en o be su icien o cha ac e ize
SRAMs co ec ly and ob ain hei mask in an e icien way [24]. F om each
se o 120 measu emen s, we used 20 measu emen s o compu e he selec ion495
mask o he de ices. Wi h he emaining 100 measu emen s we e alua ed he
p ope ies o he mic ocon olle SRAM PUFs ( ep oducibili y, uniqueness, and
unp edic abili y).
As shown in [24], empe a u e a ia ions al e he beha io o SRAM PUFs
signi ican ly. The empe a u es suppo ed by he mic ocon olle ange om500
−40 ◦C o +85 ◦C, acco ding o he manu ac u e . We conduc ed expe imen s a
a±5◦C ma gin om hese bounda ies, a −35 ◦C and 80 ◦C, and a a con olled
nominal empe a u e o 25 ◦C.
We calcula ed he in a-de ice Hamming dis ance (in a-HD) and in e -
de ice Hamming dis ance (in e -HD) acco ding o Equa ion 1. Figu e 5(a) shows505
in a-HD in one de ice a −35 ◦C wi h and wi hou selec ion mask, and Fig-
u e 5(b) he in e -HD conside ing all he 10 de ices a −35 ◦C. Figu es 6 and
7 show he same in a-HD and in e -HD ep esen a ions a 25 ◦C and 80 ◦C,
espec i ely.
I can be seen how he selec ion mask d as ically educes he in a-HD by510
mo e han 50% a ex eme empe a u es, and app oxima ely 90% in nominal
condi ions, app oaching he op imal in a-HD alue o 0%. The in e -HD dis i-
bu ions, on he o he hand, a e p ac ically una ec ed by he mask wi h a e ages
a ound he ideal uniqueness alue o 50%.
Ano he c i ical pa o he ze o-knowledge p oo p o ocol is he gene a ion515
o andom numbe s. I is impo an o e alua e he quali y, i.e., unp edic abili y
5The ime be ween measu emen s has been de e mined by cha ac e izing he mic ocon-
olle s o his pa icula p o o ype. I mus be adjus ed o each indi idual ype o mic ocon-
olle o in eg a ed ci cui .
22
(a) (b)
Figu e 5: In a- and in e -de ice Hamming dis ance (exp essed in %) wi h and wi hou selec-
ion mask a −35 ◦C.
o he seeds ha a e used o eed he pseudo andom numbe gene a o . Since
hese seeds come om he uns able cells o he SRAM, we mus e alua e hei
minimum en opy as de ailed in Equa ion 2. The expe imen al esul s o his
me ic can be seen in Figu e 8, wi h and wi hou selec ion mask, a −35 ◦C,520
25 ◦C and 80 ◦C.
10 20 30 40 50 60 70 80 90 100
Numbe o measu emen s
0
5
10
15
20
25
30
35
Pe cen age o Hmin
Masked a -35ºC
Unmasked a -35ºC
Masked a 25ºC
Unmasked a 25ºC
Masked a 80ºC
Unmasked a 80ºC
Figu e 8: Minimum en opy a −35 ◦C, 25 ◦C and 80 ◦C, wi h and wi hou selec ion mask.
23
(a) (b)
Figu e 6: In a- and in e -de ice Hamming dis ance (exp essed in %) wi h and wi hou selec-
ion mask a 25 ◦C.
Tables 1 and 2 show he indi idual measu emen s o a e age in a-HD and
minimum en opy in he en de ices, cha ac e ized a −35 ◦C, 25 ◦C and 80 ◦C,
bo h wi h and wi hou he mask. We obse e ha he ela i e beha io o all
de ices is simila , jus showing sligh ly di e en absolu e alues owing o hei 525
di e en manu ac u ing a ia ions.
De ice 1 2 3 4 5 6 7 8 9 10
Unmasked a −35 ◦C 5.18 5.31 5.02 4.24 3.98 4.94 4.23 5.14 4.91 4.86
Masked a −35 ◦C 1.99 3.86 3.79 3.86 2.31 2.35 1.96 3.96 1.95 2.65
Unmasked a 25 ◦C 4.98 5.02 4.90 5.03 4.27 4.89 4.58 4.58 5.02 4.59
Masked a 25 ◦C 0.44 0.45 0.42 0.45 0.36 0.43 0.40 0.38 0.42 0.33
Unmasked a 80 ◦C 4.85 4.71 4.67 4.40 4.80 4.71 4.90 3.57 4.41 4.11
Masked a 80 ◦C 2.45 2.70 2.48 3.50 3.51 2.41 3.36 1.58 2.01 1.98
Table 1: A e age in a-HD pe cen age o en de ices a −35 ◦C, 20 ◦C and 80 ◦C wi h and
wi hou mask.
24
Re e ences
[1] A. No d um, Popula In e ne o Things Fo ecas o 50 Billion De ices by
2020 Is Ou da ed, IEEE Spec um (2016) 0–2.635
URL h ps://spec um.ieee.o g/ ech- alk/ elecom/in e ne /
popula -in e ne -o - hings- o ecas -o -50-billion-de ices-by-2020-is-ou da ed
[2] N. Kshe i, Blockchain’s oles in mee ing key supply chain managemen
objec i es, In e na ional Jou nal o In o ma ion Managemen 39 (2018)
80–89. doi:10.1016/J.IJINFOMGT.2017.12.005.640
URL h ps://www.sciencedi ec .com/science/a icle/pii/
S0268401217305248
[3] K. W¨us , A. Ge ais, Do you need a Blockchain?, ep in .iac .o g.
URL h ps://ep in .iac .o g/2017/375.pd
[4] Q. Xu, C. Jin, M. F. B. M. Rasid, B. Vee a alli, K. M. M. Aung,645
Blockchain-based decen alized con en us o docke images, Mul ime-
dia Tools and Applica ions 77 (14) (2018) 18223–18248. doi:10.1007/
s11042-017-5224-6.
URL h p://link.sp inge .com/10.1007/s11042-017-5224-6
[5] P ese ing ai c a alue: echnical eco ds in comme cial leases.650
URL h ps://ae o ime.ae o/zi ile.zalagenai e/
20740-p ese ing-ai c a - alue- echnical- eco ds-in-comme cial-leases
[6] Pha maceu ical T aceabili y.
URL h ps://www.hda.o g/issues/pha maceu ical- aceabili y
[7] E. And oulaki, A. Ba ge , V. Bo niko , C. Cachin, K. Ch is idis, A. De655
Ca o, D. Enyea , C. Fe is, G. La en man, Y. Mane ich, S. Mu alidha-
an, C. Mu hy, B. Nguyen, M. Se hi, G. Singh, K. Smi h, A. So nio i,
C. S a hakopoulou, M. Vukoli´c, S. W. Cocco, J. Yellick, Hype ledge Fab-
ic: A Dis ibu ed Ope a ing Sys em o Pe missioned Blockchains, in:
P oceedings o he Thi een h Eu oSys Con e ence, ACM, 2018. doi:660
31

10.1145/3190508.3190538.
URL h p://a xi .o g/abs/1801.10228
[8] M. U. Hassan, M. H. Rehmani, J. Chen, P i acy p ese a ion in blockchain
based IoT sys ems: In eg a ion issues, p ospec s, challenges, and u u e
esea ch di ec ions, Fu u e Gene a ion Compu e Sys ems 97 (2019)665
512–529. doi:10.1016/J.FUTURE.2019.02.060.
URL h ps://www.sciencedi ec .com/science/a icle/pii/
S0167739X18326542
[9] M. A. Khan, K. Salah, IoT secu i y: Re iew, blockchain solu ions, and
open challenges, Fu u e Gene a ion Compu e Sys ems 82 (2018) 395–411.670
doi:10.1016/j. u u e.2017.11.022.
URL h ps://linkinghub.else ie .com/ e ie e/pii/
S0167739X17315765
[10] M. M. Teh anipoo , U. Guin, S. Bhunia, In asion o he ha dwa e sna che s,
IEEE Spec um 54 (5) (2017) 36–41. doi:10.1109/MSPEC.2017.7906898.675
URL h p://ieeexplo e.ieee.o g/documen /7906898/
[11] C. Shephe d, G. A aoui, I. Gu ulian, R. P. Lee, K. Ma kan onakis,
R. N. Ak am, D. Sau e on, E. Conchon, Secu e and T us ed Execu-
ion: Pas , P esen , and Fu u e - A C i ical Re iew in he Con ex
o he In e ne o Things and Cybe -Physical Sys ems, in: 2016 IEEE680
T us com/BigDa aSE/ISPA, IEEE, 2016, pp. 168–177. doi:10.1109/
T us Com.2016.0060.
URL h p://ieeexplo e.ieee.o g/documen /7846943/
[12] GS1 UniqueID — GS1.
URL h ps://www.gs1.o g/gs1-uniqueid685
[13] C yp oSeal (CSS100) – Ch onicled.
URL h ps://s o e.ch onicled.com/p oduc s/c yp o-seal-s ip
32
[14] R. Maes, Physically unclonable unc ions : cons uc ions, p ope ies and
applica ions, Sp inge , 2013.
[15] C. B¨ohm, M. Ho e , C. Bohm, M. Ho e , Physical Unclonable Func ions in690
Theo y and P ac ice., Sp inge , 2012. doi:10.1007/978-1-4614-5040-5.
[16] G. M. Miyake, R. A. Wei ekamp, V. A. Piuno a, R. H. G ubbs, Syn hesis o
Isocyana e-Based B ush Block Copolyme s and Thei Rapid Sel -Assembly
o In a ed-Re lec ing Pho onic C ys als, Jou nal o he Ame ican Chemical
Socie y 134 (34) (2012) 14249–14254. doi:10.1021/ja306430k.695
URL h p://pubs.acs.o g/doi/10.1021/ja306430k
[17] O. G¨ok¸ce, C. Me cande i, E. Delama che, High-Con en Op ical Codes o
P o ec ing Rapid Diagnos ic Tes s om Coun e ei ing, Analy ical Chem-
is y 90 (12) (2018) 7383–7390. doi:10.1021/acs.analchem.8b00826.
URL h p://pubs.acs.o g/doi/10.1021/acs.analchem.8b00826700
[18] R. Pappu, B. Rech , J. Taylo , N. Ge shen eld, Physical One-Way Func-
ions, Science 297 (5589).
[19] B. Gassend, D. Cla ke, M. an Dijk, S. De adas, Silicon physical andom
unc ions, in: P oceedings o he 9 h ACM con e ence on Compu e and
communica ions secu i y - CCS ’02, ACM P ess, New Yo k, New Yo k,705
USA, 2002, p. 148. doi:10.1145/586110.586132.
URL h p://po al.acm.o g/ci a ion.c m?doid=586110.586132
[20] R. Maes, P. Tuyls, I. Ve bauwhede, Low-O e head Implemen a ion o a
So Decision Helpe Da a Algo i hm o SRAM PUFs, Sp inge , Be lin,
Heidelbe g, 2009, pp. 332–347. doi:10.1007/978-3-642-04138-9_24.710
URL h p://link.sp inge .com/10.1007/978-3-642-04138-9{_}24
[21] C. Hu h, D. Becke , J. G. Me chan, P. Duplys, T. Guneysu, Secu ing
Sys ems Wi h Indispensable En opy: LWE-Based Lossless Compu a ional
Fuzzy Ex ac o o he In e ne o Things, IEEE Access 5 (2017) 11909–
33
11926. doi:10.1109/ACCESS.2017.2713835.715
URL h p://ieeexplo e.ieee.o g/documen /7944563/
[22] C. He de , L. Ren, M. an Dijk, M.-D. Yu, S. De adas, T apdoo com-
pu a ional uzzy ex ac o s and s a eless c yp og aphically-secu e physical
unclonable unc ions, IEEE T ansac ions on Dependable and Secu e Com-
pu ing 14 (1) (2017) 65–82. doi:10.1109/TDSC.2016.2536609.720
URL h p://ieeexplo e.ieee.o g/documen /7422776/
[23] C. Jin, C. He de , L. Ren, P. Nguyen, B. Fulle , S. De adas, M. an
Dijk, FPGA Implemen a ion o a C yp og aphically-Secu e PUF Based
on Lea ning Pa i y wi h Noise, C yp og aphy 1 (3) (2017) 23. doi:
10.3390/c yp og aphy1030023.725
URL h p://www.mdpi.com/2410-387X/1/3/23
[24] I. Ba u one, M. A. P ada-Delgado, S. Ei oa, Imp o ed Gene a ion o Iden-
i ie s, Sec e Keys, and Random Numbe s F om SRAMs, IEEE T ans-
ac ions on In o ma ion Fo ensics and Secu i y 10 (12) (2015) 2653–2668.
doi:10.1109/TIFS.2015.2471279.730
URL h p://ieeexplo e.ieee.o g/documen /7217837/
[25] Y. Dodis, R. Os o sky, L. Reyzin, A. Smi h, Fuzzy Ex ac o s: How o
Gene a e S ong Keys om Biome ics and O he Noisy Da a, SIAM Jou -
nal on Compu ing 38 (1) (2008) 97–139. doi:10.1137/060651380.
URL h p://epubs.siam.o g/doi/10.1137/060651380735
[26] M. A. P ada-Delgado, A. Vazquez-Reyes, I. Ba u one, Physical unclonable
keys o sma lock sys ems using Blue oo h Low Ene gy, in: IECON 2016 -
42nd Annual Con e ence o he IEEE Indus ial Elec onics Socie y, IEEE,
2016, pp. 4808–4813. doi:10.1109/IECON.2016.7792955.
URL h p://ieeexplo e.ieee.o g/documen /7792955/740
[27] R. A jona, M. A. P ada-Delgado, J. A cenegui, I. Ba u one, A PUF- and
Biome ic-Based Ligh weigh Ha dwa e Solu ion o Inc ease Secu i y a
34
Senso Nodes, Senso s 18 (8) (2018) 2429. doi:10.3390/s18082429.
URL h p://www.mdpi.com/1424-8220/18/8/2429
[28] S. Goldwasse , S. Micali, C. Racko , The knowledge complexi y o in e -745
ac i e p oo -sys ems, in: P oceedings o he se en een h annual ACM sym-
posium on Theo y o compu ing - STOC ’85, ACM P ess, New Yo k, New
Yo k, USA, 1985, pp. 291–304. doi:10.1145/22145.22178.
URL h p://po al.acm.o g/ci a ion.c m?doid=22145.22178
[29] A. Jain, S. K enn, K. Pie zak, A. Ten es, Commi men s and E icien 750
Ze o-Knowledge P oo s om Lea ning Pa i y wi h Noise, Sp inge , Be lin,
Heidelbe g, 2012, pp. 663–680. doi:10.1007/978-3-642-34961-4_40.
URL h p://link.sp inge .com/10.1007/978-3-642-34961-4{_}40
[30] N. M. D¨o ling, C yp og aphy based on he Ha dness o Decoding, Ph.D.
hesis (2014).755
[31] K. Pie zak, C yp og aphy om Lea ning Pa i y wi h Noise, Sp inge ,
Be lin, Heidelbe g, 2012, pp. 99–114. doi:10.1007/978-3-642-27660-6_
9.
URL h p://link.sp inge .com/10.1007/978-3-642-27660-6{_}9
[32] N. Yao, Y. Yu, X. Li, D. Gu, On he Robus ness o Lea ning Pa -760
i y wi h Noise, Sp inge , Cham, 2016, pp. 99–106. doi:10.1007/
978-3-319-50011-9_8.
URL h p://link.sp inge .com/10.1007/978-3-319-50011-9{_}8
[33] E. Ba ke , A. Roginsky, Recommenda ion o C yp og aphic Key Gen-
e a ion, Tech. ep., Na ional Ins i u e o S anda ds and Technology,765
Gai he sbu g, MD (dec 2012). doi:10.6028/NIST.SP.800-133.
URL h ps://n lpubs.nis .go /nis pubs/SpecialPublica ions/
NIST.SP.800-133.pd
[34] L. Chen, Recommenda ion o key de i a ion using pseudo andom unc-
ions ( e ised), Tech. ep., Na ional Ins i u e o S anda ds and Technology,770
35
Gai he sbu g, MD (2009). doi:10.6028/NIST.SP.800-108.
URL h ps://n lpubs.nis .go /nis pubs/Legacy/SP/
nis specialpublica ion800-108.pd
[35] E. B. Ba ke , J. M. Kelsey, Recommenda ion o Random Numbe Gene -
a ion Using De e minis ic Random Bi Gene a o s, Tech. ep., Na ional775
Ins i u e o S anda ds and Technology, Gai he sbu g, MD (jun 2015).
doi:10.6028/NIST.SP.800-90A 1.
URL h ps://n lpubs.nis .go /nis pubs/SpecialPublica ions/
NIST.SP.800-90A 1.pd
[36] A. Esse , R. K¨uble , A. May, LPN Decoded, Sp inge , Cham, 2017, pp.780
486–514. doi:10.1007/978-3-319-63715-0_17.
URL h p://link.sp inge .com/10.1007/978-3-319-63715-0{_}17
36