International Association
for Cryptologic Research

A fast correlation attack (FCA) is a well-known cryptanalysis technique for LFSR-based stream ciphers. The correlation between the initial state of an LFSR and corresponding key stream is exploited, and the goal is to recover the initial state of the LFSR. In this paper, we revisit the FCA from a new point of view based on a finite field, and it brings a new property for the FCA when there are multiple linear approximations. Moreover, we propose a novel algorithm based on the new property, which enables us to reduce both time and data complexities. We finally apply this technique to the Grain family, which is a well-analyzed class of stream ciphers. There are three stream ciphers, Grain-128a, Grain-128, and Grain-v1 in the Grain family, and Grain-v1 is in the eSTREAM portfolio and Grain-128a is standardized by ISO/IEC. As a result, we break them all, and especially for Grain-128a, the cryptanalysis on its full version is reported for the first time.

Order-preserving encryption emerged as a key ingredient underlying the security of practical database management systems. Boldyreva et al. (EUROCRYPT '09) initiated the study of its security by introducing two natural notions of security. They proved that their first notion, a ``best-possible'' relaxation of semantic security allowing ciphertexts to reveal the ordering of their corresponding plaintexts, is not realizable. Later on Boldyreva et al. (CRYPTO '11) proved that any scheme satisfying their second notion, indistinguishability from a random order-preserving function, leaks about half of the bits of a random plaintext.

