Cryptology and Network Security

In the last decade, location information became easily obtainable using off-the-shelf mobile devices. This gave a momentum to developing Location Based Services (LBSs) such as location proximity detection, which can be used to find friends or taxis nearby. LBSs can, however, be easily misused to track users, which draws attention to the need of protecting privacy of these users.

In this work, we address this issue by designing, implementing, and evaluating multiple algorithms for Privacy-Preserving Location Proximity (PPLP) that are based on different secure computation protocols. Our PPLP protocols are well-suited for different scenarios: for saving bandwidth, energy/computational power, or for faster runtimes. Furthermore, our algorithms have runtimes of a few milliseconds to hundreds of milliseconds and bandwidth of hundreds of bytes to one megabyte. In addition, the computationally most expensive parts of the PPLP computation can be precomputed in our protocols, such that the input-dependent online phase runs in just a few milliseconds.

Betweenness centrality is a classic network measure used to determine prominent nodes in a network G(V, E), where the edges capture a type of flow through the network (like information, material or money). Betweenness being a global centrality measure requires the entire network information to compute the centrality of even a single vertex. We consider the setting where the global network structure is not present centrally with a single individual. Rather, the data is distributed among many individuals, each having only a partial view of the network. Furthermore, confidentiality constraints prevent the individual parties from disclosing their share of the data, thus inhibiting the aggregation of the entire network for analysis. The current paper proposes a secure multiparty protocol to compute the betweenness centrality measure, in a privacy preserving manner, for the considered setting. Employing various optimizations, including oblivious data structures and oblivious RAM, we present a secure variant of the Brandes algorithm for computing betweenness centrality in unweighted networks. The protocol is designed in the semi-honest adversarial model under the two-party setting. We evaluate the performance of the designed protocol by implementing them in the Obliv-C framework for secure computation. We are the first to provide a benchmark for the implementations using the state of the art ORAM schemes and help identify the best schemes for input data of different sizes. Employing the Circuit ORAM and the Square-Root ORAM schemes, we report the complexity of the proposed protocol as \(\mathcal {O}(|V||E|\log ^3|E|)\) and \(\mathcal {O}(|V||E|^{1.5}\log ^{1.5}|E|)\) primitive operations respectively. The asymptotic complexity of Circuit ORAM is found to be the least, with an overhead of only \(\mathcal {O}(\log ^3|E|)\) compared to the traditional non-oblivious Brandes algorithm with complexity \(\mathcal {O}(|V||E|)\).

We consider the problem of privacy-preserving processing of outsourced data in the context of user-customised services. Clients store their data on a server. In order to provide user-dependent services, service providers may ask the server to compute functions on the users’ data. We propose a new solution to this problem that guarantees data privacy (i.e., an honest-but-curious server cannot access plaintexts), as well as that service providers can correctly decrypt only –functions on– the data the user gave them access to (i.e., service providers learn nothing more than the result of user-selected computations).

Our solution has as base point a new secure labelled homomorphic encryption scheme (\(\mathsf {LEEG}\)). \(\mathsf {LEEG}\) supports additional algorithms (\(\mathsf {FEET}\)) that enhance the scheme’s functionalities with extra privacy-oriented features. Equipped with \(\mathsf {LEEG}\) and \(\mathsf {FEET}\), we define \(\mathsf {HIKE}\): a lightweight protocol for private and secure storage, computation and disclosure of users’ data. Finally, we implement \(\mathsf {HIKE}\) and benchmark its performances demonstrating its succinctness and efficiency.

The detection of network flows that send excessive amounts of traffic is of increasing importance to enforce QoS and to counter DDoS attacks. Large-flow detection has been previously explored, but the proposed approaches can be used on high-capacity core routers only at the cost of significantly reduced accuracy, due to their otherwise too high memory and processing overhead. We propose CLEF, a new large-flow detection scheme with low memory requirements, which maintains high accuracy under the strict conditions of high-capacity core routers. We compare our scheme with previous proposals through extensive theoretical analysis, and with an evaluation based on worst-case-scenario attack traffic. We show that CLEF outperforms previously proposed systems in settings with limited memory.

