International Association
for Cryptologic Research

Here, we propose new algorithm for solving ECDLP named \"Bit Coincidence Mining Algorithm!\", from which ECDLP is reduced to solving some quadratic equations system.

In this algorithm, ECDLP of an elliptic curve $E$ defined over $\\bF_q$ ($q$ is prime or power of primes) reduces to solving quadratic equations system of $d-1$ variables and $d+C_0-1$ equations where $C_0$ is small natural number and $d \\sim C_0 \\, \\log_2 q$.

This equations system is too large and it can not be solved by computer.

However, we can show theoritically the cost for solving this equations system by xL algorithm is subexponential under the reasonable assumption of xL algorithm.

When outsourcing the storage of sensitive data to an (untrusted) remote server, a data owner may choose to encrypt the data beforehand to preserve confidentiality. However, it is then difficult to efficiently retrieve specific portions of the data as the server is unable to identify the relevant information. Searchable encryption has been well studied as a solution to this problem, allowing data owners and other authorised users to generate search queries which the server may execute over the encrypted data to identify relevant data portions.

However, many current schemes lack two important properties: verifiability of search results, and expressive queries. We introduce Extended Verifiable Searchable Encryption (eVSE) that permits a user to verify that search results are correct and complete. We also permit verifiable computational queries over keywords and specific data values, that go beyond the standard keyword matching queries to allow functions such as averaging or counting operations.

We formally define the notion of eVSE within relevant security models and give a provably secure instantiation.

S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential cryptanalysis is well understood. In this paper, we investigate techniques that can be used to reverse-engineer S-box design and illustrate those by studying the S-Box $F$ of the Skipjack block cipher whose design process so far remained secret. We first show that the linear properties of $F$ are far from random and propose a design criteria, along with an algorithm which generates S-Boxes very similar to that of Skipjack. Then we consider more general S-box decomposition problems and propose new methods for decomposing S-Boxes built from arithmetic operations or as a Feistel Network of up to 5 rounds. Finally, we develop an S-box generating algorithm which can fix a large number of DDT entries to the values chosen by the designer. We demonstrate this algorithm by embedding images into the visual representation of S-box\'s DDT.

In this paper we present a new method for fast scalar multiplication on elliptic curves over GF(p) in FPGA using Edwards and twisted Edwards curves over GF(p³). The presented solution works for curves with prime group order (for example for all NIST curves over GF(p)). It is possible because of using 2-isogenous twisted Edwards curves over GF(p³) instead of using short Weierstrass curves over GF(p) for point scalar multiplication. This problem was considered by Verneuil in [1], but in software solutions it is useless, because multiplication in GF(p³) is much harder than multiplication in GF(p). Fortunately in hardware solutions it is possible to make in FPGA fast multiplication in GF(p³) using parallel computations. Single multiplication in GF(p³) is still a little bit slower than in GF(p) but operations on twisted Edwards curves require less multiplications than operations on short Weierstrass curves. Using these observations results in that scalar multiplication on twisted Edwards curve may be in some situations shorter than scalar multiplication on short Weierstrass curve up to 26%. Moreover, in Edwards and twisted Edwards curves arithmetic it is possible to use unified formula (the same formula for points addition and point doubling) which protects us against some kinds of side channel attacks. We also present full coprocessor for fast scalar multiplication in FPGA using described techniques.

We present the OPTLS key-exchange protocol, its design, rationale and cryptographic analysis. OPTLS design has been motivated by the ongoing work in the TLS working group of the IETF for specifying TLS 1.3, the next-generation TLS protocol. The latter effort is intended to revamp the security of TLS that has been shown inadequate in many instances as well as to add new security and functional features. The main additions that influence the cryptographic design of TLS 1.3 (hence also of OPTLS) are a new \"0-RTT requirement\" (0-RTT stands for \"zero round trip time\") to allow clients that have a previously retrieved or cached public key of the server to send protected data already in the first flow of the protocol; making forward secrecy (PFS) a mandatory requirement; and moving to elliptic curves as the main cryptographic basis for the protocol (for performance and security reasons). Accommodating these requirements calls for moving away from the traditional RSA-centric design of TLS in favor of a protocol based on Diffie-Hellman techniques. OPTLS offers a simple design framework that supports all the above requirements with a uniform and modular logic that helps in the specification, analysis, performance optimization, and future maintenance of the protocol. The current (draft) specification of TLS 1.3 builds upon the OPTLS framework as a basis for the cryptographic core of the handshake protocol, adapting the different modes of OPTLS and its HKDF-based key derivation to the TLS 1.3 context.