This unsettling state of affairs was recently changed by Chenette et al. (FSE '16), who rigorously relaxed the above ``best-possible'' notion and constructed a scheme satisfying it based on any pseudorandom function. In addition to revealing the ordering of any two encrypted plaintexts, ciphertexts in their scheme reveal only the position of the most significant bit on which the plaintexts differ. A significant drawback of their scheme, however, is its substantial ciphertext expansion: Encrypting plaintexts of length $m$ bits results in ciphertexts of length $m \cdot \ell$ bits, where $\ell$ determines the level of security (e.g., $\ell = 80$ in practice).

In this work we prove a lower bound on the ciphertext expansion of any order-preserving encryption scheme satisfying the ``limited-leakage'' notion of Chenette et al. with respect to non-uniform polynomial-time adversaries, matching the ciphertext expansion of their scheme up to lower-order terms. This improves a recent result of Cash and Zhang (ePrint '17), who proved such a lower bound for schemes satisfying this notion with respect to computationally-unbounded adversaries (capturing, for example, schemes whose security can be proved in the random-oracle model without relying on cryptographic assumptions). Our lower bound applies, in particular, to schemes whose security is proved in the standard model.

In Eurocrypt 2018, Luykx and Preneel described hash-key-recovery and forgery attacks against polynomial hash based Wegman-Carter-Shoup (WCS) authenticators. Their attacks require $2^{n/2}$ message-tag pairs and recover hash-key with probability about $1.34 \times 2^{-n}$ where $n$ is the bit-size of the hash-key. Bernstein in Eurocrypt 2005 had provided an upper bound (known as Bernstein bound) of the maximum forgery advantages. The bound says that all adversaries making $O(2^{n/2})$ queries of WCS can have maximum forgery advantage $O(2^{-n})$. So, Luykx and Preneel essentially analyze WCS in a range of query complexities where WCS is known to be perfectly secure. Here we revisit the bound and found that WCS remains secure against all adversaries making $q \ll \sqrt{n} \times 2^{n/2}$ queries. So it would be meaningful to analyze adversaries with beyond birthday bound complexities.

In this paper, we show that the Bernstein bound is tight by describing two attacks (one in the ``chosen-plaintext model" and other in the ``known-plaintext model") which recover the hash-key (hence forges) with probability at least $\frac{1}{2}$ based on $\sqrt{n} \times 2^{n/2}$ message-tag pairs. We also extend the forgery adversary to the Galois Counter Mode (or GCM). More precisely, we recover the hash-key of GCM with probability at least $\frac{1}{2}$ based on only $\sqrt{\frac{n}{\ell}} \times 2^{n/2}$ encryption queries, where $\ell$ is the number of blocks present in encryption queries.

Abertay University, in Dundee, Scotland, is a modern university with a global outlook, rooted in its local and national communities. In 2013 we marked the 125th anniversary of our foundation as an institution dedicated to supporting science, industry and the professions with a distinctive interdisciplinary and multi-disciplinary approach to teaching, research and knowledge exchange.

The University now seeks to appoint two Lecturers in Computing and Cybersecurity within the Division of Cybersecurity, part of the School of Design and Informatics.

The School of Design and Informatics is the home of Abertay’s undergraduate and postgraduate degree programmes in games, digital arts, cybersecurity and applied computer science. Abertay was the first university to offer degrees in Computer Games Technology and Ethical Hacking, and the School continues to be recognised as an international leader in its fields. The School has long-established professional links with Dundee’s thriving computer games community and the UK\'s cybersecurity community.

The Division of Cybersecurity is Abertay\'s centre for teaching and research in applied computing and cybersecurity, with particular interests in ethical hacking, digital forensics, IoT and secure software development. Reporting to the Head of Division, you will provide high-quality, research-informed teaching across all of our degree programmes, with a particular focus on specialist content within our Ethical Hacking and Computing degrees, and conduct internationally-recognised research that contributes to Abertay\'s strategic interests within the cybersecurity industries and wider digital sector.

The Lecturer in Computing and Cybersecurity will demonstrate relevant knowledge and practical ability in one or more of the following areas:, IoT, secure software development, Big Data for cybersecurity or AI for cybersecurity, ethical hacking or network security.

If you believe you have the skills and experience for this exciting and challenging role, please submit your application through our online recruitment system.

Closing date for applications: 29 June 2018

More information: https://www.jobs.ac.uk/job/BKB796/lecturer-in-computing-and-cybersecurity/

We are looking for Research Fellow (Post-Doc), to join our group. The applicants should have background and be interested in working on different aspects of lattice-based cryptography, in particular on:

• security proofs for lattice-based schemes,
• building and implementing lattice-based constructions,
• fully homomorphic encryption

The research will take place in the Embedded Security and Cryptography (EMSEC) team, within the IRISA computer science institute located in Rennes, France.

We are looking for candidates with a PhD in cryptography and with publications in cryptographic conferences.

To apply please send your detailed CV (with publication list), a motivation letter, and contact informations of at least two people who can provide reference letters.

The duration of the position is 2 years, it has flexible starting date (ideally between September and December). Review of applications will start immediately until the position is filled.

Closing date for applications: 31 August 2018

Contact: Adeline Roux-Langlois, adeline.roux-langlois (at) irisa.fr and Pierre-Alain Fouque, pierre-alain.fouque (at) irisa.fr

A position is available for a Post-Doctoral Researcher in the Decentralized and Distributed Systems (DEDIS) lab at EPFL led by Prof. Bryan Ford. The DEDIS lab focuses on building secure, scalable, and privacy-preserving decentralized systems, with a strong emphasis on building and deploying fully functional and usable systems. DEDIS is currently developing next-generation blockchain or distributed ledger technology, already available as an open-source prototype and in use by industry partners and within EPFL’s campus-wide infrastructure. DEDIS is the only academic research lab globally to have both built a next-generation blockchain system from the ground up and regularly published its design elements in top-tier peer-reviewed security/privacy conferences such as IEEE S&P ‘16, ‘17, ‘18 and USENIX Security ‘16, ‘17.

The Post-Doctoral Researcher will work closely with Prof. Ford, PhD and undergraduate students, senior researchers, and software engineers within the DEDIS lab, along with multiple external research and development partners from industry and academia. Some participation in teaching activities is also expected. Research activities will include notably the design, implementation, and experimental validation of state-of-the-art decentralized systems, including playing a core role in the ongoing design and development of DEDIS’s next-generation blockchain architecture and software infrastructure.

Closing date for applications: 31 July 2018

Contact: dedis (at) epfl.ch

More information: https://recruiting.epfl.ch/Vacancies/568/Description/2

The Applied Crypto group of the University of Luxembourg is offering multiple Ph.D. student and post-doc positions in cryptography, funded by the H2020 ERC programme. Possible topics of interests are fully homomorphic encryption, multilinear maps, public-key cryptanalysis, and blockchain applications.

The Ph.D. students and post-docs will be members of the Security and Trust (SnT) research center from the university of Luxembourg (>200 researchers in all aspects of IT security). We offer a competitive salary (about 34,000 euro/year gross for Ph.D, and 60,000 euro/year gros for post-doc). The duration of the position is 3 years (+ 1 year extension) for Ph.D., and 2.5 years for post-doc.

Profile:

• For Ph.D. position: MSc degree or equivalent in Computer Science or in Mathematics.

• For post-doc position: a PhD in cryptography, with publications in competitive cryptographic conferences

Candidates should submit the following documents:

• Motivation letter indicating your research interests.
• Curriculum vitae (including your contact address, work experience, publications)
• For Ph.D. position: transcripts of B.Sc. and M.Sc. grades
• For post-doc position: a short description of your PhD work (max 1 page).
• Contact information for 3 referees

Closing date for applications: 15 July 2018

Contact: Jean-Sebastien Coron - jean-sebastien.coron at uni dot lu

More information: http://www.crypto-uni.lu/vacancies.html

We initiate the study of incorporating remotely unhackable hardware modules, such as air-gap switches and data diodes, into the field of multi-party computation. As a result, we are able to construct protocols with very strong composable security guarantees that cannot be achieved with adaptive security.

Our application of hardware modules is motivated by the fact that modules with very limited functionality can be implemented securely as fixed-function circuits and (formally) verified for correctness. They can therefore not be hacked remotely.

In comparison to the hardware tokens proposed by Katz at EUROCRYPT `07, our hardware modules are based on substantially weaker assumptions. Our hardware modules may be physically tampered. Hence, they cannot be passed to another (possibly malicious) party but only used and trusted by their owner. In particular, our remotely unhackable hardware modules do not constitute a setup for Universal Composability (UC).

Based on architectures with very few and very simple hardware modules, we are able to construct protocols that provide security against remote hacking if the hack occurs after a protocol party received its (first) input. More specifically, an adversary can neither learn nor change the inputs and outputs of a remotely hacked party in our constructions unless he has control over that party before it has received its (first) input (or controls all parties). In our constructions we assume erasing parties. However, we also show that this assumption can be substantially weakened.

Since the advantages provided by unhackable hardware modules cannot be adequately captured in existing composable security frameworks, we have conceived a new security framework based on the UC framework. We call our framework Fortified UC.

Different transforms used in binding a secret key to correlated physical-identifier outputs are compared. Decorrelation efficiency is the metric used to determine transforms that give highly-uncorrelated outputs. Scalar quantizers are applied to transform outputs to extract uniformly distributed bit sequences to which secret keys are bound. A set of transforms that perform well in terms of the decorrelation efficiency is applied to ring oscillator (RO) outputs to improve the uniqueness and reliability of extracted bit sequences, to reduce the hardware area and information leakage about the key and RO outputs, and to maximize the secret-key length. Low-complexity error-correction codes are proposed to illustrate two complete key-binding systems with perfect secrecy, and better secret-key and privacy-leakage rates than existing methods. A reference hardware implementation is also provided to demonstrate that the transform-coding approach occupies a small hardware area.

Recently, Faust et al. (TCC'14) introduced the notion of continuous non-malleable codes (CNMC), which provides stronger security guarantees than standard non-malleable codes, by allowing an adversary to tamper with the codeword in continuous way instead of one-time tampering. They also showed that CNMC with information theoretic security cannot be constructed in 2-split-state tampering model, and presented a construction of the same in CRS (common reference string) model using collision-resistant hash functions and non-interactive zero-knowledge proofs.

In this work, we ask if it is possible to construct CNMC from weaker assumptions. We answer this question by presenting lower as well as upper bounds. Specifically, we show that it is impossible to construct 2-split-state CNMC, with no CRS, for one-bit messages from any falsifiable assumption, thus establishing the lower bound. We additionally provide an upper bound by constructing 2-split-state CNMC for one-bit messages, assuming only the existence of a family of injective one way functions.

We also present a construction of 4-split-state CNMC for multi-bit messages in CRS model from the same assumptions. Additionally, we present definitions of the following new primitives: (1) One-to-one commitments, and (2) Continuous Non-Malleable Randomness Encoders, which may be of independent interest.

The Cryptography, Security, and Privacy (CrySP) research group at the University of Waterloo is seeking applications for a postdoctoral research position in the field of data security and applied cryptography, preferably on topics related differential privacy and secure computation. This position will be held in the Cheriton School of Computer Science.

Applicants must hold a PhD in a related field, and should have a proven research record, as demonstrated by publications in top security and privacy or database venues (such as Oakland, CCS, SIGMOD, VLDB) and/or top venues specific to data security (such as DBSEC).

The start date of the position is negotiable. The position may be for one or two years.

Applicants should submit a CV, a research plan, two or three selected papers, and the names and contact information of three references. For further information about the position, or to apply, please send email to Florian Kerschbaum with \"Postdoctoral position\" in the subject line. Applications may be considered as they arrive.

Closing date for applications: 1 September 2018

Contact: Florian Kerschbaum with \"Postdoctoral position\" in the subject line. Applications may be considered as they arrive.

Cryptography, Security, and Privacy Research Group

David R. Cheriton School of Computer Science

University of Waterloo

Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x36163

Fax: 519-885-1208

More information: https://crysp.uwaterloo.ca/prospective/postdoc/

he Cryptography, Security, and Privacy (CrySP) research group at the University of Waterloo is seeking applications for a postdoctoral research position in the field of privacy-enhancing technologies. This position will be held in the Cheriton School of Computer Science.

Applicants must hold a PhD in a related field, and should have a proven research record, as demonstrated by publications in top security and privacy venues (such as Oakland, CCS, USENIX Security, and NDSS) and/or top venues specific to privacy-enhancing technologies (such as PETS/PoPETs).

The start date of the position is negotiable. The position may be for one or two years.

Applicants should submit a CV, a research plan, two or three selected papers, and the names and contact information of three references.

Closing date for applications: 1 September 2018

Contact: Ian Goldberg with \"Postdoctoral position\" in the subject line. Applications may be considered as they arrive.

Cryptography, Security, and Privacy Research Group

David R. Cheriton School of Computer Science

University of Waterloo

Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x36163

Fax: 519-885-1208

More information: https://crysp.uwaterloo.ca/prospective/postdoc/

Thus far, several lattice-based algorithms for partial key exposure attacks on RSA, i.e., given the most/least significant bits (MSBs/LSBs) of a secret exponent $d$ and factoring an RSA modulus $N$, have been proposed such as Bl\"omer and May (Crypto'03), Ernst et al. (Eurocrypt'05), and Aono (PKC'09). Due to Boneh and Durfee's small secret exponent attack, partial key exposure attacks should always work for $d<N^{0.292}$ even without any partial information. However, it was difficult task to make use of the given partial information without losing the quality of Boneh-Durfee's attack. In particular, known partial key exposure attacks fail to work for $d<N^{0.292}$ with only few partial information. Such unnatural situation stems from the fact that the additional information makes underlying modular equations involved. In this paper, we propose improved attacks when a secret exponents $d$ is small. Our attacks are better than all known previous attacks in the sense that our attacks require less partial information. Specifically, our attack is better than all known ones for $d<N^{0.5625}$ and $d<N^{0.368}$ with the MSBs and the LSBs, respectively. Furthermore, our attacks fully cover the Boneh-Durfee bound, i.e., they always work for $d<N^{0.292}$. At a high level, we obtain the improved attacks by fully utilizing unravelled linearization technique proposed by Herrmann and May (Asiacrypt'09). Although Herrmann and May (PKC'10) already applied the technique to Boneh-Durfee's attack, we show elegant and impressive extensions to capture partial key exposure attacks. More concretely, we construct structured triangular matrices that enable us to recover more useful algebraic structures of underlying modular polynomials. We embed the given MSBs/LSBs to the recovered algebraic structures and construct our partial key exposure attacks. In this full version, we provide overviews and explicit proofs of the triangular matrix constructions. We believe that the additional explanations help readers to understand our techniques.

Private function evaluation aims to securely compute a function f (x_1 , . . ., x_n ) without leaking any information other than what is revealed by the output, where f is a private input of one of the parties (say Party_1) and x_i is a private input of the i-th party Party_i. In this work, we propose a novel and secure two-party private function evaluation (2PFE) scheme based on DDH assumption. Our scheme introduces a reusability feature that significantly improves the state-of-the-art. Accordingly, our scheme has two variants, one is utilized in the first evaluation of the function f, and the other is utilized in its subsequent evaluations. To the best of our knowledge, this is the first and most efficient special purpose PFE scheme that enjoys a reusablity feature. Our protocols achieve linear communication and computation complexities and a constant number of rounds which is at most three.

We point out an implicit unproven assumption underlying the security of rational proofs of storage that is related to a concept we call weak randomized compression. This is a class of interactive proofs designed in a security model with a rational prover who is encouraged to store data (possibly in a particular format), as otherwise it either fails verification or does not save any storage costs by deviating (in some cases it may even increase costs by ``wasting" the space). Weak randomized compression is a scheme that takes a random seed $r$ and a compressible string $s$ and outputs a compression of the concatenation $r \circ s$. Strong compression would compress $s$ by itself (and store the random seed separately). In the context of a storage protocol, it is plausible that the adversary knows a weak compression that uses its incompressible storage advice as a seed to help compress other useful data it is storing, and yet it does not know a strong compression that would perform just as well. It therefore may be incentivized to deviate from the protocol in order to save space. This would be particularly problematic for proofs of replication, designed to encourage provers to store data in a redundant format, which weak compression would likely destroy. We thus motivate the question of whether weak compression can always be used to efficiently construct strong compression, and find (negatively) that a black-box reduction would imply a universal compression scheme in the random oracle model for all compressible efficiently sampleable sources. Implausibility of universal compression aside, we conclude that constructing this black-box reduction for a class of sources is at least as hard as directly constructing a universal compression scheme for that class.

Unspent Transaction Outputs (UTXOs) are the internal mechanism used in many cryp- tocurrencies to represent coins. Such representation has some clear benefits, but also entails some complexities that, if not properly handled, may leave the system in an inefficient state. Specifically, inefficiencies arise when wallets (the software responsible for transferring coins between parties) do not manage UTXOs properly when performing payments. In this paper, we study three cryptocurrencies: Bitcoin, Bitcoin Cash and Litecoin, by analyzing the actual state of their UTXO sets, that is, the status of their sets of spendable coins. These three cryptocurrencies are the top-3 UTXO based cryptocurrencies by market capitalization. Our analysis shows that the usage of each cryptocurrency is quite different, and let to different results. Furthermore, it also points out that the management of the transactions has not been always performed efficiently and then the actual state of the UTXO set for each cryptocurrency is far from ideal.

Braid group is a very important non-commutative group. It is also an important tool of quantum field theory, and has good topological properties. This paper focuses on the provable security research of cryptosystem over braid group, which consists of two aspects: One, we proved that the Ko's cryptosystem based on braid group is secure against chosen-plaintext-attack(CPA) which proposed in CRYPTO2000, while it dose not resist active attack. The other is to propose a new public key cryptosystem over braid group which is secure against adaptive chosen-ciphertext-attack(CCA2). Our proofs are based on random oracle models, under the computational conjugacy search assumption(CCS assumption). This kind of results have never been seen before

The GGH15 multilinear maps have served as the foundation for a number of cutting-edge cryptographic proposals. Unfortunately, many schemes built on GGH15 have been explicitly broken by so-called ``zeroizing attacks,'' which exploit leakage from honest zero-test queries. The precise settings in which zeroizing attacks are possible have remained unclear. Most notably, none of the current indistinguishability obfuscation (iO) candidates from GGH15 have any formal security guarantees against zeroizing attacks.

In this work, we demonstrate that all known zeroizing attacks on GGH15 implicitly construct algebraic relations between the results of zero-testing and the encoded plaintext elements. We then propose a ``GGH15 zeroizing model" as a new general framework which greatly generalizes known attacks.

Our second contribution is to describe a new GGH15 variant, which we formally analyze in our GGH15 zeroizing model. We then construct a new iO candidate using our multilinear map, which we prove secure in the GGH15 zeroizing model. This implies resistance to all known zeroizing strategies. The proof relies on the Branching Program Un-Annihilatability (BPUA) Assumption of Garg et al. [TCC 16-B] (which is implied by PRFs in NC^1 secure against P/Poly) and the complexity-theoretic p-Bounded Speedup Hypothesis of Miles et al. [ePrint 14] (a strengthening of the Exponential Time Hypothesis).

The ICAO-standardized Password Authenticated Connection Establishment (PACE) protocol is used all over the world to secure access to electronic passports. Key-secrecy of PACE is proven by first modeling it as an Observational Transition System (OTS) in CafeOBJ, and then proving invariant properties by induction.

In this paper, we propose a new cryptanalysis method to mount collision attack on RIPEMD-160. Firstly, we review two existent cryptanalysis methods to mount (semi-free-start) collision attack on MD-SHA hash family and briefly explain their advantages and disadvantages. To make the best use of the advantages of the two methods, we come up with a new model to mount collision attack. Applying the new technique, we improve the only existent collision attack on the first 30-step RIPEMD-160 presented at Asiacrypt 2017 by a factor of $2^{11}$. Moreover, our new method is much simpler than that presented at Asiacrypt 2017 and there is no need to pre-determine many bit conditions for multi-step modification, thus leaving sufficient freedom degree of the message words. Besides, we further evaluate the pros and cons of the new method and describe how to carefully apply it in future research. We also implement this attack in C++ and can find the message words to ensure the dense right branch with time complexity $2^{30}$.