# Cryptographically verifiable anonymous voting using pan-european e-id’s
An analysis of the STORK 2.0 framework

Alessandro Preziosi<EMAIL_ADDRESS>
Diana Berbecaru<EMAIL_ADDRESS>
(November 28, 2016)

###### Contents

  1. 1 Introduction
  2. 2 Protocol description
    1. 2.1 Blind signature
      1. 2.1.1 Brute forcing the opacity factor
      2. 2.1.2 The One-More-RSA-Inversion Problem
      3. 2.1.3 RSA blinding attack
    2. 2.2 Onion routing
    3. 2.3 The protocol in detail
      1. 2.3.1 Authentication
      2. 2.3.2 Client initialization
      3. 2.3.3 Checking that nodes are alive
      4. 2.3.4 Package creation
      5. 2.3.5 Delivery
  3. 3 Experimental evaluation
    1. 3.1 Setting up virtual machines for sniffing
    2. 3.2 PEPS installation
      1. 3.2.1 Anonymity module installation
    3. 3.3 Anonimity DemoSP installation
  4. 4 Comparison with TOR
    1. 4.1 Encryption
    2. 4.2 Bootstrapping
    3. 4.3 Timing attacks
  5. 5 Conclusions

##  1 Introduction

The STORK 2.0 project (Secure idenTity acrOss boRders linKed 2.0) aims to
realize a single European electronic identification and authentication area.
The purpose of the project is to facilitate the citizens’ lives and to improve
citizen and business mobility inside the European Union. The interoperability
of eID solutions has many practical applications. For example, a German
student studying in Spain could identify to the Spanish university using his
account at the German university, without having to verify his identity in
person, create a second account, and store all the necessary data in two
different places.

In the future, this framework could allow people to start a company, get their
tax refund, or obtain their university papers without physical presence.

The role of the STORK platform is to identify a user who is in a session with
a service provider, and to send his data to this service. Whilst the service
provider may request various data items, the user will always controls the
data to be sent.

The different agents involved in the authentication process are:

  * •

The Service Provider (SP), which offers a service to the end user;

  * •

The Pan European Proxy Service (PEPS). One for each country, used to proxy
requests across countries;

  * •

The Identity Provider (IdP), to which the user can authenticate;

  * •

The Attribute Providers (AP), supplying additional information about the user;

For a more detailed explanation of the STORK architecture see [1] and [2].

In this work we will focus on the possibility of creating anonymous services
on top of the STORK architecture. This can be useful in particular in the case
of electronic surveys or elections. In this case we want the users to be
authenticated, to prevent repeated voting, but at the same time the votes
should be anonymous. It should be impossible to find out how a specific person
voted.

