International Association
for Cryptologic Research

A chosen-prefix collision attack is a stronger variant of a collision attack, where an arbitrary pair of challenge prefixes are turned into a collision. Chosen-prefix collisions are usually significantly harder to produce than (identical-prefix) collisions, but the practical impact of such an attack is much larger. While many cryptographic constructions rely on collision-resistance for their security proofs, collision attacks are hard to turn into a break of concrete protocols, because the adversary has limited control over the colliding messages. On the other hand, chosen-prefix collisions have been shown to break certificates (by creating a rogue CA) and many internet protocols (TLS, SSH, IPsec).

In this article, we propose new techniques to turn collision attacks into chosen-prefix collision attacks. Our strategy is composed of two phases: first, a birthday search that aims at taking the random chaining variable difference (due to the chosen-prefix model) to a set of pre-defined target differences. Then, using a multi-block approach, carefully analysing the clustering effect, we map this new chaining variable difference to a colliding pair of states using techniques developed for collision attacks.

We apply those techniques to MD5 and SHA1, and obtain improved attacks. In particular, we have a chosen-prefix collision attack against SHA1 with complexity between $2^{66.9}$ and $2^{69.4}$ (depending on assumptions about the cost of finding near-collision blocks), while the best-known attack has complexity $2^{77.1}$. This is within a small factor of the complexity of the classical collision attack on SHA1 (estimated as $2^{64.7}$). This represents yet another warning that industries and users have to move away from using SHA1 as soon as possible.

The area of practical proof systems, like SNARKs, STARKs, or Bulletproofs, is seeing a very dynamic development. Many use-cases of such systems involve, often as their most expensive apart, proving the knowledge of a preimage under a certain cryptographic hash function.

In this paper we present a modular framework and concrete instances of cryptographic hash functions which either work natively with GF(p) objects or on binary strings. Compared to competitors, our hash function Poseidon uses up to 8x fewer constraints per message bit compared to Pedersen Hash, whereas our STARK-friendly hash Starkad takes wins the factor of 4 over the hash function Friday by using a much smaller field.

mixFeed [CN19] is a round 1 candidate for the NIST Lightweight Cryptography Standardization Project. It is a single-pass, nonce-based, AES-based authenticated encryption algorithms. The authors claim that while there are no guarantees for security in terms of confidentiality in case of nonce-misuse (repetition), the integrity security still holds up to 2^32 data complexity. In this report, this claim is not true in case the plaintext length is non-zero (≥ 16 bytes to be exact). We show a forgery attack that requires only two encryption queries with the same nonce and 34 bytes of data.

We present "UniqueChain", a proof-of-stake based blockchain protocol that achieves secure initialization of newly joining parties without any additional trusted assumptions and fast messages (transactions) confirmation. Specifically, the adversary can send corrupt instructions to any parties at any time mildly and have messages delivery delay with an upper bound. Security of our protocol holds if majority of overall stakes are controlled by honest parties.

In "UniqueChain", we propose a new form of two-chain structure that consists of two tightly linked chains named leader chain and transaction chain with two types of corresponding blocks named leader block and transaction block. To achieve the above guarantees, we formalize a secure bootstrapping mechanism for new parties in open setting and realize uniqueness of transaction chains held by honest parties. We prove that "UniqueChain" satisfies security properties as chain growth, chain quality, common prefix and soundness, and two additional properties as uniqueness and high efficiency.

