Provable and Practical Security

Group signature is a central tool for privacy-preserving protocols, ensuring authentication, anonymity and accountability. It has been massively used in cryptography, either directly or through variants such as direct anonymous attestations. However, it remains a complex tool, especially if one wants to avoid proving security in the random oracle model.

In this work, we propose a new group signature scheme proven secure without random oracles which significantly decreases the complexity in comparison with the state-of-the-art. More specifically, we halve both the size and the computational cost compared to the most efficient alternative in the same model. Moreover, our construction is also competitive against the most efficient ones in the random oracle model.

Our construction is based on a tailored combination of two popular signatures, which avoids the explicit use of encryption schemes or zero-knowledge proofs while signing. It is flexible enough to achieve security in different models and is thus suitable for most contexts.

One important property of group signatures is forward-security, which prevents an attacker in possession of a group signing key to forge signatures produced in the past. In case of exposure of one group member’s signing key, group signatures lacking forward-security need to invalidate all group public and secret keys (by re-initializing the whole system) but also invalidate all previously issued group signatures. Most of the existing forward-secure group signatures (FS-GS) are built from number-theoretic security assumptions which are vulnerable to quantum computers. The only post-quantum secure FS-GS scheme is built from lattices by Ling et al. (PQCrypto 19) in the random oracle model, following the classical framework of encrypt-then-prove, thus using non-interactive zero-knowledge (NIZK) proofs. In this work, we achieve the first FS-GS from lattices in the standard model. Our starting point is the group signature of Katsumada and Yamada (Eurocrypt 19) which replaces NIZK by attribute-based signatures (ABS), thus removing the need for random oracles. We first modify the underlying ABS of Tsabary (TCC 17) to equip it with forward-security property. We then prove that by plugging it back in the group signature framework of Katsumada and Yamada (Eurocrypt 19), we can design a FS-GS scheme secure in the standard model with public key and signature size constant in the number of users. Our constant size is achieved by relying on complexity leveraging, which further implies relying on the subexponential hardness of the Short Integers Solution (SIS) assumption.

In this paper, we propose a first lattice-based multisignature scheme whose security is proven in QROM. The difficultly of proving the security in QROM than CROM is how to program the random oracle in the security proof. Although our proposed scheme is based on the Dilithium-QROM signature whose security is proven in QROM, their proof technique cannot be directly applied to the multisignature setting. To solve the problems in the security proof, we develop several proof techniques in QROM. First, we employ the searching query technique by Targi and Unruh to convert the Dilithium-QROM into the multisignature setting. For the second, we develop a new programming technique in QROM, since the conventional programming techniques seem not to work in the multisignature setting of QROM. We combine the programming technique by Unruh with the one by Liu and Zhandry. The new technique enables us to program the random oracle in QROM and to construct the signing oracle in the security proof.

Most aggregate signature schemes are relying on pairings, but high computational and storage costs of pairings limit the feasibility of those schemes in practice. Zhao proposed the first pairing-free aggregate signature scheme (AsiaCCS 2019). However, the security of Zhao’s scheme is based on the hardness of a newly introduced non-standard computational problem. The recent impossibility results of Drijvers et al. (IEEE S&P 2019) on two-round pairing-free multi-signature schemes whose security based on the standard discrete logarithm (DL) problem has strengthened the view that constructing a pairing-free aggregate signature scheme which is proven secure based on standard problems such as DL problem is indeed a challenging open problem.

In this paper, we offer a novel solution to this open problem. We introduce a new paradigm of aggregate signatures, i.e., aggregate signatures with an additional pre-communication stage. In the pre-communication stage, each signer interacts with the aggregator to agree on a specific random value before deciding messages to be signed. We also discover that the impossibility results of Drijvers et al. apply if the adversary can decide the whole randomness part of any individual signature. Based on the new paradigm and our discovery of the applicability of the impossibility result, we propose a pairing-free aggregate signature scheme such that any individual signature includes a random nonce which can be freely generated by the signer. We prove the security of our scheme based on the hardness of the standard DL problem. As a trade-off, in contrast to the plain public-key model, which Zhao’s scheme uses, we employ a more restricted key setup model, i.e., the knowledge of secret-key model.