Image/video compression is a widely used operation in our everyday life. Such an operation usually proceeds independantly on small rectangular portions, so-called macroblocks, and is mainly divided into four operations: color conversion, Discrete Cosine Transform (DCT), quantization and entropic encoding. This operation is carried out easily on non-encrypted image. In this paper, we consider the case where such an execution is done in the encrypted domain. In fact, this is today one central question related to individuals’ privacy since such image/video compression is most of the time done on the premises of a service provider data center, and pictures are potentially sensitive personal data. Thus, the capacity for such entity to perform an action “blindfolded”, that is not knowing the underlying input in plain, is an important topic since it permits to obtain both individual privacy and data usability.

In this context, one of the main cryptographic tool is (fully) homomorphic encryption (FHE), that permits to perform operations while keeping the data encrypted. We here consider two different instantiations of FHE, one for which the plaintext space is binary (\(\mathbb {Z}_2\)) and the other a modular space (\(\mathbb {Z}_p\) for an integer \(p> 2 \)), and compare them when running the well-known H264 and HEVC macroblock processing pipelines.

Our contribution is twofold. On one hand, we provide an exhaustive comparison between FHEs over \(\mathbb {Z}_2\) and FHEs over \(\mathbb {Z}_p\) (\(p>2\)) in terms of functional capabilities, multiplicative depth and real performances using several existing FHE implementations, over libraries such as Cingulata, SEAL and TFHE. On the other hand, we apply this to image compression in the encrypted domain, being the first to “crypto-compress” a full encrypted photograph with practically relevant performances.

Mesh networks, like e.g. smart-homes, are networks where every node has routing capabilities. These networks are usually flat, which means that one compromised device can potentially overtake the whole infrastructure, especially considering clone attacks.

To counter attacks, we propose a network architecture which enhances flat networks, especially mesh networks, with isolation and automatic containment of malicious devices. Our approach consists of unprivileged devices, clustered into groups, and privileged “bridge” devices which can cooperatively apply filter rules like a distributed firewall. Since there is no ultimate authority (not even bridges) to control the whole network, our approach has no single point-of-failure – so-called intrusion or malware tolerance. That means, attacks on a single device will not compromise the whole infrastructure and are tolerated. Previous research on mesh networks [3, 8‐10] relied on a single point-of-failure and is, thus, not intrusion or malware tolerant.

Our architecture is dynamic in the sense that bridge devices can change, misbehaving devices can be isolated by outvoting them, and cryptographic keys evolve. This effectively turns the entire network into a moving target.

We used the protocol verifier ProVerif to prove the security properties of our network architecture.

A special category of malware named ransomware has become very popular for cyber-criminals to extort money. This category limits users from accessing their machines (computers, mobile phones and IoT devices) unless a ransom is paid. Every month, security experts report many forms of ransomware attacks, termed as ransomware families. An example of these families is the GandCrab ransomware that was released at the end of January 2018. In this paper, we present a full depth malware analysis of this ransomware following some recent work and findings on ransomware detection and prevention.

Counter mode encryption uses a blockcipher to generate a key stream, which is subsequently used to encrypt data. The mode is known to achieve security up to the birthday bound. In this work we consider two approaches in literature to improve it to beyond birthday bound security: CENC by Iwata (FSE 2006) and its generalization NEMO by Lefranc et al. (SAC 2007). Whereas recent discoveries on CENC argued optimal security, the state of the art of NEMO is still sub-optimal. We draw connections among various instantiations of CENC and NEMO, and particularly prove that the improved optimal security bound on the CENC family carries over to a large class of variants of NEMO. We further conjecture that it also applies to the remaining variants, and discuss bottlenecks in proving so.

In this paper, we study the efficiency of \(\mathsf {ZMAC}\)-type message authentication codes (MACs). \(\mathsf {ZMAC}\) was proposed by Iwata et al. (CRYPTO 2017) and is a highly efficient and highly secure MAC based on tweakable blockcipher (TBC). \(\mathsf {ZMAC}\) achieves the so-called beyond-birthday-bound security: security up to \(2^{\min \{b, (b+t)/2\}}\) TBC calls, using a TBC with the input-block space \(\{0,1\}^b\) and the tweak space \(\mathcal {TW}= \mathcal {I}\times \{0,1\}^t\) where \(\mathcal {I}\) is a set with \(|\mathcal {I}| = 5\) and is used for tweak separations. In the hash function, the \(b\)-bit and \(t\)-bit spaces are used to take message blocks (in previous MACs, only the \(b\)-bit input-block space is used). In the finalization function, a TBC is called twice, and these spaces are not used. List and Nandi (ToSC 2017, Issue 4) proposed \(\mathsf {ZMAC}^+\), a variant of \(\mathsf {ZMAC}\), where one TBC call is removed from the finalization function. Although both the \(b\)-bit and \(t\)-bit spaces in the hash function are used to take message blocks, those in the finalization function are not used. That rises the following question with the aim of improving the efficiency: can these spaces be used while retaining the same level of security as \(\mathsf {ZMAC}\)? In this paper, we consider the following three \(\mathsf {ZMAC}\)-type MACs.

