International Association
for Cryptologic Research

Schemes for secure outsourcing of client data with search capability are being increasingly marketed and deployed. In the literature, schemes for accomplishing this efficiently are called Searchable Encryption (SE). They achieve high efficiency with provable security by means of a quantifiable leakage profile. However, the degree to which SE leakage can be exploited by an adversary is not well understood. To address this, we present a characterization of the leakage profiles of in-the-wild searchable encryption products and SE schemes in the literature, and present attack models based on an adversarial server’s prior knowledge. Then we empirically investigate the security of searchable encryption by providing query recovery and plaintext recovery attacks that exploit these leakage profiles. We term these 'leakage-abuse attacks' and demonstrate their effectiveness for varying leakage profiles and levels of server knowledge, for realistic scenarios. Amongst our contributions are realistic active attacks which have not been previously explored.

Recently in two independent papers, Albrecht, Bai and Ducas and Cheon, Jeong and Lee presented two very similar attacks, that allow to break NTRU with larger parameters and GGH Multinear Map without zero encodings. They proposed an algorithm for recovering the NTRU secret key given the public key which apply for large NTRU modulus, in particular to Fully Homomorphic Encryption schemes based on NTRU. Hopefully, these attacks do not endanger the security of the NTRUE NCRYPT scheme, but shed new light on the hardness of this problem. The basic idea of both attacks relies on decreasing the dimension of the NTRU lattice using the multiplication matrix by the norm (resp. trace) of the public key in some subfield instead of the public key itself. Since the dimension of the subfield is smaller, the dimension of the lattice decreases, and lattice reduction algorithm will perform better. Here, we revisit the attacks on NTRU and propose another variant that is simpler and outperforms both of these attacks in practice. It allows to break several concrete instances of YASHE, a NTRU-based FHE scheme, but it is not as efficient as the hybrid method of Howgrave-Graham on concrete parameters of NTRU. Instead of using the norm and trace, we propose to use the multiplication by the public key in some subring and show that this choice leads to better attacks. We √ can then show that for power of two cyclotomic fields, the time complexity is polynomialFinally, we show that, under heuristics, straightforward lattice reduction is even more efficient, allowing to extend this result to fields without non-trivial subfields, such as NTRU Prime. We insist that the improvement on the analysis applies even for relatively small modulus ; though if the secret is sparse, it may not be the fastest attack. We also derive a tight estimation of security for (Ring-)LWE and NTRU assumptions. when $q=2^{\Omega(\sqrt{n \log \log n})}$.

Cryptocurrencies like Bitcoin have proven to be very successful in practice and have gained lots of attention from the industries and the academia. The security of Bitcoin-like systems is based on the assumption that the majority of the computing power is under the control of honest players. However, this assumption has been seriously challenged recently and Bitcoin-like systems will fail when this assumption is broken.

We propose the first Bitcoin-like protocol that is secure in the presence of a malicious majority of computing power. On top of Bitcoin's brilliant ideas of utilizing the power of the honest miners, via their computing power together with blocks, to secure the blockchain, we further leverage the power of the honest users, via their coins together with transactions, to achieve this goal. In particular, we propose a novel strategy for selecting the best blockchain from many competing chains by carefully comparing coins in these blockchains. In addition, we rigorously prove important security properties of our protocol in an extension of the blockchain analysis framework by Garay et al [Eurocrypt 2015].

Most masking schemes used as a countermeasure against side-channel analysis attacks require an extensive amount of fresh random bits on the fly. This is burdensome especially for lightweight cryptosystems. Threshold implementations (TIs) that are secure against firstorder attacks have the advantage that fresh randomness is not required if the sharing of the underlying function is uniform. However, finding uniform realizations of nonlinear functions that also satisfy other TI properties can be a challenging task. In this paper, we discuss several methods that advance the search for uniformly shared functions for TIs. We focus especially on three-share implementations of quadratic functions due to their low area footprint. Our methods have low computational complexity even for 8-bit Boolean functions.

