International Association for Cryptologic Research

IACR News Central

Here you can see all recent updates to the IACR webpage. These updates are also available:

Now viewing news items related to:

12 March 2019
ePrint Report Sync HotStuff: Synchronous SMR with 2∆ Latency and Optimistic Responsiveness Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, Maofan Yin
Synchronous solutions for building Byzantine Fault Tolerance (BFT) replication can be safe when < 1/2 of the replicas fail. Assuming $\Delta$ is an upper bound on the time for messages to arrive, these solutions must incur at least $\Delta$ latency for consensus on a single value. In this work, we show a consensus protocol named Sync HotStuff designed to achieve consensus on a sequence of values with a latency of $2\Delta$ in the common mode when less than half of the replicas are Byzantine. Thus, in the common mode, Sync HotStuff is within a factor of 2 of the optimal latency. Moreover, Sync HotStuff has responsiveness, i.e., it advances at network speed, when < 1/4 of the replicas are not responding, a small sacrifice in availability compared with optimal asynchronous solutions. Borrowing from practical BFT solutions in the asynchronous arena, Sync HotStuff has an extremely simple, two-phase leader-based structure, that easily fits in one frame of pseudo-code.
10 March 2019
ePrint Report Software implementation of binary elliptic curves: impact of the carry-less multiplier on scalar multiplication Jonathan Taverne, Armando Faz-Hernández, Diego F. Aranha, Francisco Rodríguez-Henríquez, Darrel Hankerson, Julio López
The availability of a new carry-less multiplication instruction in the latest Intel desktop processors significantly accelerates multiplication in binary fields and hence presents the opportunity for reevaluating algorithms for binary field arithmetic and scalar multiplication over elliptic curves. We describe how to best employ this instruction in field multiplication and the effect on performance of doubling and halving operations. Alternate strategies for implementing inversion and half-trace are examined to restore most of their competitiveness relative to the new multiplier. These improvements in field arithmetic are complemented by a study on serial and parallel approaches for Koblitz and random curves, where parallelization strategies are implemented and compared. The contributions are illustrated with experimental results improving the state-of-the-art performance of halving and doubling-based scalar multiplication on NIST curves at the 112- and 192-bit security levels, and a new speed record for side-channel resistant scalar multiplication in a random curve at the 128-bit security level.
8 March 2019
Event date: 20 June to 21 June 2019
6 March 2019
ePrint Report Digital Signatures for Consensus Sergey Gorbunov, Hoeteck Wee
We present a pairing-based signature scheme for use in blockchains that achieves substantial savings in bandwidth and storage requirements while providing strong security guarantees. Our signature scheme supports aggregation on the same message, which allows us to compress multiple signatures on the same block during consensus, and achieves forward security, which prevents adaptive attacks on the blockchain. Our signature scheme can be applied to all blockchains that rely on multi-party consensus protocols to agree on blocks of transactions (such as proof-of-stake or permissioned blockchains).
5 March 2019
With increasing autonomous features of vehicles, key issues of robotic- and automotive engineering converge toward each other. Closing existing security gaps of device communication networks will be an enabling feature for connecting autonomously interacting systems in a more secure way. We introduce a novel approach for deriving a secret key using a lightweight cipher in the firmware of a low-end control unit. In this approach, we propose to use a non-standardized lightweight algorithm with unique hardware based parameters to prevent duplicate key generation. The randomness of the selected cipher was assessed by applying the NIST statistical test suite to produced key values. By evaluating the method on a typical low-end automotive platform, we could demonstrate the realistic applicability of the solution. The proposed method counteracts a known security issue in device communication between control units not only present in automotive solutions but also in the robotics domain. The security of the implemented solution has been compared to current automotive guidelines and recommendations for the security of resource constrained devices, also present in robotics. This approach allows low-end communication systems to be enhanced by message- and device authentication.
ePrint Report Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on Falcon. Angshuman Karmakar, Sujoy Sinha Roy, Ingrid Verbauwhede, Frederik Vercauteren
Sampling from discrete Gaussian distribution has applications in lattice-based post-quantum cryptography. Several efficient solutions have been proposed in recent years. However, making a Gaussian sampler secure against timing attacks turned out to be a challenging research problem. In this work, we observed an important property of the input random bit strings that generate samples in Knuth-Yao sampling. We delineate a generic step-by-step method to instantiate a discrete Gaussian sampler of arbitrary standard deviation and precision by efficiently minimizing the Boolean expressions by exploiting this prop- erty. Discrete Gaussian samplers generated in this method can be up to 37% faster than the state of the art method. Finally, we show that the signing algorithm of post-quantum signature scheme Falcon using our constant-time sampler is at most 33% slower than the fastest non-constant time sampler.
This paper introduces streamlined constant-time variants of Euclid's algorithm, both for polynomial inputs and for integer inputs. As concrete applications, this paper saves time in (1) modular inversion for Curve25519, which was previously believed to be handled much more efficiently by Fermat's method, and (2) key generation for the ntruhrss701 and sntrup4591761 lattice-based cryptosystems.
ePrint Report TEX - A Securely Scalable Trustless Exchange Rami Khalil, Arthur Gervais, Guillaume Felley
Financial exchanges are typically built out of two trusted components: a trade matching and a trade settlement system. With the advent of decentralized ledgers, that perform transactions without a trusted intermediary, so called decentralized exchanges (DEX) emerged. Some DEXs propose to off-load trade order matching to a centralized system outside the blockchain to scale, but settle each trade trustlessly as an expensive on-chain transaction. While DEX are non-custodial, their order books remains trusted, a malicious exchange operator or miner could front-run trades --- i.e. alter trade order execution for financial gain. The scalability limitations of the settlement layer (e.g. Proof of Work (PoW) blockchains) moreover hinders the practical growth of such DEX architectures.

