Information Security and Privacy

We revisit the problem of finding a nontrivial divisor of a composite integer when it has a divisor in an interval $$[\alpha , \beta ]$$. We use Strassen’s algorithm to solve this problem. Compared with Kim-Cheon’s algorithms (Math Comp 84(291): 339–354, 2015), our method is a deterministic algorithm but with the same complexity as Kim-Cheon’s probabilistic algorithm, and our algorithm does not need to impose that the divisor is prime. In addition, we can further speed up the theoretical complexity of Kim-Cheon’s algorithms and our algorithm by a logarithmic term $$\log (\beta -\alpha )$$ based on the peculiar property of polynomial arithmetic we consider.

Fuzzy extractor converts the reading of a noisy non-uniform source to a reproducible and almost uniform output $$\mathsf {R}$$. The output $$\mathsf {R}$$ in turn is used in some cryptographic system as a secret key. To enable multiple extractions of keys $$\mathsf {R}_1, \mathsf {R}_2, \ldots , \mathsf {R}_\rho $$ from the same noisy non-uniform source and applications of different $$\mathsf {R}_i$$, the concept of reusable fuzzy extractor is proposed to guarantee the pseudorandomness of $$\mathsf {R}_i$$ even conditioned on other extracted keys $$\mathsf {R}_j$$ (from the same source). In this work, we construct a reusable fuzzy extractor from the Learning With Errors (LWE) assumption. Our reusable fuzzy extractor provides resilience to linear fraction of errors. Moreover, our construction is simple and efficient and imposes no special requirement on the statistical structure of the multiple readings of the source.

After the concept of a Fuzzy Extractor (FE) was first introduced by Dodis et al., it has been regarded as one of the candidate solutions for key management utilizing biometric data. With a noisy input such as biometrics, FE generates a public helper value and a random secret key which is reproducible given another input similar to the original input. However, “helper values” may cause some leakage of information when generated repeatedly by correlated inputs, thus reusability should be considered as an important property. Recently, Canetti et al. (Eurocrypt 2016) proposed a FE satisfying both reusability and robustness with inputs from low-entropy distributions. Their strategy, the so-called Sample-then-Lock method, is to sample many partial strings from a noisy input string and to lock one secret key with each partial string independently.In this paper, modifying this reusable FE, we propose a new FE with size-reduced helper data hiring a threshold scheme. Our new FE also satisfies both reusability and robustness, and requires much less storage memory than the original. To show the advantages of this scheme, we analyze and compare our scheme with the original in concrete parameters of the biometric, IrisCode. As a result, on 1024-bit inputs, with false rejection rate 0.5 and error tolerance 0.25, while the original requires about 1 TB for each helper value, our scheme requires only 300 MB with an additional 1.35 GB of common data which can be used for all helper values.

While many cryptographic protocols for card games have been proposed, all of them focus on card games where players have some state that must be kept secret from each other, e.g closed cards and bluffs in Poker. This scenario poses many interesting technical challenges, which are addressed with cryptographic tools that introduce significant computational and communication overheads (e.g. zero-knowledge proofs). In this paper, we consider the case of games that do not require any secret state to be maintained (e.g. Blackjack and Baccarat). Basically, in these games, cards are chosen at random and then publicly advertised, allowing for players to publicly announce their actions (before or after cards are known). We show that protocols for such games can be built from very lightweight primitives such as digital signatures and canonical random oracle commitments, yielding constructions that far outperform all known card game protocols in terms of communication, computational and round complexities. Moreover, in constructing highly efficient protocols, we introduce a new technique based on verifiable random functions for extending coin tossing, which is at the core of our constructions. Besides ensuring that the games are played correctly, our protocols support financial rewards and penalties enforcement, guaranteeing that winners receive their rewards and that cheaters get financially penalized. In order to do so, we build on blockchain-based techniques that leverage the power of stateful smart contracts to ensure fair protocol execution.

