Progress in Cryptology - AFRICACRYPT 2017

Multivariate Cryptography is one of the main candidates for creating post-quantum cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. However, there is a lack of more advanced schemes, such as schemes for oblivious transfer and signature schemes with special properties. While, in the last years, a number of multivariate ring signature schemes have been proposed, all of these have weaknesses in terms of security or efficiency. In this paper we propose a simple and efficient technique to extend arbitrary multivariate signature schemes to ring signature schemes and illustrate it using the example of Rainbow. The resulting scheme provides perfect anonymity for the signer (as member of a group), as well as shorter ring signatures than all previously proposed post-quantum ring signature schemes.

Pinocchio is a practical zk-SNARK that allows a prover to perform cryptographically verifiable computations with verification effort potentially less than performing the computation itself. A recent proposal showed how to make Pinocchio adaptive (or “hash-and-prove”), i.e., to enable proofs with respect to computation-independent commitments. This enables computations to be chosen after the commitments have been produced, and for data to be shared between different computations in a flexible way. Unfortunately, this proposal is not zero-knowledge. In particular, it cannot be combined with Trinocchio, a system in which Pinocchio is outsourced to three workers that do not learn the inputs thanks to multi-party computation (MPC). In this paper, we show how to make Pinocchio adaptive in a zero-knowledge way; apply this to make Trinocchio work on computation-independent commitments; present tooling to easily program flexible verifiable computations (with or without MPC); and use it to build a prototype in a medical research case study.

In 2010, Resch and Plank proposed a computationally secure secret sharing scheme, called AONT-RS. We present a generalisation of their scheme and discuss two ways in which information is leaked if used to distribute small ciphertexts. We discuss how to prevent such leakage and provide a proof of computational privacy in the random oracle model. Next, we extend the scheme to be robust and prove the robust AONT-RS achieves computational privacy in the random oracle model and computational recoverability under standard assumptions. Finally, we compare the security, share size and complexity of the AONT-RS scheme with Krawczyk’s SSMS scheme.

Machine learning techniques represent a powerful paradigm in side-channel analysis, but they come with a price. Selecting the appropriate algorithm as well as the parameters can sometimes be a difficult task. Nevertheless, the results obtained usually justify such an effort. However, a large part of those results use simplification of the data relation and in fact do not consider allthe available information. In this paper, we analyze the hierarchical relation between the data and propose a novel hierarchical classification approach for side-channel analysis. With this technique, we are able to introduce two new attacks for machine learning side-channel analysis: Hierarchical attack and Structured attack. Our results show that both attacks can outperform machine learning techniques using the traditional approach as well as the template attack regarding accuracy. To support our claims, we give extensive experimental results and discuss the necessary conditions to conduct such attacks.

Latest nanometer CMOS technology nodes have highlighted new issues in security of cryptographic hardware implementations. The constant growth of the static power consumption has led to a new class of side-channel attacks. Common attacks exploiting static power use an univariate approach to recover information from cryptographic engines. In our work, a multivariate approach based on information theoretic security metrics is presented. The temperature-dependence helps to exploit more information leakage from the hardware implementation. Starting from a univariate analysis, mutual information reveals that increasing the working temperature, the information leaked through the static power side channel is increased as well. In this work a multivariate analysis exploiting static power consumption is presented in which the temperature-domain is used to extract more information. The use of information theoretic approach allows to precisely quantify the amount of information that can be leaked from a cryptographic hardware implementation. The perceived information shows taking advantage of the use of more than one temperature, the security level can be decreased. The improvement achieved using the presented approach is demonstrated on a 40 nm CMOS implementation of the Present 80 crypto core.

In the formal analysis of side-channel attacks, a theoretical model of side-channel information (leakage model) is supposed and dedicated attacks for the model are considered. In ASIACRYPT2015, a new leakage model for the analysis of block cipher was proposed by Bogdanov et al. The model assumes an adversary who has leaked values whose positions are unknown and randomly chosen from internal results (random leakage model). They also proposed an attack, differential bias attack for the model. This paper improves the security analysis on AES under the random leakage model. In the previous method, the adversary requires at least \(2^{34}\) chosen plaintexts, therefore, it is infeasible to recover a secret key with a small number of data. However, there may be an adversary who can recover the secret key using his computing power. To consider the security against the adversary, we reestimate complexity for the adversary given a small number of data. We propose another hypothesis-testing method which can minimize the number of required data. The reestimation of complexity shows that the proposed method requires time complexity more than \(T>2^{60}\) because of time-data tradeoff, however, some attacks are feasible under \(T\le 2^{80}\). In addition to the above method, we apply key enumeration to differential bias attack, and evaluate its efficiency by rank estimation. From the experimental evaluation, we show that the success rate of the attack can be practical if there is an advantageous restriction on the positions of leaked values.