We propose new short signature schemes under the ring-SIS assumption in the standard model. Specifically, by revisiting an existing construction in [Ducas and Micciancio, CRYPTO 2014], we demonstrate efficient lattice-based signatures with improved tag generation. We firstly construct a scheme under mild security condition that is existentially unforgeable against random message attack with auxiliary information. We then convert the mildly secure scheme to a fully secure scheme by applying a trapdoor commitment scheme. Our schemes enable the generation of tags from messages and the collision of multiple tags, which improves reduction loss. Our schemes have short signature sizes of O(1) and achieves tighter reduction loss than that of Ducas et al.’s scheme. In accordance with two kinds of parameter set for tag generation, we get two signature schemes with different properties of reduction loss and verification key size. One of our schemes has tighter reduction and as the same size verification key of \(O(\log n)\) as that of Ducas et al.’s scheme, where n is the security parameter. Another scheme achieves much tighter reduction loss of \(O(\frac{Q}{n})\) for the sake of verification size of O(n), where Q is the number of signing queries.

Delegation of signing rights can be useful to promote effective resource sharing and smooth cooperation among participants in distributed systems, and in many situations, we often need restricted delegation such as one-timeness and unlinkability rather than simple full delegation. Particularly, one-timesness cannot be achieved just by deploying cryptographic measures, and one needs to resort to some form of tamper-proofness or the assistance from external cloud servers for “key-disabling”. In this work, we extend the latter such that a delegatee can sign a message without the delegator’s involvement with the assumption that there exists at least one honest cloud server with secure erasure to achieve one-timeness. In this setting, if the delegator just shares their signing key between the delegatee and cloud servers, it may be problematic. It is because in the worst case, the delegator cannot know whether or not a signing key theft occurred because the signatures generated illegally are indistinguishable from the ones generated legally. To solve this, first we propose an efficient one-time delegation scheme of Okamoto-Schnorr signing. Further we combine the basic delegation scheme with anonymous credentials such that the delegator can detect the signing key theft even if one-time delegation is broken while also achieving unlinkability for both the delegator and cloud servers. Further we show its application to an e-cash scheme, which can prevent double-spending.

Software watermarking enables one to embed some information called “mark” into a program while preserving its functionality, and to read it from the program. As a definition of function preserving, Cohen et al. (STOC 2016) proposed statistical function preserving which requires that the input/output behavior of the marked circuit is identical almost everywhere to that of the original unmarked circuit. They showed how to construct watermarkable cryptographic primitives with statistical function preserving, including pseudorandom functions (PRFs) and public-key encryption from indistinguishability obfuscation. Recently, Goyal et al. (CRYPTO 2019) introduced more relaxed definition of function preserving for watermarkable signature. Watermarkable signature embeds a mark into a signing circuit of digital signature. The relaxed function preserving only requires that the marked signing circuit outputs valid signatures. They provide watermarkable signature with the relaxed function preserving only based on (standard) digital signature.

Nowadays, the use of database outsourcing is on the rise. Since the service provider may not be fully trusted, a crucial requirement in outsourced data sharing is therefore to ensure that users can verify the integrity and authenticity of their query results. In outsourced healthcare data sharing, because the data contains sensitive information, an equally significant issue is to guarantee that the sharing process does not lead to any information leakages. Though some privacy-preserving authentication solutions have been presented to address these issues, unfortunately, none of them consider the risk of privacy leakage during the dissemination of authenticated healthcare data. That is, the queried data may be leaked by the user since any third party getting hold of a signed data would be convinced of its validity. In other words, for privacy concerns, we need a secure mechanism to ensure that only a specific receiver can check the integrity and authenticity of shared outsourced data.

To address the these concerns, in our work, we propose a privacy-preserving authentication scheme with designated verification for tree-structured data (i.e., XML-based healthcare records). We provide the formal definition and related security properties of our scheme. We further put forward our concrete construction and prove its security under the standard cryptographic assumption in the random oracle model. The comparison analysis of theory and practice shows that our scheme provides stronger privacy protection than existing schemes while having the shortest key length and signature size. Therefore, our construction is efficient and practical for outsourced environments.

