International Association
for Cryptologic Research

In proof-of-stake blockchains, liveness is ensured by repeatedly selecting random groups of parties as leaders, who are then in charge of proposing new blocks and driving consensus forward, among all their participants. The lotteries that elect those leaders need to ensure that adversarial parties are not elected disproportionately often and that an adversary can not tell who was elected before those parties decide to speak, as this would potentially allow for denial-of-service attacks. Whenever an elected party speaks, it needs to provide a winning lottery ticket, which proves that the party did indeed win the lottery. Current solutions require all published winning tickets to be stored individually on-chain, which introduces undesirable storage overheads.

In this work, we introduce {non-interactive aggregatable lotteries} and show how these can be constructed efficiently. Our lotteries provide the same security guarantees as previous lottery constructions, but additionally allow any third party to take a set of published winning tickets and aggregate them into one short digest. We provide a formal model of our new primitive in the universal composability framework.

As one of our main technical contributions, which may be of independent interest, we introduce aggregatable vector commitments with simulation-extractability and present a concretely efficient construction thereof in the algebraic group model in the presence of a random oracle. We show how these commitments can be used to construct non-interactive aggregatable lotteries.

We have implemented our construction, called {Jackpot}, and provide benchmarks that underline its concrete efficiency.

Proof-of-Replication (PoRep) plays a pivotal role in decentralized storage networks, serving as a mechanism to verify that provers consistently store retrievable copies of specific data. While PoRep’s utility is unquestionable, its implementation in large-scale systems, such as Filecoin, has been hindered by scalability challenges. Most existing PoRep schemes, such as Fisch’s (Eurocrypt 2019), face an escalating number of challenges and growing computational overhead as the number of stored files increases. This paper introduces a novel PoRep scheme distinctively tailored for expansive decentralized storage networks. At its core, our approach hinges on polynomial evaluation, diverging from the probabilistic checking prevalent in prior works. Remarkably, our design requires only a single challenge, irrespective of the number of files, ensuring both prover’s and verifier’s run-times remain manageable even as file counts soar. Our approach introduces a paradigm shift in PoRep designs, offering a blueprint for highly scalable and efficient decentralized storage solutions.

Cryptographic constructions often base security on structured problem variants to enhance efficiency or to enable advanced functionalities. This led to the introduction of the Regular Syndrome Decoding (RSD) problem, which guarantees that a solution to the Syndrome Decoding (SD) problem follows a particular block-wise structure. Despite recent attacks exploiting that structure by Briaud and Øygarden (Eurocrypt ’23) and Carozza, Couteau and Joux (CCJ, Eurocrypt ’23), many questions about the impact of the regular structure on the problem hardness remain open.

In this work we initiate a systematic study of the hardness of the RSD problem starting from its asymptotics. We classify different parameter regimes revealing large regimes for which RSD instances are solvable in polynomial time and on the other hand regimes that lead to particularly hard instances. Against previous perceptions, we show that a classification solely based on the uniqueness of the solution is not sufficient for isolating the worst case parameters. Further we provide an in-depth comparison between SD and RSD in terms of reducibility and computational complexity, identifying regimes in which RSD instances are actually harder to solve.

We provide the first asymptotic analysis of the CCJ algorithm, establishing its worst case decoding complexity as $2^{0.141n}$. We then introduce \emph{regular-ISD} algorithms by showing how to tailor the whole machinery of advanced Information Set Decoding (ISD) techniques from attacking SD to the RSD setting. The fastest regular-ISD algorithm improves the worst case decoding complexity significantly to $2^{0.112n}$. Eventually, we show that also with respect to suggested parameters regular-ISD outperforms previous approaches in most cases, reducing security levels by up to 40 bits.

The advancement of large-scale quantum computers poses a threat to the security of current encryption systems. In particular, symmetric-key cryptography significantly is impacted by general attacks using the Grover's search algorithm. In recent years, studies have been presented to estimate the complexity of Grover's key search for symmetric-key ciphers and assess post-quantum security. In this paper, we propose a depth-optimized quantum circuit implementation for ARIA, which is a symmetric key cipher included as a validation target the Korean Cryptographic Module Validation Program (KCMVP). Our quantum circuit implementation for ARIA improves the depth by more than 88.2% and Toffoli depth by more than 98.7% compared to the implementation presented in Chauhan et al.'s SPACE'20 paper. Finally, we present the cost of Grover's key search for our circuit and evaluate the post-quantum security strength of ARIA according to relevant evaluation criteria provided NIST.

