Applied Cryptography and Network Security

Hierarchical ID-based authenticated key exchange (HID-AKE) is a cryptographic protocol to establish a common session key between parties with authentication based on their IDs with the hierarchical delegation of key generation functionality. All existing HID-AKE schemes are selective ID secure, and the only known standard model scheme relies on a non-standard assumption such as the q-type assumption. In this paper, we propose a generic construction of HID-AKE that is adaptive ID secure in the HID-eCK model (maximal-exposure-resilient security model) without random oracles. One of the concrete instantiations of our generic construction achieves the first adaptive ID secure HID-AKE scheme under the (standard) k-lin assumption in the standard model. Furthermore, it has the advantage that the computational complexity of pairing and exponentiation operations and the communication complexity do not depend on the depth of the hierarchy. Also, the other concrete instantiation achieves the first HID-AKE scheme based on lattices (i.e., post-quantum).

Time-stamping services produce time-stamp tokens as evidences to prove that digital data existed at given points in time. Time-stamp tokens contain verifiable cryptographic bindings between data and time, which are produced using cryptographic algorithms. In the ANSI, ISO/IEC and IETF standards for time-stamping services, cryptographic algorithms are addressed in two aspects: (i) Client-side hash functions used to hash data into digests for nondisclosure. (ii) Server-side algorithms used to bind the time and digests of data. These algorithms are associated with limited lifespans due to their operational life cycles and increasing computational powers of attackers. After the algorithms are compromised, time-stamp tokens using the algorithms are no longer trusted. The ANSI and ISO/IEC standards provide renewal mechanisms for time-stamp tokens. However, the renewal mechanisms for client-side hash functions are specified ambiguously, that may lead to the failure of implementations. Besides, in existing papers, the security analyses of long-term time-stamping schemes only cover the server-side renewal, and the client-side renewal is missing. In this paper, we analyse the necessity of client-side renewal, and propose a comprehensive long-term time-stamping scheme that addresses both client-side renewal and server-side renewal mechanisms. After that, we formally analyse and evaluate the client-side security of our proposed scheme.

Dynamic searchable symmetric encryption (DSSE) can enable a cloud server to search and update over the encrypted data. Recently, forward and backward privacy in DSSE receive wide attention due to the rise in a number of emerging attacks exploiting the leakage in data update operations. Forward privacy ensures newly added data is not related to queries issued in the past, whilst backward privacy ensures previously deleted data is not revealed in the queries. Unfortunately, achieving strong forward and backward privacy, i.e., only revealing insertion timestamps of search results, requires the adoption of oblivious data structures, which incur heavy computation and communication overhead at both the client and server-side. In this paper, we resort to secure enclaves, aka Intel SGX, to tackle the above problem. Specifically, we propose Maiden, the first strong backward-private DSSE scheme without relying on ORAM. Our key idea is to keep track of the states of updates and the deletion information inside the secure enclave to prevent the leakage from the server. To speed up, we further leverage a compressed data structure to maintain a sketch of addition operations in the enclave to facilitate the fast generation of search tokens of non-deleted data. We conduct formal security analysis and perform comprehensive evaluations on both synthetic and real-world datasets. Our results confirm that Maiden outperforms the prior work.

Due to the large volume of available datasets and powerful computing infrastructures, federated learning has been widely explored in many scenarios, e.g. medical screening, and image processing. It refers to all participants to jointly learn shared models under the orchestration of the server without exposing their datasets. In federated learning, since the data qualities of the participants are extremely diverse, reliability is used to measure the data qualities of the participants. To make the learning task liberally and non-discriminative, participants’ reliability privacy related to their data quality should be well preserved. However, the existing work assumed that the reliability of participants is transparent for the server provider, resulting in a severe challenge in practical applications. To thwart this challenge, we propose a novel federated learning scheme, which prevents each participant’s training set privacy and reliability privacy from being revealed to the public. Moreover, to further reduce the impact of unreliable participants and improve training efficiency, we design a cipher-based reliability weighted method to differentiate and intensify different contributions of the (un)reliable participants for joint model training. Security analysis shows that our proposed scheme can achieve the desired security requirements. Moreover, extensive performance evaluations demonstrate that our design achieves higher accuracy and is more robust against unreliable participants than conventional federated learning.