This paper describes highly-optimized AES-{128, 192, 256}-CTR assembly implementations for the popular ARM Cortex-M3 and M4 embedded microprocessors. These implementations are about twice as fast as existing implementations. Additionally, we provide the fastest bitsliced constant-time and masked implementations of AES-128-CTR to protect against timing attacks, power analysis and other (first-order) side-channel attacks. All implementations, including an architecture-specific instruction scheduler and register allocator, which we use to minimize expensive loads, are released into the public domain.

Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving SVP require space which (heuristically) grows as $2^{0.2075 n + o(n)}$, where $n$ is the lattice dimension. In high dimensions, the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity. We generalize sieving algorithms to solve SVP with less memory. We consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as $2^{0.1887 n + o(n)}$. The naive algorithm for this triple sieve runs in time $2^{0.5661 n + o(n)}$. With appropriate filtering of pairs, we reduce the time complexity to $2^{0.4812 n + o(n)}$ while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous tradeoff between the memory-intensive sieving and the asymptotically slower enumeration.

Elliptic Curve Cryptography (ECC) has gained much recognition over the last decades and has established itself among the well known public-key cryptography schemes, not least due its smaller key size and relatively lower computational effort compared to RSA. The wide employment of Elliptic Curve Cryptography in many different application areas has been leading to a variety of implementation types and domains ranging from pure software approaches over hardware implementations to hardware/software co-designs. The following review provides an overview of state of the art hardware implementations of ECC, specifically in regard to their targeted design goals. In this context the suitability of the hardware/software approach in regard to the security challenges opposed by the low-end embedded devices of the Internet of Things is briefly examined. The paper also outlines ECC’s vulnerability against quantum attacks and references one possible solution to that problem.

The chair of mobile business and multilateral security has multiple open positions for research and teaching assistants leading to a PhD degree. The candidates will work with BMBF projects, therefore fluency of German language is mandatory.

Closing date for applications: 27 July 2016

Contact: Prof. Dr. Kai Rannenberg

More information: https://m-chair.de/images/documents/career/Ausschreibung_wiss_Mat_allgemein_20160523_GER_JT.pdf

Research Training Group “UbiCrypt – Cryptography in Ubiquitous Computing”

The Horst Görtz Institute for IT-Security (HGI) at Ruhr-University Bochum is one of Europe’s leading research centers in IT security. The DFG, or German Research Foundation, awarded more than €4 million to the HGI for the establishment of the interdisciplinary research training group “New Challenges for Cryptography in Ubiquitous Computing”. We are looking for a candidate with outstanding Master/Diplom in the fields of computer science, electrical engineering, mathematics or related areas.

The research training group will study problems which are fundamental for securing the Internet of Things. The research is structured in three levels: cryptographic primitives, device and system level. The research topics range from cryptographic foundations such as fully homomorphic encryption for privacy in cloud computing, over security for medical implants to internet security solutions involving new national ID cards. A central goal of the doctoral training is an interdisciplinary and structured education at the highest scientific level. Establishing networks to top internationally research groups is part of the training.

A group of internationally renowned researchers together with excellent funding provides an extremely interesting scientific environment. The HGI is known for its good working atmosphere.

- Start: earliest possible

- Competitive salary (TV-L 13)

- Application: Send your documents by August 7, 2016, to grako (at) hgi.rub.de

- Required Documents: CV, certificates, transcript (Master or Diplom), motivation for applying (1 page), names of at least two people who can provide reference letters (email addresses are sufficient)

Further information: www.ubicrypt.org

Closing date for applications: 7 August 2016

More information: http://www.ubicrypt.hgi.rub.de/index.html.en

We study the question of how to build "compilers" that transform a unilaterally authenticated (UA) key-exchange protocol into a mutually-authenticated (MA) one. We present a simple and efficient compiler and characterize the UA protocols that the compiler upgrades to the MA model, showing this to include a large and important class of UA protocols. The question, while natural, has not been studied widely. Our work is motivated in part by the ongoing work on the design of TLS 1.3, specifically the design of the client authentication mechanisms including the challenging case of post-handshake authentication. Our approach supports the analysis of these mechanisms in a general and modular way, in particular aided by the notion of "functional security" that we introduce as a generalization of key exchange models and which may be of independent interest.

