State-free End-to-End Encrypted Storage and Chat Systems based on

Searchable Encryption

Keita Emura

1 a

, Ryoma Ito

1 b

, Sachiko Kanamori

, Ryo Nojima

and Yohei Watanabe

1,2 c

National Institute of Information and Communications Technology, Japan

The University of Electro-Communications, Japan

Keywords:

Dynamic Searchable Symmetric Encryption, State-free, Secure Storage and Chat Systems.

Abstract:

Searchable symmetric encryption (SSE) has attracted signiﬁcant attention because it can prevent data leakage

from external devices, e.g., on clouds. SSE appears to be effective to construct such a secure system; however,

it is not trivial to construct such a system from SSE in practice because other parts must be designed, e.g., user

do not have public key certiﬁcates. In this paper, we describe the implementation of two systems based upon

the state-free dynamic SSE (DSSE) (Watanabe et al., ePrint 2021), i.e., a secure storage system (for a single

user) and a chat system (for multiple users). In addition to the Watanabe et al. DSSE protocol, we employ a

secure multipath key exchange (SMKEX) protocol (Costea et al., CCS 2018), which is secure against some

classes of unsynchronized active attackers. It allows the chat system users without certiﬁcates to share a secret

key of the DSSE protocol in a secure manner. To realize end-to-end encryption, the shared key must be kept

secret; thus, we must consider how to preserve the secret on, for example, a user’s local device. However, this

requires additional security assumptions, e.g., tamper resistance, and it seems difﬁcult to assume that all users

have such devices. Thus, we propose a secure key agreement protocol by combining the SMKEX and login

information (password) that does not require an additional tamper-resistant device. Combining the proposed

key agreement protocol and the underlying state-free DSSE protocol allow users who know the password to

use the systems on multiple devices.

1 INTRODUCTION

1.1 Searchable Symmetric Encryption

Searchable symmetric encryption (SSE) (Curtmola

et al., 2006; Song et al., 2000) provides search func-

tionality against encrypted documents, and dynamic

SSE (DSSE) (Bost, 2016; Bost et al., 2017; Cash

et al., 2014; Etemad et al., 2018; Chamani et al., 2018;

Kamara and Papamanthou, 2013; Kamara et al., 2012;

Kim et al., 2017; Lai and Chow, 2017; Miers and

Mohassel, 2017; Naveed et al., 2014; Stefanov et al.,

2014; Sun et al., 2018; Yoneyama and Kimura, 2017;

Shibata and Yoneyama, 2021; Watanabe et al., 2021)

allows us to update encrypted databases. For exam-

ple, in practical applications, when encrypted stor-

age is constructed, the database is updated frequently;

thus, DSSE is employed. As a fundamental security

of DSSE, Stefanov et al. (Stefanov et al., 2014) de-

https://orcid.org/0000-0002-8969-3581

https://orcid.org/0000-0002-4929-8974

https://orcid.org/0000-0003-4028-8603

ﬁned forward privacy, which guarantees that even if

some data are added, information about whether the

data contain keywords that have been searched previ-

ously is not revealed.

DSSE prevents data leakage from external stor-

ages, e.g., on clouds, because all stored data are en-

crypted. Such a DSSE-based storage system is de-

scribed as follows. A user selects a key k that is

kept secret, and an identiﬁer id is associated with

each ﬁle f

. Here, assume that no information of

is revealed from id. A storage server manages an