We propose TEX, a front-running resilient, non-custodial centralized exchange. Our matching system enforces the trade order sequence provided by traders, i.e. is resilient against trade sequence alteration by the exchange operator. As such the matching system can operate in conjunction with a blockchain based settlement layer (as proposed in the following), or make custodian exchanges provably accountable for their matching process. Our layer-two settlement system executes a trade without holding the assets, and allows to reach similar scales as traditional exchanges (trading volume in USD, number of trades/second), despite a slow underlying ledger. TEX might become a point of availability-failure, but we show how the settlement system's security properties would not compromise the trader's assets, even if the centralized operator is compromised and/or colludes with all other traders. We provide an evaluation on a PoW blockchain.
ePrint Report Unifying computational entropies via Kullback-Leibler divergence Rohit Agrawal, Yi-Hsiu Chen, Thibaut Horel, Salil Vadhan
We introduce KL-hardness, a new notion of hardness for search problems which on the one hand is satisfied by all one-way functions and on the other hand implies both next-block pseudoentropy and inaccessible-entropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively. Thus, KL-hardness unifies the latter two notions of computational entropy and sheds light on the apparent "duality" between them. Additionally, it yields a more modular and illuminating proof that one-way functions imply next-block inaccessible entropy, similar in structure to the proof that one-way functions imply next-block pseudoentropy (Vadhan and Zheng, STOC '12).
Cryptocurrencies have provided a promising infrastructure for pseudonymous online payments. However, low throughput has significantly hindered the scalability and usability of cryptocurrency systems for increasing numbers of users and transactions. Another obstacle to achieving scalability is the requirement for every node to duplicate the communication, storage, and state representation of the entire network.

In this paper, we introduce the Asynchronous Consensus Zones, which scales blockchain system linearly without compromising decentralization or security. We achieve this by running multiple independent and parallel instances of single-chain consensus systems termed as zones. The consensus happens independently within each zone with minimized communication, which partitions the workload of the entire network and ensures a moderate burden for each individual node as the network grows. We propose eventual atomicity to ensure transaction atomicity across zones, which achieves the efficient completion of transactions without the overhead of a two-phase commit protocol. Additionally, we propose Chu-ko-nu mining to ensure the effective mining power in each zone to be at the same level of the entire network, making an attack on any individual zone as hard as that on the full network. Our experimental results show the effectiveness of our work: on a testbed including 1,200 virtual machines worldwide to support 48,000 nodes, our system delivers 1,000x throughput and 2,000x capacity over the Bitcoin and Ethereum networks.
The Fiat-Shamir transformation is a useful approach to building non-interactive arguments (of knowledge) in the random oracle model. Unfortunately, existing proof techniques are incapable of proving the security of Fiat-Shamir in the quantum setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the inability of current techniques to adaptively program random oracles in the quantum setting.

In this work, we show how to overcome the limitations above in many settings. In particular, we give mild conditions under which Fiat-Shamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications.
ePrint Report Forward-Secure Multi-Signatures Manu Drijvers, Gregory Neven
Multi-signatures allow a group of signers to jointly sign a message in a compact and efficiently verifiable signature, ideally independent of the number of signers in the group. We present the first provably secure forward-secure multi-signature scheme by deriving a forward-secure signature scheme from the hierarchical identity-based encryption of Boneh, Boyen, and Goh (Eurocrypt 2005) and showing how the signatures in that scheme can be securely composed. Multi-signatures in our scheme contain just two group elements (one from each of the base groups) and require one exponentation and three pairing computations to verify.
We propose a modular security treatment of blind signatures derived from linear identification schemes in the random oracle model. To this end, we present a general framework that captures several well known schemes from the literature and allows to prove their security. Our modular security reduction introduces a new security notion for identification schemes called One-More-Man In the Middle Security which we show equivalent to the classical One-More-Unforgeability notion for blind signatures. We also propose a generalized version of the Forking Lemma due to Bellare and Neven (CCS 2006) and show how it can be used to greatly improve the understandability of the classical security proofs for blind signatures schemes by Pointcheval and Stern (Journal of Cryptology 2000).
ePrint Report A Practical Method to Recover Exact Superpoly in Cube Attack SenPeng Wang, Bin Hu, Jie Guan, Kai Zhang, TaiRong Shi
Cube attack is an important cryptanalytic technique against symmetric cryptosystems, especially for stream ciphers. The key step in cube attack is recovering superpoly. However, when cube size is large, the large time complexity of recovering the exact algebraic normal form (ANF) of superpoly confines cube attack. At CRYPTO 2017, Todo et al. applied conventional bit-based division property (CBDP) into cube attack which could exploit large cube sizes. However, CBDP based cube attacks cannot ensure that the superpoly of a cube is non-constant. Hence the key recovery attack may be just a distinguisher. Moreover, CBDP based cube attacks can only recover partial ANF coefficients of superpoly. The time complexity of recovering the reminding ANF coefficients is very large, because it has to query the encryption oracle and sum over the cube set. To overcome these limits, in this paper, we propose a practical method to recover the ANF coefficients of superpoly. This new method is developed based on bit-based division property using three subsets (BDPT) proposed by Todo at FSE 2016. We apply this new method to reduced-round Trivium. To be specific, the time complexity of recovering the superpoly of 832-round Trivium at CRYPTO 2017 is reduced from $2^{77}$ to practical, and the time complexity of recovering the superpoly of 839-round Trivium at CRYPTO 2018 is reduced from $2^{79}$ to practical. Then, we propose a theoretical attack which can recover the superpoly of Trivium up to 842 round. As far as we know, this is the first time that the superpoly can be recovered for Trivium up to 842 rounds.
Concrete security proofs give upper bounds on the attacker's advantage as a function of its time/query complexity. Cryptanalysis suggests however that other resource limitations - most notably, the attacker's memory - could make the achievable advantage smaller, and thus these proven bounds too pessimistic. Yet, handling memory limitations has eluded existing security proofs.

This paper initiates the study of time-memory trade-offs for basic symmetric cryptography. We show that schemes like counter-mode encryption, which are affected by the Birthday Bound, become more secure (in terms of time complexity) as the attacker's memory is reduced.

One key step of this work is a generalization of the Switching Lemma: For adversaries with $S$ bits of memory issuing $q$ distinct queries, we prove an $n$-to-$n$ bit random function indistinguishable from a permutation as long as $S \times q \ll 2^n$. This result assumes a combinatorial conjecture, which we discuss, and implies right away trade-offs for deterministic, stateful versions of CTR and OFB encryption.

We also show an unconditional time-memory trade-off for the security of randomized CTR based on a secure PRF. Via the aforementioned conjecture, we extend the result to assuming a PRP instead, assuming only one-block messages are encrypted.

Our results solely rely on standard PRF/PRP security of an underlying block cipher. We frame the core of our proofs within a general framework of indistinguishability for streaming algorithms which may be of independent interest.
Event date: 24 August 2019
Submission deadline: 25 May 2019
2 March 2019
Event date: 26 July to 28 July 2019
Submission deadline: 15 April 2019
Notification: 23 May 2019
Event Calendar CrossFyre 2019 Darmstadt, Germany, 17 May - 18 May 2019
Event date: 17 May to 18 May 2019
Submission deadline: 18 March 2019
Notification: 25 March 2019
Kanazawa University, Japan, invites applications for an associate professor position or a tenure-track assistant professor position in advanced research area of information security, such as IT Security and Cryptography.

An appointee is expected on duty on July 1st, 2019 or at an early possible time after that.

Research budget:: In case of tenure-track assistant professor, Kanazawa University plans to provide a start-up research fund of approximately 800,000 JPY in the first year in addition to faculty research expense.

Closing date for applications: 15 March 2019

Contact: Masahiro Mambo (Contact information can be found below.)

More information:

Simula UiB has up to four three-year PhD positions available in the field of cryptography. The following specific topics are of particular interest:

- algorithmic and theoretical aspects of side-channel security

- cryptographic protocols for privacy-preserving applications

- privacy-preserving pairing-based and lattice-based protocols for applications like blockchain

The PhD students will enter the PhD program of the Department of informatics at the University of Bergen. Applications must be submitted via

Closing date for applications: 30 April 2019

Contact: For questions and inquiries, please contact

Martijn Stam, email: martijn (at)


Helger Lipmaa, email: helger.lipmaa (at)

More information:

Job Posting Two Postdoc Positions Information Security Group, Royal Holloway, University of London, UK
Two Postdoc positions are available in the Information Security Group at Royal Holloway, University of London, UK.

The postdoc will work alongside Martin Albrecht and other cryptographic researchers in the ISG on topics in lattice-based cryptography and related fields. One post is funded by a joint grant between Royal Holloway and Imperial College (Cong Ling) for bridging the gap between lattice-based cryptography and coding theory (starting date: 15 April or later). The second post is funded by an EPSRC grant on investigating the security of lattice-based and post-quantum cryptographic constructions (starting date: 1 June or later). Applicants with a strong background in all areas of cryptography are encouraged to apply.

Applicants should have already completed, or be close to completing, a PhD in a relevant discipline. Applicants should have an outstanding research track record in cryptography. Applicants should be able to demonstrate scientific creativity, research independence, and the ability to communicate their ideas effectively in written and verbal form.

The ISG is one of the largest departments dedicated to information security in the world with 21 core academic staff in the department, as well as research and support staff. We work with many research partners in other departments and have circa 90 PhD students working on a wide range of security research, many of whom are fully funded through our Centre for Doctoral Training in Cyber Security. We have a strong, vibrant, embedded and successful multi-disciplinary research profile spanning from cryptography to systems security and social aspects of security. This vibrant environment incorporates visiting researchers, weekly research seminars, weekly reading groups, PhD seminars and mini conferences, the WISDOM group (Women in the Security Domain Or Mathematics) and we are proud of our collegial atmosphere and approach.

Closing date for applications: 5 April 2019

Contact: Martin Albrecht, martin.albrecht _AT_

More information:

Job Posting Research Intern in Cryptography IMDEA Software Institute, Madrid, Spain
The IMDEA Software Institute (Madrid, Spain) invites applications for a research internship in the area of Cryptography. The successful candidate will join the cryptography group led by Prof. Dario Fiore to work on a project within the area of zero-knowledge proofs and their applications to blockchain protocols.

Who should apply: Applicants should be MSc or PhD students in computer science, mathematics or a related discipline. Strong knowledge of cryptography and solid programming skills are required. Familiarity with cryptographic protocols, cryptography implementation libraries or C++ will be considered as a plus.

Working at IMDEA Software: The position is based in Madrid, Spain, where the IMDEA Software Institute is situated. The institute provides for travel expenses and an internationally competitive stipend. The working language at the institute is English.

Dates: The internship duration is intended to be for 4-6 months (with some flexibility). The ideal starting period is from May 2019.

How to apply: Applicants interested in the position should submit their application at using reference code 2019-02-intern-crypto. Deadline for applications is April 15, 2019. Review of applications will begin immediately.

Closing date for applications: 15 April 2019

Contact: For enquiries about the position, please contact:

Dario Fiore, dario.fiore (at)

Matteo Campanelli, matteo.campanelli (at)

More information:

Job Posting Open Quantum Safe (libOQS), Cryptographic Research Architect position Institute for Quantum Computing at University of Waterloo
This position is available immediately in Professor Mosca’s Research group. You will be working with a team of researchers and developers from academia and industry on the Open Quantum Safe project ( You will help integrate new post-quantum cryptographic algorithms into the libOQS open-source library, and design and implement techniques for evaluating and benchmarking these cryptographic algorithms in a variety of contexts. You will be required to participate in weekly sprint meetings and perform software development tasks assigned by the project team lead, ensuring that all code contributions developed by self or integrated from 3rd party contribution sources adhere to a cohesive design and framework. The field of post-quantum cryptography is rapidly evolving, and you will need to track ongoing changes to algorithms due to peer review and advances by researchers via the the NIST Post-Quantum Cryptography project forum. Any significant findings relating to a particular PQ algorithm’s effectiveness or efficiency should be brought to the attention of team lead, and may be disclosed to other researchers in forum. In addition to algorithm research, tasks cover all aspects of the software development lifecycle and include design, programming cryptographic algorithms, integrating other cryptographic implementations into the libOQS framework, integrating libOQS into 3rd party opensource projects, testing, benchmarking and documentation. You may be required to take an ownership role in coordinating the development of a sub-component of the Open Quantum Safe project.

Closing date for applications: 30 August 2019

Contact: Michele Mosca: michele.mosca (at)

Douglas Stebila: dstebila (at)

More information:

This post offers an exciting opportunity for an appointment to strengthen the research of our existing research, for example at the interface between security and machine learning and in data science.

The Department has a large secure systems research group, led by Professor Steve Schneider, with expertise in security by design, cryptography, authentication, verification, distributed ledger technologies, trusted systems, IoT security, program analysis and cloud security. Professor Yaochu Jin also leads a research group specialising in machine learning, complex systems and networks, Bayesian learning, neuroscience, evolutionary computation and applications of machine learning.

Closing date for applications: 17 March 2019

Contact: Helen Treharne

More information:

Job Posting Postdoctoral Fellows The University of York (UK)
If you are thinking of applying for such a fellowship, the Cyber Security group at the University of York would be very happy to talk to you about the possibility of hosting your fellowship with us.

The topic is related to \"Opportunities and risks in the application of machine and deep learning to security screening\". The Government Office for Science offers UK Intelligence Community (IC) Postdoctoral Research Fellowships to outstanding early career science or engineering researchers. These Fellowships are designed to promote unclassified basic research in areas of interest to the intelligence, security and defence communities.

UK IC Postdoctoral Research Fellowships can be held on a job share basis, if two suitable candidates are available to work on the project. UK IC Postdoctoral Research Fellowships are for a two-year period with an evaluation after the first year.

Applications are capped at a maximum contribution of £100,000 per year, at 80% of Full Economic Costs.

Applicants have no nationality restrictions. The host institution of the research fellowship will be responsible for securing all necessary work permits and related costs.

The Department of Computer Science at University of York has an established reputation for conducting research that has real impact in a wide range of sectors; in the Research Excellence Framework (REF) 2014, we were ranked 5th for impact, 6th for environment and 7th in the UK overall.

The deadline for proposal submission is April 1, 2019. (Our Centre Website:

Closing date for applications: 10 March 2019

Contact: Interested candidates should contact Professor Delaram Kahrobaei (Chair of Cyber Security at University of York) delaram.kahrobaei (at) as soon as possible to develop a proposal.

Job Posting Ph.D. and Post-Doc Positions Institute of Information Security, University of Stuttgart, Germany
The Institute of Information Security at University of Stuttgart offers several

Ph.D. and Postdoc Positions

in applied cryptography, with a focus on

- Multi-Party Computation,

- Zero-Knowledge Proofs,

- Fully Homomorphic Encryption,

and applications thereof.

The positions are available immediately with an internationally competitive salary, paid according to the German public salary scale TVL-E13 or TVL-E14 (depending on the candidate\'s qualification). Appointment periods follow the German science appointment regulations, ranging from one year to up to six years.

The Institute of Information Security offers a creative international environment for top-level international research in Germany\'s high-tech region.

The successful candidate should have a Master\'s degree or a Ph.D. (or should be very close to completion thereof) in Computer Science, Mathematics, Cyber Security, or a related field. We value excellent analytical and mathematical skills. Knowledge in cryptography, and in particular, one of the mentioned fields, is an asset. Knowledge of German is not required. We can offer positions with and without teaching obligations.

The deadline for applications is

March 24th, 2019.

Late applications will be considered until the positions are filled.

Closing date for applications: 24 March 2019

Contact: Prof. Ralf Kuesters

ralf.kuesters (at)

More information:

Job Posting Ph.D. student in Hardware security for post-quantum cryptography based on elliptic curve isogenies Mines Saint-Etienne, CEA-Tech, Centre CMP, Departement SAS, F - 13541 Gardanne France
Applications are invited for a 3 years PhD fellowship/scholarship at Mines Saint-Etienne, CEA-Tech, Centre CMP, Departement SAS, Gardanne France. The position is available from 1 October 2019 or later.

The main objective of this PhD thesis is to design protections to improve the security of SIKE (Supersingular Isogeny Key Encapsulation) implementations against side-channel and fault attacks.

Walks in elliptic curve isogeny graphs can be used to establish a shared secret with a Diffie-Hellman like protocol. SIKE is a key encapsulation suite based on this asymmetric cryptography. It is executed on conventional computer and is thought to be secure against an attack by a quantum computer. NIST has initiated a competitive \"post-quantum\" cryptography standardisation. These algorithms were built to avoid cryptanalysis. But, attackers may explore alternative attack methods that exploit physical access to implementation.

Electromagnetic radiation analysis of deciphering or fault injection are examples of such attacks. There exist protections to hide secrets which are used by implementations of classical cryptography. But, there are only few counter-measures to protect SIKE implementations and the threat of physical attacks against isogeny-based cryptography is not well known, up to now. This thesis will address these two problems.

The PhD student will begin by studying the SIKE protocol and existing implementations. He/She will have to identify existing physical attack propositions and to provide new attack methods. To refine the threat characterisation, he/she will build attack demonstrators based on side-channel analysis and/or fault injection. He/She will propose counter-measures that could be algorithmic, software or hardware methods to protect SIKE implementations.

The SAS \"Secure Architectures and Systems\" research group is located in Gardanne (FRANCE). It is a joint CEA and EMSE team with state-of-art equipment to perform side-channel and fault attacks. PhD student supervisors are Nadia El-Mrabet (EMSE/SAS), Luca De Feo (UVSQ/CRYPTO) and Simon Pontié (CEA/SAS).

Closing date for applications: 25 April 2019

Contact: Simon PONTIE, Simon.PONTIE (at)

Job Posting PhD scholarships on cyber security Singapore University of Technology and Design (SUTD), Singapore
PhD scholarship on cyber security is available in SUTD. Interested candidates please send your CV with a research statement to Prof. Jianying Zhou. Only short-listed candidates will be contacted for interview.

Closing date for applications: 30 April 2019

Contact: Prof. Jianying Zhou

jianying_zhou (at)

More information:

28 February 2019
Quantum information is well-known to achieve cryptographic feats that are unattainable using classical information alone. Here, we add to this repertoire by introducing a new cryptographic functionality called uncloneable encryption. This functionality allows the encryption of a classical message such that two collaborating but isolated adversaries are prevented from simultaneously recovering the message, even when the encryption key is revealed. Clearly, such functionality is unattainable using classical information alone.

We formally define uncloneable encryption, and show how to achieve it using Wiesner's conjugate coding, combined with a quantum-secure pseudorandom function (qPRF). Modelling the qPRF as a quantum random oracle, we show security by adapting techniques from the quantum one-way-to-hiding lemma, as well as using bounds from quantum monogamy-of-entanglement games.
ePrint Report DLCT: A New Tool for Differential-Linear Cryptanalysis Achiya Bar-On, Orr Dunkelman, Nathan Keller, Ariel Weizman
Differential cryptanalysis and linear cryptanalysis are the two best-known techniques for cryptanalysis of block ciphers. In 1994, Langford and Hellman introduced the differential-linear (DL) attack based on dividing the attacked cipher $E$ into two subciphers $E_0$ and $E_1$ and combining a differential characteristic for $E_0$ with a linear approximation for $E_1$ into an attack on the entire cipher $E$. The DL technique was used to mount the best known attacks against numerous ciphers, including the AES finalist Serpent, ICEPOLE, COCONUT98, Chaskey, CTC2, and 8-round DES.

Several papers aimed at formalizing the DL attack, and formulating assumptions under which its complexity can be estimated accurately. These culminated in a recent work of Blondeau, Leander, and Nyberg (Journal of Cryptology, 2017) which obtained an accurate expression under the sole assumption that the two subciphers $E_0$ and $E_1$ are independent.

In this paper we show that in many cases, dependency between the two subcipher s significantly affects the complexity of the DL attack, and in particular, can be exploited by the adversary to make the attack more efficient. We present the Differential-Linear Connectivity Table (DLCT) which allows us to take into account the dependency between the two subciphers, and to choose the differential characteristic in $E_0$ and the linear approximation in $E_1$ in a way that takes advantage of this dependency. We then show that the DLCT can be constructed efficiently using the Fast Fourier Transform. Finally, we demonstrate the strength of the DLCT by using it to improve differential-linear attacks on ICEPOLE and on 8-round DES, and to explain published experimental results on Serpent and on the CAESAR finalist Ascon which did not comply with the standard differential-linear framework.

newer items   older items