In the crypto community, it is widely acknowledged that any cryptographic scheme that is built with no countermeasure against side-channel analysis (SCA) can be easily broken. In this paper, we challenge this intuition. We investigate a novel approach in the design of cryptographic primitives that promotes inherent security against side-channel analysis without using redundant circuits. We propose Keymill, a new keystream generator that is immune against SCA attacks. Security of the proposed scheme depends on mixing key bits in a special way that expands the size of any useful key hypothesis to the full entropy, which enables SCA-security that is equivalent to the brute force. Doing so, we do not propose a better SCA countermeasure, but rather a new one. The current solution focuses exclusively on side-channel analysis and works on top of any unprotected block cipher for mathematical security. The proposed primitive is generic and can turn any block cipher into a protected mode using only 775 equivalent NAND gates, which is almost half the area of the best countermeasure available in the literature.

The security of SHA-3 against different kinds of attacks are of vital importance for crypto systems with SHA-3 as the security engine. In this paper, we look into the differential fault analysis of SHA-3, and this is the first work to conquer SHA3-224 and SHA3-256 using differential fault analysis. Comparing with one existing related work, we relax the fault models and make them realistic for different implementation architectures. We analyze fault propagation in SHA-3 under such single-byte fault models, and propose to use fault signatures at the observed output for analysis and secret retrieval. Results show that the proposed method can effectively identify the injected single-byte faults, and then recover the whole internal state of the input of last round $\chi$ operation ($\chi^{22}_i$) for both SHA3-224 and SHA3-256.

This paper presents MQDSS, the first signature scheme with a security reduction based on the problem of solving a multivariate system of quadratic equations (MQ problem). In order to construct this scheme we give a new security reduction for the Fiat-Shamir transform from a large class of $5$-pass identification schemes and show that a previous attempt from the literature to obtain such a proof does not achieve the desired goal. We give concrete parameters for MQDSS and provide a detailed security analysis showing that the resulting instantiation MQDSS-31-64 achieves $128$ bits of post-quantum security. Finally, we describe an optimized implementation of MQDSS-31-64 for recent Intel processors with full protection against timing attacks and report benchmarks of this implementation.

We prove the related-key security of the Iterated Even-Mansour cipher under broad classes of related key derivation (RKD) functions. Our result extends the classes of RKD functions considered by Farshim and Procter (FSE, 15). Moreover, we present a far simpler proof which uses techniques similar to those used by Cogliati and Seurin (EUROCRYPT, 15) in their proof that the four-round Even-Mansour cipher is secure against XOR related-key attacks---a special case of our result and the result of Farshim and Proctor. Finally, we give a concrete example of a class of RKD functions covered by our result which does not satisfy the requirements given by Farshim and Procter and prove that the three-round Even-Mansour cipher is secure against this class of RKD functions.

Erasable memory is an important resource for designing practical cryptographic protocols that are secure against adaptive attacks. Many practical memory devices such as solid state drives, hard disks, or file systems are not perfectly erasable because a deletion operation leaves traces of the deleted data in the system. A number of methods for constructing a large erasable memory from a small one, e.g., using encryption, have been proposed. Despite the importance of erasable memory in cryptography, no formal model has been proposed that allows one to formally analyse such memory constructions or cryptographic protocols relying on erasable memory.

The contribution of this paper is three-fold. First, we provide a formal model of erasable memory. A memory device allows a user to store, retrieve, and delete data, and it is characterised by a leakage function defining the extent to which erased data is still accessible to an adversary.

Second, we investigate how the erasability of such memories can be amplified. We provide a number of constructions of memories with strong erasability guarantees from memories with weaker guarantees. One of these constructions of perfectly erasable memories from imperfectly erasable ones can be considered as the prototypical application of Canetti et al.'s All-or-Nothing Transform (AoNT). Motivated by this construction, we propose some new and better AoNTs that are either perfectly or computationally secure. These AoNTs are of possible independent interest.

Third, we show (in the constructive cryptography framework) how the construction of erasable memory and its use in cryptographic protocols (for example to achieve adaptive security) can naturally be composed to obtain provable security of the overall protocol.