encrypted database that comprises the pair (id,c

where c

is the ciphertext of f

. Let W

be a set of

keywords of ﬁle f

with identiﬁer id. The user com-

putes a search query using k, a keyword to be searched

ω ∈ W

, and the state information. The user sends

the query to the server, and then obtains c

in which

the corresponding f

(i.e., the decryption result of c

using k) contains ω. No information of ω is revealed

from the query. More precisely, a leakage function is

deﬁned, and no information of ω is revealed besides

this function. Finally, the user obtains f

by decrypt-

ing c

using k.

106

Emura, K., Ito, R., Kanamori, S., Nojima, R. and Watanabe, Y.

State-free End-to-End Encrypted Storage and Chat Systems based on Searchable Encryption.

DOI: 10.5220/0011045200003179

In Proceedings of the 24th International Conference on Enterprise Information Systems (ICEIS 2022) - Volume 2, pages 106-113

ISBN: 978-989-758-569-2; ISSN: 2184-4992

A secure storage system can be constructed eas-

ily from DSSE; however, many issues must be con-

sidered if such a system is launched in practice. For

example, a set of keywords W

, which is assumed to

be given in advance in DSSE, must be deﬁned. Al-

though a promising approach is to employ a morpho-

logical analysis tool, this approach introduces other

issues, e.g., selecting the most appropriate tool. In

addition, in a storage system, an independent area is

assigned to each user; thus, authentication and the

user login process must also be considered. More-

over, DSSE attempts to prevent information leakage

against the server; thus, we must also consider cases

where search queries sent from users are modiﬁed in

the communication channel. We must also consider

the case where multiple users share a key, e.g., a se-

cure chat system, where the ciphertexts of chat history

are preserved on the server, each user can search chat

messages owing to DSSE, and each user reads them

in a plaintext manner by locally decrypting the cipher-

texts. Here, we must consider how to share a secret

key among multiple users, and, if the state informa-

tion (which is updated periodically and used to gen-

erate search queries) must be managed, then it must

also be shared among users, which represents an ad-

ditional synchronization problem. Note that users do

not possess public key certiﬁcates in many cases, e.g.,

smartphones; thus, man-in-the-middle attacks can be

made by an active adversary that controls the commu-

nication channel among users. In summary, it would

be beneﬁcial to address these issues (in addition to

DSSE) in secure systems.

1.2 Our Contribution

In this paper, we implement two systems based

upon the DSSE scheme proposed by Watanabe et

al. (Watanabe et al., 2021), i.e., a secure storage sys-

tem (for a single user) and a chat system (for multiple

users). Watanabe’s DSSE protocol is state-free, which

means that if a user knows a (stateless) secret key,

then no other state information is required. This al-

lows us to consider multiple users easily, and we only

need to handle key agreement. In other words, we

do not have to consider the synchronization of state

information.

By combining a key agreement proto-

col (which is explained later) and the Watanabe DSSE

protocol, these two systems are state-free; thus, the

user can use the systems via a web browser (without

considering devices) if they know the appropriate lo-

gin information (i.e., the user ID and password).

To the best of our knowledge, Watanabe’s DSSE proto-

col is the ﬁrst state-free construction with forward privacy;

thus, we employed this protocol in this paper.

Security Model. In our system, we prepared two

(semi-honest) servers, i.e., an authentication server

(to manage login information) and an application

server (that preserves encrypted data and responds to

the users’ search queries). We considered a realistic

situation where two servers have public key certiﬁ-

cates via a public key infrastructure (PKI), and the

users do not have certiﬁcates. Here, we pursue end-

to-end encryption (E2EE), i.e., only the correspond-

ing users have a secret key, and no server can observe

the plaintext data (even two servers collude with each

other). Thus, we considered a relaxed security model,

i.e., unsynchronized active adversaries, presented by

Costea et al. (Costea et al., 2018). Costea et al. pro-

posed the secure multipath key exchange (SMKEX)

protocol, which is secure against unsynchronized ac-

tive adversaries. The SMKEX protocol allows chat

users to share a secret key without assuming a PKI.

Our Key Agreement Protocol. To realize E2EE, the

shared key must be kept secret; thus, we must con-

sider how to preserve key secrecy on, for example, a

local user device. However, this requires additional

security assumptions, e.g., tamper resistance, and it

seems difﬁcult to assume that all users have such a

device, as in certiﬁcates. In addition, it would be

beneﬁcial to access the systems via multiple devices

without synchronization; thus, we propose a secure

key agreement protocol that combines the SMKEX

protocol and login information (password). The pro-

posed secure key agreement protocol does not require

additional (tamper-resistant) devices. Here, a DSSE

secret key is deﬁned by the password and a random

value preserved in the application server. Then, when

a user logs into the system, they obtain the random

and compute the DSSE secret key locally. Although

this is similar to password-based authenticated key

exchange (PAKE) (Katz et al., 2001), no secret value

shared in advance is required in the proposed protocol

(under relaxed security). By combining the key man-

agement protocol and Watanabe’s state-free DSSE

protocol, users can access the systems on multiple de-

vices, and state-free E2EE storage and chat systems

can be constructed.

Concierge Functionality. We also consider the ex-

plainability of the system. Typically, general users

are not aware SSE; thus, such secure systems should

be used without recognizing the underlying crypto-

graphic tools. Even for general users, it is highly

desirable to easily explain how data are encrypted,

how encrypted data are preserved on external stor-

age devices, and so on. Thus, we also implemented

a concierge functionality where DSSE-related data

processing can be viewed. In the storage system

(concierge mode), the encrypted ﬁle names and the

State-free End-to-End Encrypted Storage and Chat Systems based on Searchable Encryption

107

corresponding ciphertexts are displayed. In addi-

tion, when a keyword is searched, the correspond-

ing trapdoor is displayed. These show the application

server’s point of view. The chat system also supports

concierge mode. Due to the page limitation, we omit

showing the functionality and see our preprint version

for details (Emura et al., 2021).

1.3 Related Work

CryptDB (Popa et al., 2015; Popa et al., 2011; Popa

et al., 2012) is a popular encrypted database system

in which SQL queries are executed on encrypted data.

As discussed in the literature (Popa et al., 2014), the

application server obtains access to the unencrypted

data and receives each user’s key when a user logs

in. In this sense, it is not an E2EE system. Popa

et al. (Popa et al., 2014) proposed Mylar, which is

a platform to build web applications using a multi-

key DSSE protocol (Popa and Zeldovich, 2013). They

also published the kChat chat service, which is based

on Mylar. Although they insisted that Mylar protects

data conﬁdentiality against attackers who have full ac-

cess to the servers, Grubbs et al. (Grubbs et al., 2016)

demonstrated that Mylar is vulnerable against active

adversarial servers that modify the encryption algo-

rithm. Here, we assume that the two servers in our

systems are semi-honest; thus, Mylar might be em-

ployed. However, this is not dynamic and requires

paring groups; thus, we employ Watanabe’s DSSE

protocol.

Chen et al. proposed password-authenticated

searchable encryption (PASE) (Chen et al., 2021). As

in our protocol, a password can be used to outsource

encrypted data and can be used for keyword search.

Moreover, they also employed two server model, and

as in our protocol, no single server can mount an of-

ﬂine attack on the user’s password. Unlike to our

protocol, PASE does not consider multiple users who

have own password respectively but share a common

encrypted data.

Secure messaging protocols have been widely re-

searched, e.g., Signal and WhatsApp. Unlike to our

E2EE systems, they do not consider the search func-

tionality over encrypted data. Crypto-chat (cry) was

established for secure messaging, where users share

passwords, and encrypted messages are decrypted on

the device only. To the best of our knowledge, no

search functionality against encrypted data is sup-

ported.

2 PRELIMINARIES

2.1 Watanabe et al. DSSE

In this section, we introduce the Watanabe DSSE pro-

tocol (Watanabe et al., 2021). Let π = {π

: {0,1}

∗

→

{0,1}

λ+`

}

k∈{0,1}

be a variable input-length pseudo-

random function, where λ is the keyword length, ` is

the identity length, and κ is the key length, which are

all polynomial of the security parameter. Typically,

the DSSE protocol does not explicitly consider data

encryption; however, here we consider it explicitly

because the search result is a ciphertext in the storage

and chat systems.

Setup: A user selects a secret key k ∈ {0,1}

. For

the simplicity, we assume that k is also used for

data encryption.

Update: When data are preserved on the server, the

user computes π

(ω,id) for all ω ∈ W

. Here,

is a set of keywords in the ﬁle f

with the

identiﬁer id. The set of identiﬁers I is considered

to be the state information, which is updated pe-

riodically according to the current database. The

user encrypts f

using k and sends id, π

(ω,id),

and the ciphertext c

to the server. Then, the

server preserves (id, c

) on the address π

(ω,id).

When data are removed, the user sends the id of

the removed data to the server, and the server re-

moves (id, c

Search: If the user searches ﬁles containing keyword

ω, the user computes a trapdoor π

(ω,id) for all

id ∈ I and sends a search query {π

(ω,id)}

id∈I

The server sends (id,c

) preserved on the address

(ω,id). Finally, the user decrypts c

using k

and obtains f

In the Watanabe DSSE protocol, the server is

modeled as semi-honest, i.e., it always follows the

protocol procedure but may extract information. As-

sume that id does not reveal any information of f

Then state information I = {id} can be publicly avail-

able, and simply the server preserves I and sends it to

the user before the user searches. The server knows

ciphertexts c

and pseudorandom numbers π

(ω,id).

Moreover, queries {π

(ω,id)}

id∈I

are computed for

the current database. Thus, the Watanabe DSSE pro-

tocol supports forward privacy and is state-free.

2.2 SMKEX and Unsynchronized

Adversaries

In this section, we introduce SMKEX proposed by

Costea et al. (Costea et al., 2018) and its security

ICEIS 2022 - 24th International Conference on Enterprise Information Systems

108

model. In the two adversaries case which we also

employed, unsynchronized adversaries are deﬁned as

follows:

Deﬁnition 1 (Costea et al., 2018). Two adversaries

X1 and X2 are said to be unsynchronized (writ-

ten X1/X2) if they can only exchange messages

before the start and after the end of a speciﬁc pro-

tocol session.

For example, let two active adversaries be considered

and two paths be prepared. Then, one active adversary

can observe and modify data on the ﬁrst path, and the

other active adversary can also observe and modify

the data on the second path; however, these adver-

saries cannot communicate with each other. Costea et

al. proposed the SMKEX protocol, which is secure

against the adversaries.

The SMKEX protocol is described as follows.

Essentially, it is a simple Difﬁe-Hellman (DH)-type

key exchange with an additional conﬁrmation phase.

Here, let G be a group with prime order p and let

g ∈ G be a generator. Two users, i.e., Alice and

Bob, would like to share a key. Then, Alice (resp.

Bob) selects x

←− Z

(resp. y

←− Z

) and computes

(resp. g

). Note that g

and g

are not long-

lived keys, and they need to choose them for each

key exchange. Through Path 1, Alice sends g

Bob, and Bob sends g

to Alice. Note that these

values may be modiﬁed because the adversary is ac-

tive. Alice further selects a nonce N

and sends it to

Bob in Path 2. Then, Bob selects a nonce N

, com-

putes hsess = Hash(N

), and sends N

and

hsess to Alice in Path 2. Alice then checks whether

hsess = Hash(N

) holds. Since the adver-

saries are unsynchronized, even if one adversary ob-

serves g

in Path 1, the adversary cannot compute

Hash(N

) and send it to Alice in Path 2.

Here, the actual shared key (application trafﬁc key

atk) is computed according to RFC5869 (Krawczyk

and Eronen, ), where a negotiated secret string is com-

puted from the DH key g

with a 0 seed via HKDF-

extract, and atk is the HKDF-expand value of the

string.

3 PROPOSED SYSTEMS

In this section, we present our storage and chat sys-

tems.

3.1 Common Part

DSSE Library. We implemented our DSSE library

in the C programming language. Here, we deﬁned the

APIs by following the DSSE syntax (Setup,Update,

Search). When data are added, a trapdoor is com-

puted for the data. In addition, when data are re-

moved, the user sends the corresponding id, and the

server removes (id,c

). In other words, no cryp-

tographic operations are required. Thus, we imple-

mented the Add API as Update and did not imple-

ment the Delete API in the library. We employed

OpenSSL (1.1.1h) to select k randomly, and HMAC-

SHA256 as π

We also employed the WebCrypto

API, which is a JavaScript API, to implement the en-

cryption functionality as a web application. For en-

cryption, pseudo-randomness against chosen plain-

text attack (PCPA) security (Curtmola et al., 2006)

is required.

Thus, we employed AES-CTR with a

256-bit key. In addition, we employed MeCab (MeC)

as the underlying morphological analysis tool. Note

that we used the wasm MeCab library (v 0.996; ipadic

dictionary).

After executing the morphological anal-

ysis tool, trapdoors are generated using the Add API.

To the best of our knowledge, “pneumonoultramicro-

scopicsilicovolcanokoniosis” (containing 45 charac-

ters) is the longest English word; thus, we set λ = 45.

System Architecture. We prepared an authentication

server to manage user login information and applica-

tion server to preserve the encrypted data and respond

to the users’ search queries. A user can use the DSSE

library via a web browser (WebAssembly). In this

implementation, we employed Amazon Elastic Com-

pute Cloud (Amazon EC2)

and assumed that the two

servers have public key certiﬁcates. We also assumed

that the communication channel between the user and

the application server is secured via transport layer

security (TLS). The system architecture is shown in

Fig. 1

interface is common to both systems, and the user se-

lects the storage or chat system. Here, we employed a

simple login system, where each user has a username

uname and password pw. The authentication server

preserves Hash(pw) with uname, and the user sends

(uname,Hash(pw)) via TLS to the server. The gener-

The Watanabe DSSE protocol requires that (1)

(ω,id) is pseudorandom and (2) the probability that a

probabilistic polynomial-time adversary ﬁnds two distinct

inputs (ω,id) 6= (ω

,id

) where π

(ω,id) = π

(ω

,id

) holds

is negligible for the security parameter. Thus, we employed

HMAC-SHA256 in our implementation.

The reason behind is that the simulator just responds a

random value in the security proof. Thus, a standard CPA

security is also enough owing to the indistinguishability of

ciphertext of 0.

https://github.com/fasiha/mecab-emscripten

https://aws.amazon.com/jp/ec2/

State-free End-to-End Encrypted Storage and Chat Systems based on Searchable Encryption

109

DXWK'%

DSS'%

:HE%URZVHU

'66(/LEUDU\ 

([SHULPHQW6\VWHP

Figure 1: System Architecture.

ation of the DSSE secret key k is explained later. The

application server preserves (id,c

) as mentioned in

Watanabe’s DSSE protocol. Here, id is generated

by the universally unique identiﬁer (UUID) version

4 (Leach et al., 2005). It does not take ﬁle informa-

tion as input; therefore, the requirement is satisﬁed,

i.e., id does not reveal any information of f

. The

application server also preserves the state information

I = {id} for each user.

3.2 Our Storage System

In this section, we give our storage system.

DSSE Key Generation. A user generates a DSSE

key k as follows. First, the user selects a random value

R ∈ {0,1}

, where κ is the security parameter, and

we set κ = 256. In the user registration phase, the

user selects two different passwords. From a usabil-

ity and practicality perspective, we assume that the

user selects one password PW, and the system sep-

arates it such as PW = pw||pw

The user sends R

and (uname,Hash(pw)) via TLS to the authentica-

tion server, and the server preserves R in addition to

(uname,Hash(pw)) where Hash is SHA256.

Then,

a DSSE secret key is deﬁned as

k = R ⊕ Hash(pw

)

E.g., the ﬁrst half and the second half, or more

generally, PW is divided into pw||pw

where |pw| =

ﬂoor(|PW|/2) and |pw

| = ceiling(|PW|/2).

We can employ some zero-knowledge proof system

to demonstrate that the user actually knows pw, e.g., zk-

SNARK (Groth, 2016). Here, the communication channel

is secure (TLS), and there is no intermediate adversary that

can observe or modify Hash(pw); thus, we did not further

consider it in this implementation. However, the system can

be extended easily in this sense.

where ⊕ is a bitwise exclusive OR. In the login phase,

the user sends uname and Hash(pw) to the application

server via TLS, and the server returns R if Hash(pw)

is preserved with uname. This structure allows the

user to generate the DSSE secret key k without re-

quiring additional information (besides uname, pw,

and pw

). Brieﬂy, R is random, and no information

of k is revealed from R. Even if the authentication

server recovers pw from Hash(pw) via an ofﬂine dic-

tionary attack, no information of k is revealed because

is only used locally by the user. As a potential at-

tack, if the authentication server obtains a ciphertext

, then the server performs an ofﬂine dictionary at-

tack where choose pw

, compute k = R ⊕ Hash(pw

and check whether the decryption result of c

using

k is meaningful, e.g., whether a readable ﬁle is recov-

ered or not. Note that c

is sent from the user to the

application server via TLS, which means that the au-

thentication server does not perform this attack unless

the authentication and application servers collude.

Secure Storage. When the user stores a ﬁle on the

application server, the ﬁle is encrypted automatically.

When a user downloads a ﬁle to the application server,

the ﬁle is decrypted automatically. Although the ﬁle

names are encrypted, they are also decrypted auto-

matically and displayed as usual. Thus, users are not

required to aware DSSE.

3.3 Our Chat System

Here, we describe the chat system. The main differ-

ence from the storage system is the preparation of a

random value R for each room in the chat system. In

addition, a DSSE key is shared to users belonging to

the room. Here, we assume that Alice creates a room

and invites Bob to the room, and then both Alice and

Bob are registered in the system (i.e., they have their

own storage). Let pw

and pw

(pw

and pw

) be Al-

ice’s (Bob’s) two passwords. We assume that there are

two different communication paths as in the SMKEX

protocol. Concretely, we consider the following.

Path 1: Alice ↔ the authentication server ↔ Bob

which are secure due to TLS.

Path 2: Alice ↔ Bob which is different from Path 1

and we simply assume an e-mail system.

In other words, the system is secure if the authenti-

cation server cannot read e-mails sent from Alice to

Bob and from Bob to Alice, which is a realistic as-

sumption. Finally, the authentication server preserves

the random values R

and R

for Alice and Bob, re-

spectively. Then, the room key k is deﬁned as k =

⊕Hash(pw

) = R

⊕Hash(pw

). Our main idea is

to encrypt the DSSE key by using a SMKEX key atk,

ICEIS 2022 - 24th International Conference on Enterprise Information Systems

110

Figure 2: Our Key Agreement Protocol Based on SMKEX.

and Alice sends the ciphertext to Bob. Then, Bob can

obtain k and deﬁne R

such that R

= k ⊕Hash(pw

This protocol allows Alice and Bob to log into the

chat system (similar to the storage system). The ac-

tual key agreement is described as follows (Fig. 2).

Alice: Choose a random value R

∈ {0, 1}

. Set

the DSSE key for the room k = R

⊕ Hash(pw

Choose x

←− Z

and compute a SMKEX public

key g

. Send g

and R

to the authentication

server (via Path 1).

Authentication Server: Preserve R

with the user

name Alice. Send g

to Bob (via Path 1).

Bob: Choose y

←− Z

and compute a SMKEX public

key g

. Send g

to the authentication server (via

Path 1).

Authentication Server: Forward g

to Alice (via

Path 1).

Alice: Choose a nonce N

and send it to Bob (via

Path 2).

Bob: Choose a nonce N

, compute hsess =

Hash(N

), and send N

and hsess to Al-

ice (via Path 2).

Alice: Compute Hash(N

) and if it is the

same as hsess, then derive atk (as in SMKEX, we

employ HKDF-extract and HKDF-expand deﬁned

in RFC5869 for key derivation) and encrypt k us-

ing atk. We denote the ciphertext C = Enc

atk

(k)

and assume AES-GCM256. Send C to the authen-

tication server (via Path 1).

Authentication Server: Forward C to Bob (via Path

1).

Bob: Derive atk, decrypt C using atk, and obtain k.

Deﬁne R

= k ⊕ Hash(pw

) and send R

to the

authentication server (via Path 1).

Authentication Server: Preserve R

with the user

name Bob.

Here, R

is chosen independently from k, pw

and pw

. Thus no information of them is revealed

from R

directly. Moreover, k is encrypted by atk and

due to the security of SMKEX, only Alice and Bob

know atk. Thus, no information of k is revealed from

C. Finally, the authentication server knows R

and

; however, as in the storage system, the authentica-

tion server does not know pw

and pw

. Therefore,

the authentication server cannot obtain k. Although

Alice knows k, she does not know R

because it is

sent via a TLS communication between the authenti-

cation server and Bob. In other words, Alice cannot

extract Hash(pw

) from k. However, if Alice and the

authentication server collude, then Hash(pw

) can be

extracted from k and R

that allows they can observe

Bob’s storage and his chat messages sent in other

room. Thus, we assume that the authentication server

does not collude with any user.

Secure Chat. When a user posts a message to the

application server, the message is encrypted automat-

ically, and when a user displays a message, the mes-

sage is decrypted automatically. Thus, users are not

required to aware DSSE.

State-free End-to-End Encrypted Storage and Chat Systems based on Searchable Encryption

111

4 PERFORMANCE ANALYSIS

We employed AWS EC2 (t2.micro (vCPU1, 1GiB

memory), OS: Ubuntu 20.04, CPU: Intel(R) Xeon(R)

CPU E5-2676 v32.40GHz) as the authentication and

application servers, and OS: Windows 10 Pro, CPU:

Intel® Core™ i7-8565U CPU 1.80GHz as a user. We

compared our system to a non-DSSE system. In this

non-DSSE case, we employed a classical inverted in-

dex method as a searching method for the storage sys-

tem, and SELECT supported by PostgreSQL

for the

chat system.

Storage System. We used copyright-free Japanese

books published by Aozora Bunko.

For example,

Botchan (Soseki Natsume) contains approximately

100,000 characters. When a ﬁle was uploaded, the

runtime was 13.7 s in the non-DSSE case and 13.5

s in the DSSE case. We consider that the DSSE

case was more efﬁcient because indexes are gener-

ated in the non-DSSE case, whereas this procedure

is not required in the DSSE case. When a keyword is

searched, we gave the case when a keyword is found

(Search Hit) in Table 1, and the case when a keyword

is not found (Search does not Hit) in Table 2, re-

spectively. Due to the AWS environment, it appears

that computation resources are not always guaranteed;

thus, there were ﬂuctuations in run times; however,

we found that the run time is generally linearly de-

pendent on the number of ﬁles.

Table 1: Storage System: Search Hit (msec).

Cases \# Files 1 3 5 10

Non-DSSE(A) 54.0 55.5 62.5 53.5

DSSE(B) 82.5 89.0 112.0 103.5

(B)-(A) 28.5 33.5 49.5 50.0

Table 2: Storage System: Search does not Hit (msec).

Cases \# Files 1 3 5 10

Non-DSSE(A) 54.0 56.0 49.0 55.0

DSSE(B) 59.5 75.0 56.5 70.5

(B)-(A) 5.5 19.0 7.5 15.5

Chat System. We used Tweet data posted by NICT

ofﬁcial publicity.

When a message was posted, the

running time was 35.0 ms in the non-DSSE case and

66.4 ms in the DSSE case. Although it becomes

worse almost twice, it seems acceptable for practice

application. When a keyword ω is searched, we gave

the case when a keyword is found (Search Hit) in

https://www.postgresql.org/

https://www.aozora.gr.jp/

https://twitter.com/NICT Publicity

Table 3, and the case when a keyword is not found

(Search does not Hit) in Table 4, respectively. Note

that the difference (B)-(A) increased as number of

messages increased due to the DSSE.

Table 3: Chat System: Search Hit (msec).

Case \# Messages 20 40 60

Non-DSSE(A) 43.8 41.0 61.2

DSSE(B) 114.6 129.4 158.2

(B)-(A) 70.8 88.4 97.0

Table 4: Chat System: Search does not Hit (msec).

Case \# Messages 20 40 60

Non-DSSE(A) 32.4 39.4 46.4

DSSE(B) 68.2 103.8 131.2

(B)-(A) 35.8 64.4 84.8

5 CONCLUSION

In this paper, we implement secure storage and chat

systems from the Watanabe et al.’s state-free DSSE

scheme and our key agreement protocol that com-

bines the SMKEX protocol and login information

(password). Encrypted Files and messages are stored

on the application server, and users can search them in

a secure manner, i.e., the server does not know what

keyword is searched. Owing to state-freeness, no ad-

ditional tamper-resistant device is required, and users

who know the password to use the systems on multi-

ple devices.

Owing to the SMKEX protocol, we assume two

different communication paths, TLS and an e-mail

system. Discussing whether this selection is reason-

able in practice, especially considering a recent work

by Fischlin et al. (Fischlin et al., 2021) that showed

multipath TCP can be used for SMKEX, and imple-

menting the key agreement protocol part are left as

future works of this paper.

ACKNOWLEDGEMENTS

The authors thank Mr. Satoru Kanno (Ierae Se-

curity, Inc.), Dr. Yumi Sakemi (Ierae Security,

Inc.), Prof. Tetsu Iwata (Nagoya University), and

Prof. Shuichi Hirose (University of Fukui) for

their invaluable comments and suggestions. This

work was supported by JSPS KAKENHI Grant

Numbers JP21K11897, JP21H03441, JP18K11293,

JP18H05289, and JP21H03395.

ICEIS 2022 - 24th International Conference on Enterprise Information Systems

112

REFERENCES

Crypto-chat. http://www.crypto-chat.com/.

MeCab: Yet another part-of-speech and morphological an-

alyzer. https://sourceforge.net/projects/mecab/.

Bost, R. (2016).

∑

oϕoς: Forward secure searchable encryp-

tion. In ACM CCS, pages 1143–1154.

Bost, R., Minaud, B., and Ohrimenko, O. (2017). Forward

and backward private searchable encryption from con-

strained cryptographic primitives. In ACM CCS, pages

1465–1482.

Cash, D., Jaeger, J., Jarecki, S., Jutla, C. S., Krawczyk, H.,

Rosu, M., and Steiner, M. (2014). Dynamic search-

able encryption in very-large databases: Data struc-

tures and implementation. In NDSS.

Chamani, J. G., Papadopoulos, D., Papamanthou, C., and

Jalili, R. (2018). New constructions for forward and

backward private symmetric searchable encryption. In

ACM CCS, pages 1038–1055.

Chen, L., Huang, K., Manulis, M., and Sekar, V. (2021).

Password-authenticated searchable encryption. Inter-

national Journal of Information Security, 20(5):675–

693.

Costea, S., Choudary, M. O., Gucea, D., Tackmann, B., and

Raiciu, C. (2018). Secure opportunistic multipath key

exchange. In ACM CCS, pages 2077–2094.

Curtmola, R., Garay, J. A., Kamara, S., and Ostrovsky, R.

(2006). Searchable symmetric encryption: improved

deﬁnitions and efﬁcient constructions. In ACM CCS ,

pages 79–88.

Emura, K., Ito, R., Kanamori, S., Nojima, R., and Watan-

abe, Y. (2021). State-free end-to-end encrypted stor-

age and chat systems based on searchable encryption.

IACR Cryptol. ePrint Arch., page 953.

Etemad, M., K

upc¸

u, A., Papamanthou, C., and Evans, D.

(2018). Efﬁcient dynamic searchable encryption with

forward privacy. Privacy Enhancing Technologies,

2018(1):5–20.

Fischlin, M., M

uller, S., M

unch, J., and Porth, L. (2021).

Multipath TLS 1.3. In ESORICS, pages 86–105.

Groth, J. (2016). On the size of pairing-based non-

interactive arguments. In EUROCRYPT, pages 305–

326.

Grubbs, P., McPherson, R., Naveed, M., Ristenpart, T., and

Shmatikov, V. (2016). Breaking web applications built

on top of encrypted data. In ACM CCS, pages 1353–

1364.

Kamara, S. and Papamanthou, C. (2013). Parallel and dy-

namic searchable symmetric encryption. In Financial

Cryptography and Data Security, pages 258–274.

Kamara, S., Papamanthou, C., and Roeder, T. (2012). Dy-

namic searchable symmetric encryption. In ACM

CCS, pages 965–976.

Katz, J., Ostrovsky, R., and Yung, M. (2001). Efﬁcient

password-authenticated key exchange using human-

memorable passwords. In EUROCRYPT, pages 475–

494.

Kim, K. S., Kim, M., Lee, D., Park, J. H., and Kim, W.

(2017). Forward secure dynamic searchable symmet-

ric encryption with efﬁcient updates. In ACM CCS,

pages 1449–1463.

Krawczyk, H. and Eronen, P. HMAC-based extract-and-

expand key derivation function (HKDF). https://

datatracker.ietf.org/doc/html/rfc5869.

Lai, R. W. F. and Chow, S. S. M. (2017). Forward-secure

searchable encryption on labeled bipartite graphs. In

Applied Cryptography and Network Security, pages

478–497.

Leach, P., Mealling, M., and Salz, R. (2005). A Universally

Unique IDentiﬁer (UUID) URN Namespace. https:

//tools.ietf.org/html/rfc4122.

Miers, I. and Mohassel, P. (2017). IO-DSSE: scaling dy-

namic searchable encryption to millions of indexes by

improving locality. In NDSS.

Naveed, M., Prabhakaran, M., and Gunter, C. A. (2014).

Dynamic searchable encryption via blind storage. In

IEEE Symposium on Security and Privacy, pages 639–

654.

Popa, R. A., Redﬁeld, C. M. S., Zeldovich, N., and Balakr-

ishnan, H. (2011). CryptDB: protecting conﬁdential-

ity with encrypted query processing. In ACM SOSP,

pages 85–100.

Popa, R. A., Redﬁeld, C. M. S., Zeldovich, N., and Balakr-

ishnan, H. (2012). CryptDB: processing queries on an

encrypted database. Commun. ACM, 55(9):103–111.

Popa, R. A., Stark, E., Valdez, S., Helfer, J., Zeldovich,

N., and Balakrishnan, H. (2014). Building web ap-

plications on top of encrypted data using Mylar. In

USENIX NSDI, pages 157–172.

Popa, R. A. and Zeldovich, N. (2013). Multi-key searchable

encryption. IACR Cryptol. ePrint Arch., 2013:508.

Popa, R. A., Zeldovich, N., and Balakrishnan, H. (2015).

Guidelines for using the CryptDB system securely.

IACR Cryptol. ePrint Arch., 2015:979.

Shibata, T. and Yoneyama, K. (2021). Universally com-

posable forward secure dynamic searchable symmet-

ric encryption. In ACM ASIA Public-Key Cryptogra-

phy Workshop, pages 41–50.

Song, D. X., Wagner, D. A., and Perrig, A. (2000). Practical

techniques for searches on encrypted data. In IEEE

Symposium on Security and Privacy, pages 44–55.

Stefanov, E., Papamanthou, C., and Shi, E. (2014). Practical

dynamic searchable encryption with small leakage. In

NDSS.

Sun, S., Yuan, X., Liu, J. K., Steinfeld, R., Sakzad, A.,

Vo, V., and Nepal, S. (2018). Practical backward-

secure searchable encryption from symmetric punc-

turable encryption. In ACM CCS, pages 763–780.

Watanabe, Y., Nakai, T., Ohara, K., Nojima, T., Liu, Y.,

Iwamoto, M., and Ohta, K. (2021). How to make a

secure index for searchable symmetric encryption, re-

visited. Cryptology ePrint Archive, Report 2021/948.

Yoneyama, K. and Kimura, S. (2017). Veriﬁable and for-

ward secure dynamic searchable symmetric encryp-

tion with storage efﬁciency. In ICICS, pages 489–501.

State-free End-to-End Encrypted Storage and Chat Systems based on Searchable Encryption

113