This report has two goals. First, we review guidelines for using the CryptDB system [PRZB11, Pop14] securely by the administrators of database applications. These guidelines were already described in [PRZB11] and elaborated on in [Pop14], but in light of some recent work [NKW15] that applied these guidelines incorrectly, a short document devoted to summarizing these guidelines may be useful.

Second, we explain that the recent study of Naveed, Kamara, and Wright [NKW15] represents an unsafe usage of CryptDB, in which the authors violate CryptDB\'s security guidelines. Hence, the conclusions drawn in that paper regarding CryptDB are both unfounded and incorrect: had the guidelines been followed, none of the claimed attacks would have been possible.

In the past few years, the design of RFID authentication protocols in accordance with the EPC Class-1 Generation-2 (EPC C1 G2) standards, has been one of the most important challenges in the information security domain. Although RFID systems provide user-friendly services for end-users, they can make security and privacy concerns for them. In this paper we analyze the security of an RFID mutual authentication protocol which is based on EPC Class-1 Generation-2 standard and proposed in 2013. The designers of protocol claimed that their protocol is secure against different security attacks and provides user privacy. In this paper, we show that unlike their claims, their protocol is not secure against most of the security attacks such as replay attack, the tag\'s ID exposure, and the spoofing attacks. As a result, their protocol cannot provide security of RFID users in different authentication applications. Finally, in order to prevent the aforementioned attacks and overcome all the existing weaknesses, we apply a modification in the updating procedure of the protocol and propose a strengthened version of it.

The challenge of maintaining confidentiality of stored data in cloud is of utmost importance to realize the potential of cloud computing. Storing data in encrypted form may solve the problem, but increases the security issues and diminishes the essence of cloud while performing operations on cloud data by repeated decryption-encryption. Hence, Fully homomorphic encryption (FHE) is an effective scheme to support arbitrary operations directly on encrypted data. Further, cloud mostly acts as storage database, hence secured sorting and searching of FHE cloud data can be an effective field of research. We have investigated the feasibility of performing comparison as well as partition based sort on CPA resistant FHE data and highlight an important observation that time requirement of partition based sort on FHE data is no better than comparison based sort owing to the security of the cryptosystem. We identify the recrypt operation, which is the denoising step of FHE as the main reason of costly timing requirement of such operations. Finally, we propose a two stage sorting technique termed as Lazy sort with reduced recrypt operation, which proves to be better in terms of performance on FHE data in comparison to partition as well as comparison sort.

Over the last twenty years, the research community has devised sophisticated methods for retrieving secret information from sidechannel emanations, and for resisting such attacks. This paper introduces a new CPU architecture called the Conjoined Microprocessor. The Conjoined Microprocessor can randomly interleave the execution of two programs at very low extra hardware cost. We developed for the Conjoined Microprocessor a preprocessor tool that turns a target algorithm into two (or more) separate queues like $Q_0$ and $Q_1$ that can run in alternation. $Q_0$ and $Q_1$ fulfill the same operation as the original target algorithm. Power-analysis resistance is achieved by randomly alternating the execution of $Q_0$ and $Q_1$, with different runs resulting in different interleavings. Experiments reveal that this architecture is indeed effective against CPA.

Recently, Gligoroski et al. proposed code-based encryption and signature schemes using list decoding, blockwise triangular private keys, and a nonuniform error pattern based on

``generalized error sets.\" The general approach was referred to as \\emph{McEliece in the World of Escher.} This paper demonstrates

attacks which are significantly cheaper than the claimed security level of the parameters given by Gligoroski et al. We implemented an attack on the proposed 80-bit parameters which was able

to recover private keys for both encryption and signatures in approximately 2 hours on a single laptop. We further find that increasing the parameters to avoid our attack will require parameters to grow by almost an order of magnitude for signatures, and (at least) two orders of magnitude for encryption.

We present in this article a freestart collision example for SHA-1, i.e., a

collision for its internal compression function. This is the first practical

break of the full SHA-1, reaching all 80 out of 80 steps, while only 10 days

of computation on a 64 GPU cluster were necessary to perform the attack.

