International Association
for Cryptologic Research

Simon's algorithm is the first example of a quantum algorithm exponentially faster than any classical algorithm, and has many applications in cryptanalysis. While these quantum attacks are often extremely efficient, they are generally missing some precise cost estimate. This article aims at resolving this issue by presenting precise query estimates for the different use cases of Simon's algorithm in cryptanalysis, and shows that Simon's algorithm requires in most cases little more than $n$ queries to succeed.

Authentication continues to be a challenge for legacy real-time communications networks involving low-speed buses interconnecting resource-limited devices. A commercial vehicle network is such a network which does not change much over the years due to safety standards and regulations in the transportation domain. The SAE J1939 incorporating the ISO 11898- 1 specification for the data link and physical layers of the standard CAN and CAN-flexible data rate (CAN-FD) handles communication among electronic control units (ECUs). The SAE J1939 is susceptible to attacks such as replay, masquerading and man-in-the-middle. This paper presents a formal analysis of the existing authentication protocols for the SAE J1939 and identifies limitation, especially man-in-the-middle attack. To mitigate the attack, we propose two new authentication protocols. One pass authentication protocol is proposed for computationally restricted nodes, and for the nodes that support public key operations, a certificateless signature-based authentication protocol is proposed which is based on certificateless key insulated manageable signature scheme (CL-KIMS). The security of the new protocol suite and the signature scheme is formally analysed in the random oracle model. We use the Tamarin tool to verify mutual authentication, session key security, known key secrecy and forward security of the proposed protocols. Performance comparison shows that compared with the existing protocol suite, the new protocol suite is computation and communication efficient with robust security. Our simulation study in Matlab 2018a reveals that the key exchange protocols in the new protocol suite are efficient regarding consumption of lesser total message delay than its counterpart.

Fault-tolerant distributed systems move the trust in a single party to a majority of parties participating in the protocol. This makes blockchain based crypto-currencies possible: they allow parties to agree on a total order of transactions without a trusted third party. To trust a distributed system, the security of the protocol and the correctness of the implementation must be indisputable.

We present the first machine checked proof that guarantees both safety and liveness for a consensus algorithm. We verify a Proof of Stake (PoS) Nakamoto-style blockchain (NSB) protocol, using the foundational proof assistant Coq. In particular, we consider a PoS NSB in a synchronous network with a static set of corrupted parties. We define execution semantics for this setting and prove chain growth, chain quality, and common prefix which together implies both safety and liveness.

In the context of secure computation, protocols with security against covert adversaries ensure that any misbehavior by malicious parties will be detected by the honest parties with some constant probability. As such, these protocols provide better security guarantees than passively secure protocols and, moreover, are easier to construct than protocols with full security against active adversaries. Protocols that, upon detecting a cheating attempt, allow the honest parties to compute a certificate that enables third parties to verify whether an accused party misbehaved or not are called publicly verifiable.

In this work, we present the first generic compilers for constructing two-party protocols with covert security and public verifiability from protocols with passive security. We present two separate compilers, which are both fully blackbox in the underlying protocols they use. Both of them only incur a constant multiplicative factor in terms of bandwidth overhead and a constant additive factor in terms of round complexity on top of the passively secure protocols they use.

The first compiler applies to all two-party protocols that have no private inputs. This class of protocols covers the important class of preprocessing protocols that are used to setup correlated randomness among parties. We use our compiler to obtain the first secret-sharing based two-party protocol with covert security and public verifiability. Notably, the produced protocol achieves public verifiability essentially for free when compared with the best known previous solutions based on secret-sharing that did not provide public verifiability

Our second compiler constructs protocols with covert security and public verifiability for arbitrary functionalities from passively secure protocols. It uses our first compiler to perform a setup phase, which is independent of the parties' inputs as well as the protocol they would like to execute.

Finally, we show how to extend our techniques to obtain multiparty computation protocols with covert security and public verifiability against arbitrary constant fractions of corruptions.

The Fiat-Shamir transform is a general method for reducing interaction in public-coin protocols by replacing the random verifier messages with deterministic hashes of the protocol transcript. The soundness of this transformation is usually heuristic and lacks a formal security proof. Instead, to argue security, one can rely on the random oracle methodology, which informally states that whenever a random oracle soundly instantiates Fiat-Shamir, a hash function that is ``sufficiently unstructured'' (such as fixed-length SHA-2) should suffice. Finally, for some special interactive protocols, it is known how to (1) isolate a concrete security property of a hash function that suffices to instantiate Fiat-Shamir and (2) build a hash function satisfying this property under a cryptographic assumption such as Learning with Errors.

