International Association
for Cryptologic Research

In 1985, Dolev and Reischuk proved a fundamental communication lower bounds on protocols achieving fault tolerant synchronous broadcast and consensus: any deterministic protocol solving those tasks requires at least a quadratic number of message to be sent by nonfaulty parties. Followup work by Abraham, Chun, Dolev, Nayak, Pass, Ren and Shi shows a similar lower bound for randomized protocols. With the rise of blockchain systems, there have been many real-world systems that achieve consensus with seemingly linear communication per instance. We bridge this discrepancy in two ways. First, we generalize the lower bound to Crusader Broadcast protocols, and to all-but $m$ Crusader Broadcast. Second, we discuss the ways these lower bounds relate to the security of blockchain systems. Specifically, we show how eclipse style attacks in such systems can be viewed as specific instances of Dolev-Reischuk style attacks. Our observation suggests a more systematic way of analyzing and thinking about eclipse style attacks through the lens of the Dolev-Reischuk family of attacks. Finally, we present an example of a simple subquadratic Crusader Broadcast protocol whose security is highly dependent on insights from the presented lower bounds.

WARP is a 128-bit block cipher published by Banik et al. at SAC 2020 as a lightweight alternative to AES. It is based on a generalized Feistel network and achieves the smallest area footprint among 128-bit block ciphers in many settings. Previous analysis results include integral key-recovery attacks on 21 out of 41 rounds.

In this paper, we propose integral key-recovery attacks on up to 32 rounds by improving both the integral distinguisher and the key-recovery approach substantially. For the distinguisher, we show how to model the monomial prediction technique proposed by Hu et al. at ASIACRYPT 2020 as a SAT problem and thus create a bit-oriented model of WARP taking the key schedule into account. Together with two additional observations on the properties of WARP's construction, we extend the best previous distinguisher by 2 rounds (as a classical integral distinguisher) or 4 rounds (for a generalized integral distinguisher). For the key recovery, we create a graph-based model of the round function and demonstrate how to manipulate the graph to obtain a cipher representation amenable to FFT-based key recovery.

The performance of Side-Channel Attacks (SCAs) decays rapidly when considering more sub-keys, making the full-key recovery a very challenging problem. Limited to independent collision information utilization, collision attacks establish the relationship among sub-keys but do not significantly slow down this trend. To solve it, we first exploit the samples from the previously attacked S-boxes to assist attacks on the targeted S-box under an assumption that similar leakage occurs in program loop or code reuse scenarios. The later considered S-boxes are easier to be recovered since more samples participate in this assist attack, which results in the ``snowball'' effect. We name this scheme as Snowball, which significantly slows down the attenuation rate of attack performance. We further introduce confusion coefficient into the collision attack to construct collision confusion coefficient, and deduce its relationship with correlation coefficient. Based on this relationship, we give two optimizations on our Snowball exploiting the ``values'' information and ``rankings'' information of collision correlation coefficients named Least Deviation from Pearson correlation coefficient (PLD) and Least Deviation from confusion coefficient (CLD). Experiments show that the above optimizations significantly improve the performance of our Snowball.

Regev's Learning with Errors (LWE) problem (STOC 2005) is a fundamental hardness assumption for modern cryptography. The Learning with Rounding (LWR) Problem was put forth by Banarjee, Peikert and Rosen (Eurocrypt 2012) as an alternative to LWE, for use in cryptographic situations which require determinism. The only method we currently have for proving hardness of LWR is the so-called "rounding reduction" which is a specific reduction from an analogous LWE problem. This reduction works whenever the LWE error is small relative to the noise introduced by rounding, but it fails otherwise. For this reason, all prior work on establishing hardness of LWR forces the LWE error to be small, either by setting other parameters extremely large (which hurts performance), or by limiting the number of LWR samples seen by the adversary (which rules out certain applications). Hardness of LWR is poorly understood when the LWE modulus ($q$) is polynomial and when the number of LWE samples ($m$) seen by the adversary is an unbounded polynomial. This range of parameters is the most relevant for practical implementations, so the lack of a hardness proof in this situation is not ideal.

