International Association
for Cryptologic Research

We consider the design of a tweakable block cipher from a block cipher whose inputs and outputs are of size $n$ bits. The main goal is to achieve $2^n$ security with a large tweak (i.e., more than $n$ bits). Previously, Mennink at FSE'15 and Wang et al. at Asiacrypt'16 proposed constructions that can achieve $2^n$ security. Yet, these constructions can have a tweak size up to $n$-bit only. As evident from recent research, a tweakable block cipher with a large tweak is generally helpful as a building block for modes of operation, typical applications including MACs, authenticated encryption, leakage-resilient cryptography and full-disk encryption.

We begin with how to design a tweakable block cipher with $2n$-bit tweak and $n$-bit security from two block cipher calls. For this purpose, we do an exhaustive search for tweakable block ciphers with $2n$-bit tweaks from two block cipher calls, and show that all of them suffer from birthday-bound attacks. Next, we investigate the possibility to design a tweakable block cipher with $2n$-bit tweak and $n$-bit security from three block cipher calls. We start with some conditions to build a such tweakable block cipher and propose a natural construction, called G1, that likely meets them. After inspection, we find a weakness on G1 which leads to a birthday-bound attack. Based on G1, we then propose another construction, called G2, that can avoid this weakness. We finally prove that G2 can achieve $n$-bit security with $2n$-bit tweak.

The current work makes a systematic attempt to describe the effect of the relative order of round constant ( RCon) addition in the round function of an SPN cipher on its algebraic structure. The observations are applied to the SymSum distinguisher, introduced by Saha et al. in FSE 2017 which is one of the best distinguishers on the SHA3 hash function reported in literature. Results show that certain ordering (referred to as Type-LCN) of RCon makes the distinguisher less effective but it still works with some limitations. Results in the form of new SymSum distinguishers are reported on concrete Type-LCN constructions - NIST LWC competition finalist Xoodyak-Hash and its internal permutation Xoodoo. New linear structures are also reported on Xoodoo that augment the distinguisher to penetrate more rounds. Final results include SymSum distinguishers on 7 rounds of Xoodoo and 5 rounds of Xoodyak-Hash with complexity 2^128 and 2^32 , respectively. All practical distinguishers have been verified. The characterization encompassing the algebraic structure and effect of RCon provided by the current work improves the under- standing of SymSum in general and constitutes one of the first such result on Xoodyak-Hash and Xoodoo.

Event date: 3 October to 4 October 2023
Submission deadline: 1 July 2023
Notification: 30 June 2023

Cryptography, Security & Privacy Research Group at Koç University has one opening at the post-doctoral researcher level. Accepted applicants may receive competitive salary, housing (accommodation) support, health insurance, computer, travel support, and lunch meal card.

Your duties include performing research on cryptography, security, and privacy in line with our research group's focus, as well as directing graduate and undergraduate students in their research and teaching. The project funding is related to cryptography, game theory and mechanism design, adversarial machine learning, and blockchain technologies.

Applicants are expected to have already obtained their Ph.D. degrees in Computer Science or related discipline with a thesis topic related to the duties above.

For more information about joining our group and projects, visit

https://crypto.ku.edu.tr/work-with-us/

Submit your application via email including

• full CV,
• transcripts of all universities attended,
• 1-3 sample publications where you are the main author,
• a detailed research proposal,
• 2-3 reference letters sent directly by the referees.

Application and start dates are flexible.

Closing date for applications:

Contact: Assoc. Prof. Alptekin Küpçü
https://member.acm.org/~kupcu

More information: https://crypto.ku.edu.tr/work-with-us/

Cryptography, Security & Privacy Research Group at Koç University has multiple openings at every level. Accepted Computer Science and Engineering applicants may receive competitive scholarships including monthly stipend, tuition waiver, housing (accommodation) support, health insurance, computer, travel support, and lunch meal card.

Your duties include performing research on cryptography, cyber security, and privacy in line with our research group's focus, including blockchains and adversarial machine learning, assist teaching, as well as collaborating with other graduate and undergraduate students. Computer Science, Mathematics, Cryptography, or related background is necessary.