In this work, we abandon this methodology and ask whether Fiat-Shamir truly requires a cryptographic hash function. Perhaps surprisingly, we show that in two of its most common applications --- building signature schemes as well as (general-purpose) non-interactive zero-knowledge arguments --- there are sound Fiat-Shamir instantiations using extremely simple and non-cryptographic hash functions such as sum-mod-p or bit decomposition. In some cases, we make idealized assumptions about the interactive protocol (i.e., we invoke the generic group model), while in others, we argue soundness in the plain model. At a high level, the security of each resulting non-interactive protocol derives from hard problems already implicit in the original interactive protocol.

On the other hand, we also identify important cases in which a cryptographic hash function is provably necessary to instantiate Fiat-Shamir. We hope that this work leads to an improved understanding of the precise role of the hash function in the Fiat-Shamir transformation.

In this paper we study multivariate public key signature schemes with "ultra"-short signatures. In order to do so, we consider that signing and verifying a signature could require about 1 minute of computation on a modern personal computer. Despite the fact that this time is way bigger than the time required by general purpose multivariate-based signature schemes, such as Quartz or GeMMS, it enables us to reach ultra-short signature length, for instance, around 70 bits long signatures for a security of 80 bits. Two main issues arise when one wants to build a signature scheme with ultra-short signatures: avoiding the birthday paradox attack and having the ability to sign arbitraly long messages, this paper gives ways to overcome both.

In a first part, we describe the attacks against multivariate public key signature and use them to compute the minimal parameters that an ultra-short signature scheme would have. In a second part, we give an explicit example of such an ultra-short signature scheme using HFE-like algorithms. In the end, we give parameters for several level of security: 80, 90, 100 bits and the classic 128, 192, and 256 bits; for each of them, we propose different choices of finite fields.

Differential cryptanalysis is an important technique to evaluate the security of block ciphers. There exists several generalisations of differential cryptanalysis and it is also used in combination with other cryptanalysis techniques to improve the attack complexity. Usefulness of Machine learning in differential cryptanalysis is introduced by Gohr in 2019 to attack the lightweight block cipher SPECK. In this paper, we present a framework to combine the classical differential distinguisher and machine learning (ML) based differential distinguisher. We propose a novel technique to construct differential-ML distinguisher which provides better results with reduced data complexity. This technique is demonstrated on lightweight block ciphers SPECK & SIMON where 96% & 99% (or more) success rate is achieved for distinguishing the 6-round SPECK and 9-round SIMON respectively.

In this paper, we propose EM side-channel attacks with carefully constructed ciphertext on Kyber, a lattice-based key encapsulation mechanism, which is a candidate of NIST Post-Quantum Cryptography standardization project. We demonstrate that specially chosen ciphertexts allow an adversary to modulate the leakage of a target device and enable full key extraction with a small number of traces through simple power analysis. Compared to prior research, our techniques require a lower number of traces and avoid the need for template attacks. We practically evaluate our methods using both a clean reference implementation of Kyber and the ARM-optimized pqm4 library. For the reference implementation, we target the leakage of the output of the inverse NTT computation and recover the full key with only four traces. For the pqm4 implementation, we develop a message-recovery attack that leads to extraction of the full secret-key with between eight and 960 traces (or 184 traces for recovering 98% of the secret-key), depending on the compiler optimization level. We discuss the relevance of our findings to other lattice-based schemes and explore potential countermeasures.

We introduce a new cryptographic primitive, a lossy correlation-intractable hash function, and use it to soundly instantiate the Fiat-Shamir transform for the general interactive sumcheck protocol, assuming sub-exponential hardness of the Learning with Errors (LWE) problem. By combining this with the result of Choudhuri et al. (STOC 2019), we show that $\#\mathsf{SAT}$ reduces to end-of-metered line, which is a $\mathsf{PPAD}$-complete problem, assuming the sub-exponential hardness of LWE.