In this work, we introduce the notion of puncturable witness pseudorandom function (pWPRF) which is a stronger variant of WPRF proposed by Zhandry, TCC 2016. The punctured technique is similar to what we have seen for puncturable PRFs and is capable of extending the applications of WPRF. Specifically, we construct a semi-adaptively secure offline witness encryption (OWE) scheme using a pWPRF, an indistinguishability obfuscation (\(i\mathcal {O}\)) and a symmetric-key encryption (SKE), which enables us to encrypt messages along with NP statements. We show that replacing \(i\mathcal {O}\) with extractability obfuscation, the OWE turns out to be an extractable offline witness encryption scheme. To gain finer control over data, we further demonstrate how to convert our OWEs into offline functional witness encryption (OFWE) and extractable OFWE. All of our OWEs and OFWEs produce an optimal size ciphertext, in particular, encryption of a message is as small as the size of the message plus the security parameter multiplied with a constant, which is optimal for any public-key encryption scheme. On the other hand, in any previous OWE, the size of a ciphertext increases polynomially with the size of messages. Finally, we show that the WPRF of Pal et al. (ACISP 2019) can be extended to a pWPRF and an extractable pWPRF.

This work presents a new experiment defining indistinguishability for searchable symmetric encryption to include security against published practical attacks. The proposed experiment allows the adversaries to use their prior knowledge about the stored documents to win. We solve the problem of modelling the adversaries with prior knowledge using the interacting split adversary technique. This new indistinguishability definition is aligned with the security goals and adversary capabilities listed in  [4]. The correctness of the indistinguishability experiment is demonstrated by presenting proofs of strength and vulnerabilities of \(\varSigma {o} \phi {o} \varsigma \)-B and one of its variant. We write the security proofs based on the indistinguishability experiment with an adversary without any prior knowledge and adversary with full knowledge of the document set. We show how to win the indistinguishability experiment using the count attack by an adversary who knows the document distribution, and the file injection attack by an adversary without prior knowledge.

Receiver selective opening (RSO) attacks for public key encryption (PKE) capture a situation where one sender sends messages to multiple receivers, and an adversary can corrupt a set of receivers and get their messages and secret keys. Security against RSO attack for a PKE scheme ensures confidentiality of other uncorrupted receivers’ ciphertexts. Among all of the RSO security notions, simulation-based RSO security against chosen ciphertext attack (SIM-RSO-CCA security) is the strongest notion. In this paper, we explore constructions of SIM-RSO-CCA secure PKE from various computational assumptions. Toward this goal, we show that a SIM-RSO-CCA secure PKE scheme can be constructed based on an IND-CPA secure PKE scheme and a designated-verifier non-interactive zero-knowledge (DV-NIZK) argument satisfying one-time simulation soundness. Moreover, we give the first construction of DV-NIZK argument satisfying one-time simulation soundness. Consequently, through our generic construction, we obtain the first SIM-RSO-CCA secure PKE scheme under the computational Diffie-Hellman (CDH) or learning parity with noise (LPN) assumption.

We propose a novel non-interactive zero-knowledge (NIZK) argument for confidential transactions. Our NIZK argument provides a highly practical prover against other existing works, in which proof generation and verification times are at the same level. Our NIZK argument is perfect zero-knowledge in the common reference string model, with its soundness holds in the random oracle model. Based on the NIZK argument, we construct a confidential transaction smart contract (CTSC) scheme which enables transferring coins between users confidentially and automatically over the account-model blockchain. Furthermore, We provide a formal security definitions of such a primitive: confidentiality and transaction soundness, along with a security proof of the construction.

The linear stochastic multi-armed bandit is a sequential learning setting, where, at each round, a learner chooses an arm and receives a stochastic reward based on an unknown linear function of the chosen arm. The goal is to collect as much reward as possible. Linear bandits have popular applications such as online recommendation based on user preferences, where obtaining a high reward means recommending an item with high expected rating. We address the security concerns that occur when outsourcing the data and the cumulative reward maximization algorithm to an honest-but-curious cloud. We propose LinUCB-DS, a distributed and secure protocol that achieves the same cumulative reward as the standard LinUCB algorithm, without disclosing to the cloud the linear function used to draw arm rewards. We formally prove the complexity and security properties of LinUCB-DS. We also show that LinUCB-DS can be easily adapted to secure the SpectralUCB algorithm, which improves LinUCB for a class of linear bandits. We show the feasibility of our protocols via a proof-of-concept experimental study using the MovieLens movie recommendation dataset.

