Here you can see all recent updates to the IACR webpage. These updates are also available:

12
December
2017

ePrint Report
Data Is a Stream: Security of Stream-Based Channels
Marc Fischlin, Felix Günther, Giorgia Azzurra Marson, Kenneth G. Paterson

The common approach to defining secure channels in the literature is to consider transportation of discrete messages provided via atomic encryption and decryption interfaces. This, however, ignores that many practical protocols (including TLS, SSH, and QUIC) offer streaming interfaces instead, moreover with the complexity that the network (possibly under adversarial control) may deliver arbitrary fragments of ciphertexts to the receiver. To address this deficiency, we initiate the study of stream-based channels and their security. We present notions of confidentiality and integrity for such channels, akin to the notions for atomic channels, but taking the peculiarities of streams into account. We provide a composition result for our setting, saying that combining chosen-plaintext confidentiality with integrity of the transmitted ciphertext stream lifts confidentiality of the channel to chosen-ciphertext security. Notably, for our proof of this theorem in the streaming setting we need an additional property, called error predictability. We give an AEAD-based construction that achieves our notion of a secure stream-based channel. The construction matches rather well the one used in TLS, providing validation of that protocol's design. Finally, we study how applications that actually aim at transporting atomic messages can do so safely over a stream-based channel. We provide corresponding security notions and a generic and secure 'encode-then-stream' paradigm.

ePrint Report
PICS: Private Image Classification with SVM
Eleftheria Makri, Dragos Rotaru, Nigel P. Smart, Frederik Vercauteren

The advent of Machine Learning as a Service (MLaaS)
makes it possible to outsource a visual object recognition
task to an external (e.g. cloud) provider. However, out-
sourcing such an image classification task raises privacy
concerns, both from the image provider’s perspective, who
wishes to keep their images confidential, and from the clas-
sification algorithm provider’s perspective, who wishes to
protect the intellectual property of their classifier. We pro-
pose PICS, a private image classification system, based on
polynomial kernel support vector machine (SVM) learn-
ing. We selected SVM because it allows us to apply only
low-degree functions for the classification on private data,
which is the reason why our solution remains computation-
ally efficient. Our solution is based on Secure Multiparty
Computation (MPC), it does not leak any information about
the images to be classified, nor about the classifier param-
eters, and it is provably secure. We demonstrate the practi-
cality of our approach by conducting experiments on realis-
tic datasets. We show that our approach achieves high accu-
racy, comparable to that achieved on non-privacy-protected
data while the input-dependent phase is at least 100 times
faster than the similar approach with Fully Homomorphic
Encryption.

ePrint Report
Return Of Bleichenbacher's Oracle Threat (ROBOT)
Hanno Böck, Juraj Somorovsky, Craig Young

Many web hosts are still vulnerable to one of the oldest attacks against RSA in TLS. We show that Bleichenbacher’s RSA vulnerability from 1998 is still very prevalent in the Internet and affects almost a third of the top 100 domains in the Alexa Top 1 Million list, among them Facebook and Paypal. We identified vulnerable products from at least eight different vendors and open source projects, among them F5, Citrix, Radware, Cisco, Erlang, Bouncy Castle, and WolfSSL. Further we have demonstrated practical exploitation by signing a message with the private key of facebook.com’s HTTPS certificate. Finally, we discuss countermeasures against Bleichenbacher attacks in TLS and recommend to deprecate the RSA encryption key exchange in TLS and the PKCS #1 v1.5 standard.

ePrint Report
Signature Schemes with a Fuzzy Private Key
Kenta Takahashi, Takahiro Matsuda, Takao Murakami, Goichiro Hanaoka, Masakatsu Nishigaki

In this paper, we introduce a new concept of digital signature that we call \emph{fuzzy signature}, which is a signature scheme that uses a noisy string such as biometric data as a private key, but \emph{does not require user-specific auxiliary data} (which is also called a helper string in the context of fuzzy extractors), for generating a signature.
Our technical contributions are three-fold:
(1) We first give the formal definition of fuzzy signature, together with a formal definition of a \lq\lq setting'' that specifies some necessary information for fuzzy data.
(2) We give a generic construction of a fuzzy signature scheme based on a signature scheme that has certain homomorphic properties regarding keys and satisfies a kind of related key attack security with respect to addition, and a new tool that we call \emph{linear sketch}.
(3) We specify two concrete settings for fuzzy data, and for each of the settings give a concrete instantiation of these building blocks for our generic construction, leading to two concrete fuzzy signature schemes.

We also discuss how fuzzy signature schemes can be used to realize a biometric-based PKI that uses biometric data itself as a cryptographic key, which we call the \emph{public biometric infrastructure (PBI)}.

We also discuss how fuzzy signature schemes can be used to realize a biometric-based PKI that uses biometric data itself as a cryptographic key, which we call the \emph{public biometric infrastructure (PBI)}.

ePrint Report
On the Round Complexity of OT Extension
Sanjam Garg, Mohammad Mahmoody, Daniel Masny, Izaak Meckler

We show that any OT extension protocol based on one-way functions (or more generally any symmetric-key primitive) either requires an additional round compared to the base OTs or must make a non-black-box use of one-way functions. This result also holds in the semi-honest setting or in the case of certain setup models such as the common random string model. This implies that OT extension in any secure computation protocol must come at the price of an additional round of communication or the non-black-box use of symmetric key primitives. Moreover, we observe that our result is tight in the sense that positive results can indeed be obtained using non-black-box techniques or at the cost of one additional round of communication.

We initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (ACM CCS 2016) into the multiparty garbling paradigm initially introduced by Beaver, Micali, and Rogaway (STOC '90). This is the first work that studies arithmetic garbled circuits in the multiparty setting. Our garbled circuits are secure in the semi-honest model, under the same hardness assumptions as Ball et al., and can be efficiently and securely computed in constant rounds assuming an honest majority.

We first extend free addition and multiplication by a constant to the multiparty setting. We further extend to the multiparty setting efficient garbled multiplication gates. The garbled multiplication gate construction we show was previously achieved only in the two-party setting and assuming a random oracle.

Our main technical contribution is in garbling selector gates. Selector gates compute a simple ``if statement" in the arithmetic setting: the gate selects the output value from two input values in $\mathbb{F}_p$, according to a Boolean selector bit; if the bit is $0$ the output equals the value on the first wire, and if the bit is $1$ the output equals the value on the second wire. We show a new and designated garbled selector gate that reduces by approximately $33\%$ the evaluation time from the best previously known constructions that use existing techniques.

On the downside, we find that testing equality and computing exponentiation by a constant are significantly more complex to garble in the multiparty setting than in the two-party setting.

We first extend free addition and multiplication by a constant to the multiparty setting. We further extend to the multiparty setting efficient garbled multiplication gates. The garbled multiplication gate construction we show was previously achieved only in the two-party setting and assuming a random oracle.

Our main technical contribution is in garbling selector gates. Selector gates compute a simple ``if statement" in the arithmetic setting: the gate selects the output value from two input values in $\mathbb{F}_p$, according to a Boolean selector bit; if the bit is $0$ the output equals the value on the first wire, and if the bit is $1$ the output equals the value on the second wire. We show a new and designated garbled selector gate that reduces by approximately $33\%$ the evaluation time from the best previously known constructions that use existing techniques.

On the downside, we find that testing equality and computing exponentiation by a constant are significantly more complex to garble in the multiparty setting than in the two-party setting.

ePrint Report
Complete Attack on RLWE Key Exchange with reused keys, without Signal Leakage
Jintai Ding, Scott Fluhrer, Saraswathy RV

Key Exchange (KE) from RLWE (Ring-Learning with Errors) is a potential alternative to Diffie-Hellman (DH) in a post quantum setting. Key leakage with RLWE key exchange protocols in
the context of key reuse has already been pointed out in previous work. The Signal leakage attack relies on changes in the signal sent by the responder reusing his key, in a sequence of key exchange
sessions initiated by an attacker with a malformed key. A possible defense against this attack would be by requiring the initiator of the key exchange to send the signal, which is the one pass case of the KE protocol. The initial attack described bu Fluhrer is designed in such a way that it only works on Peikert’s KE protocol and its variants that derives the shared secret from the most significant bits of the approximately equal keys computed by both parties. It does not work on the Ding’s key exchange that uses the least significant bits to derive a shared key. In this work, we describe a new attack on Ding’s one pass case without relying on the signal function output but using only the information of whether
the final key of both parties agree. We also use LLL reduction to make the adversary’s keys random looking to the party being compromised. This completes the series of attacks on RLWE key exchange with key reuse for all variants in both cases of the initiator and responder sending the signal. This work
shows that when a party fixes their public key for a long term, the protocol can always be broken by a malicious user. Moreover, we show that the previous Signal leakage attack can be made more efficient
with fewer queries and how it can be extended to Peikert’s key exchange, which was used in the BCNS implementation and integrated with TLS and a variant used in the New Hope implementation.

8
December
2017

Multivariate Public Key Cryptography is a leading option for security in a post quantum society. In this paper we propose a new encryption scheme, EFLASH, and analyze its efficiency and security.

ePrint Report
Round2: KEM and PKE based on GLWR
Hayo Baan, Sauvik Bhattacharaya, Oscar Garcia-Morchon, Ronald Rietman, Ludo Tolhuizen, Jose-Luis Torre-Arce, Zhenfei Zhang

Cryptographic primitives that are secure against quantum computing are receiving growing attention with recent, steady advances in quantum computing and standardization initiatives in post-quantum cryptography by NIST and ETSI. Lattice-based cryptography is one of the families in post-quantum cryptography, demonstrating desirable features such as well-understood security, efficient performance, and versatility.

In this work, we present Round2 that consists of a key-encapsulation mechanism and a public-key encryption scheme. Round2 is based on the General Learning with Rounding problem, that unifies the Learning with Rounding and Ring Learning with Rounding problems. Round2's construction using the above problem allows for a unified description and implementation. The key-encapsulation mechanism and public-key encryption scheme furthermore share common building blocks, simplifying (security and operational) analysis and code review. Round2's reliance on prime cyclotomic rings offers a large design space that allows fine-tuning of parameters to required security levels. The use of rounding reduces bandwidth requirements and the use of sparse-trinary secrets improves CPU performance and decryption success rates. Finally, Round2 includes various approaches of refreshing the system public parameter A, allowing efficient ways of preventing precomputation and back-door attacks.

In this work, we present Round2 that consists of a key-encapsulation mechanism and a public-key encryption scheme. Round2 is based on the General Learning with Rounding problem, that unifies the Learning with Rounding and Ring Learning with Rounding problems. Round2's construction using the above problem allows for a unified description and implementation. The key-encapsulation mechanism and public-key encryption scheme furthermore share common building blocks, simplifying (security and operational) analysis and code review. Round2's reliance on prime cyclotomic rings offers a large design space that allows fine-tuning of parameters to required security levels. The use of rounding reduces bandwidth requirements and the use of sparse-trinary secrets improves CPU performance and decryption success rates. Finally, Round2 includes various approaches of refreshing the system public parameter A, allowing efficient ways of preventing precomputation and back-door attacks.

ePrint Report
Distributed Computing Made Secure: A New Cycle Cover Theorem
Merav Parter, Eylon Yogev

In the area of distributed graph algorithms a number of network's entities with
local views solve some computational task by exchanging messages with their
neighbors. Quite unfortunately, an inherent property of most existing
distributed algorithms is that throughout the course of their execution, the
nodes get to learn not only their own output but rather learn quite a lot on
the inputs or outputs of many other entities. This leakage of information might
be a major
obstacle in settings where the output (or input) of network's individual is a
private information (e.g., distributed networks of selfish agents,
decentralized digital currency such as Bitcoin, voting systems).

While being quite an unfamiliar notion in the classical distributed setting, the notion of secure multi-party computation (MPC) is one of the main themes in the Cryptography community. Yet despite all extensive work in the area, no existing algorithm fits the framework of classical distributed models in which there are no assumptions on the graph topologies and only messages of bounded size are sent on the edges in each round.

In this paper, we introduce a new framework for \emph{secure distributed graph algorithms} and provide the first \emph{general compiler} that takes any "natural" non-secure distributed algorithm that runs in $r$ rounds, and turns it into a secure algorithm that runs in $\widetilde{O}(r \cdot D \cdot poly(\Delta))$ rounds where $\Delta$ is the maximum degree in the graph and $D$ is its diameter. We also show that this is nearly (existentially) optimal for any round-by-round compiler for bounded degree graphs.

The main technical part of our compiler is based on a new cycle cover theorem: We show that the edges of every bridgeless graph $G$ of diameter $D$ can be covered by a collection of cycles such that each cycle is of length $\widetilde{O}(D)$ and each edge of the graph $G$ appears in $\widetilde{O}(1)$ many cycles. In fact, our construction can be made instance optimal with respect to each single edge. Letting $C_e$ be the shortest cycle containing $e$ in $G$, our cycle collection contains a cycle of length $\widetilde{O}(|C_e|)$ that covers $e$ for every $e \in G$, and in addition, each edge appears on $\widetilde{O}(1)$ many cycles. As a result, our compiler becomes instance optimal for bounded degree graphs.

While being quite an unfamiliar notion in the classical distributed setting, the notion of secure multi-party computation (MPC) is one of the main themes in the Cryptography community. Yet despite all extensive work in the area, no existing algorithm fits the framework of classical distributed models in which there are no assumptions on the graph topologies and only messages of bounded size are sent on the edges in each round.

In this paper, we introduce a new framework for \emph{secure distributed graph algorithms} and provide the first \emph{general compiler} that takes any "natural" non-secure distributed algorithm that runs in $r$ rounds, and turns it into a secure algorithm that runs in $\widetilde{O}(r \cdot D \cdot poly(\Delta))$ rounds where $\Delta$ is the maximum degree in the graph and $D$ is its diameter. We also show that this is nearly (existentially) optimal for any round-by-round compiler for bounded degree graphs.

The main technical part of our compiler is based on a new cycle cover theorem: We show that the edges of every bridgeless graph $G$ of diameter $D$ can be covered by a collection of cycles such that each cycle is of length $\widetilde{O}(D)$ and each edge of the graph $G$ appears in $\widetilde{O}(1)$ many cycles. In fact, our construction can be made instance optimal with respect to each single edge. Letting $C_e$ be the shortest cycle containing $e$ in $G$, our cycle collection contains a cycle of length $\widetilde{O}(|C_e|)$ that covers $e$ for every $e \in G$, and in addition, each edge appears on $\widetilde{O}(1)$ many cycles. As a result, our compiler becomes instance optimal for bounded degree graphs.

ePrint Report
Implementing Joux-Vitse's Crossbred Algorithm for Solving MQ Systems over GF(2) on GPUs
Ruben Niederhagen, Kai-Chun Ning, Bo-Yin Yang

The hardness of solving multivariate quadratic (MQ) systems is the underlying problem for multivariate-based schemes in the field of post-quantum cryptography. The concrete, practical hardness of this problem needs to be measured by state-of-the-art algorithms and high-performance implementations. We describe, implement, and evaluate an adaption of the Crossbred algorithm by Joux and Vitse for solving MQ systems over GF(2). Our adapted algorithm is highly parallelizable and is suitable for solving MQ systems on GPU architectures. Our implementation is able to solve an MQ system of 134 equations in 67 variables in 98.39 hours using one single commercial Nvidia GTX 980 graphics card, while the original Joux-Vitse algorithm requires 6200 CPU-hours for the same problem size. We used our implementation to solve all the Fukuoka Type-I MQ challenges for n = 55,...,74. Based on our implementation, we estimate that the expected computation time for solving an MQ system of 80 equations in 84 variables is about one year using a cluster of 3647 GTX 980 graphics cards. These parameters have been proposed for 80-bit security by, e.g., Sakumoto, Shirai, and Hiwatari in 2011.

ePrint Report
FPGA-based Niederreiter Cryptosystem using Binary Goppa Codes
Wen Wang, Jakub Szefer, Ruben Niederhagen

This paper presents an FPGA implementation
of the Niederreiter cryptosystem
using binary Goppa codes,
including modules for encryption, decryption,
and key generation.
We improve over previous implementations in terms of
efficiency (time-area product and raw performance)
and security level.
Our implementation is constant time
in order to protect against timing side-channel analysis.
The design is fully parameterized,
using code-generation scripts,
in order to support a wide range of parameter choices
for security, including binary field size,
the degree of the Goppa polynomial,
and the code length.
The parameterized design allows us to choose
design parameters for time-area trade-offs
in order to support a wide variety of applications
ranging from smart cards
to server accelerators.
For parameters that are considered to provide
128-bit ‘’post-quantum security'',
our time-optimized implementation
requires 966,400 cycles
for the generation of both
public and private portions of a key
and 14,291 cycles to decrypt a ciphertext.
The time-optimized design uses
only 121,806 ALMs (52% of the available logic)
and 961 RAM blocks (38% of the available memory),
and results in a design that runs at about 250 MHz
on a medium-size Stratix V FPGA.

ePrint Report
On the exponents of APN power functions and Sidon sets, sum-free sets, and Dickson polynomials
Claude Carlet, Stjepan Picek

We derive necessary conditions related to the notions, in additive combinatorics, of Sidon sets and sum-free sets, on those exponents $d\in {\mathbb Z}/(2^n-1){\mathbb Z}$ which are such that $F(x)=x^d$ is an APN function over ${\mathbb F}_{2^n}$ (which is an important cryptographic property). We study to which extent these new conditions may speed up the search for new APN exponents $d$.
We also show a new connection between APN exponents and Dickson polynomials: $F(x)=x^d$ is APN if and only if the reciprocal polynomial of the Dickson polynomial of index $d$ is an injective function from $\{y\in {\Bbb F}_{2^n}^*; tr_n(y)=0\}$ to ${\Bbb F}_{2^n}\setminus \{1\}$. This also leads to a new and simple connection between Reversed Dickson polynomials and reciprocals of Dickson polynomials in characteristic 2 (which generalizes to every characteristic thanks to a small modification): the squared Reversed Dickson polynomial of some index and the reciprocal of the Dickson polynomial of the same index are equal.

ePrint Report
Comparison analysis and efficient implementation of reconciliation-based RLWE key exchange protocol
Xinwei Gao, Jintai Ding, Saraswathy RV, Lin Li, Jiqiang Liu

Error reconciliation is an important technique for Learning With Error (LWE) and Ring-LWE (RLWE)-based constructions. In this paper, we present a comparison analysis on two error reconciliation-based RLWE key exchange protocols: Ding et al. in 2012 (DING12) and Bos et al. in 2015 (BCNS15). We take them as examples to explain core idea of error reconciliation, building key exchange over RLWE problem, implementation, real-world performance and compare them comprehensively. We also analyse a LWE key exchange “Frodo” that uses an improved error reconciliation mechanism in BCNS15. To the best of our knowledge, our work is the first to present at least 128-bit classic (80-bit quantum) and 256-bit classic (>200-bit quantum) secure parameter choices for DING12 with efficient portable C/C++ implementations. Benchmark shows that our efficient implementation is 11x faster than BCNS15 and one key exchange execution only costs 0.07ms on a 4-year-old middle range CPU. Error reconciliation is 1.57x faster than BCNS15.

Mobile platforms use biometrics for authentication. Unfortunately, biometrics exhibit noise between repeated readings. Due to the noise, biometrics are stored in plaintext, so device compromise completely reveals the user's biometric value.

To limit privacy violations, one can use fuzzy extractors to derive a stable cryptographic key from biometrics (Dodis et al., Eurocrypt 2004). Unfortunately, fuzzy extractors have not seen wide deployment due to insufficient security guarantees. Current fuzzy extractors provide no security for real biometric sources and no security if a user enrolls the same biometric with multiple devices or providers.

Previous work claims key derivation systems from the iris but only under weak adversary models. In particular, no known construction securely handles the case of multiple enrollments. Canetti et al. (Eurocrypt 2016) proposed a new fuzzy extractor called sample-then-lock.

We construct biometric key derivation for the iris starting from sample-then-lock. Achieving satisfactory parameters requires modifying and coupling of the image processing and the cryptography. Our construction is implemented in Python and being open-sourced. Our system has the following novel features:

-- 45 bits of security. This bound is pessimistic, assuming the adversary can sample strings distributed according to the iris in constant time. Such an algorithm is not known.

-- Secure enrollment with multiple services.

-- Natural incorporation of a password, enabling multifactor authentication. The structure of the construction allows the overall security to be sum of the security of each factor (increasing security to 79 bits).

To limit privacy violations, one can use fuzzy extractors to derive a stable cryptographic key from biometrics (Dodis et al., Eurocrypt 2004). Unfortunately, fuzzy extractors have not seen wide deployment due to insufficient security guarantees. Current fuzzy extractors provide no security for real biometric sources and no security if a user enrolls the same biometric with multiple devices or providers.

Previous work claims key derivation systems from the iris but only under weak adversary models. In particular, no known construction securely handles the case of multiple enrollments. Canetti et al. (Eurocrypt 2016) proposed a new fuzzy extractor called sample-then-lock.

We construct biometric key derivation for the iris starting from sample-then-lock. Achieving satisfactory parameters requires modifying and coupling of the image processing and the cryptography. Our construction is implemented in Python and being open-sourced. Our system has the following novel features:

-- 45 bits of security. This bound is pessimistic, assuming the adversary can sample strings distributed according to the iris in constant time. Such an algorithm is not known.

-- Secure enrollment with multiple services.

-- Natural incorporation of a password, enabling multifactor authentication. The structure of the construction allows the overall security to be sum of the security of each factor (increasing security to 79 bits).

ePrint Report
Cyclic Locking and Memristor-based Obfuscation Against CycSAT and Inside Foundry Attacks
Amin Rezaei, Yuanqi Shen, Shuyu Kong, Jie Gu, Hai Zhou

The high cost of IC design has made chip protection one of the first priorities of the semiconductor industry. Although there is a common impression that combinational circuits must be designed without any cycles, circuits with cycles can be combinational as well. Such cyclic circuits can be used to reliably lock ICs. Moreover, since memristor is compatible with CMOS structure, it is possible to efficiently obfuscate cyclic circuits using polymorphic memristor-CMOS gates. In this case, the layouts of the circuits with different functionalities look exactly identical, making it impossible even for an inside foundry attacker to distinguish the defined functionality of an IC by looking at its layout. In this paper, we propose a comprehensive chip protection method based on cyclic locking and polymorphic memristor-CMOS obfuscation. The robustness against state-of-the-art key-pruning attacks is demonstrated and the overhead of the polymorphic gates is investigated.

ePrint Report
Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima
Vladimir Kolesnikov, Ahmad-Reza Sadeghi, Thomas Schneider

We consider generic Garbled Circuit (GC)-based techniques for Secure Function Evaluation (SFE) in the semi-honest model.

We describe efficient GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits for subtraction and comparison are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using our efficient building blocks. The techniques rely on recently proposed ``free XOR'' GC technique.

Further, we present concrete and detailed improved GC protocols for the problem of secure integer comparison, and related problems of auctions, minimum selection, and minimal distance. Performance improvement comes both from building on our efficient basic blocks and several problem-specific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.

We describe efficient GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits for subtraction and comparison are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using our efficient building blocks. The techniques rely on recently proposed ``free XOR'' GC technique.

Further, we present concrete and detailed improved GC protocols for the problem of secure integer comparison, and related problems of auctions, minimum selection, and minimal distance. Performance improvement comes both from building on our efficient basic blocks and several problem-specific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.

5
December
2017

This paper presents a new hard problem for use in cryptography, called Short Solutions to Nonlinear Equations (SSNE). This problem generalizes the Multivariate Quadratic (MQ) problem by requiring the solution be short; as well as the Short Integer Solutions (SIS) problem by requiring the underlying system of equations be nonlinear. The joint requirement causes common solving strategies such as lattice reduction or GrÃ¶bner basis algorithms to fail, and as a result SSNE admits shorter representations of equally hard problems. We show that SSNE can be used as the basis for a provably secure hash function. Despite failing to find public key cryptosystems relying on SSNE, we remain hopeful about that possibility.

ePrint Report
Efficient Optimal Ate Pairing at 128-bit Security Level
Md. Al-Amin Khandaker, Yuki Nanjo, Loubna Ghammam, Sylvain Duquesne, Yasuyuki Nogami, Yuta Kodera

Following the emergence of Kim and Barbulescu's new number field sieve (exTNFS) algorithm at CRYPTO'16 [21] for solving discrete logarithm problem (DLP) over the finite field; pairing-based cryptography researchers are intrigued to find new parameters that confirm standard security levels against exTNFS. Recently, Barbulescu and Duquesne have suggested new parameters [3] for well-studied pairing-friendly curves i.e., Barreto-Naehrig (BN) [5], Barreto-Lynn-Scott (BLS-12) [4] and Kachisa-Schaefer-Scott (KSS-16) [19] curves at 128-bit security level (twist and sub-group attack secure). They have also concluded that in the context of Optimal-Ate pairing with their suggested parameters, BLS-12 and KSS-16 curves are more efficient choices than BN curves.
Therefore, this paper selects the atypical and less studied pairing-friendly curve in literature, i.e., KSS-16 which offers quartic twist, while BN and BLS-12 curves have sextic twist. In this paper, the authors optimize Miller's algorithm of Optimal-Ate pairing for the KSS-16 curve by deriving efficient sparse multiplication and implement them. Furthermore, this paper concentrates on the Miller's algorithm to experimentally verify Barbulescu et al.'s estimation. The result shows that Miller's algorithm time with the derived pseudo 8-sparse multiplication is most efficient for KSS-16 than other two curves. Therefore, this paper defends Barbulescu and Duquesne's conclusion for 128-bit security.

ePrint Report
Fully Verifiable Secure Delegation of Pairing Computation: Cryptanalysis and An Efficient Construction
Osmanbey Uzunkol, Öznur Kalkar, İsa Sertkaya

We address the problem of secure and verifiable delegation of general pairing computation. We first analyze some recently proposed pairing delegation schemes and present several attacks on their security and/or verifiability properties. In particular, we show that none of these achieve the claimed security and verifiability properties simultaneously. We then provide a fully verifiable secure delegation scheme ${\sf VerPair}$ under one-malicious version of a two-untrusted-program model (OMTUP). ${\sf VerPair}$ not only significantly improves the efficiency of all the previous schemes, such as fully verifiable schemes of Chevallier-Mames et al. and Canard {\em et al.} by eliminating the impractical exponentiation- and scalar-multiplication-consuming steps, but also offers for the first time the desired full verifiability property unlike other practical schemes. Furthermore, we give a more efficient and less memory consuming invocation of the subroutine ${\sf Rand}$ for ${\sf VerPair}$ by eliminating the requirement of offline computations of modular exponentiations and scalar-multiplications. In particular, ${\sf Rand}$ includes a fully verifiable partial delegation under the OMTUP assumption. The partial delegation of ${\sf Rand}$ distinguishes ${\sf VerPair}$ as a useful lightweight delegation scheme when the delegator is resource-constrained (e.g. RFID tags, smart cards or sensor nodes).

ePrint Report
A Note on Stream Ciphers that Continuously Use the IV
Matthias Hamann, Matthias Krause, Willi Meier

Time-memory-data tradeoff (TMD-TO) attacks limit the security level of many classical stream ciphers (like $E_0$, A5/1, Trivium, Grain) to $n/2$, where $n$ denotes the inner state length of the underlying keystream generator. This implies that to withstand TMD tradeoff attacks, the state size should be at least double the key size. In 2015, Armknecht and Mikhalev introduced a new line of research, which pursues the goal of reducing the inner state size of lightweight stream ciphers below this boundary by deploying a key-dependent state update function in a Grain-like stream cipher. Although their design Sprout was broken soon after publication, it has raised interest in the design principle, and a number of related ciphers have been suggested since, including Plantlet, a follow-up of Sprout, and the cipher Fruit.

In 2017, Hamann et al. showed that the initial hope of achieving full security against TMD-TO attacks by continuously using the secret key has failed. In particular, they demonstrated that there are generic distinguishing attacks against such ciphers with a complexity significantly smaller than that of exhaustive key search. However, by studying the assumptions underlying the applicability of these attacks, they came up with a new design idea for small-state stream ciphers, which is based on also continuously using the public IV as part of the state update. The authors conjectured that this design principle might allow to finally achieve full security against TMD-TO attacks.

In this note, we take their idea one step further. While Hamann et al. aimed for improving the security of small-state stream ciphers that continuously use the secret key against distinguishing, we explain here that also other stream cipher constructions can benefit from continuously using the IV. In particular, our approach allows for thwarting the well-known TMD-TO inner state recovery attacks of Babbage and Biryukov and Shamir without using the secret key more than once.

In 2017, Hamann et al. showed that the initial hope of achieving full security against TMD-TO attacks by continuously using the secret key has failed. In particular, they demonstrated that there are generic distinguishing attacks against such ciphers with a complexity significantly smaller than that of exhaustive key search. However, by studying the assumptions underlying the applicability of these attacks, they came up with a new design idea for small-state stream ciphers, which is based on also continuously using the public IV as part of the state update. The authors conjectured that this design principle might allow to finally achieve full security against TMD-TO attacks.

In this note, we take their idea one step further. While Hamann et al. aimed for improving the security of small-state stream ciphers that continuously use the secret key against distinguishing, we explain here that also other stream cipher constructions can benefit from continuously using the IV. In particular, our approach allows for thwarting the well-known TMD-TO inner state recovery attacks of Babbage and Biryukov and Shamir without using the secret key more than once.

ePrint Report
Attacks on the AJPS Mersenne-based cryptosystem
Koen de Boer, Léo Ducas, Stacey Jeffery, Ronald de Wolf

Aggarwal, Joux, Prakash and Santha recently introduced a new potentially quantum-safe public-key cryptosystem, and suggested that a brute-force attack is essentially optimal against it. They consider but then dismiss both Meet-in-the-Middle attacks and LLL-based attacks. Very soon after their paper appeared, Beunardeau et al.\ proposed a practical LLL-based technique that seemed to significantly reduce the security of the AJPS system.
In this paper we do two things. First, we show that a Meet-in-the-Middle attack can also be made to work against the AJPS system, using locality-sensitive hashing to overcome the difficulty that Aggarwal et al.\ saw for such attacks. We also present a quantum version of this attack. Second, we give a more precise analysis of the attack of Beunardeau et al., confirming and refining their results.

Logic encryption is a hardware security technique that uses extra key inputs to prevent unauthorized use of a circuit. With the discovery of the SAT-based attack, new encryption techniques such as SARLock and Anti-SAT are proposed, and further combined with traditional logic encryption techniques, to guarantee both high error rates and resilience to the SAT-based attack. In this paper, the SAT-based bit-flipping attack is presented. It first separates the two groups of keys via SAT-based bit-flippings, and then attacks the traditional encryption and the SAT-resilient encryption, by conventional SAT-based attack and by-passing attack, respectively. The experimental results show that the bit-flipping attack successfully returns a circuit with the correct functionality and significantly reduces the executing time compared with other advanced attacks.

ePrint Report
here Goes Your PIN: Exploiting Smartphone Sensor Fusion Under Single and Cross User Setting
David Berend, Bernhard Jungk, Shivam Bhasin

A range of zero-permission sensors are found in modern smartphones to enhance user experience. These sensors can lead to unintentional leakage of user private data. In this paper, we combine leakage from a pool of zero-permission sensors, to reconstruct user's secret PIN. By harvesting the power of machine learning algorithms, we show a practical attack on the full four-digit PIN space. Able to classify all 10,000 PIN combinations, results show up to 83.7\% success within 20 tries in a single user setting. Latest previous work demonstrated 74\% success on a reduced space of 50 chosen PINs, where we report 99.5\% success with a single try in a similar setting. Moreover, we extend the PIN recovery attack from a single user to a cross-user scenario. Firstly, we show that by training on several users, the PIN recovery success can be boosted, when a target user is part of the training pool. On the other hand, PIN recovery is still possible when training pool is mutually exclusive to the target user, albeit with low success rate.

1
December
2017

ePrint Report
Itsuku: a Memory-Hardened Proof-of-Work Scheme
Fabien Coelho, Arnaud Larroche, Baptiste Colin

Proof-of-Work (PoW) schemes allow to limit access to resources or to share rewards for crypto-currency mining. The MTP-Argon2 PoW by Biryukov and Khovratovich is loosely based on the Argon2 memory-hard password hashing function. Several attacks have been published. We introduce a new transposed parallel implementation attack which achieves higher performance by circumventing apparent bandwidth requirements. We then present Itsuku, a new scheme that fixes known issues by changing MTP-Argon2 parameters and adds new operations to improve memory hardness. Our scheme is built on a simple security criterion: any implementation which requires half the memory or less should induce at least a times-64 computation cost for difficulty d <= 100. The Itsuku proof size is typically 1/16 th of the initial scheme, while providing better memory hardness. We also describe high-end hardware designs for MTP-Argon2 and Itsuku.

30
November
2017

This work shows that weighted majority voting games occur in cryptocurrencies. In particular, two such games are highlighted. The first game, which we call the Rule Game, pertains to the scenario where the entities in the system engage in a voting procedure to accept or reject a change of rules. The second game, which we call the Attack Game, refers to the scenario where a group of entities in a cryptocurrency system can form a coalition to engage in double spending. For the Rule Game we provide analysis to argue that the Coleman’s preventive power measure is the appropriate tool for measuring a player’s influence in the game while for the Attack Game, we define a notion of stability based on the notion of minimal winning coalitions. For both the Rule Game and the Attack Game, we show how to analyse the games based on a snapshot of real world data for Bitcoin which is presently the most popular of all the cryptocurrencies.

ePrint Report
SCADPA: Side-Channel Assisted Differential-Plaintext Attack on Bit Permutation Based Ciphers
Jakub Breier, Dirmanto Jap, Shivam Bhasin

Bit permutations are a common choice for diffusion function in lightweight block ciphers, owing to their low implementation footprint. In this paper, we present a novel Side-Channel Assisted Differential-Plaintext Attack (SCADPA), exploiting specific vulnerabilities of bit permutations. SCADPA is a chosen-plaintext attack, knowledge of the ciphertext is not required. Unlike statistical methods, commonly used for distinguisher in standard power analysis, the proposed method is more differential in nature. The attack shows that diffusion layer can play a significant role in distinguishing the internal cipher state. We demonstrate how to practically exploit such vulnerability to extract the secret key. Results on microcontroller-based PRESENT-80 cipher lead to full key retrieval using as low as 17 encryptions.
It is possible to automate the attack by using a thresholding method detailed in the paper. Several case studies are presented, using various attacker models and targeting different encryption modes (such as CTR and CBC). We provide a discussion on how to avoid such attack from the design point of view.

ePrint Report
Efficient, Round-optimal, Universally-Composable Oblivious Transfer and Commitment Scheme with Adaptive Security
Megha Byali, Arpita Patra, Divya Ravi, Pratik Sarkar

Adaptive security embodies one of the strongest notions of security that allows an adversary to corrupt parties at any point during protocol execution and gain access to its internal state. Since it models real-life situations such as "hacking", adaptively-secure multiparty computation (MPC) protocols are desirable. Such protocols demand primitives such as oblivious transfer (OT) and commitment schemes that are adaptively-secure as building blocks. Efficient realisations of these primitives have been found to be challenging when no erasures is assumed. In this paper, we provide efficient constructions for these primitives that are Universally-Composable.

$Adaptively-Secure$ $Oblivious$ $Transfer.$ We present the first $round$ $optimal$ adaptively-secure OT based on the 2-round static OT protocol of $Peikert$ et al. (Crypto 2008). Our protocol is in the programmable random oracle (PRO) model. It incurs a minimal communication overhead of one $\kappa$ bit string and computational overhead of 5 random oracle queries over its static counterpart, where $\kappa$ is the security parameter. Additionally, we present a construction of adaptively-secure 1-out-of-$N$ OT by extending the result of $Naor$ et al. (Journal of Cryptology 2005) that transforms $\log N$ copies of 1-out-of-2 OTs to one 1-out-of-$N$ OT. Based on PRO assumption, we prove that the transformation is adaptively-secure at the expense of $\mathcal{O}(\log N)$ exponentiations whereas, the existing state-of-the-art protocols for adaptively-secure 1-out-of-$N$ OT incur at least $\mathcal{O}(N)$ exponentiations. Interestingly, it can be established that our transformation continues to be adaptively-secure, despite replacing the adaptively-secure 1-out-of-2 OTs in the above result with statically-secure OTs, that support equivocation of receiver's view irrespective of equivocation of sender's view.

$Adaptively-Secure$ $Commitment$ $Scheme.$ We provide a $round$ $optimal$ non-interactive commitment scheme (NICOM) based on the observable random oracle (ORO) assumption in the CRS model. Our construction incurs communication of 4$\kappa$ bit strings and computation of 4 exponentiations and 2 random oracle queries for committing to an arbitrary length message. Additionally, we present a statically-secure scheme for one-time generation of CRS that can be reused for multiple commitments. This eliminates the need of a trusted CRS setup for the commitment scheme, thereby reducing the assumptions solely to ORO. The static version of our NICOM finds applications in secure two-party computation (2PC) protocols that adopt offline-online paradigm, where the CRS can be generated in the offline phase.

$Adaptively-Secure$ $Oblivious$ $Transfer.$ We present the first $round$ $optimal$ adaptively-secure OT based on the 2-round static OT protocol of $Peikert$ et al. (Crypto 2008). Our protocol is in the programmable random oracle (PRO) model. It incurs a minimal communication overhead of one $\kappa$ bit string and computational overhead of 5 random oracle queries over its static counterpart, where $\kappa$ is the security parameter. Additionally, we present a construction of adaptively-secure 1-out-of-$N$ OT by extending the result of $Naor$ et al. (Journal of Cryptology 2005) that transforms $\log N$ copies of 1-out-of-2 OTs to one 1-out-of-$N$ OT. Based on PRO assumption, we prove that the transformation is adaptively-secure at the expense of $\mathcal{O}(\log N)$ exponentiations whereas, the existing state-of-the-art protocols for adaptively-secure 1-out-of-$N$ OT incur at least $\mathcal{O}(N)$ exponentiations. Interestingly, it can be established that our transformation continues to be adaptively-secure, despite replacing the adaptively-secure 1-out-of-2 OTs in the above result with statically-secure OTs, that support equivocation of receiver's view irrespective of equivocation of sender's view.

$Adaptively-Secure$ $Commitment$ $Scheme.$ We provide a $round$ $optimal$ non-interactive commitment scheme (NICOM) based on the observable random oracle (ORO) assumption in the CRS model. Our construction incurs communication of 4$\kappa$ bit strings and computation of 4 exponentiations and 2 random oracle queries for committing to an arbitrary length message. Additionally, we present a statically-secure scheme for one-time generation of CRS that can be reused for multiple commitments. This eliminates the need of a trusted CRS setup for the commitment scheme, thereby reducing the assumptions solely to ORO. The static version of our NICOM finds applications in secure two-party computation (2PC) protocols that adopt offline-online paradigm, where the CRS can be generated in the offline phase.

ePrint Report
Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications
M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori, Thomas Schneider, Farinaz Koushanfar

We present Chameleon, a novel hybrid (mixed-protocol) framework for secure function evaluation (SFE) which enables two parties to jointly compute a function without disclosing their private inputs. Chameleon combines the best aspects of generic SFE protocols with the ones that are based upon additive secret sharing. In particular, the framework performs linear operations in the ring $\mathbb{Z}_{2^l}$ using additively secret shared values and nonlinear operations using Yao's Garbled Circuits or the Goldreich-Micali-Wigderson protocol. Chameleon departs from the common assumption of additive or linear secret sharing models where three or more parties need to communicate in the online phase: the framework allows two parties with private inputs to communicate in the online phase under the assumption of a third node generating correlated randomness in an offline phase. Almost all of the heavy cryptographic operations are precomputed in an offline phase which substantially reduces the communication overhead.
Chameleon is both scalable and significantly more efficient than the ABY framework (NDSS'15) it is based on. Our framework supports signed fixed-point numbers. In particular, Chameleon's vector dot product of signed fixed-point numbers improves the efficiency of mining and classification of encrypted data for algorithms based upon heavy matrix multiplications. Our evaluation of Chameleon on a 5 layer convolutional deep neural network shows 110x and 3.5x faster executions than Microsoft CryptoNets (ICML'16) and MiniONN (CCS'17), respectively.

ePrint Report
MILP-aided Cryptanalysis of Round Reduced ChaCha
Najwa Aaraj, Florian Caullery, Marc Manzano

The inclusion of ChaCha20 and Poly1305 into the list of supported ciphers in TLS 1.3 necessitates a security evaluation of those ciphers with all the state-of-the-art tools and innovative cryptanalysis methodologies. Mixed Integer Linear Programming (MILP) has been successfully applied to find more accurate characteristics of several ciphers such as SIMON and SPECK. In our research, we use MILP-aided cryptanalysis to search for differential characteristics, linear approximations and integral properties of ChaCha. We are able to find differential trails up to 2 rounds and linear trails up to 1 round. However, no integral distinguisher has been found, even for 1 round.