Data trading is an emerging business, in which data sellers provide buyers with, for example, their private datasets and get paid from buyers. In many scenarios, sellers prefer to sell pieces of data, such as statistical results derived from the dataset, rather than the entire dataset. Meanwhile, buyers wish to hide the results they retrieve. Since it is not preferable to rely on a trusted third party (TTP), we are wondering, in the absence of TTP, whether there exists a practical mechanism satisfying the following requirements: the seller Sarah receives the payment if and only if she obliviously returns the buyer Bob the correct evaluation result of a function delegated by Bob on her dataset, and Bob can only derive the result for which he pays. Despite a lot of attention data trading has received, a desirable mechanism for this scenario is still missing. This is due to the fact that general solutions are inefficient when the size of datasets is considerable or the evaluated function is complicated, and that existing efficient cryptographic techniques cannot fully capture the features of our scenario or can only address very limited computing tasks.

In this paper, we propose the first desirable mechanism that is practical and supports a wide variety of computing tasks—evaluation of arbitrary functions that can be represented as polynomials. We introduce a new cryptographic notion called blind polynomial evaluation and instantiate it with an explicit protocol. We further combine this notion with the blockchain paradigm to provide a practical framework that can satisfy the requirements mentioned above.

Multi-party fair exchange (MFE) considers scenarios where fairness means that either all exchanges as agreed upon between multiple parties take place, or no item changes hands. The two-party case was widely studied starting with the seminal work of Asokan et al. in ACM CCS 1998. The state-of-the-art MFE protocol was shown by Kılınç and Küpçü in CT-RSA 2015. Unfortunately, it only works on items that can be efficiently verifiably encrypted, which, in particular, means that it cannot efficiently handle exchange of large files in a peer-to-peer file sharing scenario. In this work, first, we extend the optimistic two-party fair computation definition of Cachin and Camenisch in CRYPTO 2000 for the MFE setting, and prove the security of our protocol with ideal-real simulation. Secondly, we extend the CT-RSA 2015 solution of Kılınç and Küpçü in a way that our protocol enables parties to exchange any item, be it a large file. While doing so, we employ electronic payments, where if a party does not obtain the desired item at the end of the protocol, the payment of the item’s owner will be obtained instead. Third, we achieve asymptotic optimality with O(1) rounds and \( O(n^2) \) messages, where n is the number of participating parties. Finally, we also provide experimental results from our prototype code.

We introduce a new key generation mechanism where users can generate a “back up key”, securely nested inside the secret key of a signature scheme.

Our main motivation is that in case of leakage of the secret key, established techniques based on zero-knowledge proofs of knowledge are void since the key becomes public. On the other hand, the “back up key”, which is secret, can be used to generate a “proof of ownership”, i.e., only the real owner of this secret key can generate such a proof. To the best of our knowledge, this extra level of security is novel, and could have already been used in practice, if available, in digital wallets for cryptocurrencies that suffered massive leakage of account private keys. In this work, we formalize the notion of “Proof of Ownership” and “Fallback” as new properties. Then, we introduce our construction, which is compatible with major designs for wallets based on ECDSA, and adds a \(\text{ W-OTS}^{+}\) signing key as a “back up key”. Thus offering a quantum secure fallback. This design allows the hiding of any quantum secure signature key pair, and is not exclusive to \(\text{ W-OTS}^{+}\). Finally, we briefly discuss the construction of multiple generations of proofs of ownership.

As main contribution, we design a smart contract with two collateral deposits that works, in general, on GAEN-based systems. We then also suggest the design of a more sophisticated smart contract, using DECO, that could be used to attack in a different way GAEN-based systems (i.e., this second smart contract can succeed even in case GAEN systems are repaired making ineffective the first smart contract).

Our work shows how to realize with GAEN-based systems (in particular with Immuni and SwissCovid), the terrorist attack to decentralized contact tracing systems envisioned by Vaudenay.

Sanitizable signatures (SaS) allow a (single) sanitizer, chosen by the signer, to modify and re-sign a message in a somewhat controlled way, that is, only editing parts (or blocks) of the message that are admissible for modification.

In this work, we look at the notion of \(\gamma \)-sanitizable signatures (\(\gamma \)SaS): we take the sanitizable signatures one step further by allowing the signer to not only decide which blocks can be modified, but also how many of them at most can be modified within a single sanitization, setting a limit, denoted with \(\gamma \). We adapt the security properties listed above to \(\gamma \)SaS and propose our own scheme, ULISS (Unlinkable Limited Invisible Sanitizable Signature), then show that it verifies these properties. This extension of SaS can not only improve current use cases, but also introduce new ones, e.g., restricting the number of changes in a document within a certain timeframe.