SKINNY is a new lightweight tweakable block cipher family proposed by Beierle et al. at CRYPTO 2016. SKINNY has 6 main variants where SKINNY-n-t is a block cipher that operates on n-bit blocks using t-bit tweakey (key and tweak) where \(n=64\) or 128 and \(t=n\), 2n, or 3n. In this paper, we present impossible differential attacks against reduced-round versions of all the 6 members of the SKINNY family in the single-tweakey model. More precisely, using an 11-round impossible differential distinguisher, we present impossible differential attacks against 18-round SKINNY-n-n, 20-round SKINNY-n-2n and 22-round SKINNY-n-3n (\(n=64\) or 128). To the best of our knowledge, these are the best attacks against these 6 variants in the single-tweakey model.

SPARX-64/128 is an ARX-based block cipher with 64-bit block size and 128-bit key. It was published in ASIACRYPT 2016 as one of the instantiations of a family of ARX-based block ciphers with provable security against single-characteristic differential and linear cryptanalysis. In this work, we present 12 and 13-round impossible distinguishers on SPARX-64/128 that can be used to attack 15 and 16-round SPARX-64/128 with post-whitening keys, respectively. While the 15-round attack starts from round 0, the 16-round one, exploiting the key schedule, has to start from round 2.

In this paper, we propose an efficient protocol to process a private conjunctive query over encrypted data in the cloud using the somewhat homomorphic encryption (SwHE) scheme with a batch technique. In 2016, Cheon, Kim, and Kim (CKK) [IEEE Trans. Inf. Forensics Security] showed conjunctive query processing over encrypted data using search-and-compute circuits and an SwHE scheme and mentioned that their scheme should be improved in performance. To improve the performance of processing a private conjunctive query, we also propose a new packing method to support an efficient batch computation for our protocol using a few multiplications. Our implementation shows that our protocol works more than 50 times as fast as the CKK protocol for conjunctive query processing. In addition, the security level of our protocol is better than the security level of the CKK protocol.

In this article, a new oblivious transfer (OT) protocol, secure in the presence of erasure-free one-sided active adaptive adversaries is presented. The new bit OT protocol achieves better communication complexity than the existing bit OT protocol in this setting. The new bit OT protocol requires fewer number of public key encryption operations than the existing bit OT protocol in this setting. As a building block, a new two-party lossy threshold homomorphic public key cryptosystem is designed. It is secure in the same adversary model. It is of independent interest.

While the smart grid has the potential to have a positive impact on the sustainability and efficiency of the electricity market, it also poses some serious challenges with respect to the privacy of the consumer. One of the traditional use-cases of this privacy sensitive data is the usage for forecast prediction. In this paper we show how to compute the forecast prediction such that the supplier does not learn any individual consumer usage information. This is achieved by using the Fan-Vercauteren somewhat homomorphic encryption scheme. Typical prediction algorithms are based on artificial neural networks that require the computation of an activation function which is complicated to compute homomorphically. We investigate a different approach and show that Ivakhnenko’s group method of data handling is suitable for homomorphic computation.

Our results show this approach is practical: prediction for a small apartment complex of 10 households can be computed homomorphically in less than four seconds using a parallel implementation or in about half a minute using a sequential implementation. Expressed in terms of the mean absolute percentage error, the prediction accuracy is roughly \(21\%\).

Many authors have studied the problem of constructing indifferentiable and deterministic hash functions into elliptic and hyperelliptic curves with well-distributed encodings. In this work, we have designed three encodings suitable for indifferentiable hashing for the following hyperellitic curves of genus 2: \(\mathbb {H}^{1}: y^{2}=F_{1}(x)=x^{5}+ax^{4}+cx^{2}+dx, \ \mathbb {H}^{2}: y^{2}=F_{2}(x)=x^{5}+bx^{3}+dx+e; \ \mathbb {H}^{3}: y^{2}=F_{3}(x)=x^{5}+ax^{4}+e\). Since they are well-distributed, our encodings can be used to design indifferentiable and deterministic hash functions into the Jacobian of these hyperelliptic curves, using the technique developed by Farashahi et al. in 2013 (J. Math. Comput). Because of square rooting steps, these new encodings have the same asymptotic complexity as the work of Kammerer et al. at Pairing 2010, namely \(\mathcal {O}(\log ^{2+\circ (1)}q)\).

We address a cryptanalysis of two protocols based on the supposed difficulty of discrete logarithm problem on (semi) groups of matrices over a group ring. We can find the secret key and break entirely the protocols.