We address the problem of user fast revocation in the lattice-based Ciphertext Policy Attribute-Based Encryption (CP-ABE) by extending the scheme originally introduced by Zhang and Zhang [Zhang J, Zhang Z. A ciphertext policy attribute-based encryption scheme without pairings. In: International Conference on Information Security and Cryptology. Springer; 2011. p. 324–40. doi: https://doi.org/10.1007/978-3-642-34704-7_23.]. While a lot of work exists on the construction of revocable schemes for CP-ABE based on pairings, works based on lattices are not so common, and – to the best of our knowledge – we introduce the first server-aided revocation scheme in a lattice-based CP-ABE scheme, hence being embedded in a post-quantum secure environment. In particular, we rely on semi-trusted “mediators” to provide a multi-step decryption capable of handling mediation without re-encryption. We comment on the scheme and its application, and we provide performance experiments on a prototype implementation in the Attribute-Based Encryption spin-off library of Palisade to evaluate the overhead compared with the original scheme.

The Critical Node Detection Problem (CNDP) consists in finding the set of nodes, defined critical, whose removal maximally degrades the graph. In this work we focus on finding the set of critical nodes whose removal minimizes the pairwise connectivity of a direct graph (digraph). Such problem has been proved to be NP-hard, thus we need efficient heuristics to detect critical nodes in real-world applications. We aim at understanding which is the best heuristic we can apply to identify critical nodes in practice, i.e., taking into account time constrains and real-world networks. We present an in-depth analysis of several heuristics we ran on both real-world and on synthetic graphs. We define and evaluate two different strategies for each heuristic: standard and iterative. Our main findings show that an algorithm recently proposed to solve the CNDP and that can be used as heuristic for the general case provides the best results in real-world graphs, and it is also the fastest. However, there are few exceptions that are thoroughly analyzed and discussed. We show that among the heuristics we analyzed, few of them cannot be applied to very large graphs, when the iterative strategy is used, due to their time complexity. Finally, we suggest possible directions to further improve the heuristic providing the best results.

Algebraic Cryptanalysis is a widely used technique that tackles the problem of breaking ciphers mainly relying on the ability to express a cryptosystem as a solvable polynomial system. Each output bit/word can be expressed as a polynomial equation in the cipher’s inputs—namely the key and the plaintext or the initialisation vector bits/words. A part of research in this area consists in finding suitable algebraic structures where polynomial systems can be effectively solved, e.g., by computing Gröbner bases. In 2009, Dinur and Shamir proposed the cube attack, a chosen plaintext algebraic cryptanalysis technique for the offline acquisition of an equivalent system by means of monomial reduction; interpolation on cubes in the space of variables enables retrieving a linear polynomial system, hence making it exploitable in the online phase to recover the secret key. Since its introduction, this attack has received both many criticisms and endorsements from the crypto community; this work aims at providing, under a unified notation, a complete state-of-the-art review of recent developments by categorising contributions in five classes. We conclude the work with an in-depth description of the kite attack framework, a cipher-independent tool that implements cube attacks on GPUs. Mickey2.0 is adopted as a showcase.

Defining accurate and flexible models for real-world networks of human beings is instrumental to understand the observed properties of phenomena taking place across those networks and to support computer simulations of dynamic processes of interest for several areas of research - including computational epidemiology, which is recently high on the agenda. In this paper we present a flexible model to generate age-stratified and geo-referenced synthetic social networks on the basis of widely available aggregated demographic data and, possibly, of estimated age-based social mixing patterns. Using the Italian city of Florence as a case study, we characterize our network model under selected configurations and we show its potential as a building block for the simulation of infections' propagation. A fully operational and parametric implementation of our model is released as open-source.

The COVID-19 pandemic triggered a global research effort to define and assess timely and effective containment policies. Understanding the role that specific venues play in the dynamics of epidemic spread is critical to guide the implementation of fine-grained non-pharmaceutical interventions (NPIs). In this paper, we present a new model of context-dependent interactions that integrates information about the surrounding territory and the social fabric. Building on this model, we developed an open-source data-driven simulator of the patterns of fruition of specific gathering places that can be easily configured to project and compare multiple scenarios. We focused on the greatest park of the City of Florence, Italy, to provide experimental evidence that our simulator produces contact graphs with unique, realistic features, and that gaining control of the mechanisms that govern interactions at the local scale allows to unveil and possibly control non-trivial aspects of the epidemic.

The definition of suitable generative models for synthetic yet realistic social networks is a widely studied problem in the literature. By not being tied to any real data, random graph models cannot capture all the subtleties of real networks and are inadequate for many practical contexts--including areas of research, such as computational epidemiology, which are recently high on the agenda. At the same time, the so-called contact networks describe interactions, rather than relationships, and are strongly dependent on the application and on the size and quality of the sample data used to infer them. To fill the gap between these two approaches, we present a data-driven model for urban social networks, implemented and released as open source software. By using just widely available aggregated demographic and social-mixing data, we are able to create, for a territory of interest, an age-stratified and geo-referenced synthetic population whose individuals are connected by "strong ties" of two types: Intra-household (e.g., kinship) or friendship. While household links are entirely data-driven, we propose a parametric probabilistic model for friendship, based on the assumption that distances and age differences play a role, and that not all individuals are equally sociable. The demographic and geographic factors governing the structure of the obtained network under different configurations, are thoroughly studied through extensive simulations focused on three Italian cities of different size.

Network-based ranking methods (e.g. centrality analysis) have found extensive use in systems medicine for the prediction of essential proteins, for the prioritization of drug targets candidates in the treatment of several pathologies and in biomarker discovery, and for human disease genes identification. Here we propose to use critical nodes as defined by the Critical Node Problem for the analysis of key physiological and pathophysiological signaling pathways, as target candidates for treatment and management of several cancer types, neurologic and inflammatory dysfunctions, among others. We show how critical nodes allow to rank the importance of proteins in the pathways in a non-trivial way, substantially different from classical centrality measures. Such ranking takes into account the extent to which the network depends on its key players to maintain its cohesiveness and consistency, and coherently maps biologically relevant characteristics that can be critical in disease onset and treatments.

The cube attack is a flexible cryptanalysis technique, with a simple and fascinating theoretical implant. It combines offline exhaustive searches over selected tweakable public/IV bits (the sides of the "cube"), with an online key-recovery phase. Although virtually applicable to any cipher, and generally praised by the research community, the real potential of the attack is still in question, and no implementation so far succeeded in breaking a real-world strong cipher. In this paper, we present, validate and analyze the first thorough implementation of the cube attack on a GPU cluster. The framework is conceived so as to be usable out-of-the-box for any cipher featuring up to 128-bit key and IV, and easily adaptable to larger key/IV, at just the cost of some fine (performance) tuning, mostly related to memory allocation. As a test case, we consider previous state-of-the-art results against a reduced-round version of a well-known cipher (Trivium). We evaluate the computational speedup with respect to a CPU-parallel benchmark, the performance dependence on system parameters and GPU architectures (Nvidia Kepler vs Nvidia Pascal), and the scalability of our solution on multi-GPU systems. All design choices are carefully described, and their respective advantages and drawbacks are discussed. By exhibiting the benefits of a complete GPU-tailored implementation of the cube attack, we provide novel and strong elements in support of the general feasibility of the attack, thus paving the way for future work in the area.

With black-box access to the cipher being its unique requirement, Dinur and Shamir's cube attack is a flexible cryptanalysis technique which can be applied to virtually any cipher. However, gaining a precise understanding of the characteristics that make a cipher vulnerable to the attack is still an open problem, and no implementation of the cube attack so far succeeded in breaking a real-world strong cipher. In this paper, we present a complete implementation of the cube attack on a GPU/CPU cluster able to improve state-of-the-art results against the Trivium cipher. In particular, our attack allows full key recovery up to 781 initialization rounds without brute-force, and yields the first ever maxterm after 800 initialization rounds. The proposed attack leverages a careful tuning of the available resources, based on an accurate analysis of the offline phase, that has been tailored to the characteristics of GPU computing. We discuss all design choices, detailing their respective advantages and drawbacks. Other than providing remarkable results, this paper shows how the cube attack can significantly benefit from accelerators like GPUs, paving the way for future work in the area.

Searching for words or sentences within large sets of textual documents can be very challenging unless an index of the data has been created in advance. However, indexing can be very time consuming especially if the text is not readily available and has to be extracted from files stored in different formats. Several solutions, based on the MapReduce paradigm, have been proposed to accelerate the process of index creation. These solutions perform well when data are already distributed across the hosts involved in the elaboration. On the other hand, the cost of distributing data can introduce noticeable overhead. We propose ISODAC, a new approach aimed at improving efficiency without sacrificing reliability. Our solution reduces to the bare minimum the number of I/O operations by using a stream of in-memory operations to extract and index text. We further improve the performance by using GPUs for the most computationally intensive tasks of the indexing procedure. ISODAC indexes heterogeneous documents up to 10.6x faster than other widely adopted solutions, such as Apache Spark. As proof-of-concept, we developed a tool to index forensic disk images that can easily be used by investigators through a web interface.