Provable Security

There is an increasing demand of data sharing via cloud. Data privacy and secrecy protections are arguably the major challenges in such applications. It is widely suggested to encrypt outsourced data using advanced encryption primitives for flexible sensitive data sharing in cloud. In all existing asymmetric based systems, a subtle issue is that the data owner itself cannot read the encrypted and outsourced data. This raises a problem for the data owner when she needs to access the outsourced data but locally there is no copy in the clear text form. To cope with this problem, we formalize a new framework, referred to as Self-EXtractable Encryption (SEXE). In addition to the normal functionalities of an advanced encryption primitive, SEXE is equipped with a useful self-extractability. With this property, the data owner can always access her encrypted data. We propose a generic SEXE construction from any advanced encryption primitives. Following the proposed generic construction, we instantiate several typical SEXE systems, including Self-EXtractable Identity-Based Encryption (SEXIBE), Self-Extractable Attribute-Based Encryption (SXABE) in Key-Policy setting and in Ciphertext-Policy setting.

The single-writer/multi-reader searchable encryption (SMSE) allows an arbitrary authorized user to submit a valid search token and get the corresponding encrypted identifiers. In order to achieve fine-grained access control, the identifiers are encrypted by the attribute-based encryption. In this case, the user can decrypt a ciphertext only when the access policy in it matches the user’s attribute set. However, the server unable to determine whether the user can decrypt a certain ciphertext without the knowledge of the user’s attribute set. As a result, all the ciphertexts based on a search token have to be returned to the user, which causes unnecessary communication and decryption costs. In this paper, we propose a new SMSE scheme, in which the server just needs to return the ones which can be decrypted by the user rather than the whole search results. In order to achieve this goal, we present a server-side match technique with which the server can test whether the user can decrypt a ciphertext without knowing the user’s attribute set. Furthermore, the decryption computation is very efficient, irrespective of the structure of access policy. Therefore, both the communication and decryption overheads are dramatically reduced in our scheme.

Public key encryption with keyword search (PEKS) is a promising cryptographic mechanism to enable secure search over encrypted data in cloud. The mechanism allows a semi-trusted cloud server to return related encrypted contents without knowing what the query is and what the corresponding contents are. It has been combined with attribute based encryption (ABE) to support more expressiveness in search. Most of the existing searchable ABE schemes, however, are restricted to heavy complexity. In particular, the size of ciphertext and pairing cost in the test phase are both linear in the size of the keyword set, say O(n), where n is the number of keyword. This limitation hinders the scalability of searchable ABE in practice. To address this long-lasting open problem, this paper proposes a new key-policy attribute-based search encryption (KP-ABSE) scheme. Our construction can be regarded as a novel combination of fast decryption, anonymous-like encryption, and KP-ABE technologies. As of independent interest, the scheme is built in asymmetric bilinear groups. The scheme is further proved secure under the asymmetric decisional DBDH, decisional q-BDHE and decisional linear assumptions in the standard model. Compared with existing KP-ABSE schemes, our new scheme achieves the following properties: (1) flexible access structure for search - any monotonic access structure, (2) constant ciphertext size, (3) constant pairing operations in the test phase.

In multi-label (ML) learning, each training instance is associated with a set of labels to present its multiple semantic information, and the task is to predict the associated labels for each unclassified instance. Nowadays, many multi-label learning approaches have been proposed, unfortunately, all of the existing approaches did not consider the issue of protecting the privacy information. In this paper, we propose a scheme for secure multi-label classification over encrypted data in cloud. Our scheme can outsource the multi-label classification task to the cloud servers which dramatically reduce the storage and computation burden of data owner and data users. Based on the theoretical proof, our scheme can protect the privacy information of data owner and data users, the cloud servers can not learn anything useful about the input data and output multi-label classification results. Additionally, we evaluate our computation complexity and communication overheads in detail.

