Updated: 14 hours 30 min ago

### Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs

Sat, 06/24/2017 - 01:56
Two recent works [Lin, EUROCRYPT 2016, Lin and Vaikuntanathan, FOCS 2016] showed how to construct Indistinguishability Obfuscation (IO) from constant degree multilinear maps. However, the concrete degrees of multilinear maps used in their constructions exceed 30. In this work, we reduce the degree of multilinear maps needed to 5, by giving a new construction of IO from asymmetric $L$-linear maps and a pseudo-random generator (PRG) with output locality $L$ and polynomial stretch. When plugging in a candidate PRG with locality-$5$ (\eg, [Goldreich, ECCC 2010, Mossel, Shpilka, and Trevisan, FOCS 2013, O'Donnald and Wither, CCC 2014]), we obtain a construction of IO from 5-linear maps. Our construction improves the state-of-the-art at two other fronts: First, it relies on classical'' multilinear maps, instead of their powerful generalization of graded encodings. Second, it comes with a security reduction to i) the SXDH assumption on algebraic multilinear maps [Boneh and Silverberg, Contemporary Mathematics, Rothblum, TCC 2013], ii) the security of PRG, and iii) sub-exponential LWE, all with sub-exponential hardness. The SXDH assumption is weaker and/or simpler than assumptions on multilinear maps underlying previous IO constructions. When noisy multilinear maps [Garg, Gentry, and Halivi, EUROCRYPT 2013] are used instead, security is based on a family of more complex assumptions that hold in the generic model.

### A Modular Analysis of the Fujisaki-Okamoto Transformation

Fri, 06/23/2017 - 16:55
The Fujisaki-Okamoto (FO) transformation (CRYPTO 1999 and Journal of Cryptology 2013) turns any weakly secure public-key encryption scheme into a strongly (i.e., IND-CCA) secure one in the random oracle model. Unfortunately, the FO analysis suffers from several drawbacks, such as a non-tight security reduction, and the need for a perfectly correct scheme. While several alternatives to the FO transformation have been proposed, they have stronger requirements, or do not obtain all desired properties. In this work, we provide a fine-grained and modular toolkit of transformations for turning weakly secure into strongly secure public-key encryption schemes. All of our transformations are robust against schemes with correctness errors, and their combination leads to several tradeoffs among tightness of the reduction, efficiency, and the required security level of the used encryption scheme. For instance, one variant of the FO transformation constructs an IND-CCA secure scheme from an IND-CPA secure one with a tight reduction and very small efficiency overhead. Another variant assumes only an OW-CPA secure scheme, but leads to an IND-CCA secure scheme with larger ciphertexts. We note that we also analyze our transformations in the quantum random oracle model, which yields security guarantees in a post-quantum setting.

### Implementation and Evaluation of a Lattice-Based Key-Policy ABE Scheme

Fri, 06/23/2017 - 15:10
In this paper, we report on our implementation of a lattice-based Key-Policy Attribute-Based Encryption (KP-ABE) scheme, which uses short secret keys. The particular KP-ABE scheme can be used directly for Attribute-Based Access Control (ABAC) applications, as well as a building block in more involved applications and cryptographic schemes such as audit log encryption, targeted broadcast encryption, functional encryption, and program obfuscation. We adapt a recently proposed KP-ABE scheme based on the Learning With Errors (LWE) problem to a more efficient scheme based on the Ring Learning With Errors (RLWE) problem, and demonstrate an implementation that can be used in practical applications. Our state-of-the-art GPU implementation shows that the homomorphic public key and ciphertext evaluation operations, which dominate the execution time of the KP-ABE scheme, can be performed in a reasonably short amount of time. Our practicality results also hold when scaled to a relatively large number of attributes. To the best of our knowledge, this is the first KP-ABE implementation that supports both ciphertext and public key homomorphism and the only experimental practicality results reported in the literature.

### Verifiable Classroom Voting in Practice

Fri, 06/23/2017 - 13:04
Classroom voting is an important pedagogical technique in which students learn by voting on the answers to questions. The same voting platform is also often used for exercises such as rating lecturer performance and voting for prizes. In this paper, we present VCV, an end-to-end (E2E) verifiable classroom voting system built based on the DRE-i protocol. Our system provides E2E verifiability without tallying authorities; it supports voting through mobile phones with constrained computing resources; it reports the tallying results instantly after voting is finished along with cryptographic proofs that enable the public to verify the tallying integrity. Since 2013, the VCV system has been used regularly in real classroom teaching, as well as academic prize competitions, in Newcastle University with positive user feedback. Our experience suggests that E2E verifiable voting through the internet and using mobile phones is feasible for daily routine activities such as classroom voting.

### The Bitcoin Backbone Protocol: Analysis and Applications

Fri, 06/23/2017 - 11:49
Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two of its fundamental properties which we call common prefix and chain quality in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the “hashing power” of the adversary relative to network synchronicity; we show our results to be tight under high synchronization. Next, we propose and analyze applications that can be built “on top” of the backbone pro- tocol, specifically focusing on Byzantine agreement (BA) and on the notion of a public trans- action ledger. Regarding BA, we observe that Nakamoto’s suggestion falls short of solving it, and present a simple alternative which works assuming that the adversary’s hashing power is bounded by 1/3. The public transaction ledger captures the essence of Bitcoin’s operation as a cryptocurrency, in the sense that it guarantees the liveness and persistence of committed transactions. Based on this notion we describe and analyze the Bitcoin system as well as a more elaborate BA protocol, proving them secure assuming high network synchronicity and that the adversary’s hashing power is strictly less than 1/2, while the adversarial bound needed for security decreases as the network desynchronizes. Finally, we show that our analysis of the Bitcoin backbone protocol for synchronous networks extends with relative ease to the recently considered “partially synchronous” model, where there is an upper bound in the delay of messages that is unknown to the honest parties.

### Cryptanalytic Time-Memory Tradeoff for Password Hashing Schemes

Fri, 06/23/2017 - 11:06
A cryptanalytic technique known as time-memory tradeoff (TMTO) was proposed by Hellman for finding the secret key of a block cipher. This technique allows sharing the effort of key search between the two extremes of exhaustively enumerating all keys versus listing all possible ciphertext mappings produced by a given plaintext (i.e. table lookups). The TMTO technique has also been used as an effective cryptanalytic approach for password hashing schemes (PHS). Increasing threat of password leakage from compromised password hashes demands a resource consuming algorithm to prevent the precomputation of the password hashes. A class of password hashing designs provide such a defense against TMTO attack by ensuring that any reduction in the memory leads to exponential increase in runtime. These are called \textit{Memory hard} designs. However, it is generally difficult to evaluate the memory hardness" of a given PHS design.\\ In this work, we present a simple technique to analyze TMTO for any password hashing schemes which can be represented as a directed acyclic graph (DAG). The nodes of the DAG correspond to the storage required by the algorithm and the edges correspond to the flow of the execution. Our proposed technique provides expected run-times at varied levels of available storage for the DAG. Although our technique is generic, we show its efficacy by applying it on three designs from the Password Hashing Competition" (PHC) - Argon2i (the PHC winner), Catena and Rig. Our analysis shows that Argon2i fails to maintain the claimed memory hardness. In a recent work Corrigan-Gibbs et al. indeed showed an attack highlighting the weak memory hardening of Argon2i. We also analyze these PHS for performance under various settings of time and memory complexities.

### A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK

Fri, 06/23/2017 - 11:02
Recent efficient constructions of zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs), require a setup phase in which a common-reference string (CRS) with a certain structure is generated. This CRS is sometimes referred to as the public parameters of the system, and is used for constructing and verifying proofs. A drawback of these constructions is that whomever runs the setup phase subsequently possesses trapdoor information enabling them to produce fraudulent pseudoproofs. Building on a work of Ben-Sasson, Chiesa, Green, Tromer and Virza [BCGTV15], we construct a multi-party protocol for generating the CRS of the Pinocchio zk-SNARK [PHGR15], such that as long as at least one participating party is not malicious, no party can later construct fraudulent proofs except with negligible probability. The protocol also provides a strong zero-knowledge guarantee even in the case that all participants are malicious. This method has been used in practice to generate the required CRS for the Zcash cryptocurrency blockchain.

### Bit-Sliding: A Generic Technique for Bit-Serial Implementations of SPN-based Primitives -- Applications to AES, PRESENT and SKINNY

Fri, 06/23/2017 - 10:54
Area minimization is one of the main efficiency criterion for lightweight encryption primitives. While reducing the implementation data path is a natural strategy for achieving this goal, Substitution-Permutation Network (SPN) ciphers are usually hard to implement in a bit-serial way (1-bit data path). More generally, this is hard for any data path smaller than its Sbox size, since many scan flip-flops would be required for storage, which are more area-expensive than regular flip-flops.% in addition to extra multiplexers. In this article, we propose the first strategy to obtain extremely small bit-serial ASIC implementations of SPN primitives. Our technique, which we call bit-sliding, is generic and offers many new interesting implementation trade-offs. It manages to minimize the area by reducing the data path to a single bit, while avoiding the use of many scan flip-flops. Following this general architecture, we could obtain the first bit-serial and the smallest implementation of AES-128 to date (1563 GE for encryption only, and 1744 GE for encryption and decryption with IBM 130nm standard-cell library), greatly improving over the smallest known implementations (about 30% decrease), making AES-128 competitive to many ciphers specifically designed for lightweight cryptography. To exhibit the generality of our strategy, we also applied it to the PRESENT and SKINNY block ciphers, again offering the smallest implementations of these ciphers thus far, reaching an area as low as 1054 GE for a 64-bit block 128-bit key cipher. It is also to be noted that our bit-sliding seems to obtain very good power consumption figures, which makes this implementation strategy a good candidate for passive RFID tags.

### Practical Functional Encryption for Quadratic Functions with Applications to Predicate Encryption

Fri, 06/23/2017 - 05:46
We present two practically efficient functional encryption schemes for a large class of quadratic functionalities. Specifically, our constructions enable the computation of so-called bilinear maps on encrypted vectors. This represents a practically relevant class of functions that includes, for instance, multivariate quadratic polynomials (over the integers). Our realizations work over asymmetric bilinear groups and are surprisingly efficient and easy to implement. For instance, in our most efficient scheme the public key and each ciphertext consist of $$2n + 1$$ and $$4n + 2$$ group elements respectively, where n is the dimension of the encrypted vectors, while secret keys are only two group elements. Our two schemes build on similar ideas, but develop them in a different way in order to achieve distinct goals. Our first scheme is proved (selectively) secure under standard assumptions, while our second construction is concretely more efficient and is proved (adaptively) secure in the generic group model. As a byproduct of our functional encryption schemes, we show new predicate encryption schemes for degree-two polynomial evaluation, where ciphertexts consist of only $$O(n)$$ group elements. This significantly improves the $$O(n^2)$$ bound one would get from inner product encryption-based constructions.

### Zero Round-Trip Time for the Extended Access Control Protocol

Thu, 06/22/2017 - 10:21
The Extended Access Control (EAC) protocol allows to create a shared cryptographic key between a client and a server. It is for instance referenced by the International Civil Aviation Organization for securing the communication between machine readable travel documents and terminals, and is also deployed on current German identity cards. Here we discuss how to enhance the EAC protocol by a so-called zero-round trip time (0RTT) mode. Through this mode the client can, without further interaction, immediately derive a new key from cryptographic material exchanged in previous executions. This makes the 0RTT mode attractive from an efficiency viewpoint such that the upcoming TLS 1.3 standard, for instance, will include its own 0RTT mode. Here we show that the EAC protocol can be augmented to support a 0RTT mode, too. Our proposed EAC+0RTT protocol is compliant with the basic EAC protocol and adds the 0RTT mode smoothly on top. We also prove the security of our proposal according to the common security model of Bellare and Rogaway in the multi-stage setting.

### Using State Space Encoding To Counter Biased Fault Attacks on AES Countermeasures

Thu, 06/22/2017 - 01:46
Biased fault attacks such as the Differential Fault Intensity Analysis (DFIA) have been a major threat to cryptosystems in recent times. DFIA combines principles of side channel analysis and fault attacks to try and extract the key using faulty ciphertexts only. Biased fault attacks have also been shown to weaken traditional redundancy based countermeasures, such as Concurrent Error Detection (CED) techniques, that provide security against classical fault attacks such as Differential Fault Analysis (DFA). While these countermeasures are effective under the assumption that the adversary uses a uniform fault model, they are vulnerable to attacks using biased fault models. Till date, no effective countermeasure against such biased fault attacks has been reported in literature. In this work, we propose a countermeasure strategy that combines the principles of redundancy with that of fault space transformation to achieve security against both classical and biased fault attacks. The novelty in the proposed countermeasure lies in the concept of transforming the fault space, that reduces the probability that the adversary can bypass the redundant checks by introducing the same fault in the original and redundant computations. All claims have been validated via practical experiments on a SASEBO GII board.

### A Subversion-Resistant SNARK

Wed, 06/21/2017 - 11:32
While succinct non-interactive zero-knowledge arguments of knowledge (zk-SNARKs) are widely studied, the question of what happens when the CRS has been subverted has received little attention. In ASIACRYPT 2016, Bellare, Fuchsbauer and Scafuro showed the first negative and positive results in this direction, proving also that it is impossible to achieve subversion soundness and (even non-subversion) zero knowledge at the same time. On the positive side, they constructed an involved sound and subversion zero-knowledge argument system for NP. We show that Groth's zk-SNARK for \textsc{Circuit-SAT} from EUROCRYPT 2016 can be made computationally knowledge-sound and perfectly composable Sub-ZK with minimal changes. We just require the CRS trapdoor to be extractable and the CRS to be publicly verifiable. To achieve the latter, we add some new elements to the CRS and construct an efficient CRS verification algorithm. We also provide a definitional framework for sound and Sub-ZK SNARKs and describe implementation results of the new Sub-ZK SNARK.

### Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms

Wed, 06/21/2017 - 11:31
We give precise quantum resource estimates for Shor's algorithm to compute discrete logarithms on elliptic curves over prime fields. The estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, implemented within the framework of the quantum computing software tool suite LIQ$Ui|\rangle$. We determine circuit implementations for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an $n$-bit prime field can be computed on a quantum computer with at most $9n + 2\lceil\log_2(n)\rceil+10$ qubits using a quantum circuit of at most $448 n^3 \log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate the Toffoli networks corresponding to the controlled elliptic curve point addition as the core piece of Shor's algorithm for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons to recent resource estimates for Shor's factoring algorithm. The results also confirm estimates given earlier by Proos and Zalka and indicate that, for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA, suggesting that indeed ECC is an easier target than RSA.

### Round Optimal Concurrent MPC via Strong Simulation

Wed, 06/21/2017 - 11:31
In this paper, we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model. In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model. We obtain the following results: • Three-round concurrent MPC with SPS security against Byzantine adversaries, assuming sub-exponentially secure DDH and LWE. • A barrier to constructing stand-alone two-round MPC for general functionalities, achieving any notion of meaningful security against Byzantine adversaries, from standard falsifiable assumptions. • This barrier breaks down in the setting of input-less functionalities; where we construct two-round concurrent MPC with SPS security against Byzantine adversaries for input- less functionalities, assuming sub-exponentially secure indistinguishability obfuscation and DDH. In particular, this class includes sampling functionalities that allow parties to jointly sample a secure common reference string for cryptographic applications. Prior to our work, to the best of our knowledge, concurrent MPC with SPS security required roughly 20 rounds, although we are not aware of any work that even gave an approximation of the constant round complexity sufficient for the multi-party setting. We also improve over the previous best round complexity for the two-party setting, where 5 rounds were needed (Garg, Kiyoshima, and Pandey, Eurocrypt 2017). To obtain our results, we compile protocols that already achieve security against “semi- malicious” adversaries, to protocols secure against fully malicious adversaries, additionally as- suming sub-exponential DDH. Our protocols develop new techniques to use two-round zero- knowledge with super-polynomial strong simulation, defined by Pass (EUROCRYPT 2003) and very recently realized by Khurana and Sahai (Eprint 2017). These remain zero-knowledge against adversaries running in time larger than the running time of the simulator.

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

Wed, 06/21/2017 - 11:30
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.

### FPGA-based Key Generator for the Niederreiter Cryptosystem using Binary Goppa Codes

Wed, 06/21/2017 - 11:30
This paper presents an post-quantum secure, efficient, and tunable FPGA implementation of the key generation algorithm for the Niederreiter cryptosystem using binary Goppa codes. Our key generator implementation requires as few as 896,052 cycles to produce both public and private portions of a key, and can achieve an estimated frequency Fmax of over 240 MHz when synthesized for Stratix V FPGAs. To the best of our knowledge, this work is the first hardware-based implementation that works with parameters equivalent to, or exceeding, the recommended 128-bit "post-quantum security" level. The key generator can produce a key pair for parameters $n=6960$, $m=13$, $t=119$ in only $3.7$ms when no systemization failure occurs, and in $3.5 \cdot 3.7$ms on average. To achieve such performance, we implement an optimized and parameterized Gaussian systemizer for matrix systemization, which works for any large-sized matrix over any finite field $\text{GF}(2^m)$. Our work also presents an FPGA-based implementation of the Gao-Mateer additive FFT, which only takes about 1000 clock cycles to finish the evaluation of a degree-119 polynomial at $2^{13}$ data points, for example. The key generator Verilog HDL code is partly code-generated using Python and Sage, and can be easily re-generated for different parameters, not just the ones shown in this paper. Design validation was performed using Sage, iVerilog simulation, and data from real FPGA hardware.

### Single-Trace Side-Channel Attacks on Masked Lattice-Based Encryption

Wed, 06/21/2017 - 11:29
Although lattice-based cryptography has proven to be a particularly efficient approach to post-quantum cryptography, its security against side-channel attacks is still a very open topic. There already exist some first works that use masking to achieve DPA security. However, for public-key primitives SPA attacks that use just a single trace are also highly relevant. For lattice-based cryptography this implementation-security aspect is still unexplored. In this work, we present the first single-trace attack on lattice-based encryption. As only a single side-channel observation is needed for full key recovery, it can also be used to attack masked implementations. We use leakage coming from the Number Theoretic Transform, which is at the heart of almost all efficient lattice-based implementations. This means that our attack can be adapted to a large range of other lattice-based constructions and their respective implementations. Our attack consists of 3 main steps. First, we perform a template matching on all modular operations in the decryption process. Second, we efficiently combine all this side-channel information using belief propagation. And third, we perform a lattice-decoding to recover the private key. We show that the attack allows full key recovery not only in a generic noisy Hamming-weight setting, but also based on real traces measured on an ARM Cortex-M4F microcontroller.

### Solving Multivariate Polynomial Systems and an Invariant from Commutative Algebra

Wed, 06/21/2017 - 11:29
The security of several post-quantum cryptosystems is based on the assumption that solving a system of multivariate (quadratic) polynomial equations $p_1=\dots=p_m=0$ over a finite field is hard. Such a system can be solved by computing a lexicographic Groebner basis of the ideal $(p_1,\dots,p_m)$. The most efficient algorithms for computing Groebner bases, such as $F_4$ and $F_5$, transform the problem into several instances of Gaussian elimination. The computational complexity of these algorithms is not completely understood, especially when the polynomials $p_1,\dots,p_m$ are non-homogeneous. In this paper, we prove that this complexity is bounded by a function of the Castelnuovo-Mumford regularity of the ideal $(p_1^h,\dots,p_m^h)$ obtained by homogenizing the input polynomials. This allows us to bound the complexity of solving a system of polynomial equations when the associated ideal is zero-dimensional, a common situation in cryptography. More precisely, we show that the degree of the polynomials involved in the computation a Groebner basis of a zero-dimensional ideal grows at most linearly in the number of variables. In combination with some theorems in commutative algebra, our results also allow us to bound the complexity of some instances of the MinRank Problem.

### Speeding up lattice sieve with Xeon Phi coprocessor

Wed, 06/21/2017 - 11:26
Major substep in a lattice sieve algorithm which solves the Euclidean shortest vector problem (SVP) is the computation of sums and Euclidean norms of many vector pairs. Finding a solution to the SVP is the foundation of an attack against many lattice based crypto systems. We optimize the main subfunction of a sieve for the regular main processor and for the co-processor to speed up the algorithm in total. Furthermore, we show that the co-processor can provide a significant performance improvement for highly parallel tasks in the lattice sieve. Four-fold speed up achieved, compared to the CPU, indicates that co-processors are a viable choice for implementation of lattice sieve algorithms.

### On the Security of Carrier Phase-based Ranging

Wed, 06/21/2017 - 11:26
Multicarrier phase-based ranging is fast emerging as a cost-optimized solution for a wide variety of proximity-based applications due to its low power requirement, low hardware complexity and compatibility with existing standards such as ZigBee and 6LoWPAN. Given potentially critical nature of the applications in which phase-based ranging can be deployed (e.g., access control, asset tracking), it is important to evaluate its security guarantees. Therefore, in this work, we investigate the security of multicarrier phase-based ranging systems and specifically focus on distance decreasing relay attacks that have proven detrimental to the security of proximity-based access control systems (e.g., vehicular passive keyless entry and start systems). We show that phase-based ranging, as well as its implementations, are vulnerable to a variety of distance reduction attacks. We describe different attack realizations and verify their feasibility by simulations and experiments on a commercial ranging system. Specifically, we successfully reduced the estimated range to less than 3 m even though the devices were more than 50 m apart. We discuss possible countermeasures against such attacks and illustrate their limitations, therefore demonstrating that phase-based ranging cannot be fully secured against distance decreasing attacks.