We show that none of the above MACs achieve the same level of security as \(\mathsf {ZMAC}(^+)\). Hence, \(\mathsf {ZMAC}^+\) is the most efficient MAC in the \(\mathsf {ZMAC}\)-type ones with \(2^{\min \{b, (b+t)/2\}}\)-security.

We next consider whether the tweak separations can be removed (i.e., \(\mathcal {I}\) can be used to take a message block), with the aim of improving the efficiency of \(\mathsf {ZMAC}^+\). Iwata et al. mentioned that the tweak separations can be removed by using distinct field multiplications such as multiplications by 3 and 7, but these render the implementation much more complex (note that in \(\mathsf {ZMAC}\), field multiplications by 2 are used). For this problem, we show that the tweak separations can be removed without the field multiplications except for the multiplications by 2, that is, all spaces \(\mathcal {TW}\) and \(\{0,1\}^b\) in the hash function can be used to take message blocks without such complex implementations.

Attribute-based Signatures (ABS) are a powerful tool allowing users with attributes issued by authorities to sign messages while also proving that their attributes satisfy some policy. ABS schemes provide a flexible and privacy-preserving approach to authentication since the signer’s identity and attributes remain hidden within the anonymity set of users sharing policy-conform attributes. Current ABS schemes exhibit some limitations when it comes to the management and issue of attributes. In this paper we address the lack of support for hierarchical attribute management, a property that is prevalent in traditional PKIs where certification authorities are organised into hierarchies and signatures are verified along roots of trust.

We anticipate that HABS will be useful for privacy-preserving authentication in applications requiring hierarchical delegation of attribute-issuing rights and where knowledge of delegation paths might leak information about signers and their attributes, e.g., in intelligent transport systems where vehicles may require certain attributes to authenticate themselves to the infrastructure but remain untrackable by the latter.

Despite the recent advances in attribute-based signatures (ABS), no schemes have yet been considered under a strong privacy definition. We enhance the security of ABS by presenting a strengthened simulation-based privacy definition and the first attribute-based signature functionality in the framework of universal composability (UC). Additionally, we show that the UC definition is equivalent to our strengthened experiment-based security definitions. To achieve this we rely on a general unforgeability and a simulation-based privacy definition that is stronger than standard indistinguishability-based privacy. Further, we show that two extant concrete ABS constructions satisfy this simulation-based privacy definition and are therefore UC secure. The two concrete constructions are the schemes by Sakai et al. (PKC’16) and by Maji et al. (CT-RSA’11). Additionally, we identify the common feature that allows these schemes to meet our privacy definition, giving us further insights into the security requirements of ABS.

We introduce the notion of Protean Signature schemes. This novel type of signature scheme allows to remove and edit signer-chosen parts of signed messages by a semi-trusted third party simultaneously. In existing work, one is either allowed to remove or edit parts of signed messages, but not both at the same time. Which and how parts of the signed messages can be modified is chosen by the signer. Thus, our new primitive generalizes both redactable (Steinfeld et al., ICISC ’01, Johnson et al., CT-RSA ’02 & Brzuska et al., ACNS ’10) and sanitizable signatures schemes (Ateniese et al., ESORICS ’05 & Brzuska et al., PKC ’09). We showcase a scenario where either primitive alone is not sufficient. Our provably secure construction (offering both strong notions of transparency and invisibility) makes only black-box access to sanitizable and redactable signature schemes, which can be considered standard tools nowadays. Finally, we have implemented our scheme; Our evaluation shows that the performance is reasonable.

We present two code-based identification protocols and signature schemes in the rank metric, providing detailed pseudocode and selecting practical parameters. The proposals are derived from their analogue in the Hamming metric. We discuss their security in the post-quantum scenario. With respect to other signature schemes based on codes, our constructions maintain a similar efficiency, possess large but still practical signatures, and the smallest key and public key sizes.

