*03:17* [Pub][ePrint]
Fault Analysis of Kuznyechik, by Riham AlTawy and Onur Duman and Amr M. Youssef
Kuznyechik is an SPN block cipher that has been chosen recently to be standardized by the Russian federation as a new GOST cipher. In this paper, we present two fault analysis attacks on two different settings of the cipher. The first attack is a differential fault attack which employs the random byte fault model, where the attackeris assumed to be able to fault a random byte in rounds seven and eight. Using this fault model enables the attacker to recover the master key using an average of four faults. The second attack considers the cipher with a secret sbox. By utilizing an ineffective fault analysis in the byte stuck-at-zero fault model, we present a four stage attack to recover both the master key and the secret sbox parameters. Our second attack is motivated by the fact that, similar to GOST 28147-89, Kuznyechik is expected to include the option of using secret sbox based on the user supplied key to increase its security margin. Both the presented attacks have practical complexities and aim to demonstrate the importance of protecting the hardware and software implementations of the new standard even if its sbox is kept secret.

*03:17* [Pub][ePrint]
Database Outsourcing with Hierarchical Authenticated Data Structures, by Mohammad Etemad and Alptekin Küpçü
In an outsourced database scheme, the data owner delegates the data management tasks to a remote service provider. At a later time, the remote service is supposed to answer any query on the database. The essential requirements are ensuring the data integrity and authenticity with efficient mechanisms. Current approaches employ authenticated data structures to store security information, generated by the client and used by the server, to compute proofs that show the answers to the queries are authentic. The existing solutions have shortcomings with multi-clause queries and duplicate values in a column.We propose a hierarchical authenticated data structure for storing security information, which alleviates the mentioned problems. Our solution handles many different types of queries, including multi-clause selection and join queries, in a dynamic database. We provide a unified formal definition of a secure outsourced database scheme, and prove that our proposed scheme is secure according to this definition, which captures previously separate properties such as correctness, completeness, and freshness. The performance evaluation based on our prototype implementation confirms the efficiency of our proposed scheme, showing about 3x to 5x enhancement in proof size and proof generation time in comparison to previous work, and about only 4% communication overhead compared to the actual query result in a real university database.

*03:17* [Pub][ePrint]
Broadcast from Minicast Secure Against General Adversaries, by Pavel Raykov
Byzantine broadcast is a distributed primitive that allows a specific party to consistently distribute a message among $n$ parties in the presence of potential misbehavior of up to $t$ of the parties. The celebrated result of \\cite{PSL80} shows that broadcast is achievable from point-to-point channels if and only if $t < n/3$.The following two generalizations have been proposed to the original broadcast problem. In~\\cite{FM98} the authors considered a \\emph{general adversary} characterized by the sets of parties that can be corrupted. It was shown that broadcast is achievable from point-to-point channels if and only if no three possible corrupted sets can cover the whole party set. In~\\cite{CFFLMM05} the notion of point-to-point channels has been extended to the $b$-minicast channels allowing to locally broadcast among any subset of $b$ parties. It has been shown that broadcast secure against adversaries corrupting up to $t$ parties is achievable from $b$-minicast if and only if $t < \\frac{b-1}{b+1}n$.

In this paper we combine both generalizations by considering the problem of achieving broadcast from $b$-minicast channels secure against general adversaries. Our main result is a condition on the possible corrupted sets such that broadcast is achievable from $b$-minicast if and only if this condition holds.