In this work, we identify an obstacle for proving the hardness of LWR via a reduction from LWE in the above parameter regime. Specifically, we show that any "point-wise" reduction from LWE to LWR can be used to directly break the corresponding LWE problem. A reduction is "point-wise" if it maps LWE samples to LWR samples one at a time. Our argument goes roughly as follows: first we show that any point-wise reduction from LWE to LWR must have good agreement with some affine map; then we use a Goldreich-Levin-type theorem to extract the LWE secret given oracle access to a point-wise reduction with good affine agreement. Both components may be of independent interest.

The lattice-based cryptography is considered a strong candidate amongst many other proposed quantum-safe schemes for the currently deployed asymmetric cryptosystems that do not seem to stay secure when quantum computers come into play. Lattice-based algorithms possess a time-consuming operation of polynomial multiplication. As it is relatively the highest time-consuming operation in lattice-based cryptosystems, one can obtain fast polynomial multiplication by using number theoretic transform (NTT). In this paper, we focus on and develop a radix-3 NTT polynomial multiplication and compute its computational complexity. In addition, utilizing the ring structure, we propose two parameter sets of CRYSTALS-KYBER, one of the four round-three finalists in the NIST Post-Quantum Competition.

In recent years, several MILP models were introduced to search automatically for boomerang distinguishers and boomerang attacks on block ciphers. However, they can only be used when the key schedule is linear. Here, a new model is introduced to deal with nonlinear key schedules as it is the case for AES. This model is more complex and actually it is too slow for exhaustive search. However, when some hints are added to the solver, it found the current best related-key boomerang attack on AES 192 with $2^{136.4}$ time, $2^{126.2}$ data, and $2^{94.4}$ memory complexities, which is better than the one presented by Biryukov and Khovratovich at ASIACRYPT 2009 with complexities $2^{176}/2^{123}/2^{152}$ respectively. This represents a huge improvement for the time and memory complexity, illustrating the power of MILP in cryptanalysis.

The code-based post-quantum algorithm Hamming Quasi-Cyclic (HQC) is a third round alternative candidate in the NIST standardization project. For their third round version the authors utilize a new combination of error correcting codes, namely a combination of a Reed-Muller and a Reed-Solomon code, which requires an adaption of published attacks. We identify that the power side-channel attack by Uneo et al. from CHES 2021 does not work in practice as they miss the fact that the implemented Reed-Muller decoder does not have a fixed decoding boundary. In this work we provide a novel attack strategy that again allows for a successful attack. Our attack does not rely on simulation to verify it success but is proven with high probability for the HQC parameter sets. In contrast to the timing side-channel attack by Guo et al. we are able to reduce the required attack queries by a factor of 12 and are able to eliminate the inherent uncertainty of their used timing oracle. We show practical attack results utilizing a power side-channel of the used Reed-Solomon decoder on an ARM Cortex-M4 microcontroller. In addition, we provide a discussion on how or whether our attack strategy to be usable with the side-channel targets of mentioned related work. Finally, we use information set decoding to evaluate the remaining attack complexity for partially retrieved secret keys. This work again emphasizes the need for a side-channel secure implementation of all relevant building blocks of HQC.

Technology Innovation Institute (TII) is a publicly funded research institute, based in Abu Dhabi, United Arab Emirates. It is home to a diverse community of leading scientists, engineers, mathematicians, and researchers from across the globe, transforming problems and roadblocks into pioneering research and technology prototypes that help move society ahead.

Cryptography Research Center

In our connected digital world, secure and reliable cryptography is the foundation of digital information security and data integrity. We address the world’s most pressing cryptographic questions. Our work covers post-quantum cryptography, lightweight cryptography, cloud encryption schemes, secure protocols, quantum cryptographic technologies and cryptanalysis.

Position: Post Quantum Cryptography Expert

Study and design post quantum primitives such as PKE, KEM, KEX, and Digital Signatures

Conduct research, with particular focus on how to improve or attack existing proposals

Design new and/or more efficient post quantum Zero Knowledge Proofs

Collaboration and possible participation in NIST proposals

Design and implementation of hybrid (post quantum – classical) solutions

We welcome candidates specializing in lattices and codes. Exceptional candidates with expertise in other areas of PQC are also encouraged

Collaborate with skillful software, hardware, and telecommunication engineers

Attend personalized in-house trainings with top cryptographers and international conferences and workshops

Skills required for the job

A strong publication record in post quantum cryptography

Extensive knowledge on post quantum cryptography

Extensive experience in secure software development

Extensive experience developing in C, C++, or RUST

Willingness to continue learning and push the limits of knowledge

