International Association
for Cryptologic Research

Recently, Picnic3 has introduced several alternative LowMC instances, which prompts the cryptanalysis competition for LowMC. In this paper, we provide new solutions to the competition with full S-box layers under single-data complexity. First, we present a new guess-and-determine attack framework that achieves the best trade-off in complexity, while effectively enhancing two algorithms applicable to 2-round LowMC cryptanalysis. Next, we present a new meet-in-the-middle attack framework for 2-/3-round LowMC, which can gradually reduce the number of variables and narrow down the range of candidate keys in stages. As a result, our 3-stage MITM attacks have both lower time complexity and memory complexity than the best previous 2-round attacks proposed by Banik et al. at ASIACRYPT 2021, with memory reduced drastically by a factor of $ 2^{29.7} \sim 2^{70.4} $.

We present an efficient zero-knowledge argument of knowledge system customized for the Paillier cryptosystem. Our system enjoys sublinear proof size, low verification cost, and acceptable proof generation effort, while also supporting batch proof generation/verification. Existing works specialized for Paillier cryptosystem feature linear proof size and verification time. Using existing sublinear argument systems for generic statements (e.g., zk-SNARK) results in unaffordable proof generation cost since it involves translating the relations to be proven into an inhibitive large Boolean or arithmetic circuit over a prime order field. Our system does not suffer from these limitations.

The core of our argument systems is a constraint system defined over the ring of residue classes modulo a composite number, together with novel techniques tailored for arguing binary values in this setting. We then adapt the approach from Bootle et al. (EUROCRYPT 2016) to compile the constraint system into a sublinear argument system. Our constraint system is generic and can be used to express typical relations in Paillier cryptosystems including range proof, correctness proof, relationships between bits of plaintext, relationships of plaintexts among multiple ciphertexts, and more. Our argument supports batch proof generation and verification, with the amortized cost outperforming state-of-the-art protocol specialized for Paillier when the number of Paillier ciphertext is in the order of hundreds.

We report an end-to-end prototype and conduct comprehensive experiments across multiple scenarios. Scenario 1 is Paillier with packing. When we pack 25.6K bits into 400 ciphertexts, a proof that all these ciphertexts are correctly computed is 17 times smaller and is 3 times faster to verify compared with the naive implementation: using 25.6K OR-proofs without packing. Furthermore, we can prove additional statements almost for free, e.g., one can prove that the sum of a subset of the witness bits is less than a threshold t. Another scenario is range proof. To prove that each plaintext in 200 Paillier ciphertexts is of size 256 bits, our proof size is 10 times smaller than the state-of-the-art. Our analysis suggests that our system is asymptotically more efficient than existing protocols, and is highly suitable for scenarios involving a large number (more than 100) of Paillier ciphertexts, which is often the case for data analytics applications.

With the widespread development of cloud storage, searching over the encrypted data (without decryption) has become a crucial issue. Public key authenticated encryption with keyword search (PAEKS) retrieves encrypted data, and resists inside keyword guessing attacks (IKGAs). Most PAEKS schemes cannot support access control in multi-receiver models. To address this concern, attribute-based authenticated encryption with keyword search (ABAEKS) has been studied. However, the access privilege for the ciphertext may change, and the conventional cryptographic primitives are not resistant to quantum computing attacks, which exhibits a limited applicability and poor security for cloud storage. In this paper, we propose RABAEKS, the first post-quantum revocable attribute-based authenticated encrypted search scheme for multi-receiver cloud storage. Our design enables cloud server enforces the access control of data receivers in the search process. For practical consideration, we further introduce a revocation mechanism of data receivers, which makes the access control more dynamic. We then define and rigorously analyze the security our scheme. Through the performance evaluations and comparisons, our computational overhead of ciphertext generation, trapdoor generation and search algorithm are at least 20×, 1.67× and 1897× faster than prior arts, respectively, which is practical for cloud storage.

Clinical trials are crucial in the development of new medical treatment methods. To ensure the correctness of clinical trial results, medical institutes need to collect and process large volumes of participant data, which has prompted research on privacy preservation and data reliability. However, existing solutions struggle to resolve the trade-off between them due to the trust gap between the physical and digital worlds, limiting their practicality. To tackle the issues above, we present Kalos, a novel authentication scheme for clinical trials. Kalos leverages diversified cryptographic tools, such as card-based anonymous credential and zero-knowledge proof to achieve authentication with visual verification and selective disclosure of attributes. It has properties such as unforgeability, blindness, privacy preservation, and human-binding that support hierarchical auditability and data de-duplication to enhance the reliability of clinical trials. We then provide the security and performance analysis of Kalos to show its potential to be deployed in the medical consumer electronics scenario. The computational cost of the smartcard is irrespective of the number of certified attributes, and the total computational cost of Kalos is within tens of milliseconds with the commonly used number of attributes.

