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.

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.

The development of Boolean algebra based algorithms lied the foundation for a wide variety of cryptanalysis techniques based on the reformulation of a cryptosystem as a polynomial function over F2. Widely used approaches to solve multivariate system of equations include Gröbner bases (see [11]) and linearisation techniques like XL [4] and XSL [5]). Performances of these methodologies were however completely unfeasible for real problems’ size, making it impossible to directly find useful relations between cryptographic schemes’ input and output. At Eurocrypt’09 a new methodology settled in this environment, providing a feasible family of attacks able to retrieve useful in- put/output relations within feasible time: Dinur and Shamir Cube Attack [7]. The attack relied on the new concept of tweakable poly- nomials, polynomials in variables the attacker can set at will during the attack through which a black-box representation of the cipher is analysed. The resonance of this approach was unexpected, making it the forefather of many other approaches ranging from generic finite fields [1, 15] and non-linear [14] approaches to Meet-in-the- Middle [2, 13] and side channels [8] attacks. The idea of tweakable polynomials was also exploited to provide property (cube) testers which generated Conditional [12] and Dynamic [9] cube attacks. All of these approaches come with their own nomenclature, often making it unclear about their real contribute to the state of the art. The aim of this work is to introduce a novel notation to provide a global representation of the cube attacks family.

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.

Expansions in noninteger bases often appear in number theory and probability theory, and they are closely connected to ergodic theory, measure theory and topology. For two-letter alphabets the golden ratio plays a special role: in smaller bases only trivial expansions are unique, whereas in greater bases there exist nontrivial unique expansions. In this paper we determine the corresponding critical bases for all three-letter alphabets and we establish the fractal nature of these bases in function of the alphabets.

Two T helper (Th) cell subsets, namely Th1 and Th2 cells, play an important role in inflammatory diseases. The two subsets are thought to counter-regulate each other, and alterations in their balance result in different diseases. This paradigm has been challenged by recent clinical and experimental data. Because of the large number of genes involved in regulating Th1 and Th2 cells, assessment of this paradigm by modeling or experiments is difficult. Novel algorithms based on formal methods now permit the analysis of large gene regulatory networks. By combining these algorithms with in silico knockouts and gene expression microarray data from human T cells, we examined if the results were compatible with a counterregulatory role of Th1 and Th2 cells. We constructed a directed network model of genes regulating Th1 and Th2 cells through text mining and manual curation. We identified four attractors in the network, three of which included genes that corresponded to Th0, Th1 and Th2 cells. The fourth attractor contained a mixture of Th1 and Th2 genes. We found that neither in silico knockouts of the Th1 and Th2 attractor genes nor gene expression microarray data from patients with immunological disorders and healthy subjects supported a counter-regulatory role of Th1 and Th2 cells. By combining network modeling with transcriptomic data analysis and in silico knockouts, we have devised a practical way to help unravel complex regulatory network topology and to increase our understanding of how network actions may differ in health and disease.

Motivation: An unbalanced differentiation of T helper cells from precursor type TH0 to the TH1 or TH2 phenotype in immune responses often leads to a pathological condition. In general, immune reactions biased toward TH1 responses may result in auto-immune diseases, while enhanced TH2 responses may cause allergic reactions. The aim of this work is to integrate a gene network of the TH differentiation in an agent-based model of the hyper-sensitivity reaction. The implementation of such a system introduces a second level of description beyond the mesoscopic level of the inter-cellular interaction of the agent-based model. The intra-cellular level consists in the cell internal dynamics of gene activation and transcription. The gene regulatory network includes genes-related molecules that have been found to be involved in the differentiation process in TH cells. Results: The simulator reproduces the hallmarks of an IgE-mediated hypersensitive reaction and provides an example of how to combine the mesoscopic level description of immune cells with the microscopic gene-level dynamics.

: In this article we present the implementation of an environment supporting Levy's optimal reduction for the X-calculus on parallel (or distributed) computing systems. In a similar approach to Lamping's, we base our work on a graph reduction technique, known as directed virtual reduction, which is actually a restriction of Danos-Regnier virtual reduction. The environment, which we refer to as PELCR (parallel environment for optimal lambdacalculus reduction), relies on a strategy for directed virtual reduction, namely half combustion. While developing PELCR we adopted both a message aggregation technique, allowing reduction of the communication overhead, and a fair policy for distributing dynamically originated load among processors. We also present an experimental study demonstrating the ability of PELCR to definitely exploit the parallelism intrinsic to lambda-terms while performing the reduction. We show how PELCR allows achieving up to 70-80% of the ideal speedup on last generation multiprocessor computing systems. As a last note, the software modules have been developed with. the C language and using a standard interface for message passing, that is, MPI, thus making PELCR itself a highly portable software package.

In [M. Pedicini and F. Quaglia. A parallel implementation for optimal lambda-calculus reduction PPDP '00: Proceedings of the 2nd ACM SIGPLAN international conference on Principles and practice of declarative programming, pages 3–14, ACM, 2000, M. Pedicini and F. Quaglia. PELCR: Parallel environment for optimal lambda-calculus reduction. CoRR, cs.LO/0407055, accepted for publication on TOCL, ACM, 2005], PELCR has been introduced as an implementation derived from the Geometry of Interaction in order to perform virtual reduction on parallel/distributed computing systems. In this paper we provide an extension of PELCR with computational effects based on directed virtual reduction [V. Danos, M. Pedicini, and L. Regnier. Directed virtual reductions. In M. Bezem D. van Dalen, editor, LNCS 1258, pages 76–88. EACSL, Springer Verlag, 1997], namely a restriction of virtual reduction [V. Danos and L. Regnier. Local and asynchronous beta-reduction (an analysis of Girard's EX-formula). LICS, pages 296–306. IEEE Computer Society Press, 1993], which is a particular way to compute the Geometry of Interaction [J.-Y. Girard. Geometry of interaction 1: Interpretation of system F. In R. Ferro, et al. editors Logic Colloquium '88, pages 221–260. North-Holland, 1989] in analogy with Lamping's optimal reduction [J. Lamping. An algorithm for optimal lambda calculus reduction. In Proc. of 17th Annual ACM Symposium on Principles of Programming Languages. ACM, San Francisco, California, pages 16–30, 1990]. Moreover, the proposed solution preserves scalability of the parallelism arising from local and asynchronous reduction as studied in [M. Pedicini and F. Quaglia. PELCR: Parallel environment for optimal lambda-calculus reduction. CoRR, cs.LO/0407055, accepted for publication on TOCL, ACM, 2005].

We generalize a result of Dar{\'o}czy and K{\'a}tai, on the characterization of univoque numbers with respect to a non-integer base \cite{DarKat95} by relaxing the digit alphabet to a generic set of real numbers. We apply the result to derive the construction of a B\"uchi automaton accepting all and only the greedy sequences for a given base and digit set. In the appendix we prove a more general version of the fact that the expansion of an element $x\in \QQ(q)$ is ultimately periodic, if $q$ is a Pisot number.

Within the framework of generic programming, we implement an abstract algorithm for solution of an integral equation of the second kind with the resolvent kernels method. Then, as an application of the idempotent analysis analog of resolvent kernels developed in \cite{MR2002d:49038}, we apply the algorithm to the numerical solution of an optimal control problem with stopping time.