The single cycle T-function is a particular permutation function with complex algebraic structures, maximum period and efficient implementation in software and hardware. In this paper, on the basis of existing methods, we present a new construction using a class of single cycle T-functions meeting certain conditions to construct a family of new single cycle T-functions, and we also give the numeration lower bound for the newly constructed single cycle T-functions.

One of the key questions in contemporary applied cryptography is whether there exist an efficient algorithm for solving the discrete logarithm problem in elliptic curves. The primary approach for this problem is to try to solve a certain system of polynomial equations. Current attempts try to solve them directly with existing software tools which does not work well due to their very loosely connected topology and illusory reliance on degree falls. A deeper reflection on what makes systems of algebraic equations efficiently solvable is missing. In this paper we propose a new approach for solving this type of polynomial systems which is radically different than current approaches. We carefully engineer systems of equations with excessively dense topology obtained from a complete clique/biclique graphs and hypergraphs and unique special characteristics. We construct a sequence of systems of equations with a parameter K and argue that asymptotically when K grows the system of equations achieves a high level of saturation with lim_{K\to\infty} F/T = 1 which allows to reduce the "regularity degree" and makes that polynomial equations over finite fields may become efficiently solvable.

Silent Text, the instant messaging application by the company Silent Circle, provides its users with end-to-end encrypted communication on the Blackphone and other smartphones. The underlying protocol, SCimp, has received many extensions during the update to version 2, but has not been subjected to critical review from the cryptographic community. In this paper, we analyze both the design and implementation of SCimp by inspection of the documentation (to the extent it exists) and code. Many of the security properties of SCimp version 1 are found to be secure, however many of the extensions contain vulnerabilities and the implementation contains bugs that affect the overall security. These problems were fed back to the SCimp maintainers and some bugs were fixed in the code base. In September 2015, Silent Circle replaced SCimp with a new protocol based on the Signal Protocol.

The Department of Computer Science of the Technische Universität Darmstadt invites applications for positions of

Research Assistants in Cryptography and Complexity Theory

both on doctoral and postdoctoral level, in the group of Professor Marc Fischlin. The positions are funded through various research projects, all in the area of complexity-based cryptography. These are: SecOBig for secure computation on Big Data, CROSSING about signature schemes supporting special operations, and CRISP about secure channels. More information about the projects and our research is available under www.cryptoplexity.de.

The starting date is immediate. The initial funding for the positions is for approximately two years, but the contract should be renewable, based upon availability of funding. Candidates are expected to perform scientific research in the areas of the projects, and to contribute to the teaching, research, and administrative tasks of the group.

Requirements: Master’s degree (or equivalent) in Computer Science, Mathematics, or a similar discipline; extensive knowledge in the areas of cryptography and IT security, for postdoctoral candidates proven in the form of publications in these areas; fluent English language skills; experience in IT system administration is welcome

Applications should include: a curriculum vitae, including references; copies of relevant diplomas and certificates; copies of 3 selected publications (for postdoctoral candidates) or, alternatively, a research statement.

The application data should be bundled into a single PDF file. Applications and enquires should be sent to: jobs (at) cryptoplexity.de. Applications should be received no later than September 30th, 2016, but review of applications will begin immediately on a rolling basis, and the positions may be filled earlier.

Closing date for applications: 30 September 2016

Contact: jobs (at) cryptoplexity.de

More information: http://www.cryptoplexity.de

We are looking for an experienced researcher with excellent scientific credentials, international visibility through publications and projects and substantial experience in the acquisition of external research funding. In particular, we are looking for a person with a distinguished research profile in cybersecurity, e.g. in one of the following research areas: Cryptography, Formal Foundations of IT-Security, Network Security, Security of Complex Software Systems, Security of Embedded Systems.

Closing date for applications: 31 August 2016

Contact: Informal enquiries by email may be addressed to Professor Johannes Buchmann: buchmann (at) cdc.informatik.tu-darmstadt.de

More information: https://www.tu-darmstadt.de/karriere_planen/allgemeineausschreibung/stellen_details_201153.en.jsp