At CRYPTO 2019, A. Gohr introduced Neural Differential Cryptanalysis by applying deep learning to modern block cipher cryptanalysis. Surprisingly, the resulting neural differential distinguishers enabled a new state-of-the-art key recovery complexity for 11 rounds of SPECK32. As of May 2024, according to Google Scholar, Gohr’s article has been cited 178 times. The wide variety of targets, techniques, settings, and evaluation methodologies that appear in these follow-up works grants a careful systematization of knowledge, which we provide in this paper. More specifically, we propose a taxonomy of these 178 publications and focus on the 50 that deal with differential neural distinguishers to systematically review and compare them. We then discuss two challenges for the field, namely comparability of neural distinguishers and scaling.

Rollups are special applications on distributed state machines (aka blockchains) for which the underlying state machine only logs, but does not execute transactions. Rollups have become a popular way to scale applications on Ethereum and there is now growing interest in running rollups on Bitcoin. Rollups scale throughput and reduce transaction costs by using auxiliary machines that have higher throughput and lower cost of executing transactions than the underlying blockchain. State updates are periodically posted to the underlying blockchain and either verified directly through succinct cryptographic proofs (zk rollups) or can be challenged for a defined period of time in a verifiable way by third parties (optimistic rollups). However, once computation is removed as a bottleneck, communication quickly becomes the new bottleneck. The critical service the underlying blockchain provides in addition to verification is data availability: that necessary data can always be recovered upon request. While broadcasting transaction data is one way to ensure this, it requires communication blowup linear in the number of participating nodes. Verifiable information dispersal (VID) systems achieve sublinear blowup in the same participation model and the same security assumptions as Ethereum, where all nodes have a strong public-key identity. It was not known how to do so in the same permissionless model as Bitcoin, where participants are unauthenticated and participation is dynamic. We construct a VID system that is secure under the same model as Bitcoin, with one minimal additional requirement on the existence of reliable participants. Our system uses a state machine replication (SMR) protocol (e.g., Bitcoin) as a black box, and is therefore backward compatible. We implemented the system on top of Bitcoin core with the Regression Test Network (regtest), and our analysis shows that it reduces communication costs by more than 1,000x and latency by more than 10x.

This article addresses the issue of efficient and safe (de)compression of $\mathbb{F}_{\!q}$-points on an elliptic curve $E$ over a highly $2$-adic finite field $\mathbb{F}_{\!q}$ of characteristic $5$ or greater. The given issue was overlooked by cryptography experts, probably because, until recently, such fields were not in trend. Therefore, there was no difficulty (with rare exceptions) in finding a square $\mathbb{F}_{\!q}$-root. However, in our days, fields with large $2$-adicities have gained particular popularity in the ZK (zero-knowledge) community, despite the fact that $\sqrt{\cdot} \in \mathbb{F}_{\!q}$ should be computed via more sophisticated square-root algorithms such as (Cipolla-Lehmer-)Müller's one. The article explains why the classical $x$-coordinate (de)compression method based on Müller's algorithm often contains Achilles' heel to successfully perform a novel fault attack, which also fits the definition of a (D)DoS attack. In a nutshell, the trouble stems from the non-deterministic initialization of Müller's algorithm.

Moreover, the article suggests a countermeasure, namely an alternative (still simple) (de)compression method that completely prevents the discovered attack whenever the curve $E/\mathbb{F}_{\!q}$ is of even order. In particular, all twisted Edwards (i.e., Montgomery) curves are relevant. The decompression stage of the new method equally suffers from one square-root extraction in $\mathbb{F}_{\!q}$. But the corresponding quadratic residue is inherently equipped with additional information, providing an opportunity to launch Müller's algorithm immediately from its main deterministic part. In turn, the compression stage of the new method remains (almost) free as well as for the $x$-coordinate method.

