International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2015-05-05
21:17 [Pub][ePrint] HETest: A Homomorphic Encryption Testing Framework, by Mayank Varia and Sophia Yakoubov and Yang Yang

  In this work, we present a generic open-source software framework that can evaluate the correctness and performance of homomorphic encryption software. Our framework, called HEtest, auto- mates the entire process of a test: generation of data for testing (such as circuits and inputs), execution of a test, comparison of performance to an insecure baseline, statistical analysis of the test results, and production of a LaTeX report. To illustrate the capability of our framework, we present a case study of our analysis of the open-source HElib homomorphic encryption software. We stress though that HEtest is written in a modular fashion, so it can easily be adapted to test any homomorphic encryption software.



21:17 [Pub][ePrint] Order-Revealing Encryption and the Hardness of Private Learning, by Mark Bun and Mark Zhandry

  An order-revealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying plaintexts. We show how to use order-revealing encryption to separate computationally efficient PAC learning from efficient $(\\epsilon, \\delta)$-differentially private PAC learning. That is, we construct a concept class that is efficiently PAC learnable, but for which every efficient learner fails to be differentially private. This answers a question of Kasiviswanathan et al. (FOCS \'08, SIAM J. Comput. \'11).

To prove our result, we give a generic transformation from an order-revealing encryption scheme into one with strongly correct comparison, which enables the consistent comparison of ciphertexts that are not obtained as the valid encryption of any message. We believe this construction may be of independent interest.



21:17 [Pub][ePrint] Optimized Interpolation Attacks on LowMC, by Itai Dinur and Yunwen Liu and Willi Meier and Qingju Wang

  LowMC is a collection of block cipher families introduced at Eurocrypt 2015 by Albrecht et al. Its design is optimized for instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. A unique feature of LowMC is that its internal affine layers are chosen at random, and thus each block cipher family contains a huge number of instances. The Eurocrypt paper proposed two specific block cipher families of LowMC, having 80-bit and 128-bit keys.

In this paper, we mount interpolation attacks (algebraic attacks introduced by Jakobsen and Knudsen) on LowMC, and show that a practically significant fraction of $2^{-38}$ of its 80-bit key instances could be broken $2^{23}$ times faster than exhaustive search. Moreover, essentially all instances that are claimed to provide 128-bit security could be broken about $1000$ times faster. In order to obtain these results, we had to develop novel techniques and optimize the original interpolation attack in new ways. While some of our new techniques exploit specific internal properties of LowMC, others are more generic and could be applied, in principle, to any block cipher.



21:17 [Pub][ePrint] Non-invasive Spoofing Attacks for Anti-lock Braking Systems, by Yasser Shoukry and Paul Martin and Paulo Tabuada and Mani B. Srivastava

  This work exposes a largely unexplored vector of physical-layer attacks with demonstrated consequences in automobiles. By modifying the physical environment around analog sensors such as Antilock Braking Systems (ABS), we exploit weaknesses in wheel speed sensors so that a malicious attacker can inject arbitrary measurements to the ABS computer which in turn can cause life-threatening situations. In this paper, we describe the development of a prototype ABS spoofer to enable such attacks and the potential consequences of remaining vulnerable to these attacks. The class of sensors sensitive to these attacks depends on the physics of the sensors themselves. ABS relies on magnetic--based wheel speed sensors which are exposed to an external attacker from underneath the body of a vehicle. By placing a thin electromagnetic actuator near the ABS wheel speed sensors, we demonstrate one way in which an attacker can inject magnetic fields to both cancel the true measured signal and inject a malicious signal, thus spoofing the measured wheel speeds. The mounted attack is of a non-invasive nature, requiring no tampering with ABS hardware and making it harder for failure and/or intrusion detection mechanisms to detect the existence of such an attack. This development explores two types of attacks: a disruptive, naive attack aimed to corrupt the measured wheel speed by overwhelming the original signal and a more advanced spoofing attack, designed to inject a counter-signal such that the braking system mistakenly reports a specific velocity. We evaluate the proposed ABS spoofer module using industrial ABS sensors and wheel speed decoders, concluding by outlining the implementation and lifetime considerations of an ABS spoofer with real hardware.



21:17 [Pub][ePrint] What Information is Leaked under Concurrent Composition?, by Vipul Goyal and Divya Gupta and Abhishek Jain

  Achieving security under concurrent composition is notoriously hard. Indeed, in the plain model, far reaching impossibility results for concurrently secure computation are known. On the other hand, some positive results have also been obtained according to various weaker notions of security (such as by using a super-polynomial time simulator). This suggest that somehow, ``not all is lost in the concurrent setting.\"

In this work, we ask what and exactly how much private information can the adversary learn by launching a concurrent attack? ``Can he learn all the private inputs in all the sessions? Or, can we preserve the security of some (or even most) of the sessions fully while compromising (a small fraction of) other sessions? Or is it the case that the security of all (or most) sessions is (at least partially) compromised? If so, can we restrict him to learn an arbitrarily small fraction of input in each session?\" We believe the above questions to be fundamental to the understanding of concurrent composition. Indeed, despite a large body of work on the study of concurrent composition, in our opinion, the understanding of what exactly is it that goes wrong in the concurrent setting and to what extent is currently quite unsatisfactory.

Towards that end, we adopt the knowledge-complexity based approach of Goldreich and Petrank [STOC\'91] to quantify information leakage in concurrently secure computation. We consider a model where the ideal world adversary (a.k.a simulator) is allowed to query the trusted party for some ``leakage\'\' on the honest party inputs. We obtain both positive and negative results, depending upon the nature of the leakage queries available to the simulator. Informally speaking, our results imply the following: in the concurrent setting, ``significant loss\" of security (translating to high leakage in the ideal world) in some of the sessions is unavoidable if one wishes to obtain a general result. However on the brighter side, one can make the fraction of such sessions to be an arbitrarily small polynomial (while fully preserving the security in all other sessions). Our results also have an implication on secure computation in the bounded concurrent setting [Barak-FOCS\'01]: we show there exist protocols which are secure as per the standard ideal/real world notion in the bounded concurrent setting. However if the actual number of sessions happen to exceed the bound, there is a graceful degradation of security as the number of sessions increase. (In contrast, prior results do not provide any security once the bound is exceeded.)

In order to obtain our positive result, we model concurrent extraction as the classical set-covering problem and develop, as our main technical contribution, a new sparse rewinding strategy. Specifically, unlike previous rewinding strategies which are very ``dense\'\', we rewind ``small intervals\'\' of the execution transcript and still guarantee extraction. This yields other applications as well, including improved constructions of precise concurrent zero-knowledge [Pandey et al.-Eurocrypt\'08] and concurrently secure computation in the multiple ideal query model [Goyal et al.-Crypto\'10].

In order to obtain our negative results, interestingly, we employ techniques from the regime of leakage-resilient cryptography [Dziembowski-Pietrzak-FOCS\'08].



21:17 [Pub][ePrint] VLSI Implementation of Double-Base Scalar Multiplication on a Twisted Edwards Curve with an Efficiently Computable Endomorphism, by Zhe Liu and Husen Wang and Johann Gro{\\ss}sch{\\\"a}dl and Zhi Hu a

  The verification of an ECDSA signature requires a double-base scalar multiplication, an operation of the form $k \\cdot G + l \\cdot Q$ where $G$ is a generator of a large elliptic curve group of prime order $n$, $Q$ is an arbitrary element of said group, and $k$, $l$ are two integers in the range of $[1, n-1]$. We introduce in this paper an area-optimized VLSI design of a Prime-Field Arithmetic Unit (PFAU) that can serve as a loosely-coupled or tightly-coupled hardware accelerator in a system-on-chip to speed up the execution of double-base scalar multiplication. Our design is optimized for twisted Edwards curves with an efficiently computable endomorphism that allows one to reduce the number of point doublings by some 50% compared to a conventional implementation. An example for such a special curve is $-x^2 + y^2 = 1 + x^2y^2$ over the 207-bit prime field $F_p$ with $p = 2^{207} - 5131$. The PFAU prototype we describe in this paper features a ($16 \\times 16$)-bit multiplier and has an overall silicon area of 5821 gates when synthesized with a $0.13\\mu$ standard-cell library. It can be clocked with a frequency of up to 50 MHz and is capable to perform a constant-time multiplication in the mentioned 207-bit prime field in only 198 clock cycles. A complete double-base scalar multiplication has an execution time of some 365k cycles and requires the pre-computation of 15 points. Our design supports many trade-offs between performance and RAM requirements, which is a highly desirable property for future Internet-of-Things (IoT) applications.



21:17 [Pub][ePrint] Efficient Server-Aided Secure Two-Party Function Evaluation with Applications to Genomic Computation, by Marina Blanton and Fattaneh Bayatbabolghani

  Computation based on genomic data is becoming increasingly popular today, be

it for medical or other purposes such as ancestry or paternity testing.

Non-medical uses of genomic data in a computation often take place in a

server-mediated setting where the server offers the ability for joint

genomic testing between the users. Undeniably, genomic data is highly

sensitive, which in contrast to other biometry types, discloses a plethora

of information not only about the data owner, but also about his or her

relatives. Thus, there is an urgent need to protect genomic data, especially

when it is used in computation for what we call as recreational

non-health-related purposes. Towards this goal, in this work we put forward

a framework for server-aided secure two-party computation with the security

model motivated by genomic applications. One particular security setting

that we treat in this work provides stronger security guarantees with

respect to malicious users than the traditional malicious model. In

particular, we incorporate certified inputs into secure computation based on

garbled circuit evaluation to guarantee that a malicious user is unable to

modify her inputs in order to learn unauthorized information about the other

user\'s data.

Our solutions are general in the sense that they can be used to securely

evaluate arbitrary functions and offer attractive performance compared to

the state of the art. We apply the general constructions to three specific

types of genomic tests: paternity, genetic compatibility, and ancestry

testing and implement the constructions. The results show that all such

private tests can be executed within a matter of seconds or less despite the

large size of one\'s genomic data.



21:17 [Pub][ePrint] On the Implementation of Unified Arithmetic on Binary Huff Curves, by Santosh Ghosh, Amit Kumar, Amitabh Das and Ingrid Verbauwhede

  Unified formula for computing elliptic curve point addition and doubling are considered to be resistant against simple power-analysis attack. A new elliptic curve formula known as unified binary Huff curve in this regard has appeared into the literature in 2011. This paper is devoted to analyzing the applicability of this elliptic curve in practice. Our paper has two contributions. We provide an efficient implementation of the unified Huff formula in projective coordinates on FPGA. Secondly, we point out its side-channel vulnerability and show the results of an actual attack. It is claimed that the formula is unified and there will

be no power consumption difference when computing point addition and point doubling operations, observable with simple power analysis (SPA). In this paper, we contradict their claim showing actual SPA results on a FPGA platform and propose a modified arithmetic and its suitable implementation technique to overcome the vulnerability.



21:17 [Pub][ePrint] FIDES: Lightweight Authenticated Cipher with Side-Channel Resistance for Constrained Hardware, by Begül Bilgin and Andrey Bogdanov and Miroslav Knezević and Florian Mendel and Qingju Wang

  In this paper, we present a novel lightweight authenticated cipher optimized for hardware implementations called FIDES. It is an online nonce-based authenticated encryption scheme with authenticated data whose area requirements are as low as 793 GE and 1001 GE for 80-bit and 96-bit security, respectively. This is at least two times smaller than its closest competitors Hummingbird-2 and Grain-128a. While being extremely compact, Fides is both throughput and latency efficient, even in its most serial implementations. This is attained by our novel sponge-like design approach. Moreover, cryptographically optimal 5-bit and 6-bit S-boxes are used as basic nonlinear components while paying a special attention on the simplicity of providing first order side-channel resistance with threshold implementation.



21:17 [Pub][ePrint] Smaller Keys for Code-Based Cryptography: QC-MDPC McEliece Implementations on Embedded Devices, by Stefan Heyse and Ingo von Maurich and Tim Güneysu

  In the last years code-based cryptosystems were established as promising alternatives for asymmetric cryptography since they base their security on well-known NP-hard problems and still show decent performance on a wide range of computing platforms. The main drawback of code-based schemes, including the popular proposals by McEliece and Niederreiter, are the large keys whose size is inherently determined by the underlying code. In a very recent approach, Misoczki et al. proposed to use quasi-cyclic MDPC (QC-MDPC) codes that allow for a very compact key representation. In this work, we investigate novel implementations of the McEliece scheme using such QC-MDPC codes tailored for embedded devices, namely a Xilinx Virtex-6 FPGA and an 8-bit AVR microcontroller. In particular, we evaluate and improve different approaches to decode QC-MDPC codes. Besides competitive performance for encryption and decryption on the FPGA, we achieved a very compact implementation on the microcontroller using only 4,800 and 9,600 bits for the public and secret key at 80 bits of equivalent symmetric security.



21:17 [Pub][ePrint] Complementing Feistel Ciphers, by Alex Biryukov and Ivica Nikolic

  In this paper, we propose related-key differential distinguishers based on the complementation property of Feistel ciphers. We show that with relaxed requirements on the complementation, i.e. the property does not have to hold for all keys and the complementation does not have to be on all bits, one can obtain a variety of distinguishers. We formulate criteria sufficient for attacks based on the complementation property. To stress the importance of our findings we provide analysis of the \\textit{full-round} primitives:

* For the hash mode of \\camo without $FL,FL^{-1}$ layers, differential multicollisions with $2^{112}$ time

* For GOST, practical recovery of the full key with 31 related keys and $2^{38}$ time/data