In this work we first provide a framework for defining a large subset of pairing-based digital signature schemes which we call Partially Structure-Preserving Signature (PSPS) schemes. PSPS schemes are similar in nature to structure-preserving signatures with the exception that in PSPS schemes messages are scalars from \(\mathbb {Z}_p\) instead of being group elements. This class encompasses various existing schemes which have a number of desirable features which makes them an ideal building block for many privacy-preserving cryptographic protocols. Such schemes include the widely-used schemes of Camenisch-Lysyanskaya (CRYPTO 2004) and Pointcheval-Sanders (CT-RSA 2016). We then provide various impossibility and lower bound results for variants of this class. Our results include bounds for the signature and verification key sizes as well as lower bounds for achieving strong unforgeability. We also give a generic framework for transforming variants of PSPS schemes into structure-preserving ones. As part of our contribution, we also give a number of optimal PSPS schemes which may be of independent interest. Our results aid in understanding the efficiency of pairing-based signature schemes and show a connection between this class of schemes and structure-preserving ones.

Certificate-based cryptography optimizes certificate management of the traditional public key infrastructure (PKI) and overcomes the problems of the key escrow and the key distribution in identity-based cryptography (IBC). Currently, many certificate-based signature (CBS) schemes have been proposed in the random oracle model or standard model. However, all existing schemes in the standard model are quietly inefficient. In this paper, we propose an efficient certificate-based signature over bilinear groups in the standard model. Compared with the state-of-the-art constructions in the standard model, the proposed scheme is superior in both communication cost and computational overhead.

Convolutional Neural Networks (CNNs) are the target of several side-channel attacks aiming at recovering their parameters and hyper-parameters. Attack vectors include monitoring of the cache, power consumption analysis and execution time measurements. These attacks often rely on the knowledge of a certain – large – set of hyper-parameters among which the victim model lies. The goal of the potential attacker is then to reduce that search space or even deduce the correct architecture. One such attack, Cache Telepathy by Yan et al., monitors access to a common matrix multiplication algorithm, GeMM (Generalized Matrix Multiply), in order to determine the victim model’s hyper-parameters. In this paper, we propose to change the order in which the computations are made and add randomness to the said computations in order to mitigate Cache Telepathy. The security analysis of our protection shows that the Cache Telepathy attack on a protected VGG-16 has an increased search space: from 16 to \(2^{22}\).

Elliptic curve cryptography (ECC) is one of promising cryptosystems in embedded systems as it provides high security levels with short keys. Scalar multiplication is a dominating and time-consuming process that ensures security in ECC. We implement hardware modules for generic ECC over 256-bit prime fields on field-programmable gate array (FPGA). The key points in our design are (1) secure and exception-free for any scalar with less memory usage, (2) long-bit modular arithmetic modules utilizing today’s advanced and high-performance programmable logic and considering balance between the modules in terms of propagation delay, (3) parallelism extraction inside each elliptic curve point computation as well as between the point computations, and (4) efficient hardware–software co-processing facilitated by application interfaces between a processing core and hardware modules. The evaluation results demonstrate that our design achieves the best performance to existing FPGA designs without using a table for generic ECC.

A password protected secret sharing (\(\mathsf {PPSS}\)) allows a user to store shares of a secret on a set of L servers, and use a single password to authenticate itself to any subset of k servers at a later time to access the shares and reconstruct the secret. Security of \(\mathsf {PPSS}\) ensures that a coalition of up to \(k-1\) servers cannot reveal any information about the secret message or the password. A related primitive is threshold password authenticated key exchange protocol (\(\mathsf {TPAKE}\)) that allows a user to establish individual authenticated shared secret keys with members of a subset of k out of L servers, using a single password. These primitives are well motivated, with applications such as secure storage of secret keys, and secure group communication using passwords for authentication. In this paper, we give the first construction of these primitives that provide post-quantum security. We prove security of our constructions in concurrent setting, and in the standard model, reducing security to the decisional LWE problem.

In the past few years, significant progress on homomorphic encryption (HE) has been made toward both theory and practice. The most promising HE schemes are based on the hardness of the Learning With Errors (LWE) problem or its ring variant (RLWE). In this work, we present new conversion algorithms that switch between different (R)LWE-based HE schemes to take advantage of them. Specifically, we present and combine three ideas to improve the key-switching procedure between LWE ciphertexts, transformation from LWE to RLWE, as well as packing of multiple LWE ciphertexts in a single RLWE encryption. Finally, we demonstrate an application of building a secure channel between a client and a cloud server with lightweight encryption, low communication cost, and capability of homomorphic computation.