Updated: 12 hours 26 min ago

### Separable Statistics and Multidimensional Linear Cryptanalysis

Wed, 10/11/2017 - 12:39
Multidimensional linear cryptanalysis of block ciphers is improved in this work by introducing a number of new ideas. Firstly, formulae is given to compute approximate multidimensional distributions of encryption internal bits. Conventional statistics like LLR(Logarithmic Likelihood Ratio) do not fit to work in Matsui's Algorithm 2 for large dimension data, as the observation depend on too many cipher key bits. So, secondly, a new statistic which reflects the structure of the cipher round is constructed instead. Thirdly, computing the statistic values which fall into a critical region is presented as an optimisation problem for which an efficient algorithm is suggested. The algorithm works much faster than brute forcing all relevant key bits to compute the statistic. An attack for 16-round DES was implemented. We got an improvement over Matsui's attack on DES in data and time complexity keeping success probability the same.

### A Framework for Efficient Adaptively Secure Composable Oblivious Transfer in the ROM

Wed, 10/11/2017 - 12:38
Oblivious Transfer (OT) is a fundamental cryptographic protocol that finds a number of applications, in particular, as an essential building block for two-party and multi-party computation. We construct a round-optimal (2 rounds) universally composable (UC) protocol for oblivious transfer secure against active adaptive adversaries from any OW-CPA secure public-key encryption scheme with certain properties in the random oracle model (ROM). In terms of computation, our protocol only requires the generation of a public/secret-key pair, two encryption operations and one decryption operation, apart from a few calls to the random oracle. In~terms of communication, our protocol only requires the transfer of one public-key, two ciphertexts, and three binary strings of roughly the same size as the message. Next, we show how to instantiate our construction under the low noise LPN, McEliece, QC-MDPC, LWE, and CDH assumptions. Our instantiations based on the low noise LPN, McEliece, and QC-MDPC assumptions are the first UC-secure OT protocols based on coding assumptions to achieve: 1) adaptive security, 2) optimal round complexity, 3) low communication and computational complexities. Previous results in this setting only achieved static security and used costly cut-and-choose techniques. Our instantiation based on CDH achieves adaptive security at the small cost of communicating only two more group elements as compared to the gap-DH based Simplest OT protocol of Chou and Orlandi (Latincrypt 15), which only achieves static security in the ROM.

### Leakage Bounds for Gaussian Side Channels

Wed, 10/11/2017 - 12:38
In recent years, many leakage-resilient schemes have been published. These schemes guarantee security against side-channel attacks given bounded leakage of the underlying primitive. However, it is a challenging task to reliably determine these leakage bounds from physical properties. In this work, we present a novel approach to find reliable leakage bounds for side channels of cryptographic implementations when the input data complexity is limited such as in leakage-resilient schemes. By mapping results from communication theory to the side-channel domain, we show that the channel capacity is the natural upper bound for the mutual information (MI) to be learned from multivariate side-channels with Gaussian noise. It shows that this upper bound is determined by the device-specific signal-to-noise ratio (SNR). We further investigate the case when attackers are capable of measuring the same side-channel leakage multiple times and perform signal averaging. Our results here indicate that the gain in the SNR obtained from averaging is exponential in the number of points of interest that are used from the leakage traces. Based on this, we illustrate how the side-channel capacity gives a tool to compute the minimum attack complexity to learn a certain amount of information from side-channel leakage. We then show that our MI bounds match with reality by evaluating the MI in multivariate Gaussian templates built from practical measurements on an ASIC. We finally use our model to show the security of the Keccak-f[400]-based authenticated encryption scheme ISAP on this ASIC against power analysis attacks.

### Secure Code Updates for Smart Embedded Devices based on PUFs

Wed, 10/11/2017 - 12:35
Code update is a very useful tool commonly used in low-end embedded devices to improve the existing functionalities or patch discovered bugs or vulnerabilities. If the update protocol itself is not secure, it will only bring new threats to embedded systems. Thus, a secure code update mechanism is required. However, existing solutions either rely on strong security assumptions, or result in considerable storage and computation consumption, which are not practical for resource-constrained embedded devices (e.g., in the context of Internet of Things). In this work, we first propose to use intrinsic device characteristics (i.e., Physically Unclonable Functions or PUF) to design a practical and lightweight secure code update scheme. Our scheme can not only ensure the freshness, integrity, confidentiality and authenticity of code update, but also verify that the update is installed correctly on a specific device without any malicious software. Cloned or counterfeit devices can be excluded as the code update is bound to the unpredictable physical properties of underlying hardware. Legitimate devices in an untrustworthy software state can be restored by filling suspect memory with PUF-derived random numbers. After update installation, the initiator of the code update is able to obtain the verifiable software state from device, and the device can maintain a sustainable post-update secure check by enforcing a secure call sequence. To demonstrate the practicality and feasibility, we also implement the proposed scheme on a low-end MCU platform (TI MSP430) by using onboard SRAM and Flash resources.