SNOVA is a multivariate signature scheme submitted to the NIST project for additional signature schemes by Cho, Ding, Kuan, Li, Tseng, Tseng, and Wang. With small key and signature sizes good performance, SNOVA is one of the more efficient schemes in the competition, which makes SNOVA an important target for cryptanalysis. In this paper, we observe that SNOVA implicitly uses a structured version of the ``whipping'' technique developed for the MAYO signature scheme. We show that the extra structure makes the construction vulnerable to new forgery attacks. Concretely, we formulate new attacks that reduce the security margin of the proposed SNOVA parameter sets by a factor between $2^{8}$ and $2^{39}$. Furthermore, we show that large fractions of public keys are vulnerable to more efficient versions of our attack. For example, for SNOVA-37-17-2, a parameter set targeting NIST's first security level, we show that roughly one out of every $500$ public keys is vulnerable to a universal forgery attack with bit complexity $2^{97}$, and roughly one out of every $143000$ public keys is even breakable in practice within a few minutes.

Order fairness in the context of distributed ledgers has received recently significant attention due to a range of attacks that exploit the reordering and adaptive injection of transactions (violating what is known as “input causality”). To address such concerns an array of definitions for order fairness has been put forth together with impossibility and feasibility results highlighting the difficulty and multifaceted nature of fairness in transaction serialization. Motivated by this we present a comprehensive modeling of order fairness capitalizing on the universal composition (UC) setting. Our results capture the different flavors of sender order fairness and input causality (which is arguably one of the most critical aspects of ledger transaction processing with respect to serialization attacks) and we parametrically illustrate what are the limits of feasibility for realistic constructions via an impossibility result. Our positive result, a novel distributed ledger protocol utilizing trusted enclaves, complements tightly our impossibility result, hence providing an optimal sender order fairness ledger construction that is also eminently practical.

Lattice-based identity-based encryption having both efficiency and provable security in the standard model is currently still a challenging task and has drawn much attention. In this work, we introduce a new IBE construction from NTRU lattices in the standard model, based on the framework proposed by Agrawal, Boneh, and Boyen (EUROCRYPT 2010). Particularly, by introducing the NTRU trapdoor and the RingLWE computational assumption, we remove a crux restriction of the column number and obtain a more compact IBE construction in the standard model. Besides, we provide a concrete implementation and detailed performance results with a comparison of previous works in terms of the security model and the assumption, which demonstrates the advantage of our construction.

The recent works of Ananth et al. (ITCS 2022) and Bartusek et al. (Eurocrypt 2023) initiated the study of pre-constrained cryptography which achieves meaningful security even against the system authority. In this work we significantly expand this area by defining several new primitives and providing constructions from simple, standard assumptions as follows.

- Pre-Constrained Encryption. We define a weaker notion of pre-constrained encryption (PCE), as compared to the work of Ananth et al. which nevertheless suffices for all known applications. We then provide constructions for general constraints, satisfying malicious security from a variety of assumptions including DDH, LWE, QR and DCR. Our LWE based construction satisfies unconditional security against malicious authorities. In contrast, the construction by Ananth et al. supporting general constraints must rely (inherently) on strong assumptions like indistinguishability obfuscation. - Pre-Constrained Static Functional Encryption and Input Obfuscation. We provide a new definition for pre-constrained functional encryption in the so-called static setting (PCSFE) where the functions to be embedded in secret keys are specified during the setup phase. We provide constructions for PCSFE supporting general constraints, with security against malicious authorities. As in the case of PCE, our first construction can be instantiated from a variety of assumptions including DDH, LWE, QR and DCR. Our second, LWE based construction satisfies unconditional security against malicious authorities. We also study succinctness in PCSFE, where the public key is sublinear in the number of function keys. We provide the first construction from LWE in the random oracle model. We additionally provide a heuristic construction in the standard model using lattices together with groups. - Pre-Constrained Input Obfuscation. We define and provide the first construction of pre-constrained input obfuscation from the same assumptions as those used to instantiate PCSFE. - Pre-Constrained Group Signatures. For pre-constrained group signatures (PCGS), we provide the first construction supporting general constraints, achieving unconditional security against malicious authorities from the LWE assumption. The only other construction by Bartusek et al. supports the restricted set/database membership constraint, and achieves computational security from the DDH assumption (and is therefore quantum insecure).

In this paper, we propose Greyhound, the first concretely efficient polynomial commitment scheme from standard lattice assumptions. At the core of our construction lies a simple three-round protocol for proving evaluations for polynomials of bounded degree $N$ with verifier time complexity $O(\sqrt{N})$. By composing it with the LaBRADOR proof system (CRYPTO 2023), we obtain a succinct proof of polynomial evaluation (i.e. polylogarithmic in $N$) that admits a sublinear verifier runtime.