This work builds on a continuous series of cryptanalytic advancements on SHA-1

since the theoretical collision attack breakthrough in 2005.

In particular, we extend the recent freestart collision work on reduced-round

SHA-1 from CRYPTO 2015 that leverages the computational power of graphic cards

and adapt it to allow the use of boomerang speed-up techniques.

We also leverage the cryptanalytic techniques by Stevens from EUROCRYPT 2013

to obtain optimal attack conditions,

which required further refinements for this work.

Freestart collisions, like the one presented here, do not directly imply a

collision for SHA-1.

However, this work is an important milestone towards an actual SHA-1 collision

and it further shows how graphics cards can be used very efficiently for these

kind of attacks.

Based on the state-of-the-art collision attack on SHA-1 by Stevens from

EUROCRYPT 2013, we are able to present new projections on the

computational/financial cost required by a SHA-1 collision computation.

These projections are significantly lower than previously anticipated by the

industry, due to the use of the more cost efficient graphics cards compared to

regular CPUs.

We therefore recommend the industry, in particular Internet browser vendors

and Certification Authorities, to retract SHA-1 soon.

We hope the industry has learned from the events surrounding the cryptanalytic

breaks of MD5 and will retract SHA-1 before example signature forgeries appear

in the near future.

With our new cost projections in mind, we strongly and urgently recommend

against a recent proposal to extend the issuance of SHA-1 certificates with a

year in the CAB/forum (vote closes October 9 2015).

In this work, we refine a partitioning technique recently proposed by

Biham and Carmeli to improve the linear cryptanalysis of addition

operations, and we propose an analogue improvement of differential

cryptanalysis of addition operations. These two technique can reduce

the data complexity of linear and differential attacks, at the cost of

more processing time. Our technique can be seen of the analogue for ARX

ciphers of partial key guess and partial decryption for SPN ciphers.

We show a first application of the generalized linear partitioning

technique on FEAL-8X, revisiting the attack of Biham and Carmeli. We

manage to reduce the data complexity from 2^14 to 2^12 known plaintexts,

while the time complexity increases from 2^45 to 2^47.

Then, we use these technique to analyze Chaskey, a recent MAC proposal

by Mouha et al, that is being studied for standardisation by ISO and

ITU-T. Chaskey uses an ARX structure very similar to SipHash. We use a

differential-linear attack with improvements from the partitioning

technique, combined with a convolution-based method to reduce the time

complexity. This leads to an attack on 6 rounds with 2^25 data and

2^28.6 time (verified experimentally), and an attack on 7 rounds with

2^48 data and 2^67 time. These results show that the full version of

Chaskey with 8 rounds has a rather small security margin.

In this work we introduce a new hard problem in lattices called Isometric Lattice Problem (ILP) and reduce Linear Code Equivalence over prime fields and Graph Isomorphism to this prob- lem. We also show that this problem has an (efficient prover) perfect zero-knowledge interactive proof; this is the only hard problem in lattices that is known to have this property (with respect to malicious verifiers). Under the assumption that the polynomial hierarchy does not collapse, we also show that ILP cannot be NP-complete. We finally introduce a variant of ILP over the rationals radicands and provide similar results for this new problem.

After CLT13 of multilinear map over the integers was broken by Cheon, Han, Lee, Ryu and Stehle using zeroizing attack, a new variant CLT15 of CLT13 was proposed by Coron, Lepoint and Tibouchi by constructing new zero-testing parameter. Very recently, CLT15 was broken independently by Cheon, Lee and Ryu, and Minaud and Fouque using an extension of Cheon et al.\'s attack. To immune CLT13 against zeroizing attack, we present a new construction of multilinear map over the integers using switching modulus technique. The security of our construction depends upon new hardness assumption.

We describe a new attack on the Search Ring Learning-With-Errors (RLWE) problem based on the chi-square statistical test, and give examples of RLWE instances in Galois number fields which are vulnerable to our attack. We prove a search-to-decision reduction for Galois fields which applies for any unramified prime modulus $q$, regardless of the residue degree $f$ of $q$, and we use this in our attacks.

The time complexity of our attack is $O(q^{2f})$, where $f$ is the {\\it residue degree} of $q$ in $K$.

We also show an attack on the RLWE problem in general cyclotomic rings (non $2$-power cyclotomic rings) which works when the modulus is a ramified prime.

We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.

