Updated: 9 hours 30 min ago

### Context Hiding Multi-Key Linearly Homomorphic Authenticators

Tue, 06/26/2018 - 12:00
Demanding computations are increasingly outsourced to cloud platforms. For such outsourced computations, the efficient verifiability of results is a crucial requirement. When sensitive data is involved, the verification of a computation should preserve the privacy of the input values: it should be context hiding. Context hiding verifiability is enabled by existing homomorphic authenticator schemes. However, until now, no context hiding homomorphic authenticator scheme supports multiple independent clients, e.g. multiple keys. Multi-key support is necessary for datasets involving input authenticated by different clients, e.g. multiple hospitals in e-health scenarios. In this paper, we propose the first perfectly context hiding, publicly verifiable multi-key homomorphic authenticator scheme supporting linear functions. Our scheme is provably unforgeable in the standard model, and succinct. Verification time depends only linearly on the number of clients, in an amortized sense.

### Dynamic Searchable Symmetric Encryption Schemes Supporting Range Queries with Forward (and Backward) Security

Tue, 06/26/2018 - 12:00
Dynamic searchable symmetric encryption (DSSE) is a useful cryptographic tool in the encrypted cloud storage. However, it has been reported that DSSE usually suffers from the file-injection attacks and content leak of deleted documents. To mitigate these attacks, forward security and backward security have been proposed. Nevertheless, the existing forward/backward-secure DSSE schemes can only support single keyword queries. To address this problem, in this paper, we propose two DSSE schemes supporting range queries. One is forward-secure and supports a large number of documents. The other can achieve both forward security and backward security, while it can only support a limited number of documents. Finally, we also give the security proofs of the proposed DSSE schemes in the random oracle model.

### Efficient Evaluation of Low Degree Multivariate Polynomials in Ring-LWE Homomorphic Encryption Schemes

Tue, 06/26/2018 - 11:54
Homomorphic encryption schemes allow to perform computations over encrypted data. In schemes based on RLWE assumption the plaintext data is a ring polynomial. In many use cases of homomorphic encryption only the degree-0 coefficient of this polynomial is used to encrypt data. In this context any computation on encrypted data can be performed. It is trickier to perform generic computations when more than one coefficient per ciphertext is used. In this paper we introduce a method to efficiently evaluate low-degree multivariate polynomials over encrypted data. The main idea is to encode several messages in the coefficients of a plaintext space polynomial. Using ring homomorphism operations and multiplications between ciphertexts, we compute multivariate monomials up to a given degree. Afterwards, using ciphertext additions we evaluate the input multivariate polynomial. We perform extensive experimentations of the proposed evaluation method. As example, evaluating an arbitrary multivariate degree-3 polynomial with 100 variables over Boolean space takes under 13 seconds.

### Blockchain and Consensus from Proofs of Work without Random Oracles

Mon, 06/25/2018 - 11:58
One of the most impactful applications of proofs of work'' (POW) currently is in the design of blockchain protocols such as Bitcoin. Yet, despite the wide recognition of POWs as the fundamental cryptographic tool in this context, there is no known cryptographic formulation that implies the security of the Bitcoin blockchain protocol. Indeed, all previous works formally arguing the security of the Bitcoin protocol relied on direct proofs in the random oracle model, thus circumventing the difficulty of isolating the required properties of the core POW primitive. In this work we fill this gap by providing a formulation of the POW primitive that implies the security of the Bitcoin blockchain protocol in the standard model. Our primitive entails a number of properties that parallel an efficient non-interactive proof system: completeness and fast verification, security against malicious provers (termed hardness against tampering and chosen message attacks'') and efficiency and security for honest provers (the latter captured as almost $k$-wise independence of the proving algorithm running time). Interestingly, our formulation is incomparable with previous formulations of POWs that applied the primitive to contexts other than the blockchain and highlights the importance of {\em run-time independence} as a property for POWs suitable for blockchain protocols. Using our primitive and standard properties of the underlying hash function, we establish the security of the Bitcoin backbone protocol [Eurocrypt 2015] without relying on random oracles. We then tackle the question of constructing a consensus protocol based on POW. We illustrate that previously known solutions essentially relied on the random oracle and propose a new blockchain-based consensus protocol provably secure under the same assumptions as above. This yields the first consensus protocol for honest majority reducible to a POW primitive without random oracles.

### Optimally Resilient and Adaptively Secure Multi-Party Computation with Low Communication Locality