### Bounds on the Differential Branch Number of Permutations

Wed, 10/11/2017 - 11:13
Nonlinear permutations (S-boxes) are key components in block ciphers. Differential branch number measures the diffusion power of a permutation. Differential branch number of nonlinear permutations of $\mathbb{F}_2^n$ has not been analyzed, although it is well studied for linear permutations. In this paper we obtain a bound on differential branch number of permutations (both linear and nonlinear) of $\mathbb{F}_2^n$. We also show that in case of $\mathbb{F}_2^4$, the maximum differential branch number can be achieved only by affine permutations.

### Decentralized Multi-Client Functional Encryption for Inner Product

Wed, 10/11/2017 - 11:12
Multi-input functional encryption is a very useful generalization of Functional Encryption, which has been motivated by Goldwasser et al. from Eurocrypt ’14. All the constructions, however, rely on non-standard assumptions. Very recently, at Eurocrypt ’17, Abdalla et al. considered a restricted case and proposed an efficient multi-input inner-product functional encryption scheme. In this paper, regarding the case of inner product, we argue that the multi-client setting (MCFE, for Multi-Client Functional Encryption), which borrows techniques from both Functional Encryption and Private Stream Aggregation, is better suited to real-life applications because of the strong restrictions implied by linear relations. We then propose a practical solution for Multi-Client Inner-Product Functional Encryption (IP-MCFE) which relies on the sole DDH assumption and supports adaptive corruptions. In MCFE schemes, each data input is encrypted by a different client, and the clients might not trust anybody for the functional decryption keys. It thus seems quite important to remove any authority, while allowing corruptions of the clients by the adversary. We thus propose the notion of Decentralized Multi-Client Functional Encryption (DMCFE) and provide a generic construction from two MCFE schemes with particular properties. More concretely, combining two instantiations of our previous IP-MCFE, we can build an efficient and non-interactive decentralized scheme for inner product. Our construction relies on the SXDH assumption, and supports adaptive corruptions in the random oracle model.

### On Rejection Sampling Algorithms for Centered Discrete Gaussian Distribution over Integers

Wed, 10/11/2017 - 11:11
Lattice-based cryptography has been accepted as a promising candidate for public key cryptography in the age of quantum computing. Discrete Gaussian sampling is one of fundamental operations in many lattice-based cryptosystems. In this paper, we discuss a sub-problem of discrete Gaussian sampling, which is to sample from a centered discrete Gaussian distribution over the integers with positive standard deviation and zero center. We propose three alternative rejection sampling algorithms for centered discrete Gaussian distributions with standard deviation in two specific forms. The first algorithm is designed for the case where the standard deviation is an positive integer, and it requires neither pre-computation storage nor floating-point arithmetic. While the other two algorithms are fit for a standard deviation that is an integer multiple of a fixed real number (approximately equal to 0.849). These two algorithms require fixed look-up tables of very small size (e.g. 128 bits and 320 bits respectively), but they are much more efficient than the first algorithm. The experimental results show that our algorithms have better performance than that of two rejection sampling algorithms proposed by Karney in 2016 and by Ducas et al.\ in 2013 respectively. The expected numbers of random bits used in our algorithms are significantly smaller than that of random bits used in Karney's rejection sampling algorithm.

### Towards Sound and Optimal Leakage Detection Procedure (Extended Version)

Wed, 10/11/2017 - 10:27
Evaluation of side channel leakage for the embedded crypto systems requires sound leakage detection procedures. We relate the test vector leakage assessment (TVLA) procedure to the statistical minimum p-value (mini-p) procedure, and propose a sound method of deciding leakage existence in the statistical hypothesis setting. To improve detection, an advanced statistical procedure Higher Criticism (HC) is applied. The detection of leakage existence and the identification of exploitable leakage are separated when there are multiple leakage points. For leakage detection, the HC-based procedure is shown to be optimal in that, for a given number of traces with given length, it detects existence of leakage at the signal level as low as possibly detectable by any statistical procedure. We provide theoretical proof of the optimality of the HC procedure. Numerical studies show that the HC-based procedure perform as well as the mini-p based procedure when leakage signals are very sparse, and can improve the leakage detection significantly when there are multiple leakages.