*03:17* [Pub][ePrint]
Matrix Computational Assumptions in Multilinear Groups, by Paz Morillo and Carla R\\`afols and Jorge L. Villar
We put forward a new family of computational assumptions, the Kernel Matrix Diffie-Hellman Assumption. This family abstracts and includes as a special case several assumptions used in the literature under different names. Given some matrix $\\matrA$ sampled from some distribution $\\mathcal{D}_{\\ell,k}$, the kernel assumption saysthat it is hard to find ``in the exponent\'\' a nonzero vector in the kernel of $\\mathbf{A}^\\top$. Our assumption is the natural computational analogue of the Matrix Decisional Diffie-Hellman Assumption (MDDH), proposed by Escala \\textit{et al}.

We show that the $\\mathcal{D}_{\\ell,k}$ Kernel DH Assumption is a strictly increasing family of weaker computational assumptions when $k$ grows. This requires ruling out the existence of some black-box reductions between flexible problems (\\textit{i.e.}, computational problems with a non unique solution), which is specially subtle.

As opposed to the decisional MDDH Assumption, our kernel assumption might hold in the recent candidate multilinear groups.

Kernel assumptions have implicitly been used in recent works on QA-NIZK and structure-preserving signatures. We also provide a new construction of commitments to group elements in the multilinear setting, based on any kernel assumption.

*03:17* [Pub][ePrint]
SEMA and MESD Leakage of TinyECC 2.0 on a LOTUS Sensor Node, by Jacek Samotyja and Kerstin Lemke-Rust and Markus Ullmann
TinyECC 2.0 is an open source library for Elliptic Curve Cryptography (ECC) in wireless sensor networks. This paper analyzes the side channel susceptibility of TinyECC 2.0 on a LOTUS sensor node platform. In our work we measured the electromagnetic (EM) emanation during computation of the scalar multiplication using 56 different configurations of TinyECC 2.0. All of them were found to be vulnerable, but to a different degree. The different degrees of leakage include adversary success using (i) Simple EM Analysis (SEMA) with a single measurement, (ii) SEMA using averaging, and (iii) Multiple-Exponent Single-Data (MESD) with a single measurement of the secret scalar. It is extremely critical that in 30 TinyECC 2.0 configurations a single EM measurement of an ECC private key operation is sufficient to simply read out the secret scalar. MESD requires additional adversary capabilities and it affects all TinyECC 2.0 configurations, again with only a single measurement of the ECC private key operation. These findings give evidence that in security applications a configuration of TinyECC 2.0 should be chosen that withstands SEMA with a single measurement and, beyond that, an addition of appropriate randomizing countermeasures is necessary.

*06:17* [Pub][ePrint]
Two Round MPC from LWE via Multi-Key FHE, by Pratyay Mukherjee and Daniel Wichs
We construct a general multiparty computation (MPC) protocol in the common random string (CRS) model with only two rounds of interaction, which is known to be optimal. In the honest-but-curious setting we only rely on the learning with errors (LWE) assumption, and in the fully malicious setting we additionally assume the existence of non-interactive zero knowledge arguments (NIZKs). Previously, Asharov et al. (EUROCRYPT \'12) showed how to achieve three rounds based on LWE and NIZKs, while Garg et al. (TCC \'14) showed how to achieve the optimal two rounds based on indistinguishability obfuscation, but it was unknown if two rounds were possible under simpler assumptions without obfuscation.Our approach relies on \\emph{multi-key fully homomorphic encryption (MFHE)}, introduced by Lopez-Alt et al. (STOC \'12), which enables homomorphic computation over data encrypted under different keys. We simplify a recent construction of MFHE based on LWE by Clear and McGoldrick (ePrint \'14), and give a stand-alone exposition of that scheme. We then extend this construction to allow for a one-round distributed decryption of a multi-key ciphertext. Our entire MPC protocol consists of the following two rounds:

- Each party individually encrypts its input under its own key and broadcasts the ciphertext. All parties can then homomorphically compute a multi-key encryption of the output.

- Each party broadcasts a partial decryption of the output using its secret key. The partial decryptions can be combined to recover the output in plaintext.

*06:17* [Pub][ePrint]
End-to-End Verifiable Elections in the Standard Model∗ , by Aggelos Kiayias and Thomas Zacharias and Bingsheng Zhang
We present the cryptographic implementation of \"DEMOS\", a new e-voting system that is end-to-end verifiable in the standard model, i.e., without any additional \"setup\" assumption or access to a random oracle (RO). Previously known end-to-end verifiable e-voting systems required such additional assumptions (specifically, either the existence of a \"randomness beacon\" or were only shown secure in the RO model). In order to analyze our scheme, we also provide a modeling of end-to-end verifiability as well as privacy and receipt-freeness that encompasses previous definitions inthe form of two concise attack games.

Our scheme satisfies end-to-end verifiability information theoretically in the standard model and privacy/receipt-freeness under a computational assumption (subexponential Decisional Diffie Helman). In our construction, we utilize a number of techniques used for the first time in the context of e-voting schemes that include utilizing randomness from bit-fixing sources, zero-knowledge proofs with imperfect verifier randomness and complexity leveraging.