In order to do this blind signatures and an onion routing system similar to
the one used in TOR[9] (https://www.torproject.org/) are implemented.

Source code for the STORK 2.0 framework, used in all the following sections,
can be found at [5]

The purpose of this work is to describe this anonymity protocol in detail, to
anlyze a reference implementation, and highlight potential weaknesses.

##  2 Protocol description

To describe the protocol we will use an analogy with real life voting. In our
case the Ballot Box is a server owned by the service provider, and the voting
tickets are packages sent through the network.

In order to make it impossible to identify voters, the packages are bounced
through a number of proxy nodes before reaching the ballot box, making it as
hard as possible to trace their origin. We cannot allow anyone to vote as many
times as they want, therefore tickets must be signed, but the service provider
cannot sign the plaintext tickets, otherwise anonymity would be lost.
Therefore a blind signature scheme is used, to provide unlinkability.

###  2.1 Blind signature

A blind signature is a system through which an entity can sign a message with
no knowledge of the message itself.

In this case the RSA blind signature scheme described by Chaum is
implemented[3].

  * •

First, the client generates a big random number r, and raises it to the public
exponent, modulo N. This is called the blinding factor.

  * •

The message is then multiplied by the blinding factor, and the result is sent
to the SP for signing.

  * •

The SP signs the blinded message and returns the signature s to the client.

Due to the mathematical properties of RSA signatures, if the client divides s
by r modulo N, he will obtain a valid signature of the original message. For
more details see [3].

In order for the blind signature to be secure the number r should be big and
truly random, otherwise it can be brute forced by the signing entity. Let’s
check if this is true for the reference implementation.

####  2.1.1 Brute forcing the opacity factor

In the demo-client.js the random number is generated by the function
`rndInt32()`. The size of the opacity factor used by the demo client is 64
bits:

(demo-client.js:627)

⬇

opc[I]=k=new eSvyBigInteger(rndG.rndInt32()+”+rndG.rndInt32(),10);

A length of 64 bits could be considered secure in this use case, but a longer
opacity factor could be preferred. With a distributed brute force attack it
could be possible for the SP to unblind the ticket of a specific voter, and
find out who he voted for. This would take a couple years with current
technology, in order to unblind a single ticket (in 2002, the Distributed.net
project cracked a 64-bit RC5 key in 1,757 days using at total of 331,252
computers[6]).

But this specific implementation is much weaker for another reason. In fact,
it is not sufficient for the opacity factor to be big enough, but it must also
be truly random.

The client uses the function `eSvyPrng()` as an entropy buffer.

All the data used for the buffer is basically a fingerprint of the browser
(resolution, platform, available plugins, etc.), with the addition of two
calls to Math.random().

If we look at the Math.random() implementation in major browsers, it is not
cryptographically secure. In fact it is usually a pseudo-random generator
seeded with the time of the first call in milliseconds. For details on the
different implementations see [7].

This means that if an attacker can run javascript on the voter’s client, and
he knows the time when the opacity factor was generated, he can easily brute
force the opacity factor.

That information is always available to the SP, but it can also be available
to a third party attacker who could obtain the timing information by sniffing
the connection between the client and the SP as well, and the browser
fingerprint by managing to make the voter run some javascript in his browser.

The real entropy of the opacity factor is thus reduced to just the time of
generation of the pseudo random number, in milliseconds. This can easily be
known with little uncertainty, thus brute forcing the opacity factor would be
trivial.

In order to prevent this, a better random generator with an improved entropy
pool should be used. For example, Fortuna[8] is a javascript crypto library
with a strong pseudo number implementation which accumulates entropy from
various sources including:

  * •

mouse movements

  * •

internal clock

  * •

keyboard activity

  * •

the built-in crypto.getRandomValues() of some modern browsers

####  2.1.2 The One-More-RSA-Inversion Problem

In a blind signature scheme it is also desired that signing one blinded
message produces at most one valid signed messages. In the case of Chaum’s
scheme case this is not true[4]. In particular, the blinded message and the
unblinded signature s would also constitute a correct combination, which could
potentially allow a user to vote twice. This can be avoided by asking users to
sign a hash of the message instead of the message itself.

In our the ticket is signed directly, but this is only a security concern if
given the structure of the ticket, it is possible to easily find a blinding
factor which, multiplied by the original ticket (modulo N) still generates a
valid ticket. Given the relative complexity of a valid ticket in this case, I
would argue it would be computationally unfeasible to craft such an opacity
factor and use it to double vote.

####  2.1.3 RSA blinding attack

It is also important to be aware of the RSA blinding attack when using this
blind signature scheme. With this attack the signer can be tricked into
decrypting a message by blind signing another message.

This happens because the signing process is equivalent to decrypting with the
signer’s private key. An attacker can thus provide a blinded version of an
encrypted message for the SP to sign, in order to decrypt the message. It is
therefore important that the SP does not use the same key for signing tickets
and for encryption.

The SP implementation in this case doesn’t suffer from this, as a new, survey-
specific, private key is generated for each survey:

(survey.php:225)

⬇

function generateNewSurvey(){

global $keyLength;

list($certificate,$key,$module,$exponent)=newKeyandCert($keyLength);

mysql_query(”insert into Surveys (privatekey,module,exponent,certificate) ”.

”values (’$key’,’$module’,’$exponent’,’$certificate’)”);

return mysql_insert_id();

}

(wserv.php:255)

⬇

//Signature MUST BE survey-specific, to avoid cross-survey

//authorizations (and thus, multiple participations for a single

//citizen)

if (!$surveyId=$_REQUEST[’idsvy’])

errorDie(999,’You must provide a survey id’);

//Get the survey-specific signing key

list($sKeyS)=mysql_fetch_row(mysql_query(”select privatekey from Surveys where
surveyId = ’$surveyId’”));

$k=openssl_pkey_get_private($sKeyS);

###  2.2 Onion routing

In order to make voting anonymous it is not sufficient to use a blinding
signature scheme. In fact, if the signed tickets were then sent directly by
the voters to the SP, it would be easy to deanonymize a voter by looking at
the time the vote was sent and/or the sender IP address. Therefore it is
necessary to hide this information in one way or another.

An anonymization network like the one used in TOR[9] could be useful to hide
the voter’s IP, and make it impossible for the SP to know which IP address the
ticket was sent from. In TOR every package is proxied through several routers
before reaching its destination. Packages are encrypted several times, so they
have with multiple layers, like an onion. Each layer is encrypted with the
public key of a specific node in the route, so that every node will only be
able to read who’s next in the route, but not the contents of the packet or
its real destination[9].

This is used to hide the sender IP address, but in this case it’s not enough.
In fact, by knowing the time when the ticket was blindly signed, the SP could
easily identify the user who sent a certain ticket by looking at the time the
ticket was received. This kind of time-based linking will not be 100%
accurate, but it can be extremely accurate if the voters are not too many.

It is therefore paramount to make the votes reach the Ballot Box in a truly
random order, so they cannot be linked with the user who sent them.

In order to achieve this, in the STORK anonymity network, packages are not
relayed as fast as possible, but according to a specific delay set by the user
who created the package.

The SP will choose an interval during which all tickets for a specific survey
must be collected. EndDate (endD) is the time when no more participations can
be issued, and the ballot box will start accepting tickets. CloseDate (cloD)
is the time when the ticket collection ends.

It will be the client to decide at which time his packets will be relayed
between the nodes in the network, and the time of final delivery to the ballot
box.

These timings are picked backwards, starting from the time of delivery to the
ballot box.

Figure 1: The delivery time is picked at random within the frame

The random delivery time is picked at random within a ”frame”, which starts at
endD + safety and ends at cloD - tolerance, as shown in Fig. 1. Tolerance is a
value to avoid packets reaching the ballot box too late. It is hardcoded (2
minutes in this case), and the choice depends mainly on how often the nodes in
the network check their queue to forward packets (which is roughly the upper
limit of the maximum delay a package should experience).

The safety parameter is a time, in seconds, which represents the minimum
acceptable delay, to avoid packages going through the anonymity network with
no delay at all.

The client will pick a random delivery time to send the packet to the ballot
box within this frame. Then all the delivery times for the previous steps in
the onion routing will be picked, starting from the last node and going back,
as shown in Fig. 2.

Figure 2: The remaining time (A) is divided by the number of remaining nodes
(3 in this case) to pick a random delivery time for each node.

For example, let’s say endD=1000, cloD=1200 and `now()` = 100. A randomly
chosen delivery time for the ballot box could be 1100. Then the remaining
available time is calculated, as 1100-`now()` = 1000, then divided by the
number of remaining nodes on the route, let’s assume 10. The delivery time for
node number 9 would be picked at random between 1100 (the time of delivery to
the ballot box) and (1100 - (1000/10)). This calculation is repeated
recursively for all remaining nodes on the route, from the last one to the
first, to choose the delivery time for every step in the route.

This should provide untraceability of the voters, as all votes are received by
the ballot box at a random random between the closing time and the end time,
from random nodes in the network.

The problem is that a malicious SP could provide different clients with
different values of cloD and endD, thus identifying voters by the time their
ticket is received.

Therefore it is important that all voters are served the same values of cloD
and endD. This must be verified before the packets are sent into the network.
To do this, a hash of these parameters could be published on some third party
server.

###  2.3 The protocol in detail

####  2.3.1 Authentication

Before being allowed to participate every user must be authenticated to the
SP. This authentication can happen through any means and must not necessarily
use the STORK network.

The authentication is needed to avoid multiple voting or voting by people who
shouldn’t be allowed to take part in the survey. It also lowers the surface
area for a Denial Of Service attack, as any unauthenticated request to the SP
will be immediately dropped.

In the case of the demo-SP, authentication is not implemented. A dummy
function is used, which always returns true. Every user who connects to the
demo SP is considered as authenticated and is given access to the survey.

(wserv.php:400)

⬇

function checkAuthenticationAndAuthorization($surveyId=”,$mark=false) {

// Here, being authenticated and authorised should be checked (to

// participate if survey id is given, and to use the proxy if

// not). Always true on the demoSP

if ($mark)

// Here participant should be marked so he cannot participate twice.

return true;

return true;

}

####  2.3.2 Client initialization

Figure 3: The information about the survey and the list of nodes are retrieved
from the SP through https

Initially the client needs to download the list of nodes in the network. This
list is retrieved from the S-PEPS.

(common.php:73)

⬇

$nodelistDownloadURL=$SPEPSHost.’/PEPS/anonymity/resources/nodes/citizen/js’;

To avoid problems with ssl certificates, in the demo the list of nodes is not
taken directly from the PEPS but from the SP (Fig. 3, step 1) which forwards
the request to the PEPS (step 2), then sends it back to the client as a
javascript, through https (step 4):

(survey.php:184).

⬇

if($TESTMODE){

//Client expects the node list from a secure url. demoSP gets it and

//delivers to the client through an https connection (Client will

//already be trusting demoSP’s certificatem eventhough it is self

//signed)

$nodelistURL=’?op=nodesjs’;

}

The demo client always checks that all data is loaded through https:

(demo-client.js:134)

⬇

for (var i in scripts){

if(scripts[i].match(/^(http?|HTTP?)/) &&
!scripts[i].match(/^(https:?|HTTPS:?)/)){

alert(_(’Safety threat: Critical data was retrieved through an unsecured
channel.\n\n’+scripts[i]+’\n\nAborting.’));

stat=’err’;

this.ended = true;

break;

}

}

This is true in this case as well, because the survey page will be delivered
through https, and the javascript client will trust the survey’s certificate
even if it’s self signed (because it’s on the same page).

On a deployment configuration the client should download this list directly
from the PEPS, through a secure SSL connection. This is important otherwise an
attacker could serve a list of nodes controlled by him. This would not enough
to deanonymize voters though, unless the attacker also has access to the
ballot box server.

The list is received as a javascript script which populates the variable
`nodes`.

If the client is not javascript and not limited to the same-origin policy, the
list can also be retreived in JSON or XML format
(services/ResourcesService.java), from the endpoints:

    /PEPS/anonymity/resources/nodes/citizen/json
    /PEPS/anonymity/resources/nodes/citizen/xml

For every node in the list the client receives its url, its public key, and a
weight.

The weight is used for load balancing when picking a route at random, so nodes
with a higher weight get picked with a higher probability.

The client also needs information regarding the survey and the SP. This is
passed through a variable `parameters` generated by survey.php.

These are the elements contained in the anonymousSurvey XML structure:

  * •

name : name of the survey (only chars and numbers)

  * •

idSvy : id of the survey, generated by the SP (only numbers)

  * •

lang : language to be used for client messages, two letter ISO code

  * •

srvUrl : URL of the Service Provider

  * •

srvAuth : token for authentication and authorization towards SP. Will be sent
along with each connection and SP must reject them if the token is not valid
(user is no longer authenticated or authorised)

  * •

srvCert : survey specific RSA key modulus for blind signature (base 64
encoded)

  * •

SRVeXP : public exponent for previous modulus (base 64 encoded)

  * •

rouLen : route length (recommended 3 … 6), 0 = direct to ballot box through SP
proxy

  * •

bBxUrl : absolute URL of the ballot box

  * •

bBxMod : public key (modulus) of the ballot box (base 64 encoded)

  * •

bBxExp : public key (exponent) of the ballot box (base 64 encoded)

  * •

endD : datetime (ISO string or timestamp in miliseconds) of the end of polling
(when no more participations can be issued)

  * •

cloD : datetime (ISO string or timestamp in miliseconds) when the tallying
will start (at least cloD-endD >= 600+rouLen*120, if 0, the client will assume
endD+2(600+rouLen*120)

  * •

areaLog : name attribute value of a textarea to show logs to the user, null if
not available

  * •

disExt : true to disable the automatic launch of browser extension

  * •

urlExt : URL for an informational page (for the browser extension)

  * •

pause : optional: true to start eSurvey paused (routes won’t be calculated
before hitting submit). Else, route calculation will start on page load

  * •

pauseIfExt : optional: true to start eSurvey paused when the extension is
present, call the iterate method to start

  * •

refresh : true if the extension must invite the user to reload the page after
submitting the participation

  * •

minVer : minimum required version of the client software

  * •

keepA : To send periodic connections to SP to keep the session alive while the
survey is being filled in

  * •

skip : name of an element of the form to be skipped (will not be sent)

An example survey would look like this:

    <anonymousSurvey>
       <name>surveyForm</name>
       <idSvy>845</idSvy>
       <lang>en</lang>
       <svrUrl>wserv.php</svrUrl>
       <svrAuth></svrAuth>
     <svrSCert>9eF5Lm7iEncZDxE...mpw241Z8gbfcOjPVropK845M=</svrSCert>
       <svrSExp>AQAB</svrSExp>
       <keepA>true</keepA>
       <rouLen>2</rouLen>
       <bBxUrl>https://.../demoSP/wserv.php</bBxUrl>
       <bBxMod>AMhgf21MMHKYJY...9rWbFrC55K0iNn8xjaQPJrn</bBxMod>
       <bBxExp>AQAB</bBxExp>
       <endD>1395820821000</endD>
       <cloD>1395822501000</cloD>
       <sButt>sendButton</sButt>
       <areaLog>logarea</areaLog>
       <pause>true</pause>
       <disExt>true</disExt>
    </anonymousSurvey>

(The srvAuth is always empty in the demoSP code, but it should be a valid
authentication token)

Before starting the voting process the client asks the SP if the user is
authenticated by sending a request containing the surveyId and the
authentication token.

Example request: `param=auth&token=...&idsvy=999`

Example response: `<response><authorised/></response>`

In the case of the demoSP the answer is always positive.

The client will also ask the SP the current time to avoid problems due to date
sincronization when calculating delivery times.

Example request: `param=date&token=...&idsvy=999`

Example response:

`<response><serverTime format="unix">1395820534</serverTime></response>`

####  2.3.3 Checking that nodes are alive

Figure 4: A bundle containing challenges for the first node of each route is
signed by the SP and then relayed to the network by the PEPS, to check which
nodes are alive. The response is proxied back to the client

At this point the client generates the random routes the ticket will take.

For each alternative route, the first node in the route is challenged to check
if it’s up and working.

A challenge package is like a participation package but with only one layer of
encryption, and no relay data, only the challenge. The nodes will just
decipher it, send back the challenge, and discard the package. Packages are
encapsulated inside a bundle, which is sent to the SP (Fig. 4, step 1). The
request to proxy the package to the peps looks like this:

    param=proxy
    token=dl0tim56ujtlu2pd2509cdm7j2
    idsvy=845
    bundle=
    <bundle>
     <sealedPackage>
       <id>0</id>
       <payload>...</payload>
       <key>...</key>
       <recipient>.../PEPS/anonymity/handler/node</recipient>
     </sealedPackage>
    </bundle>

The SP will sign the bundle with XMLdsig and then relay it to the PEPS (Fig.
4, step 2):

(wserv.php:300)

⬇

//We sign the bundle (or else, it won’t be accepted by the S-PEPS)

$bundle = calculateXMLDsig($bundle,$demoSPCertFile,$demoSPKeyFile);

The PEPS will check the signature and if it’s not a valid signature from a
trusted SP (or node), the package will be discarded. This allows only trusted
entities to forward packets into the network to prevent some Denial of Service
attacks.

(InboundPackageHandler.java:330)

⬇

Bundle bundle = Bundle.getBundleFromXMLString(strBundle);

checkBundleSignature(strBundle, NO_PROXY);

LOG.trace(”Bundle signature check!”);

If the signature is correct, the PEPS will send the packages inside the bundle
to the respective nodes (Fig. 4, step 3). When the PEPS wil receive the
responses from the nodes (Fig. 4, step 4) it will relay them to the SP (Fig.
4, step 5), which will again relay them to the client (Fig. 4, step 6).

An example of request with a signed bundle can be seen in Fig. 5. Fig. 6 shows
the response from the node.

If the client doesn’t receive any challenge response from any of the first
nodes in the alternative routes, the process is interrupted and he will have
to try again a later time.

Figure 5: Request

Figure 6: Response

####  2.3.4 Package creation

At this point the client generates a ticket with this structure:

    <ticket>
    Ψ<idTicket>12345</idTicket>
    Ψ<idSurvey>12345</idSurvey>
        <endTime>endD</endTime>
    Ψ<closeTime>cloD</closeTime>
    </ticket>

The ticket ID is a randomly generated number, expressed in base 64. In the
case of the demo client the number is 168 bits long:

(demo-client.js:612).

⬇

itkt[I]=j=sMod.bin2b64(rndG.random(21)); //21*8=168 bits

This means the number of different ticket ids that could be generated are in
the order of $10^{50}$, so it would be extremely unlikely for two different
voters to generate the same ticket ID, assuming the algorithms they use are
sufficiently random. Once the ticket has been generated, it will be blinded
with the opacity factor and sent to the SP for signing.

The request will look like this:

    param=ssign
    token=dl0tim56ujtlu2pd2509cdm7j2
    idsvy=845
    opct=...blinded ticket...

The SP will sign the ticket with the survey-specific key and return it to the
client. It is very important for the signature to be survey specific because
otherwise multiple participations could be allowed if a ticket generated for
one survey is used to vote in another.

The response from the SP looks like this:

    <response>
      <signedTicket>...</signedTicket>
    </response>

The client now has the innermost ticket that he will send to the ballot box.

If at this point the client is stopped before sending the ticket, he wont be
able to vote anymore, because the SP will only sign a ticket once for every
client.

This can be an issue. An attacker could deny a user the right to vote if he
manages to keep the response from reaching the user. And if the users stops
the process for some reason like a loss of connectivity, loss of power, or a
crash in the client software, he will also be unable to vote.

To solve this issue, instead of marking the user and preventing him from
getting another blindly signed ticket, the SP could allow a user to ask for a
blind signature more than once, as long as the request is identical to his
first request. On the client side, before sending a signature request, the
ticket should be saved on disk so it can be restored and used again in case of
problems on the client side (if a different blinded ticket is provided, the SP
will refuse to sign it).

Now that we have the inner ticket, it must be encrypted several times to be
sent through the anonymity network, and finally the ballot box.

The innermost participation package will contain the ticket, its signature and
the form contents. All of this is encrypted with the SP ballot box public key
using RSA and RC4. The payload is encrypted with RC4, and stored in the cryp
field. The RC4 key is encrypted with rsa and store in the evkey field.

A package contains various fields:

  * •

cryp : the encrypted payload

  * •

chk : an md5 checksum of the package

  * •

url : destination url of the next node

  * •

chal : the challenge expected from the next node

  * •

pChal : the challenge to be returned to previous node

  * •

sndD : timestamp when the package must be relayed

  * •

cloD : timestamp when the tallying will begin

  * •

rejD : timestamp when it’s safe to discard the package in case it couldn’t be
delivered

Figure 7: Package encapsulation.

The package will then be recursively encrypted and encapsulated in an outer
package as shown in Fig. 7, once for each node in the route, starting from the
last one. Every node will only be able to decrypt its own layer, reading the
time the package must be relayed to the next node, the url of the next node,
and the challenge that must be returned to the previous node. The sending node
will delete a package from the queue only if the challenge received is the
expected one, else it will try resending it.

Let’s see an example of the process with two nodes to make it clearer:

  * •

The innermost package (A) is first created. It contains the signed ticket and
the survey data, and it’s encrypted with the ballot box public key.

  * •

The encrypted package A is encapsulated in a bigger package B, inside its cryp
field (see Fig. 7). The url field will contain the url of the ballot box. Chal
will contain, for example, 999 and pChal 888\. The entire package is encrypted
with the public key of the last node in the route (nodeL).

  * •

This encrypted package is again encapsulated inside the cryp of a bigger
package C. The url field will contain the url of the last node (nodeL). Chal
will be 888. The entire package is encrypted with the public key of the first
node (nodeF).

At the end of the process we have one big package with several layers of
encryption. The package will be sent to the first node, nodeF, with a request
that looks like the one in Fig. 5. NodeF will use its private key to decrypt
the ”key” field, and use the decrypted symmetric key to decript the ”payload”
field (see Fig. 7). In the paload it will find package C, from which it can
read the url of the next node, nodeL, and the expected challenge from that
node (888). The fields cryp and evkey will be unreadable because they are
encrypted with nodeL’s public key. When the package must be relayed a new
sealedPackage like the one in Fig. 5 will be created, using the evkey field of
package B for the ”key” field, and the cryp field of package B for the
”payload” field (Fig. 7). This sealedPackage will be sent to nodeL which,
using its private key, will be able to decrypt it and obtain package B (which
was unreadable to nodeF). The node will reply to nodeF with the content of the
field pChal (888). It will also read the url field, and when sndD is reached,
relay the inner, encrypted package to the next node, which in this case is the
ballot box.

####  2.3.5 Delivery

Figure 8: A bundle containing the packets is proxied to the PEPS (2), which
relays it to the anonymity network (3). After bouncing between nodes a few
times (4) the package will reach the ballot box on the SP (5)

Once the packages for the various alternative routes are created they are
proxied through the PEPS and sent to the network (Fig. 8). The packages can
all be put inside a single bundle (the demo client sends them in separate
bundles though).

The bundle is sent to the SP with the request to proxy it to the S-PEPS:

    param=proxy
    token=12345
    idsvy=12345
    bundle=<bundle>...</bundle>

The SP will apply an XMLDsig and send the package to the S-PEPS, which acts as
the first node in the anonymity network.

Every node in the network will decrypt the package with its private key when
its received, and add it to a local queue. Periodically the node will run the
function `processQueue()` (OutboundPackageHandler.java), and each package that
needs to be sent (because the sndD time has passed), will be sent to the
relative node.

The package will only be removed from the queue if a correct challenge
response is received by the next node, otherwise it will be kept in the queue
to retry at a later time.

The packages are kept in the queue until the ReceivalDue time + a rejectTime
variable which is set up in the configuration file (anonymity.properties). The
default value is 24 hours (86400000ms). The ReceivalDue value is taken from
the CloD value in the package.

This kind of queue management is risky, because in the current implementation
there’s no defence against maliciously forged CloD values and challenge
values. This could be exploited to force the nodes to continuously keep
bouncing packets between each other. The queues could grow indefinitely
causing memory starvation on a target node.

In particular a package can be created such as the expected challenge from the
next node will be different from the challenge encrypted in the package
destined to that node. This way the package will remain in the sender queue
forever because the challenge response will always be wrong, and the sender
will keep trying to send it until cloD is reached. cloD can also be set by the
attacker to an arbitrary distant date, so the packages will be kept in the
queue forever.

It would also be hard to trace the source of the attack and block these
malicious packets, as the challenge ”bomb” can be hidden at any layer of
encryption, making it hard to identify the original sender of the malicious
packet.

A malicious packet could be created in such a way:

  * •

The inner ticket can be anything, even random bits (it doesn’t matter because
it will never reach the ballot box).

  * •

The challenge field of layer N will be a random number

  * •

The expected challenge field of layer N-1 will be a number different from the
previous one, and the cloD field will be an arbitrarily big value

  * •

All other layers will be fabricated normally

A package crafted this way is designed to remain forever stuck in the queue at
node N-1. The first nodes will see it as a regular package, indistinguishable
from the others, it will reach node N-1 from another arbitrary node in the
network. By sending enough packages crafted this way, an attacker could
deliberately congest node N-1.

A solution to this problem would be to discard a packet if the challenge
response received is incorrect, instead of keeping it in the queue
(OutboundPackageHandler:280).

The same could happen if on a certain layer the url of the next node is
deliberately set to an unreachable address, and the cloD value is set to a
high number.

To prevent this from happening, instead of trying until cloD, a maximum delay
from the sndD date or a maximum number of tries could be set.

Once the closing time is reached the Ballot Box server will receive all
participations from the anonimity network. Given that the same participation
will be sent through multiple alternative routes, the ballot box only
considers the first ticket it receives with a certain ticket id. Subsequent
tickets with the same ID, coming from alternative routes, will be discarded.

At the end of the election the SP should show publicly all the tickets
received, so that users can check that their vote was counted. (only they will
know which ticket ID belonged to them). If a voter sees that his vote wasn’t
included in the ballot box, currently there is no way to know which server was
the one maliciously dropping his vote. If all servers were required to return
a signed message to confirm the recieval of a package, then with their
collaboration it would be possible to identify the server who maliciously
dropped the vote.

##  3 Experimental evaluation

###  3.1 Setting up virtual machines for sniffing

For testing purposes the code was deployed on three virtual machines using
VirtualBox, two running the PEPS software, and one acting as a demo Service
Provider.

In order to run the virtual machines on the same virtual network, and be able
to sniff the traffic between them, for every virtual machine go to
`Device->Network Adapter` and choose attached to ”Internal network” and
”intnet” as the name of the network.

Then, on the guest OS (xubuntu 12.04) the machines have been set up to use a
static IP address:

    192.168.0.2  : node1 (a PEPS serer)
    192.168.0.3  : node2 (another PEPS server)
    192.168.0.99 : demoSP

To sniff the packets we used VirtualBox’s network tracing feature. It can be
enabled with this command, before running the VM:

”VBoxManage modifyvm [vm-name] –nictrace[adapter-number] on
–nictracefile[adapter-number] file.pcap”

For example:

”VBoxManage modifyvm ”PEPS” –nictrace1 on –nictracefile1 file.pcap”

###  3.2 PEPS installation

The PEPS software was installed and deployed under Tomcat 7.

Before compiling and installing the PEPS it is necessary to set up the correct
keystores and edit configuration files.

Other than the files listed in the documentation, it is also required to
modify the files in `PEPS\src\main\config\embedded\SignModule_*****.xml` with
the correct certificate information (serial number and issuer).

The logs, useful for debugging, can be found inside the `webapps` subfolder in
the `CATALINA_HOME` directory, usually:

`C:\Program Files (x86)\Apache Software Foundation\Tomcat 7.0` (on Windows)

or `/var/lib/tomcat7/` (on Linux)

####  3.2.1 Anonymity module installation

The anonymity module can be installed as described in the official guide, but
some extra steps are necessary.

In the configuration file `anonymity.properties` two extra lines were
nrequired:

    #Anonymity properties
    anonymity.keystore.path=file:/pathToKeystore.jks
    anonymity.keystore.pass=password

The aliases in the example keystore should also be changed:

    From:     To:
    node1 --> node1
    node2 --> node2.current
    node3 --> node3.current

The software expects a ”.current” suffix for all aliases except the node it’s
running on. This is used to deal with the update of certificates.

The Anonymity module also needs the ojdbc6 library (version 11.2.0.2.0) which,
if not present, should be downloaded directly from Oracle’s website
(http://www.oracle.com/technetwork/database/enterprise-
edition/jdbc-112010-090769.html) , after accepting their license.

The ojdbc jar can be manually added to the maven repositoy with the command:

    mvn install:install-file -Dfile=./ojdbc6.jar -DgroupId=com.oracle \
    -DartifactId=ojdbc6 -Dversion=11.2.0.2.0 -Dpackaging=jar

When installing the database, make sure that the `addres` value of nodes,
corresponds to the real, absolute addresses of test nodes.

Once the module has been compiled, the PEPS code must be compiled again, with
the anonymity option enabled:

`mvn clean package -P embedded -P anonymity -DskipTests`

###  3.3 Anonimity DemoSP installation

For testing purposes the demoSP was installed inside a virtual machine running
Ubuntu 12.04.

Apache was used as a web server (with PHP support), and MySQL for the database
functionality.

The database schema to be installed can be found in `Anonymity_demoSP/db.sql`,
it is used for storing the information about surveys and storing the tickets
received by the ballot box.

Before running the demoSP, the configuration file, `common.php` must be edited
with the correct information.

In particular the mysql credentials must be changed, as well as the url of the
S-PEPS.

For the PEPS to accept bundles signed by the demo SP, the SP public key must
be imported in the PEPS keystore. This can be done with the command:

`keytool -import -alias demoSP -keystore storkNodeKeys.jks -file
demoSP_cert.pem`

Figure 9: Settings shown on index.html

On the index.html page there are some settings for testing, as shown in Fig.
9:

  * •

Participations allowed until corresponds to the cloD field.

  * •

Participations reception until corresponds to the endD field.

  * •

Number of paths is the number of alternative routes to be used for a single
ticket.

  * •

Update suggestions changes the dates according to the current date.

  * •

Server-side injector is used to generate partecipations directly on the SP and
inject them in the network (survey.php:129).

The payload padding can be important in some cases. Consider a survey where
option B is 50 bytes longer than option A, it would be easy for any entity in
the network to differentiate between tickets voting for A and tickets voting
for B, just by looking at the size of the encrypted package.

It would be important, therefore, to pad packets with a random length, to make
it harder to differentiate encrypted votes. Even better than using a big
random length pad, one could generate a padding such that all options in the
survey have the same length. Otherwise malicious nodes could calculate, given
a certain package length, how likely it is to be a vote for candidate A or
candidate B, and drop the packet according to this information.

Even if there isn’t a 100% certainty, on a big enough number of packets this
could skew the survey towards a certain option. In particular the SP or the
PEPS could do this. Nodes in the network can drop packets maliciously as well,
but they would need to control nodes on all the alternatives routes to drop
packets successfully.

It is also important to notice that, while the SP doesn’t know who is voting
for what, in this configuration it knows with certainty who voted and who
chose to abstain. To keep this information private, an extra option should be
present in the survey to account for abstainees, generating a package
indistinguishable from a regular vote.

##  4 Comparison with TOR

The onion routing strategy used to anonymize users is very similar to the one
used in TOR (The Onion Router), with some minor differences.

###  4.1 Encryption

For the stream encryption TOR uses 128-bit AES in counter mode, with an IV of
all 0 bytes[9], and for the public-key cipher, it uses RSA with 1024-bit keys
and a fixed exponent of 65537. Although recent versions have increased the key
size, most users still run older versions with 1024 bit keys.

This PEPS implementation also uses RSA keys of 1024 bit, although the key
length can be increased in the configuration file:

(common.php:47)

⬇

$keyLength=’1024’;

For the stream cypher, RC4 is used, with a key length of 128 bit.

(demo-client.js:1793)

⬇

var S=rndG.random(16); //16*8=128 bits

RC4 is subject to statistical attacks but this should not be an issue in this
use-case, as it is only used as a one-time pad.

The encryption strength of both systems is comparable. It would be advisable
to switch from 1024 bit keys to bigger keys, as 1024 bit keys are considered
creckable by government entities as of 2014. The NIST suggests a key size of
2048 bits or higher.

###  4.2 Bootstrapping

The way the client becomes aware of nodes in the network is very important for
an anonymizing protocol such as these. The TOR and PEPS implementations are
different in this regard.

The PEPS approach is very centralized. The list of nodes is retrieved from the
PEPS through https. This means the user must trust the entity running the
PEPS, and its certificate authority, or he could be served a malicious list of
nodes.

TOR has a more distributed approach. There are a number of known, independent
”Directory Authorities”, which are contacted by the clients to learn about the
nodes in the network. There are 10 official Directory Authorities, and they
are hardcoded in the TOR client. Alternative authorities can be used, but this
is advised against to avoid splitting of the network.

Nodes in the network (routers, in TOR’s terminology) regularly contact the
Directory Authorities to advertise their status. Every day, starting at 00:00
am, the authorities vote to reach a new consensus on the status of the
network. Routers are considered active only if the majority of authorities has
included them in their ”vote”. A consensus document on the status of the
network is thus generated. The users download the consensus document at a
random time from a random Directory Authority. The actual protocol is more
complicated than this, for details see[10].

In this case, the end user only needs to trust the majority of the Directory
Authorities. If a single authority is compromised, it is not an issue.

The approach chosen by the STORK project is simpler, and has a single point of
failure, but it shouldn’t be a big issue in this case. In fact, even if the
attacker manages to serve a compromised list of nodes, the votes will still
remain anonymous as long as the SP is not also compromised. What an attacker
could do by serving a compromised list of nodes, is denying a user the right
to vote. Given that the list of nodes is passed from the PEPS to the client
directly, the PEPS will know the IP addresses of voters requesting the node
list, and could make it impossible for some users to vote, based on their IP
address.

If the PEPS cannot be trusted to be impartial in the delivery of node lists,
it would be better to use an approach more similar to TOR’s, with multiple
entities serving the public node list, so everyone knows they’re being served
the same list, unless all servers are colluding.

###  4.3 Timing attacks

This is where the two systems differ the most. TOR was created mainly to
anonymize access to websites, or general purpose connections. It’s therefore
important to have a latency which is not too high, to keep the services
usable, while making the users hard to identify. In order to do this, TOR
needs a lot of nodes and a lot of traffic going between them, to make time-
based traffic analysis harder.

Our use case is different. Using tor wouldnt be sufficient to anonymize users
in the case of an election, because their votes need to be authenticated, so
even if their IP is hidden, the votes will still be tied to their accounts.
Even if a blind signature scheme is used, it would still be possible to trace
voters with some degree of certainty, based on the time when their vote
reaches the ballot box.

What the STORK anonymity network does to solve this issue, other than hiding
the users IP, is also making sure all the packets (the votes) reach the server
within a specific time window, and in a completely random order, making it
impossible for the server to link packets with users. This cannot be done in
the case of TOR, which was engineered to be used in many different situations,
where additional, artificial delays are not desirable.

This also means that the anonymity network in STORK doesn’t need as many
nodes, or as much traffic, because it is resilient to timing analysis attacks
by design. Increasing the number of nodes is mainly useful to increase
availability and reduce the risk that all nodes are controlled by a malicious
entity. This is still a risk in any case, though, given that the list of nodes
is received by a single entity, no matter how many the nodes in the network.

##  5 Conclusions

This anonymity protocol can be useful in many cases, and the reference
implementation works, but there are some security concerns which should be
addressed before deployment:

  * •

the client should use a better entropy buffer for the generation of the
opacity factor, otherwise the SP could easily brute force it, and unblind a
blinded ticket (see 2.1.1)

  * •

the cloD value (the time when the votes are tallied) must be verifiably the
same for all voters (see 2.2), otherwise voters can be deanonymized based on
the time their vote is received

  * •

the client should be allowed to request a blind signature more than once, as
long as the blinded ticket provided is the same. Otherwise, connectivity
problems (malicious or involuntary) could prevent a user from voting (see
2.3.4)

  * •

nodes should discard packets if the challenge received from the next node is
incorrect, and if the next node is offline, only keep trying for a limited
number of times. Otherwise, queues can grow indefinitely and cause memory
starvation on a target node (see 2.3.5)

  * •

an option to abstain should be present in every survey, and all options should
have the same length in bytes, or a long, random padding should be used. This
makes it impossible to profile encrypted votes based on the package length
(see 3.3)

  * •

longer RSA keys of 2048 bits or more would be preferred, to protect against
targeted attacks from government entities (see 4.1)

  * •

it would be better if the list of nodes wasn’t downloaded from a single entity
(the PEPS). A distributed approach like the one used in TOR could be preferred
(see 4.2)

As it stands, if the SP and the PEPS are controlled by the same entity, or
they are colluding to deanonymize users, they can easily do so. Therefore a
system like this should not be trusted to grant anonymity in the case of a
government-run election.

The reference implementation has been tested and it works for a simple test
case, but further tests would be required to observe the behaviour under heavy
load on a deployment server.

## References

  * [1] Herbert Leitold, “Challenges of eID Interoperability: The STORK Project”, Privacy and Identity Management for Life, Volume 352, 2011, pp. 144-150
  * [2] V. Koulolias et al. “STORK e-privacy and security”, 5th International Conference on Network and System Security, 2011, pp. 234 - 238
  * [3] Chaum, David, ”Blind signatures for untraceable payments”, Advances in Cryptology Proceedings of Crypto 82 (3), 1989, pp. 199-203
  * [4] M. Bellare and C. Namprempre and D. Pointcheval and M. Semanko, ”The One-More-RSA-Inversion Problems and the Security of Chaum’s Blind Signature Scheme” Journal of Cryptology (16), 2003, pp. 185-215
  * [5] Stork 2.0 source code, https://www.eid-stork2.eu/index.php?option=com_content&view=article&id=61
  * [6] http://blogs.distributed.net/2002/09/25/00/00/bovine/
  * [7] Amit Klein, ”Temporary user tracking in major browsers and Cross-domain information leakage and attacks”, 2008, chapter 2
  * [8] https://clipperz.is/security_privacy/crypto_algorithms/#prng
  * [9] Roger Dingledine, Nick Mathewson, ”Tor Protocol Specification”, https://gitweb.torproject.org/torspec.git?a=blob_plain;hb=HEAD;f=tor-spec.txt
  * [10] ”Tor directory protocol, version 3”, https://gitweb.torproject.org/torspec.git?a=blob_plain;hb=HEAD;f=dir-spec.txt


# The Impact of Semantic Context Cues on the User Acceptance of Tag
Recommendations: An Online Study

Dominik Kowald*, Paul Seitlinger**, Tobias Ley**, Elisabeth Lex  *Know-Center
Graz & Graz University of Technology (Austria), **Tallinn University (Estonia)
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
(2018)

###### Abstract.

In this paper, we present the results of an online study with the aim to shed
light on the impact that semantic context cues have on the user acceptance of
tag recommendations. Therefore, we conducted a work-integrated social
bookmarking scenario with 17 university employees in order to compare the user
acceptance of a context-aware tag recommendation algorithm called 3Layers with
the user acceptance of a simple popularity-based baseline. In this scenario,
we validated and verified the hypothesis that semantic context cues have a
higher impact on the user acceptance of tag recommendations in a collaborative
tagging setting than in an individual tagging setting. With this paper, we
contribute to the sparse line of research presenting online recommendation
studies.

Keywords. Tag Recommendations; Online Evaluation; 3Layers

††journalyear: 2018††copyright: iw3c2w3††conference: The 2018 Web Conference
Companion; April 23–27, 2018; Lyon, France††booktitle: WWW ’18 Companion: The
2018 Web Conference Companion, April 23–27, 2018, Lyon, France††doi:
10.1145/3184558.3186899††isbn: 978-1-4503-5640-4/18/04

##  1\. Introduction

Tag recommendation algorithms support users in finding descriptive tags for
their bookmarked resources. Related research has proposed various ways to
calculate tag recommendations (see e.g., (Seitlinger et al., 2013)) and in our
previous work (Kowald and Lex, 2016), we have shown that the factors of tag
usage frequency, recency and semantic context influence the accuracy of tag
recommendations. While frequency and recency were found to be important in
both individual tagging settings (i.e., narrow folksonomies) and collaborative
tagging settings (i.e, broad folksonomies), the semantic context only
increased the tag recommendation accuracy in the collaborative tagging
setting.

Therefore, it is the aim of this paper to validate these offline evaluation
results also in an online tag recommendation study, which enables us to test
the following hypothesis: “Semantic context cues have a higher impact on the
user acceptance of tag recommendations in a collaborative tagging setting than
in an individual tagging setting”. Thus, the contributions of our paper are
two-fold: (i) we shed light on the impact that semantic context cues have on
the user acceptance of tag recommendations, and (ii) with this paper, we
contribute to the sparse line of research presenting results of online tag
recommendation studies (see e.g., (Jäschke et al., 2009)).

##  2\. Method

Tagging setting | $|T|$ | $|Y|$ | $|B|$ | $|MostPop|$ | $|3Layers|$
---|---|---|---|---|---
Individual (narrow) | 119 | 191 | 53 | 29 | 24
Collaborative (broad) | 127 | 262 | 62 | 29 | 33
Full dataset | 213 | 453 | 115 | 58 | 57
Table 1. The data collected by the 17 participants during the four weeks of
our online bookmarking study: $|T|$ is the number of distinct tags, $|Y|$ is
the number of tag assignments, $|B|$ is the number of bookmarks, $|MostPop|$
is the number of bookmarks supported by the $MostPop$ algorithm and
$|3Layers|$ is the number of bookmarks supported by the $3Layers$ algorithm.

We constructed a work-integrated bookmarking scenario, in which 17 university
employees from the areas of computer science and psychology have explored a
given topic (i.e., “designing workplaces that inspire people”) for a period of
four weeks. Each participant was assigned the task to collect topic-relevant
resources (i.e., three Web links or documents per week) in the DropBox-like
tool KnowBrain111https://github.com/learning-layers/KnowBrain. Furthermore,
they had to annotate these resources using a tagging interface.

In this tagging interface, the participants were not only asked to provide a
set of tags but also to select from a predefined set of categories (i.e.,
“Gamification & Playfulness”, “Inspiration sources & techniques”,
“Collaboration technologies”, “Personalization services”, “Augmented reality”,
“Interior design”, “Wellbeing & health”, and “Socializing”). These category
selections were then used as semantic context cues for the calculation of tag
recommendations.

To test our hypothesis, the participants were split into two groups, where the
participants in the first group conducted the task individually and the
participants of the second group conducted the task collaboratively. The
collected data for both groups as well as for the full dataset is shown in
Table 1. For details on the study design, please see (Seitlinger et al.,
2017).

(a) Individual tagging setting (narrow) (b) Collaborative tagging setting
(broad) (c) Full dataset (narrow + broad)

Figure 1. User acceptance rates for the two tagging settings (a and b), and
the full dataset (c) measured by Precision and Recall. The results show that
semantic context cues have a higher impact on these metrics in the
collaborative setting than in the individual one.

Tag recommendations. The tagging interface supported the annotation process by
showing 7 tag recommendations to the users, which were either calculated via a
baseline approach (i.e., $MostPop$) or an algorithm, which incorporates
semantic context cues (i.e., $3Layers$). For each bookmark, the recommendation
algorithm was chosen by the system at random.

MostPop. The $MostPop$ algorithm is a simple tag recommendation approach,
which ranks the tags by their overall frequency. Thus, $MostPop$ recommends
the 7 most frequently used tags.

3Layers. 3Layers builds on MINERVA2, which is a parameter-free formalization
of how people make use of context cues (e.g., semantic categories) to (i)
search memory for contextually similar episodes (e.g., of other bookmarks with
similar category combinations), and (ii) access relevant items, such as tags
that have frequently co-varied with these episodes (e.g., popular tags of
similar bookmarks) (Hintzman, 1984). For implementing this context cue-
dependent search process, we realized a simple ranking principle that weighs a
tag’s usage frequency by the extent to which it has co-occurred with
categories that apply to the current resource (see (Seitlinger et al., 2013)).

User acceptance. We measured the user acceptance by means of Precision and
Recall for $k$ = 1 - 7 recommended tags. Hence, for each bookmark, we compared
the set of recommended tags with the set of tags the user has actually used in
the bookmark. Additionally, we report the F1-score for $k$ = 5 (i.e., $F1@5$)
as also used in (Kowald and Lex, 2015).

##  3\. Results

In Figure 1, we present the results of our online study related to the two
tagging settings. Additionally, we present the results for the full dataset in
order to relate our results to previous offline studies.

Individual tagging setting. In the individual setting (plot (a) of Figure 1),
we see overlapping Precision / Recall plot-lines and thus, cannot observe a
significant difference between the user acceptance of $MostPop$ and $3Layers$.
This is in line with the F1-score for $k$ = 5 since $F1@5$ = .309 for
$3Layers$ and $F1@5$ = .302 for $MostPop$ ($p>$ .5)222According to a Wilcoxon
rank-sum significance test.. These results show that semantic context cues
have only a small impact in an individual (i.e., narrow) tagging setting.

Collaborative tagging setting. In the collaborative setting (plot (b) of
Figure 1), we identify a significant advantage of $3Layers$ with $F1@5$ = .418
over $MostPop$ with $F1@5$ = .302 ($p<$ .05). We attribute this to the fact
that in this collaborative setting, $3Layers$ is better able to exploit the
additional information of the semantic context than in the individual tagging
setting. These results mirror our previous work since in (Kowald and Lex,
2016), we showed that the semantic context has a low influence in narrow
folksonomies (i.e, in an individual setting) and a high influence in broad
folksonomies (i.e., in a collaborative setting).

Full dataset. In the full dataset (plot (c) of Figure 1), $3Layers$ with
$F1@5$ = .372 significantly outperforms $MostPop$ with $F1@5$ = .302 ($p<$
.05). This validates our previous results presented in (Seitlinger et al.,
2013), where we showed that $3Layers$ outperforms a context-unaware algorithm
(i.e., Latent Dirichlet Allocation – LDA) in an offline study setting, now
also in an online study setting.

##  4\. Conclusion

In this paper, we presented the results of an online study to identify the
impact of semantic context cues on the user acceptance of tag recommendations.
Based on our stated hypothesis, our two main findings showed (i) that the
impact of semantic context cues greatly depends on the given tagging setting
(i.e, individual vs. collaborative), and (ii) that in a collaborative setting,
a tag recommendation algorithm, which incorporates semantic context cues,
reaches a higher user acceptance than a solely frequency-based algorithm.
These findings are also well in line with the results of previous offline tag
recommendation evaluation studies (Seitlinger et al., 2013; Kowald and Lex,
2016), which are now verified in an online setting. For future work, we plan
to extend our study design by a third tag recommendation algorithm, which
incorporates the temporal context of tag assignments (i.e., $BLL_{AC}$ from
(Kowald and Lex, 2016)). We hypothesize, that this time-aware approach
positively influences the user acceptance of recommendation in individual
tagging settings.

Acknowledgments. This work is funded by the Know-Center, the EU projects
Learning Layers (GA318209) and AFEL (GA687916), and the Austrian Science Fund
(P25593-G22 and P27709-G22).

## References

  * (1)
  * Hintzman (1984) Douglas L Hintzman. 1984\.  MINERVA 2: A simulation model of human memory.  _Behavior Research Methods, Instruments, & Computers_ 16, 2 (1984), 96–101.
  * Jäschke et al. (2009) Robert Jäschke, Folke Eisterlehner, Andreas Hotho, and Gerd Stumme. 2009.  Testing and Evaluating Tag Recommenders in a Live System. In _Proc. of RecSys’09_. ACM, New York, NY, USA, 369–372.
  * Kowald and Lex (2015) Dominik Kowald and Elisabeth Lex. 2015.  Evaluating tag recommender algorithms in real-world folksonomies: A comparative study. In _Proc. of RecSys’15_. ACM, 265–268.
  * Kowald and Lex (2016) Dominik Kowald and Elisabeth Lex. 2016.  The Influence of Frequency, Recency and Semantic Context on the Reuse of Tags in Social Tagging Systems. In _Proc. of HT’16_. ACM, 237–242.
  * Seitlinger et al. (2013) Paul Seitlinger, Dominik Kowald, Christoph Trattner, and Tobias Ley. 2013.  Recommending tags with a model of human categorization. In _Proc. of CIKM’13_. ACM, 2381–2386.
  * Seitlinger et al. (2017) Paul Seitlinger, Tobias Ley, Dominik Kowald, Dieter Theiler, Ilire Hasani-Mavriqi, Sebastian Dennerlein, Elisabeth Lex, and Dietrich Albert. 2017.  Balancing the Fluency-Consistency Tradeoff in Collaborative Information Search with a Recommender Approach.  _International Journal of Human–Computer Interaction_ (2017), 1–19.


MillenniumDB: A Persistent, Open-Source, Graph Database]MillenniumDB: A Persistent, Open-Source, Graph Database

D. Vrgoč]Domagoj Vrgoč