### Searchable Encrypted Relational Databases: Risks and Countermeasures

Wed, 10/11/2017 - 05:41
We point out the risks of protecting relational databases via Searchable Symmetric Encryption (SSE) schemes by proposing an inference attack exploiting the structural properties of relational databases. We show that record-injection attacks mounted on relational databases have worse consequences than their file-injection counterparts on unstructured databases. Moreover, we discuss some techniques to reduce the effectiveness of inference attacks exploiting the access pattern leakage existing in SSE schemes. To the best of our knowledge, this is the first work that investigates the security of relational databases protected by SSE schemes.

### Reducing Communication Channels in MPC

Wed, 10/11/2017 - 05:24
In both information theoretic and computationally secure Multi-Party Computation (MPC) protocols the parties are usually assumed to be connected by a complete network of, respectively, secure or authenticated channels. Taking inspiration from a recent, highly efficient, 1-out-of-3 computationally secure MPC protocol of Araki et al, we show how to perform computationally secure MPC for an arbitrary $Q^2$ access structure over an incomplete network. Our tool is to combine the practical techniques of Araki with the information theoretic approach of Maurer for arbitrary $Q^2$ structures. We present both passive and actively secure (with abort) variants of our protocol. In all cases we require less communication channels than Maurer's protocol, at the expense of requiring pre-shared secret keys for Pseudo-Random Functions (PRFs). By shedding light on the theoretical underpinnings of the recent protocol of Araki et al. we hope that our work may result in future highly communication-efficient protocols for other access structures.

### A Side-Channel Assisted Cryptanalytic Attack Against QcBits

Wed, 10/11/2017 - 05:24
QcBits is a code-based public key algorithm based on a problem thought to be resistant to quantum computer attacks. It is a constant time implementation for a quasi-cyclic moderate density parity check (QC-MDPC) Niederreiter encryption scheme, and has excellent performance and small key sizes. In this paper, we present a key recovery attack against QcBits. We first used differential power analysis (DPA) against the syndrome computation of the decoding algorithm to recover partial information about one half of the private key. We then used the recovered information to set up a system of noisy binary linear equations. Solving this system of equations gave us the entire key. Finally, we propose a simple but effective countermeasure against the power analysis used during the syndrome calculation.

### Forward-Security under Continual Leakage

Tue, 10/10/2017 - 20:46
Current signature and encryption schemes secure against continual leakage fail completely if the key in any time period is fully exposed. We suggest forward security as a second line of defense, so that in the event of full exposure of the current secret key, at least uses of keys prior to this remain secure, a big benefit in practice. (For example if the signer is a certificate authority, full exposure of the current secret key would not invalidate certificates signed under prior keys.) We provide definitions for signatures and encryption that are forward-secure under continual leakage. Achieving these definitions turns out to be challenging, and we make initial progress with some constructions and transforms.

### Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model

Tue, 10/10/2017 - 17:49
Non-malleable codes were introduced by Dziembowski et al. (ICS 2010) as coding schemes that protect a message against tampering attacks. Roughly speaking, a code is non-malleable if decoding an adversarially tampered encoding of a message m produces the original message m or a value m' (eventually abort) completely unrelated with m. It is known that non-malleability is possible only for restricted classes of tampering functions. Since their introduction, a long line of works has established feasibility results of non-malleable codes against different families of tampering functions. However, for many interesting families the challenge of finding "good" non-malleable codes remains open. In particular, we would like to have explicit constructions of non-malleable codes with high-rate and efficient encoding/decoding algorithms (i.e. low computational complexity). In this work we present two explicit constructions: the first one is a natural generalization of the work of Dziembowski et al. and gives rise to the first constant-rate non-malleable code with linear-time complexity (in a model including bit-wise indepen- dent tampering). The second construction is inspired by the recent works about non-malleable codes of Agrawal et al. (TCC 2015) and of Cher- aghchi and Guruswami (TCC 2014) and improves the previous result in the bit-wise tampering model: it builds the first non-malleable codes with linear-time complexity and optimal-rate (i.e. rate 1 - o(1)).