For applying online, and questions about the application-process for M.Sc. and Ph.D. positions, visit

https://gsse.ku.edu.tr/en/admissions/application-requirements

All applications must be completed online. Applications with missing documents will not be considered. Applications via e-mail will not be considered. Application Requirements:

1. CV
2. Recommendation Letters (2 for MSc, 3 for PhD)
3. TOEFL (for everyone whose native language is not English, Internet Based: Minimum Score 80)
4. GRE score
5. Official transcripts from all the universities attended
6. Statement of Purpose
7. Area of Interest Form filled online

https://gsse.ku.edu.tr/en/admissions/how-to-apply/

We also have a non-thesis paid Cyber Security M.Sc. program:

https://cybersecurity.ku.edu.tr/

For more information about joining our group and projects, visit

https://crypto.ku.edu.tr/work-with-us/

Closing date for applications:

Contact: https://gsse.ku.edu.tr/en/admissions/how-to-apply/

More information: https://gsse.ku.edu.tr/en/admissions/how-to-apply/

Paderborn University is a high-performance and internationally oriented campus university with around 20,000 students. In interdisciplinary teams, we shape future-oriented research, innovative teaching and the active transfer of knowledge to society. As an important research and cooperation partner, the university also shapes regional development strategies.
The Faculty of Electrical Engineering, Computer Science and Mathematics - Institute of Computer Science / Codes and Cryptography Group - has a vacancy (100% of the regular working time) at the earliest opportunity:

Research Assistant (f/m/d) (salary is according to 13 TV-L)

This is a qualification position within the meaning of the Wissenschaftszeitvertragsgesetz (WissZeitVG - German Act on Scientific Temporary Contracts), which serves to promote a doctoral procedure or an early postdoc phase in the field of "Codes and Cryptography". The position is to be filled for a limited period, depending on the qualification achieved to date, but generally for a period of 3 years. An extension is possible within the time limits of the WissZeitVG if applicable.

Your duties and responsibilities
Research in one of the following areas:
- Cryptography and quantum cryptography
- Algorithmic number theory and complexity theory
- Quantum algorithms and quantum complexity
- Teaching on the order of 4 teaching hours (SWS) per week

Hiring requirement: Scientific Master degree in computer science, mathematics of physics
Since Paderborn University seeks to increase the number of female scientists, applications of women are especially welcome. In case of equal qualification and scientific achievements, they will receive preferential treatment according to the North Rhine-Westphalian Equal Opportunities Policy (LGG), unless there are cogent reasons to give preference to another applicant. Part-time employment is possible. Likewise, applications of disabled people with appropriate qualification are explicitly requested. This also applies to people with equal status according to the German social law SGB IX.

Closing date for applications:

Contact: Please send your application including a CV (preferably in a single pdf file) using the Ref. No. 5963 by 30 June 2023 to: bloemer@upb.de.

Prof. Dr. Johannes Blömer Faculty of Computer Science, Electrical Engineering and Mathematics Paderborn University Warburger Str. 100 33098 Paderborn

More information: https://cs.uni-paderborn.de/en/cuk/research

Event date: 5 March to 8 March 2024
Submission deadline: 20 July 2023
Notification: 12 September 2023

Event date: 3 June to 6 June 2024

We describe a pairing-based SNARK with a universal updateable CRS that can be instantiated with any pairing-friendly curve endowed with a sufficiently large prime scalar field. We use the monomial basis, thus sidestepping the need for large smooth order subgroups in the scalar field. In particular, the scheme can be instantiated with outer curves to widely used curves such as Ed25519, secp256k1 and BN254. This allows us to largely circumvent the overhead of non-native field arithmetic for succinct proofs of statements in these base fields. These include proofs of valid signatures in Ed25519 and secp256k1 and one layer recursion with BN254.

The proof size is constant \( (10\; \mathbb{G}_1\), \(20\;\mathbb{F}_p)\), as is the verification runtime, which is dominated by a single pairing check (i.e. two pairings). The Prover time is dominated by the \(10\) multi-scalar multiplications in \(\mathbb{G}_1\) - with a combined MSM length of $22\cdot |\mathrm{Circuit}|$ - and, to a lesser extent, the computation of a single sum of polynomial products over the scalar field.