To highlight practicality of Greyhound, we provide implementation details including concrete sizes and runtimes. Notably, for large polynomials of degree at most $N=2^{30}$, the scheme produces evaluation proofs of size $53$KB, which is more than $10^4$ times smaller than the recent lattice-based framework, called SLAP (EUROCRYPT 2024), and around three orders of magnitude smaller than Ligero (CCS 2017) and Brakedown (CRYPTO 2023).

Identity-based matchmaking encryption (IB-ME) is an advanced encryption scheme that enables a sender and a receiver to specify each of identity. In general, from the aspect of abilities for adversaries, we have two flavors of security for encryption schemes chosen plaintext attacks (CPA) security and chosen ciphertext attacks (CCA) security. Compared to CPA security, CCA security can capture active adversaries, then it has been recognized as a desirable one.

In this paper, we investigate the CCA security for IB-ME. Concretely, we provide the following three contributions. (i) A method to obtain a CCA secure IB-ME scheme in the standard model based on our new primitive called hierarchical IB-ME (HIB-ME) along with strong one-time signature. (ii) A construction of HIB-ME based on hierarchical identity-based encryption and hierarchical identity-based signature. (iii) A variant of the first method to get an IB-ME scheme satisfying slightly tweaked CCA security solely based on a CPA secure IB-ME scheme (without strong one-time signature). We believe that this new type of CCA security is a reasonable one for IB-ME.

This paper presents Raccoon, a lattice-based signature scheme submitted to the NIST 2022 call for additional post-quantum signatures. Raccoon has the specificity of always being masked. Concretely, all sensitive intermediate values are shared into ? parts. The main design rationale of Raccoon is to be easy to mask at high orders, and this dictated most of its design choices, such as the introduction of new algorithmic techniques for sampling small errors. As a result, Raccoon achieves a masking overhead $?(? \log ?)$ that compares favorably with the overheads $?(?^2 \log ?)$ observed when masking standard lattice signatures. In addition, we formally prove the security of Raccoon in the ?-probing model: an attacker is able to probe $? ≤ ? −1$ shares during each execution of the main algorithms (key generation, signing, verification). While for most cryptographic schemes, the black-box ?-probing security can be studied in isolation, in Raccoon this analysis is performed jointly. To that end, a bridge must be made between the black-box game-based EUF-CMA proof and the usual simulation proofs of the ISW model (CRYPTO 2003). We formalize an end-to-end masking proof by deploying the probing EUF-CMA introduced by Barthe et al.(Eurocrypt 2018) and exhibiting the simulators of the non-interference properties (Barthe et al. CCS 2016). The proof is divided into three novel parts: - a simulation proof in the ISW model that allows to propagate the dependency to a restricted number of inputs and random coins, - a game-based proof showing that the security of Raccoon with probes can be reduced to an instance of Raccoon with smaller parameters, - a parameter study to ensure that the smaller instance is secure, using a robust generalization of the Rényi divergence. While we apply our techniques to Raccoon, we expect that the algorithmic and proof techniques we introduce will be helpful for the design and analysis of future masking-friendly schemes.

In the last fifteen years, there has been a steady stream of works combining differential privacy with various other cryptographic disciplines, particularly that of multi-party computation, yielding both practical and theoretical unification. As a part of that unification, due to the rich definitional nature of both fields, there have been many proposed definitions of differential privacy adapted to the given use cases and cryptographic tools at hand, resulting in computational and/or distributed versions of differential privacy. In this work, we offer a systemization of such definitions, with a focus on definitions that are both computational and tailored for a multi-party setting. We order the definitions according to the distribution model and computational perspective and propose a viewpoint on when given definitions should be seen as instantiations of the same generalised notion. The ordering highlights a clear, and sometimes strict, hierarchy between the definitions, where utility (accuracy) can be traded for stronger privacy guarantees or lesser trust assumptions. Further, we survey theoretical results relating the definitions to each other and extend some such results. We also discuss the state of well-known open questions and suggest new open problems to study. Finally, we consider aspects of the practical use of the different notions, hopefully giving guidance also to future applied work.

Blind signatures represent a class of cryptographic primitives enabling privacy-preserving authentication with several applications such as e-cash or e-voting. It is still a very active area of research, in particular in the post-quantum setting where the history of blind signatures has been hectic. Although it started to shift very recently with the introduction of a few lattice-based constructions, all of the latter give up an important characteristic of blind signatures (size, efficiency, or security under well-known assumptions) to achieve the others. In this paper, we propose another design which revisits the link between the two main procedures of blind signatures, namely issuance and showing, demonstrating that we can significantly alleviate the second one by adapting the former. Concretely, we show that we can harmlessly inject excess randomness in the issuance phase, and then recycle the entropy surplus during showing to decrease the complexity of the zero-knowledge proof which constitutes the main component of the signature. This leads to a blind signature scheme with small sizes, low complexity, and that still relies on well-known lattice assumptions.