Divisible e-cash, proposed in 1991 by Okamoto and Ohta, addresses a practical concern of electronic money, the problem of paying the exact amount. Users of such systems can indeed withdraw coins of a large value $N$ and then divide it into many pieces of any desired values $V\\leq N$. Such a primitive therefore allows to avoid the use of several denominations or change issues. Since its introduction, many constructions have been proposed but all of them make use of the same framework: they associate each coin with a binary tree, which implies, at least, a logarithmic complexity for the spendings.

In this paper, we propose the first divisible e-cash system without such a tree structure, and so without its inherent downsides. Our construction is the first one to achieve constant-time spendings while offering a quite easy management of the coins. It compares favorably with the state-of-the-art, while being provably secure in the standard model.

At SAC 2006, Liskov proposed the zipper hash, a technique for constructing secure (indifferentiable from random oracles) hash functions based on weak (invertible) compression functions. Zipper hash is a two pass scheme, which makes it unfit for practical consideration. But, from the theoretical point of view it seemed to be secure, as it had resisted standard attacks for long. Recently, Andreeva {\\em et al.} gave a forced-suffix herding attack on the zipper hash, and Chen and Jin showed a second preimage attack provided $f_1$ is strong invertible. In this paper, we analyse the construction under the random oracle model as well as when the underlying compression functions have some weakness. We show (second) preimage, and herding attacks on an $n$-bit zipper hash and its relaxed variant with $f_1 = f_2$, all of which require less than $ 2^{n} $ online computations.

Hoch and Shamir have shown that the concatenated hash offers only $\\frac{n}{2}$-bits security when both the underlying compression functions are strong invertible. We show that the bound is tight even when only one of the underlying compression functions is strong invertible.

KATAN is a family of block ciphers published at CHES 2009. Based on the Mixed-integer linear programming (MILP) technique, we propose the first third-party linear cryptanalysis on KATAN. Besides, we evaluate the security of KATAN against the linear attack under the consideration of the dependence of the S-boxes. We present a 131/120-round linear hull attack on KATAN32/48 which are the best known single-key known plaintext attacks. Also, a 94-round linear hull attack on KATAN64 is proposed.

The rapid development of genome sequencing technology allows researchers to access large genome datasets. However, outsourcing the data processing to the cloud poses high risks for personal privacy. The aim of this paper is to give a practical solution for this problem using homomorphic encryption. In our approach, all the computations can be performed in an untrusted cloud without requiring the decryption key or any interaction with the data owner, which preserves the privacy of genome data.

In this paper, we present evaluation algorithms for secure computation of the minor allele frequencies and chi-squared statistic in a genome-wide association studies setting. We also describe how to privately compute the Hamming distance and approximate Edit distance between encrypted DNA sequences. Finally, we compare performance details of using two practical homomorphic encryption schemes - the BGV scheme by Gentry, Halevi and Smart and the YASHE scheme by Bos, Lauter, Loftus and Naehrig. Such an approach with the YASHE scheme analyzes data from 400 people within about 2 seconds and picks a variant associated with disease from 311 spots. For another task, using the BGV scheme, it took about 65 seconds to securely compute the approximate Edit distance for DNA sequences of size 5K and figure out the differences between them.

CryptoExperts is looking for an excellent, motivated, self-driven doctoral student with some background on cryptology and proven research abilities, to work in the area of white-box cryptography. The position is for 3 years at CryptoExperts in Paris (https://www.cryptoexperts.com) with an academic co-direction, starting as soon as possible.

The candidate may be of any nationality but may have resided in France for at most 1 year in the 3 years preceeding the application. They can have at most 2 years of research experience at the doctoral level. The PhD student is expected to have a MSc degree or equivalent.

This PhD position will be fully funded by the ECRYPT-NET project (www.ecrypt.eu.org/net/). ECRYPT-NET is a European research network that intends to develop advanced cryptographic techniques and implementations for the Internet of Things and the Cloud. The network is currently recruiting a group of 15 PhD students who will be trained in an international context, that involves Summer Schools and internships. The project offers opportunities to travel and interact with PhD students and scientists all over Europe.

The PhD thesis will focus on white-box cryptography and may include works ranging from theoretic solutions (e.g. indistinguishability obfuscation) to practical cryptanalytic attacks on software claimed to be white-box secure, as well as designing reliable software solutions of industrial strength in mobile environments.