IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
14 February 2022
Virtual event, Anywhere on Earth, 10 July - 16 July 2022
Event date: 10 July to 16 July 2022
Submission deadline: 1 April 2022
Notification: 15 May 2022
Submission deadline: 1 April 2022
Notification: 15 May 2022
Ikebukuro, Japan, 31 August - 2 September 2022
Event date: 31 August to 2 September 2022
Submission deadline: 26 March 2022
Notification: 30 May 2022
Submission deadline: 26 March 2022
Notification: 30 May 2022
National Research Council Canada, Ottawa, Ontario
Your Challenge
Help bring research to life and drive your career forward with the National Research Council of Canada (NRC), Canada's largest research and technology organization.
We are looking for an early-career Research Associate to support our Digital Technologies research centre (DT). The Research Associate would be someone who shares our core values of Integrity, Excellence, Respect and Creativity.
Help bring research to life and drive your career forward with the National Research Council of Canada (NRC), Canada's largest research and technology organization. Working with the NRC is an exciting opportunity to pursue a research career both independently and with a dynamic research team.
We are looking for a Research Associate to join NRC’s Digital Technologies Research Centre (NRC-DT). The Digital Technologies Research Centre collects multiple research teams who focus on machine learning, advanced analytics, computer vision, bioinformatics, cyber security, natural language processing, quantum computing and other branches of digital technologies and artificial intelligence.
The primary responsibility of the researcher in this position is to support the goals of NRC and the activities of the Digital Technologies Research Centre in conducting research of international calibre in applied quantum computing, including quantum algorithms and software, quantum error correction, theoretical models of quantum computing and other related areas. The researcher will work in a team environment with other researchers and technical experts in world-class facilities. The researcher will participate in the development and execution of an original research agenda in collaboration with NRC colleagues and with academic and commercial partners across Canada. The researcher will be called upon to contribute to collaborative research projects in support of NRC’s Applied Quantum Computing challenge program.
Closing date for applications:
Contact: Human Resources at: NRC.NRCHiring-EmbaucheCNRC.CNRC@nrc-cnrc.gc.ca
More information: https://recruitment-recrutement.nrc-cnrc.gc.ca/job-invite/15641
Nanyang Technological University, Singapore
The Cryptanalysis Taskforce at Nanyang Technological University in Singapore led by Prof. Jian Guo is seeking for candidates to fill several post-doctoral research fellow positions on symmetric-key cryptography. Topics include but are not limited to the following sub-areas:
- tool aided cryptanalysis, such as MILP, CP, STP, and SAT
- machine learning aided cryptanalysis and designs
- privacy-preserving friendly symmetric-key designs
- quantum cryptanalysis
- provable security
- cryptanalysis against SHA-2, SHA-3, and AES
- threshold cryptography
Closing date for applications:
Contact: Jian Guo, guojian@ntu.edu.sg, with subject [IACR-CATF]
More information: https://team.crypto.sg
Mohammed VI Polytechnic University, Morocco
We are looking for a Postdoc fellow in the area of security of wireless IoT networks.
The project is jointly conducted between Mohammed VI Polytechnic University, Morocco, and EPFL Switzerland.
To apply, please send your cv with your list of publications.
The project is jointly conducted between Mohammed VI Polytechnic University, Morocco, and EPFL Switzerland.
To apply, please send your cv with your list of publications.
Closing date for applications:
Contact: Mehdi Amhoud, email : elmehdi.amhoud(at)um6p.ma
Protocol Labs
About Protocol Labs
Protocol Labs drives breakthroughs in computing to push humanity forward. Protocol Labs is a product-development lab, but behind the protocols and tools we build, behind the research and implementations, are passionate people, teammates and community members. We are a fully distributed company. Our team of more than 150 members works remotely and in the open to improve the internet — humanity's most important technology — as we explore new advances at the intersection of many exciting fields (crypto, networks, distributed systems) and cultures (startups, research, open source, distributed work).
Seeking an experienced cryptographer to help us research and develop state of the art cryptosystems to upgrade the internet.
Research at Protocol Labs
This isn't an ordinary Research Scientist position. Your expertise is mostly driven by both a hunger to learn and a need to work toward solving important problems. Our research scientists are granted both the freedom to develop their knowledge by working on novel applications, and a responsibility to contribute those skills toward advancing the flagship projects of Protocol Labs. You’ll feel at home working with us if your knowledge and optimism enables you to name a few unusual possible approaches when you’re first presented with a problem that people often consider intractable.
We see cryptography often acting as the last line of defense in a world that’s rife with malicious actors. We examine a broad spectrum of potential projects, like Filecoin, that rely on providing various cryptographic guarantees to users. Achieving these guarantees in practice often requires drawing from or advancing the frontiers of cryptographic protocols. As a result, we seek cryptographers who can discover, conceive, incorporate, and implement new techniques.
Closing date for applications:
Contact: Apply here- https://boards.greenhouse.io/protocollabs/jobs/4283969004
More information: https://boards.greenhouse.io/protocollabs/jobs/4283969004
13 February 2022
The submission deadline for CRYPTO 2022 is 16 February 2022 (AoE) and the submission server is now open.
Instructions for authors and the link to submission server can be found here https://crypto.iacr.org/2022/papersubmission.php.
Instructions for authors and the link to submission server can be found here https://crypto.iacr.org/2022/papersubmission.php.
12 February 2022
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray, Daniel S. Roche
We describe a straightforward method to generate a random prime q such that the multiplicative group GF(q)* also has a random large prime-order subgroup. The described algorithm also yields this order p as well as a p'th primitive root of unity. The methods here are efficient asymptotically, but due to large constants may not be very useful in practical settings.
George-Mircea Grosu, Silvia-Elena Nistor, Emil Simion
The past couple of decades witnessed a tremendous expansion in the IoT world that gathers now billions of devices, sensors, users and transactions. The aspirations of ubiquitous computing have changed the computing world drastically, from a parallel point of view, to distributed, then grid and cloud computing – all these just to keep up with the proliferation of devices and the users’ expectations. Alongside with this fast development, many issues appeared, especially in terms of scalability and security. Regardless of protocol, device, applications or technologies used, there will be critical data involved and, therefore, vulnerabilities that can affect the performance of the system or be exploited maliciously. The higher the number of devices, the more constraints appear and along with these constraints the existing models and technologies become overwhelmed and simply not enough. The size of the IoT and its autonomous character make it impossible to sustain and implement a centralized authentication system. Therefore, to allow reliable peer authentication and to approach a trust level management, we propose discussing a model based on blockchain technology. Blockchain is a revolutionary technology, modeled by a linear sequence of blocks, considered to be the future of wireless networks security. We rely on this new data structure to address two major components of security in mobile networks: authentication and trust.
Olivier Bronchain, Gaëtan Cassiers
The performance of higher-order masked implementations of lattice-based based key encapsulation mechanisms (KEM) is currently limited by the costly conversions between arithmetic and boolean masking. While bitslicing has been shown strongly speed up to masked implementations of symmetric primitives, it has never been used in higher-order arithmetic-to-boolean and boolean-to-arithmetic masking conversion gadgets. In this paper, we first show that bitslicing can indeed accelerate existing conversion gadgets. We then optimize these gadgets, exploiting the degrees of freedom offered by bitsliced implementations. As a result, we introduce new arbitrary-order boolean masked addition, arithmetic-to-boolean and boolean-to-arithmetic masking conversion gadgets, each in two variants: modulo \(2^k\) and modulo \(p\) (for any integers \(k\) and \(p\)). Practically, our new gadgets achieve a speedup of up to 25x over the state of the art. Turning to the KEM application, we develop the first open-source embedded (Cortex-M4) implementations of Kyber768 and Saber masked at arbitrary order. The implementations based on the new bitsliced gadgets achieve a speedup of 1.8x for Kyber and 3x for Saber, compared to the implementation based on state of the art gadgets. The bottleneck of the bitslice implementations is the masked Keccak-f[1600] permutation.
Yanxue Jia, Shi-Feng Sun, Hong-Sheng Zhou, Jiajun Du, Dawu Gu
Private Set Union ($\mathsf{PSU}$) allows two players, the sender and the receiver, to compute the union of their input datasets without revealing any more information than the result. While it has found numerous applications in practice, not much research has been carried out so far, especially for large datasets.
In this work, we take shuffling technique as a key to design $\mathsf{PSU}$ protocols for the first time. By shuffling receiver's set, we put forward the first protocol, denoted as $\Pi_{\mathsf{PSU}}^{\mathsf{receiver}}$, that eliminates the expensive operations in previous works, such as additive homomorphic encryption and repeated operations on the receiver's set. It outperforms the state-of-the-art design by Kolesnikov et al. (ASIACRYPT 2019) in both efficiency and security; the unnecessary leakage in Kolesnikov et al.'s design, can be avoided in our design.
We further extend our investigation to the application scenarios in which both players may hold unbalanced input datasets. We propose our second protocol $\Pi_{\mathsf{PSU}}^{\mathsf{sender}}$, by shuffling the sender's dataset. This design can be viewed as a dual version of our first protocol, and it is suitable in the cases where the sender's input size is much smaller than the receiver's.
Finally, we implement our protocols $\Pi_{\mathsf{PSU}}^{\mathsf{receiver}}$ and $\Pi_{\mathsf{PSU}}^{\mathsf{sender}}$ in C++ on big datasets, and perform a comprehensive evaluation in terms of both scalability and parallelizability. The results demonstrate that our design can obtain a $4$-$5 \times$ improvement over the state-of-the-art by Kolesnikov et al. with a single thread in WAN/LAN settings.
In this work, we take shuffling technique as a key to design $\mathsf{PSU}$ protocols for the first time. By shuffling receiver's set, we put forward the first protocol, denoted as $\Pi_{\mathsf{PSU}}^{\mathsf{receiver}}$, that eliminates the expensive operations in previous works, such as additive homomorphic encryption and repeated operations on the receiver's set. It outperforms the state-of-the-art design by Kolesnikov et al. (ASIACRYPT 2019) in both efficiency and security; the unnecessary leakage in Kolesnikov et al.'s design, can be avoided in our design.
We further extend our investigation to the application scenarios in which both players may hold unbalanced input datasets. We propose our second protocol $\Pi_{\mathsf{PSU}}^{\mathsf{sender}}$, by shuffling the sender's dataset. This design can be viewed as a dual version of our first protocol, and it is suitable in the cases where the sender's input size is much smaller than the receiver's.
Finally, we implement our protocols $\Pi_{\mathsf{PSU}}^{\mathsf{receiver}}$ and $\Pi_{\mathsf{PSU}}^{\mathsf{sender}}$ in C++ on big datasets, and perform a comprehensive evaluation in terms of both scalability and parallelizability. The results demonstrate that our design can obtain a $4$-$5 \times$ improvement over the state-of-the-art by Kolesnikov et al. with a single thread in WAN/LAN settings.
Benjamin Chan, Cody Freitag, Rafael Pass
We define a framework for analyzing the security of cryptographic protocols that makes minimal assumptions about what a "realistic model of computation is". In particular, whereas classical models assume that the attacker is a (perhaps non-uniform) probabilistic polynomial-time algorithm, and more recent definitional approaches also consider quantum polynomial-time algorithms, we consider an approach that is more agnostic to what computational model is physically realizable.
Our notion of cosmic security considers a reduction-based notion of security that models attackers as arbitrary unbounded stateful algorithms; we also consider a more relaxed notion of cosmic security w.r.t. weakly-restartable adversaries which makes additional restrictions on the attacker’s behavior. We present both impossibility results and general feasibility results for our notions, indicating that extended Church-Turing hypotheses may not be needed for a well-founded theory of Cryptography.
Our notion of cosmic security considers a reduction-based notion of security that models attackers as arbitrary unbounded stateful algorithms; we also consider a more relaxed notion of cosmic security w.r.t. weakly-restartable adversaries which makes additional restrictions on the attacker’s behavior. We present both impossibility results and general feasibility results for our notions, indicating that extended Church-Turing hypotheses may not be needed for a well-founded theory of Cryptography.
Conor McMenamin, Vanesa Daza, Matthias Fitzi
An idealised decentralised exchange (DEX) provides a medium in which players wishing to exchange one token for another can interact with other such players and liquidity providers at a price which reflects the true exchange rate, without the need for a trusted third-party. Unfortunately, extractable value is an inherent flaw in existing blockchain-based DEX implementations. This extractable value takes the form of monetizable opportunities that allow blockchain participants to extract money from a DEX without adding demand or liquidity to the DEX, the two functions for which DEXs are intended. This money is taken directly from the intended DEX participants. As a result, the cost of participation in existing DEXs is much larger than the upfront fees required to post a transaction on a blockchain and/or into a smart contract.
We present FairTraDEX, a decentralised variant of a frequent batch auction (FBA), a DEX protocol which provides formal game-theoretic guarantees against extractable value. FBAs when run by a trusted third-party provide unique game-theoretic optimal strategies which ensure players are shown prices equal to the liquidity provider's fair price, excluding explicit, pre-determined fees. FairTraDEX replicates the key features of an FBA that provide these game-theoretic guarantees using a combination of set-membership in zero-knowledge protocols and an escrow-enforced commit-reveal protocol. We extend the results of FBAs to handle monopolistic and/or malicious liquidity providers, and provide a detailed pseudo-code implementation of FairTraDEX based on existing mainstream blockchain protocols.
Ishtiyaque Ahmad, Laboni Sarker, Divyakant Agrawal, Amr El Abbadi, Trinabh Gupta
Given a private string q and a remote server that holds a set of public documents D, how can one of the K most relevant documents to q in D be selected and viewed without anyone (not even the server) learning anything about q or the document? This is the oblivious document ranking and retrieval problem. In this paper, we describe Coeus, a system that solves this problem. At a high level, Coeus composes two cryptographic primitives: secure matrix-vector product for scoring document relevance using the widely-used term frequency-inverse document frequency (tf-idf) method, and private information retrieval (PIR) for obliviously retrieving documents. However, Coeus reduces the time to run these protocols, thereby improving the user-perceived latency, which is a key performance metric. Coeus first reduces the PIR overhead by separating out private metadata retrieval from document retrieval, and it then scales secure matrix-vector product to tf-idf matrices with several hundred billion elements through a series of novel cryptographic refinements. For a corpus of English Wikipedia containing 5 million documents, a keyword dictionary with 64K keywords, and on a cluster of 143 machines on AWS, Coeus enables a user to obliviously rank and retrieve a document in 3.9 seconds---a 24x improvement over a baseline system.
Gora Adj, Jesús-Javier Chi-Domínguez, Víctor Mateu, Francisco Rodríguez-Henríquez
In SIDH and SIKE protocols, public keys are defined over quadratic extensions of prime fields.
We present in this work a projective invariant property characterizing affine Montgomery curves defined over prime fields.
We then force a secret 3-isogeny chain to repeatedly pass through a curve defined over a prime field in order to exploit the new property and inject zeros in the A-coefficient of an intermediate curve to successfully recover the isogeny chain one step at a time.
Our results introduce a new kind of fault attacks applicable to SIDH and SIKE.
Minjoo Sim, Siwoo Eum, Gyeongju Song, HyeokDong Kwon, Kyungbae Jang, HyunJun Kim, HyunJi Kim, Yujin Yang, Wonwoong Kim, Wai-Kong Lee, Hwajeong Seo
Hash-Based Signature (HBS) uses a hash function to construct a digital signature scheme, where its security is guaranteed by the collision resistance of the hash function used. To provide sufficient security in the post-quantum environment, the length of hash should be satisfied. Modern HBS can be classified into stateful and stateless schemes. Two representative stateful and stateless HBS are XMSS and SPHINCS$^+$, respectively. In this paper, we propose two HBS schemes: K-XMSS and
K-SPHINCS$^+$, which replace internal hash functions of XMSS and SPHINCS$^+$ with Korean cryptography algorithms. K-XMSS is a stateful signature, while K-SPHINCS$^+$ is its stateless counterpart. We also showcase the reference implementation of K-XMSS and K-SPHINCS$^+$ employing LSH and two hash functions based on block ciphers (i.e. CHAM and LEA) as the internal hash function. The reference code is developed as a proof-of-concept, which can be optimized for better performance using advanced implementation techniques (e.g. AVX2 and NEON).
Ling Sun, Wei Wang, Meiqin Wang
In ToSC 2021(2), Sun et al. implemented an automatic search with the Boolean satisfiability problem (SAT) method on GIFT-128 and identified a 19-round linear approximation with the expected linear potential being $2^{-117.43}$, which is utilised to launch a 24-round attack on the cipher. In this addendum, we discover a new 19-round linear approximation with a lower expected linear potential. However, in the attack, one more round can be appended after the distinguisher. As a result, we improve the previous optimal linear attack by one round and put forward a 25-round linear attack. Given that the optimal differential attack on GIFT-128, for now, covers 27-round, the resistances of the cipher against differential and linear attacks still have a 2-round gap.
Tomoki Moriya, Hiroshi Onuki, Yusuke Aikawa, Tsuyoshi Takagi
Isogeny-based cryptography is one of the main candidates of post-quantum cryptography. To realize efficient computations, one usually uses formulas of scalar multiplications and isogeny computations on elliptic curves using only one coordinate in isogeny-based cryptography. The $x$-coordinate of Montgomery curves is the most standard, and we sometimes use the $x$-coordinate of Montgomery$^-$ curves, the $w$-coordinate of Edwards curves, and the $w$-coordinate of Huff's curves.
In this paper, we define a novel function on elliptic curves called the generalized Montgomery coordinate that has the four coordinates described above as special cases. For a generalized Montgomery coordinate, we construct an explicit formula of scalar multiplication which includes the division polynomial, and both a formula of an image point under an isogeny and that of a coefficient of the codomain curve.
Finally, we expect numerous applications for the generalized Montgomery coefficient. As an experimental study, we present two applications of the theory of a generalized Montgomery coordinate. The first one is to construct a new efficient formula to compute isogenies on Montgomery curves. This formula is more efficient than the previous one for high degree isogenies as the $\sqrt{\vphantom{2}}$\'{e}lu's formula in our implementation. The second one is to construct a new generalized Montgomery coordinate for Montgomery$^-$ curves used for CSURF.
In this paper, we define a novel function on elliptic curves called the generalized Montgomery coordinate that has the four coordinates described above as special cases. For a generalized Montgomery coordinate, we construct an explicit formula of scalar multiplication which includes the division polynomial, and both a formula of an image point under an isogeny and that of a coefficient of the codomain curve.
Finally, we expect numerous applications for the generalized Montgomery coefficient. As an experimental study, we present two applications of the theory of a generalized Montgomery coordinate. The first one is to construct a new efficient formula to compute isogenies on Montgomery curves. This formula is more efficient than the previous one for high degree isogenies as the $\sqrt{\vphantom{2}}$\'{e}lu's formula in our implementation. The second one is to construct a new generalized Montgomery coordinate for Montgomery$^-$ curves used for CSURF.
Pierre-Emmanuel Clet, Martin Zuber, Aymen Boudguiga, Renaud Sirdey, Cédric Gouy-Pailler
In this work, we first propose a new functional bootstrapping with TFHE for evaluating any function of domain and codomain the real torus T by using a small number of bootstrappings. This result improves some aspects of previous approaches: like them, we allow for evaluating any functions, but with better precision. In addition, we develop more efficient multiplication and addition over ciphertexts building on the digit-decomposition approach. As a practical application, our results lead to an efficient implementation of ReLU, one of the most used activation functions in deep learning. The paper is concluded by extensive experimental results comparing each building block as well as their practical relevance and trade-offs.
Thomas Johansson, Willi Meier, Vu Nguyen
Firekite is a synchronous stream cipher using a pseudo-random number generator (PRNG) whose security relies on the hardness of the \textit{Learning Parity with Noise} (LPN) problem. It is one of a few LPN-based symmetric encryption schemes and it can be very efficiently implemented on a low-end SoC FPGA. The designers, Bogos, Korolija, Locher, and Vaudenay, demonstrated appealing properties of Firekite such as requiring only one source of cryptographically strong bits, small key size, high attainable throughput, and a concrete measurement for the bit level security depending on the selected practical parameters.
We propose distinguishing and key-recovery attacks on Firekite by exploiting the structural properties of its PRNG. We adopt several \textit{birthday-paradox} techniques to show that a particular sum of Firekite's output has a low Hamming weight with higher probability than the random case. We achieve the best distinguishing attacks with complexities $2^{66.75}$ and $2^{106.75}$ for Firekite's parameters corresponding to $80$-bit and $128$-bit security, respectively.
By applying the distinguishing attacks and an additionally suggested algorithm, one can also recover the secret matrix used in the Firekite PRNG, which is built from the secret key bits. This key recovery attack works on most large parameter sets and has slightly larger complexity, for example $2^{69.87}$ on the $80$-bit security parameters $n=16384, m = 216, k = 216$.