This is the NIST Threshold Call, calling for public submissions of multi-party threshold schemes, and other related crypto-systems, to support the United States’ National Institute of Standards and Technology (NIST) in gathering a public body of reference materials unadvanced cryptography. In a threshold scheme, a reference cryptographic primitive (e.g., signing, encryption, decryption, key generation) is computed in a distributed manner, while its private/secret key is or becomes secret-shared across various parties. The threshold schemes submitted in reply to this call will be interchangeable with a reference no threshold primitive of interest, in the sense that their outputs can be used interchangeably in a subsequent operation. The primitives of interest are organized into various categories, across two classes: Class N, for selected NIST-specified primitives; and Class S, for special primitives that are not specified by NIST but are threshold friendly or have useful functional features. The scope of Class S also includes fully homomorphic encryption, zero-knowledge proofs, and auxiliary gadgets. This document specifies submission phases, and the requirements for submitting a package, including a technical specification, a reference implementation, and a report on experimental evaluation. A subsequent phase of public analysis will support the elaboration of a characterization report, which may help assess new interests beyond the cryptographic techniques currently standardized by NIST, and may include recommendations for future processes.
Zero-knowledge proofs (ZKPs) are widely applied in digital economies, such as cryptocurrencies and smart contracts, for establishing trust and privacy between untrusted parties. Classical ZKPs rely on computational assumptions and are vulnerable to quantum attacks. While a recent advance suggests quantum-sound symmetric relativistic ZKPs for the graph three-coloring problem without computational assumptions, the high round complexity, which leads to unachievable runtime and overall randomness cost, renders them impractical for real-life deployment. To overcome this, we develop an efficient asymmetric relativistic ZKP protocol using relativistic bit commitments, and prove its quantum soundness by relating it to the nonlocal Clauser-Horne-Shimony-Holt (CHSH) game. Our protocol achieves a linear relationship between the round complexity and the number of edges, and thus significantly improves practical feasibility. In addition, we implement a proof-of-principle experiment which completes all interactive rounds in about 0.22 seconds and requires an overall randomness cost of 430.81 MB. Our work illustrates the powerful potential of integrating special relativity with quantum theory in trustless cryptography, paving the way for robust applications against quantum attacks in distrustful Internet environments. Zero-knowledge proofs can protect privacy online, but almost all current methods are vulnerable to quantum attacks. Here, the authors report an efficient relativistic protocol and experiment that resists quantum attacks and greatly reduces runtime, randomness cost and communication rounds.
Collision-resistant cryptographic hash functions (CRHs) are crucial for security, particularly for message authentication in Zero-knowledge Proof (ZKP) applications. However, traditional CRHs like SHA-2 or SHA-3, while optimized for CPUs, generate large circuits, rendering them inefficient in the ZK domain. Conversely, ZK-friendly hashes are designed for circuit efficiency but struggle on conventional hardware, often orders of magnitude slower than standard hashes due to their reliance on expensive finite field arithmetic. To bridge this performance gap, we present HashEmAll, a novel collection of FPGA-based realizations for three prominent ZK-friendly hashes: Griffin, Rescue-Prime, and Reinforced Concrete. Each offers distinct optimization profiles, with both area-optimized and latency-optimized variants available, allowing users to tailor hardware selection to specific application constraints regarding resource utilization and performance. Our extensive evaluation shows that latency-optimized HashEmAll designs outperform CPU implementations by at least $10 \times$, with the leading design achieving a $23 \times$ speedup. These gains are coupled with lower power consumption and compatibility with accessible FPGAs. Importantly, the highly parallel and pipelined architecture of HashEmAll enables significantly better practical scaling than CPU-based approaches towards building real-world ZKP applications, such as data commitments with Merkle Trees, by mitigating the hashing bottleneck for large trees. This highlights the suitability of HashEmAll for real-world ZKP applications involving large-scale data authentication. We also highlight the ability to translate the HashEmAll methodology to various ZK-friendly hash functions and different field sizes.
Satellite communication (SC) is an indispensable component of future communication systems due to its extensive coverage and flexibility. In this work, we investigate the fine-grained anonymous access technique, which not only ensures user equipments (UEs) privacy in the open SC environment but also enables satellites to enforce fine-grained access policies with low overhead. Firstly, we design a Merkle forest based framework that facilitates efficient UE attribute data synchronization, leveraging the broadcasting capability of satellites. Subsequently, we construct a zero-knowledge based protocol for UE authentication, key agreement, and handover in SC. The analysis demonstrates the protocol's resilience against prevalent attacks, and simulation results validate its practicality.
Classical symmetric cryptography interprets ciphers and hash functions as bit-based functions, that is, as functions between binary vector spaces. However, in the past decade, research and adoption of cryptographic protocols with advanced privacy-enhancing features, such as Fully Homomorphic Encryption, Multi-Party Computation and Zero-Knowledge proof systems, have accelerated. These privacy-enhancing protocols often have a novel feature: Their mathematical model is native over a prime field, whose characteristic p is significantly larger than 2. Applications of the aforementioned protocols often require a symmetric cipher for data encryption or a hash function for data compression. For efficiency reasons, two novel criteria must be satisfied: - A primitive should be native over a prime field, so it is modeled as function between vector spaces of characteristic p. - It should be possible to evaluate or represent a primitive with a low number of multiplications. Primitives satisfying these criteria are often summarized under the term Arithmetization-Oriented. To satisfy the second criterion, Arithmetization-Oriented primitives are often constructed by iterating relatively low-degree polynomials. However, this choice comes at a cost: Such primitive can also be modeled as a low-degree polynomial system for key or preimage recovery. Analyzing the complexity of polynomial system solving-based attacks poses a major problem in the design of Arithmetization-Oriented primitives. In practice, cryptodesigners often applied generic complexity bounds for cryptanalysis without proving the underlying assumptions. The aim of this manuscript is the development of tools for complexity estimations based on provable properties of a cryptographic polynomial system. We also apply our tools to the analysis of Arithmetization-Oriented Substitution-Permutation Network and Feistel ciphers. For early Arithmetization-Oriented primitives, our analysis reveals a large complexity gap between initial cryptanalysis and the capabilities of state-of-the-art polynomial system solving techniques.
Physical unclonable function (PUF) is a critical hardware primitive that provides unique identities for authenticating a large number of devices in the Industrial Internet of Things (IIoT). Most existing PUF-based schemes face challenge-response pair (CRP) leakage during machine-learning attack. Some studies that use hardware or time-consuming cryptographic operations to protect the PUF responses are expensive and unsuitable for existing IIoT devices. To address these issues, a lightweight and anonymous PUF-based authentication scheme is proposed for resource-constrained IIoTs. Using elliptic curve cryptography and zero-knowledge proof, a lightweight blinding mechanism is designed in the proposed scheme that prevents explicit CRP leakage and ensures anonymity. In addition, the authenticated keys are random with forward and backward secrecy. Moreover, the security of the proposed scheme is demonstrated using a random oracle model. Experimental results demonstrate that the proposed scheme is notably more efficient and practical for resource-constrained devices compared to other related schemes.
Open access
Physical Unclonable Functions (PUFs) and Hardware Security
This thesis explores the concept of zero-knowledge proofs and their application in zkVMs - virtual machines capable of generating proofs of correct computation without revealing private input. We begin by introducing fundamental cryptographic tools such as zk-SNARKs and zk-STARKs, along with supporting techniques such as lookup tables. We then analyze the architecture of two concrete zkVM implementations: RISC Zero and SP1. We describe their different approaches to proof systems, recursion mechanisms, and optimization strategies. In the final part, we present comparative benchmarks on various examples, highlighting their performance differences. The results show that RISC Zero produces smaller proofs and has faster verification, while SP1 is faster in proof generation and requires fewer computation cycles.
Increasing attention to digital identity and self-sovereign identity (SSI) is gaining momentum. SSI brings various benefits to natural persons, such as owning controls; conversely, digital identity systems in the real world require Sybil-resistance to comply with anti-money laundering (AML) and other needs. CanDID by Maram et al. proposed that decentralized digital identity systems may achieve Sybil-resistance and preserve privacy by utilizing multi-party computation (MPC), assuming a distributed committee of trusted nodes. Pass et al. proposed the formal abstraction of attested execution secure processors (AESPs) while equipping hardware-assisted security in mobile devices has become the norm. We first describe our proposal to utilize AESPs for building secure Sybil-resistant SSI systems, the architecture with a set of system protocols$\Pi ^{{\mathcal {G}}_{\mathtt {att}}}$, which brings drastic flexibility and efficiency compared to existing systems. In addition, we propose a novel scheme that enables users (holders) to request verifiers to verify their credentials without AESPs, and it further achieves unlinkability among credentials created for public verification. Our scheme introduces a simplified format for computed claims and commitment-based anonymous identifiers. We also describe a technique to utilize zero-knowledge membership proofs, in particular, “One-Out-of-Many Proofs”$\Sigma $-protocol by Groth and Kohlweiss, which can prove the existence of an expected credential without identifying it. Along with other techniques, such as utilizing the BBS+ signature scheme, we demonstrate how our scheme can achieve its goals with the extended anonymous and Sybil-resistant SSI system protocols$\Pi ^{{\mathcal {G}}_{\mathtt {att}}+}$. Entitling unlinkability among derived credentials in the anonymous Sybil-resistant SSI results in proper privacy preservation.
Joel Poncha Lemayian, Ghyslain Gagnon, Kaiwen Zhang, Pascal Giard
ABSTRACT Cryptocurrency blockchain networks safeguard digital assets using cryptographic keys, with wallets playing a critical role in generating, storing, and managing these keys. Wallets, typically categorized as hot and cold, offer varying degrees of security and convenience. However, they are generally software‐based applications running on microcontrollers. Consequently, they are vulnerable to malware and side‐channel attacks, allowing perpetrators to extract private keys by targeting critical algorithms, such as ECC, which processes private keys to generate public keys and authorize transactions. To address these issues, this work presents EthVault, the first hardware architecture for an Ethereum hierarchically deterministic cold wallet, featuring hardware implementations of key algorithms for secure key generation. Also, an ECC architecture resilient to side‐channel and timing attacks is proposed. Moreover, an architecture of the child key derivation function, a fundamental component of cryptocurrency wallets, is proposed. The design minimizes resource usage, meeting market demand for small, portable cryptocurrency wallets. FPGA implementation results validate the feasibility of the proposed approach. The ECC architecture exhibits uniform execution behavior across varying inputs, while the complete design utilizes only 27%, 7%, and 6% of LUTs, registers, and RAM blocks, respectively, on a Xilinx Zynq UltraScale+ FPGA.