IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
03 March 2023
Poulami Das, Andreas Erwig, Sebastian Faust, Julian Loss, Siavash Riahi
ePrint ReportIn 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
ePrint ReportIn 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
ePrint ReportAsymptotically, 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
ePrint ReportIn 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
ePrint ReportDaniel Escudero, Vipul Goyal, Antigoni Polychroniadou, Yifan Song, Chenkai Weng
ePrint ReportPractically, 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
ePrint ReportMarco Macchetti
ePrint ReportEcublens, Switzerland, 1 May - 3 May 2023
Event CalendarSimula UiB, Bergen, Norway
Job PostingProject/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
Job PostingDescryption. 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
ePrint ReportBrandon Goodell, Aaron Feickert
ePrint ReportLéo Ducas, Ludo Pulles
ePrint ReportHowever, 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
ePrint ReportA 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
ePrint Report28 February 2023
Yonglin Hao, Qingju Wang, Lin Jiao, Xinxin Gong
ePrint ReportTo 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.
Mihir Bellare, Hannah Davis, Zijing Di
ePrint ReportSimone Colombo, Kirill Nikitin, Henry Corrigan-Gibbs, David J. Wu, Bryan Ford
ePrint ReportEthan Heilman, Lucie Mugnier, Athanasios Filippidis, Sharon Goldberg, Sebastien Lipman, Yuval Marcus, Mike Milano, Sidhartha Premkumar, Chad Unrein
ePrint ReportOpenPubkey is transparent to users and OpenID Providers. An OpenID Provider can not even determine that OpenPubkey is being used. This makes OpenPubkey fully compatible with existing OpenID Providers. In fact a variant of OpenPubkey is currently deployed and used to authenticate signed messages and identities for users with accounts on Google, Microsoft, Okta, and Onelogin. OpenPubkey does not add new trusted parties to OpenID Connect and reduces preexisting trust assumptions. If used in tandem with our MFA-cosigner, OpenPubkey can maintain security even against a malicious OpenID Provider (the most trusted party in OpenID Connect).