Information Security and Privacy

Public Key Encryption with Keyword Search (PEKS), introduced by Boneh et al. in Eurocrypt’04, allows users to search encrypted documents on an untrusted server without revealing any information. This notion is very useful in many applications and has attracted a lot of attention by the cryptographic research community. However, one limitation of all the existing PEKS schemes is that they cannot resist the Keyword Guessing Attack (KGA) launched by a malicious server. In this paper, we propose a new PEKS framework named Dual-Server Public Key Encryption with Keyword Search (DS-PEKS). This new framework can withstand all the attacks, including the KGA from the two untrusted servers, as long as they do not collude. We then present a generic construction of DS-PEKS using a new variant of the Smooth Projective Hash Functions (SPHFs), which is of independent interest.

In this paper we show conceptually simple methods for constructing dynamic TPKE schemes with decryption consistency from only static assumptions (e.g., the decisional linear assumption in bilinear groups) without relying on random oracles. Our first construction is a purely generic construction from public-key encryption with non-interactive opening (PKENO) formalized by Damgård et al. (CT-RSA 2008). However, this construction achieves a slightly weaker notion of decryption consistency compared to the random oracle extension of the Delerablée and Pointcheval scheme, which satisfies the notion defined by Boneh, Boyen and Halevi (CT-RSA 2005). Our second construction uses a specific PKENO scheme based on the decisional linear assumption in combination with the efficient zero-knowledge proofs by Groth and Sahai. In contrast to our first construction, our second construction achieves the stronger notion of decryption consistency defined by Boneh, Boyen and Halevi.

OAEP and other similar schemes proven secure in Random-Oracle Model require one or more hash functions with output size larger than those of standard hash functions. In this paper, we show that by utilizing popular Sponge constructions in OAEP framework, we can eliminate the need of such hash functions. We provide a new scheme in OAEP framework based on Sponge construction and call our scheme Sponge based asymmetric encryption padding (SpAEP). SpAEP is based on 2 functions: Sponge and SpongeWrap, and requires only standard output sizes proposed and standardized for Sponge functions. Our scheme is CCA2 secure for any trapdoor one-way permutation in the ideal permutation model for arbitrary length messages. Our scheme utilizes the versatile Sponge function to enhance the capability and efficiency of the OAEP framework. SpAEP with any trapdoor one-way permutation can also be used as a key encapsulation mechanism and a tag-based key encapsulation mechanism for hybrid encryption. Our scheme SpAEP utilizes the permutation model efficiently in the setting of public key encryption in a novel manner.

The notion of online/offline encryption was put forth by Guo, Mu and Chen (FC 2008), where they proposed an identity-based scheme called identity-based online/offline encryption (IBOOE). An online/offline encryption separates an encryption into two stages: offline and online. The offline phase carries much more computational load than the online phase, where the offline phase does not require the information of the message to be encrypted and the identity of the receiver. Subsequently, many applications of IBOOE have been proposed in the literature. As an example, Hobenberger and Waters (PKC 2014) have recently applied it to attribute-based encryption. In this paper, we move one step further and explore a much more efficient variant. We propose an efficient semi-generic transformation to obtain an online/offline encryption from a tradition identity-based encryption (IBE). Our transformation provides a new method to separate the computation of receiver’s identity into offline and online phases. The IBOOE schemes using our transformation saves one group element in both offline and online phases compared to other IBOOE schemes in identity computing. The transformed scheme still maintains the same level of security as in the original IBE scheme.

Digital signatures guarantee practical security only if the corresponding verification keys are distributed authentically; however, arguably, satisfying solutions for the latter haven’t been found yet. This paper introduces a novel approach for cryptographic message authentication where this problem does not arise: A linkable message tagging scheme (LMT) identifies pairs of messages and accompanying authentication tags as related if and only if these tags were created using the same secret key. Importantly, our primitive fully avoids public keys, and hence elegantly sidesteps the key distribution problem of signature schemes.

As technical contributions we formalize the notions of LMT and its (more efficient) variant CMT (classifiable message tagging), including corresponding notions of unforgeability. For both variants we propose a range of provably secure constructions, basing on different hardness assumptions, with and without requiring random oracles.

Detecting malicious attempts to access computers is difficult with current security applications. Many current applications do not give the user the right information to find and analyze possible attempts. We present VisRAID – a novel visual analytics web application for detecting intrusions via remote access attempts, and a user study to evaluate the effectiveness and usability of the application with security professionals. The implications of the study will help inform the design of future security visualization applications.

Cryptanalytic time-memory tradeoffs were introduced by Martin Hellman in 1980 to perform key-recovery attacks on cryptosystems. Rainbow tables are a variant and a major advance presented by Philippe Oechslin at Crypto 2003. Checkpoints for rainbow tables have been proposed in Indocrypt 2005 as a method to reduce the cost of false alarms. Endpoints truncation has also been suggested to reduce their memory consumption.

We present a Dynamic Provable Data Possession (PDP) system with Public Verifiability and Data Privacy. Three entities are involved: a client who is the owner of the data to be stored, a server that stores the data and a Third Party Auditor (TPA) who may be required when the client wants to check the integrity of its data stored on the server. The system is publicly verifiable with the possible help of the TPA who acts on behalf of the client. The system exhibits data dynamicity at block level allowing data insertion, deletion and modification to be performed. Finally, the system is secure at the untrusted server and data private. We present a practical PDP system by adopting asymmetric pairings to gain efficiency and reduce the group exponentiation and pairing operations. In our scheme, no exponentiation and only three pairings are required during the proof of data possession check, which clearly outperforms all the existing schemes in the literature. Furthermore, our protocol supports proof of data possession on as many data blocks as possible at no extra cost.

In this paper, we study the security of PMAC-type constructions generalizing the underlying primitive to keyed functions. We first consider the construction with two different primitives: one for intermediate calls and another for finalization. While the security of original PMAC was based on the assumption that the primitive (block ciphers) is a pseudo-random permutation (PRP), here we show that for MAC security of the construction, we just need MAC security of the internal primitives and privacy-preserving MAC (PP-MAC) security for the finalization primitive. As PP-MAC is strictly weaker than a pseudo-random function (PRF), this shows that PRF assumption on underlying primitives is not a necessary condition to achieve MAC security of PMAC type constructions. In the context, we also show that for PRF security of the construction, we only need the finalization primitive to be PRF secure. The requirement on the internal primitive reduces from PRF to just a secure MAC. Moreover, we show that for MAC security of the construction, PRF security of underlying primitive is not essential. We claim that, if we restrict to use only one primitive (as two keys are required, if two different primitives are used) then for MAC security, the primitive only needs to be PP-MAC secure. This essentially makes the construction single key PP-MAC domain extender, having the parallelizability advantage over iCBC-MAC. We also show that, if we want the construction to be PRF secure, then we need the underlying primitive to be PRF secure. This can be thought as an alternative proof of the original PMAC, not restricted to block-ciphers only but takes care any keyed functions.