Monero is one of the first and most popular cryptocurrencies to address privacy issues of other crypto coins such as Bitcoin. Monero has a market capitalization of over one billion US dollars, and is ranked the 12th most valuable cryptocurrency on CoinMarketCap (17 April 2019). This digital coin provides different mechanisms to protect its users, such as decoy keys or mixins to obfuscate transaction inputs. However, in spite of the efforts to protect Monero’s users privacy, transaction tracing attacks are still feasible. Our contribution is twofold. First, we propose and evaluate a new traceability attack, called transaction flooding attack (FloodXMR). Second, we present an analysis of thecosts required for an attacker to conduct FloodXMR. We show how an attacker can take advantage of Monero’s Bulletproof protocol, which reduces transaction fees, to flood the network with his own transactions and, consequently, remove mixins from transaction inputs. Assuming an attack timeframe of 12 months, our findings show that an attacker can trace up to 47.63% of the transaction inputs at a cost of just 1,746.53 USD. Moreover, we show also that more than 90% of the inputs are affected by our tracing algorithm.

Secure multiparty computation (MPC) has been repeatedly optimized, and protocols with two communication rounds and strong security guarantees have been achieved. While progress has been made constructing non-interactive protocols with just one-round of online communication (i.e., non-interactive MPC or NI-MPC), since correct evaluation must be guaranteed with only one round, these protocols are by their nature vulnerable to the residual function attack in the standard model. This is because a party that receives a garbled circuit may repeatedly evaluate the circuit locally, while varying their own inputs and fixing the input of others to learn the values entered by other participants. We present the first MPC protocol with a one-round online phase that is secure against the residual function attack. We also present rigorous proofs of correctness and security in the covert adversary model, a reduction of the malicious model that is stronger than the semi-honest model and better suited for modeling the behaviour of parties in the real world, for our protocol. Furthermore, we rigorously analyze the communication and computational complexity of current state of the art protocols which require two rounds of communication or one-round during the online-phase with a reduced security requirement, and demonstrate that our protocol is comparable to or outperforms their complexity.