### REM: Resource-Efficient Mining for Blockchains

Tue, 10/10/2017 - 15:56
Blockchains show promise as potential infrastructure for financial transaction systems. The security of blockchains today, however, relies critically on Proof-of-Work (PoW), which forces participants to waste computational resources. We present REM (Resource-Efficient Mining), a new blockchain mining framework that uses trusted hardware (Intel SGX). REM achieves security guarantees similar to PoW, but leverages the partially decentralized trust model inherent in SGX to achieve a fraction of the waste of PoW. Its key idea, Proof-of-Useful-Work (PoUW), involves miners providing trustworthy reporting on CPU cycles they devote to inherently useful workloads. REM flexibly allows any entity to create a useful workload. REM ensures the trustworthiness of these workloads by means of a novel scheme of hierarchical attestations that may be of independent interest. To address the risk of compromised SGX CPUs, we develop a statistics-based formal security framework, also relevant to other trusted-hardware-based approaches such as Intel's Proof of Elapsed Time (PoET). We show through economic analysis that REM achieves less waste than PoET and variant schemes. We implement REM and, as an example application, swap it into the consensus layer of Bitcoin core. The result is the first full implementation of an SGX-based blockchain. We experiment with four example applications as useful workloads for our implementation of REM, and report a computational overhead of $5-15\%$.

### Statistical and Linear Independence of Binary Random Variables

Tue, 10/10/2017 - 07:05
Linear cryptanalysis makes use of statistical models that consider linear approximations over block cipher and random permutation as binary random variables. In this note we develop conditions under which linear independence of binary random variables and statistical independence of their correlations are equivalent properties. As an application we obtain that the correlations of linear combinations of the components of a random $n$-bit to $m$-bit transformation are statistically independent if and only if these linear combinations are linearly independent.

### New Approach to Practical Leakage-Resilient Public-Key Cryptography

Tue, 10/10/2017 - 04:52
We present a new approach to construct several leakage-resilient cryptographic primitives, including leakage-resilient public-key encryption (PKE) schemes, authenticated key exchange (AKE) protocols and low-latency key exchange (LLKE) protocols. To this end, we introduce a new primitive called leakage-resilient non-interactive key exchange (LR-NIKE) protocol. We introduce a generic security model for LR-NIKE protocols, which can be instantiated in both the bounded and continuous-memory leakage ((B/C)-ML) settings. We then show a secure construction of LR-NIKE protocol in the bounded- memory leakage (BML) setting, that achieves an optimal leakage rate, i.e., 1-o(1). Finally, we show how to construct the aforementioned leakage-resilient primitives from such a LR-NIKE protocol as summarized below. All the primitives also achieve the same (optimal) leakage rate as the underlying LR-NIKE protocol. We show how to construct a leakage-resilient IND-CCA-2-secure PKE scheme in the BML model generically from a LR-NIKE protocol. Our construction differs from the state-of-the-art constructions of leakage-resilient IND-CCA-2-secure PKE schemes, which use hash proof techniques to achieve leakage-resilience. Moreover, our transformation preserves the leakage-rate of the underlying LR- NIKE and admits more efficient construction than previous such PKE constructions. We introduce a new leakage model for AKE protocols, in the BML setting. We show how to construct a leakage-resilient AKE protocol starting from LR-NIKE protocol. We introduce the first-ever leakage model for LLKE protocols in the BML setting, and the first construction of such a leakage-resilient LLKE from LR-NIKE protocol.

### Security considerations for Galois non-dual RLWE families

Mon, 10/09/2017 - 17:36
We explore further the hardness of the non-dual discrete variant of the Ring-LWE problem for various number rings, give improved attacks for certain rings satisfying some additional assumptions, construct a new family of vulnerable Galois number fields, and apply some number theoretic results on Gauss sums to deduce the likely failure of these attacks for 2-power cyclotomic rings and unramified moduli.

### Attacks on the Search-RLWE problem with small error