Sun, 06/24/2018 - 22:44
Secure multi-party computation (MPC) has been thoroughly studied over the past decades. The vast majority of works assume a full communication pattern: every party exchanges messages with {\em all} the network participants over a complete network of point-to-point channels. This can be problematic in modern large scale networks, where the number of parties can be of the order of millions, as for example when computing on large distributed data. Motivated by the above observation, Boyle, Goldwasser, and Tessaro [TCC 2013] recently put forward the notion of {\em communication locality}, namely, the total number of point-to-point channels that each party uses in the protocol, as a quality metric of MPC protocols. They proved that assuming a public-key infrastructure (PKI) and a common reference string (CRS), an MPC protocol can be constructed for computing any $n$-party function, with communication locality $\bigo[\log^c n]$ and round complexity $\bigo[\log^{c'} n]$, for appropriate constants $c$ and $c'$. Their protocol tolerates a static (i.e., non-adaptive) adversary corrupting up to $t<(\frac{1}{3}-\epsilon)n$ parties for any given constant $0<\epsilon<\frac{1}{3}$. These results leave open the following questions: (1) Can we achieve low communication locality and round complexity while tolerating {\em adaptive} adversaries? \\ (2) Can we achieve low communication locality with {\em optimal resiliency} $t<n/2$? In this work we answer both questions affirmatively. First, we consider the model from [TCC 2013], where we replace the CRS with a symmetric-key infrastructure (SKI). In this model we give a protocol with communication locality and round complexity \polylog[n] (as in the [TCC~2013] work) which tolerates up to $t<n/2$ {\em adaptive} corruptions, under a standard intractability assumption for adaptively secure protocols, \vaddon{namely, the existence of enhanced trapdoor permutations and secure erasures.} This is done by using the SKI to derive a sequence of random {\it hidden communication graphs} among players. A central new technique then shows how to use these graphs to emulate a complete network in \polylog[n] rounds while preserving the \polylog[n] locality. Second, we show how we can even remove the SKI setup assumption at the cost, however, of increasing the communication locality (but not the round complexity) by a factor of~$\sqrt{n}$.

### On the Architectural Analysis of Arbiter Delay PUF Variants

Sat, 06/23/2018 - 12:34
The Arbiter Physically Unclonable Function (APUF) is a widely used strong delay PUF design. There are two FPGA variants of this design, namely, Programmable Delay Line APUF (PAPUF) and Double APUF (DAPUF) to mitigate the FPGA platform specific implementation issues. In this paper, we introduce the idea of Architectural Bias to compare the impact of the architecture of these APUF designs on their design bias. The biased challenge-response behavior of a delay PUF implies the non-uniform distributions of 0’s and 1’s in its response, and if this bias is due to the architectural issue of the PUF design, then it is called “Architectural Bias”. Another important source of bias is the implementation issue specific to an implementation platform. According to our study, a good PUF architecture results in PUF instances with a small amount of architectural bias. In this paper, we provide a comparison of APUF, PAPUF, and DAPUF based on their architectural bias values. In addition, we also compare these APUF architectures with respect to fulfilling the Strict Avalanche Criterion (SAC) and robustness against the machine learning (ML) based modeling attack. We validate our theoretical findings with Matlab based simulations, and the results reveal that the classic APUF has the least architectural bias, followed by DAPUF and PAPUF, respectively. We also conclude from the experimental results that the SAC property of DAPUF is better than that of APUF and PAPUF, and PAPUF’s SAC property is significantly poor. However, our analyses indicate that these APUF variants are vulnerable to ML-based modeling attack.

### Indistinguishability Obfuscation Without Multilinear Maps: iO from LWE, Bilinear Maps, and Weak Pseudorandomness

Fri, 06/22/2018 - 23:59
The existence of secure indistinguishability obfuscators (iO) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. All known approaches to constructing iO rely on d-linear maps which allow the encoding of elements from a large domain, evaluating degree d polynomials on them, and testing if the output is zero. While secure bilinear maps are well established in cryptographic literature, the security of candidates for $d>2$ is poorly understood. We propose a new approach to constructing iO for general circuits. Unlike all previously known realizations of iO, we avoid the use of d-linear maps of degree $d\ge 3$. At the heart of our approach is the assumption that a new weak pseudorandom object exists, that we call a perturbation resilient generator ($\Delta\mathsf{RG}$). Informally, a $\Delta\mathsf{RG}$ maps n integers to m integers, and has the property that for any sufficiently short vector $a\in \mathbb{Z}^m$, all efficient adversaries must fail to distinguish the distributions $\Delta\mathsf{RG}(s)$ and $(\Delta\mathsf{RG}(s)+a)$, with at least some probability that is inverse polynomial in the security parameter. We require that the $\Delta\mathsf{RG}$ be computable by degree-2 polynomials over Z. We use techniques building upon the Dense Model Theorem to deal with adversaries that have nontrivial but non-overwhelming distinguishing advantage. As a result, we obtain iO for general circuits assuming: - Subexponentially secure LWE - Bilinear Maps - $(1-1/poly(\lambda))$-secure 3-block-local PRGs - $1/poly(\lambda)$-secure $\Delta\mathsf{RG}$s

### Better Than Advertised: Improved Collision-Resistance Guarantees for MD-Based Hash Functions

Fri, 06/22/2018 - 12:01
The MD transform that underlies the MD and SHA families iterates a compression function $\mathsf{h}$ to get a hash function $\mathsf{H}$. The question we ask is, what property X of $\mathsf{h}$ guarantees collision resistance (CR) of $\mathsf{H}$? The classical answer is that X itself be CR. We show that weaker conditions X, in particular forms of what we call constrained-CR, suffice. This reduces demands on compression functions, to the benefit of security, and also, forensically, explains why collision-finding attacks on compression functions have not, historically, lead to immediate breaks of the corresponding hash functions. We obtain our results via a definitional framework called RS security, and a parameterized treatment of MD, that also serve to unify prior work and variants of the transform.

### Formal Analysis of Vote Privacy using Computationally Complete Symbolic Attacker

Fri, 06/22/2018 - 12:00
We analyze the FOO electronic voting protocol in the provable secu- rity model using the technique of Computationally Complete Symbolic Attacker (CCSA). The protocol uses commitments, blind signatures and anonymous chan- nels to achieve vote privacy. Unlike the Dolev-Yao analyses of the protocol, we assume neither perfect cryptography nor existence of perfectly anonymous chan- nels. Our analysis reveals new attacks on vote privacy, including an attack that arises due to the inadequacy of the blindness property of blind signatures and not due to a specific implementation of anonymous channels. With additional assumptions and modifications, we were able to show that the protocol satisfies vote privacy. Our techniques demonstrate effectiveness of the CCSA technique for both attack detection and verification.

### New techniques for multi-value homomorphic evaluation and applications

Fri, 06/22/2018 - 11:59
In this paper, we propose a new technique to perform several homomorphic operations in one bootstrapping call over a multi-value plaintext space. Our construction relies on the FHEW-based gate bootstrapping: we analyze its structure and propose a strategy we call multi-value bootstrapping which allows to bootstrap an arbitrary function in an efficient way. The security of our scheme relies on the LWE assumption over the torus. We give three applications: the first one is the efficient evaluation of an arbitrary boolean function (LUT), the second one is the optimization of the circuit bootstrapping from (Asiacrypt'2017) which allows to compose circuits in a leveled mode, the third one is the homomorphic evaluation of a neural network where the linear part is evaluated using a generalization of the key-switching procedure and the non-linear part is evaluated with our multi-value bootstrapping. We have implemented the proposed method and were able to evaluate arbitrary 6-to-6 LUTs under 1.2 seconds. Our implementation is based on the TFHE library but can be easily integrated into other homomorphic libraries based on the same structure, such as FHEW (Eurocrypt'2015). The number of LUT outputs does not influence the execution time by a lot, e.g. evaluation of additional 128 outputs on the same 6 input bits takes only 0.05 more seconds.

### Cache-Attacks on the ARM TrustZone implementations of AES-256 and AES-256-GCM via GPU-based analysis

Fri, 06/22/2018 - 11:58
The ARM TrustZone is a security extension which is used in recent Samsung flagship smartphones to create a Trusted Execution Environment (TEE) called a Secure World, which runs secure processes (Trustlets). The Samsung TEE includes cryptographic key storage and functions inside the Keymaster trustlet. The secret key used by the Keymaster trustlet is derived by a hardware device and is inaccessible to the Android OS. However, the ARM32 AES implementation used by the Keymaster is vulnerable to side channel cache-attacks. The Keymaster trustlet uses AES-256 in GCM mode, which makes mounting a cache attack against this target much harder. In this paper we show that it is possible to perform a successful cache attack against this AES implementation, in AES-256/GCM mode, using widely available hardware. Using a laptop's GPU to parallelize the analysis, we are able to extract a raw AES-256 key with 7 minutes of measurements and under a minute of analysis time and an AES-256/GCM key with 40 minutes of measurements and 30 minutes of analysis.

### Ground-up Root-cause Analysis guided Low-Overhead Generic Countermeasure for Electro-Magnetic Side-Channel Attack

Fri, 06/22/2018 - 11:58
The threat of side-channels is becoming increasingly prominent for resource-constrained internet-connected devices. While numerous power side-channel countermeasures have been proposed, a promising approach to protect the non-invasive electromagnetic side-channel attacks has been relatively scarce. Today's availability of high-resolution electromagnetic (EM) probes mandates the need for a low-overhead solution to protect EM side-channel analysis (SCA) attacks. This work, for the first time, performs a white-box analysis to root-cause the origin of the EM leakage from an integrated circuit. System-level EM simulations with Intel 32 nm CMOS technology interconnect stack reveals that the EM leakage from metals above layer 8 can be detected by an external non-invasive attacker with the commercially available EM probes. This work proposes a two-stage solution to eliminate the critical signal radiation from the higher-level metal layers. Firstly, we propose routing the entire cryptographic core using the local lower-level metal layers, whose leakage cannot be picked up by an external attacker. Then, the entire crypto IP is embedded within a signature attenuation hardware (SAH) which in turn suppresses the critical encryption signature and finally connects to the highly radiating top-level metal layers. We utilize the Attenuated Signature Noise Injection (ASNI) circuit, which was recently proposed as a low-overhead generic power SCA countermeasure, in order to encapsulate the cryptographic core with local low-level metal routing, and thereby significantly suppress the critical signatures even before it reaches to the higher metals. System-level implementation of the ASNI circuit with local lower-level metal layers in TSMC 65 nm CMOS technology, with an AES-128 core (as an example cryptographic engine) operating at 40 MHz, shows that the system remains secure against EM SCA attack even after $1 M$ encryptions, with $67\%$ power efficiency compared to the unprotected AES.

### On some methods for constructing almost optimal S-Boxes and their resilience against side-channel attacks

Fri, 06/22/2018 - 11:57
Substitution Boxes (S-Boxes) are crucial components in the design of many symmetric ciphers. The security of these ciphers against linear, differential, algebraic cryptanalyses and side-channel attacks is then strongly dependent on the choice of the S-Boxes. To construct S-Boxes having good resistive properties both towards classical cryptanalysis as well side-channel attacks is not a trivial task. In this article we propose new methods for generating S-Boxes with strong cryptographic properties and therefore study the resilience of such S-Boxes against side-channel attacks in terms of its theoretical metrics and masking possibility.

### Two Notions of Differential Equivalence on Sboxes

Fri, 06/22/2018 - 11:55
In this work, we discuss two notions of differential equivalence on Sboxes. First, we introduce the notion of DDT-equivalence which applies to vectorial Boolean functions that share the same difference distribution table (DDT). Next, we compare this notion to what we call the $\gamma$-equivalence, applying to vectorial Boolean functions whose DDTs have the same support. We discuss the relation between these two equivalence notions, demonstrate that the number of DDT- or $\gamma$-equivalent functions is invariant under EA- and CCZ-equivalence and provide an algorithm for computing the DDT-equivalence and the $\gamma$-equivalence classes of a given function. We study the sizes of these classes for some families of Sboxes. Finally, we prove a result that shows that the rows of the DDT of an APN permutation are pairwise distinct.

### Matrioska: A Compiler for Multi-Key Homomorphic Signatures

Fri, 06/22/2018 - 11:54
Multi-Key Homomorphic Signatures (MKHS) enable clients in a system to sign and upload messages to an untrusted server. At any later point in time, the server can perform a computation $C$ on data provided by $t$ different clients, and return the output $y$ and a short signature $\sigma{C, y}$ vouching for the correctness of $y$ as the output of the function $f$ on the signed data. Interestingly, MKHS enable verifiers to check the validity of the signature using solely the public keys of the signers whose messages were used in the computation. Moreover, the signatures $\sigma{C, y}$ are succinct, namely their size depends at most linearly in the number of clients, and only logarithmically in the total number of inputs of $C$. Existing MKHS are constructed based either on standard assumptions over lattices (Fiore et al., ASIACRYPT'16), or on non-falsifiable assumptions (SNARKs) (Lai et al., ePrint'16). In this paper, we investigate connections between single-key and multi-key homomorphic signatures. We propose a generic compiler, called \matrioska, which turns any (sufficiently expressive) single-key homomorphic signature scheme into a multi-key scheme. Matrioska establishes a formal connection between these two primitives and is the first alternative to the only known construction under standard falsifiable assumptions. Our result relies on a novel technique that exploits the homomorphic property of a single-key HS scheme to compress an arbitrary number of signatures from $t$ different users into only $t$ signatures.

### A Note on Key Rank

Fri, 06/22/2018 - 11:47
In recent years key rank has become an important aspect of side-channel analysis, enabling an evaluation lab to analyse the security of a device after a side-channel attack. In particular, it enables the lab to do so when the enumeration effort would be beyond their computing power. Due to its importance there has been a host of work investigating key rank over the last few years. In this work we build upon the existing literature to make progress on understanding various properties of key rank. We begin by showing when two different "scoring methods" will provide the same rank. This has been implicitly used by various algorithms in the past but here it is shown for a large class of functions. We conclude by giving the computational complexity of key rank. This implies that it is unlikely for, considerably, better algorithms to exist.

### One-Message Zero Knowledge and Non-Malleable Commitments

Fri, 06/22/2018 - 11:46
We introduce a new notion of one-message zero-knowledge (1ZK) arguments that satisfy a weak soundness guarantee — the number of false statements that a polynomial-time non-uniform adversary can convince the verifier to accept is not much larger than the size of its non-uniform advice. The zero-knowledge guarantee is given by a simulator that runs in (mildly) super-polynomial time. We construct such 1ZK arguments based on the notion of multi-collision-resistant keyless hash functions, recently introduced by Bitansky, Kalai, and Paneth (STOC 2018). Relying on the constructed 1ZK arguments, subexponentially-secure time-lock puzzles, and other standard assumptions, we construct one-message fully-concurrent non-malleable commitments. This is the first construction that is based on assumptions that do not already incorporate non-malleability, as well as the first based on (subexponentially) falsifiable assumptions.

### Burning Zerocoins for Fun and for Profit: A Cryptographic Denial-of-Spending Attack on the Zerocoin Protocol

Fri, 06/22/2018 - 11:46
Zerocoin (Miers et. al, IEEE S&P’13), designed as an extension to Bitcoin and similar cryptocurrencies, was the first anonymous cryptocurrency proposal which supports large anonymity sets. We identify a cryptographic denial-of-spending attack on the original Zerocoin protocol and a second Zerocoin protocol (Groth and Kohlweiss, EUROCRYPT’15), which enables a network attacker to destroy money of honest users. The attack leads to real-world vulnerabilities in multiple cryptocurrencies, which rely on implementations of the original Zerocoin protocol. The existence of the attack does not contradict the formal security analyses of the two Zerocoin protocols but exposes the lack of an important missing property in the security model of Zerocoin. While the security definitions model that the attacker should not be able to create money out of thin air or steal money from honest users, it does not model that the attacker cannot destroy money of honest users. Fortunately, there are simple fixes for the security model and for both protocols.

### Is Java Card ready for hash-based signatures?

Fri, 06/22/2018 - 11:45
The current Java Card platform does not seem to allow for fast implementations of hash-based signature schemes. While the underlying implementation of the cryptographic primitives provided by the API can be fast, thanks to implementations in native code or in hardware, the cumulative overhead of the many separate API calls results in prohibitive performance for many common applications. In this work, we present an implementation of XMSS$^{MT}$ on the current Java Card platform, and make suggestions how to improve this platform in future versions.

### Hierarchical Attribute-based Signatures

Fri, 06/22/2018 - 11:44
Attribute-based Signatures (ABS) are a powerful tool allowing users with attributes issued by authorities to sign messages while also proving that their attributes satisfy some policy. ABS schemes provide flexible and privacy-preserving approach to authentication since the signer's identity and attributes remain hidden within the anonymity set of users sharing policy-conform attributes. Current ABS schemes exhibit some limitations when it comes to the management and issue of attributes. In this paper we address the lack of support for hierarchical attribute management, a property that is prevalent in traditional PKIs where certification authorities are organised into hierarchies and signatures are verified along roots of trust. Hierarchical Attribute-based Signatures (HABS) introduced in this work support delegation of attributes along paths from the top-level authority down to the users while also ensuring that signatures produced by these users do not leak their delegation paths, thus extending the original privacy guarantees of ABS schemes. Our generic HABS construction also ensures unforgeability of signatures in the presence of collusion attacks and contains an extended tracebility property allowing a dedicated tracing authority to identify the signer and reveal its attribute delegation paths. We include public verification procedure for the accountability of the tracing authority. We anticipate that HABS will be useful for privacy-preserving authentication in applications requiring hierarchical delegation of attribute-issuing rights and where knowledge of delegation paths might leak information about signers and their attributes, e.g., in intelligent transport systems where vehicles may require certain attributes to authenticate themselves to the infrastructure but remain untrackable by the latter.