Dynamic Searchable Symmetric Encryption ([Formula: see text]), apart from providing support for search operation, allows a client to perform update operations on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are desirable from a [Formula: see text] scheme. The former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that search queries should not leak matching entries after they have been deleted. These security properties are formalized in terms of the information leakage that can be incurred by the respective constructions. Existing backward private constructions either have a non-optimal communication overhead or they make use of heavy cryptographic primitives. Our main contribution consists of two efficient backward private schemes [Formula: see text] and [Formula: see text] that aim to achieve practical efficiency by using light weight symmetric cryptographic components only. In the process, we also revisit the existing definitions of information leakage for backward privacy [Bost et al. (In ACM CCS ( 2017 ) 1465–1482 ACM Press)] and propose a relaxed formulation. [Formula: see text] is the first construction to achieve backward privacy in the general setting with optimal communication complexity. Our second construction, [Formula: see text], is the first single round-trip scheme achieving backward privacy in a restricted setting with optimal communication complexity using light weight symmetric cryptographic primitives. The prototype implementations of our schemes depict the practicability of the proposed constructions and indicate that the cost of achieving backward privacy over forward privacy is substantially small. The performance results also show that the proposed constructions outperform the currently most efficient scheme achieving backward privacy.

Since the discovery of identity-based encryption schemes in 2000, bilinear pairings have been used in the design of hundreds of cryptographic protocols. The most commonly used pairings are constructed from elliptic curves over finite fields with small embedding degree. These pairings can have different security, performance, and functionality characteristics, and were therefore classified into Types 1, 2, 3 and 4. In this paper, we observe that this conventional classification is not applicable to pairings from elliptic curves with embedding degree one. It is important to understand the security, efficiency, and functionality of these pairings in light of recent attacks on certain pairings constructed from elliptic curves with embedding degree greater than one. We define three kinds of pairings from elliptic curves with embedding degree one, discuss some subtleties with using them to implement pairing-based protocols, and provide an estimated cost of implementing them on modern processors.

Several papers have studied fault attacks on computing a pairing value e(P,Q), where P is a public point and Q is a secret point. In this paper, we observe that these attacks are in fact effective only on a small number of pairing-based protocols, and that too only when the protocols are implemented with specific symmetric pairings. We demonstrate the effectiveness of the fault attacks on a public-key encryption scheme, an identity-based encryption scheme, and an oblivious transfer protocol when implemented with a symmetric pairing derived from a supersingular elliptic curve with embedding degree 2.