The success of deep learning is largely due to the availability of big training data nowadays. However, data privacy could be a big concern, especially when the training or inference is done on untrusted third-party servers. Fully Homomorphic Encryption (FHE) is a powerful cryptography technique that enables computation on encrypted data in the absence of decryption key, thus could protect data privacy in an outsourced computation environment. However, due to its large performance and resource overheads, current applications of FHE to deep learning are still limited to very simple tasks. In this paper, we first propose a neural network training framework on FHE encrypted data, namely PrivGD. PrivGD leverages the Single-Instruction Multiple-Data (SIMD) packing feature of FHE to efficiently implement the Gradient Descent algorithm in the encrypted domain. In particular, PrivGD is the first to support training a multi-class classification network with double-precision float-point weights through approximated Softmax function in FHE, which has never been done before to the best of our knowledge. Then, we show how to apply FHE with transfer learning for more complicated real-world applications. We consider outsourced diagnosis services, as with the Machine-Learning-as-a-Service paradigm, for multi-class machine faults on machine sensor datasets under different operating conditions. As directly applying the source model trained on the source dataset (collected from source operating condition) to the target dataset (collect from the target operating condition) will lead to degraded diagnosis accuracy, we propose to transfer the source model to the target domain by retraining (fine-tuning) the classifier of the source model with data from the target domain. The target domain data is encrypted with FHE so that its privacy is preserved during the transfer learning process. We implement the secure transfer learning process with our PrivGD framework. Experiments results show that by fine-tuning a source model for fewer than 10 epochs with encrypted target domain data, the model can converge to an increased diagnosis accuracy by up to 20%, while the whole fine-tuning process takes approximate 3.85 h on our commodity server.

Secure computation is the technology that computes an arbitrary function represented as a circuit without revealing input values. Typical technologies related to secure computation are secure multiparty computation (MPC) that uses secret sharing (SS) schemes, for example, SS-MPC, garbled circuit (GC), and homomorphic encryption (HE). These cryptographic technologies have a trade-off relationship with respect to the computation cost, communication cost, and type of computable circuit. Hence, the optimal choice depends on the computing resources, communication environment, and function related to applications. The private decision tree evaluation (PDTE) is one of important applications of secure computation. There exist several PDTE protocols with constant communication rounds that use GC, HE, and SS-MPC over the field. However, to the best of our knowledge, PDTE protocols with constant communication rounds that use SS-MPC over the ring (requiring only lower computation costs and communication complexity) is non-trivial and still missing. In this paper, we propose a PDTE protocol that uses a secure three-party computation (3PC) protocol over the ring with one corruption.

With the emergence of quantum communication, it is of folkloric belief that the security of classical cryptographic protocols is automatically broken if the Adversary is allowed to perform superposition queries and the honest players forced to perform actions coherently on quantum states. Another widely held intuition is that enforcing measurements on the exchanged messages is enough to protect protocols from these attacks.

However, the reality is much more complex. Security models dealing with superposition attacks only consider unconditional security. Conversely, security models considering computational security assume that all supposedly classical messages are measured, which forbids by construction the analysis of superposition attacks. To fill in the gap between those models, Boneh and Zhandry have started to study the quantum computational security for classical primitives in their seminal work at Crypto’13, but only in the single-party setting. To the best of our knowledge, an equivalent model in the multiparty setting is still missing.

In this work, we propose the first computational security model considering superposition attacks for multiparty protocols. We show that our new security model is satisfiable by proving the security of the well-known One-Time-Pad protocol and give an attack on a variant of the equally reputable Yao Protocol for Secure Two-Party Computations. The post-mortem of this attack reveals the precise points of failure, yielding highly counter-intuitive results: Adding extra classical communication, which is harmless for classical security, can make the protocol become subject to superposition attacks. We use this newly imparted knowledge to construct the first concrete protocol for Secure Two-Party Computation that is resistant to superposition attacks. Our results show that there is no straightforward answer to provide for either the vulnerabilities of classical protocols to superposition attacks or the adapted countermeasures.