With the advancement of quantum computers, it has been demonstrated that Shor's algorithm enables public key cryptographic attacks to be performed in polynomial time. In response, NIST conducted a Post-Quantum Cryptography Standardization competition. Additionally, due to the potential reduction in the complexity of symmetric key cryptographic attacks to square root with Grover's algorithm, it is increasingly challenging to consider symmetric key cryptography as secure. In order to establish secure post-quantum cryptographic systems, there is a need for quantum post-quantum security evaluations of cryptographic algorithms. Consequently, NIST is estimating the strength of post-quantum security, driving active research in quantum cryptographic analysis for the establishment of secure post-quantum cryptographic systems. In this regard, this paper presents a depth-optimized quantum circuit implementation for SEED, a symmetric key encryption algorithm included in the Korean Cryptographic Module Validation Program (KCMVP). Building upon our implementation, we conduct a thorough assessment of the post-quantum security for SEED. Our implementation for SEED represents the first quantum circuit implementation for this cipher.

Quantum computers, especially those with over 10,000 qubits, pose a potential threat to current public key cryptography systems like RSA and ECC due to Shor's algorithms. Grover's search algorithm is another quantum algorithm that could significantly impact current cryptography, offering a quantum advantage in searching unsorted data. Therefore, with the advancement of quantum computers, it is crucial to analyze potential quantum threats.

While many works focus on Grover’s attacks in symmetric key cryptography, there has been no research on the practical implementation of the quantum approach for lattice-based cryptography. Currently, only theoretical analyses involve the application of Grover's search to various Sieve algorithms.

In this work, for the first time, we present a quantum NV Sieve implementation to solve SVP, posing a threat to lattice-based cryptography. Additionally, we implement the extended version of the quantum NV Sieve (i.e., the dimension and rank of the lattice vector). Our extended implementation could be instrumental in extending the upper limit of SVP (currently, determining the upper limit of SVP is a vital factor). Lastly, we estimate the quantum resources required for each specific implementation and the application of Grover's search.

In conclusion, our research lays the groundwork for the quantum NV Sieve to challenge lattice-based cryptography. In the future, we aim to conduct various experiments concerning the extended implementation and Grover's search.

Blind rotation is one of the key techniques to construct fully homomorphic encryptions with the best known bootstrapping algorithms running in less than one second. Currently, the two main approaches, namely, AP and GINX, for realizing blind rotation are first introduced by Alperin-Sheriff and Peikert (CRYPTO 2014) and Gama, Izabachene, Nguyen and Xie (EUROCRYPT 2016), respectively.

\qquad In this paper, we propose a new blind rotation algorithm based on a GSW-like encryption from the NTRU assumption. Our algorithm has performance asymptotically independent from the key distributions, and outperforms AP and GINX in both the evaluation key size and the computational efficiency(especially for large key distributions). By using our blind rotation algorithm as a building block, we present new bootstrapping algorithms for both LWE and RLWE ciphertexts.