From 2022, Korean Post-Quantum Cryptography (KpqC) Competition has been held. Among the Round 1 algorithms of KpqC, eight algorithms were selected in December 2023. To evaluate the algorithms, the performance is critical factor. However, the performance of the algorithms submitted to KpqC was evaluated in different development environments. Consequently, it is difficult to compare the performance of each algorithm fairly, because the measurements were not conducted in the identical development environments. In this paper, we introduce KpqClean ver2, the successor to the KpqClean project. KpqClean ver2 provides comprehensive benchmark analysis results for all KpqC Round 2 algorithms across various environments (Ryzen, Intel, and aarch64). This framework includes both a ``clean'' implementation and an ``avx2'' implementation of the KpqC Round 2 candidate algorithms. To benchmark the algorithms, we not only removed external library dependencies from each algorithm but also integrated the same source code for common algorithms (such as AES, SHA2, SHAKE, and etc.) to enable more accurate performance comparisons. The framework automatically recognizes the user’s environment, providing easy benchmarking for all users without the need for separate settings. This study also includes memory usage analysis using Valgrind for each algorithm and function usage proportion analysis during the execution of each cryptographic algorithm using Xcode's profiling tool. Finally we show that the practical strength of KpqC algorithms in terms of execution timing and memory usages. This result can be utilized for the understanding of KpqC finalist in terms of performance.

The PC chairs of Crypto 2025 are soliciting nominations (including self-nominations) for program committee service. The bulk of the work will take place from mid-February to the first week of May. Each PC member will be expected to review approximately 15 papers.

Please submit nominations via this form: https://forms.gle/8ufq56Q3TujGc3oN6

The College of Science seeks a diverse and inclusive workforce and is committed to equality of opportunity. We welcome applications from all and recruit on the basis of merit, regardless of age, race, gender, religion, marital status and family responsibilities, or disability. The Division of Mathematical Sciences in the School of Physical and Mathematical Sciences at NTU provides a multidisciplinary academic program that provides students with a wide-ranging and up-to-date education. The Division of Mathematical Sciences invites applications for an Asst/Assoc Prof (Tenure Track/Tenured) position specializing in Post-Quantum Cryptography (PQC). This position focuses on advancing the field of PQC, which is critical in the era of quantum computing. Key Responsibilities Conduct pioneering research in post-quantum cryptography. ·Publish high-impact papers in leading journals and conferences. ·Secure research funding from competitive grants and industry partnerships. ·Mentor and supervise graduate students and postdoctoral researchers. ·Collaborate with interdisciplinary teams within the university and with external partners. ·Deliver engaging and effective teaching to both undergraduate and graduate students. ·Undertake essential administrative responsibilities within the School. Qualifications ·Doctoral degree in Mathematics, Computing Science, or a closely related field with a specialization in Post-Quantum Cryptography. ·Demonstrated excellence in research, evidenced by a strong publication record in reputable journals and conferences. ·Recognition in the research community, such as invited talks, awards, or memberships in professional societies. ·Proven ability to secure research funding (for Assoc Prof). ·Strong commitment to teaching and mentoring students. ·Excellent communication and collaboration skills. Application Procedure Required application documents: ·Cover letter ·Curriculum Vitae including a full publication list ·Statement of current and future research interest ·Teaching statement ·Names of at least three referees

Closing date for applications:

Contact: MAS, Search Chair MAS_Search@ntu.edu.sg

More information: https://ntu.wd3.myworkdayjobs.com/Careers/job/NTU-Main-Campus-Singapore/Assistant-Professor-Associate-Professor--Tenure-Track-Tenured--in-Post-Quantum-Cryptography--PQC-_R00018013

This tutorial focuses on describing the fundamental mathematical concepts and design decisions used in the two ``main'' lattice schemes standardized by NIST and included in the CNSA 2.0 algorithmic suite. They are the KEM / encryption scheme CRYSTALS-Kyber (ML-KEM) and the signature scheme CRYSTALS-Dilithium (ML-DSA) . In addition, we will also give the main ideas behind other lattice-based KEMs like Frodo and NTRU.