Achieving fairness and soundness in non-simultaneous rational secret sharing schemes has proved to be challenging. On the one hand, soundness can be ensured by providing side information related to the secret as a check, but on the other, this can be used by deviant players to compromise fairness. To overcome this, the idea of incorporating a time delay was suggested in the literature: in particular, time-delay encryption based on memory-bound functions has been put forth as a solution. In this paper, we propose a different approach to achieve such delay, namely using homomorphic time-lock puzzles (HTLPs), introduced at CRYPTO 2019, and construct a fair and sound rational secret sharing scheme in the non-simultaneous setting from HTLPs.

HTLPs are used to embed sub-shares of the secret for a predetermined time. This allows to restore fairness of the secret reconstruction phase, despite players having access to information related to the secret which is required to ensure the soundness of the scheme. Key to our construction is the fact that the time-lock puzzles are homomorphic so that players can compactly evaluate sub-shares. Without this efficiency improvement, players would have to independently solve each puzzle sent from the other players to obtain a share of the secret, which would be computationally inefficient. We argue that achieving both fairness and soundness in a non-simultaneous scheme using a time delay based on CPU-bound functions rather than memory-bound functions is more cost-effective and realistic in relation to the implementation of the construction.

Motivated by the need of catering for changes of security policy during the deployment of distribution of trust, threshold changeable secret sharing studies the construction of secret sharing schemes that have a built-in mechanism that, when activated, transforms the scheme into one with different access structures. By combining the two main techniques frequently used in previous constructions: packing and folding, we construct optimal threshold changeable ramp schemes that cover the full threshold change range, while known constructions either achieve only reconstruction threshold change or change both privacy and reconstruction thresholds but require the two thresholds to change proportionally. We justify the claim that the full threshold change range for which optimal schemes are possible is completely covered by proving a completeness result information-theoretically. The share size of these threshold changeable ramp schemes are much bigger than the lower bounds for plain ramp schemes (without requiring threshold changeability). This suggests the natural open question of understanding the share size lower and upper bounds for ramp schemes with built-in structures.

The National Institute of Standards and Technology (NIST) is working on the standardization of post-quantum algorithms. In February 2019, NIST announced 26 candidate post-quantum cryptosystems had entered the Round 2. Prior work has shown how to mount key recovery attacks on several candidates like FrodoKEM, NewHope, and Kyber, but their methods do not work for LAC, which uses a different encoding scheme and rounding method. To address this gap, we describe a powerful new attack on LAC. In particular, we propose a simple and effective method to recover the reused secret key of LAC.CPA. Following the method we show that, using the recommended parameters, thousands of queries are sufficient to recover the full secret key with a 100% probability, which is verified by experiments. Since LAC.KE is based on LAC.CPA, our method can be used to assess the key-reuse resilience of LAC.KE. In particular, if Alice reuses a secret key, Bob can recover it by communicating with Alice thousands of times. Since LAC is a Round 2 candidate in the NIST PQ process, the presented result may well have a high impact on the understanding of this important cryptosystem.

The National Institute of Standards and Technology (NIST) is working on the standardization of post-quantum algorithms. In February 2019, NIST announced 26 candidate post-quantum cryptosystems, including NewHope and LAC, had entered the second round. In order to investigate the resilience of various candidate algorithms in key reuse situations, a series of work has been carried out.

In fact, randomness also has the risk of reuse, and in the real word random number generators (RNGs) frequently fail and produce bad randomness. In this work, we assess the resilience of candidate NewHope-CPA-KEM and LAC.KE in randomness reuse situations. In particular, we propose a method, which can recover the reused randomness after several communications. NewHope-CPA-KEM and LAC.KE are based on NewHope-CPA-PKE and LAC.CPA, respectively. The key to our method is that they share a common feature: if public key satisfies certain conditions, the ciphertext will reveal information about the randomness of encryption. The recovered randomness can be used to attack another session where the same randomness is used.