IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
24 July 2023
Rui Gao
A New Sieving Approach for Solving the HNP with One Bit of Nonce by Using Built-in Modulo Arithmetic
Yao Sun, Shuai Chang
To decrease the number of vectors that are shorter than the target vector and avoid the duplicated reduction, we introduce the modulo-$q$ lattice, a residue class ring of the general lattice modulo $q$, where $q$ is the modulus of the HNP. We present a new sieving algorithm to search for the shortest vectors in the modulo-$q$ lattice. Our algorithm uses built-in modulo $q$ arithmetic and many optimization techniques. As a result, we can solve a general 1-bit HNP ($q=2^{120}$) within 5 days and solve a general 1-bit HNP ($q=2^{128}$) within 17 days.
Ran Cohen, Jack Doerner, Yashvanth Kondi, abhi shelat
This flavor of security permits denial-of-service attacks in many applications, unless the cheating participants who cause aborts are identified. At present, there is a substantial performance gap between the best known protocols that are secure with non-identifiable abort, and the best known protocols that achieve security with identifiable abort (IA). Known constructions with IA rely on generic zero-knowledge proofs, adaptively secure oblivious transfer (OT) protocols, or homomorphic primitives.
We present a novel approach for realizing functionalities with a weak form of input-revealing IA, which is based on delicate and selective revealing of committed input values. We refer to this new approach as vindicating release. When our approach is applied to several well-known protocols---including a variant of PVW OT, Softspoken OT extension, DKLs multiplication, and MASCOT generic MPC---the resulting protocols can be combined to realize any sampling functionality with (standard) IA. Such a realization is statistically secure given a variant of statically-corruptable ideal OT, and it differs minimally in terms of cost, techniques, and analysis from the equivalent realization (using the same well-known protocols, unmodified) that lacks identifiability.
Using our protocol to sample the correlated randomness of the IOZ compiler reduces the compiler's requirements from an adaptively secure OT protocol to a variant of statically-corruptable ideal OT.
Oussama Sayari, Soundes Marzougui, Thomas Aulbach, Juliane Krämer, Jean-Pierre Seifert
This paper presents the first hardware implementation of the signature scheme MAYO. Our implementation can be easily integrated with different FPGA architectures. Additionally, it includes an agile instantiation with respect to the NIST-defined security levels for long-term security and encompasses modules' optimizations such as the vector-matrix multiplication and the Gaussian elimination method employed during the signing process. Our implementation is tested on the Zynq ZedBoard with the Zynq-7020 SoC and its performance is evaluated and compared to its counterpart multivariate scheme UOV.
Gaëtan Cassiers, Loïc Masure, Charles Momin, Thorben Moos, Amir Moradi, François-Xavier Standaert
Fukang Liu, Mohammad Mahzoun, Willi Meier
Ali Rezapour, Zahra Ahmadian
Pierre Pébereau
This proves that the security of the UOV scheme lies in the complexity of finding exactly one vector in the oil space. In addition, we deduce a key recovery attack from any forgery attack by applying a corollary of our main result.
We show how to extend this result to schemes related to UOV, such as MAYO and VOX.
Ittai Abraham, Gilad Asharov, Arpita Patra, Gilad Stern
We provide a new solution for Agreement on a Core Set that runs in expected $O(1)$ rounds, is perfectly secure, and resilient to $t<\frac{n}{4}$ corruptions. Our solution is based on a new notion of Asynchronously Validated Asynchronous Byzantine Agreement (AVABA) and new information theoretic analogs to techniques used in the authenticated model. We show a similar result with statistical security for $t<\frac{n}{3}$.
Haruka Hirata, Daiki Miyahara, Victor Arribas, Yang Li, Noriyuki Miura, Svetla Nikova, Kazuo Sakiyama
Then, we propose a countermeasure that prevents these attacks. We extend M&M with a fine-grained detection-based feature capable of detecting the zero-value glitch attacks. In this effort, we also solve the problem of a combined attack on the ciphertext output check of M&M scheme by using Kronecker's delta function. We deploy the countermeasure on FPGA and verify its security against both fault and side-channel analysis with practical experiments.
Furkan Aydin, Aydin Aysu
Cayle Sharrock, Schalk van Heerden
Navid Alamati, Varun Maram, Daniel Masny
We introduce a substantially weaker variant of the random oracle model in the post-quantum setting, which we call "non-observable quantum random oracle model" (NO QROM). Our model uses weaker heuristics than the quantum random oracle model by Boneh, Dagdelen, Fischlin, Lehmann, Schaffner, and Zhandry (ASIACRYPT 2011), or the non-observable random oracle model proposed by Ananth and Bhaskar (ProvSec 2013). At the same time, we show that our model is a viable option for establishing the post-quantum security of many cryptographic schemes by proving the security of important primitives such as extractable non-malleable commitments, digital signatures, and chosen-ciphertext secure public-key encryption in the NO QROM.
Léo Ducas, Thomas Espitau, Eamonn W. Postlethwaite
We apply this cryptanalysis to examples from the literature where taking such small moduli has been suggested. A recent work [Espitau–Tibouchi–Wallet–Yu, CRYPTO 2022] suggests small \(q\) versions of the lattice signature scheme FALCON and its variant MITAKA.
For one small \(q\) parametrisation of FALCON we reduce the estimated security against signature forgery by approximately 26 bits. For one small \(q\) parametrisation of MITAKA we successfully forge a signature in $15$ seconds.
Robert Christian Subroto
Benedikt Auerbach, Miguel Cueto Noval, Guillermo Pascual-Perez, Krzysztof Pietrzak
The recently proposed protocol CoCoA [Alwen et al. Eurocrypt'22], however, shows that this overhead can be reduced if PCS requirements are relaxed, and only a logarithmic number of rounds is required. The natural question, thus, is whether CoCoA is optimal in this setting.
In this work we answer this question, providing a lower bound on the cost (concretely, the amount of data to be uploaded to the server) for CGKA protocols that heal in an arbitrary $k$ number of rounds, that shows that CoCoA is very close to optimal. Additionally, we extend CoCoA to heal in an arbitrary number of rounds, and propose a modification of it, with a reduced communication cost for certain $k$.
We prove our bound in a combinatorial setting where the state of the protocol progresses in rounds, and the state of the protocol in each round is captured by a set system, each set specifying a set of users who share a secret key. We show this combinatorial model is equivalent to a symbolic model capturing building blocks including PRFs and public-key encryption, related to the one used by Bienstock et al.
Our lower bound is of order $k\cdot n^{1+1/(k-1)}/\log(k)$, where $2\le k\le \log(n)$ is the number of updates per user the protocol requires to heal. This generalizes the $n^2$ bound for $k=2$ from Bienstock et al. This bound almost matches the $k\cdot n^{1+2/(k-1)}$ or $k^2\cdot n^{1+1/(k-1)}$ efficiency we get for the variants of the CoCoA protocol also introduced in this paper.
Xinle Cao, Jian Liu, Yongsheng Shen, Xiaohua Ye, Kui Ren
Unfortunately, there are still vulnerabilities in all existing FH-OPE schemes. In this work, we revisit the security of all existing FH-OPE schemes. We are the first to demonstrate that plaintext frequency hidden by them is recoverable. We present three ciphertext-only attacks named frequency-revealing attacks to recover plaintext frequency. We evaluate our attacks in three real-world datasets. They recover over 90% of plaintext frequency hidden by any existing FH-OPE scheme. With frequency revealed, we also show the potentiality to apply inference attacks on existing FH-OPE schemes.
Our findings highlight the limitations of current FH-OPE schemes. Our attacks demonstrate that achieving frequency-hiding requires addressing the leakages of both non-uniform ciphertext distribution and insertion orders of ciphertexts, even though the leakage of insertion orders is always ignored in OPE.
Alireza Kavousi, Zhipeng Wang, Philipp Jovanovic
Muhammad Faisal, Jerry Zhang, John Liagouris, Vasiliki Kalavri, Mayank Varia
23 July 2023
Hasso-Plattner-Institut, Potsdam/Berlin, Germany
We have several open positions for PhD students and Postdocs to join our group at the Hasso-Plattner-Institute (HPI) in the area of cryptography and privacy. The HPI is academically structured as the independent Faculty of Digital Engineering at the University of Potsdam, and unites excellent research and teaching with the advantages of a privately financed institute.
Your tasks- Development and analysis of provably secure cryptographic protocols for real-world problems. Topics of interest include (but are not limited to):
- Privacy-preserving protocols
- Hardware-based cryptography
- User- and privacy-friendly identity management
- Foundations for real-world protocols
- Publish and present results at top-tier international conferences
- Participate in teaching activities
- Master's degree (or PhD for postdoctoral position) in Computer Science, Mathematics, or a related area by the time of appointment
- Strong algorithmic or mathematical background and good knowledge in the area of cryptography (for postdoctoral candidates proven in the form of publications)
- Fluent in English
We look forward to your application including a CV and motivation letter. Applications for the PhD position should also include a list of attended Master courses and grades, whereas applications for the Postdoc position should include contact information for two references.
Closing date for applications:
Contact: Anja Lehmann; anja.lehmann [at] hpi.de
More information: https://hpi.de/lehmann/home.html