Cloud backup has been widely used in recent years. Over time, if the stored content is not under control, there will be a lot of redundant data stored in the cloud. When a user issues a delete instruction, the cloud service provider may not actually destroy the data, so that the user’s data is exposed to the risk of being compromised. In order to avoid storing duplicate data and prevent deleted data from being recovered, we design a cloud backup system that can solve the two problems. No matter how large the files, each client only keeps one key. Through the experimental evaluation, we verify that our scheme is valid and our local overhead is greatly saved.

Keeping correct and informative log files is crucial for system maintenance, security and forensics. Cryptographic logging schemes offer integrity checks that protect a log file even in the case where an attacker has broken into the system.

A relatively recent feature of these schemes is resistance against truncations, i.e. the deletion and/or replacement of the end of the log file. This is especially relevant as system intruders are typically interested in manipulating the later log entries that point towards their attack. However, there are not many schemes that are resistant against truncating the log file. Those that are have at least one of the following disadvantages: They are memory intensive (they store at least one signature per log entry), or fragile (i.e. a single error in the log renders the signature invalid and useless in determining where the error occurred).

We obtain a publicly-verifiable secure logging scheme that is simultaneously robust, space-efficient and truncation secure with provable security under simple assumptions. Our generic construction uses forward-secure signatures, in a plain and a sequential aggregate variant, where the latter is additionally fault-tolerant, as recently formalized by Hartung et al. [9]. Fault-tolerant schemes can cope with a number of manipulated log entries (bounded a priori) and offer strong robustness guarantees while still retaining space efficiency. Our implementation and the accompanying performance measurements confirm the practicality of our scheme.

Recently, verifiably encrypted signatures (VESs) have been widely used in fair exchange, however most of them do not provide a method to protect the anonymity of the signer, leading to privacy leakage in fair exchange. Verifiably Encrypted Group Signature (VEGS) overcomes drawbacks of VES, which allows a verifier to check its validity without decryption. And VEGS does not reveal the identity of the signer, thus protecting the privacy of the signer. In VEGS systems, a signer generates a group signature with his private key, then encrypts it with the adjudicator’s public key and outputs a VEGS. A verifier can check whether a VEGS is valid. The group manager reveals the identity of the VEGS if necessary. The adjudicator can extract the original group signature from the VEGS with his private key. In this paper, we propose the first concrete VEGS scheme according to our model. We define several security properties which are essential to VEGS schemes and we prove that our scheme is secure in the standard model. Additionally, we discuss some relevant issues about our scheme.

Offset codebook mode (OCB) provides neither integrity under releasing unverified plaintext (INT-RUP) nor nonce-misuse resistance. The tag of OCB is generated by encrypting a plaintext checksum, which is vulnerable in the INT-RUP security model. This paper focuses on the weakness of the checksum processing in OCB. We describe a new type of structure, called plaintext and ciphertext checksum (PCC), which is a generalization of the plaintext checksum, and prove that all authenticated encryption schemes with PCC are insecure in the INT-RUP security model. Then, we fix the weakness of PCC and present another new type of structure, called intermediate checksum (IC), to generate the authentication tag. To settle the INT-RUP security of OCB in the nonce-misuse setting, we provide a modified OCB scheme based on IC, called OCB-IC. OCB-IC is proven INT-RUP secure up to the birthday bound in the nonce-misuse setting if the underlying tweakable blockcipher is a secure mixed tweakable pseudorandom permutation (MTPRP). Finally, we present some discussions about OCB-IC.

Recently, Chakraborty et al. (Cryptoeprint:2017:441) showed a novel approach of constructing several leakage-resilient cryptographic primitives by introducing a new primitive called leakage-resilient non-interactive key exchange (LR-NIKE). Their construction of LR-NIKE was only in the bounded-memory leakage model, and they left open the construction of LR-NIKE in continuous-memory leakage model. In this paper we address that open problem. Moreover, we extend the continuous-memory leakage model by addressing more realistic after-the-fact leakage. The main ingredients of our construction are a leakage-resilient storage scheme and a refreshing protocol (Dziembowski and Faust, Asiacrypt 2011) and a (standard) chameleon hash function (CHF), equipped with an additional property of oblivious sampling, which we introduce. We observe that the present constructions of CHF already satisfies our new notion. Further, our protocol can be used as a building block to construct leakage-resilient public-key encryption schemes, interactive key exchange and low-latency key exchange protocols in the continuous-memory leakage model, following the approach of Chakraborty et al. (Cryptoeprint:2017:441).