Qualifications

PhD degree in Cryptography, Applied Cryptography, Information Theory and Mathematics, Computer Science or any relevant Engineering degree

Closing date for applications:

Contact:
Mehdi Messaoudi - Talent Acquisition Manager
mehdi.messaoudi@tii.ae

The School of Electrical & Data Engineering is recruiting for two Postdoctoral Research Associates or Postdoctoral Research Fellows to join a multi-disciplinary collaborative research team comprising industry (Bosch) and UTS academics, postdocs and PhD students working on Privacy Preserving Technologies. The position will be based at the centrally located UTS Campus in Ultimo and will report directly to the Director RF Communications Technologies Lab, Associate Professor Justin Lipman

The School of Electrical & Data Engineering is deeply engaged in research of national and international standing in many areas. Key areas include: wireless communications and networking, Internet of Things (IoT), applied electro-magnetics and antennas, electrical systems and power electronics, image processing, computer vision, machine learning, cybersecurity, big data analytics and big data systems, and RF IC design. Our School hosts three IEEE Fellows and 3 ARC DECRA grant holders and we conduct research funded by government agencies and national and international industry partners.

About the role
Conduct research in:
1) Computing on encrypted data technologies in the context of privacy-preserving Federated Learning in particular secure multi-party computation and homomorphic encryption
2) Design and development of trustworthy digital cleanrooms/marketplaces using privacy-preserving computing technologies

About you
• Computer Science or Engineering PhD in cryptographic communication protocols or secure multi-party computation or federated learning.
• Thorough knowledge of the mathematical and statistical foundations of cryptographic systems.
• Proficient in one or more of the following: Rust, Go, C++, C, Python, Java.
• Demonstrated record of research in cryptographic communication protocols or secure multi-party computation.

Closing date for applications:

Contact: A/Prof Justin Lipman
email: justin.lipman@uts.edu.au

More information: https://www.seek.com.au/job/57060632

A candidate will work in the area of post-quantum cryptography. A candidate will conduct research on post-quantum cryptography in term of design and analysis; the emphasis is on quantum analysis. The work requires to carry out some simulations. Applicants are expected to have a PhD degree in Mathematics/Physics/Computer Science and a strong background in quantum algorithm, algebra, linear algebra or algebraic number theory. Preferred candidates are expected to be proficient in Magma software or SAGEMATH software or knowledge on quantum software (eg. Qiskit, etc), a team worker and able to conduct independent research. Interested candidates will kindly include their full CV and transcripts in their applications and send to Dr Chik How Tan, tsltch@nus.edu.sg. Only shortlisted applications will be notified.

Closing date for applications:

Contact: Dr Chik How Tan, tsltch@nus.edu.sg

The rectangle attack has shown to be a very powerful form of cryptanalysis against block ciphers. Given a rectangle distinguisher, one expects to mount key recovery attacks as efficiently as possible. In the literature, there have been four algorithms for rectangle key recovery attacks. However, their performance vary from case to case. Besides, numerous are the applications where the attacks lack optimality. In this paper, we investigate the rectangle key recovery in depth and propose a unified and generic key recovery algorithm, which supports any possible attacking parameters. Notably, it not only covers the four previous rectangle key recovery algorithms, but also unveils five types of new attacks which were missed previously. Along with the new key recovery algorithm, we propose a framework for automatically finding the best attacking parameters, with which the time complexity of the rectangle attack will be minimized using the new algorithm. To demonstrate the efficiency of the new key recovery algorithm, we apply it to Serpent, CRAFT, SKINNY and Deoxys-BC-256 based on existing distinguishers and obtain a series of improved rectangle attacks.

Introducing small errors in the lattice-based key exchange protocols, although it is resistant to quantum computing attacks, will cause both parties to only get roughly equal secret values, which brings uncertainty to the negotiation of the key agreement. The role of the error reconciliation mechanism is to eliminate this uncertainty and ensure that both parties can reach a consensus. This paper designs a new error reconciliation mechanism: Speedy Error Reconciliation (SER), which can efficiently complete key negotiation while ensuring key correctness and security. SER exploits the properties of the approximate secret values σ1 and σ2 shared by the two parties, and simultaneously reconciles the most and least significant bits of the secret value, and a two-bit key can be obtained by one coordination. By sharing g-bit auxiliary information between two entities, SER expands the fault tolerance interval during reconciliation and improves the success rate of consensus. To test the actual performance of SER, we integrate it into key ex- change protocols based on LWE, RLWE, and MLWE, such as Frodo and NewHope. By comparing parameters such as failure rate, security strength, and the number of CPU rounds, we find that SER performs well in various modes, especially in RLWE-based protocol. Since SER doubles the error to reconcile the least significant bit, which in turn leads to a relatively large error in SER; while the RLWE-based key ex- change scheme adopts a polynomial ring and selects a large parameter q, which is very suitable for SER. Compared with Frodo and NewHope, SER improves the reconciliation efficiency of the per-bit key by 61.6% and 797.6%, respectively.

