IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
03 March 2023
Sajin Sasy, Ian Goldberg
In this work we survey 31 systems targeting metadata-protected communications, and present a unified view of the current state of affairs. We provide two different taxonomies for existing MPCS, first into three different categories by the precise type of metadata protections they offer, and next into six families based on the core techniques that underlie them. By contrasting these systems we identify potential vulnerabilities, as well as subtle privacy implications of design choices of existing MPCS. Furthermore, we identify promising avenues for future research for MPCS, and desirable properties that merit more attention.
Poulami Das, Andreas Erwig, Sebastian Faust, Julian Loss, Siavash Riahi
In this work, we address this significant drawback of non-hardened nodes by laying out the design for the first hierarchical deterministic wallet scheme with thresholdized non-hardened nodes. We first provide a game-based notion of threshold signatures with rerandomizable keys and show an instantiation via the Gennaro and Goldfeder threshold ECDSA scheme (CCS'18). We further observe that the derivation of hardened child wallets according to the BIP32 specification does not translate easily to the threshold setting. Therefore, we devise a new and efficient derivation mechanism for hardened wallets in the threshold setting that satisfies the same properties as the original BIP32 derivation mechanism and therefore allows for efficient constructions of BIP32-compatible threshold wallets.
Léo Colisson, Garazi Muguruza, Florian Speelman
In particular, by instantiating our construction using Non-Interactive ZK (NIZK), we provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model, and round-optimal extensions to string and $k$-out-of-$n$ OT. At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing (too much) information on it, even in a non-interactive way and/or with statistical guarantees when using an appropriate classical ZK protocol. We can notably prove that a state has been partially measured (with arbitrary constraints on the set of measured qubits), without revealing any additional information on this set. This notion can be seen as an analog of ZK to quantum states, and we expect it to be of independent interest as it extends complexity theory to quantum languages, as illustrated by the two new complexity classes we introduce, ZKstateQIP and ZKstateQMA.
Lennart Braun, Mahak Pancholi, Rahul Rachuri, Mark Simkin
Asymptotically, our protocol requires a constant number of rounds and a amortized sublinear amount of communication and computation per memory access. In terms of concrete efficiency, our protocol outperforms previous solutions. For a memory of size $2^{26}$ our memory accesses are \(30\times\) faster in the LAN and \(8.7\times\) faster in the WAN setting, when compared to the previously fastest solution by Vadapalli, Henry, and Goldberg (ePrint 2022). Due to our superior asymptotic guarantees, the efficiency gap is only widening as the memory gets larger and for this reason Ramen provides the currently most scalable concretely efficient solution for securely computing RAM programs.
Rohann Bella, Xavier Bultel, Céline Chevalier, Pascal Lafourcade, Charles Olivier-Anclin
In 2019, X. Bultel and P. Lafourcade proposed a cryptographic protocol for Spades in the random oracle model allowing peer-to-peer trick-taking games to be played securely without the possibility of cheating, even by playing a card that does not respect the secret constraints. However, to simulate card shuffling, this protocol requires a custom proof of shuffle with quadratic complexity in the number of cards, which makes the protocol inefficient in practice. In this paper, we improve their work in several ways. First, we extend their model to cover a broader range of games, such as those implying a set of cards set aside during the deal (for instance Triomphe or French Tarot). Then, we propose a new efficient construction for Spades in the standard model (without random oracles), where cards are represented by partially homomorphic ciphertexts. It can be instantiated by any standard generic proof of shuffle, which significantly improves the efficiency. We demonstrate the feasibility of our approach by giving an implementation of our protocol, and we compare the performances of the new shuffle protocol with the previous one. Finally, we give a similar protocol for French Tarot, with comparable efficiency.
Vincent Grosso, Pierre-Louis Cayrel, Brice Colombier, Vlad-Florin Dragoi
Daniel Escudero, Vipul Goyal, Antigoni Polychroniadou, Yifan Song, Chenkai Weng
Practically, we also compare our work with the best concretely efficient online protocol Turbospeedz (Ben-Efraim \emph{et al}, ACNS 2019), which achieves $2(1-\epsilon)n$ field elements per multiplication gate among all parties. Our online protocol improves over Turbospeedz as $n$ grows, and as $\epsilon$ approaches $1/2$. For example, if there are $90\%$ corruptions ($\epsilon=0.1$), with $n=50$ our online protocol is $1.5\times$ better than Turbospeedz and with $n=100$ this factor is $3\times$, but for $70\%$ corruptions ($\epsilon=0.3$) with $n=50$ our online protocol is $3.5\times$ better, and for $n=100$ this factor is $7\times$.
Our circuit-dependent preprocessing can be instantiated from OLE/VOLE. The amount of OLE/VOLE correlations required in our work is a factor of $\approx \epsilon n/2$ smaller than these required by Le Mans (Rachuri and Scholl, CRYPTO 2022) leveraged to instantiate the preprocessing of Turbospeedz. Our dishonest majority protocol relies on packed secret-sharing and leverages ideas from the honest majority \textsc{TurboPack} (Escudero \emph{et al}, CCS 2022) protocol to achieve concrete efficiency for any circuit topology, not only SIMD. We implement both \textsc{SuperPack} and Turbospeedz and verify with experimental results that our approach indeed leads to more competitive runtimes in distributed environments with a moderately large number of parties.
Khashayar Barooti, Giulio Malavolta, Michael Walter
Marco Macchetti
Ecublens, Switzerland, 1 May - 3 May 2023
Simula UiB, Bergen, Norway
Project/Job description: The Ph.D. candidate will be supervised by Helger Lipmaa (https://sites.google.com/view/helgerlipmaa) on topics related to zk-SNARKs and zero-knowledge and their various applications (cryptocurrencies, verifiable computation, e-voting, to name a few). Zk-SNARKs have become excessively popular during the last few years due to their application in privacy-preserving cryptocurrencies. We expect the focus to be at least partially on post-quantum secure zk-SNARKs.
Candidate Profile: a completed MSc degree in cryptography or related areas (in particular, theoretical computer science, including algorithms and/or complexity theory, and mathematics). We will also consider applicants who are in the final phase of their MSc studies. We expect an excellent academic track record, including top grades. The student should be at home both in theory and practice: a good background in mathematics and TCS is particularly expected but having both this and an ability to read and write code is also useful. We value strong motivation with a combination of teamwork and the ability to work alone.
About Simula UiB (http://simula-uib.com): Simula UiB is a research center owned by the Simula Research Laboratory AS and the University of Bergen (UiB). Simula UiB has a large research group in cryptography and information theory, with eight faculty members who regularly publish at IACR conferences. The student will officially defend at UiB.
Simula UiB offers: modern office facilities located in downtown Bergen (“the gateway to the fjords”). A competitive salary starting from 501200 NOK (approx 45000-50000 euros, depending on the exchange rate). Emphasis on work-life balance. Numerous additional benefits.
Closing date for applications: 31.03.2023 but earlier application is encouraged
Research group homepage: https://sites.google.com/view/helgerlipmaa/research-group
Apply at: https://www.simula.no/about/job/phd-student-zero-knowledge-proofs (early application Is encouraged)
Closing date for applications:
Contact: Helger Lipmaa
More information: https://www.simula.no/about/job/phd-student-zero-knowledge-proofs
Cryptology Group, CWI Amsterdam and Mathematical Institute, Leiden University
Descryption. The CWI Cryptology group in Amsterdam and the Mathematical Institute of Leiden University offer a joint PhD position on the topic of Post-Quantum Cryptanalysis. The goal is to advance the state of the art in post-quantum cryptanalysis for the schemes that are currently being standardized. This ranges from improving our understanding in the fundamental computational problems underlying these important quantum-safe schemes, to improving the state of the art in cryptanalytic attacks, e.g., in more refined memory models.
Requirements. Candidates are required to have a master’s degree in mathematics or in computer science. Experience in one or more of these relevant background areas is an advantage: cryptography, algorithms, number theory, coding theory, and quantum algorithms. Some programming skills are expected. Candidates are expected to have an excellent command of English.
Information and application. All applications should include a detailed resume and motivation letter. The application deadline is 31 March 2023. Please visit the vacancy page (click the title) for more information about our terms of employment.
Closing date for applications:
Contact: Marc Stevens (stevens@cwi.nl), Peter Bruin (p.j.bruin@math.leidenuniv.nl)
More information: https://www.cwi.nl/en/jobs/vacancies/983536/
01 March 2023
Eleni Agathocleous, Vishnupriya Anupindi, Annette Bachmayr, Chloe Martindale, Rahinatou Yuh Njah Nchiwo, Mima Stanojkovski
Brandon Goodell, Aaron Feickert
Léo Ducas, Ludo Pulles
However, from a theoretical perspective, all of these works are painfully specific to Learning with Errors, while the principle of the Dual-Sieve attack is more general (Laarhoven & Walter, CT-RSA 2021). More critically, all of these works are based on heuristics that have received very little theoretical and experimental attention.
This work attempts to rectify the above deficiencies of the literature. We first propose a generalization of the FFT trick by Guo and Johansson to arbitrary Bounded Distance Decoding instances. This generalization offers a new improvement to the attack.
We then theoretically explore the underlying heuristics and show that these are in contradiction with formal, unconditional theorems in some regimes, and with well-tested heuristics in other regimes. The specific instantiations of the recent literature fall into this second regime.
We confirm these contradictions with experiments, documenting several phenomena that are not predicted by the analysis, including a ``waterfall-floor'' phenomenon, reminiscent of Low-Density Parity-Check decoding failures.
We conclude that the success probability of the recent Dual-Sieve-FFT attacks are presumably significantly overestimated. We further discuss the adequate way forward towards fixing the attack and its analysis.
Kamil Kluczniak, Giacomo Santato
A desirable property for homomorphic encryption is circuit privacy, which requires that a ciphertext leaks no information on the computation performed to obtain it. Despite numerous improvements, directed toward improving efficiency, the question of circuit privacy for approximate homomorphic encryption remains open.
In this paper, we give the first formal study of circuit privacy for homomorphic encryption over approximate arithmetic. We introduce formal models that allow us to reason about circuit privacy. Then, we show that approximate homomorphic encryption can be made circuit private using tools from differential privacy with appropriately chosen parameters. In particular, we show that by applying an exponential (in the security parameter) Gaussian noise on the evaluated ciphertext, we remove useful information on the circuit from the ciphertext. Crucially, we show that the noise parameter is tight, and taking a lower one leads to an efficient adversary against such a system.
We expand our definitions and analysis to the case of multikey and threshold homomorphic encryption for approximate arithmetic. Such schemes allow users to evaluate a function on their combined inputs and learn the output without leaking anything on the inputs. A special case of multikey and threshold encryption schemes defines a so-called partial decryption algorithm where each user publishes a ``masked'' version of its secret key, allowing all users to decrypt a ciphertext. Similarly, in this case, we show that applying a proper differentially private mechanism gives us IND-CPA-style security where the adversary additionally gets as input the partial decryptions. This is the first security analysis of approximate homomorphic encryption schemes that consider the knowledge of partial decryptions. We show lower bounds on the differential privacy noise that needs to be applied to retain security. Analogously, in the case of circuit privacy, the noise must be exponential in the security parameter. We conclude by showing the impact of the noise on the precision of CKKS-type schemes.
Hu Xiaobo, Xu Shengyuan, Tu Yinzi, Feng Xiutao
28 February 2023
Yonglin Hao, Qingju Wang, Lin Jiao, Xinxin Gong
To show the utility of our method, we propose boomerang attacks on the keyed permutations of three ARX hash functions of BLAKE. For the first time we mount an attack on the full 7 rounds of BLAKE3, with the complexity as low as $2^{180}$. Our best attack on BLAKE2s can improve the previously best result by 0.5 rounds but with lower complexity. The attacks on BLAKE-256 cover the same 8 rounds with the previous best result but with complexity $2^{16}$ times lower. All our results are verified practically with round-reduced boomerang quartets.