In this paper, we introduce a new framework of password-based key exchange (PAKE). Until now, most PAKEs are based on smooth projective hash function on secure encryption. Our PAKE does not rely on smooth projective hash function, and consists of a variate lossy encryption, called only-one lossy encryption, and indistinguishable plaintext checkable secure encryption. We also give construction of only-one lossy encryption based decisional Diffie Hellman (DDH) and learning with errors (LWE) assumptions. Although the instantiation based on DDH assumption does not improve efficiency of precious works, our framework provides more easier and elegant way to construct PAKE from LWE assumption.

The Diffie-Hellman problem as a cryptographic primitive plays an important role in modern cryptology. The Bit Security or Hard-Core Bits of Diffie-Hellman problem in arbitrary finite cyclic group is a long-standing open problem in cryptography. Until now, only few groups have been studied. Hyperelliptic curve cryptography is an alternative to elliptic curve cryptography. Due to the recent cryptanalytic results that the best known algorithms to attack hyperelliptic curve cryptosystems of genus \(g<3\) are the generic methods and the recent implementation results that hyperelliptic curve cryptography in genus 2 has the potential to be competitive with its elliptic curve cryptography counterpart. In this paper, we generalize Boneh and Shparlinksi’s method and result about elliptic curve to the case of Jacobians of hyperelliptic curves. We prove that the least significant bit of each coordinate of hyperelliptic curves Diffie-Hellman secret value in genus 2 is hard as the entire Diffie-Hellman value, and then we also show that any bit is hard as the entire Diffie-Hellman value. Finally, we extend our techniques and results to hyperelliptic curves of any genus.

Replayable CCA (RCCA) security is a reasonable relaxation of CCA security for public-key encryptions. Pd-RCCA and sd-RCCA security are two variants of it according to a “replaying” can be detected publicly or secretly. Existing “natural” RCCA schemes satisfy pd-RCCA security, while those satisfying only sd-RCCA security are left as open. We present such schemes via KEM+DEM hybrid paradigm. Sd-RCCA secure DEMs are sufficient for this purpose. It is known that an RCCA secure DEM can be achieved by combining a passive secure DEM with a regular (but not a strong) secure message authentication code (MAC), where forgeries for old messages might be possible. Unfortunately, most practical MACs are deterministic, which makes the two notions equivalent. However, the recently proposed probabilistic MACs activate this paradigm. We formalize the related notions and the paradigm, then show natural examples of regular secure probabilistic MACs under the DDH assumption, based on which natural instances of sd-RCCA secure schemes are given.

The lifetime of commonly used digital signature schemes is limited because their security is based on computational assumptions that potentially break in the future. In 1993, Bayer et al. suggested that the lifetime of a digital signature can be prolonged by time-stamping the signature together with the signed document. Based on this idea, various long-term timestamp schemes have been proposed and standardized that repeatedly renew the protection with new timestamps. In order to minimize the risk of a design failure affecting the security of these schemes, it is indispensable to formally analyze their security. However, many of the proposed schemes have not been subject to a formal security analysis yet. In this paper, we address this issue by formally describing and analyzing a long-term timestamp scheme that uses hash trees for timestamp renewal. Our analysis shows that the security level of the described scheme degrades cubic over time, which suggests that in practice the scheme should be instantiated with a certain security margin.