In this paper, we propose secret-sharing-based bit-decomposition and modulus-conversion protocols for a prime order ring $$\mathbb {Z}_p$$ with an honest majority: an adversary can corrupt $$k-1$$ parties of n parties and $$2k-1 \le n$$. Our protocols are secure against passive and active adversaries depending on the components of our protocols. We assume a secret is an $$\ell $$-bit element and $$2^{\ell +\lceil \log m \rceil } < p$$, where $$m= k$$ in the passive security and $$m= \left( {\begin{array}{c}n\\ k-1\end{array}}\right) $$ in the active security. The outputs of our bit-decomposition and modulus-conversion protocols are $$\ell $$ tuple of shares in $$\mathbb {Z}_2$$ and a share in $$\mathbb {Z}_{p'}$$, respectively, where $$p'$$ is the modulus after the conversion. If k and n are small, the communication complexity of our passively secure bit-decomposition and modulus-conversion protocols are $$O(\ell )$$ bits and $$O(\lceil \log p' \rceil )$$ bits, respectively. Our key observation is that a quotient of additive shares can be computed from the least significant $$\lceil \log m \rceil $$ bits. If a secret a is “shifted” and additively shared as $$x_i$$s so that $$2^{\lceil \log m \rceil }a = {\sum _{i=0}^{m-1}}x_i = 2^{ \lceil \log m \rceil } a + qp$$, the least significant $$\lceil \log m \rceil $$ bits of $$\sum _{i=0}^{m-1} x_i$$ determine q since p is an odd prime and the least significant $$\lceil \log m \rceil $$ bits of $$2^{\lceil \log m \rceil } a$$ are 0s.

Secret sharing, first introduced by Shamir and Blakley independently, is an important technique to ensure secrecy and availability of sensitive information. It is also an indispensable building block in various cryptographic protocols. In the literature, most of these existing protocols are employing Shamir’s secret sharing, while Blakley’s one has attracted very little attention. In this paper, we revisit Blakley’s secret sharing that is based on hyperplane geometry, and illustrate that some of its potentials are yet to be employed. In particular, it has an appealing property that compared with Shamir’s secret sharing, it not only handles (t, n) secret sharing with similar computational costs, but also handles (n, n) secret sharing with better efficiency. We further apply this property to design a provably secure and optimal resilient proactive secret sharing scheme. Our proposed protocol is versatile to support proactive cryptosystems based on various assumptions, and it employs only one type of verifiable secret sharing as the building block. By contrast, the existing proactive secret sharing schemes with similar properties all employ two different types of verifiable secret sharing. Finally, we briefly discuss some possible extensions of our proposed protocol as well as how to explore more potentials of Blakley’s secret sharing.

Multikey fully homomorphic encryption (MFHE) allows homomorphic operations between ciphertexts encrypted under different keys. In applications for secure multiparty computation (MPC) protocols, MFHE can be more advantageous than usual fully homomorphic encryption (FHE) since users do not need to agree with a common public key before the computation when using MFHE. In EUROCRYPT 2016, Mukherjee and Wichs constructed a secure MPC protocol in only two rounds via MFHE which deals with a common random/reference string (CRS) in key generation. After then, Brakerski et al. replaced the role of CRS with the distributed setup for CRS calculation to form a four round secure MPC protocol. Thus, recent improvements in round complexity of MPC protocols have been made using MFHE.In this paper, we go further to obtain round-efficient and secure MPC protocols. The underlying MFHE schemes in previous works still involve the common value, CRS, it seems to weaken the power of using MFHE to allow users to independently generate their own keys. Therefore, we resolve the issue by constructing an MFHE scheme without CRS based on LWE assumption, and then we obtain a secure MPC protocol against semi-malicious security in three rounds.

In Eurocrypt 2016, Kiayias, Zhou and Zikas (KZZ) have designed a multiparty protocol for computing an arbitrary function, which they prove to be secure in the malicious model with identifiable abort supporting robustness property. In their algorithm, the total transaction verification time has turned out to be $$O(n^6)$$, where n is the number of parties participating in the protocol. The main contribution of this paper is the improvement of their verification time to $$O(n^3\log {n})$$. We achieve this by observing that a deposit transaction created by a party in KZZ can be generated simply from the information contained in a different deposit transaction. This observation coupled with a host of novel techniques for addition and elimination of elements on a set relevant for our protocol is primarily the reason we were able to improve the verification time complexity of the KZZ protocol. Our trick can potentially be applied to speed up many other similar protocols (as much as it is prohibitive in some other specific scenarios). We compare our protocol with the others, based on various performance and security parameters, and, finally discuss the feasibility of implementing this in the Ethereum platform.

In this paper, we consider the implications of parallelizing time-memory tradeoff attacks using a large number of distributed processors. It is shown that Hellman’s original tradeoff method and the Biryukov-Shamir attack on stream ciphers, which incorporates data into the tradeoff, can be effectively distributed to reduce both time and memory, while other approaches are less advantaged in a distributed approach. Distributed tradeoff attacks are specifically discussed as applied to stream ciphers and the counter mode operation of block ciphers, where their feasibility is considered in relation to distributed exhaustive key search. In particular, for counter mode with an unpredictable initial count, we show that distributed tradeoff attacks are applicable, but can be made infeasible if the entropy of the initial count is at least as large as the key. In general, the analyses of this paper illustrate the effectiveness of a distributed tradeoff approach and show that, when enough processors are involved in the attack, it is possible some systems, such as lightweight cipher implementations, may be susceptible to attack in practice.

This paper investigates key correlations of the keystream generated from RC4, and then presents significant improvements for a plaintext recovery attack on WPA-TKIP from the attack by Isobe et al. at FSE 2013. We first discuss newly discovered key correlations between 2 bytes of the RC4 key and a keystream byte in each round. Such correlations are referred as iterated RC4 key correlations. We further apply our iterated RC4 key correlations to the plaintext recovery attack on WPA-TKIP in the same way as the attack by Sen Gupta et al. at FSE 2014, and achieve significant improvements for recovering 8 bytes of a plaintext from the attack by Isobe et al. at FSE 2013. Our result implies that WPA-TKIP further lowers the security level of generic RC4.

In this paper, we focus on traditional cube attacks against Trivium-like ciphers in which linear and nonlinear superpolies are experimentally tested. We provide a new framework on nonlinear superpoly recoveries by exploiting a kind of linearization technique. It worth noting that, in this new framework, the complexities of testing and recovering nonlinear superpolies are almost the same as those of testing and recovering linear superpolies. Moreover, extensive experiments show that by making use of the new framework, the probability to find a quadratic superpoly is almost twice as large as that to find a linear superpoly for Kreyvium and they are almost the same for Trivium. Hopefully, this new framework would provide some new insights on cube attacks against NFSR-based ciphers, and in particular make nonlinear superpolies potentially useful in the future cube attacks.

In SAC 2013, Berger et al. defined Extended Generalized Feistel Networks (EGFN) and analyzed their security. Later, they proposed a cipher based on this structure: $$ LILLIPUT $$. Impossible differential attacks and integral attacks have been mounted on $$ LILLIPUT $$. We propose a tool which has found some classical, impossible and improbable differential attacks by using the variance method. It has highlighted unusual differential conditions which lead to efficient attacks according to the complexity. Moreover, it is the first time we apply the generic variance method to a concrete cipher.

Nonlinear permutations (S-boxes) are key components in block ciphers. The differential branch number measures the diffusion power of a permutation, whereas the linear branch number measures resistance against linear cryptanalysis. There has not been much analysis done on the differential branch number of nonlinear permutations of $$\mathbb {F}_2^n$$, although it has been well studied in case of linear permutations. Similarly upper bounds for the linear branch number have also not been studied in general. In this paper we obtain bounds for both the differential and the linear branch number of permutations (both linear and nonlinear) of $$\mathbb {F}_2^n$$. We also prove that in the case of $$\mathbb {F}_2^4$$, the maximum differential branch number can be achieved only by affine permutations.

In this paper, we study the pseudo-random function (PRF) security of keyed sponges. “Capacity” is a parameter of a keyed sponge that usually defines a dominant term in the PRF-security bound. So far, the PRF-security of the “prefix” keyed sponge has mainly been analyzed, where for a key $$K$$, a message $$M$$ and the sponge function $$\mathtt {Sponge}$$, the output is defined as $$\mathtt {Sponge}(K\Vert M)$$. A tight bound for the capacity term was given by Naito and Yasuda (FSE 2016): $$O((qQ+q^2)/2^c)$$ for the capacity $$c$$, the number of online queries $$q$$ and the number of offline queries $$Q$$. Later, Naito (CANS 2016) showed that using the sandwich method where the output is defined as $$\mathtt {Sponge}(K\Vert M\Vert K)$$, the dependence between $$c$$ and $$q$$ can be removed, i.e., the capacity term is improved to $$O(rQ/2^c)$$, where $$r$$ is the rate. However, unlike the prefix keyed sponge, the sandwich keyed sponge uses the suffix key that requires the memory to keep the suffix key. The additional memory requirement seems not to be appropriate for lightweight settings.For this problem, we consider a keyed sponge with a prefix-free padding, $$\mathtt {KSpongePF}$$, where for a prefix-free padding function $$\mathsf {pfpad}$$, the output is defined as $$\mathtt {Sponge}(K\Vert \mathsf {pfpad}(M))$$. We show that $$\mathtt {KSpongePF}$$ achieves the same level of PRF-security as the sandwich keyed sponge: the capacity term is $$O(rQ/2^c)$$. Hence, using $$\mathtt {KSpongePF}$$, the independence between $$c$$ and $$q$$ can be ensured without the suffix key.

We present the first linkable ring signature scheme with both unconditional anonymity and forward-secure key update: a powerful tool which has direct applications in elegantly addressing a number of simultaneous constraints in remote electronic voting. We propose a comprehensive security model, and construct a scheme based on the hardness of finding discrete logarithms, and (for forward security) inverting bilinear or multilinear maps of moderate degree to match the time granularity of forward security. We prove efficient security reductions—which, of independent interest, apply to, and are much tighter than, linkable ring signatures without forward security, thereby vastly improving the provable security of these legacy schemes. If efficient multilinear maps should ever admit a secure realisation, our contribution would elegantly address a number of problems heretofore unsolved in the important application of (multi-election) practical internet voting. Even if multilinear maps never obtain, our minimal two-epoch construction instantiated from bilinear maps can be combinatorially boosted to synthesize a polynomial time granularity, which would be sufficient for internet voting and more.

An Identity-based encryption (IBE) simplifies key management by taking users’ identities as public keys. However, how to dynamically revoke users in an IBE scheme is not a trivial problem. To solve this problem, IBE scheme with revocation (namely revocable IBE scheme) has been proposed. Apart from those lattice-based IBE, most of the existing schemes are based on decisional assumptions over pairing-groups. In this paper, we propose a revocable IBE scheme based on a weaker assumption, namely Computational Diffie-Hellman (CDH) assumption over non-pairing groups. Our revocable IBE scheme was inspired by the IBE scheme proposed by Döttling and Garg in Crypto2017. Like Döttling and Garg’s IBE scheme, the key authority maintains a complete binary tree where every user is assigned to a leaf node. To adapt such an IBE scheme to a revocable IBE, we update the nodes along the paths of the revoked users in each time slot. Upon this updating, all revoked users are forced to be equipped with new encryption keys but without decryption keys, thus they are unable to perform decryption any more. We proved that our revocable IBE is adaptive IND-ID-CPA secure in the standard model. Our scheme serves as the first revocable IBE scheme from the CDH assumption. Moreover, the size of updating key in each time slot is only related to the number of newly revoked users in the past time slot.

In this paper, we introduce a new cryptographic primitive: private functional signatures, where functional signing keys $$\mathsf {sk}_f$$ for functions f derived from master signing key $$\mathsf {msk}$$ which can be used to sign any message, allow one to sign any message in the range of the underlying function f. Besides, there is an encryption algorithm which takes as input the master secret key $$\mathsf {msk}$$ to produce a ciphertext $$\mathsf {c}_x$$ for message x. And the signing algorithm applies a signing key $$\mathsf {sk}_f$$ on the ciphertext $$\mathsf {c}_x$$ to produce a signature $$\sigma _{f(x)}$$ on the result f(x).We also formalize the security notions of private functional signatures. Furthermore, we provide a general compiler from any (single-key) symmetric-key predicate encryption scheme into a single-key private functional signature scheme. By instantiating our construction with schemes for symmetric-key predicate encryption, we obtain private functional signature schemes based on a variety of assumptions (including the LWE assumption, simple multilinear-maps assumptions, obfuscation assumptions, and even the existence of any one-way function) offering various trade-offs between security and efficiency.

Abusing anonymity has become a severe threat for anonymous communication system. Auditing and further tracing the identity of illegal users become an urgent requirement. Although a large body of anonymous communication mechanisms have been proposed, there is almost no research on auditing and supervising. In this paper, we propose a general construction of linkable group signature to achieve the anonymity, auditing and tracing functions for communication sender simultaneously. The general framework is constructed by using basic cryptography modules of blind signature, public key encryption, trapdoor indicative commitment and signature of knowledge. Furthermore, we first formally define a new concept called trapdoor indicative commitment, which helps to determine whether two given signatures are signed by the same member without opening signatures. Finally, we present an efficient linkable group signature instance. Performance analysis shows that our instance requires less computation and shorter signature length, compared with related works, making it suitable for practical applications.

A member of an intelligence agency needs to receive messages secretly from outside. Except for authorized officers of the agency, no one knows how the members are organized, even a receiver only knows the organization of his/her subordinates. However, existing primitives cannot implement this typical scenario. In this paper, we propose a primitive, referred to as auditable hierarchy-private public-key encryption (AHPE), to address the problem. The system has several important properties: the organization of the members in the agency is hidden from the outside world, but the members can still communicate with the outside secretly; if there exists a suspicious behaviour in one of the members, managers in the system can still discover him/her. Finally, analyses show that the proposed AHPE scheme is efficient and practical.

Public-key encryption with keyword search (PEKS) enables us to search over encrypted data, and is expected to be used between a cloud server and users’ devices such as laptops or smartphones. However, those devices might be lost accidentally or be stolen. In this paper, we deal with such a key-exposure problem on PEKS, and introduce a concept of PEKS with key-updating functionality, which we call key-updatable PEKS (KU-PEKS). Specifically, we propose two models of KU-PEKS: The key-evolution model and the key-insulation model. In the key-evolution model, a pair of public and secret keys can be updated if needed (e.g., the secret key is exposed). In the key-insulation model, a public key remains fixed while a secret key can be updated if needed. The former model makes a construction simple and more efficient than the latter model. On the other hand, the latter model is preferable for practical use since a user never updates his/her public key. We show constructions of a KU-PEKS scheme in each model in a black-box manner. We also give an experimental result for the most efficient instantiation, and show our proposal is practical.

Anonymous Identity-Based Encryption can protect privacy of the receiver. However, there are some situations that we need to recover the identity of the receiver, for example a dispute occurs or the privacy mechanism is abused. In this paper, we propose a new concept, referred to as Anonymous Identity-Based Encryption with Identity Recovery (AIBEIR), which is an anonymous IBE with identity recovery property. There is a party called the Identity Recovery Manager (IRM) who has a secret key to recover the identity from the ciphertext in our scheme. We construct it with an anonymous IBE and a special IBE which we call it testable IBE. In order to ensure the semantic security in the case where the identity recovery manager is an adversary, we define a stronger semantic security model in which the adversary is given the secret key of the identity recovery manager. To our knowledge, we propose the first AIBEIR scheme and prove the security in our defined model.

Subversion attacks against cryptosystems have already received wide attentions since several decades ago, while the Snowden revelations in 2013 reemphasized the need to further exploring potential avenues for undermining the cryptography in practice. In this work, inspired by the kleptographic attacks introduced by Young and Yung in 1990s [Crypto’96], we initiate a formal study of asymmetric subversion attacks against signature schemes. Our contributions can be summarized as follows.We provide a formal definition of asymmetric subversion model for signature schemes. Our asymmetric model improves the existing symmetric subversion model proposed by Ateniese, Magri and Venturi [CCS’15] in the sense that the undetectability is strengthened and the signing key recoverability is defined as a strong subversion attack goal.We introduce a special type of signature schemes that are splittable and show how to universally mount the subversion attack against such signature schemes in the asymmetric subversion model. Compared with the symmetric attacks introduced by Ateniese, Magri and Venturi [CCS’15], our proposed attack enables much more efficient key recovery that is independent of the signing key size.Our asymmetric subversion framework is somewhat conceptually simple but well demonstrates that subversion attacks against signature schemes could be quite practical, and thus increases awareness and spurs the search for deterrents.

Cloud storage auditing is a crucial service that provides integrity checking for clients’ data in the cloud server. However, if the client’s auditing secret key is exposed, the malicious cloud server can tamper even throw away the client’s data without being detected. In this paper, we propose an intrusion-resilient public auditing protocol that can reduce the damage caused by key exposure. In our protocol, the auditing secret key is managed by the client with the help of a third party auditor (TPA), who cannot compute the client’s auditing secret key. Our protocol divides the lifetime of file stored on cloud into several time periods, and each time period is further divided into several refreshing periods. We show that our protocol is secure (i.e., backward security and forward security) against the adversary as long as the client and TPA are compromised in different refreshing period. Our protocol still captures the forward security when the client and TPA are compromised in the same refreshing period.

Computation outsourcing is a vital cloud service that can be provided for users. Using the cloud to address complex computations is crucial to users with lightweight devices. However, computations may not be correctly executed by the cloud due to monetary reasons. In this paper, we propose a secure publicly verifiable computation scheme in cloud computing, which is designed based on the polynomial commitment. Owing to the public key de-commitment of the polynomial commitment, our scheme can provide public verifiability for computation results. Security analysis shows that the proposed scheme is correct and can support public verifiability. Comparison and simulation results reveal that our scheme can be performed with low computational cost compared to previous schemes.

It has been widely recognized as a challenge to carry out data analysis and meanwhile preserve its privacy in the cloud. In this work, we mainly focus on a well-known data analysis approach namely association rule mining. We found that the data privacy in this mining approach have not been well considered so far. To address this problem, we propose a scheme for privacy-preserving association rule mining on outsourced cloud data which are uploaded from multiple parties in a twin-cloud architecture. In particular, we mainly consider the scenario where the data owners and miners have different encryption keys that are kept secret from each other and also from the cloud server. Our scheme is constructed by a set of well-designed two-party secure computation algorithms, which not only preserve the data confidentiality and query privacy but also allow the data owner to be offline during the data mining. Compared with the state-of-art works, our scheme not only achieves higher level privacy but also reduces the computation cost of data owners.

In PKC’08, Plantard, Susilo and Win proposed a lattice-based signature scheme, whose security is based on the hardness of the closest vector problem with the infinity norm (CVP$$_\infty $$). This signature scheme was proposed as a countermeasure against the Nguyen-Regev attack, which improves the security and the efficiency of the Goldreich, Goldwasser and Halevi scheme (GGH). Furthermore, to resist potential side channel attacks, the authors suggested modifying the deterministic signing algorithm to be randomized. In this paper, we propose a chosen message attack against the randomized version. Note that the randomized signing algorithm will generate different signature vectors in a relatively small cube for the same message, so the difference of any two signature vectors will be relatively short lattice vector. Once collecting enough such short difference vectors, we can recover the whole or the partial secret key by lattice reduction algorithms, which implies that the randomized version is insecure under the chosen message attack.

Key Exchange (KE) from RLWE (Ring-Learning with Errors) is a potential alternative to Diffie-Hellman (DH) in a post quantum setting. Key leakage with RLWE key exchange protocols in the context of key reuse has already been pointed out in previous work. The initial attack described by Fluhrer is designed in such a way that it only works on Peikert’s KE protocol and its variants that derives the shared secret from the most significant bits of the approximately equal keys computed by both parties. It does not work on Ding’s key exchange that uses the least significant bits to derive a shared key. The Signal leakage attack relies on changes in the signal sent by the responder reusing his key, in a sequence of key exchange sessions initiated by an attacker with a malformed key. A possible defense against this attack would be to require the initiator of a key exchange to send the signal, which is the one pass case of the KE protocol. In this work, we describe a new attack on Ding’s one pass case without relying on the signal function output but using only the information of whether the final key of both parties agree. We also use LLL reduction to create the adversary’s keys in such a way that the party being compromised cannot identify the attack in trivial ways. This completes the series of attacks on RLWE key exchange with key reuse for all variants in both cases of the initiator and responder sending the signal. Moreover, we show that the previous Signal leakage attack can be made more efficient with fewer queries and how it can be extended to Peikert’s key exchange, which was used in the BCNS implementation and integrated with TLS and a variant used in the New Hope implementation.

Extension Field Cancellation (EFC) was proposed by Alan et al. at PQCrypto 2016 as a new trapdoor for constructing secure multivariate encryption cryptographic schemes. Along with this trapdoor, two schemes $$\text {EFC}_p^{-}$$ and $$\text {EFC}_{pt^2}^{-}$$ that apply this trapdoor and some modifiers were proposed. Though their security seems to be high enough, their decryption efficiency has room for improvement. In this paper, we introduce a new and more efficient decryption approach for $$\text {EFC}_p^{-}$$ and $$\text {EFC}_{pt^2}^{-}$$, which manages to avoid all redundant computation involved in the original decryption algorithms, and theoretically speed up the decryption process of $$\text {EFC}_p^{-}$$ and $$\text {EFC}_{pt^2}^{-}$$ by around 3.4 and 8.5 times, respectively, under 128-bit security parameters with our new designed private keys for them. Meanwhile, our approach does not interfere with the public key, so the security remains the same. The implementation results of both decryption algorithms for $$\text {EFC}_p^{-}$$ and $$\text {EFC}_{pt^2}^{-}$$ are also provided.

Universal accumulator provides a way to accumulate a set of elements into one. For each element accumulated, it can provide a short membership (resp. nonmembership) witness to attest the fact that the element has been (resp. has not been) accumulated. When combined with a suitable zero-knowledge proof system, it can be used to construct many privacy-preserving applications. However, existing universal accumulators are usually based on non-standard assumptions, e.g., the Strong RSA assumption and the Strong Diffie-Hellman assumptions, and are not secure against quantum attacks. In this paper, we propose the first lattice-based universal accumulator from standard lattice-based assumptions. The starting point of our work is the lattice-based accumulator with Merkle-tree structure proposed by Libert et al. (Eurocrypt’16). We present a novel method to generate short witnesses for non-accumulated members in a Merkle-tree, and give the construction of universal accumulator. Besides, we also propose the first zero-knowledge arguments to prove the possession of the nonmembership witness of a non-accumulated value in the lattice-based setting via the abstract Stern’s protocol of Libert et al. (Asiacrypt’17). Moreover, our proposed universal accumulator can be used to construct many privacy-preserving cryptographic primitives, such as group signature and anonymous credential.

Dual receiver encryption (DRE), proposed by Diament et al. at ACM CCS 2004, is a special extension notion of public-key encryption, which enables two independent receivers to decrypt a ciphertext into a same plaintext. This primitive is quite useful in designing combined public key cryptosystems and denial of service attack-resilient protocols. Up till now, a series of DRE schemes are constructed with bilinear pairing groups. In this work, we introduce the first construction of lattice-based DRE. Our scheme is secure against chosen-ciphertext attacks from the standard Learning with Errors (LWE) assumption with a public key of bit-size about $$2nm\log q$$, where m and q are small polynomials in n. Additionally, for the DRE notion in the identity-based setting, identity-based DRE (ID-DRE), we also give a lattice-based ID-DRE scheme that achieves chosen-plaintext and adaptively chosen identity security based on the LWE assumption with public parameter size about $$(2\ell +1)nm\log q$$, where $$\ell $$ is the bit-size of the identity in the scheme.

An Identity-Based Hash Proof System (IB-HPS) is a fundamental and important primitive, which is widely adapted to construct a number of cryptographic schemes and protocols, especially for leakage-resilient ones. Therefore it is significant to instantiate IB-HPSs from various assumptions. However, all existing IB-HPSs based on lattices are set only in the random oracle model. Thus, proposing an IB-HPS from lattices in the standard model is an essential and interesting work.In this paper, we introduce a much more compact definition for an anonymous IB-HPS, defining computational indistinguishability of valid/invalid ciphertexts and anonymity of identity simultaneously. Then, through utilizing the technique for delegating a short lattice basis due to Agrawal et al. in CRYPTO 2010 and the property of the smoothing parameter over random lattices, we present a new construction of IB-HPS in the standard model. Furthermore, we show that our new construction is selectively secure and anonymous based on the standard learning with errors (LWE) assumption in the standard model.

In this paper, we construct a Lattice-based one-time Linkable Ring Signature (L2RS) scheme, which enables the public to verify if two or more signatures were generated by same signatory, whilst still preserving the anonymity of the signatory. The L2RS provides unconditional anonymity and security guarantees under the Ring Short Integer Solution (Ring-SIS) lattice hardness assumption. The proposed L2RS scheme is extended to be applied in a protocol that we called Lattice Ring Confidential transaction (Lattice RingCT) v1.0, which forms the foundation of the privacy-preserving protocol in any post-quantum secure cryptocurrency such as Hcash.

A contactless payment lets a card holder execute payment without any interaction (e.g., entering PIN or signing) between the terminal and the card holder. Even though the security is the first priority in a payment system, the formal security model of contactless payment does not exist. Therefore, in this paper, we design an adversarial model and define formally the contactless-payment security against malicious cards and malicious terminals including relay attacks. Accordingly, we design a contactless-payment protocol and show its security in our security model. At the end, we analyze EMV-contactless which is a commonly used specification by most of the mobile contactless-payment systems and credit cards in Europe. We find that it is not secure against malicious cards. We also prove its security against malicious terminals in our model. This type of cryptographic proof has not been done before for the EMV specification.

Anonymous Distance-Bounding (DB) protocols allow a prover to convince a verifier that they are within a distance bound from the verifier, without revealing their identity. This is an attractive property that enables the prover to enjoy proximity based services while preserving their privacy. Combination of anonymity and distance-bounding however introduces new security challenges. We show two new realistic attacks, using directional antenna and the collusion of multiple users, that breaks all existing anonymous DB protocols, and propose a new security model that captures these new attacks. We construct a protocol with provable security in this new model and discuss directions for future research.

Bug-tracking systems are widely used by software developers to manage bug reports. Since it is time-consuming and costly to fix all the bugs, developers usually pay more attention to the bugs with higher impact, such as security bugs (i.e., vulnerabilities) which can be exploited by malicious users to launch attacks and cause great damages. However, manually identifying security bug reports from millions of reports in bug-tracking systems is difficult and error-prone. Furthermore, existing automated identification approaches to security bug reports often incur many false negatives, causing a hidden danger to the computer system. To address this important problem, we present an automatic security bug reports identification model via multitype features analysis, dubbed Security Bug Report Identifier (SBRer). Specifically, we make use of multiple kinds of information contained in a bug report, including meta features and textual features, to automatically identify the security bug reports via natural language processing and machine learning techniques. The experimental results show that SBRer with imbalanced data processing can successfully identify the security bug reports with a much higher precision of 99.4% and recall of 79.9% compared to existing work.

Cognitive radio technique is regarded as a promising way for allowing secondary users (SUs) to access available channels without introducing the interference to the primary users (PUs). However, database-driven cognitive radio networks (CRNs) are facing a series of security and privacy threats, especially the privacy breaches of SUs. To address this issue, this paper proposes a practical privacy-preserving protocol for database-driven CRNs that allows SUs to get the available channels in their vicinity efficiently while protecting their privacy. Our protocol takes advantage of modular square root technique to verify the identity of a SU and enables a legitimate SU to obtain the available channel without leaking its privacy. By prefetching channels, our protocol reduces the latency of obtaining available channels for SUs. Besides, the proposed protocol provides strong privacy preservation that the database cannot trace any SUs and get nothing about location or identity information of SUs, even the database colludes with all base stations. The results of security analysis and performance evaluation indicate the feasibility and practicality of the proposed privacy-preserving protocol.

Software defined network (SDN) is the key part of the next generation networks. Its central controller enables the high programmability and flexibility. However, SDN can be easily disrupted by a new DDoS attack which triggers enormous Packet_IN messages. Since the existing solutions focus on checking current network states with content feature to detect the attack, they can possibly be misled. In this paper, we propose a detection and defense scheme against the DDoS attack based on the time feature. Specifically, the time feature is the hit rate gradient of the flow table. We first extract the temporal behavior of an attack. A back propagation neural network is trained to extract an attack pattern and used to recognize an attack. Then either a defense or recovery action will be taken. We test our scheme with the DARPA 1999 intrusion detection data set and compare our scheme with another method using sequential probability ratio test (SPRT). The experiment and evaluation show that our scheme enables the real-time detection, effective defense and quick recovery from DDoS attacks.

Transactions using the Bitcoin system, which is built atop a novel blockchain technology where miners run distributed consensus to ensure the security, will cause relatively high transaction costs to incentivize miners to behave honestly. Besides, a transaction should wait a quite long time (about 10 min on average) before being confirmed on the blockchain, which makes micropayments not cost-effective. In CCS’15, Pass and shelat proposed three novel micropayment schemes for any ledger-based transaction system, using the idea of probabilistic payments suggested by Wheeler (1996) and Rivest (1997), which are called as the “Lottery-based Micropayments”. However, the one among the three schemes, which is fully compatible with the current Bitcoin system and only requires an “invisible” verifiable third party, needs two on-chain transactions during each execution, even if both the user and the merchant are honest. To reduce the transaction costs and increase efficiency, this paper proposes a fast lottery-based micropayment scheme to improve their work. By setting up a time-locked deposit, whose secure utilization is assured by the security of a primitive called accountable assertions under the discrete logarithm assumption, our scheme reduces the number of on-chain transactions to one, and yet maintains the original scheme’s advantages.

Decentralized ledger-based cryptocurrencies like Bitcoin present a way to construct payment systems without trusted banks. However, the anonymity of Bitcoin is fragile. Many altcoins and protocols are designed to improve Bitcoin on this issue, among which Zerocash is the first full-fledged anonymous ledger-based currency, using zero-knowledge proof, specifically zk-SNARK, to protect privacy. However, Zerocash suffers two problems: poor scalability and low efficiency. In this paper, we address the above issues by constructing a micropayment system in Zerocash called Z-Channel. First, we improve Zerocash to support multisignature and time lock functionalities, and prove that the reconstructed scheme is secure. Then we construct Z-Channel based on the improved Zerocash scheme. Our experiments demonstrate that Z-Channel significantly improves the scalability and reduces the confirmation time for Zerocash payments.

Recently, due to the inherent restriction of Bitcoin design, the throughput of Bitcoin blockchain protocol fails to meet the daily needs, leaving the scalability technology in dire need to provide better efficiency. To address this issue, numerous solutions have been proposed, including blocksize expansion, off-chain transactions and block structure modification. Among them, Bitcoin-NG, a scalable blockchain protocol introduced by Eyal et al. in USENIX 2016, improves scalability while simultaneously avoiding the deterioration of other metrics in the network. Bitcoin-NG has two types of blocks: key blocks for leader election and microblocks that contain ledger entries. Eyal et al. assert that the proportion of fee allocation of transactions in microblocks is bounded by miners’ mining power ratio out of all mining power in the system. Specifically, the upper bound is determined by the incentive sub-mechanism of longest chain extension, while the lower bound determined by the incentive sub-mechanism of transaction inclusion. We revisit the incentive mechanism of Bitcoin-NG. We point out that Eyal et al. neglect on the calculation of lower bound and manifest the over-simplification in the analysis of upper bound in detail. After that, the correct incentive mechanism is derived. Finally, we put forward an optimal proportion of transaction fee distribution.

Blacklistable anonymous credential systems provide service providers with a way to authenticate users according to their historical behaviors, while guaranteeing that all users can access services in an anonymous and unlinkable manner, thus are potentially useful in practice. Traditionally, to protect services from illegal access, the credential issuer, which completes the registration with users, must be trusted by the service provider. However, in practice, this trust assumption is usually unsatisfied.In this paper, we solve this problem and present the decentralized blacklistable anonymous credential system with reputation (DBLACR), which inherits nearly all features of the BLACR system presented in Au et.al. (NDSS’12) but does not need a trusted party to register users. The new system also has extra advantages. In particular, it enables blacklist (historical behaviors) sharing among different service providers and is partially resilient to the blacklist gaming attack, where dishonest service providers attempt to compromise the privacy of users via generating blacklist maliciously.Technically, the main approach to achieve DBLACR system is a novel use of the blockchain technique, which serves as a public append-only ledger. The system can be instantiated from three different types of cryptographic systems, including the RSA system, the classical DL system, and the pairing based system. To demonstrate the practicability of our system, we also give a proof of concept implementation for the instantiation under the RSA system. The experiment results indicate that when authenticating with blacklists of reasonable size, our implementation can fulfill practical efficiency demands.

The user revocation of certificateless cryptosystems is an important issue. One of the existing solutions is to issue extra time keys periodically for every non-revoked user. However, since the scheme requires different time keys to decrypt data for different time periods, the user needs to hold a long list of time keys (linear growth with time), which is inefficient in practical applications. Moreover, the ciphertexts produced before revocation are still available to the revoked users, which is not acceptable in most applications such as cloud storage. To overcome these shortcomings, in this paper, we present an efficient solution called revocable certificateless encryption with ciphertext evolution. In our scheme, a current time key together with a private key are enough for the decryptions by non-revoked users. Meanwhile, revoked users cannot make decryptions on ciphertexts in the past any more. We give formal security proofs based on the IND-CPA model under the standard BDH problem.

We propose a rank metric codes based encryption based on the hard problem of rank syndrome decoding problem. We distort the matrix used for our encryption by adding a random distortion matrix over $$\mathbb {F}_{q^m}$$. We show that IND-CPA security is achievable for our encryption under assumption of Decisional Rank Syndrome Decoding problem. Our proposal allows the choice of the error terms with rank up to r/2, where r is the error-correcting capability of a code. Our encryption based on Gabidulin codes has public key size of 13.68 KB, which is 82 times smaller than the public key size of McEliece Cryptosystem based on Goppa codes. For similar post-quantum security level of $$2^{140}$$ bits, our encryption scheme has smaller public key size than key size suggested by LOI17 Encryption [7].

To construct an intelligent alarm filter is a promising solution to help reduce false alarms for an intrusion detection system (IDS), in which an appropriate algorithm can be selected in an adaptive way. Taking the advantage of cloud computing, the process of algorithm selection can be offloaded to the cloud, but it may cause communication delay and additional burden on the cloud side. This issue may become worse when it comes to distributed intrusion detection systems (DIDSs), i.e., some IoT applications might require very short response time and most of the end nodes in IoT are energy constrained things. In this paper, with the advent of edge computing, we propose a framework for improving the intelligent false alarm reduction for DIDSs based on edge computing devices (i.e., the data can be processed at the edge for shorter response time and could be more energy efficient). The evaluation shows that the proposed framework can help reduce the workload for the central server and shorten the delay as compared to the similar studies.

Through memory vulnerabilities, control flow hijacking allows an attacker to force a running program to execute other than what the programmer has intended. Control Flow Integrity (CFI) aims to prevent the adversarial effects of these attacks. CFI attempts to enforce the programmer’s intent by ensuring that a program only runs according to a control flow graph (CFG) of the program. The enforced CFG can be built statically or dynamically, and Per-Input Control Flow Integrity (PICFI) represents a recent advance in dynamic CFI techniques. PICFI begins execution with the empty CFG of a program and lazily adds edges to the CFG during execution according to concrete inputs. However, this CFG grows monotonically, i.e., edges are never removed when corresponding control flow transfers become illegal. This paper presents LPCFI, Live Path Control Flow Integrity, to more precisely enforce forward edge CFI using a dynamically computed CFG by both adding and removing edges for all indirect control flow transfers from indirect callsites, thereby raising the bar against control flow hijacking attacks.

At ACISP 2017, Wu et al. provided an identity-based encryption scheme with equality test that considers to prevent insider attacks. In this paper, we demonstrate that their scheme does not achieve the claimed security requirement by presenting an attack. Subsequently, we provide a modification of their construction.

In this paper, we propose a simple method to improve the BKZ algorithm with small blocksize. At first, we observe that reordering the LLL-reduced basis vectors by increasing norm will change the distribution of search nodes in the enumeration tree, which gives a chance to reduce the enumeration search nodes with non-negligible probability. Thus the runtime of enumeration algorithm is accelerated approximately by a factor of two. We explain this phenomenon from a theoretical point of view, which follows the Gama-Nguyen-Regev’s analysis [6]. Then we apply this reordering technique on the BKZ algorithm and implement it in the open source library NTL. Our experimental results in dimensions 100–120 with blocksize 15–30 show that on LLL-reduced bases, our modified NTL-BKZ outputs a vector shorter than the original NTL-BKZ with probability 40%–46% with LLL Lovász constant $$\delta _{LLL}=0.99$$. Furthermore, in the instances where the improved BKZ found a same or shorter vector, the runtime is up to 2.02 times faster when setting the blocksize $$\beta =25$$ with $$\delta _{LLL}=0.99$$.

Malware developers often use various obfuscation techniques to generate polymorphic and metamorphic versions of malwares. Keeping up with new variants and creating signatures for each individuals in a timely fashion has been an important problem but tedious works that anti-virus companies face all the time. It motivates us the idea of no more dancing with variants. In this paper, we aim to find a malware family’s main characteristic operations directly related to its intent. We propose global execution sequence alignment and segmentation algorithms to generate the execution stage chart of a malware family which presents a simple and easy-to-understand overview of the lifecycle as well as common and different operations that individual variants perform at a stage. We also present an automated dynamic Android malware profiling and family security analysis system in which we focus on the execution sequences of sensitive and permission-related API calls referred to as motifs of variants of malware family. To achieve the goal, we modify Android Debug Bridge (ADB) tool to add on several new features including enabling the recording of parameters and return value of an API call, the support of UID-based profiling to capture all the processes and threads to gain complete understanding of the activities of target malware app, and per thread trace generation. Finally, we use real-world dataset to validate the proposed system and methods. The generated family stage chart and motifs can provide security analysts semantics-rich understanding of what and how a malware family is designed and implemented. The main characteristic API call sequences of malware families can be used as signatures for effective and efficient malware detection in the future.

In this paper, we utilize the recent advances in indistinguishability obfuscation, overcome several obstacles and propose a multi-hop unidirectional proxy re-encryption scheme. The proposed scheme is proved to be CCA-secure in the standard model (i.e., without using the random oracle heuristic), and its ciphertext remains constant-size regardless of how many times it has been transformed.

In this paper, we present a new lattice-based signature scheme, $$\text {PASS}_{G}$$, based on signatures from the partial Fourier recovery problem $$\text {PASS}_{RS}$$ introduced by Hoffstein et al. in 2014. Same as $$\text {PASS}_{RS}$$, security of our construction relies on the average-case hardness of a special kind of Short Integer Solution (SIS) problem and the hardness of partial Fourier recovery problem. $$\text {PASS}_{G}$$ improves $$\text {PASS}_{RS}$$ in two aspects. Firstly, unlike $$\text {PASS}_{RS}$$, $$\text {PASS}_{G}$$ comes with a reduction proof and is thus provably secure. Secondly, we adopt rejection sampling technique introduced by Lyubashevsky in 2008 to reduce the signature size and improve the efficiency. More concretely, signatures of $$\text {PASS}_{G}$$ are Gaussian-distributed and is more space efficient. We also present another security parameter set based on best known attack using BKZ 2.0 algorithm introduced by Chen and Nguyen in 2011.

Key Predistribution Schemes (KPS) are efficient key management solutions that are well suited to establish lightweight symmetric keys even in resource starved environments, like low cost Internet of Things (IoT). This paper uses Chinese Remainder Theorem (CRT) to propose an energy efficient and deterministic KPS for distributed ad hoc networks, that we name as CRT-KPS. We theoretically establish the effectiveness of CRT-KPS in term of crucial metrics. Comparative study establishes that our proposals have better balance in overall performance as compared to state-of-the-art schemes and should find wide applications in IoT systems (specially for resource starved end devices).