PUC Chile & IMFD

C. Rojas]Carlos Rojas

R. Angles]Renzo Angles

University of Talca & IMFD

Marcelo Arenas

PUC Chile & IMFD

D. Arroyuelo]Diego Arroyuelo

UTFSM Chile & IMFD

C. Buil Aranda]Carlos Buil Aranda

UTFSM Chile & IMFD

A. Hogan]Aidan Hogan

DCC, University of Chile & IMFD

G. Navarro]Gonzalo Navarro

DCC, University of Chile & IMFD

C. Riveros]Cristian Riveros

PUC Chile & IMFD

J. Romero]Juan Romero

PUC Chile & IMFD

In this systems paper, we present MillenniumDB: a novel graph database engine that is modular, persistent, and open source. MillenniumDB is based on a graph data model, which we call domain graphs, that provides a simple abstraction upon which a variety of popular graph models can be supported. The engine itself is founded on a combination of tried and tested techniques from relational data management, state-of-the-art algorithms for worst-case-optimal joins, as well as graph-specific algorithms for evaluating path queries. In this paper, we present the main design principles underlying MillenniumDB, describing the abstract graph model and query semantics supported, the concrete data model and query syntax implemented, as well as the storage, indexing, query planning and query evaluation techniques used. We evaluate MillenniumDB over real-world data and queries from the Wikidata knowledge graph, where we find that it outperforms other popular persistent graph database engines (including both enterprise and open source alternatives) that support similar query features.