Learning Parity with Noise (LPN) represents the average-case analogue of the NP-Complete problem “decoding random linear codes”, and it has been extensively studied in learning theory and cryptography with applications to quantum-resistant cryptographic schemes. In this paper, we study a sparse variant of the LPN whose public matrix consists of sparse vectors (or alternatively each element of the matrix follows the Bernoulli distribution), of which the variant considered by Benny, Boaz and Avi (STOC 2010) falls into a (extreme) special case. We show a win-win argument that at least one of the following is true: (1) either the hardness of sparse LPN is implied by that of the standard LPN under the same noise rate; (2) there exist new black-box constructions of public-key encryption (PKE) schemes and oblivious transfer (OT) protocols from the standard LPN.

Since a quantum adversary is supposed to be able to perform hash computation with superposition of the quantum bits, it is natural that in random oracle model, the reduction algorithm for security proof should allow the quantum adversary to query random oracle in superposition of quantum bits. However, due to physical nature of quantum states, any observation on a superposition of quantum bits will be noticed by quantum adversaries. Hence, to simulate the true random oracle, the reduction algorithm has to answer the queries without observing their content. This makes the classical reduction algorithms fail to properly perform rewinding and random oracle programming against quantum adversaries and it has been shown recently that several signature schemes generated by Fiat-Shamir transformation might be insecure against quantum adversaries although they have been proven secure in classical setting against classical adversaries.

In this paper, we propose a method to construct reduction algorithm without rewinding of quantum adversary and such that the random oracle programming is unnoticeable by the quantum adversary except with negligible probability. We show the feasibility of our method by applying it on signature scheme generated via Fiat-Shamir transformation of an identification scheme whose security is based on the decisional problem of isomorphism of polynomials with two secrets.

Despite a great deal of progress in resent years, efficiency of fully homomorphic encryption (FHE) is still a major concern. Specifically, the bootstrapping procedure is the most costly part of a FHE scheme. FHE schemes with ring element plaintexts, such as the ring-LWE based BGV scheme, are the most efficient ones, since they can not only encrypt a ring element instead of a single bit in one ciphertext, but also support CRT-based ciphertext packing techniques. Thanks to homomorphic operations in a SIMD fashion (Single Instruction Multiple Data), the ring-LWE BGV scheme can achieve a nearly optimal homomorphic evaluation. However, the BGV scheme, as implemented in HElib, can only bootstrap within super-polynomial noise so far. Note that such a noise rate for a ring-LWE based scheme is less safe and more costly, because one has to choose larger dimensions to ensure security. On the other hand, existing polynomial noise bootstrapping techniques can only be applied to FHE schemes with bit plaintexts. In this paper, we provide a polynomial noise bootstrapping method for the BGV scheme with ring plaintexts. Specifically, our bootstrapping method allows users to choose any plaintext modulus \(p>1\) and any modulus polynomial \(\varPhi (X)\) for the BGV scheme. Our bootstrapping method incurs only polynomial error \(O(n^3)\cdot B\) for lattice dimension n and noise bound B comparing to \((B\cdot poly(n))^{\tilde{O}(\log (n))}\) for previous best methods. Concretely, to achieve 70 bit security, the dimension of the lattice that we use is no more than \(2^{12}\), while previous methods in HElib need about \(2^{14}\) to \(2^{16}\).

Predicate encryption, formalized by Katz, Sahai, and Waters (EUROCRYPT 2008), is an attractive branch of public-key encryption, which provides fine-grained and role-based access to encrypted data. As for many multi-user cryptosystems, an efficient revocation mechanism is necessary and imperative in the context of predicate encryption, in order to address scenarios when users misbehave or their private keys are compromised. The formal model of revocable predicate encryption was introduced by Nieto, Manulis and Sun (ACISP 2012), who suggest the strong, full-hiding security notion, demanding that the ciphertexts do not leak any information about the encrypted data, the attribute and the revocation information associated with it.

In this work, we introduce the first construction of lattice-based revocable predicate encryption. Our scheme satisfies the full-hiding security notion (in a selective manner) in the standard model, based on the hardness of the Learning With Errors \((\mathsf {LWE})\) problem. In terms of asymptotic efficiency, the scheme is somewhat comparable to the pairing-based instantiation put forward by Nieto, Manulis and Sun. Furthermore, better efficiency could be easily achieved in the random oracle model.