A reputation system assigns a user or item a reputation value which can be used to evaluate trustworthiness. Bl{\"o}mer, Juhnke and Kolb in 2015, and Kaafarani, Katsumata and Solomon in 2018, gave formal models for \mathit{centralised} reputation systems, which rely on a central server and are widely used by service providers such as AirBnB, Uber and Amazon. In these models, reputation values are given to items, instead of users. We advocate a need for shift in how reputation systems are modelled, whereby reputation values are given to users, instead of items, and each user has unlinkable items that other users can give feedback on, contributing to their reputation value. This setting is not captured by the previous models, and we argue it captures more realistically the functionality and security requirements of a reputation system. We provide definitions for this new model, and give a construction from standard primitives, proving it satisfies these security requirements. We show that there is a low efficiency cost for this new functionality.

The purpose of this paper is to use a Central Limit approach to develop a statistical framework for analysing ciphertexts in Ring-LWE homomorphic encryption schemes. This statistical framework gives rise to Normal approximations for ciphertext random variables, and we show that this allows probabilities to be determined more accurately and hence enables better bounds for decryption failure probabilities than the widely used existing approach based on $\delta$-subgaussian random variables. To demonstrate the benefit of the Central Limit approach, we apply our framework and results to a homomorphic Ring-LWE cryptosystem of Lyubashevsky, Peikert and Regev (Eurocrypt 2013, full version).

This paper presents CONCRETE (Commit-Encrypt-Send-the-Key) a new Authenticated Encryption mode that offers CIML2 security, that is, ciphertext integrity in the presence of nonce misuse and side-channel leakages in both encryption and decryption.

CONCRETE improves on a recent line of works aiming at leveled implementations, which mix a strongly protected and energy demanding implementation of a single component, and other weakly protected and much cheaper components. Here, these components all implement a tweakable block cipher TBC.

CONCRETE requires the use of the strongly protected TBC only once while supporting the leakage of the full state of the weakly protected components -- it achieves CIML2 security in the so-called unbounded leakage model.

All previous works need to use the strongly protected implementation at least twice. As a result, for short messages whose encryption and decryption energy costs are dominated by the strongly protected component, we halve the cost of a leakage-resilient implementation. CONCRETE additionally provides security when unverified plaintexts are released, and confidentiality in the presence of simulatable leakages in encryption and decryption.

In this paper, we introduce two lightweight historical data based multi-factor authenticated key exchange (HMAKE) protocols in the random oracle model. Our HMAKE protocols use a symmetric secret key, as their first authentication factor, together with their second authentication factor, historical data exchanged between the two parties in the past, and the third authentication factor, a set of secret tags associated with the historical data, to establish a secure communication channel between the client and the server.

A remarkable security feature of HMAKE is bounded historical tag leakage resilience, which means that (informally speaking) if a small portion of the secret tags is leaked to an adversary, it will not affect the security of one HMAKE protocol with an overwhelming probability. Our first HMAKE protocol can provide static bounded leakage resilience, meaning that the secret tags are leaked at the beginning of the security game. To enhance its security, our second HMAKE protocol makes use of our first protocol as a compiler to transform any passively secure two-message key exchange protocol to an actively secure HMAKE protocol with perfect forward secrecy, and therefore it can be secure even if the historical tags are compromised adaptively by an attacker.

In addition to the strong security properties we achieved, our protocols can potentially have great impacts in practice: they are efficient in computation, and they are compatible with legacy devices in cyber-physical systems.

There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question: "When can we rule out the existence of a non-malleable code for a tampering class $\mathcal{F}$?"

We show that non-malleable codes are impossible to construct for three different tampering classes: 1. Functions that change $d/2$ symbols, where $d$ is the distance of the code; 2. Functions where each input symbol affects only a single output symbol; 3. Functions where each of the $n$ output symbols is a function of $n-\log n$ input symbols.

We additionally rule out constructions of non-malleable codes for certain classes $\mathcal{F}$ via reductions to the assumption that a distributional problem is hard for $\mathcal{F}$, that make black-box use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for $\mathsf{NC}$, even assuming average-case variants of $P\not\subseteq\mathsf{NC}$.

Secure multiparty computation (MPC) often relies on sources of correlated randomness for better efficiency and simplicity. This is particularly useful for MPC with no honest majority, where input-independent correlated randomness enables a lightweight “non-cryptographic” online phase once the inputs are known. However, since the amount of correlated randomness typically scales with the circuit size of the function being computed, securely generating correlated randomness forms an efficiency bottleneck, involving a large amount of communication and storage. A natural tool for addressing the above limitations is a pseudorandom correlation generator (PCG). A PCG allows two or more parties to securely generate long sources of useful correlated randomness via a local expansion of correlated short seeds and no interaction. PCGs enable MPC with silent preprocessing, where a small amount of interaction used for securely sampling the seeds is followed by silent local generation of correlated pseudorandomness. A concretely efficient PCG for Vector-OLE correlations was recently obtained by Boyle et al. (CCS 2018) based on variants of the learning parity with noise (LPN) assumption over large fields. In this work, we initiate a systematic study of PCGs and present concretely efficient constructions for several types of useful MPC correlations. We obtain the following main contributions: – PCG foundations. We give a general security definition for PCGs. Our definition suffices for any MPC protocol satisfying a stronger security requirement that is met by existing protocols. We prove that a stronger security requirement is indeed necessary, and justify our PCG definition by ruling out a stronger and more natural definition. – Silent OT extension. We present the first concretely efficient PCG for oblivious transfer correlations. Its security is based on a variant of the binary LPN assumption and any correlation-robust hash function. We expect it to provide a faster alternative to the IKNP OT extension protocol (Crypto ’03) when communication is the bottleneck. We present several applications, including protocols for non-interactive zero-knowledge with bounded-reusable preprocessing from binary LPN, and concretely efficient related-key oblivious pseudorandom functions. – PCGs for simple 2-party correlations. We obtain PCGs for several other types of useful 2-party correlations, including (authenticated) one-time truth-tables and Beaver triples. While the latter PCGs are slower than our PCG for OT, they are still practically feasible. These PCGs are based on a host of assumptions and techniques, including specialized homomorphic secret sharing schemes and pseudorandom generators tailored to their structure. – Multiparty correlations. We obtain PCGs for multiparty correlations that can be used to make the circuit-dependent communication of MPC protocols scale linearly (instead of quadratically) with the number of parties.

Conditional cube attack was proposed by Huang et al. at EUROCRYPT 2017 to attack Keccak keyed mode. Inspired by dynamic cube attack, they reduce the degree by appending key bit conditions on the initial value (IV). Recently, Li et al. proposed new conditional cube attacks on Keccak keyed mode with extremely small degrees of freedom. In this paper, we find a new property on Li et al.'s method, and modify the new conditional cube attack for lightweight encryption algorithms using a 8-2-2 pattern, and apply it on 5-round Ketje Jr, 6-round Xoodoo-AE and Xoodyak, where Ketje Jr is among the 3rd round CAESAR competition candidates and Xoodyak is a Round 1 submission of the ongoing NIST lightweight cryptography project. Then we give the updated conditional cube attack analysis. All our results are of practical time complexity with negligible memory cost and our test codes are given in this paper. Notably, it is the first third-party cryptanalysis result for Xoodyak.

Dynamic Searchable Symmetric Encryption ($\mathsf{DSSE}$), apart from providing support for search operation, allows a client to perform update operations on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are desirable from a $\mathsf{DSSE}$ scheme. The former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that search queries should not leak matching entries after they have been deleted. These security properties are formalized in terms of the information leakage that can be incurred by the respective constructions. Existing backward private constructions either have a non-optimal communication overhead or they make use of heavy cryptographic primitives. Our main contribution consists of three efficient backward private schemes that aim to achieve practical efficiency by using light weight symmetric cryptographic components only. In the process, we also revisit the existing definitions of information leakage for backward privacy [Bost et al. CCS'17] and propose alternative formulations. Our first construction $\Pi_\mathsf{BP}\text{-}\mathsf{prime}$ achieves a stronger notion of backward privacy whereas our next two constructions $\Pi_\mathsf{BP}$ and $\Pi_\mathsf{WBP}$ achieve optimal communication complexity at the cost of some additional leakage. The prototype implementations of our schemes depict the practicability of the proposed constructions and indicate that the cost of achieving backward privacy over forward privacy is substantially small.

We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree $k\ge 2$, where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree $k\ge 2$ have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P '18) and arithmetic circuit arguments (EUROCRYPT '16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case ($k=1$) and a very specific quadratic case ($k=2$), which are obtained as a special case of our technique.

Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting ``inter-slot'' operations, and ``NTT-friendly'' tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.

To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.

Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.

Key exchange protocols in the asymmetric-key setting are known to provide stronger security properties than protocols in symmetric-key cryptography. In particular, they can provide perfect forward secrecy, as illustrated by key exchange protocols based on the Diffie-Hellman scheme. However public-key algorithms are too heavy for low-resource devices, which can then not benefit from forward secrecy. In this paper, we describe a scheme that solves this issue. Using a nifty resynchronisation technique, we propose an authenticated key exchange protocol in the symmetric-key setting that guarantees perfect forward secrecy. We prove that the protocol is sound, and provide a formal security proof.

We study protocols that rely on a public ledger infrastructure, concentrating on protocols for zero-knowledge contingent payment, whose security properties combine diverse notions of fairness and privacy. We argue that rigorous models are required for capturing the ledger semantics, the protocol-ledger interaction, the cryptographic primitives and, ultimately, the security properties one would like to achieve.

Our focus is on a particular level of abstraction, where network messages are represented by a term algebra, protocol execution by state transition systems (e.g. multiset rewrite rules) and where the properties of interest can be analyzed with automated verification tools. We propose models for: (1) the rules guiding the ledger execution, taking the coin functionality of public ledgers such as Bitcoin as an example; (2) the security properties expected from ledger-based zero-knowledge contingent payment protocols; (3) two different security protocols that aim at achieving these properties relying on different ledger infrastructures; (4) reductions that allow simpler term algebras for homomorphic cryptographic schemes.

Altogether, these models allow us to derive a first automated verification for ledger-based zero-knowledge contingent payment using the Tamarin prover. Furthermore, our models help in clarifying certain underlying assumptions, security and efficiency tradeoffs that should be taken into account when deploying protocols on the blockchain.

At the Computer Science Department at the University of Twente, we are looking for highly motivated and enthusiastic Assistant/Associate/Full Professors (f/m) in several domains.

In the Security & Privacy domain, we are particularly looking for someone in the areas of \"Big Data and Security\" (which considers both \"Big Data for Security\" and \"Security for Big Data\") and \"Security and the Internet of Things\" (broadly conceived).

For more information, please check the link provided below.

Closing date for applications: 25 May 2019

More information: https://www.utwente.nl/en/organization/careers/!/121825/assistantassociatefull-professors-in-computer-science

For a 3-year collaborative research project on automotive security, Lund University (Sweden) and Nanyang Technological University (Singapore) are seeking candidates for two postdoc/research fellow positions (from fresh post-doc to senior research fellow, flexible contract duration) in the areas of symmetric key cryptography and/or hardware implementations. One position is available for Lund University and one position is available for Nanyang Technological University.

Salaries are competitive and are determined according to the successful applicants accomplishments, experience and qualifications. Interested applicants should send their detailed CVs, cover letter and references to Prof. Thomas Johansson (thomas.johansson (at) eit.lth.se) and Prof. Thomas Peyrin (thomas.peyrin (at) ntu.edu.sg).

Review of applications starts immediately and will continue until positions are filled.

Closing date for applications: 15 October 2019

Contact: thomas.johansson (at) eit.lth.se and thomas.peyrin (at) ntu.edu.sg

Postdoctoral research fellow openings are immediately available in the School of Computer Science and Engineering (SCSE) at Nanyang Technological University (NTU) in Singapore. The postdoc will work with Assistant Professor Jun ZHAO (biography below) on one of the following topics:

1. Differential privacy with applications to deep learning, federated learning, or machine learning in general,

2. Local differential privacy,

3. Adversarial machine learning and security in AI systems,

4. Blockchains,

5. Other areas in AI security/privacy or IoT security/privacy.

Interested candidates can contact Jun Zhao via email at JunZhao (at) ntu.edu.sg?JunZhao (at) alumni.cmu.edu?via WeChat by scanning the QR code at http://www.ntu.edu.sg/home/JunZhao/wechat.png

via Skype at live:junzhaocmu, or by calling Singapore phone number +65 8648 3534 (the first two numbers 65 represent the area code of Singapore). Thanks.

Jun Zhao’s homepage: http://ntu.edu.sg/home/JunZhao/

Biography: Jun Zhao received a PhD degree in Electrical and Computer Engineering from Carnegie Mellon University (CMU) in the USA (advisors: Virgil Gligor, Osman Yagan), affiliating with CMU CyLab Security & Privacy Institute. He is currently an Assistant Professor at Nanyang Technological University (NTU) in Singapore. His research interests include blockchains, security, and privacy with applications to deep learning, the Internet of Things, and social networks.

Closing date for applications: 1 November 2019

Contact: Interested candidates can contact Jun Zhao via email at JunZhao (at) ntu.edu.sg?JunZhao (at) alumni.cmu.edu?via WeChat by scanning the QR code at http://www.ntu.edu.sg/home/JunZhao/wechat.png

via Skype at live:junzhaocmu, or by calling Singapore phone number +65 8648 3534 (the first two numbers 65 represent the area code of Singapore). Thanks.

More information: http://www.ntu.edu.sg/home/JunZhao/HirePostdoc.htm