IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
01 March 2024
Dipayan Das, Antoine Joux
In this paper, we propose an alternative attack on the PV Knapsack problem, which provides key recovery for a much larger set of keys. Like the Crypto'22 attack, it is based on lattice reduction and uses a dimension reduction technique to speed-up the underlying lattice reduction algorithm and enhance its performance. As a side bonus, our attack transforms the PV Knapsack problem into uSVP instances instead of SVP instances in the Crypto'22 attack. This also helps the lattice reduction algorithm, both from a theoretical and practical point of view.
We use our attack to re-assess the hardness of the concrete parameters used in the literature. It appears that many contain a non-negligible fraction of weak keys, which are easily identified and extremely susceptible to our attack. For example, a fraction of $2^{-19}$ of the public keys of a parameter set from ACISP'18 can be solved in about $30$ hours on a moderate server using off-the-shelf lattice reduction. This parameter set was initially claimed to have a $129$-bit security against key recovery attack. Its security was reduced to $87$-bit security using the distinguishing attack from Crypto'22. Similarly, the ACNS'14 proposal also includes a parameter set containing a fraction of $2^{-19}$ of weak keys; those can be solved in about $17$ hours.
Jakob Feldtkeller, Jan Richter-Brockmann, Pascal Sasdrich, Tim Güneysu
In this work, we propose a new methodology to generate combined-secure circuits. We show how to transform TI-like constructions to resist any adversary with the capability to tamper with internal gates and probe internal wires. For the resulting protection scheme, we can prove the combined security in a well-established theoretical security model.
Since the transformation preserves the advantages of TI-like structures, the resulting circuits prove to be more efficient in the number of required bits of randomness (up to 100%), the latency in clock cycles (up to 40%), and even the area for pipelined designs (up to 40%) than the state of the art for an adversary restricted to manipulating a single gate and probing a single wire.
Lars Ran, Simona Samardjiska, Monika Trimoska
ATFE is a hard equivalence problem known to be in the class of equivalence problems that includes, for instance, the Tensor Isomorphism (TI), Quadratic Maps Linear Equivalence (QMLE) and the Matrix Code Equivalence (MCE) problems. Due to the increased cryptographic interest, the understanding of its practical hardness has also increased in the last couple of years. Currently, there are several combinatorial and algebraic algorithms for solving it, the best of which is a graph-theoretic algorithm that also includes an algebraic subroutine.
In this paper, we take a purely algebraic approach to the ATFE problem, but we use a coding theory perspective to model the problem. This modelling was introduced earlier for the MCE problem. Using it, we improve the cost of algebraic attacks against ATFE compared to previously known ones.
Taking into account the algebraic structure of alternating trilinear forms, we show that the obtained system has less variables but also less equations than for MCE and gives rise to structural degree-3 syzygies. Under the assumption that outside of these syzygies the system behaves semi-regularly, we provide a concrete, non-asymptotic complexity estimate of the performance of our algebraic attack. Our results show that the complexity of our attack is below the estimated security levels of ALTEQ by more than 20 bits for NIST level I (and more for the others), thus the scheme requires re-parametrization for all three NIST security levels.
Roozbeh Sarenche, Ren Zhang, Svetla Nikova, Bart Preneel
Shan Chen, Marc Fischlin
Until now, for messaging channels (where conversations take place), both the proper causality model and the provably secure constructions have been left open. Our work fills this gap, with the goal to facilitate the formal understanding of causality preservation in messaging.
First, we focus on the common two-user secure messaging channels and model the desired causality preservation property. We take the popular Signal protocol as an example and analyze the causality security of its cryptographic core (the double-ratchet mechanism). We show its inadequacy with a simple causality attack, then fix it such that the resulting Signal channel is causality-preserving, even in a strong sense that guarantees post-compromise security. Our fix is actually generic: it can be applied to any bidirectional channel to gain strong causality security.
Then, we model causality security for the so-called message franking channels. Such a channel additionally enables end users to report individual abusive messages to a server (e.g., the service provider), where this server relays the end-to-end-encrypted communication between users. Causality security in this setting further allows the server to retrieve the necessary causal dependencies of each reported message, essentially extending isolated reported messages to message flows. This has great security merit for dispute resolution, because a benign message may be deemed abusive when isolated from the context. As an example, we apply our model to analyze Facebook’s message franking scheme. We show that a malicious user can easily trick Facebook (i.e., the server) to accuse an innocent user. Then we fix this issue by amending the underlying message franking channel to preserve the desired causality.
Jiaxin Pan, Doreen Riepel, Runzhi Zeng
Inspired by GGJJ, we propose a new notion, called one-way verifiable weak forward secrecy (OW-VwFS), and prove that OW-VwFS can be transformed tightly to FS using key confirmation in the random oracle model (ROM). To implement our generic transformation, we show that several tightly wFS AKE protocols additionally satisfy our OW-VwFS notion tightly. We highlight that using the recent lattice-based protocol from Pan, Wagner, and Zeng (CRYPTO 2023) can give us the first lattice-based tightly FS AKE via key confirmation in the classical random oracle model. Besides this, we also obtain a Decisional-Diffie-Hellman-based protocol that is considerably more efficient than the previous ones.
Finally, we lift our study on FS via key confirmation to the quantum random oracle model (QROM). While our security reduction is overall non-tight, it matches the best existing bound for wFS in the QROM (Pan, Wagner, and Zeng, ASIACRYPT 2023), namely, it is square-root- and session-tight. Our analysis is in the multi-challenge setting, and it is more realistic than the single-challenge setting as in Pan et al..
Yassine Hamoudi, Qipeng Liu, Makrand Sinha
This paper explores the implications of quantum attacks in the Noisy-Intermediate Scale Quantum (NISQ) era. In this work, we investigate three different models for NISQ algorithms and achieve tight bounds for all of them: (1) A hybrid algorithm making adaptive quantum or classical queries but with a limited quantum query budget, or (2) A quantum algorithm with access to a noisy oracle, subject to a dephasing or depolarizing channel, or (3) A hybrid algorithm with an upper bound on its maximum quantum depth; i.e., a classical algorithm aided by low-depth quantum circuits.
In fact, our results handle all regimes between NISQ and full-scale quantum computers. Previously, only results for the pre-image search problem were known for these models by Sun and Zheng, Rosmanis, Chen, Cotler, Huang and Li while nothing was known about the collision finding problem.
Along with our main results, we develop an information-theoretic framework for recording query transcripts of quantum-classical algorithms. The main feature of this framework is that it allows us to record queries in two incompatible bases - classical queries in the standard basis and quantum queries in the Fourier basis - consistently. We call the framework the hybrid compressed oracle as it naturally interpolates between the classical way of recording queries and the compressed oracle framework of Zhandry for recording quantum queries.
Caicai Chen, Chris Jones
Qi Feng, Kang Yang, Kaiyi Zhang, Xiao Wang, Yu Yu, Xiang Xie, Debiao He
We present the notion of information-theoretic message authenticated codes (IT-MACs) over groups in the multi-verifier setting, and adopt the recent pseudorandom correlation function (PCF) to generate IT-MACs statelessly and deterministically. Furthermore, we generalize the two-party IT-MACs-based ZK protocol by Baum et al. (Crypto'21) into the multi-verifier setting, which may be of independent interest. Together with multi-verifier extended doubly-authenticated bits (mv-edabits) with errors, we design a multi-verifier zero-knowledge (MVZK) protocol to derive nonces statelessly and deterministically. Building upon the MVZK protocol, we propose a stateless deterministic multi-party EdDSA signature, tolerating all-but-one malicious corruptions. Compared to the state-of-the-art multi-party EdDSA signature by Garillot et al. (Crypto'21), we improve communication cost by a factor of $61\times$, at the cost of increasing computation cost by about $2.25\times$ and requiring three extra rounds.
Douglas Stebila
Kai-Min Chung, Eli Goldin, Matthew Gray
Pratish Datta, Jiaxin Guan, Alexis Korb, Amit Sahai
Lev Soukhanov
We explain the general principle (which can be applied to both Protostar and Hypernova), and describe the Wrongfield ARithmetic for Protostar folding in details.
Our construction supports circuits over mutilple non-native fields simultaneously and allows interfacing between them using range-checked elements.
WARPfold can be used to warp between different proof systems and construct folding schemes over curves not admitting a dual partner (such as BLS12-381).
Felicitas Hörmann, Wessel van Woerden
Xiaoyang Dong, Jian Guo, Shun Li, Phuong Pham, Tianyu Zhang
Zahra Ahmadian, Akram Khalesi, Dounia M'foukh, Hossein Moghimi, María Naya-Plasencia
29 February 2024
Institute of Software Chinese Academy of Sciences
Candidates should have a Ph.D. in a related field and proven expertise in areas like lattice-based, multivariable polynomial-based, hash-based, code-based, or isogeny-based cryptography. A strong publication record and the ability to work collaboratively are essential. Excellent programming skills and knowledge of provable security theories are preferred.
Responsibilities include conducting high-level research, publishing findings, collaborating with team members, and participating in academic and industry events. The positions offer an annual pre-tax salary of 500,000 to 700,000 CNY (approx. 80,000 to 100,000 USD) and are based in Beijing. English proficiency is required; Chinese is not.
Applicants should send a CV with publications, a research statement, and at least two recommendation letters. Apply by July 30, 2024, for full consideration. This opportunity allows you to contribute to the advancement of cryptography at a leading Chinese research institution.
Closing date for applications:
Contact: Dr. Long Chen (Email:chenlong@iscas.ac.cn)
More information: https://people.ucas.ac.cn/~zfzhang
University of Wollongong, Australia
Closing date for applications:
Contact: Steven Duong
University of Versailles St-Quentin-en-Yvelines, France
A tenured Professor faculty position (“Professeur des universités”) is open to highly qualified candidates who are committed to a career in research and teaching. Preference will be given to candidates with very strong research achievements in one or several of the areas related to the general fields of cryptology and information security.
Responsibilities include research leadership and dissemination, supervision of doctoral students, development of national or international research projects, and strong commitment to teaching at undergraduate or graduate level.
IMPORTANT NOTE: Except for candidates who are currently “Maître de conférences” in France and hold an HDR diploma (“Habilitation à diriger des recherches”), a “Qualification aux fonctions de professeur des universités” certificate from the french “Conseil National des Universités” is usually required to apply. However candidates who already hold a tenured professor (or equivalent) position may in some cases be exempted from this certificate.
Closing date for applications:
Contact: Louis Goubin, Full Professor, head of the "Cryptology and Information Security" group
e-mail: louis.goubin (at) uvsq.fr
More information: https://www.galaxie.enseignementsup-recherche.gouv.fr/ensup/ListesPostesPublies/ANTEE/2024_1/0781944P/FOPC_0781944P_4338.pdf
Technical University of Darmstadt, Germany
The Cryptography and Privacy Engineering Group (ENCRYPTO) @CS Department @Technical University of Darmstadt offers a fully funded position as Doctoral Researcher (Research Assistant/PhD Student) in Cryptography and Privacy Engineering to be filled as soon as possible and initially for 3 years with the possibility of extension.
Job description:You'll work in the collaborative research center CROSSING funded by the German Research Foundation (DFG). In our project E4 Compiler for Privacy-Preserving Protocols, we build compilers to automatically generate optimized MPC protocols for privacy-preserving applications. See https://encrypto.de/CROSSING for details. As PhD@ENCRYPTO, you primarily focus on your research aiming to publish&present the results at top venues.
We offer:We demonstrate that privacy is efficiently protectable in real-world applications via cryptographic protocols. Our open and international working environment facilitates excellent research in a sociable team. TU Darmstadt is a top research university for IT security, cryptography and CS in Europe. Darmstadt is a very international, livable and well-connected city in the Rhine-Main area around Frankfurt.
Your profile:- Completed Master's degree (or equivalent) at a top university with excellent grades in IT security, computer science, or a similar area.
- Extensive knowledge in applied cryptography/IT security and very good software development skills. Knowledge in cryptographic protocols (ideally MPC) is a plus.
- Experience and interest to engage in teaching.
- Self-motivated, reliable, creative, can work independently, and striving to do excellent research.
- Our working language is English: Able to discuss/write/present scientific results in English. German is beneficial but not required.
Closing date for applications:
Contact: Thomas Schneider (application@encrypto.cs.tu-darmstadt.de)
More information: https://encrypto.de/2024-CROSSING