Broadcast encryption is an efficient way to send the broadcast messages, but, it does not yield a productive way to send the personalized messages to individuals. A broadcast encryption with personalized messages (BEPM) skillfully sends the broadcast message to a group of users together with the personalized messages to individual users. This article identifies constructional flaws in the BEPM scheme of Xu et al. and designs three BEPM constructions, namely, BEPM-I, BEPM-II and BEPM-III. BEPM-I, BEPM-III are selectively secure. Unlike the existing similar works, these schemes eliminate the need of storing public key and secret key for transmitting personalized messages. We emphasize that BEPM-III employs multilinear maps and achieves logarithmic size public parameter with increasing computation cost. More positively, BEPM-II achieves adaptive security with the parameter size and computation cost as in the existing BEPM. All our constructions have constant communication cost and proven to be secure in the standard security model under reasonable assumptions in generic group model. Furthermore, our schemes are fully collision resistant and flexible for adding and removing of users from the broadcast system.

Signcryption has shown many useful applications, in particular for the environment where the computation and communication resources are constrained, for instance, for applications on lightweight devices. However, we notice that traditional signcryption schemes do not support homomorphic properties, which are very useful in many application scenarios. We also notice that the previous attempt of capturing the homomorphism in signcryption is not provably secure. In this paper, we propose a provably secure additive homomorphic signcryption. Our scheme offers the following two features: (1) Signing and encrypting are carried out in one go, unlike the traditional encryption and signature schemes which are computed separately. (2) We allow the collected signcrypted data items to be aggregated without requiring decryption. The second feature confirms the significance of the first feature in that the traditional signcryption cannot be applied due to lacking of the homomorphic property. Our scheme is the first provably secure signcryption that supports homomorphic property.

We study public key encryptions (PKE) of simulation-based security against sender selective-opening (SIM-SSO) attacks, where the attacker can corrupt a subset of senders, learning the plaintexts together with the corresponding randomness. Concretely:

A recent breakthrough by Boyle et al. [7] demonstrated secure function evaluation protocols for branching programs, where the communication complexity is sublinear in the size of the circuit (indeed just linear in the size of the inputs, and polynomial in the security parameter). Their result is based on the Decisional Diffie-Hellman assumption (DDH), using (variants of) the ElGamal cryptosystem. In this work, we extend their result to show a construction based on the circular security of the Paillier encryption scheme. We also offer a few optimizations to the scheme, including an alternative to the “Las Vegas”-style share conversion protocols of [7, 9] which directly checks the correctness of the computation. This allows us to reduce the number of required repetitions to achieve a desired overall error bound by a constant fraction for typical cases, and for large programs, reduces the total computation cost.

Biometric data is an inherent representation of a human user, and it would be highly desirable to derive a private key of a public-key cryptographic scheme from a user’s biometric input such that the user does not need to remember any password or carry any device to store the private key and is able to enjoy all benefits of the public-key cryptographic scheme. In this paper, we introduce a notion called fuzzy public-key encryption (FPKE), which is a public-key encryption (PKE) scheme that accepts a piece of fuzzy data (i.e., a noisy version of the original biometric data) as the private key to decrypt the ciphertext. Compared to the traditional PKE scheme where a private key is usually stored in a device (e.g., a USB token), an FPKE scheme does not need to use any device for the storage of the private key. We first define a formal security model for FPKE, and then give generic constructions of FPKE based on the cryptographic primitives of linear sketch and PKE with some special properties.

Proxy re-encryption (PRE) is a cryptographic primitive introduced by Blaze, Bleumer and Strauss [4] to provide delegation of decryption rights. PRE allows re-encryption of a ciphertext intended for Alice (delegator) to a ciphertext for Bob (delegatee) via a semi-honest proxy, who should not learn anything about the underlying message. In 2003, Al-Riyami and Patterson introduced the notion of certificateless public key cryptography which offers the advantage of identity-based cryptography without suffering from key escrow problem. The existing certificateless PRE (CLPRE) schemes rely on costly bilinear pairing operations. In ACM ASIA-CCS SCC 2015, Srinivasan \(et\ al.\) proposed the first construction of a certificateless PRE scheme without resorting to pairing in the random oracle model. In this work, we demonstrate a flaw in the CCA-security proof of their scheme. Also, we present the first construction of a CLPRE scheme without pairing which meets CCA security under the computational Diffie-Hellman hardness assumption in the random oracle model.