The scheme supports succinct lookup arguments for subsets as well as subsequences. Our construction relies on homomorphic table commitments, which makes them amenable to vector lookups. The Prover algorithm runs in runtime $O(M\cdot \log(M))$, where $M = \max \{|\text{Circuit}| , \;|\text{Table}|\}.$

When the scalar field has low $2$-adicity - as is inevitably the case with any outer curve to Ed25519, secp256k1 or BN254 - we use the Schonhage-Strassen algorithm or the multimodular FFT algorithm to compute the sum of polynomial products that occurs in one of the steps of the proof generation. Despite the small (but discernible) slowdown compared to polynomial products in FFT-friendly fields, we empirically found that the MSMs dominate the proof generation time. To that end, we have included some benchmarks for polynomial products in FFT-unfriendly fields.

Furthermore, the scheme supports custom gates, albeit at the cost of a larger proof size. As an application of the techniques in this paper, we describe a protocol that supports multiple \( \mathbf{univariate}\) custom gates $\mathcal{G}_i$ of high degree that are sparsely distributed, in the sense that \[ \sum_{i} \deg(\mathcal{G}_i)\cdot \#(\mathcal{G}_i\;\text{gates}) \; = \; O(|\text{Circuit}|). \] This comes at the cost of three additional $\mathbb{G}_1$ elements and does not blow up the proof generation time, i.e. it does not entail MSMs or FFTs of length larger than the circuit size.

At the moment, Panther Protocol's Rust implementation in a 576-bit pairing-friendly outer curve to Ed25519 has a (not yet optimized) Prover time of 45 seconds for a million gate circuit on a 64 vCPU AWS machine.

Safety, liveness, and privacy are three critical properties for any private proof-of-stake (PoS) blockchain. However, prior work (SP'21) has shown that to obtain safety and liveness, a PoS blockchain must in theory forgo privacy. Specifically, to ensure safety and liveness, PoS blockchains elect parties based on stake proportion, potentially exposing a party's stake even with private transaction processing. In this work, we make two key contributions. First, we present the first stake inference attack applicable to both deterministic and randomized PoS with exponentially less running time in comparison with SOTA designs. Second, we use differentially private stake distortion to achieve privacy in PoS blockchains and design two stake distortion mechanisms that any PoS protocol can use. We further evaluate our proposed methods using Ethereum 2.0, a widely-recognized PoS blockchain in operation. Results demonstrate effective stake inference risk mitigation, reasonable privacy, and preservation of essential safety and liveness properties.

The ecosystem around blockchain and Decentralized Finance (DeFi) is seeing more and more interest from centralized regulators. For instance, recently, the US government placed sanctions on the largest DeFi mixer, Tornado.Cash (TC). To our knowledge, this is the first time that centralized regulators sanction a decentralized and open-source blockchain application. It has led various blockchain participants, e.g., miners/validators and DeFi platforms, to censor TC-related transactions. The blockchain community has extensively discussed that censoring transactions could affect users’ privacy.

In this work, we analyze the efficiency and possible security implications of censorship on the different steps during the life cycle of a blockchain transaction, i.e., generation, propagation, and validation. We reveal that fine-grained censorship will reduce the security of block validators and centralized transaction propagation services, and can potentially cause Denial of Service (DoS) attacks. We also find that DeFi platforms adopt centralized third-party services to censor user addresses at the frontend level, which blockchain users could easily bypass. Moreover, we present a tainting attack whereby an adversary can prevent users from interacting normally with DeFi platforms by sending TC-related transactions.

This article is dedicated to a new generation method of two ``independent'' $\mathbb{F}_{\!q}$-points $P_0$, $P_1$ on almost any ordinary elliptic curve $E$ over a finite field $\mathbb{F}_{\!q}$ of large characteristic. In particular, the method is relevant for all standardized and real-world elliptic curves of $j$-invariants different from $0$, $1728$. The points $P_0$, $P_1$ are characterized by the fact that nobody (even a generator) knows the discrete logarithm $\log_{P_0}(P_1)$ in the group $E(\mathbb{F}_{\!q})$. Moreover, only one square root extraction in $\mathbb{F}_{\!q}$ (instead of two ones) is required in comparison with all previous generation methods.

A sequential aggregate signature (SAS) scheme allows multiple users to sequentially combine their respective signatures in order to reduce communication costs. Historically, early proposals required the use of trapdoor permutation (e.g., RSA). In recent years, a number of attempts have been made to extend SAS schemes to post-quantum assumptions. Many post-quantum signatures have been proposed in the hash-and-sign paradigm, which requires the use of trapdoor functions and appears to be an ideal candidate for sequential aggregation attempts. However, the hardness in achieving post-quantum one-way permutations makes it difficult to obtain similarly general constructions. Direct attempts at generalizing permutation-based schemes have been proposed, but they either lack formal security or require additional properties on the trapdoor function, which are typically not available for multivariate or code-based functions. In this paper, we propose a history-free sequential aggregate signature based on generic trapdoor functions, generalizing existing techniques. We prove the security of our scheme in the random oracle model by adopting the probabilistic hash-and-sign with retry paradigm, and we instantiate our construction with three post-quantum schemes, comparing their compression capabilities. Finally, we discuss how direct extensions of permutation-based SAS schemes are not possible without additional properties, showing the insecurity of two existing multivariate schemes when instantiated with Unbalanced Oil and Vinegar.

The Brakerski-Gentry-Vaikuntanathan (BGV) scheme is a Fully Homomorphic Encryption (FHE) cryptosystem based on the Ring Learning With Error (RLWE) problem. Ciphertexts in this scheme contain an error term that grows with operations and causes decryption failure when it surpasses a certain threshold. For this reason, the parameters of BGV need to be estimated carefully, with a trade-off between security and error margin. The ciphertext space of BGV is the ring $\mathcal R_q=\mathbb Z_q[x]/(\Phi_m(x))$, where usually the degree $n$ of the cyclotomic polynomial $\Phi_m(x)$ is chosen as a power of two for efficiency reasons. However, the jump between two consecutive powers-of-two polynomials can sometimes also cause a jump of the security, resulting in parameters that are much bigger than what is needed.

In this work, we explore the non-power-of-two instantiations of BGV. Although our theoretical research encompasses results applicable to any cyclotomic ring, our main investigation is focused on the case of $m=2^s 3^t$, i.e., cyclotomic polynomials with degree $n=2^s 3^{t-1}$. We provide a thorough analysis of the noise growth in this new setting using the canonical norm and compare our results with the power-of-two case considering practical aspects like NTT algorithms. We find that in many instances, the parameter estimation process yields better results for the non-power-of-two setting.

Designing symmetric-key primitives for applications in Fully Homomorphic Encryption (FHE) has become important to address the issue of the ciphertext expansion. In such a context, cryptographic primitives with a low-AND-depth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the well-known $\chi$ function over $\mathbb{F}_2^n$ and the power map over a large finite field $\mathbb{F}_{p^n}$. In this work, we study the growth of the algebraic degree for an SPN cipher over $\mathbb{F}_{2^n}^{m}$, whose S-box is defined as the combination of a power map $x\mapsto x^{2^d+1}$ and an $\mathbb{F}_2$-linearized affine polynomial $x\mapsto c_0+\sum_{i=1}^{w}c_ix^{2^{h_i}}$ where $c_1,\ldots,c_w\neq0$. Specifically, motivated by the fact that the original coefficient grouping technique published at EUROCRYPT 2023 becomes less efficient for $w>1$, we develop a variant technique that can efficiently work for arbitrary $w$. With this new technique to study the upper bound of the algebraic degree, we answer the following questions from a theoretic perspective:

1. can the algebraic degree increase exponentially when $w=1$?

2. what is the influence of $w$, $d$ and $(h_1,\ldots,h_w)$ on the growth of the algebraic degree?

Based on this, we show (i) how to efficiently find $(h_1,\ldots,h_w)$ to achieve the exponential growth of the algebraic degree and (ii) how to efficiently compute the upper bound of the algebraic degree for arbitrary $(h_1,\ldots,h_w)$. Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.

A Key Derivation Function KDF generates a uniform and highly random key-stream from weakly random key material. KDFs are broadly used in various security protocols such as digital signatures and key exchange protocols. HKDF is the most deployed KDF in practice. It is based on the $\textit{extract-then-expand}$ paradigm and is presently used, among others, in the Signal Protocol for end-to-end encrypted messaging. HKDF was proposed as a generic KDF for general input sources and thus is not optimized for source-specific use cases such as key derivation from Diffie-Hellman (DH) sources (i.e. DH shared secrets as key material). Furthermore, the sequential HKDF design is unnecessarily slower on some general-purpose platforms that benefit from parallelization. In this work, we propose a novel, efficient and secure KDF called $\mathsf{Skye}$. $\mathsf{Skye}$ follows the $\textit{extract-then-expand}$ paradigm and consists of two algorithms: efficient deterministic $\textit{randomness extractor}$ and $\textit{expansion}$ functions. Instantiating our extractor for dedicated source-specific (e.g. DH sources) inputs allows us to achieve a significant efficiency speed-up over HKDF at the same security level. We provide concrete security analysis of $\mathsf{Skye}$ and both its algorithms in the standard model. We provide a software performance comparison of $\mathsf{Skye}$ with the AES-based expanding PRF $\mathsf{ButterKnife}$ and HKDF with SHA-256 (as used in Signal). Our results show that in isolation $\mathsf{Skye}$ performs from 4x to 47x faster than HKDF, depending on the platform instruction support. We further demonstrate that with such a performance gain, when $\mathsf{Skye}$ is integrated within the current Signal implementation, we can achieve significant overall improvements ranging from $38\%$ to $64\%$ relative speedup in unidirectional messaging. Even in bidirectional messaging, that includes DH computation with dominating computational cost, $\mathsf{Skye}$ still contributes to $12-36\%$ relative speedup when just 10 messages are sent and received at once.

Confidentiality, authentication, and anonymity are the fundamental security requirements in broadcast communication that can be achieved by Digital Signature (DS), encryption, and pseudo-anonymous identity techniques. Signcryption offer both DS and encryption in a single logical step with high efficiency. Similarly, anonymous multireceiver signcryption ensure receiver privacy by generating identical ciphertext for multiple receivers while keeping their identities private. While signcryption is a significant improvement over “sign then encrypt”, it still incurs higher computational and communication cost and does not provide the required level of security. In this paper, we propose a multiple-recipient Key Encapsulation Mechanism (mKEM) - Data Encapsulation Mechanism (DEM) based Anonymous Multireceiver Certificateless Hybrid Signcryption (AMCLHS). The AMCLHS uses a combination of symmetric key and asymmetric key cryptography to signcrypt an arbitrary length message in broadcast communication and has two unique settings as follows: Pseudo-Identity PID Settings: We introduce a new algorithmic step in AMCLHS construction where each user (sender and receiver) is assigned a PID to enable the sender to signcrypt identical messages for multiple receivers while keeping the identities of other receivers anonymous. The receiver anonymity is achieved by choosing random Real-Identity (ID_R) to generate PID of the users in key generation algorithm of AMCLHS scheme. Our approach relies on the Elliptic Curve Discrete Logarithm (ECDL) hardness assumptions, the hash function, and verification-based secret key of the Register Authority (RA), using time Delta T. mKEM-DEM Settings: We introduce the first construction that achieves optimal ciphertext from the Diffie-Hellman (DH) assumption using mKEM-DEM for Signcryption. Our scheme uses mKEM to generate a symmetric key for multiple-receivers and DEM to signcrypt message using the previously generated symmetric key and the sender's private key. mKEM for key setup and Signcryption for confidentiality and forward security, and DEM for key generation and unsigncryption for indistinguishability under Indistinguishability against Chosen Ciphertext Attack (IND-CCA2). Our scheme relies on DH and Bilinear Pairing (BP) assumption and uses a single key for all messages, which minimizes ciphertext length and ultimately reduces complexity overhead. The scheme operates in a multireceiver certificateless environment, preventing the key escrow problem, and demonstrates cryptographic notions for Indistinguishability under Chosen-Ciphertext Attack (IND-CCA2) and Existential Unforgeability against Chosen Message Attack (EUF-CMA) for Type-I and Type-II adversaries under q-Decisional Bilinear Diffie-Hellman Inversion (q-DBDHI) and ECDL hard assumptions. We compare the proposed scheme with existing multireceiver hybrid signcryption schemes in terms of computation cost, communication cost, and security requirements. We show that, compared to existing multireceiver schemes which has overall cost of O(n^2), our scheme is computationally more efficient and has optimal communication cost, with signcryption cost linear O(n) to the number of designated receivers while the unsigncryption cost remains constant O(1). Our scheme achieves confidentiality, authentication, anonymity, and simultaneously achieves unlinkability, non-repudiation, and forward security.

The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic $p$ given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime.

In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have $O(\log\log p)$ many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer $N$ with $O(\log\log p)$ many prime factors to powersmooth elements.

As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.

Zero Knowledge Proofs (ZKPs) are cryptographic protocols by which a prover convinces a verifier of the truth of a statement with- out revealing any other information. Typically, statements are expressed in a high-level language and then compiled to a low-level representation on which the ZKP operates. Thus, a bug in a ZKP compiler can com- promise the statement that the ZK proof is supposed to establish. This paper takes a step towards ZKP compiler correctness by partially veri- fying a field-blasting compiler pass, a pass that translates Boolean and bit-vector logic into equivalent operations in a finite field. First, we define correctness for field-blasters and ZKP compilers more generally. Next, we describe the specific field-blaster using a set of encoding rules and de- fine verification conditions for individual rules. Finally, we connect the rules and the correctness definition by showing that if our verification conditions hold, the field-blaster is correct. We have implemented our approach in the CirC ZKP compiler and have proved bounded versions of the corresponding verification conditions. We show that our partially verified field-blaster does not hurt the performance of the compiler or its output; we also report on four bugs uncovered during verification.

All modern lattice-based schemes build on variants of the LWE problem. Information leakage of the LWE secret $\mathbf s \in \mathbb{Z}_q^n$ is usually modeled via so-called hints, i.e., inner products of $\mathbf s$ with some (random, but known) vector.

At Crypto`20, Dachman-Soled, Ducas, Gong and Rossi (DDGR) defined among other so-called perfect hints and modular hints. The trailblazing DDGR framework allows to integrate and combine hints successively into lattices, and estimates the resulting LWE security loss.

We introduce a new methodology to integrate and combine an arbitrary number of perfect and modular in a single stroke. As opposed to DDGR, our methodology is significantly more efficient in constructing lattice bases, and thus easily allows for a large number of hints up to cryptographic dimensions, a regime that is impractical in DDGR. The efficiency of our method defines a large LWE parameter regime, in which we can fully carry out attacks faster than DDGR can solely estimate them. A key component of our new method is dimension reduction of $\mathbf s$, which significantly reduces LWE security.

The benefits of our approach allow us to practically determine which number of hints is sufficient to efficiently break LWE-based lattice schemes in practice. For mod-$q$ hints, i.e., modular hints defined over $\mathbb{Z}_q$, we reconstruct Kyber-512 secret keys via LLL reduction (only!) with an amount of $449$ hints. For Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we need $452$, $622$, $702$ and $876$ modular hints, respectively. Our results for perfect hints significantly improve over these numbers, requiring for LWE dimension $n$ roughly $n/2$ perfect hints. Namely, we reconstruct via LLL reduction Kyber-512 keys with merely $234$ perfect hints. For secret keys of Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we require $233$, $332$, $390$ and $463$ perfect hints, respectively. We find such a small amount of perfect hints quite remarkable. If we resort to stronger lattice reduction techniques like BKZ, we need even fewer hints.

For mod-$q$ hints our method is extremely efficient, taking total time for constructing our lattice bases and secret key recovery via LLL of around 20 mins for dimension 512, 40 mins for dimensions 701 and 768, and less than 10 hours for dimension 1024. For perfect hints we require around 3 hours (dim 512), 11 hours (dim 701), 1 day (dim 768), and one week (dim 1024).

Our results demonstrate that especially perfect hints are powerful in practice, and stress the necessity to properly protect lattice schemes against leakage.