Many commercial cloud service providers (CSPs) adopt pay-per-query pricing models, in which data owners are charged based on the amount of data scanned by each query. In such a data sharing model, not only the privacy preservation for the data and queries but also the trustworthiness of the underlying billing system is of the utmost importance. In this paper, we revisit multi-key searchable encryption (MKSE), an efficient and secure data search algorithm allowing a data owner to grant users the ability to retrieve data of interest over the outsourced, encrypted datasets. We first investigate which factor in existing MKSE schemes renders authorized users over-privileged such that, without risking their credits (e.g., leaking the private keys and/or the passwords for their accounts associated with a project where the shared data resides), they can allow unauthorized users to make valid queries. Unfortunately, this concern may be devastating because the queries made by unauthorized users would incur unexpected financial damage to the owner in practical pay-per-query models. We then propose a novel multi-key data search scheme that is resilient to unauthorized queries. The proposed scheme features a novel user authorization mechanism that carefully limits user privilege such that even an authorized user cannot illegally invite unauthorized users to query unless he entirely leaks his credit. We demonstrate the proposed scheme is comparable to prior work in terms of performance while achieving a higher level of security.

Public key encryption with keyword search (PEKS) enables users to search over encrypted data outsourced to an untrusted server. Unfortunately, updates to the outsourced data may incur information leakage by exploiting the previously submitted queries. Prior works addressed this issue by means of forward privacy, but most of them suffer from significant performance degradation. In this paper, we present a novel forward private PEKS scheme leveraging Software Guard Extension (SGX), a trusted execution environment provided by Intel. The proposed scheme presents substantial performance improvements over prior work. Specifically, we reduce the query processing cost from $O\left(n\right)$ to $O\left(1\right)$, where n is the number of encrypted data. According to our performance analysis, the overall computation time is reduced by 80% on average. Lastly, we provide a formal security definition of SGX-based forward private PEKS, as well as a rigorous security proof of the proposed scheme.

Dynamic searchable symmetric encryption (DSSE) enables searches over encrypted data as well as data dynamics such as flexible data addition and deletion operations. A major security concern in DSSE is how to preserve forward and backward privacy, which are typically achieved by removing the linkability between the newly added data and previous queries, and between the deleted data and future queries, respectively. After information leakage types were formally defined for different levels of backward privacy (i.e., Type-I, II, III), many backward private DSSE schemes have been constructed under the definitions. However, we observed that the backward privacy can be violated by leveraging additional secondary leakage, which is typically leaked in specific constructions of schemes in spite of their theoretical guarantees. In this paper, in order to understand the security gap between the theoretical definitions and practical constructions, we conduct an in-depth analysis of the root cause for the secondary leakage, and demonstrate how it can be abused to violate Type-II backward privacy (e.g., the exposure of the deletion history) of DSSE constructions in practice. We then propose a novel Type-II backward private DSSE scheme based on Intel SGX, which is resilient to the secondary leakage abuse attack. According to the comparative analysis of our scheme with the state-of-the-art SGX-based DSSE schemes, Bunker-B (EuroSec’19) and SGX-SE1 (ACNS’20), our scheme shows higher efficiency in terms of the search latency with a negligible utility loss under the same security level (cf. Bunker-B) while showing similar efficiency with a higher security level (cf. SGX-SE1). Finally, we formally prove that our scheme guarantees Type-II backward privacy.

Dynamic searchable symmetric encryption (DSSE) enables users to outsource their data while retaining the capability to search and update on the encrypted database. Although various DSSE schemes have been proposed to achieve higher efficiency and stronger security, many of them incurred information leakages due to the linkability between ciphertexts and queries as side information. The notions of forward and backward privacy are defined to capture such information leakage in DSSE formally. In particular, backward privacy guarantees that queries do not reveal their relationship with the deleted database, which is further classified into four types (Type-I, I ^- , II, and III) based on the types of information leakage. In this study, we provide a backward privacy attack that exploits the information leakages and apply it to Type-I ^- backward private schemes to lower their security level to Type-III. We then propose a new DSSE framework, which is robust against the proposed attack. We apply our framework to the previous DSSE scheme (Zuo et al., ESORICS 2019) to build the first forward and backward Type-I private DSSE scheme under the backward privacy attack, and demonstrate its efficacy.

Mail user agent (MUA) programs provide an integrated interface for email services. Many MUAs support email encryption functionality to ensure the confidentiality of emails. In practice, they encrypt the content of an email using email encryption standards such as OpenPGP or S/MIME, mostly implemented using GnuPG. Despite their widespread deployment, there has been insufficient research on their software structure and the security dependencies among the software components of MUA programs. In order to understand the security implications of the structures and analyze any possible vulnerabilities of MUA programs, we investigated a number of MUAs that support email encryption. As a result, we found severe vulnerabilities in a number of MUAs that allow cache side-channel attacks in virtualized desktop environments. Our analysis reveals that the root cause originates from the lack of verification and control over the third-party cryptographic libraries that they adopt. In order to demonstrate this, we implemented a cache side-channel attack on RSA in GnuPG and then conducted an evaluation of the vulnerability of 13 MUAs that support email encryption in Ubuntu 14.04, 16.04 and 18.04. Based on our experiment, we found that 10 of these MUA programs (representing approximately 77% of existing MUA programs) allow the installation of a vulnerable version of GnuPG, even when the latest version of GnuPG, which is secure against most cache side-channel attacks, is in use. In order to substantiate the importance of the vulnerability we discovered, we conducted a FLUSH+RELOAD attack on these MUA programs and demonstrated that the attack restored 92% of the bits of the 2048-bit RSA private key when the recipients read a single encrypted email.

Dynamic searchable symmetric encryption (DSSE) enables searches over encrypted data as well as data dynamics such as flexible data addition and deletion operations.A major security concern in DSSE is how to preserve forward and backward privacy, which are typically achieved by removing the linkability between the newly added data and previous queries, and between the deleted data and future queries, respectively. After information leakage types were formally defined for different levels of backward privacy (i.e., Type-I, II, III), many backward-private DSSE schemes have been constructed under the definitions. However, we observed that the backward privacy can be violated by leveraging additional secondary leakage which is typically leaked in specific constructions of schemes in spite of their theoretical guarantees.In this paper, in order to understand the security gap between the theoretical definitions and practical constructions, we conduct an in-depth analysis of the root cause for the secondary leakage, and demonstrate how it can be abused to violate Type-II backward privacy (e.g., the exposure of the deletion history) of DSSE constructions in practice. We then propose a novel Type-II backward private DSSE scheme based on Intel SGX which is resilient to the secondary leakage abuse attack. According to the comparative analysis of our scheme with the state-of-the-art SGX-based DSSE schemes, Bunker-B (EuroSec'19) and SGX-SE1 (ACNS'20),our scheme shows higher efficiency in terms of the search latency with a negligible utility loss under the same security level (cf. Bunker-B); while showing similar efficiency with a higher security level (cf. SGX-SE1). Finally, we formally prove that our scheme guarantees Type-II backward privacy.