§ INTRODUCTION

§ DATA MODEL

§ QUERY LANGUAGE

§ SYSTEM ARCHITECTURE

§ BENCHMARKING

§ CONCLUSIONS AND LOOKING AHEAD

This work was supported by ANID – Millennium Science Initiative Program – Code ICN17_002.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Ali, Saleem, Yao, Hogan, and NgomoAli
et al2021]
authorpersonWaqas Ali, personMuhammad
Saleem, personBin Yao, personAidan Hogan, and
personAxel-Cyrille Ngonga Ngomo.
A Survey of RDF Stores & SPARQL Engines for
Querying Knowledge Graphs.
journalCoRR  volumeabs/2102.13027

[Angles, Arenas, Barceló, Boncz,
Fletcher, Gutiérrez, Lindaaker, Paradies, Plantikow, Sequeda, van Rest,
and VoigtAngles et al2018]
authorpersonRenzo Angles, personMarcelo
Arenas, personPablo Barceló, personPeter A.
Boncz, personGeorge H. L. Fletcher, personClaudio
Gutiérrez, personTobias Lindaaker, personMarcus
Paradies, personStefan Plantikow, personJuan F.
Sequeda, personOskar van Rest, and personHannes
Voigt. year2018.
G-CORE: A Core for Future Graph Query
Languages. In booktitleProceedings of the 2018
International Conference on Management of Data, SIGMOD Conference 2018,
Houston, TX, USA, June 10-15, 2018. pages1421–1432.