We implement our bootstrapping algorithm for LWE ciphertexts, and compare the actual performance with two bootstrapping algorithms, namely, FHEW/AP by Ducas and Micciancio (EUROCRYPT 2015) and TFHE/GINX by Chillotti, Gama, Georgieva and Izabach\`ene (Journal of Cryptology 2020), that were implemented in the OpenFHE library. For parameters with ternary key distribution at 128-bit security, our bootstrapping only needs to store evaluation key of size 18.65MB for blind rotation, which is about 89.8 times smaller than FHEW/AP and 2.9 times smaller than TFHE/GINX. Moreover, our bootstrapping can be done in 112ms on a laptop, which is about 3.2 times faster than FHEW/AP and 2.1 times faster than TFHE/GINX. More improvements are available for large key distributions such as Gaussian distributions.

This paper formally analyzes two major non-profiled deep-learning-based side-channel attacks (DL-SCAs): differential deep-learning analysis (DDLA) by Timon and collision DL-SCA by Staib and Moradi. These DL-SCAs leverage supervised learning in non-profiled scenarios. Although some intuitive descriptions of these DL-SCAs exist, their formal analyses have been rarely conducted yet, which makes it unclear why and when the attacks succeed and how the attack can be improved. In this paper, we provide the first information-theoretical analysis of DDLA. We reveal its relevance to the mutual information analysis (MIA), and then present three theorems stating some limitations and impossibility results of DDLA. Subsequently, we provide the first probability-theoretical analysis on collision DL-SCA. After presenting its formalization with a proposal of our distinguisher for collision DL-SCA, we prove its optimality. Namely, we prove that the collision DL-SCA using our distinguisher theoretically maximizes the success rate if the neural network (NN) training is completely successful (namely, the NN completely imitates the true conditional probability distribution). Accordingly, we propose an improvement of the collision DL-SCA based on a dedicated NN architecture and a full-key recovery methodology using multiple neural distinguishers. Finally, we experimentally evaluate non-profiled (DL-)SCAs using a newly created dataset using publicly available first-order masked AES implementation. The existing public dataset of side-channel traces is insufficient to evaluate collision DL-SCAs due to a lack of substantive side-channel traces for different key values. Our dataset enables a comprehensive evaluation of collision (DL-)SCAs, which clarifies the current situation of non-profiled (DL-)SCAs.

The Implicit Factorization Problem (IFP) was first introduced by May and Ritzenhofen at PKC'09, which concerns the factorization of two RSA moduli $N_1=p_1q_1$ and $N_2=p_2q_2$, where $p_1$ and $p_2$ share a certain consecutive number of least significant bits. Since its introduction, many different variants of IFP have been considered, such as the cases where $p_1$ and $p_2$ share most significant bits or middle bits at the same positions. In this paper, we consider a more generalized case of IFP, in which the shared consecutive bits can be located at $any$ positions in each prime, not necessarily required to be located at the same positions as before. We propose a lattice-based algorithm to solve this problem under specific conditions, and also provide some experimental results to verify our analysis.

As the ubiquity and complexity of system-on-chip (SoC) designs increase across electronic devices, the task of incorporating security into an SoC design flow poses significant challenges. Existing security solutions are inadequate to provide effective verification of modern SoC designs due to their limitations in scalability, comprehensiveness, and adaptability. On the other hand, Large Language Models (LLMs) are celebrated for their remarkable success in natural language understanding, advanced reasoning, and program synthesis tasks. Recognizing an opportunity, our research delves into leveraging the emergent capabilities of Generative Pre-trained Transformers (GPTs) to address the existing gaps in SoC security, aiming for a more efficient, scalable, and adaptable methodology. By integrating LLMs into the SoC security verification paradigm, we open a new frontier of possibilities and challenges to ensure the security of increasingly complex SoCs. This paper offers an in-depth analysis of existing works, showcases practical case studies, demonstrates comprehensive experiments, and provides useful promoting guidelines. We also present the achievements, prospects, and challenges of employing LLM in different SoC security verification tasks.

A zero-knowledge proof (ZKP) allows a party to prove to another party that it knows some secret, such as the solution to a difficult puzzle, without revealing any information about it. We propose a physical zero-knowledge proof using only a deck of playing cards for solutions to a pencil puzzle called \emph{Moon-or-Sun}. In this puzzle, one is given a grid of cells on which rooms, marked by thick black lines surrounding a connected set of cells, may contain a number of cells with a moon or a sun symbol. The goal is to find a loop passing through all rooms exactly once, and in each room either passes through all cells with a moon, or all cells with a sun symbol. Finally, whenever the loop passes from one room to another, it must go through all cells with a moon if in the previous room it passed through all cells with a sun, and visa-versa. This last rule constitutes the main challenge for finding a physical zero-knowledge proof for this puzzle, as this must be verified without giving away through which borders the loop enters or leaves a given room. We design a card-based zero-knowledge proof of knowledge protocol for Moon-or-Sun solutions, together with an analysis of their properties. Our technique of verifying the alternation of a pattern along a non-disclosed path might be of independent interest for similar puzzles.

Event date: 23 March to 24 March 2024
Submission deadline: 22 November 2023
Notification: 22 January 2024

We are looking for a postdoc to work with us on lattice-based cryptography. Broadly speaking, this is to build/analyse practical post-quantum privacy-preserving primitives and protocols.

Job ad: https://www.kcl.ac.uk/jobs/076525-research-fellowresearch-associate-in-cryptography

Closing date: 31 January 2024

Closing date for applications:

Contact: Martin Albrecht <martin.albrecht@kcl.ac.uk>

More information: https://martinralbrecht.wordpress.com/2023/10/12/postdoc-positions/

Aarhus University - an international top-100 University - has made an ambitious strategic investment in recruitment to expand the Department of Computer Science. We expect to hire four candidates in 2024. The department has world-class research groups within "Algorithms, Data Structures and Foundations of Machine Learning", “Data-Intensive Systems", "Cryptography and Security", "Computational Complexity and Game Theory", "Logic and Semantics", "Ubiquitous Computing and Interaction", “Human Computer Interaction (HCI)", and "Programming Languages”. We encourage applicants to strengthen the above groups. Additionally, we in particular wish to expand competencies within Machine Learning/Artificial Intelligence, NLP/Large Language Models, Quantum Computing, Quantum Cryptography, Economics and Computation, Systems and Networks, as well as Software Engineering. We are looking for both tenure-track Assistant professors and Associate professors, and we generally encourage candidates within all areas of Computer Science – not restricted to the above – to apply.

Closing date for applications:

Contact: Kaj Grønbæk, Professor, Head of Department, e-mail: kgronbak@cs.au.dk

More information: https://cs.au.dk/about-us/vacancies/job/aarhus-university-is-hiring-assistant-and-associate-professors-to-contribute-to-the-future-of-the-department-of-computer-science-2

We are looking for a strong PhD-candidate. There may be possibilities for a postdoc position on the project “Verified voting protocols and blockchains”.

Deadline:1 November 2023. https://phd.nat.au.dk/for-applicants/open-calls/november-2023/verified-voting-protocols-and-blockchains

The PhD positions include full tuition waiver and a very competitive scholarship. Aarhus University provides international students with a safe and stable environment, a high standard of living and a wealth of social opportunities. Besides having an excellent reputation that enables our PhD graduates to find outstanding employment prospects, Aarhus University offers attractive working conditions, research support and campus resources.

https://cs.au.dk/education/phd/

https://international.au.dk/

This project is supported by the Danish DIREC research center. It is a collaboration between Aarhus University, the Alexandra Institute and Concordium ApS. The aim of the project is work towards secure implementations of Blockchain Voting Governance Protocols and Internet Voting Protocols.

Voting and blockchains are intimately connected. Voting is used in blockchains for consensus, governance, and decentralized organizations. Conversely, elections are based on trust, which means that election systems ideally should be based on algorithms and data structures that are already trusted. Blockchains provide such a technology. They provide a trusted bulletin board, which can be used as part of some voting protocols. Moreover, voting crucially depends on establishing the identity of the voter to avoid fraud and to establish eligibility verifiability. Decades of research in voting protocols have shown how difficult it is to combine the privacy of the vote with the auditability of the election outcome. It is easy to achieve one without the other, but hard to combine both into one protocol. Thus, the topic of this research proposal is to investigate voting protocols and their relation to blockchains. The team will work on security proofs of these protocols and their implementations.

Closing date for applications:

Contact: Bas Spitters

More information: https://phd.nat.au.dk/for-applicants/open-calls/november-2023/verified-voting-protocols-and-blockchains

a16z crypto research is a new kind of multidisciplinary lab that bridges the worlds of academic theory and industry practice to advance the science and technology of the next generation of the internet. In addition to fundamental research, we collaborate with portfolio companies to solve hard technical and conceptual problems. Research interns will have the opportunity to learn from the firm’s investment and engineering teams, although this is a research role with no responsibility for investment decisions. We are seeking students with a strong research background and an interest in blockchains and web3 to join the group for the summer. Specific research areas of interest include cryptography, security, distributed computing, economics (both micro and macro), incentives, quantitative finance, political science and governance, and market and mechanism design. This list is not exhaustive and we encourage applicants with different backgrounds who may have unique perspectives on the space to apply.

Closing date for applications:

Contact: Joseph Bonneau

More information: https://a16z.com/about/jobs/?gh_jid=5766443003

We optimise the verification of the SQIsign signature scheme. By using field extensions in the signing procedure, we are able to significantly increase the amount of available rational $2$-power torsion in verification, which achieves a significant speed-up. This, moreover, allows several other speed-ups on the level of curve arithmetic. We show that the synergy between these high-level and low-level improvements gives significant improvements, making verification $2.65$ times faster, or up to $4.40$ times when using size-speed trade-offs, without degrading the performance of signing.

Fault attacks impose a serious threat against the practical implementations of cryptographic algorithms. Statistical Ineffective Fault Attacks (SIFA), exploiting the dependency between the secret data and the fault propagation overcame many of the known countermeasures. Later, several countermeasures have been proposed to tackle this attack using error detection methods. However, the efficiency of the countermeasures, in part governed by the number of error checks, still remains a challenge. In this work, we propose a fault countermeasure, StaTI, based on threshold implementations and linear encoding techniques. The proposed countermeasure protects the implementations of cryptographic algorithms against both side-channel and fault adversaries in a non-combined attack setting. We present a new composable notion, stability, to protect a threshold implementation against a formal gate/register-faulting adversary. Stability ensures fault propagation, making a single error check of the output suffice. To illustrate the stability notion, first, we provide stable encodings of the XOR and AND gates. Then, we present techniques to encode threshold implementations of S-boxes, and provide stable encodings of some quadratic S-boxes together with their security and performance evaluation. Additionally, we propose general encoding techniques to transform a threshold implementation of any function (e.g., non-injective functions) to a stable one. We then provide an encoding technique to use in symmetric primitives which encodes state elements together significantly reducing the encoded state size. Finally, we used StaTI to implement a secure Keccak on FPGA and report on its efficiency.

At ASIACRYPT 2019, Zhang proposed a near collision attack on A5/1 claiming to recover the 64-bit A5/1 state with a time complexity around $2^{32}$ cipher ticks with negligible memory requirements. Soon after its proposal, Zhang's near collision attack was severely challenged by Derbez \etal who claimed that Zhang's attack cannot have a time complexity lower than Golic's memoryless guess-and-determine attack dating back to EUROCRYPT 1997. In this paper, we study both the guess-and-determine and the near collision attacks for recovering A5/1 states with negligible memory complexities. Firstly, we propose a new guessing technique called the \emph{move guessing technique} that can construct linear equation filters in a more efficient manner. Such a technique can be applied to both guess-and-determine and collision attacks for efficiency improvements. Secondly, we take the filtering strength of the linear equation systems into account for complexity analysis. Such filtering strength are evaluated with practical experiments making the complexities more convincing. Based on such new techniques, we are able to give 2 new guess-and-determine attacks on A5/1: the 1st attack recovers the internal state $\vec{s}^0$ with time complexity $2^{43.92}$; the 2nd one recovers a different state $\vec{s}^1$ with complexity $2^{43.25}$. We also revisit Golic's guess-and-determine attack and Zhang's near collision attacks. According to our detailed analysis, the complexity of Golic's $\vec{s}^1$ recovery attack is no lower than $2^{46.04}$, higher than the previously believed $2^{43}$. On the other hand, Zhang's near collision attack recovers $\vec{s}^0$ with the time complexity $2^{53.19}$: such a complexity can be further lowered to $2^{50.78}$ with our move guessing technique.

The security of blockchain protocols is a combination of two properties: safety and liveness. It is well known that no blockchain protocol can provide both to sleepy (intermittently online) clients under adversarial majority. However, safety is more critical in that a single safety violation can cause users to lose money. At the same time, liveness must not be lost forever. We show that, in a synchronous network, it is possible to maintain safety for all clients even during adversarial majority, and recover liveness after honest majority is restored. Our solution takes the form of a recovery gadget that can be applied to any protocol with certificates (such as HotStuff, Streamlet, Tendermint, and their variants).