Today, our society produces massive amounts of data, part of which are strictly private. So, a long line of research has worked to design protocols that perform functions on such private data without revealing them. One function that has attracted significant interest is a multi-party private set operation, where each party's input is a set. The parties commonly intend to compute these sets' collective intersection (MPSI) or union (MPSU), which finds uses in various applications, including private scheduling and threat intelligence. Most current protocols use integer-based homomorphic encryption, with large elements and expensive operations, or oblivious transfers, which require communicationally-expensive pairwise interactions between all parties. Thus, existing solutions introduce significant overhead that hinders practical use. This paper considers a certain class of previously-proposed MPSI and MPSU protocols. We propose to express them in terms of new private AND or OR operations among all parties and use elliptic curves to realize these operations efficiently. We achieve a significant performance gain: Firstly, our protocols take only three rounds of communication. Secondly, our constant-time open-source implementation is two orders of magnitude faster than the state-of-the-art MPSI for small universes and outperforms the state-of-the-art MPSI for large universes for three parties or more.

Division property is a generalized integral property proposed by Todo at EUROCRYPT 2015. Subsequently, Todo and Morii extended division property to the bit level and proposed conventional bit-based division property (CBDP) and bit-based division property using three subsets (BDPT). At ASIACRYPT 2016, Xiang et al. applied MILP technique to model the CBDP propagation for the first time. To construct an automatic search model for BDPT propagation, Hu et al. characterized a variant BDPT based on SMT/SAT. Later at ASIACRYPT 2019, Wang et al. characterized the BDPT based MILP. However, the above two automatic search models have some limitations.

In this paper, we focus on constructing an automatic search model that can more accurately characterize the BDPT propagation. Firstly, we define a new notion named BDPT Trail, which divides the BDPT propagation into three parts: the division trail K, division trail L, and Key-Xor operation. Secondly, we improve the insufficiency of the previous methods of calculating division trails and propose an effective algorithm that can obtain more valid division trails L of the S-box operation. Thirdly, we propose a new algorithm that models each Key-Xor operation based on MILP technique for the first time. Based on this, we can accurately characterize the Key-Xor operation by solving these MILP models. After that, by selecting appropriate initial BDPT and stopping rules, we construct an automatic search model that more accurately characterizes the BDPT propagation. As a result, our automatic search model is applied to search integral distinguishers for some block ciphers. For Rectangle, we find a 10-round integral distinguisher which is one more round than the previous best results. For Simon64, we can find more balanced bits than the previous longest distinguishers. For Present, we find a better 9-round integral distinguisher with less active bits.

The fair exchange problem has faced for a long time the bottleneck of a required trusted third party. The recent development of blockchains introduces a new type of party to this problem, whose trustworthiness relies on a public ledger and distributed computation. The challenge in this setting is to reconcile the minimalistic and public nature of blockchains with elaborate fair exchange requirements, from functionality to privacy. Zero-knowledge contingent payments (ZKCP) are a class of protocols that are promising in this direction, allowing the fair exchange of data for payment. We propose a new ZKCP protocol that, when compared to others, requires less computation from the blockchain and less interaction between parties. The protocol is based on two-party (weak) adaptor signatures, which we show how to instantiate from state of the art multiparty signing protocols. We improve the symbolic definition of ZKCP security and, for automated verification with Tamarin, we propose a general security reduction from the theory of abelian groups to the theory of exclusive or.

In this paper, for the first time, we consider a four-party scenario, where a \textit{customer} holding a smart card wants to authenticate herself to a \textit{server}, which employs a \textit{cloud database} to verify the customer. The customers initially register with the \textit{manager}. The manager outsources the processed registration data to a cloud database. Then, the customer only interacts with the server for authentication purposes. The server employs the help of the cloud database during authentication. In addition to the security of the authentication, privacy is another goal, where the cloud should not learn which customer is interacting with which server. We consider several different threat models and provide secure and efficient generic solutions as well as a post-quantum secure solution.