[Angles, Arenas, Barceló, Hogan, Reutter,
and VrgocAngles et al2017]
authorpersonRenzo Angles, personMarcelo
Arenas, personPablo Barceló, personAidan
Hogan, personJuan L. Reutter, and personDomagoj
Vrgoc. year2017.
Foundations of Modern Query Languages for Graph
journalACM Comput. Surv. volume50,
number5 (year2017), pages68:1–68:40.

[Angles and GutiérrezAngles and
authorpersonRenzo Angles and personClaudio
Gutiérrez. year2008.
Survey of graph database models.
journalACM Comput. Surv. volume40,
number1 (year2008), pages1:1–1:39.

authorpersonPablo Barceló Baeza.
Querying graph databases. In
booktitleProceedings of the 32nd ACM
SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS
2013, New York, NY, USA - June 22 - 27, 2013. pages175–188.

[Baier, Daroch, Reutter, and VrgocBaier
et al2017]
authorpersonJorge A. Baier, personDietrich
Daroch, personJuan L. Reutter, and personDomagoj
Vrgoc. year2017.
Evaluating Navigational RDF Queries over the
Web. In booktitleProceedings of the 28th ACM Conference
on Hypertext and Social Media, HT 2017, Prague, Czech Republic, July 4-7,
2017. pages165–174.

[Bishop, Kiryakov, Ognyanoff, Peikov, Tashev,
and VelkovBishop et al2011]
authorpersonBarry Bishop, personAtanas
Kiryakov, personDamyan Ognyanoff, personIvan Peikov,
personZdravko Tashev, and personRuslan Velkov.
OWLIM: A family of scalable semantic
journalSemantic Web volume2,
number1 (year2011), pages33–42.

[Bonifati, Martens, and TimmBonifati
et al2020]
authorpersonAngela Bonifati, personWim
Martens, and personThomas Timm.
An analytical study of large SPARQL query logs.
journalVLDB J. volume29,
number2-3 (year2020), pages655–679.

authorpersonRick Cattell.
Scalable SQL and NoSQL data stores.
journalSIGMOD Rec. volume39,
number4 (year2010), pages12–27.

[Cyganiak, Wood, and LanthalerCyganiak
et al2014]
authorpersonRichard Cyganiak, personDavid
Wood, and personMarkus Lanthaler.
titleRDF 1.1 Concepts and Abstract Syntax.
howpublishedW3C Recommendation.

authorpersonOrri Erling.
Virtuoso, a Hybrid RDBMS/Graph Column Store.
journalIEEE Data Eng. Bull.
volume35, number1 (year2012),

authorpersonThe Wikimedia Foundation.
booktitleWikidata:Database download.

[Francis, Green, Guagliardo, Libkin, Lindaaker,
Marsault, Plantikow, Rydberg, Selmer, and TaylorFrancis
et al2018]
authorpersonNadime Francis, personAlastair
Green, personPaolo Guagliardo, personLeonid Libkin,
personTobias Lindaaker, personVictor Marsault,
personStefan Plantikow, personMats Rydberg,
personPetra Selmer, and personAndrés Taylor.
Cypher: An Evolving Query Language for Property
Graphs. In booktitleProceedings of the 2018 International
Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA,
June 10-15, 2018, editorpersonGautam Das,
personChristopher M. Jermaine, and personPhilip A.
Bernstein (Eds.). publisherACM, pages1433–1445.

[Garcia-Molina, Ullman, and
WidomGarcia-Molina et al2009]
authorpersonHector Garcia-Molina,
personJeffrey D. Ullman, and personJennifer Widom.
booktitleDatabase systems - the complete book (2.
publisherPearson Education.

[Harris, Seaborne, and Prud'hommeauxHarris
et al2013]
authorpersonSteve Harris, personAndy
Seaborne, and personEric Prud'hommeaux.
titleSPARQL 1.1 Query Language.
howpublishedW3C Recommendation.

authorpersonOlaf Hartig.
Foundations of RDF\(\star\) and
SPARQL\(\star\) (An Alternative Approach to Statement-Level Metadata in
RDF). In booktitleProceedings of the 11th Alberto
Mendelzon International Workshop on Foundations of Data Management and the
Web, Montevideo, Uruguay, June 7-9, 2017 (seriesCEUR
Workshop Proceedings), editorpersonJuan L. Reutter
and personDivesh Srivastava (Eds.),
Vol. volume1912. publisherCEUR-WS.org.

[Heath and BizerHeath and Bizer2011]
authorpersonTom Heath and personChristian
Bizer. year2011.
booktitleLinked Data: Evolving the Web into a
Global Data Space.
publisherMorgan & Claypool Publishers.

[Hernández, Hogan, and
KrötzschHernández et al2015]
authorpersonDaniel Hernández,
personAidan Hogan, and personMarkus
Krötzsch. year2015.
Reifying RDF: What Works Well With Wikidata?. In
booktitleProceedings of the 11th International Workshop on
Scalable Semantic Web Knowledge Base Systems co-located with 14th
International Semantic Web Conference (ISWC 2015), Bethlehem, PA, USA,
October 11, 2015 (seriesCEUR Workshop Proceedings),
editorpersonThorsten Liebig and
personAchille Fokoue (Eds.), Vol. volume1457.
publisherCEUR-WS.org, pages32–47.

[Hogan, Arenas, Mallea, and PolleresHogan
et al2014]
authorpersonAidan Hogan, personMarcelo
Arenas, personAlejandro Mallea, and personAxel
Polleres. year2014.
Everything you always wanted to know about blank
journalJ. Web Semant.  volume27-28
(year2014), pages42–69.

[Hogan, Blomqvist, Cochez, d'Amato, de Melo,
Gutiérrez, Gayo, Kirrane, Neumaier, Polleres, Navigli, Ngomo, Rashid,
Rula, Schmelzeisen, Sequeda, Staab, and ZimmermannHogan
et al2020]
authorpersonAidan Hogan, personEva
Blomqvist, personMichael Cochez, personClaudia
d'Amato, personGerard de Melo, personClaudio
Gutiérrez, personJosé Emilio Labra Gayo,
personSabrina Kirrane, personSebastian Neumaier,
personAxel Polleres, personRoberto Navigli,
personAxel-Cyrille Ngonga Ngomo, personSabbir M.
Rashid, personAnisa Rula, personLukas Schmelzeisen,
personJuan F. Sequeda, personSteffen Staab, and
personAntoine Zimmermann. year2020.
Knowledge Graphs.
journalCoRR  volumeabs/2003.02320

[Hogan, Riveros, Rojas, and SotoHogan
et al2019]
authorpersonAidan Hogan, personCristian
Riveros, personCarlos Rojas, and personAdrián
Soto. year2019.
A Worst-Case Optimal Join Algorithm for SPARQL.
In booktitleThe Semantic Web - ISWC 2019 - 18th
International Semantic Web Conference, Auckland, New Zealand, October 26-30,
2019, Proceedings, Part I (seriesLecture Notes in
Computer Science), editorpersonChiara Ghidini,
personOlaf Hartig, personMaria Maleshkova,
personVojtech Svátek, personIsabel F. Cruz,
personAidan Hogan, personJie Song,
personMaxime Lefrançois, and personFabien
Gandon (Eds.), Vol. volume11778. publisherSpringer,

[Ilievski, Garijo, Chalupsky, Divvala, Yao,
Rogers, Li, Liu, Singh, Schwabe, and SzekelyIlievski et al2020]
authorpersonFilip Ilievski, personDaniel
Garijo, personHans Chalupsky, personNaren Teja
Divvala, personYixiang Yao, personCraig Milo Rogers,
personRonpeng Li, personJun Liu,
personAmandeep Singh, personDaniel Schwabe, and
personPedro A. Szekely. year2020.
KGTK: A Toolkit for Large Knowledge Graph
Manipulation and Analysis. In booktitleInternational
Semantic Web Conference (ISWC). publisherSpringer,

[Lassila, Schmidt, Bebee, Bechberger, Broekema,
Khandelwal, Lawrence, Sharda, and ThompsonLassila et al2021]
authorpersonOra Lassila, personMichael
Schmidt, personBrad Bebee, personDave Bechberger,
personWillem Broekema, personAnkesh Khandelwal,
personKelvin Lawrence, personRonak Sharda, and
personBryan B. Thompson. year2021.
Graph? Yes! Which one? Help!
journalCoRR  volumeabs/2110.13348

[Malyshev, Krötzsch, González,
Gonsior, and BielefeldtMalyshev et al2018]
authorpersonStanislav Malyshev, personMarkus
Krötzsch, personLarry González,
personJulius Gonsior, and personAdrian Bielefeldt.
Getting the Most Out of Wikidata: Semantic
Technology Usage in Wikipedia's Knowledge Graph. In
booktitleInternational Semantic Web Conference (ISWC).
publisherSpringer, pages376–394.

[Mendelzon and WoodMendelzon and
authorpersonAlberto O. Mendelzon and
personPeter T. Wood. year1989.
Finding Regular Simple Paths in Graph Databases.
In booktitleProceedings of the Fifteenth International
Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The
Netherlands. pages185–193.

[Pérez, Arenas, and
GutiérrezPérez et al2009]
authorpersonJorge Pérez, personMarcelo
Arenas, and personClaudio Gutiérrez.
Semantics and complexity of SPARQL.
journalACM Trans. Database Syst.
volume34, number3 (year2009),

[Ramakrishnan and GehrkeRamakrishnan and
authorpersonRaghu Ramakrishnan and
personJohannes Gehrke. year2000.
booktitleDatabase management systems.

authorpersonMarko A. Rodriguez.
The Gremlin graph traversal machine and language
(invited talk). In booktitleProceedings of the 15th
Symposium on Database Programming Languages, Pittsburgh, PA, USA, October
25-30, 2015, editorpersonJames Cheney and
personThomas Neumann (Eds.). publisherACM,

authorpersonEdward Sciore.
booktitleDatabase Design and Implementation - Second

authorpersonAllegroGraph Team.
titleAllegroGraph 7.1.0 Documentation.

authorpersonArangoDB Team.
titleArangoDB v3.7.11 Documentation.

authorpersonAmazon Neptune Team.
titleWhat Is Amazon Neptune?

authorpersonJanusGraph Team.
titleJanusGraph Documentation, v.0.5.

authorpersonJena Team.
titleTDB Documentation.

authorpersonMillenniumDB Team.
titleMillenniumDB: A Persistent, Opne-Source, Graph
Database [Extended VErsion].

authorpersonMillenniumDB Team.
titleMillenniumDB Source Code.

authorpersonMillenniumDB Team.
titleWikidata Benchmark.

authorpersonOrientDB Team.
titleOrientDB Manual – version 3.0.34.

authorpersonStardog Team.
titleStardog 7.6.3 Documentation.

authorpersonTigerGraph Team.
titleTigerGraph Documentation – version 3.1.

[Thompson, Personick, and CutcherThompson
et al2014]
authorpersonBryan B. Thompson, personMike
Personick, and personMartyn Cutcher.
The Bigdata® RDF Graph
In booktitleLinked Data Management,
editorpersonAndreas Harth, personKatja
Hose, and personRalf Schenkel (Eds.).
publisherChapman and Hall/CRC, pages193–237.

authorpersonTodd L. Veldhuizen.
Triejoin: A Simple, Worst-Case Optimal Join
Algorithm. In booktitleProc. 17th International Conference
on Database Theory (ICDT), Athens, Greece, March 24-28, 2014.

[Vrandecic and KrötzschVrandecic and
authorpersonDenny Vrandecic and
personMarkus Krötzsch. year2014.
Wikidata: a free collaborative knowledgebase.
journalCommun. ACM volume57,
number10 (year2014), pages78–85.

authorpersonJim Webber.
A programmatic introduction to Neo4j. In
booktitleConference on Systems, Programming, and
Applications: Software for Humanity, SPLASH '12, Tucson, AZ, USA, October
21-25, 2012, editorpersonGary T. Leavens (Ed.).
publisherACM, pages217–218.

[Yu and OzsoyogluYu and Ozsoyoglu1979]
authorpersonC. T. Yu and personM. Z.
Ozsoyoglu. year1979.
An algorithm for tree-query membership of a
distributed query. In booktitleThe IEEE Computer
Society's Third International Computer Software and Applications Conference,
COMPSAC 1979, 6-8 November, 1979, Chicago, Illinois, USA.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Ali, Saleem, Yao, Hogan, and NgomoAli
et al2021]
authorpersonWaqas Ali, personMuhammad
Saleem, personBin Yao, personAidan Hogan, and
personAxel-Cyrille Ngonga Ngomo.
A Survey of RDF Stores & SPARQL Engines for
Querying Knowledge Graphs.
journalCoRR  volumeabs/2102.13027

[Angles, Arenas, Barceló, Boncz,
Fletcher, Gutiérrez, Lindaaker, Paradies, Plantikow, Sequeda, van Rest,
and VoigtAngles et al2018]
authorpersonRenzo Angles, personMarcelo
Arenas, personPablo Barceló, personPeter A.
Boncz, personGeorge H. L. Fletcher, personClaudio
Gutiérrez, personTobias Lindaaker, personMarcus
Paradies, personStefan Plantikow, personJuan F.
Sequeda, personOskar van Rest, and personHannes
Voigt. year2018.
G-CORE: A Core for Future Graph Query
Languages. In booktitleProceedings of the 2018
International Conference on Management of Data, SIGMOD Conference 2018,
Houston, TX, USA, June 10-15, 2018. pages1421–1432.

[Angles, Arenas, Barceló, Hogan, Reutter,
and VrgocAngles et al2017]
authorpersonRenzo Angles, personMarcelo
Arenas, personPablo Barceló, personAidan
Hogan, personJuan L. Reutter, and personDomagoj
Vrgoc. year2017.
Foundations of Modern Query Languages for Graph
journalACM Comput. Surv. volume50,
number5 (year2017), pages68:1–68:40.

[Angles and GutiérrezAngles and
authorpersonRenzo Angles and personClaudio
Gutiérrez. year2008.
Survey of graph database models.
journalACM Comput. Surv. volume40,
number1 (year2008), pages1:1–1:39.

authorpersonPablo Barceló Baeza.
Querying graph databases. In
booktitleProceedings of the 32nd ACM
SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS
2013, New York, NY, USA - June 22 - 27, 2013. pages175–188.

[Baier, Daroch, Reutter, and VrgocBaier
et al2017]
authorpersonJorge A. Baier, personDietrich
Daroch, personJuan L. Reutter, and personDomagoj
Vrgoc. year2017.
Evaluating Navigational RDF Queries over the
Web. In booktitleProceedings of the 28th ACM Conference
on Hypertext and Social Media, HT 2017, Prague, Czech Republic, July 4-7,
2017. pages165–174.

[Bishop, Kiryakov, Ognyanoff, Peikov, Tashev,
and VelkovBishop et al2011]
authorpersonBarry Bishop, personAtanas
Kiryakov, personDamyan Ognyanoff, personIvan Peikov,
personZdravko Tashev, and personRuslan Velkov.
OWLIM: A family of scalable semantic
journalSemantic Web volume2,
number1 (year2011), pages33–42.

[Bonifati, Martens, and TimmBonifati
et al2020]
authorpersonAngela Bonifati, personWim
Martens, and personThomas Timm.
An analytical study of large SPARQL query logs.
journalVLDB J. volume29,
number2-3 (year2020), pages655–679.

authorpersonRick Cattell.
Scalable SQL and NoSQL data stores.
journalSIGMOD Rec. volume39,
number4 (year2010), pages12–27.

[Cyganiak, Wood, and LanthalerCyganiak
et al2014]
authorpersonRichard Cyganiak, personDavid
Wood, and personMarkus Lanthaler.
titleRDF 1.1 Concepts and Abstract Syntax.
howpublishedW3C Recommendation.

authorpersonOrri Erling.
Virtuoso, a Hybrid RDBMS/Graph Column Store.
journalIEEE Data Eng. Bull.
volume35, number1 (year2012),

authorpersonThe Wikimedia Foundation.
booktitleWikidata:Database download.

[Francis, Green, Guagliardo, Libkin, Lindaaker,
Marsault, Plantikow, Rydberg, Selmer, and TaylorFrancis
et al2018]
authorpersonNadime Francis, personAlastair
Green, personPaolo Guagliardo, personLeonid Libkin,
personTobias Lindaaker, personVictor Marsault,
personStefan Plantikow, personMats Rydberg,
personPetra Selmer, and personAndrés Taylor.
Cypher: An Evolving Query Language for Property
Graphs. In booktitleProceedings of the 2018 International
Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA,
June 10-15, 2018, editorpersonGautam Das,
personChristopher M. Jermaine, and personPhilip A.
Bernstein (Eds.). publisherACM, pages1433–1445.

[Garcia-Molina, Ullman, and
WidomGarcia-Molina et al2009]
authorpersonHector Garcia-Molina,
personJeffrey D. Ullman, and personJennifer Widom.
booktitleDatabase systems - the complete book (2.
publisherPearson Education.

[Harris, Seaborne, and Prud'hommeauxHarris
et al2013]
authorpersonSteve Harris, personAndy
Seaborne, and personEric Prud'hommeaux.
titleSPARQL 1.1 Query Language.
howpublishedW3C Recommendation.

authorpersonOlaf Hartig.
Foundations of RDF\(\star\) and
SPARQL\(\star\) (An Alternative Approach to Statement-Level Metadata in
RDF). In booktitleProceedings of the 11th Alberto
Mendelzon International Workshop on Foundations of Data Management and the
Web, Montevideo, Uruguay, June 7-9, 2017 (seriesCEUR
Workshop Proceedings), editorpersonJuan L. Reutter
and personDivesh Srivastava (Eds.),
Vol. volume1912. publisherCEUR-WS.org.

[Heath and BizerHeath and Bizer2011]
authorpersonTom Heath and personChristian
Bizer. year2011.
booktitleLinked Data: Evolving the Web into a
Global Data Space.
publisherMorgan & Claypool Publishers.

[Hernández, Hogan, and
KrötzschHernández et al2015]
authorpersonDaniel Hernández,
personAidan Hogan, and personMarkus
Krötzsch. year2015.
Reifying RDF: What Works Well With Wikidata?. In
booktitleProceedings of the 11th International Workshop on
Scalable Semantic Web Knowledge Base Systems co-located with 14th
International Semantic Web Conference (ISWC 2015), Bethlehem, PA, USA,
October 11, 2015 (seriesCEUR Workshop Proceedings),
editorpersonThorsten Liebig and
personAchille Fokoue (Eds.), Vol. volume1457.
publisherCEUR-WS.org, pages32–47.

[Hogan, Arenas, Mallea, and PolleresHogan
et al2014]
authorpersonAidan Hogan, personMarcelo
Arenas, personAlejandro Mallea, and personAxel
Polleres. year2014.
Everything you always wanted to know about blank
journalJ. Web Semant.  volume27-28
(year2014), pages42–69.

[Hogan, Blomqvist, Cochez, d'Amato, de Melo,
Gutiérrez, Gayo, Kirrane, Neumaier, Polleres, Navigli, Ngomo, Rashid,
Rula, Schmelzeisen, Sequeda, Staab, and ZimmermannHogan
et al2020]
authorpersonAidan Hogan, personEva
Blomqvist, personMichael Cochez, personClaudia
d'Amato, personGerard de Melo, personClaudio
Gutiérrez, personJosé Emilio Labra Gayo,
personSabrina Kirrane, personSebastian Neumaier,
personAxel Polleres, personRoberto Navigli,
personAxel-Cyrille Ngonga Ngomo, personSabbir M.
Rashid, personAnisa Rula, personLukas Schmelzeisen,
personJuan F. Sequeda, personSteffen Staab, and
personAntoine Zimmermann. year2020.
Knowledge Graphs.
journalCoRR  volumeabs/2003.02320

[Hogan, Riveros, Rojas, and SotoHogan
et al2019]
authorpersonAidan Hogan, personCristian
Riveros, personCarlos Rojas, and personAdrián
Soto. year2019.
A Worst-Case Optimal Join Algorithm for SPARQL.
In booktitleThe Semantic Web - ISWC 2019 - 18th
International Semantic Web Conference, Auckland, New Zealand, October 26-30,
2019, Proceedings, Part I (seriesLecture Notes in
Computer Science), editorpersonChiara Ghidini,
personOlaf Hartig, personMaria Maleshkova,
personVojtech Svátek, personIsabel F. Cruz,
personAidan Hogan, personJie Song,
personMaxime Lefrançois, and personFabien
Gandon (Eds.), Vol. volume11778. publisherSpringer,

[Ilievski, Garijo, Chalupsky, Divvala, Yao,
Rogers, Li, Liu, Singh, Schwabe, and SzekelyIlievski et al2020]
authorpersonFilip Ilievski, personDaniel
Garijo, personHans Chalupsky, personNaren Teja
Divvala, personYixiang Yao, personCraig Milo Rogers,
personRonpeng Li, personJun Liu,
personAmandeep Singh, personDaniel Schwabe, and
personPedro A. Szekely. year2020.
KGTK: A Toolkit for Large Knowledge Graph
Manipulation and Analysis. In booktitleInternational
Semantic Web Conference (ISWC). publisherSpringer,

[Lassila, Schmidt, Bebee, Bechberger, Broekema,
Khandelwal, Lawrence, Sharda, and ThompsonLassila et al2021]
authorpersonOra Lassila, personMichael
Schmidt, personBrad Bebee, personDave Bechberger,
personWillem Broekema, personAnkesh Khandelwal,
personKelvin Lawrence, personRonak Sharda, and
personBryan B. Thompson. year2021.
Graph? Yes! Which one? Help!
journalCoRR  volumeabs/2110.13348

[Malyshev, Krötzsch, González,
Gonsior, and BielefeldtMalyshev et al2018]
authorpersonStanislav Malyshev, personMarkus
Krötzsch, personLarry González,
personJulius Gonsior, and personAdrian Bielefeldt.
Getting the Most Out of Wikidata: Semantic
Technology Usage in Wikipedia's Knowledge Graph. In
booktitleInternational Semantic Web Conference (ISWC).
publisherSpringer, pages376–394.

[Mendelzon and WoodMendelzon and
authorpersonAlberto O. Mendelzon and
personPeter T. Wood. year1989.
Finding Regular Simple Paths in Graph Databases.
In booktitleProceedings of the Fifteenth International
Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The
Netherlands. pages185–193.

[Pérez, Arenas, and
GutiérrezPérez et al2009]
authorpersonJorge Pérez, personMarcelo
Arenas, and personClaudio Gutiérrez.
Semantics and complexity of SPARQL.
journalACM Trans. Database Syst.
volume34, number3 (year2009),

[Ramakrishnan and GehrkeRamakrishnan and
authorpersonRaghu Ramakrishnan and
personJohannes Gehrke. year2000.
booktitleDatabase management systems.

authorpersonMarko A. Rodriguez.
The Gremlin graph traversal machine and language
(invited talk). In booktitleProceedings of the 15th
Symposium on Database Programming Languages, Pittsburgh, PA, USA, October
25-30, 2015, editorpersonJames Cheney and
personThomas Neumann (Eds.). publisherACM,

authorpersonEdward Sciore.
booktitleDatabase Design and Implementation - Second

authorpersonAllegroGraph Team.
titleAllegroGraph 7.1.0 Documentation.

authorpersonArangoDB Team.
titleArangoDB v3.7.11 Documentation.

authorpersonAmazon Neptune Team.
titleWhat Is Amazon Neptune?

authorpersonJanusGraph Team.
titleJanusGraph Documentation, v.0.5.

authorpersonJena Team.
titleTDB Documentation.

authorpersonMillenniumDB Team.
titleMillenniumDB: A Persistent, Opne-Source, Graph
Database [Extended VErsion].

authorpersonMillenniumDB Team.
titleMillenniumDB Source Code.

authorpersonMillenniumDB Team.
titleWikidata Benchmark.

authorpersonOrientDB Team.
titleOrientDB Manual – version 3.0.34.

authorpersonStardog Team.
titleStardog 7.6.3 Documentation.

authorpersonTigerGraph Team.
titleTigerGraph Documentation – version 3.1.

[Thompson, Personick, and CutcherThompson
et al2014]
authorpersonBryan B. Thompson, personMike
Personick, and personMartyn Cutcher.
The Bigdata® RDF Graph
In booktitleLinked Data Management,
editorpersonAndreas Harth, personKatja
Hose, and personRalf Schenkel (Eds.).
publisherChapman and Hall/CRC, pages193–237.

authorpersonTodd L. Veldhuizen.
Triejoin: A Simple, Worst-Case Optimal Join
Algorithm. In booktitleProc. 17th International Conference
on Database Theory (ICDT), Athens, Greece, March 24-28, 2014.

[Vrandecic and KrötzschVrandecic and
authorpersonDenny Vrandecic and
personMarkus Krötzsch. year2014.
Wikidata: a free collaborative knowledgebase.
journalCommun. ACM volume57,
number10 (year2014), pages78–85.

authorpersonJim Webber.
A programmatic introduction to Neo4j. In
booktitleConference on Systems, Programming, and
Applications: Software for Humanity, SPLASH '12, Tucson, AZ, USA, October
21-25, 2012, editorpersonGary T. Leavens (Ed.).
publisherACM, pages217–218.

[Yu and OzsoyogluYu and Ozsoyoglu1979]
authorpersonC. T. Yu and personM. Z.
Ozsoyoglu. year1979.
An algorithm for tree-query membership of a
distributed query. In booktitleThe IEEE Computer
Society's Third International Computer Software and Applications Conference,
COMPSAC 1979, 6-8 November, 1979, Chicago, Illinois, USA.

§ APPENDIX

§ SYNTAX OF MILLENNIUMDB QUERIES

§ FORMAL DEFINITION OF DOMAIN GRAPH QUERIES