In data security, the main objectives one tries to achieve are confidentiality, data integrity and authentication. In a public-key setting, confidentiality is reached through asymmetric encryption and both data integrity and authentication through signature. Meeting all the security objectives for data exchange requires to use a concatenation of those primitives in an encrypt-then-sign or sign-then-encrypt fashion. Signcryption aims at providing all the security requirements in one single primitive at a lower cost than using encryption and signature together. Most existing signcryption schemes are using ElGamal-based or pairing-based techniques and thus rely on the decisional Diffie-Hellman assumption. With the current growth of a quantum threat, we seek for post-quantum counterparts to a vast majority of public-key primitives. In this work, we propose a lattice-based signcryption scheme in the random oracle model inspired from a construction of Malone-Lee. It comes in two flavors, one integrating the usual lattice-based key exchange into the signature and the other merging the scheme with a RLWE encryption. Our instantiation is based on a ring version of the scheme of Bai and Galbraith as was done in ring-TESLA and TESLA\(\sharp \). It targets 128 bits of classical security and offers a save in bandwidth over a naive concatenation of state-of-the-art key exchanges and signatures from the literature. Another lightweight instantiation derived from GLP is feasible but raises long-term security concerns since the base scheme is somewhat outdated.

Code-based public-key cryptosystems based on QC-LDPC and QC-MDPC codes are promising post-quantum candidates to replace quantum-vulnerable classical alternatives. However, a new type of attacks based on Bob’s reactions have recently been introduced and appear to significantly reduce the length of the life of any keypair used in these systems. In this paper we estimate the complexity of all known reaction attacks against QC-LDPC and QC-MDPC code-based variants of the McEliece cryptosystem. We also show how the structure of the secret key and, in particular, the secret code rate affect the complexity of these attacks. It follows from our results that QC-LDPC code-based systems can indeed withstand reaction attacks, on condition that some specific decoding algorithms are used and the secret code has a sufficiently high rate.

HQC (Hamming Quasi-Cyclic) cryptosystem, proposed by Aguilar Melchor et al., is a code-based key encapsulation mechanism (KEM) running for standardization to NIST’s competition in the category “post-quantum public key encryption scheme”. The underlying hard mathematical problem of HQC is presented as the s-DQCSD (Decision Quasi-Cyclic Syndrome Decoding) problem, which refers to the question of distinguishing whether a given instance came from the s-QCSD distribution or the uniform distribution. Under the assumption that 2-DQCSD and 3-DQCSD are hard, HQC, viewed as a PKE scheme, is proven to be IND-CPA secure, and can be transformed into an IND-CCA2 secure KEM. However, in this paper, we are going to show that s-DQCSD problem is actually not intractable. More precisely, we can efficiently distinguish the s-QCSD distribution instances from the uniform distribution instances with at least a constant advantage. Furthermore, with a similar technique, we show that HQC can not attain IND-CPA security with all the proposed parameter sets.