A Hash Time Lock Contract (HTLC) is a protocol that is commonly used to exchange payments across different blockchains. Using HTLC as a building block for cross blockchain atomic swaps has its drawbacks: The notion of time is handled differently in each blockchain, be it private or public. Additionally, if the swap ends up aborted, the funds are locked in escrow until the safety timeout expires.

In this work we formulate a new cryptographic primitive: Attribute Verifiable Timed Commitment which enables to prove that a timed commitment commits to a value which possesses certain attributes. Using our cryptographic primitive, we describe a new cross chain atomic swap protocol that operates without blockchain derived time and unlike the state of the art, all parties can instantly abort the swap without waiting for the safety timeouts to expire.

In order to prove in zero knowledge that a secret committed to using a timed commitment has a claimed hash value, we employ the "MPC in the head" technique by Ishai et al. and implement our zero-knowledge proof protocol and evaluate its performance. As part of our techniques, we develop a novel and efficient procedure for integer Lower-Than validation in arithmetic circuits which may be of independent interest.

The choice of the elliptic curve for a given pairing based protocol is primordial. For many cryptosystems based on pairings such as group signatures and their variants (EPID, anonymous attestation, etc) or accumulators, operations in the first pairing group $\mathbb{G}$ of points of the elliptic curve is more predominant. At $128$-bit security level two curves $BW13-P310$ and $BW19-P286$ with odd embedding degrees $13$ and $19$ suitable for super optimal pairing have been recommended for such pairing based protocols . But a prime embedding degree ($k=13;19$) eliminates some important optimisation for the pairing computation. However The Miller loop length of the superoptimal pairing is the half of that of the optimal ate pairing but involve more exponentiations that affect its efficiency. In this work, we successfully develop methods and construct algorithms to efficiently evaluate and avoid heavy exponentiations that affect the efficiency of the superoptimal pairing. This leads to the definition of new bilinear and non degenerate pairing on $BW13-P310$ and $BW19-P286$ called $x$-superoptimal pairing wchich is about $27.3\%$ and $49\%$ faster than the optimal ate pairing previousely computed on $BW13-P310$ and $BW19-P286$ respectively.

In this paper we revisit the Spectre v1 vulnerability and software-only countermeasures. Specifically, we systematically investigate the performance penalty and security properties of multiple variants of speculative load hardening (SLH). As part of this investigation we implement the “strong SLH” variant by Patrignani and Guarnieri (CCS 2021) as a compiler extension to LLVM. We show that none of the existing variants, including strong SLH, is able to protect against all Spectre v1 attacks in practice. We do this by demonstrating, for the first time, that variable-time arithmetic instructions leak secret information even if they are executed only speculatively. We extend strong SLH to include protections also against this kind of leakage, implement the resulting full protection in LLVM, and use the SPEC2017 benchmarks to compare its performance to the existing variants of SLH and to code that uses fencing instructions to completely prevent speculative execution. We show that our proposed countermeasure is able to offer full protection against Spectre v1 attacks at much better performance than code using fences. In fact, for several benchmarks our approach is more than twice as fast.

Secure aggregation on user private data with the aid of an entrusted server provides strong privacy guarantees and has been well-studied in the context of privacy-preserving federated learning. An important problem in privacy-preserving federated learning with user constrained computation and wireless network resources is the computation and communication overhead which wastes bandwidth, increases training time, and can even impacts the model accuracy if many users drop out. The seminal work of Bonawitz et al. and the work of Bell et al. have constructed secure aggregation protocols for a very large number of users which handle dropout users in a federated learning setting. However, these works suffer from high round complexity (referred to as the number of times the users exchange messages with the server) and overhead in every training iteration. In this work, we propose and implement MicroFedML, a new secure aggregation system with lower round complexity and computation overhead per training iteration. MicroFedML reduces the computational burden by at least 100 orders of magnitude for 500 users (or more depending on the number of users) and the message size by 50 times compared to prior work. Our system is suitable and performs its best when the input domain is not too large, i.e., small model weights. Notable examples include gradient sparsification, quantization, and weight regularization in federated learning.