Recei ed: May 2, 2024. Re ised: Augus 9, 2024. Accep ed: Oc obe 4, 2024
© The Au ho (s) 2024. Published by Ox o d Uni e si y P ess on behal o The B i ish Compu e Socie y.
This is an Open Access a icle dis ibu ed unde he e ms o he C ea i e Commons A ibu ion License (h ps://c ea i ecommons.o g/licenses/by/4.0/), which
pe mi s un es ic ed euse, dis ibu ion, and ep oduc ion in any medium, p o ided he o iginal wo k is p ope ly ci ed.
The Compu e Jou nal, 2024, 1–12
h ps://doi.o g/10.1093/comjnl/bxae109
O iginal A icle
Game on: a pe o mance compa ison o in e pola ion
echniques applied o Shami ’s sec e sha ing
Anas assis Voudou is1,*,A is omenis T essos1,Apos olis Za as2,Ch is os Xenakis1
1Uni e si y o Pi aeus, G eece
2Founda ion o Resea ch and Technology—Hellas, G eece
*Co esponding au ho : Uni e si y o Pi aeus, G eece. E-mail: anas assis. oudou [email protected]
Abs ac
Public-key enc yp ion is ypically managed h ough a public key in as uc u e. Howe e , i elies on a cen al con ol poin , he
ce i ica ion au ho i y, which ac s as a single poin o ailu e. Recen echnological ad ancemen s ha e led o he need o decen alized
c yp og aphic p o ocols. This pape p esen s a comp ehensi e s udy on enhancing public-key enc yp ion ia h eshold c yp og aphy
and mul ipa y compu a ion o ensu e obus secu i y in decen alized sys ems. The ocus lies in explo ing a ious polynomial
in e pola ion echniques wi hin Shami ’s sec e sha ing scheme, pa icula ly add essing he e iciency and p ac icali y o New on
in e pola ion, as Fou ie ans o ma ion (FFT), and ad anced e sions o Lag ange’s me hod. U ilizing SageMa h o a dedica ed es ing
en i onmen , he esea ch in es iga es he swi es in e pola ion me hods o sec e eco e y, in oducing new sha es in o he sys em,
and e alua ing he impac o op imiza ions on pe o mance. The indings highligh FFT as he mos e ec i e in e pola ion me hod
in speed and e iciency, albei wi h limi a ions on he numbe o sha es ha can be p ocessed. This pape c i ically e alua es hese
in e pola ion echniques agains p ac ical cons ain s and aims o answe pi o al esea ch ques ions ega ding he op imal app oach
o la ge-scale scena ios, challenging exis ing no ions on he e iciency o New on’s me hod and p o iding expe imen al e idence o
suppo he supe io i y o FFT in speci ic con ex s.
1. INTRODUCTION
Public-key enc yp ion in c yp og aphic schemes is commonly
managed h ough a public key in as uc u e (PKI). PKI ensu es
secu e communica ion ac oss insecu e public ne wo ks by
employing digi al signa u es o au hen ica e en i ies. PKI elies
on he secu i y o a cen al con ol poin , named he ce i ica ion
au ho i y (CA), and is conside ed us ed by all; howe e , i also
ac s as a single poin o ailu e. I his poin ge s comp omised,
he en i e ne wo k’s secu i y will all. Recen echnological
ad ancemen s showed ha he esea ch communi y needs o
s eng hen cu en c yp og aphic p o ocols in a decen alized
manne [1]. New ideas a e d i en by a well-s udied a ea o
c yp og aphy called h eshold c yp og aphy [2]. A (n,k) h eshold
c yp og aphy scheme allows nen i ies o sha e he abili y o
pe o m a c yp og aphic ope a ion so ha any ken i ies su ice
o pe o m his ope a ion join ly. In con as , i is in easible o a
mos k−1en i ies o do so, e en by collusion. A c yp og aphic
key, which will be used o enc yp he message ansmi ed
om one pe son o ano he , is he undamen al ool o bo h
symme ic and asymme ic c yp og aphy and mus be p o ec ed,
om he gene a ion pa o he sec e sha ing among he g oup’s
en i ies.
Sec e sha ing and h eshold c yp og aphy a e bo h b anches
o he same ee, called, in gene al e ms, mul ipa y compu a-
ion (MPC). One secu i y applica ion o MPC is o p o ec c yp o-
g aphic keys om he and misuse by ne e ha ing hem exposed
a any single poin a any single ime and by en o cing usage
policies a mul iple en i ies. By emb acing MPC’s abili y o p o ec
c yp og aphic keys in so wa e, an al e na i e o legacy ha dwa e
solu ions, such as T us ed Pla o m Module’s oo o us , is p o-
ided, mi iga ing many ope a ional challenges in oday’s hyb id
and mul i-cloud en i onmen s.
Shami ’s sec e sha ing scheme (SSS) is he main sub-module
o h eshold c yp og aphic p o ocols [3]. Assuming ha us is
es ablished, a deale owning a sec e desi es o dis ibu e his
sec e among a g oup o nsha eholde s. A sha ed sec e is gen-
e a ed by a us ed deale , who dis ibu es a sha e (o a c yp o-
g aphic key, o example) o each membe o he g oup, such ha
any subse o size g ea e han a h eshold ( )can e eal o use he
sha ed sec e , while smalle subse s do no ha e any knowledge
abou i . The co e sub ou ine o SSS is Lag ange’s in e pola ion,
h ough which he sha ed sec e is e en ually econs uc ed.
I is no ewo hy ha nume ous op imiza ions o Lag ange’s
in e pola ion ha e been documen ed in he li e a u e, aimed
a accele a ing he compu a ion o Lag ange polynomials and
ob aining he cons an e m o he in e pola ing polynomial,
which se es as he sec e in he s anda d SSS scheme [4].
Addi ionally, he e a e a ious o he me hods a ailable o
in e pola ion. He e a e a ew no able cases: mul i-sec e schemes
in ol e using he sec e sas he highes deg ee coe icien ,
he eby inc easing he e iciency o ano he in e pola ion me hod
called New on’s in e pola ion [5]. The adop ion o New on’s
in e pola ion has also been p oposed in a ecen academic
publica ion whe e he au ho s explo e he applica ion o his
Downloaded om h ps://academic.oup.com/comjnl/ad ance-a icle/doi/10.1093/comjnl/bxae109/7900561 by gues on 02 Decembe 2024
2|Voudou is e al.
app oach in he con ex o Mul i-Fac o au hen ica ion du ing
he in oduc ion o a new node in a communica ion p o ocol [6].
Fu he mo e, Tomescu e al.[
7] agg ega e a Boneh–Lynn–Shacham
signa u e [8] 3000 imes as e in 46 s compa ed wi h 1.5 days i
done nai ely. This imp o emen is achie ed by u ilizing a Fas
Lag ange in e pola ion algo i hm, which has a ime complexi y
o ( log
2 ), whe e in n o al use s, he >n/2mus be
hones ,and inco po a es a Fas Fou ie in e pola ion me hod.This
app oach ou pe o ms he nai e Lag ange algo i hm, which has a
ime complexi y o ( 2). This cen e s on explo ing al e na i e
in e pola ion echniques ins ead o he adi ional Lag ange
me hod, ocusing on enhancing pe o mance.
In esponse o conce ns ega ding in e pola ion me hods
wi hin he con ex o SSS, his a icle p esen s a comp ehensi e
explo a ion o a ious polynomial in e pola ion echniques.
The me hodologies sc u inized include New on in e pola ion,
he as Fou ie ans o ma ion (FFT), and wo e inemen s o
Lag ange’s me hod. The esea ch u ilizes a dedica ed es ing
en i onmen , employing SageMa h [9], a eely a ailable open-
sou ce ma hema ics so wa e sys em licensed unde he GPL,
and u ilizing Py hon-based language. The es ing en i onmen
accommoda es ields wi h di e se use coun s and speci ic
ma hema ical p ope ies. Addi ionally, he au ho s del e in o
he implica ions o in oducing new sha es in o he sys em,
akin o a simple communica ion p o ocol. Expe imen al indings
demons a e ha , in e ms o pe o mance, he FFT eme ges
as he mos e icien in e pola ion me hod in bo h scena ios.
Howe e , i is no ewo hy ha limi a ions exis ega ding he
numbe o sha es ha can be e ec i ely u ilized. O e all, his
a icle poses h ee main esea ch ques ions: (i) Wha is he
swi es me hod and mos sui able in la ge-scale scena ios o
in e pola e he polynomial in he con ex o SSS o eco e
he sec e om he cons an e m? (ii) Wha is he quickes
app oach o in e pola e he polynomial o eco e ing he sec e
when adding addi ional membe s/sha es? (iii) Do op imiza ions
(e.g. p ecompu ing alues) a ec he o e all pe o mance o
in e pola ion me hods? These esea ch ques ions o m he basis
o his wo k.
In summa y, his a icle makes he ollowing main con ibu-
ions:
•A comp ehensi e examina ion o di e en in e pola ion
echniques and hei implemen a ion in he SSS scheme.
• A speci ic use case add essing he addi ion o new sha es and
he subsequen econs uc ion o he sec e , challenging he
asse ion by Bezza ee e al.[
6] ega ding New on’s me hod
as he swi es .
• Expe imen al e idence demons a ing he supe io e iciency
o he FFT compa ed wi h o he me hods.
The emainde o his pape is o ganized as ollows. In Sec-
ion 2, we elabo a e on se e al undamen al concep s in c yp og-
aphy, encompassing ini e ields and oo s o uni y, culmina ing
in an exhaus i e explo a ion o SSS. Mo ing o wa d, Sec ion 3
conduc s an in-dep h analysis o a ious in e pola ion me h-
ods, including Lag ange’s me hod, i s op imiza ions, New on’s
me hod, and a specialized case in ol ing FFT. Sec ion 4encap-
sula es he culmina ion o all he expe imen s. In Sec ion 5,
a concise discussion add esses he o iginal esea ch ques ions.
Addi ionally, Sec ion 6includes a numbe o esea ch pape s ha
employ a ious in e pola ion me hods wi hin he con ex o SSS,
ollowing he no able con ibu ions o Shami and Blakley. Finally,
Sec ion 7w aps up he pape by ou lining a enues o u u e
esea ch and posing pe inen ques ions.
2. BACKGROUND
Be o e del ing in o he concep s o sec e sha ing and polynomial
in e pola ion, i is impe a i e o es ablish a ounda ional unde -
s anding. To enhance he cla i y o subsequen sec ions in ou
wo k, we aim o lucidly p esen essen ial ma hema ical concep s
om a ious ields, a icula ing de ini ions and heo ems wi hou
p oo . Reade s a e guided o he ele an e e ences o comp e-
hensi e insigh when u he elucida ion is equi ed.
2.1. Ma hema ical ounda ions
As a p e equisi e o he undamen als o c yp og aphic heo y,
a g asp o ini e ields and g oups is indispensable. The ensuing
pa ag aphs u nish a concise in oduc ion o i al ma hema ical
concep s, laying he g oundwo k o a comp ehensi e unde -
s anding o ou implemen a ions and app oaches o polynomial
in e pola ion.
Fini e ields. The se o eal numbe s, R, has in ini e o de , i.e.
con ains an in ini e numbe o elemen s, whe eas a ini e ield, o
Galois Field (GF), has a ini e o de . GF(p)(o Fp),whe e pis p ime, is
a ini e ield wi h ini e o de pand is mos ly used in c yp og aphic
applica ions due o i s excellen p ope ies. No e ha he o de
o a ini e ield is always a p ime po a p ime powe , pn[10].
Fini e ields ha e wo ope a ions (i.e. addi ion and mul iplica ion),
which adop hem om he co esponding g oups. A undamen al
in ui ion o g oups, especially he cyclic ones, is he gene a o o
a g oup. The o de o an elemen x∈Fp, deno ed as |x|,is he
numbe o unique elemen s ha xcan gene a e aised o he
elemen s o he g oup 1, 2, 3, ..., p−1. The elemen s ha gene a e
all p−1elemen s o he g oup a e called gene a o s o p imi i e oo s,
and he g oups gene a ed by a gene a o a e called cyclic g oups.
The o de o gene a o s is always equal o p−1.I anelemen
g∈Fpis a gene a o , hen gk= 1∀k= p−1.
2.2. Roo s o uni y
The ollowing poin s a e c ucial o g asping he mo i a ion
behind he FFT and he disc e e Fou ie ans o ma ion (DFT),
which we will demons a e o be he as es me hod in e ms o
ime o compu ing he sec e o SSS, unde speci ic condi ions.
A complex oo o uni y is a con olu ed numbe ωsuch ha
ωn=1. The e a e exac ly ncomplex n h oo s o uni y: ei2kπ
n·
k=0.1. ···n−1. Acco ding o he cancela ion lemma [11]we
ake ha o any in ege s n≥0, k≥0,andd≥0, ωdk
dn =ωk
n,
and ha o any e en in ege n≥0, ω
n
2
n=ω2=−1. Las ly,
acco ding o he hal ing lemma [11], i n≥0is e en, he squa es
o he ncomplex n h oo s o uni y a e he n/2complex n/2 h
oo s o uni y. The hal ing lemma is c ucial o he di ide-and-
conque echnique o con e ing be ween coe icien and poin -
alue ep esen a ions o polynomials, which we will analyze in
he polynomial in e pola ion sec ion, since i ensu es ha he
ecu si e subp oblems a e hal as la ge as he o iginal p oblem.
Howe e , conside ing ha we a e wo king on a ini e ield and no
on complex numbe s, he de ini ion o he oo s o uni y has a
small wis .Le pbe a p ime and Fpbe he ini e ield o pelemen s.
Le ωbe an elemen o Fp.Wesay ha ωis an n h oo o uni y i
ωn≡1(mod p)bu no ωm=1, o all 0<m<n. Reade s a e
e e ed o S ewa [12] o an in-dep h subjec analysis. Las ly, a
c i e ion o de e mine a oo o uni y is ha he ini e ield Fphas
a p imi i e n h oo o uni y i and only i ndi ides he o de o
Fp, which is p−1. P imi i e n h oo s o uni y can be a con enien
way o speci y elemen s o a g oup ha ha e o de n[13].
Downloaded om h ps://academic.oup.com/comjnl/ad ance-a icle/doi/10.1093/comjnl/bxae109/7900561 by gues on 02 Decembe 2024
In e pola ion echniques applied o SSS |3
2.3. Sec e sha ing
Sec e sha ing is now one o he undamen al elemen s o c yp-
og aphic p o ocols. Conside a g oup S=s1,s2,...,sno pa ies
called sha eholde s o nodes ha a e mu ually dis us ing o one
ano he and a cen alized ad e sa y wi h he abili y o con ol up
o pa ies, o en e e ed o as a deale o da a owne . Usually, he
designa ed deale D∈Pmay sha e a sec e sby p o iding each si
asha eσio he sec e s ia a sec e sha ing scheme.
On a high le el, a sec e sha ing scheme is secu e i any
unau ho ized subse o pa icipan s lea ns no hing abou he
message, while any au ho ized subse o pa icipan s can ully
econs uc he sec e , also known as accessibili y. SSS is pe ec ly
secu e, i.e. secu e in an in o ma ion- heo e ic sense, meaning ha
unau ho ized coali ions canno deduce any in o ma ion abou he
sec e .
Shami ’s sec e sha ing scheme. We decided o p esen SSS
unde he p elimina ies sec ion i s ly because i is one o he
mos well-known and esea ched sec e sha ing schemes, and
secondly o he eade s o ha e an in ui ion o which is he end
goal o his pape . Ou ollowing expe imen s a e en i ely based
on his scheme.
The SSS scheme is an algo i hm i s p oposed in 1979 by he
enowned Is aeli c yp og aphe Adi Shami [3]. Shami ’s ( ,n)-
h eshold scheme, whe e is he econs uc ing h eshold and n
is he size o he se S=s1,...,sno sha eholde s, uses Lag ange
in e pola ion. The co e componen s o SSS scheme consis o
wo key algo i hms: he Sha e algo i hm and he Recons uc ion
algo i hm.
The Sha e algo i hm akes as inpu a message m∈Fq,whe eq
is a p ime numbe . I selec s a polynomial p(x)=a0+a1x+···+
a −1x −1o deg ee deg(p(x)) = −1,whe ea0:=mand coe icien s
a1,...,a −1∈Fqa e chosen uni o mly a andom. I compu es
sha e σi∈Fq o sha eholde si∈Sas a poin on polynomial p(x),
i.e. σi:=(i,p(i)),whe eiis he ID o sha eholde si. I dis ibu es
sha e σi o sha eholde si h ough an in o ma ion- heo e ically
secu e channel, o i=1, ...,n.
The Recons uc algo i hm akes as inpu a se o sha es σ1,...,σ
held by a subse R∈So sha eholde s, and wi h su icien
sha es he in e pola ing polynomial p(x)is econs uc ed using
he Lag ange’s in e pola ion o mula and ou pu s message m∈Fq
as p(0)=m.
O he schemes o sha ing sec e s, such as Blakley’s [14]and
Migno e’s [15], may o e al e na i e secu i y assump ions, com-
plexi y, and pe o mance ade-o s. SSS was chosen o his anal-
ysis because i s ikes a balance be ween simplici y, e iciency,
secu i y, and e sa ili y, which has led o i s widesp ead adop-
ion and p e e ence ac oss a wide ange o applica ions. Due o
i s sole eliance on polynomial in e pola ion, SSS is ela i ely
s aigh o wa d o comp ehend and implemen . In addi ion, i
o e s in o ma ion- heo e ic secu i y, also known as pe ec secu-
i y, which means ha he scheme’s secu i y is based on ma he-
ma ical p inciples a he han compu a ional assump ions and
canno be imp o ed. This makes i excep ionally esis an o
a ious a acks, including hose u ilizing quan um compu e s. I
mus be no ed, howe e , ha he undamen al secu i y elies on
one’s us in he deale ’s hones y. I he deale is dishones , a
sha e e i ica ion mechanism [16] mus be used, which is beyond
he scope o his pape and will be he subjec o u u e esea ch.
The abili y o cus omize he h eshold is a c ucial componen o
SSS. As we ha e seen, he h eshold de e mines he numbe o
sha es necessa y o econs uc he sec e , allowing o lexibili y
in es ablishing he desi ed le el o secu i y and a ailabili y. SSS
can accommoda e any numbe o pa icipan s. In addi ion, SSS
is esis an o sha e loss and comp omise. I he h eshold is no
exceeded, he sec e canno be econs uc ed e en i some sha es
a e los o comp omised.Las ly, he p o ocol’s obus ness makes i
sui able o si ua ions whe e he in eg i y o sha es canno always
be gua an eed.
3. POLYNOMIAL INTERPOLATION
The p ima y ocus o his a icle is on he applica ion o
polynomial in e pola ion in SSS o e ini e ields, aiming o
demons a e ha , in speci ic scena ios, al e na i e in e pola ion
me hods migh o e be e pe o mance han he con en ional
Lag ange me hod. Following a concise o e iew o polynomial
in e pola ion and i s connec ion o polynomial e alua ion, we
analyze ou in e pola ion echniques. Ou explo a ion begins
wi h he s anda d Lag ange in e pola ion, which Shami also
ad oca ed in his scheme. Subsequen ly, we in oduce wo
op imiza ions o he s anda d me hod: he op imized Lag ange o
he cons an e m and he well-es ablished Ba ycen ic Lag ange
(BL) o mula. While elucida ing he Lag ange o ms, we sc u inize
he New on in e pola ion and delinea e i s ade-o s compa ed
wi h he Lag ange me hod. The concluding segmen o his
sec ion will cen e on he Fas Fou ie me hod, culmina ing in
a succinc assessmen o he ad an ages and limi a ions o each
echnique.
3.1. Two ways o polynomial ep esen a ion
Polynomial in e pola ion inds wide applica ion in app oxima ing
complex cu es, such as e alua ing igonome ic unc ions o he
na u al loga i hm. I s e icien compu a ion makes i a p e e ed
choice o sub-quad a ic mul iplica ion and squa ing ope a ions,
exempli ied by echniques like he Toom-Cook mul iplica ion [17]
and he Ka a suba mul iplica ion [18]. In Euclidean geome y, wo
poin s de e mine a line, h ee poin s a pa abola, and so o h.
Howe e , gi en he a ie y o app oaches a ailable, econs uc ing
a smoo h unc ion (x) om a se o collec ed sample alues
lacks a s aigh o wa d answe . A o hcoming analysis aims o
es ablish a ma hema ical language ha b idges he unde s anding
be ween he eade and he au ho s.
Polynomials a e commonly ep esen ed in wo o ms: (i)
coe icien - o m and (ii) poin - alue o m. Ne e heless, e e y
polynomial in coe icien o m has a unique coun e pa in
poin - alue o m and ice e sa. The coe icien ep esen a ion
o he n-deg ee polynomial p(x)is he ec o o coe icien s
p0,p1,...,pn. Con e sely, he poin - alue ep esen a ion o he
n-deg ee polynomial p(x)consis s o a se o npoin - alue pai s,
deno ed as {(x0,P(x0)),(x1,P(x1)),...,(xn,P(xn))},whe eallxia e
dis inc . Fo conciseness, le yi=P(xi). Consequen ly, he sha es
will be deno ed as {(x0,y0),(x1,y1),...,(xn,yn)}.
The p ocess o compu ing he poin - alue ep esen a ion o
a polynomial P(x), bounded by deg ee n, gi en i s coe icien
ep esen a ion p∈Rn,isknownase alua ion. By selec ing n
dis inc poin s x0,x1,...,xn−1, o each xi,whe ei=0, 1, ...,n−1,
P(xi)can be compu ed.The e alua ion o he alue o any a bi a y
polynomial P(x)o deg ee na a gi en poin xcan be achie ed in
(n) ime, u ilizing Ho ne ’s me hod [19]. This me hod employs
he ollowing o mula: P(x)=p0+x(p1+x(p2+ ··· + x(pn−2+
x(pn−1)) ···)). Con e sely, i one we e o compu e he poin - alue
ep esen a ion o a polynomial P(x)o deg ee n, i would equi e
(n2) ime. On he o he hand, he p ocess o compu ing he
coe icien ep esen a ion o a polynomial P(x),bounded by deg ee
n, gi en i s poin - alue ep esen a ion {(x0,y0),(x1,y1),...,(xn,yn)},
is e e ed o as in e pola ion.
Downloaded om h ps://academic.oup.com/comjnl/ad ance-a icle/doi/10.1093/comjnl/bxae109/7900561 by gues on 02 Decembe 2024
4|Voudou is e al.
3.2. Lag ange in e pola ion
Ou examina ion o in e pola ion me hods commences wi h he
classical Lag ange in e pola ion echnique [20], widely ega ded
as he mos p e alen and ex ensi ely u ilized me hod o
da a in e pola ion. This me hod, ini ially p oposed by Shami
in his seminal wo k, o ms he co ne s one o many in e po-
la ion p ocedu es. In he ollowing ex , we p o ide a concise
o e iew o i s unc ioning and subsequen ly in oduce wo
op imiza ions.
A he ou se , gi en a se o n+1poin s (x0,y0),(x1,y1),...,
(xn,yn), he in e pola ion p oblem, as desc ibed in Sec ion 3.1,
en ails de ining a unique polynomial P(x)o deg ee nsuch
ha yi=P(xi), o i=0, 1, ...,n. Fo he se o poin s
(x0,y0),(x1,y1),...,(xk,yk),whe exj= xm o all j= m, he
Lag ange basis o polynomials o deg ee ≤k o hose poin s
consis s o he basis polynomials 0(x),1(x),...,k(x), each o
deg ee k. These polynomials sa is y j(xm)=0i m= j,o j(xj)=1
i m=j. Each basis polynomial j(x)can be exp essed as
lj(x)=
0≤m≤k
x−xm
xj−xm
(1)
The Lag ange in e pola ing polynomial o hose poin s
h ough he co esponding alues y0,y1,...,ykis he linea
combina ion:
L(x)=
k
j=0
yjj(x)(2)
In his con ex , P(xi)=yi o all 0 ≤i≤ . Each basis polynomial
possesses a deg ee o k, hence he summa ion L(x)has a deg ee o
≤k, ensu ing in e pola ion o he da a as L(xm)=k
j=0yjj(xm)=
k
j=0yjδmj =ym. The polynomial P(x)sa is ying P(xi)=yi o all
0≤i≤ , as de i ed om he a o emen ioned exp ession L(x)=
k
j=0yjj(x), is indeed unique.
3.2.1. Op imiza ions o s anda d lag ange me hod
The p ima y objec i e o in e pola ion wi hin he con ex o SSS
is o asce ain he alue o P(0), ep esen ing he sec e alue. In
ou comp ehension o SSS, i is unnecessa y o in e pola e he
en i e polynomial up o he maximum deg ee, solely he cons an
e m necessi a es ex ac ion. Hence, by se ing he a iable x o
ze o, we in oduce ou ini ial op imiza ion, p imized Lag ange
(Op .L). Le e aging Lag ange polynomials, a simple op imiza ion
echnique (achie ed h ough subs i u ions and basic a i hme ic
ope a ions), can educe he numbe o mul iplica ions by nea ly
50%:
P(0)=n−1
i=0
−xin−1
i=0
yi
−xi(n−1
j=0,j=i(xi−xj)) .(3)
The p e iously men ioned op imiza ion lacks cla i y in he
exis ing li e a u e. While nume ous schemes employing SSS
e e ence he s anda d Lag ange in e pola ion me hod, p ac ical
implemen a ions equen ly di e ge, balancing secu i y wi h
speed. Hence, we con end ha p o iding de elope s o SSS-
based sec e -sha ing applica ions wi h access o and comp e-
hension o his op imiza ion echnique would be in aluable,
hus wa an ing i s inclusion in ou esea ch. Ne e heless,
subsequen sec ions will demons a e he exis ence o supe io
op imiza ions.
3.2.2. Ba ycen ic Lag ange o mula
Con inuing wi h he Lag ange op imiza ions, he subsequen
one is e med he BL o mula. He e, we will p o ide a concise
o e iew, adhe ing explici ly o he no a ion and de ini ions
ou lined in Be u e al.[21]. Commencing wi h he s anda d
Lag ange o mula, he nume a o o ljin Equa ion 1can be
exp essed as
(x)=(x−x0)x−x1···x−xn(4)
di ided by x−xj. By de ining he Ba ycen ic weigh s:
wj=1
k=i(xj−xk),j=0, ...,n,(5)
we can hus w i e ljas
j(x)=(x)wj
x−xj
.(6)
So, in he end, we de ine he polynomial P(x)as
P(x)=(x)
n
j=0
wj
x−xj
j.(7)
The undamen al con as be ween he cu en op imiza ion
and he s anda d Lag ange in e pola ion o mula lies in he
me hodology employed o cons uc ing he in e pola ion
polynomial. The BL o mula en ails exp essing he nume a o
o each Lag ange basis unc ion as he quo ien o he p oduc
o di e ences be ween he in e pola ion poin and all o he
poin s, and he di e ence be ween he in e pola ion poin and
he cu en poin . The de e mina ion o Ba ycen ic weigh s
is based on hese di e ences, as shown in Equa ion 5,which
a e subsequen ly u ilized o compu e he Lag ange basis
unc ions. E en ually, he polynomial is ob ained by mul iplying
he Lag ange basis unc ions wi h he unc ion alues a he
in e pola ion poin s while accoun ing o he Ba ycen ic weigh s.
Sec ion 4will show ha he BL me hod signi ican ly educes
in e pola ion imes.
3.3. New on in e pola ion
New on’s in e pola ion o mula p o ides an al e na i e app oach
o compu e P(x), gi en a se o n+1 da a poin s (x0,y0),(x1,y1),...,
(xn,yn),whe e hexia e dis inc . The ini ial s ep o his me hod
in ol es compu ing New on’s able o di ided di e ences. This
able cons i u es a iangula a ay o numbe s de ined by he
ecu si e o mula:
[xi,xi+1,...,xi+k]= [xi+1,xi+2, ..., xi+k]− [xi,xi+1, ..., xi+k−1]
xi+k−xi
(8)
Downloaded om h ps://academic.oup.com/comjnl/ad ance-a icle/doi/10.1093/comjnl/bxae109/7900561 by gues on 02 Decembe 2024
In e pola ion echniques applied o SSS |5
wi h ini ial condi ions [xi]= (xi). The able has he ollowing
o m:
x0 [x0]
x1 [x1] [x0,x1]
x2 [x2] [x1,x2] [x0,x1,x2]
.
.
..
.
..
.
..
.
.
xn [xn] [xn−1,xn] [xn−2,xn−1,xn]... [x0,x1,...,xn]
Once he able is compu ed, he subsequen s ep in ol es
e alua ing P(x)using he ollowing New on in e pola ion o mula:
n
k=1 [x0,x1,...,xk](x−x0)···(x−xk−1), whe e he coe icien s
[x0,x1,...,xk] a e he en ies in he able. This o mula can be
in e p e ed as a weigh ed sum o e ms (x−x0)···(x−xk−1),
whe e each e m is weigh ed by he co esponding coe icien
[x0,x1,...,xk].
I should be emphasized ha when he in e pola ion poin s
x0,...,xna e dis inc , inding a polynomial passing h ough he
poin s (xi,yi)is equi alen o sol ing a sys em o linea equa ions
Ax=b ha has a unique solu ion. The ma ix Ais de e mined
by he choice o basis o he space o polynomials o deg ee n
o less. In New on in e pola ion, he basis unc ions a e he se
Nj(x)n
j=0de ined ecu si ely as N0(x)=1, and o j=1, ...,n:
Nj(x)=j−1
k=0(x−xk). These basis unc ions a e s uc u ed such
ha Nj(x)is a polynomial o deg ee j,andNj(xk)=0 o k=
0, ...,j−1. Consequen ly, any polynomial o deg ee a mos ncan
be exp essed as a linea combina ion o hese basis unc ions, i.e.
Pn(x)=a0N0(x)+a1N1(x)+···+anNn(x).
Upda ing he in e pola ing polynomial becomes s aigh o -
wa d as in e pola ion poin s a e added because he basis unc-
ions {Nj(x)},j=0, ...,n, emain unchanged. New in e pola ion
poin s can be added o upda e he in e pola ing polynomial
using New on’s me hod, and hen he di ided di e ences able
is upda ed acco dingly. Fo ins ance, suppose we ha e a se o
n+1dis inc poin s xi,yi, and we ha e compu ed he di ided
di e ences able o hese poin s. I we wish o add a new poin
(xn+1,yn+1), we upda e he di ided di e ences able by adding
a new column o he igh . The i s en y in his new column
will be he di ided di e ence o he new poin , which is simply
he unc ion alue yn+1. Subsequen en ies in he column can be
ecu si ely compu ed using di ided di e ences om he p e ious
column. Speci ically, he (k+1) h en y in he new column is
de e mined as ollows: [xn+1,x0,···,xk]= [xn+1,x1,...,xk]− [xn,x0,...,xk−1]
xn+1−xn.
He e, [xn+1,x1,...,xk] ep esen s he di ided di e ence compu ed
in he p e ious column, while [xn,x0,...,xk−1] deno es he
di ided di e ence om he same ow bu in he p eceding
column.
Once he di ided di e ences able is upda ed, he upda ed
in e pola ing polynomial can be compu ed using he same o -
mula as be o e Pn(x)=n
k=0 [x0,···,xk]Nk(x),whe eNk(x)signi ies
he k h New on basis unc ion.
3.4. Fou ie in e pola ion
As demons a ed ea lie , polynomials can be de ined o e a ield
deno ed as F. Howe e , in he con ex o c yp og aphy, we ha e
chosen o de ine hem speci ically on GF(p),whe epis a p ime.
The Fou ie ans o m is ypically de ined on he in ini e se C,
which is he ield o complex numbe s. Fo he in ended scope o
ou esea ch, i is necessa y o es ablish i s de ini ion on GF(p)
as well. Subsequen ly, wi hin his sec ion, we will examine he
me hodology o achie ing his objec i e h ough he u iliza ion
o he oo s o uni y on ini e ields. This esea ch in ol es he
u iliza ion o he FFT o al e he ep esen a ion o a polynomial
P(x), which has a deg ee ¡nand consis s o coe icien s belonging
o he ield GF(p), om a coe icien s-based ep esen a ion o
an e alua ion-based ep esen a ion (and ice e sa). The e al-
ua ion is conduc ed exclusi ely o e ndis inc ield elemen s,
which a e he n h oo s o uni y. As a esul , su icien knowl-
edge o he p elimina ies ha we e desc ibed a he beginning is
equi ed.
We analyze he DFT, he FFT, and las ly he in e ses o bo h,
which will lead us o he in e pola ion.
DFT o e ini e ields. Conside a polynomial P(x)o deg ee n
exp essed in coe icien o m, deno ed as p∈Fn,whe epis a
column ec o gi en by p=[p0p1...pn−1]T. We aim o ep esen P(x)
in i s poin - alue o m by compu ing i s alues a he ndis inc
n h oo s o uni y, namely ω0
n,ω1
n,...,ωn−1
n.Le yjdeno e P(ωj
n) o
j anging om 0 o n−1.Then h o de DFT is a ma hema ical
ope a ion ha akes he coe icien s o a polynomial Po deg ee
n−1as inpu . I s ou pu is an n-dimensional ec o , whe e
each componen ep esen s he e alua ion o Pa one o he
n h oo s o uni y. Con en ionally, we deno e his ope a ion as
y=DFTn(p),whe epsigni ies he polynomial o deg ee n−
1. A isual depic ion o his p oblem can be seen as a ma ix
mul iplica ion:
⎛
⎜
⎜
⎜
⎜
⎝
y0
y1
.
.
.
yn−1
⎞
⎟
⎟
⎟
⎟
⎠
=⎡
⎢
⎢
⎢
⎢
⎣
1x0x2
0··· xn−1
0
1x1x2
1··· xn−1
1
.
.
..
.
..
.
.....
.
.
1xn−1x2
n−1··· xn−1
n−1
⎤
⎥
⎥
⎥
⎥
⎦
·⎛
⎜
⎜
⎜
⎜
⎝
a0
a1
.
.
.
an−1
⎞
⎟
⎟
⎟
⎟
⎠
(9)
Wha he DFT essen ially p o ides is a ans o ma ion:
⎛
⎜
⎜
⎜
⎜
⎝
F0
F1
.
.
.
Fn−1
⎞
⎟
⎟
⎟
⎟
⎠
=⎡
⎢
⎢
⎢
⎢
⎣
11 1 ··· 1
1ωω
2··· ωn−1
.
.
..
.
..
.
.....
.
.
1ωn−1ω2(n−1)··· ω(n−1)2
⎤
⎥
⎥
⎥
⎥
⎦
·⎛
⎜
⎜
⎜
⎜
⎝
a0
a1
.
.
.
an−1
⎞
⎟
⎟
⎟
⎟
⎠
(10)
In he ans o med ela ion, obse e ha xico esponds o ωi.
We designa e he Vande monde ma ix o 1, ω,ω2,...,ωn−1as he
DFT ma ix. Al e na i ely, we can exp ess his algeb aically as
Fk=
n−1
i=0
aiωki (11)
A e ea anging, we de i e he in e se disc e e Fou ie
ans o ma ion (IDFT) o mula, designed o ecompu e he
coe icien s ai.
ai=1
n
n−1
k=0
Fkω−ik (12)
Downloaded om h ps://academic.oup.com/comjnl/ad ance-a icle/doi/10.1093/comjnl/bxae109/7900561 by gues on 02 Decembe 2024
6|Voudou is e al.
This o mula a ises om he symme ic p ope ies inhe en in
he p imi i e n h oo s o uni y. Simila ly, he IDFT can also be
exp essed h ough ma ix mul iplica ion.
⎛
⎜
⎜
⎜
⎜
⎝
a0
a1
.
.
.
an−1
⎞
⎟
⎟
⎟
⎟
⎠
=1
n
⎡
⎢
⎢
⎢
⎢
⎣
11 1 ··· 1
1ω−1ω−2··· ω−(n−1)
.
.
..
.
..
.
.....
.
.
1ω−(n−1)ω−2(n−1)··· ω−(n−1)2
⎤
⎥
⎥
⎥
⎥
⎦
·⎛
⎜
⎜
⎜
⎜
⎝
F0
F1
.
.
.
Fn−1
⎞
⎟
⎟
⎟
⎟
⎠
(13)
In line wi h he DFT ma ix, we deno e he ma ix con aining
he in e se powe s o ωas he IDFT ma ix.
3.5. Fas Fou ie ans o m o e ini e ields
We know ha Ho ne ’s algo i hm [22] acili a es he compu a ion
o DFTnin (n2)s eps. Howe e , when dealing wi h signi ican ly
la ge alues o n(e.g. hund eds o housands o millions), execu -
ing DFTnmay demand excessi e ime. An al e na i e algo i hm
o compu ing he DFT o size nin (nlog n)ope a ions, known
as he FFT, add esses his challenge. This app oach le e ages he
symme ic p ope ies o he n h oo s o uni y and is oo ed in
he echnique in oduced by Cooley and Tukey [23]. We adhe e
explici ly o he ma hema ical no a ions and de ini ions ou lined
by Fa eman [24], as hey o e a mo e algeb aic pe spec i e and
a e u ilized in ou implemen a ions.
Fas Fou ie ans o m. The FFT algo i hm le e ages he
symme y and pe iodici y p ope ies inhe en in oo s o uni y
o compu e he Fou ie ans o m mo e e icien ly. By employing
he Cooley and Tukey algo i hm [23], he complexi y is educed
om O(n2) o O(nlog n)ope a ions. The undamen al concep
in ol es b eaking down he ini ial DFT p oblem in o smalle
DFT p oblems o hal he size, employing a ecu si e di ide-
and-conque app oach. This cha ac e is ic makes he FFT
pa icula ly aluable o handling la ge da ase s and eal- ime
applica ions. Fo demons a ion pu poses and o showcase
he algo i hm’s op imal pe o mance, we op o he numbe
o sha es n o be a powe o 2, i.e. n=2k. While he same
me hodology can be ex ended o o he alues o n,suchas
n=pko n=p1p2p3...pk, hese choices may no unde sco e
he signi ican ad an age o he Cooley and Tukey algo i hm as
e ec i ely.
Conside he polynomial Pde ined as P(x)=n−1
i=0aixi.We
can pa i ion Pin o wo polynomials: one comp ising he e en-
indexed coe icien s o P, deno ed as P0, and ano he consis ing o
he odd-indexed coe icien s, deno ed as P1.
P(x)=(a0+a2x2+... an−2xn−2)
P0
+(a1x+a3x3+... +an−1xn−1)
P1
(14)
P(x)=
n
2−1
i=0
a2ix2i
P0
+
n
2−1
i=0
a2i+1x2i+1
P1
(15)
P(x)=
n
2−1
i=0
a2i(x2)i
P0
+x
n
2−1
i=0
a2i+1(x2)i
P1
(16)
No ice ha he i s e m in he summa ion ep esen s he
e alua ion o he (n/2)-deg ee polynomial P0a x2,while he
second e m ep esen s he e alua ion o he (n/2)-deg ee poly-
nomial P1a x2. Consequen ly, we can exp ess Pas
P(x)=P0(x2)+xP1(x2)(17)
We i e a e his p ocedu e o each o P0and P1un il he size
o he FFT educes o 1 and can no longe be spli u he . By
ecu si ely e alua ing he smalle sized FFTs and subs i u ing
hese e alua ions in o he polynomial o he highe laye , we
e en ually de i e he sha es o he o iginal polynomial.
The in e se Fou ie ans o m is he p oblem o de e mining
he le -hand side coe icien ec o o he ollowing ela ion:
⎛
⎜
⎜
⎜
⎜
⎝
a0
a1
.
.
.
an−1
⎞
⎟
⎟
⎟
⎟
⎠
=1
n
⎡
⎢
⎢
⎢
⎢
⎣
11 1 ··· 1
1ω−1ω−2··· ω−(n−1)
.
.
..
.
..
.
.....
.
.
1ω−(n−1)ω−2(n−1)··· ω−(n−1)2
⎤
⎥
⎥
⎥
⎥
⎦
·⎛
⎜
⎜
⎜
⎜
⎝
F0
F1
.
.
.
Fn−1
⎞
⎟
⎟
⎟
⎟
⎠
(18)
The algo i hm esembles he s anda d Fou ie T ans o m, bu
in his case, he equi ed ma ix comp ises nega i e powe s o ω.
Thus, he objec i e is o apply he FFT as desc ibed abo e, bu his
ime e alua ing a nega i e powe s. As a inal s ep, he in e se
Fou ie ans o m di ides he inne p oduc o each mul iplied
ec o by n o ob ain he coe icien s.
Sec ion 4p esen s ou es bed en i onmen and he a ionale
behind selec ing he espec i e pa ame e s.
4. EVALUATION
A e es ablishing he essen ial ma hema ical g oundwo k and
conduc ing a ho ough analysis o each in e pola ion me hod,
his sec ion encapsula es he culmina ion o ou expe imen s.
The expe imen al esul s demons a e how a ious pa ame e s
in luence he e iciency and pe o mance o each in e pola-
ion me hod. This con ibu ion is mo i a ed by he lack o
ela ed wo k on his opic, pa icula ly when combined wi h
sec e sha ing. To unde sco e he easibili y and p ac icali y
o ou app oach, we implemen ed a p o o ype using Py hon
3.11.18 and SageMa h 10.3 [9] on a MacBook unning macOS
Sonoma 14.4.
4.1. Domain pa ame e s con igu a ion
Conside ing ha ou in e pola ion echniques will be employed
o SSS ac oss ini e ields, de ining he ini e ield wi hin he
speci ied domain we will be wo king wi h is c ucial. The domain
pa ame e s encompass a se o p ede ined cha ac e is ics ha
hold uni e sal applicabili y and will be consis en ly u ilized
ac oss all expe imen al p ocedu es. These pa ame e s a e
in luenced by he cons ain s o he FFT in he ollowing
manne .
The ini ial s ep in ol es cons uc ing he ini e ield Fp. Since
he FFT does no unc ion wi h a andomly chosen p,wemus
manually cons uc i . To compu e he p imi i e n h oo s o uni y,
he di ision p−1
nmus yield an in ege , indica ing ha ndi ides
p−1.Weop o p o be a sa e p ime ollowing he o ma p=
nmaxq+1,whe eq ep esen s a andom 28-bi p ime numbe . He e,
we se nmax o 2100 as an uppe bound since, in ou speci ic use
Downloaded om h ps://academic.oup.com/comjnl/ad ance-a icle/doi/10.1093/comjnl/bxae109/7900561 by gues on 02 Decembe 2024
In e pola ion echniques applied o SSS |7
Table 1. Pe o mance o unop imized New on, Ba ycen ic, and FFT.
Me hods 128 256 512 1024 2048 4096 8192
New on 0.05 0.12 0.6445 1.9967 8.8905 31.8654 320.3828
Ba ycen ic 0.1483 0.3906 0.9381 2.998 12.5994 38.0322 114.7491
FFT 0.0025 0.0081 0.0112 0.0344 0.1144 0.1393 0.2699
cases, nwill ne e each such magni udes. Hence, he alue o p
is de e mined as
p=2100 ∗135783853 +1
=172126482756751667503106328023403593729 (19)
Thesizeo pis a bi a y as i does no a ec he pe o mance o
he in e pola ion me hods.
Ano he impo an domain pa ame e c ucial mos ly o FFT is
he g oup gene a o g. We can ind gusing any classical me hod
o de e mining gene a o s, bu o simplici y, as s a ed by Lynn
e al.[
25], we le g=3.
Fo each speci ic scena io, a 128-bi AES key will be consis en ly
designa ed as he cons an e m o he polynomial and ea ed
as he sec e alue s. The selec ion o a 128-bi key aligns wi h
he leng h o he p ime numbe p(Equa ion (19)). While he
algo i hm could suppo longe keys, such as hose wi h 256 o 512
bi s, main aining equi alen secu i y necessi a es p opo ionally
inc easing he leng h o he p ime numbe . De ia ing om his
balance by selec ing a sho e p ime numbe o ex ending he key
leng h beyond wha is p opo ional comp omises secu i y. Sho e
p imes isk insecu i y due o modula a i hme ic p ope ies and
loss o in o ma ion, while longe keys necessi a e padding. The
objec i e is o dis ibu e his con iden ial in o ma ion among
pa icipan s o he sec e -sha ing p o ocol o secu ely each a
consensus on he same key.
4.2. A compa a i e analysis o di e en
in e pola ion me hods
Rega ding ou ini ial expe imen , ce ain adjus men s a e neces-
sa y o accommoda e he cons ain s o he FFT algo i hm.
1. The numbe o sha es nshould be a powe o 2. Speci ically,
we se nmin =27and nmax =213 as hese selec ions e ec i ely
highligh pe o mance di e ences.
2. Main aining consis ency in he alue o he p imi i e oo ,
ω, ac oss a ious nnecessi a es mino adjus men s, which
a e no aligned wi h ou objec i es. While p ecompu ing he
oo s o uni y could po en ially esol e his issue, ou cu en
app oach u ilizes unop imized e sions o each algo i hm.
3. Due o he conside a ions abo e, i is impe a i e ha he
deg ee o he in e pola ing polynomial emains n−1 o all
alues o n.
Consequen ly, i is no possible o de e mine a ixed in e po-
la ing polynomial, necessi a ing he gene a ion o an a bi a y
polynomial o deg ee (n−1) o each alue o n.
We will now analyze he esul s ob ained om he unop imized
implemen a ions o he New on, Ba ycen ic, and FFT algo i hms.
Each cell wi hin he Table 1 deno es he du a ion, measu ed in
seconds, equi ed o comple e he in e pola ion p ocess. I is
wo h no ing ha , based on he FFT algo i hm’s compu a ional
complexi y o O(nlog2n), i s pe o mance ou pe o ms by a all
he o he in e pola ion me hods.
Figu e 1. In e pola ion imes o unop imized New on, ba ycen ic, and
FFT diag am.
Table 2. Pe o mance o unop imized nai e Lag ange.
Numbe o use s In e pola ion ime (s)
100 0.5433
200 3.1385
300 6.5299
400 16.1861
500 25.2504
600 49.3655
700 64.2438
800 80.3796
900 107.0505
1000 152.7803
We no ice ha o alues o nup o 4096, bo h New on
and Ba ycen ic me hods demons a e nea ly compa able
pe o mance. Howe e , New on’s ime complexi y unde goes
a no able and apid inc ease beyond his h eshold. The
dispa i y be ween he compu a ional complexi ies o O(nlog2(n))
and O(n2)becomes e iden in Fig. 1, as demons a ed by
he loga i hmic na u e o he FFT g aph, which con e ges
owa d a cons an O(1)wi h an in ini esimally small a e o
change.
In he second segmen o ou ini ial expe imen (i.e. he s an-
da d Lag ange me hod), we se he lowe bound nmin o 100 and
he uppe bound nmax o 1000, inc emen ing he alue o nby 100
in each successi e i e a ion. Due o he absence o cons ain s
associa ed wi h he FFT, i becomes easible o es ablish a de e -
minis ic solu ion o a andomly selec ed polynomial o deg ee
i e. The ou comes a e depic ed in Table 2.
I is e iden ha o n=1000, he Lag ange algo i hm neces-
si a es ∼2 min o comple e, as depic ed in Fig. 2. Nai e Lag ange
in e pola ion ime inc eases quickly e en wi h a small numbe
o sha es (n=1000), as an icipa ed due o i s quad a ic ime
complexi y O(n2).
Downloaded om h ps://academic.oup.com/comjnl/ad ance-a icle/doi/10.1093/comjnl/bxae109/7900561 by gues on 02 Decembe 2024
8|Voudou is e al.
Table 3. Pe o mance o New on and Ba ycen ic wi hou p ecompu ed alues.
Me hods 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010
New on 8.5294 9.376 8.7036 9.3542 9.3054 9.5331 8.9018 8.8316 10.1682 9.0897 8.8205
Ba ycen ic 5.6065 5.5197 5.7283 5.6771 5.6474 5.6487 5.7032 5.5013 5.6746 5.7882 5.524
Figu e 2. S anda d Lag ange me hod o inc easing numbe o membe s.
4.3. Enhancing New on and ba ycen ic me hods
wi h new sha es
This expe imen aims o explo e an applica ion employing
sec e sha ing o key exchange. Bo h he enhanced New on and
Ba ycen ic me hods u ilize p ecompu ed di ided di e ences and
weigh s. These p ecompu ed alues a e eused o each new use
added o he sys em, elimina ing he need o ecalcula ions om
sc a ch.
To illus a e his concep , we se he a iable ep esen ing he
numbe o sha es o n=5000. The p ecompu ed alues a e s o ed
and g adually expanded wi h each new sha e un il he alue o n
eaches 5010. Le us i s examine he scena io whe e no alues
ha e been p ecompu ed. Table 3 exhibi s he esul s ob ained
om he New on and Ba ycen ic me hods when he p ecom-
pu a ion o di ided di e ences and weigh s is no conduc ed. I
is c ucial o no e ha he u ilized e sions o hese app oaches
a e op imized, ocusing solely on eco e ing he cons an e m a0
a he han he en i e polynomial. Each cell deno es he du a ion
in seconds equi ed o comple e he in e pola ion p ocess. The
ad an age o Ba ycen ic o e New on is e iden om he e y
beginning wi h he n=5000 sha es. The numbe o sha es is
selec ed a bi a ily and is in en ionally se o a la ge alue o
ep esen a eal-li e scena io. This is in con as o he n=1000
used in he nai e Lag ange me hod, which is no sui able o high
alues o nand has no impac on he esul . Mo eo e , he ime
ad an age pe sis s e en when inco po a ing addi ional sha es.
Bezza ee e al.[
6] p oposed ha using New on in e pola ion
o adding a single new sha e in he mul i ac o au hen ica ion
se ing is bene icial, compa ed wi h nai e Lag ange. While his
is co ec , we bols e his assump ion by demons a ing ha he
Ba ycen ic echnique is mo e ad an ageous, e en o a la ge
numbe o new sha es. In he subsequen expe imen s, we show-
case ha he FFT ou pe o ms all me hods wi h he co ec se up.
Now, le us examine he ou comes o he New on and Ba ycen-
ic me hods when u ilizing p ecompu ed alues wi h he same
numbe o sha es. Table 4 highligh s he signi ican di e ence in
ime complexi y when di ided di e ences and weigh s a e p e-
compu ed. Fo he ini ial alue n=5000, he ime in he i s col-
umn is nea ly iden ical o Table 3, as he expe imen is epea ed
o es ablish he ini ial di ided di e ences and weigh s. Howe e ,
subsequen in e pola ions wi h n+1sha es show no able changes
in in e pola ion ime. This is because in e pola ions wi h n+1
sha es u ilize he p ecompu ed ndi ided di e ences and weigh
alues, while in e pola ions wi h n+2sha es u ilize he p e-
compu ed n+1 alues, and so o h. Bo h me hods demons a e
subs an ial imp o emen s in in e pola ion imes compa ed wi h
Table 3, wi h he Ba ycen ic me hod s ill main aining a compu-
a ional ad an age o e New on.
I can be concluded ha i espec i e o he applica ion,
employing Ba ycen ic in e pola ion is mo e ad an ageous o
a sec e -sha ing applica ion expe iencing a p og essi e inc ease
in he numbe o use s.
4.4. Compa ison o all op imized in e pola ion
me hods
In ou inal expe imen , we compa e all he a o emen ioned
in e pola ion me hods. I should be no ed ha he es ic ions o
he FFT me hod a e conside ed, such as he equi emen o he
numbe o sha es n o be a powe o 2. All app oaches a e op i-
mized by p ecompu ing alues o di ided di e ences in New on’s
me hod, weigh s in BL’s me hod, and oo s o uni y in he FFT
me hod. This expe imen aims o de e mine he mos e ec i e
in e pola ion me hod o s anda d SSS based only on pe o mance
me ics such as in e pola ion ime and sha ed sec e e ie al a0
among nuse s. Table 5 p esen s in e pola ion imes in seconds o
a ying numbe s o sha es. I is wo h no ing ha he FFT me hod
does no e en su pass 1 s o n=16 384 sha es.
Fu he mo e, Fig. 3 illus a es all op imal a ia ions o he
me hodologies. Compu a ional bounds a e se a nmin =27and
nmax =213. The FFT app oach demons a es almos a s aigh
line on he x−yplane due o i s ime complexi y o O(nlog2(n)),
which is signi ican ly lowe han he O(n2)complexi y o o he
me hods, excep Ba ycen ic, which has an O(n) e ie al ime
wi h p ecompu ed weigh s.
5. DISCUSSION
Th ough an examina ion o he esea ch ques ions, we conduc ed
an in-dep h in es iga ion in o he p ac icali ies and ela i e
e iciencies o di e en polynomial in e pola ion echniques as
hey apply o sec e -sha ing schemes and mo e ex ensi e eal-
wo ld implemen a ions. This esea ch has been ho ough, encom-
passing bo h heo e ical amewo ks and empi ical alida ions
h ough ca e ully designed expe imen s. Ou jou ney h ough
his analy ical p ocess illumina ed he dis inc capabili ies, limi-
a ions, and si ua ional ad an ages o he FFT, he BL o mula, and
New on’s in e pola ion me hod. E e y echnique was e alua ed
in e ms o i s compu a ional complexi y, p ac icabili y in ini e
ields, and ease o implemen a ion in dynamic en i onmen s.
Ou main objec i e while analyzing hese me hodologies was
Downloaded om h ps://academic.oup.com/comjnl/ad ance-a icle/doi/10.1093/comjnl/bxae109/7900561 by gues on 02 Decembe 2024
In e pola ion echniques applied o SSS |9
Table 4. Pe o mance o New on and Ba ycen ic wi h p ecompu ed alues.
Me hods 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010
New on 8.557 0.0085 0.0086 0.0087 0.3562 0.0082 0.008 0.0083 0.008 0.0083 0.0083
Ba ycen ic 5.7163 0.0091 0.0092 0.0088 0.0086 0.0092 0.009 0.009 0.0095 0.0093 0.0098
Table 5. Pe o mance o FFT and op imized s anda d Lag ange, New on, and Ba ycen ic.
Me hods 128 256 512 1024 2048 4096 8192
S anda d Lag ange 0.0112 0.0465 0.1719 0.6817 2.7803 10.9333 43.7564
New on 0.0322 0.0194 0.1042 0.4909 1.6527 6.1578 27.8844
Ba ycen ic 0.004 0.0157 0.0615 0.246 0.9626 3.7881 15.1438
FFT 0.001 0.0019 0.0044 0.0092 0.019 0.0405 0.0864
Figu e 3. Op imized me hods pe o mance.
o unequi ocally espond o he esea ch ques ions ha we e
in oduced a he beginning o his pape . Ha ing eached he
inal phase o ou in es iga ion, equipped wi h a comp ehensi e
body o e idence and insigh s de i ed om ou igo ous analysis,
we con iden ly conclude and espond o he ini ial esea ch
ques ions. This se es as conc e e p oo o ou dedica ion o
expanding he knowledge o he esea ch communi y in o
applying polynomial in e pola ion me hods in o p ac ical, la ge-
scale applica ions, in addi ion o being an endo semen o he
dep h o ou in es iga ion.
RQ1:Wha is he swi es me hod and mos sui able in la ge-scale
scena ios o in e pola e he polynomial in he con ex o SSS o
eco e he sec e om he cons an e m?
The FFT eme ges as he p emie choice o polynomial e al-
ua ion and in e pola ion in SSS scheme, due o i s unpa alleled
compu a ional e iciency and apid execu ion imes, pa icula ly
when handling la ge da ase s. Shami ’s scheme elies on con-
s uc ing a polynomial o deg ee k−1 o a k- h eshold scheme,
whe e he sec e is embedded in he cons an e m. Fo econ-
s uc ion, adi ionally, Lag ange in e pola ion is used, which has
a compu a ional complexi y o O(n2) o nsha es. In con as , FFT
can pe o m he necessa y polynomial e alua ions o in e pola-
ions in O(nlog n) ime. This e iciency is la gely due o he FFT’s
abili y o pe o m polynomial ope a ions in O(nlogn) ime, le e -
aging di ide-and-conque s a egies [23] and he disc e e Fou ie
ans o m’s symme y p ope ies. Such a signi ican educ ion
in compu a ional complexi y posi ions he FFT as excep ion-
ally ad an ageous o sec e econs uc ion wi hin la ge-scale
ope a ions. None heless, he FFT equi es he numbe o pa -
icipan s and he polynomial’s deg ee o adhe e o powe s o
2, a cons ain ha can be ci cum en ed h ough algo i hmic
enhancemen s designed o b oaden i s applicabili y [26].
On he o he hand, he Lag ange in e pola ion me hod and i s
e olu ion h ough he BL o mula o e a di e en se o ad an-
ages and limi a ions. While he Lag ange me hod is enowned
o i s e sa ili y, i aces p ac ical di icul ies in dynamically
changing scena ios, such as he addi ion o new pa icipan s
o a sha ing scheme. This limi a ion a ises om he need o
ecalcula e Lag ange polynomials om sc a ch wi h each new
addi ion, ende ing he p ocess cumbe some in apidly e ol ing
se ings.
The BL o mula, in con as , add esses some o he p ac ical
challenges inhe en in he s anda d Lag ange app oach by elimi-
na ing he need o comple e polynomial ecalcula ions o e e y
new in e pola ion poin . This e inemen signi ican ly enhances
e iciency, pa icula ly in la ge da ase s, by educing he o e all
compu a ional demand o O(n) o e alua ing in e pola ing poly-
nomials once Ba ycen ic weigh s a e compu ed. The p ima y
challenge o BL me hod lies in managing small da ase s whe e
he o e head o compu ing Ba ycen ic weigh s may ou weigh i s
compu a ional bene i s.
Fu he mo e, New on’s in e pola ion me hod, while sha ing
ounda ional simila i ies wi h he Lag ange app oach in e ms o
employing a speci ic se o basis unc ions, dis inguishes i sel
h ough he u iliza ion o di ided di e ence polynomials. This
me hod o e s ad an ages in compu a ional e iciency o i e a-
i e polynomial e alua ions, albei a he cos o inc eased mem-
o y complexi y due o he s o age equi emen s o he di ided
di e ence able. Despi e hese ad an ages, New on’s me hod is
no he p ima y choice compa ed wi h he FFT and BL me hods,
especially when quick in e pola ion o polynomials a new poin s
is equi ed.
In del ing deepe in o he compa a i e analysis o hese me h-
ods, i becomes e iden ha he FFT s ands ou o i s obus
applicabili y and supe io e iciency in la ge-scale sec e -sha ing
schemes, assuming i s speci ic cons ain s a e e ec i ely man-
aged.The BL o mula, wi h i s ocus on o e coming he limi a ions
o he Lag ange me hod in dynamic and la ge da ase s, p o ides
a complemen a y app oach ha excels unde ce ain condi ions,
pa icula ly in en i onmen s no es ic ed by he size o he
da ase . Consequen ly, when assessing he mos sui able in e -
pola ion me hod o la ge-scale scena ios, he FFT unequi ocally
o e s he mos p omising solu ion, subjec o u he e ine-
men s and adap a ions o ex end i s u ili y beyond he con ines o
Downloaded om h ps://academic.oup.com/comjnl/ad ance-a icle/doi/10.1093/comjnl/bxae109/7900561 by gues on 02 Decembe 2024