The Hamming Quasi-Cyclic (HQC) proposal is a promising candidate in the second round of the NIST Post-Quantum cryptography Standardization project. It features small public key sizes, precise estimation of its decryption failure rates and contrary to most of the code-based systems, its security does not rely on hiding the structure of an error-correcting code. In this paper, we propose the first power side-channel attack on the Key Encapsulation Mechanism (KEM) version of HQC. Our attack utilizes a power side-channel to build an oracle that outputs whether the BCH decoder in HQC's decryption algorithm corrects an error for a chosen ciphertext. Based on the decoding algorithm applied in HQC, it is shown how to design queries such that the output of the oracle allows to retrieve a large part of the secret key. The remaining part of the key can then be determined by an algorithm based on linear algebra. It is shown in experiments that less than 10000 measurements are sufficient to successfully mount the attack on the HQC reference implementation running on an ARM Cortex-M4 microcontroller.

The University of Luxembourg invites applications from M.Sc. holders in the general area of applied cryptography. Cryptolux.org is a team of cryptographers and security researchers interested in applied cryptography, cryptanalysis, privacy, network security, cryptographic blockchains and is led by Prof. Alex Biryukov. We are affiliated to the Department of Computer Science (DCS) and to the interdisciplinary Security and Trust center (SnT).

Area (potential topics of the thesis)

• Cryptanalysis and design of cryptographic primitives
• Lightweight block ciphers, hash functions, authenticated encryption schemes
• Privacy Enhancing Technology (Tor-like networks, privacy for cryptocurrencies, blockchains)
• Blockchain Cryptography
• Design of proofs of work, resource-hard functions, commitment schemes
• Side-channel attacks and countermeasures
• White-box cryptography

The University offers a Ph.D. study program with an Initial contract of 36 months, with a further possible 1-year extension if required. The University offers competitive salaries and is an equal opportunity employer. You will work in an exciting international environment and will have a chance to participate in the development of a newly created research center.

Starting date 15-Oct-2020 or later upon agreement. Early submission is encouraged; applications will be processed upon receipt.

Closing date for applications:

Contact: Prof. Alex Biryukov

More information: https://recruitment.uni.lu/en/details.html?nPostingId=52476&nPostingTargetId=71379&id=QMUFK026203F3VBQB7V7VV4S8&LG=UK&ma

The University of Luxembourg, Computer Science department and Centre for Security, Reliability and Trust (SnT) invite applications from Ph.D. holders in the general area of Applied Cryptography. SnT is carrying out interdisciplinary research in secure, reliable and trustworthy ICT. CryptoLux/SnT team is currently doing research in cryptography, distributed ledgers and privacy.

Research area The successful candidate will join the CryptoLux research team led by Prof. Alex Biryukov. He or she will contribute to a research project entitled "Security, Scalability, and Privacy in Blockchain Applications and Smart Contracts (FINCRYPT)", which is funded by the Luxembourg National Research Fund (FNR). Candidates with proven research track record in one or more of the following areas are particularly encouraged to apply:

Applied Cryptography (SK or PK, PoWs, efficient ZK proofs, etc.)
Crypto-currencies, smart-contracts, financial cryptography, blockchains
Privacy enhancing technologies
Distributed consensus protocols

Your Profile

• A Ph.D. degree in Computer Science, Applied Mathematics or a related field
• Competitive research record in cryptography or information security (at least one paper in top 10 IT security/crypto conferences)
• Strong mathematical and algorithmic CS background, interest in economics/finance - a plus
• Good skills in programming and scripting languages
• Fluent written and verbal communication skills in English are mandatory

Starting date 1-Oct-2020 or later upon agreement. Due to Covid, EU citizens or residents will be given preference. Position is for 12 month with possible extension.

Closing date for applications:

Contact: Prof. Alex Biryukov

More information: https://recruitment.uni.lu/en/details.html?nPostingId=52476&nPostingTargetId=71379&id=QMUFK026203F3VBQB7V7VV4S8&LG=UK&ma

We are looking for an excellent, motivated, post-doctoral researcher to work in the area of information security and cryptography. The post-doctoral researcher will join Katerina Mitrokotsa's research group (Chair of Cyber Security), working in the area of information and communication security with a focus on authentication protocols, verifiable delegation of computation, and secure multi-party computation. The position is available for one plus one year after a successful review evaluation.

Closing date for applications:

Contact: Katerina Mitrokotsa

More information: http://direktlink.prospective.ch/?view=7716a2ff-927c-4fb5-aa35-90e310e2f4f3

