USENIX Secu i y ’25 A i ac Appendix:
OBLIVIATOR:OBLIVIous Pa allel Joins and o he Ope ATORs
in Sha ed Memo y En i onmen s
Apos olos Ma ogiannakis*
UCSC
Xian Wang*
HKUST
Ioannis Deme zis
UCSC
Dimi ios Papadopoulos
HKUST
Minos Ga o alakis
ATHENA Resea ch Cen e &
Technical Uni e si y o C e e
A A i ac Appendix
A.1 Abs ac
We in oduce obli ious pa allel ope a o s designed o bo h
non- o eign key and o eign key equi-joins. Obli iousness
ensu es no hing is e ealed abou he da a besides inpu /ou -
pu sizes, e en agains a s ong ad e sa y ha can obse e
memo y access pa e ns. Ou solu ion achie es his by com-
bining us ed ha dwa e wi h e icien obli ious p imi i es o
compac ion and so ing, and wo obli ious algo i hms: (i) an
obli ious agg ega ion ee, which can be desc ibed as a a ia-
ion o he pa allel p e ix sum, cus omized o us ed ha d-
wa e, and (ii) a no el algo i hm o obli iously expanding he
elemen s o a ela ion. We hen implemen ed ou non- o eign
key join and o eign key join wi h he wo new algo i hms.
In he sequen ial se ing, ou obli ious join pe o ms
4.6×
-
5.14×
as e han he p io s a e-o - he-a solu ion (K as -
niko e al., VLDB 2020) on da a se s o size
n=224
. In he
pa allel se ing, ou algo i hm achie es a speedup o up o
oughly
16×
o e he sequen ial e sion, when unning wi h
32 h eads (becoming up o
80×
compa ed o he sequen ial
algo i hm o K as niko e al.). Finally, ou obli ious ope -
a o s can be used independen ly o suppo o he obli ious
ela ional da abase que ies, such as obli ious selec ion and
obli ious g oup-by, which a e implemen ed and e alua ed
wi h complex da abase que ies.
A.2 Desc ip ion & Requi emen s
A.2.1 Secu i y, p i acy, and e hical conce ns
The e is no malicious o des uc i e ope a ions in he a i ac .
We p opose algo i hms and implemen sys ems wi h a posi i e
impac on p ese ing da a p i acy. The a i ac does no han-
dle any sensi i e da a o pe sonal in o ma ion. All ou es s
1
The wo i s au ho s con ibu ed equally o his wo k and hei names
a e lis ed he e alphabe ically.
we e execu ed ei he on syn he ic da ase s o on publicly a ail-
able eal-wo ld da ase s. The e hical implica ions ha e also
been ca e ully conside ed and ou wo k is in ull acco dance
wi h he 2025 USENIX Secu i y e hics guidelines.
A.2.2 How o access
We open-sou ce all code, da ase s and sc ip s necessa y o
he e alua ion o Obli ia o and hey can be accessed a [2].
A.2.3 Ha dwa e dependencies
To e alua e he unc ionali y o ou a i ac , we equi e a
machine wi h an In el p ocesso and a leas 9GB memo y.
A.2.4 So wa e dependencies
Ou implemen a ions a e o Linux OS. The a i ac equi es
gcc-7 and g++-7. Fo all o he so wa e dependencies, e.g.,
he Open Encla e SDK [3], In el SGX SDK [1], we p o ide
sc ip s (./sc ip s/ae-ins all-dependencies.sh) o ins all hem.
In he sc ip , he de ailed package e sions a e chosen o he
Ubun u 20.04 en i onmen .
A.2.5 Benchma ks
We p o ide eady- o-use da ase s o some expe imen s in ou
pape . O he expe imen s need la ge da ase s (hund eds o
GB), and we p o ide sc ip s o download and p ocess hem.
The da ase s and sc ip s a e in hei co esponding sub- olde s
in ./da a deno ed by hei da ase names. To e alua e he unc-
ionali y o ou a i ac , he o iginal hund eds o GB inpu
da ase s a e no necessa y and we p o ide a es inpu ile
( es . x ) wi hin p og am olde s (e.g., ./join/ es . x ).
1 g i c l o n e [ Gi Hub l i n k o h e a i a c ]
2cd ./ obli ia o
3 chmod +x . / s c i p s / ae *
4 . / s c i p s / ae − i n s a l l − d e p e n d e n c i e s . sh
5 s o u c e ~ / . b a s h c
6 . / s c i p s / ae − i n e l −sgx . sh
7cd ~/ li n u x −sgx
8 [ L as commands p i n e d in he e minal]
9cd ~/ obli ia o
10 . / s c i p s / ae − b a si c − e s . sh
Figu e 1: Commands o se -up.
A.3 Se -up
A.3.1 Ins alla ion
To ins all he a i ac and dependencies, we p o ide com-
mands o e e ence in Figu e 1. I may needs 1 hou in o al
(depending on de ailed machines). A e he execu ion o
he command a line 6, ano he sugges ed command will be
p in ed in he e minal. Please change he di ec o y o an-
o he olde as sugges ed a line 7, and execu e he command
p in ed in he e minal. I he e is any issue and e o ega d-
ing he dependency ins alla ion, we sugges o execu e he
commands p o ided in ./sc ip s/ae-ins all-dependencies.sh
and ./sc ip s/ae-in el-sgx.sh line by line o na ow down he
de ailed inco ec s eps.
A.3.2 Basic Tes
We p o ide ./sc ip s/ae-basic- es .sh o check compila ion and
see i all so wa e dependencies a e ins alled success ully.
Please e e o line 9-10 in Figu e 1. E o in o ma ion will
be p in ed in he e minal i i is no execu ed success ully.
A.4 E alua ion wo k low
A.4.1 Majo Claims
(C1):
We p opose and implemen he new obli ious pa allel
non- o eign key (NFK) join algo i hm. I s unc ion is
o join wo ables, i.e., ma ching able ows based on
a gi en join a ibu e. I s pe o mance wi h espec o
consumed ime is expec ed o be
2.86 −77×
compa ed
o KKS and KKS* [7], as epo ed in Sec ion 5.1 o ou
pape (Table 2, Figu e 9 and 10).
(C2):
We p opose and implemen he new obli ious pa allel
o eign key (FK) join algo i hm. I s unc ion is o join a
p ima y key able and a o eign key ables, whe e he join
a ibu e in he p ima y able is dis inc . I s pe o mance
wi h espec o consumed ime is expec ed o be
1.7−
60×
compa ed o Opaque [10], as epo ed in Sec ion 5.1
o ou pape (Table 2 and Figu e 11 op le sub- igu e).
(C3):
We p opose and implemen he new obli ious il e
ope a o . I s unc ion is o e ie e speci ic subse s o
1 . / s c i p s / ae −e1 . sh
2 . / s c i p s / ae . sh
Figu e 2: Commands o expe imen s.
elemen s om a da abase. I s pe o mance wi h espec
o consumed ime is expec ed o be
2.8−52.3×
com-
pa ed o Opaque, as epo ed in Sec ion 5.2 o ou pape
(Figu e 11 bo om sub- igu e).
(C4):
We p opose and implemen he new obli ious agg e-
ga ion ope a o . I s unc ion is o gene a e s a is ics o a
summa y o mul iple able ows. I s pe o mance wi h
espec o consumed ime is expec ed o be
2.5−53×
compa ed o Opaque, as epo ed in Sec ion 5.2 o ou
pape (Figu e 11 bo om sub- igu e).
(C5):
We also implemen complex que ies o es he abo e
sepa a e ope a o s oge he . Thei unc ion is o ob-
ain he inal esul s o se e al gi en ope a o s based
on hei de ailed que y equi emen s [4,5]. I s pe o -
mance wi h espec o consumed ime is expec ed o be
2.58 −37.57×
compa ed wi h Opaque, as epo ed in
Sec ion 5.2 o ou pape (Figu e 11 op igh and bo om
sub- igu es).
A.4.2 Expe imen s
The e alua ion consis s o i e expe imen s co esponding o
he i e claims in Sec ion A.4.1. We p o ide a sc ip (./sc ip -
s/ae.sh) o hem, and please e e o he sugges ed commands
in Figu e 2 o execu e he ollowing i e expe imen s. Al-
e na i ely, e alua o s can un ./sc ip s/ae-e1.sh o E1 sub-
expe imen , ./sc ip s/ae-e2.sh o E2 sub-expe imen , e c., sep-
a a ely.
(E1):
[NFK Join] [5 compu e-minu es + 9GB memo y]: This
expe imen e alua es he NFK join o Obli ia o , and
compa es i wi h KKS*. We a e expec ed o see wo
loa ing poin numbe s p in ed in he e minal, which co -
espond o he consumed ime o Obli ia o and KKS*.
Ou esul is expec ed o be as e han KKS and KKS*
and ha e he sugges ed speedup as in oduced in C1 Sec-
ion A.4.1. We also conduc E1 on a PC whe e Obli ia o
and KKS* ake 0.0365 and 0.1294 seconds espec i ely.
(E2):
[FK Join] [5 compu e-minu es + 9GB memo y]: This
expe imen e alua es he FK join o Obli ia o , and com-
pa es i wi h Opaque. We a e expec ed o see wo loa ing
poin numbe s p in ed in he e minal, which co espond
o he consumed ime o Obli ia o and Opaque. Ou
esul is expec ed o be as e han Opaque and ha e he
sugges ed speedup as in oduced in C2 Sec ion A.4.1.
We also conduc E2 on a PC whe e Obli ia o and
Opaque ake 0.0002 and 0.0004 seconds espec i ely.
(E3):
[Fil e Que y] [5 compu e-minu es + 9GB memo y]:
This expe imen e alua es he il e que o Obli ia-
o , and compa es i wi h Opaque. We a e expec ed o
see wo loa ing poin numbe s p in ed in he e minal,
which co espond o he consumed ime o Obli ia o
and Opaque. Ou esul is expec ed o be as e han
Opaque and ha e he sugges ed speedup as in oduced
in C3 Sec ion A.4.1. We also execu e E3 on a PC whe e
Obli ia o and Opaque ake 0.0076 and 0.1288 seconds
espec i ely.
(E4):
[Agg ega ion Que y] [5 compu e-minu es + 9GB mem-
o y]: This expe imen e alua es he NFK join o Obli i-
a o , and compa es i wi h Opaque. We a e expec ed o
see wo loa ing poin numbe s p in ed in he e minal,
which co espond o he consumed ime o Obli ia o
and Opaque. Ou esul is expec ed o be as e han
Opaque and ha e he sugges ed speedup as in oduced
in C4 Sec ion A.4.1. We also execu e E4 on a PC whe e
Obli ia o and Opaque ake 0.1522 and 0.3788 seconds
espec i ely.
(E5):
[Complex Que y] [5 compu e-minu es + 9GB mem-
o y]: This expe imen e alua es he NFK join o Obli i-
a o , and compa es i wi h KKS and KKS*. We a e ex-
pec ed o see six loa ing poin numbe s p in ed in he
e minal, which co espond o he consumed ime o
Obli ia o ( he i s h ee numbe s) and Opaque ( he las
h ee numbe s). Ou esul is expec ed o be as e han
Opaque and ha e he sugges ed speedup as in oduced in
C5 Sec ion A.4.1. We also execu ed E5 on a PC whe e
Obli ia o and Opaque spen 1.1705 ( he sum o he i s
3 numbe s) and 3.4669 ( he sum o he las 3 numbe s)
seconds espec i ely.
A.5 No es on Reusabili y.
To ep oduce he e alua ion o he same expe imen s wi h
ha dwa e mode in ou pape , la ge machines a e equi ed. We
a e unable o suppo he o iginal e alua ion he e due o he
la ge scale and ou ecen sho age o In el SGX. The de ailed
o iginal machine con igu a ion is desc ibed in he Sec ion 5
o ou pape . Addi ionally, o e e ence, he de ailed o iginal
con igu a ion ile o In el SGX is gi en in ./sc ip /pa al-
lel.con . I use s ha e an access o such la ge machines as ou
pape (i.e., Azu e S anda d_DC32ds_ 3) and wan o ep o-
duce, please eplace ./[p og am name]/encla e/pa allel.con
wi h ./sc ip s/pa allel.con . And, o Obli ia o , se he
hi d pa ame e o oe_c ea e_pa alle_encla e in ./[p og am
name]/hos /pa allel.c o be 0 ( eplacing he o iginal
OE_ENCLAVE_FLAG_SIMULATE), o KKS* (i.e.,
./join_kks), se SGX_MODE in Make ile o be HW (o
eplace Make ile wi h he con en in SGX_Make ile). No e
ha , o un KKS*, you need o u he ins all he SGX PSW
and Openssl, e e [1] o check ./sc ip s/in el-sgx2.sh .
We imp o e he scalabili y o he obli ious ope a o s by de-
signing e icien and ully pa allel algo i hms, and do no ha e
ex a op imiza ions o i s paging o e head. We gi e ou obli -
iousness p oo in ou ex ended pape [8]. And as men ioned
in ou pape , In el Pin ool [6] and obli ious cons an - ime
ins uc ions om [9] a e also used o help a oid so wa e
side-channel a acks o In el SGX men ioned in ou h ead
model Sec ion 2.
When use s es ou p og ams wi h hei own da ase s, hey
a e sugges ed o pay a en ion o he encla e con igu a ion
ile pa allel.con and ensu e he numbe o max h eads, size
o heap, s ack (in pa allel.con ) and MAX_BUF_SIZE (in
pa allel.c) a e enough.
A.6 Ve sion
Based on he LaTeX empla e o A i ac E alua ion
V20231005. Submission, e iewing and badging me hodol-
ogy ollowed o he e alua ion o his a i ac can be ound a
h ps://seca i ac s.gi hub.io/usenixsec2025/.
Re e ences
[1]
In el( ) so wa e gua d ex ensions o linux* os.
h ps://
gi hub.com/in el/linux-sgx.
[2] Obli ia o . h ps://zenodo.o g/ eco ds/14723872.
[3]
Open encla e.
h ps://gi hub.com/openencla e/
openencla e.
[4] Tpc-h benchma k. h p://www. pc.o g/ pch.
[5]
AMPLab, Uni e si y o Cali o nia, Be kley. Big da a bench-
ma k.
h ps://amplab.cs.be keley.edu/benchma k/
,
2014.
[6]
In el. Pin - a dynamic bina y ins u-
men a ion ool.
h ps://www.in el.com/
con en /www/us/en/de elope /a icles/ ool/
pin-a-dynamic-bina y-ins umen a ion- ool.h ml.
[7]
Simeon K as niko , Flo ian Ke schbaum, and Douglas S ebila.
E icien obli ious da abase joins. VLDB, 2020.
[8]
Apos olos Ma ogiannakis, Xian Wang, Ioannis Deme zis,
Dimi ios Papadopoulos, and Minos Ga o alakis. OBLIVIA-
TOR: Obli ious pa allel joins and o he ope a o s in sha ed
memo y en i onmen s. C yp ology eP in A chi e, Pape
2025/183, 2025.
[9]
Nicholas Ngai, Ioannis Deme zis, Ja ad Gha eh Chamani, and
Dimi ios Papadopoulos. Dis ibu ed & Scalable Obli ious
So ing and Shu ling . In 2024 IEEE Symposium on Secu i y
and P i acy (SP), pages 4277–4295, Los Alami os, CA, USA,
May 2024. IEEE Compu e Socie y.
[10]
Wen ing Zheng, Anku Da e, Je h o G. Beekman, Raluca Ada
Popa, Joseph E. Gonzalez, and Ion S oica. Opaque: An obli -
ious and enc yp ed dis ibu ed analy ics pla o m. In 14 h
USENIX Symposium on Ne wo ked Sys ems Design and Im-
plemen a ion (NSDI 17), pages 283–298, Bos on, MA, 3 2017.
USENIX Associa ion.