In this paper we put forward a new generalization of Functional Encryption (FE) that we call Mergeable FE (mFE). In a mFE system, given a ciphertext \(c_1\) encrypting \(m_1\) and a ciphertext \(c_2\) encrypting \(m_2\), it is possible to produce in an oblivious way a ciphertext encrypting the merged string \(m_1||m_2\) under the security constraint that the new ciphertext does not leak more information about the original ciphertexts. For instance, let us suppose to have a token for a program (for inputs of variable length) \(P_x\) that, on input a string D representing a list of elements, checks if a given element x is in D, and suppose that \(c_1\) (resp. \(c_2\)) encrypts a list \(D_1\) (resp. \(D_2\)). Then the token evaluated on \(c_1\) (resp. \(c_2\)) reveals if x is in list \(D_1\) (resp. \(D_2\)) but the same token evaluated on c, the ciphertext resulting from the merge of \(c_1\) and \(c_2\), should only reveal if x is in \(D_1\) or x is in \(D_2\) but not in which of the two lists it is in.

This primitive is in some sense FE with the “best possible” homomorphic properties and, besides being interesting in itself, it offers wide applications. For instance, it has as special case multi-inputs FE (and thus indistinguishability obfuscation), but enables applications not possible with the latter.

In many applications, information can be stored and managed using graph data structures, and there is a rich set of graph algorithms that can be used to solve different problems. The subgraph isomorphism problem is defined as, given two graphs G and H, whether G contains a subgraph that is isomorphic to H. The problem has been well studied for many years, and it can be used for many application areas, such as cheminformatics, pattern matching, data mining and image processing. In this paper, we present a private subgraph matching protocol, which solves a special case of the subgraph isomorphism problem. The protocol allows two parties, each holding a private graph, to jointly compute whether one graph is a subgraph of the other. During the protocol, each party learns no useful information about the graph of the other party. We prove that the protocol is secure in the semi-honest setting.

Value-Added Tax or VAT plays an important role in the Indonesian state revenue. Despite its importance, it requires a complex administration process to be done properly. The complexity of the tax administration creates loopholes that can be exploited by dishonest taxpayers to minimize the tax paid to the government. The current system does not prevent the dishonest taxpayers to forge tax invoices which bring tax loss for the government. We utilize the blockchain technology to create a novel approach of implementing the distributed ledger in taxation area. Our proposed protocol creates a transparent and secure VAT system as well as simplifies the process of administering the VAT. The system increases the tax compliance by reducing the risk of tax fraud and increasing the monitoring capability of the tax authority.

Delegating the computation of a polynomial to a server in a verifiable way is challenging. An even more challenging problem is ensuring that this polynomial remains hidden to clients who are able to query such a server. In this paper, we formally define the notion of Private Polynomial Evaluation (PPE). Our main contribution is to design a rigorous security model along with relations between the different security properties. We define polynomial protection (\(\textsf {PP}\)), proof unforgeability (\(\textsf {UNF}\)), and indistinguishability against chosen function attack (\(\textsf {IND}\text {-}\textsf {CFA}\)), which formalizes the resistance of a PPE against attackers trying to guess which polynomial is used among two polynomials of their choice. As a second contribution, we give a cryptanalysis of two PPE schemes of the literature. Finally, we design a PPE scheme called \(\mathsf {PIPE}\) and we prove that it is \(\textsf {PP}\)-, \(\textsf {UNF}\)- and \(\textsf {IND}\text {-}\textsf {CFA}\)-secure under the decisional Diffie-Hellman assumption in the random oracle model.