We are looking for an excellent, motivated, self-driven doctoral student to work in the area of information security and cryptography. The position is within the group of Prof. Katerina Mitrokotsa (Chair of Cyber Security) who is doing research in cryptographic protocols that guarantee reliable authentication, privacy-preservation and verifiable delegation of computation. The topic of this project is focusing on investigating security and privacy issues for resource-constrained devices (e.g., sensors) that rely on external untrusted servers in order to perform computations. More precisely, the student shall be working on investigating efficient authentication and verifiable delegation of computation mechanisms that provide: i) provable security guarantees, and ii) rigorous privacy guarantees. The overall aim of the PhD position will be to design and evaluate provably secure cryptographic protocols for privacy-preserving authentication and verifiable delegation of computation protocols. The research shall also consider the case where multiple clients outsource jointly computations to untrusted cloud servers.

Closing date for applications:

Contact: Katerina Mitrokotsa

More information: http://direktlink.prospective.ch/?view=2d5b5bd0-e017-4917-90bb-14f3b6efe9c4

Event date: 17 May to 21 May 2021
Submission deadline: 1 December 2020
Notification: 17 February 2021

Registration has now opened for Crypto 2020. There are four affiliated events associated with the conference that occur on Friday-Sunday before the conference, and information on these has been updated.

A common primitive in election and auction protocols is plaintext equivalence test (PET) in which two ciphertexts are tested for equality of their plaintexts, and a verifiable proof of the test's outcome is provided. The most commonly-cited PETs require at least one honest party, but many applications claim universal verifiability, at odds with this requirement. If a test that relies on at least one honest participant is mistakenly used in a place where universally verifiable proof is needed, then a collusion by all participants can insert a forged proof of equality into the tallying transcript. We show this breaks universal verifiability for the JCJ/Civitas scheme among others, because the only PETs they reference are not universally verifiable. We then demonstrate how to fix the problem.

Minrank problem is investigated as a problem related to a rank attack in multivariate cryptography and decoding of a rank code in coding theory. Recently, the Kipnis-Shamir method for solving this problem has been made significant progress due to Verbel et al. As this method reduces the problem to the MQ problem that asks for a solution of a system of quadratic equations, its complexity depends on the solving degree of a quadratic system deduced from the method. A theoretical value introduced by Verbel et al. approximates the minimal solving degree of the quadratic systems in the method although their value is defined under a certain limit for a considering system. A quadratic system outside their limitation often has the larger solving degree, but its solving complexity is not necessary larger since it has a smaller number of variables and equations. Thus, in order to discuss the best complexity of the Kipnis-Shamir method, we need a theoretical value approximating the solving degree of each deduced quadratic system. A quadratic system deduced from the Kipnis-Shamir method has a multi-degree always, and its solving complexity is influenced by this property. In this paper, we introduce a theoretical value defined by such a multi-degree and show it approximates the solving degree of each quadratic system. Thus we are able to compare the systems in the method and to discuss the best complexity. As its application, in the Minrank problem from the rank attack using the Kipnis-Shamir method against Rainbow, we show a case that a quadratic system outside Verbel et al.'s limitation is the best. Consequently, by using our estimation, the complexities of the attack against Rainbow parameter sets Ia, IIIc and Vc are improved as $2^{160.6}, 2^{327.9}$ and $2^{437.0}$, respectively.

In cloud computing, multiple users can share the same physical machine that can potentially leak secret information, in particular when the memory de-duplication is enabled. Flush+Reload attack is a cache-based attack that makes use of resource sharing. T-table implementation of AES is commonly used in the crypto libraries like OpenSSL. Several Flush+Reload attacks on T-table implementation of AES have been proposed in the literature which requires a notable number of encryptions. In this paper, we present a technique to enhance the Flush+Reload attack on AES in the ciphertext-only scenario by significantly reducing the number of needed encryptions in both native and cross-VM setups. In this paper, we focus on finding the wrong key candidates and keep the right key by considering only the cache miss event. Our attack is faster than previous Flush+Reload attacks. In particular, our method can speed-up the Flush+Reload attack in cross-VM environment significantly. To verify the theoretical model, we implemented the proposed attack.

In this paper, we present an optimally-resilient, unconditionally-secure asynchronous multi-party computation (AMPC) protocol for $n$ parties, tolerating a computationally unbounded adversary, capable of corrupting up to $t < \frac{n}{3}$ parties. Our protocol needs a communication of ${\cal O}(n^4)$ field elements per multiplication gate. This is to be compared with previous best AMPC protocol (Patra et al, ICITS 2009) in the same setting, which needs a communication of ${\cal O}(n^5)$ field elements per multiplication gate. To design our protocol, we present a simple and highly efficient asynchronous verifiable secret-sharing (AVSS) protocol, which is of independent interest.