Mon, 10/09/2017 - 15:58
The Ring Learning-With-Errors (RLWE) problem shows great promise for post-quantum cryptography and homomorphic encryption. We describe a new attack on the non-dual search RLWE problem with small error widths, using ring homomorphisms to finite fields and the chi-squared statistical test. In particular, we identify a subfield vulnerability'' (Section 5.2) and give a new attack which finds this vulnerability by mapping to a finite field extension and detecting non-uniformity with respect to the number of elements in the subfield. We use this attack to give examples of vulnerable RLWE instances in Galois number fields. We also extend the well-known search-to-decision reduction result to Galois fields with any unramified prime modulus $q$, regardless of the residue degree $f$ of $q$, and we use this in our attacks. The time complexity of our attack is $O(n q^{2f})$, where $n$ is the degree of $K$ and $f$ is the {\it residue degree} of $q$ in $K$. We also show an attack on the non-dual (resp. dual) RLWE problem with narrow error distributions in prime cyclotomic rings when the modulus is a ramified prime (resp. any integer). We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.

### Robust Transforming Combiners from Indistinguishability Obfuscation to Functional Encryption

Mon, 10/09/2017 - 15:07
Indistinguishability Obfuscation (iO) has enabled an incredible number of new and exciting applications. However, our understanding of how to actually build secure iO remains in its infancy. While many candidate constructions have been published, some have been broken, and it is unclear which of the remaining candidates are secure. This work deals with the following basic question: \emph{Can we hedge our bets when it comes to iO candidates?} In other words, if we have a collection of iO candidates, and we only know that at least one of them is secure, can we still make use of these candidates? This topic was recently studied by Ananth, Jain, Naor, Sahai, and Yogev [CRYPTO 2016], who showed how to construct a robust iO combiner: Specifically, they showed that given the situation above, we can construct a single iO scheme that is secure as long as (A) at least one candidate iO scheme is a subexponentially secure iO, and (B) either the subexponential DDH or LWE assumptions hold. In this work, we make three contributions: \begin{itemize} \item (\textbf{Better robust iO combiners.}) First, we work to improve the assumptions needed to obtain the same result as Ananth et al.: namely we show how to replace the DDH/LWE assumption with the assumption that subexponentially secure one-way functions exist. \item (\textbf{FE and NIKE from iO candidates and minimal assumptions.}) Second, we consider a broader question: what if we start with several iO candidates where only one works, but we don't care about achieving iO itself, rather we want to achieve concrete applications of iO? In this case, we are able to work with the \emph{minimal} assumption of just polynomially secure one-way functions, and where the working iO candidate only achieves polynomial security. Under these circumstances, we show how to achieve both \emph{functional encryption} and \emph{non-interactive multiparty key exchance (NIKE)}. \item (\textbf{Correctness Amplification for iO from polynomial security and one-way functions.}) Finally, along the way, we obtain a result of independent interest: Recently, Bitansky and Vaikuntanathan [TCC 2016] showed how to amplify the correctness of an iO scheme, but they needed subexponential security for the iO scheme and also require subexponentially secure DDH or LWE. We show how to achieve the same correctness amplification result, but requiring only polynomial security from the iO scheme, and assuming only polynomially secure one-way functions. \end{itemize}

### Efficient Maliciously Secure Multiparty Computation for RAM

Mon, 10/09/2017 - 14:04
A crucial issue, that mostly affects the performance of actively secure computation of RAM programs, is the task of reading/writing from/to memory in a private and authenticated manner. Previous works in the active security and multiparty settings are based purely on the SPDZ (reactive) protocol, hence, memory accesses are treated just like any input to the computation. However, a garbled-circuit-based construction (such as BMR), which benefits from a lower round complexity, must resolve the issue of converting memory data bits to their corresponding wire keys and vice versa. In this work we propose three techniques to construct a secure memory access, each appropriates to a different level of abstraction of the underlying garbling functionality. We provide a comparison between the techniques by several metrics. To the best of our knowledge, we are the first to construct, prove and implement a concretely efficient garbled-circuit-based actively secure RAM computation with dishonest majority. Our construction is based on our third (most efficient) technique, cleverly utilizing the underlying SPDZ authenticated shares (Damgård et al., Crypto 2012), yields lean circuits and a constant number of communication rounds per physical memory access. Specifically, it requires no additional circuitry on top of the ORAM's, incurs only two rounds of broadcasts between every two memory accesses and has a multiplicative overhead of 2 on top of the ORAM's storage size. Our protocol outperforms the state of the art in this settings when deployed over WAN. Even when simulating a very conservative RTT of 100ms our protocol is at least one order of magnitude faster than the current state of the art protocol of Keller and Scholl (Asiacrypt 2015).