The typical approach in attacking an LWR\(_{m,n,q,p}(\chi _s)\) instance parameterized by four integers m, n, q, p \( (q \ge p)\) and a probability distribution \(\chi _s\) is just by simply regarding it as a Learning with Errors (LWE) modulo q instance and then trying to adapt known LWE attacks to this LWE instance. In this paper, we show that for an LWR\(_{m,n,q,p}(\chi _s)\) instance whose parameters satisfy a certain sufficient condition, one can use the BDD strategy to recover the secret with higher advantages if one transforms the LWR instance to an LWE modulo \(q'\) instance with \(q'\) chosen appropriately instead of an LWE modulo q instance. The optimal modulus \(q'\) used in our BDD attack is quite close to p as well as typically smaller than q. Especially, our experiments confirm that our BDD attack is much better in solving search-LWR in terms of root Hermite factor, success probability and even running time either in case the ratio \(\log (q)/ \log (p)\) is big or/and the dimension n is sufficiently large.

In 2018, Amadori et al. proposed a new variant of index calculus to solve the elliptic curve discrete logarithm problem (ECDLP), using Semaev’s summation polynomials. The variant drastically decreases the number of required Gröbner basis computations, and it outperforms other index calculus algorithms for the ECDLP over prime fields. In this paper, we provide several improvements to accelerate to solve systems of multivariate equations arising in the variant. A main improvement is to apply the hybrid method, which mixes exhaustive search and Gröbner bases techniques to solve multivariate systems over finite fields. We also make use of symmetries of summation polynomials. We show experimental results of our improvements, and give their complexity analysis to discuss a limitation of our acceleration in both theory and practice.

SNOW 2.0 is a software-oriented stream cipher and internationally standardized by ISO/IEC 18033-4. In this paper, we present three attacks on SNOW 2.0 by MILP-aided automatic search algorithms. First, we present an efficient algorithm to find linear masks with the high correlation. It enables us to improve time and data complexities of the known fast correlation attacks. Then we propose a 17-round integral distinguisher out of 32 rounds by evaluating the propagation of the division property. Moreover, we propose a cube attack on the 14-round SNOW 2.0. The time complexity is \(2^{61.59}\) where \(2^{39}\) chosen IVs are required. As far as we know, these are the first investigations about integral and cube attacks of SNOW 2.0, respectively.

Leakage-resilience guarantees that even if some information about the secret key is partially leaked, the security is maintained. Several security models considering leakage-resilience have been proposed. Among them, auxiliary leakage model proposed by Dodis et al. in STOC’09 is especially important, since it can deal with a leakage caused by a function which information-theoretically reveals the secret key, e.g., one-way permutation.

Contribution of this work is two-fold. Firstly, we propose an identity-based encryption (IBE) scheme and prove that it is fully secure and resilient to the auxiliary leakage under the decisional linear assumption in the standard model. Secondly, although the IBE scheme proposed by Yuen et al. in Eurocrypt’12 has been considered to be the only IBE scheme resilient to auxiliary leakage, we prove that the security proof for the IBE scheme is defective. We insist that our IBE scheme is the only IBE scheme resilient to auxiliary leakage.

Verifiable random functions are pseudorandom functions producing publicly verifiable proofs for their outputs, allowing for efficient checks of the correctness of their computation. In this work, we introduce a new computational hypothesis, the \(n\text {-}\mathsf {Eigen}\text {-}\mathsf {Value} \) assumption, which can be seen as a particularization of the \(\mathcal {U}_{l,k}\)-\(\mathrm {MDDH}\) assumption for the case \(l=k+1\), and prove its equivalence with the \(n\text {-}\mathsf {Rank} \) problem. Based on the newly introduced computational hypothesis, we build the core of a verifiable random function having an exponentially large input space and reaching adaptive security under a static assumption. The final construction achieves shorter public and secret keys compared to the existing schemes reaching the same properties.

We consider access structures over a set \(\mathcal {P}\) of n participants, defined by a parameter k with \(1 \le k \le n\) in the following way: a subset is authorized if it contains participants \(i,i+1,\ldots ,i+k-1\), for some \(i \in \{1,\ldots ,n-k+1\}\). We call such access structures, which may naturally appear in real applications involving distributed cryptography, (k, n)-consecutive.

We prove that these access structures are only ideal when \(k=1,n-1,n\). Actually, we obtain the same result that has been obtained for other families of access structures: being ideal is equivalent to being a vector space access structure and is equivalent to having an optimal information rate strictly bigger than \(\frac{2}{3}\). For the non-ideal cases, we give either the exact value of the optimal information rate, for \(k=n-2\) and \(k=n-3\), or some bounds on it.

Recently, a general framework to help assess the security of extended biometric visual cryptographic schemes (e-BVC) was proposed, formalizing the notion of perfect resistance against false authentication. In this paper, we extend this framework with respect to indistinguishability and index privacy notions. Based on our definitions, we present theoretical analysis of e-BVC schemes and propose new attack strategies. We show that the general framework can be applied to derive new and quantifiable upper bounds on the security of e-BVC schemes. We also discuss the practical impact of our attacks in detail and present several case analyses for a recent implementation of a face recognition protocol.

Multi-Channel Broadcast Encryption (MCBE) introduced by Phan et al. provides a suitable way to broadcast messages efficiently to groups of recipients while usual broadcast encryption (BE) sends a message to a particular group of users, consequently increases communication bandwidth and computation cost to send different messages to different group of users by employing BE repeatedly. We have proposed two public key multi-channel broadcast encryption schemes while all the existing schemes are in private key setting. Our first construction achieves semi-static security against chosen plaintext attack (CPA) under Decisional Bilinear Diffie-Hellman Exponent Sum (DBDHE-sum) assumption and second scheme achieves selective security against CPA under modified squared Decisional Diffie-Hellman Exponent (m-sq-DDHE) assumption. Both of our proposed constructions have constant header size. Our second construction achieves outsider-anonymity which hides user identity from outsiders apart from data hiding.