International Association
for Cryptologic Research

Side-channel secure implementations of public-key cryptography algorithms must be able to load and store their secret keys safely. We describe WrapQ, a masking-friendly key management technique and encoding format for Kyber and Dilithium Critical Security Parameters (CSPs). WrapQ protects secret key integrity and confidentiality with a Key-Encrypting Key (KEK) and allows the keys to be stored on an untrusted medium. Importantly, its encryption and decryption processes avoid temporarily collapsing the masked asymmetric secret keys (which are plaintext payloads from the viewpoint of the wrapping primitive) into an unmasked format. We demonstrate that a masked Kyber or Dilithium private key can be loaded any number of times from a compact WrapQ format without updating the encoding in non-volatile memory. We also consider the keys-in-RAM use case (without the write-back restriction) and introduce Mask Compression, a technique that leverages fast, unmasked deterministic samplers. Mask compression saves working memory while reducing the need for true randomness and is especially useful when higher-order masking is applied in lattice cryptography. The techniques have been implemented in a side-channel secure hardware module. Kyber and Dilithium wrapping and unwrapping functions were validated with 100K traces of TVLA-type leakage assessment.

Timed commitment schemes, introduced by Boneh and Naor (CRYPTO 2000), can be used to achieve fairness in secure computation protocols in a simple and elegant way. The only known non-malleable construction in the standard model is due to Katz, Loss, and Xu (TCC 2020). This construction requires general-purpose zero knowledge proofs with specific properties, and it suffers from an inefficient commitment protocol, which requires the committing party to solve a computationally expensive puzzle.

We propose new constructions of non-malleable non-interactive timed commitments, which combine (an extension of) the Naor-Yung paradigm used to construct IND-CCA secure encryption with a non-interactive ZK proofs for a simple algebraic language. This yields much simpler and more efficient non-malleable timed commitments in the standard model.

Furthermore, our constructions also compare favourably to known constructions of timed commitments in the random oracle model, as they achieve several further interesting properties that make the schemes very practical. This includes the possibility of using a homomorphism for the forced opening of multiple commitments in the sense of Malavolta and Thyagarajan (CRYPTO 2019), and they are the first constructions to achieve public verifiability, which seems particularly useful to apply the homomorphism in practical applications.

Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli-$X$ or $Z$ measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the $XY$-plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the $XY$-plane up to a Pauli-$Z$ correction.

A new CRT-based positive (non-zero) secret-sharing scheme with perfect information-theoretic (PIT) security and multiplicative homomorphism is presented. The scheme is designed to support the evaluation of multiplications of non-zero secrets of multiplicative groups.

Our CRT-based scheme is partially homomorphic, supporting homomorphic multiplications. Nevertheless, our scheme has the potential to be regarded as fully homomorphic for practical scenarios, such as bounded-sized multi-cloud databases.

FALCON and Crystals-Dilithium are the digital signatures algorithms selected as NIST PQC standards at the end of the third round. FALCON has the advantage of the shortest size of the combined public key and signature but has the disadvantage of the relatively long signing time. Since FALCON algorithm is faithfully designed based on theoretical security analysis, the implementation of the algorithms is quite complex and needs considerable complexity. In order to implement the FALCON algorithm, the isochronous discrete Gaussian sampling algorithm should be used to prevent the side-channel attack, which causes a longer signature time. Also, FFT operations with floating-point numbers should be performed in FALCON, and they cause difficulty in applying the masking technique, making it vulnerable to side-channel attacks. We propose the Peregrine signature algorithm by devising two methods to make the signing algorithm of the FALCON scheme efficient. To reduce the signing time, Peregrine replaces the discrete Gaussian sampling algorithm with the sampling algorithm from the centered binomial distribution in the key generation algorithm and the signing algorithm by adjusting the encryption parameters. Also, it replaces the fast Fourier transform (FFT) operations of floating-point numbers with the number theoretic transform (NTT) operations of integers represented in residue number system (RNS), making the scheme faster and easy to be applied with a masking technique to prevent the side channel attack.

In 2008 Satoshi wrote the first permissionless consensus protocol, known as Nakamoto Consensus (NC), and implemented in Bitcoin. A large body of research was dedicated since to modify and extend NC, in various aspects: speed, throughput, energy consumption, computation model, and more. One line of work focused on alleviating the security-speed tradeoff which NC suffers from by generalizing Satoshi's blockchain into a directed acyclic graph of blocks, a block DAG. Indeed, the block creation rate in Bitcoin must be suppressed in order to ensure that the block interval is much smaller than the worst case latency in the network. In contrast, the block DAG paradigm allows for arbitrarily high block creation rate and block sizes, as long as the capacity of nodes and of the network backbone are not exceeded. Still, these protocols, as well as other permissionless protocols, assume an a priori bound on the worst case latency, and hardcode a corresponding parameter in the protocol. Confirmation times then depend on this worst case bound, even when the network is healthy and messages propagate very fast. In this work we set out to alleviate this constraint, and create the first permissionless protocol which contains no a priori in-protocol bound over latency. DAG-KNIGHT is thus responsive to network conditions, while tolerating a corruption of up to 50% of the computational power (hashrate) in the network. To circumvent an impossibility result by Pass and Shi, we require that the client specifies locally an upper bound over the maximum adversarial recent latency in the network. DAG-KNIGHT is an evolution of the PHANTOM paradigm, which is a parameterized generalization of NC.

We present a novel code-based digital signature scheme, called enhanced pqsigRM for post-quantum cryptography (PQC). This scheme is based on a modified Reed--Muller (RM) code, which reduces the signature size and verification time compared with existing code-based signature schemes. In fact, it strengthens pqsigRM submitted to NIST for post-quantum cryptography standardization. The proposed scheme has the advantage of the short signature size and fast verification and uses public codes that are more difficult to distinguish from random codes. We use $(U,U+V)$-codes with the high-dimensional hull to overcome the disadvantages of code-based schemes. The proposed decoder samples from coset elements with small Hamming weight for any given syndrome and efficiently finds such an element. Using a modified RM code, the proposed signature scheme resists various known attacks on RM-code-based cryptography. It has advantages on signature size, verification time, and proven security. For 128 bits of classical security, the signature size of the proposed signature scheme is 512 bytes, which corresponds to 1/4.7 of that of CRYSTALS-DILITHIUM, and the number of median verification cycles is 759,248, which corresponds to the twice of that of CRYSTALS-DILITHIUM.

There are a multitude of Blockchain-based physical infrastructure systems, ranging from decentralized 5G wireless to electric vehicle charging networks. These systems operate on a crypto-currency enabled token economy, where node suppliers are rewarded with tokens for enabling, validating, managing and/or securing the system. However, today's token economies are largely designed without infrastructure systems in mind, and often operate with a fixed token supply (e.g., Bitcoin). Such fixed supply systems often encourage early adopters to hoard valuable tokens, thereby resulting in reduced incentives for new nodes when joining or maintaining the network. This paper argues that token economies for infrastructure networks should be structured differently - they should continually incentivize new suppliers to join the network to provide services and support to the ecosystem. As such, the associated token rewards should gracefully scale with the size of the decentralized system, but should be carefully balanced with consumer demand to manage inflation and be designed to ultimately reach an equilibrium. To achieve such an equilibrium, the decentralized token economy should be adaptable and controllable so that it maximizes the total utility of all users, such as achieving stable (overall non-inflationary) token economies. Our main contribution is to model infrastructure token economies as dynamical systems - the circulating token supply, price, and consumer demand change as a function of the payment to nodes and costs to consumers for infrastructure services. Crucially, this dynamical systems view enables us to leverage tools from mathematical control theory to optimize the overall decentralized network’s performance. Moreover, our model extends easily to a Stackelberg game between the controller and the nodes, which we use for robust, strategic pricing. In short, we develop predictive, optimization-based controllers that outperform traditional algorithmic stablecoin heuristics by up to $2.4 \times$ in simulations based on real demand data from existing decentralized wireless networks.

We instantiate the hash-based post-quantum stateful signature schemes LMS and LMS described in RFC 8554 and NIST SP 800-208 with SM3, and report on the results of the preliminary performance test.

Quantum computing threatens classical cryptography, leading to the search for stronger alternatives. The cryptographic approach based on lattices is considered as a viable option. Schemes with that approach use Gaussian sampling, a design which brings along two concerns: efficiency and information leakage. This work addresses those concerns in the RLWE formulation, for digital signatures. Efficiency mitigation uses the central limit theorem, and the Walsh–Hadamard transform, whereas the information leakage risk is reduced via isochronous implementation. Up to \( 2^{23} \) samples are queried, and the results are compared against those of a cumulative distribution table sampler. Statistical metrics show the suitability of the presented sampler in a number of contexts.

For arbitrary finite field F_q, q > 2 we prove that known qregular bipartite algebraic graphs A(n; q) existence on 2q^n vertices have girth 2n or 2n + 2. Similar result is formulated for more general graphs A(n; K) defined over general commutative integrity ring K. The impact of these results on Extremal Graph Theory and graph based Algebraic Cryptography is discussed.

We show that a Beaufort cipher is simultaneously both a quagmire 1 and a quagmire 2 cipher, which includes it in the set of quagmire 4 ciphers as well, albeit as a degenerate one. The Beaufort is one of a family of ciphers that share this property.

In our survey of the various zk-EVM constructions, it becomes apparent that verifiable storage of the EVM state starts to be one of the dominating costs. This is not surprising because a big differentiator of EVM from UTXO is exactly the ability to carry states and, most importantly, their transitions, i.e., EVM is a **state** machine. In other words, to build an efficient zk-EVM, one must first build an efficient verifiable state. The common approach, which has been used in production, is a Merkle forest to authenticate the memory that would be randomly accessed within zk-SNARK, and optimize the verification of such memory accesses. In this note we describe a way to instantiate a Merkle tree with very few gates in TurboPlonk. We use customized gates in TurboPlonk to implement a SNARK-friendly hash function called Anemoi and its Jive k-to-1 compression mode of operation, both by Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov, and Danny Willems. We demonstrate that with $14$ gates ($\approx1$ gate per round in a 12-round Amenoi hash), one can verify a 3-to-1 compression in a 3-ary Merkle tree. Before this, prior implementations often would require hundreds of gates. We anticipate this technique to benefit a large number of applications built off zk-SNARK. Our implementation can be found in $\mathtt{noah}$, a library for modern privacy tokens: https://github.com/FindoraNetwork/noah

We provide the first constructions of SNARGs for Batch-NP and P based solely on the sub-exponential Decisional Diffie Hellman (DDH) assumption. Our schemes achieve poly-logarithmic proof sizes.

Central to our results and of independent interest is a new construction of correlation-intractable hash functions for ``small input'' product relations verifiable in $\mathsf{TC}^0$, based on sub-exponential DDH.

In this work we make progress towards solving an open problem posed by Bilzhause et. al, to give constructions of redactable signature schemes that allow the signer to limit the possible redactions performed by a third party. A separate, but related notion, called controlled disclosure allows a redactor to limit future redactions. We look at two types of data, sets and linear data (data organized as a sequence). In the case of sets, we limit redactions using a policy modeled by a monotone circuit or any circuit depending on the size of the universe the set is drawn from. In the case of linear data, we give a linear construction from vector commitments that limits redactions using a policy modeled as a monotone circuit. Our constructions have the attractive feature that they are built using only blackbox techniques.

Non-interactive zero-knowledge proofs of knowledge (NIZKPoK) serve as a key building block in many important cryptographic constructions. Achieving universally composable NIZKPoK secure against adaptive corruptions was a long-standing open problem, recently solved by Canetti, Sarkar, and Wang (Asiacrypt'22). This sole known construction requires heavy cryptographic machinery such as correlation-intractable hash functions, and is not ready for use in practice. In this paper, we give constructions of adaptively secure universally composable NIZKPoK in the global random-oracle model; we consider both the programmable and the non-programmable versions of the model. For many practical NIZK proof systems, our constructions incur only a super-polylogarithmic slowdown factor compared to stand-alone security.

Neural networks (NNs) have become one of the most important tools for artificial intelligence (AI). Well-designed and trained NNs can perform inference (e.g., make decisions or predictions) on unseen inputs with high accuracy. Using NNs often involves sensitive data: depending on the specific use case, the input to the NN and/or the internals of the NN (e.g., the weights and biases) may be sensitive. Thus, there is a need for techniques for performing NN inference securely, ensuring that sensitive private data remains secret. This challenge belongs to the "privacy and data governance" dimension of trustworthy AI.

In the past few years, several approaches have been proposed for secure neural network inference. These approaches achieve better and better results in terms of efficiency, security, accuracy, and applicability, thus making big progress towards practical secure neural network inference. The proposed approaches make use of many different techniques, such as homomorphic encryption and secure multi-party computation. The aim of this survey paper is to give an overview of the main approaches proposed so far, their different properties, and the techniques used. In addition, remaining challenges towards large-scale deployments are identified.

The privacy set intersection (PSI) protocol with the oblivious pseudorandom function (OPRF) as the core component is a crucial member of PSI family, and the most efficient PSI protocol at present also belongs to this category. Based on DDH assumption, Hash Diffie-Hellman (HashDH) PSI is one of the most classical PSI protocols. Benefiting by its low communication overhead, it still has tremendous research value today. The OPRF subprotocol at the bottom of classical DH-PSI protocol falls into the abstract blind-query-de-blinding OPRF paradigm, while employs the exponential blinding (Exp-HashDH) method. An alternative method called multiplication blinding (Mult-HashDH) offers the improvement which the exponential blinding can't give in performance. This method substitutes multiple variable-base exponentiations with fixed-base exponentiations, and by taking full advantage of this outstanding feature and pre-computation, the computational efficiency of the client can be at least doubled. However, neither Mult-HashDH OPRF nor Mult-HashDH PSI can give a strict security proof under the semi-honest model, which makes the security of the scheme is now reeling from a crisis of confidence. In this paper, the security proof of a modified Mult-HashDH OPRF is formally given under the semi-honest model, and then the HashDH PSI protocol is constructed based on it, which not only ensures the security of the scheme but also have no influence on damaging the efficiency of the protocol. the experimental comparison shows that our protocol achieves 2.65−13.20× speedup in running time.

Recent years have seen many advances in provably secure messaging protocols, both in features and detailed security proofs. However, some important areas of the design space have not yet been explored.

In this work we design the first provably secure protocol that at the same time achieves (i) strong resilience against fine-grained compromise, (ii) post-quantum security, and (iii) immediate decryption with constant-size overhead. Besides these main design goals, we prove that our protocol achieves even stronger security than protocols previously conjectured to be in this space. Finally, we introduce a novel definition of offline deniability suitable for our setting, and prove that our protocol meets it, notably when combined with a post-quantum initial key exchange.

We use game-based security notions to be able to prove post-quantum and strong compromise resilience. At a technical level, we build on the SM protocol and security notion from [1], but the security properties that we aim for require a different proof approach. Our work shows how these properties can be simultaneously achieved, and our temporal healing and offline deniability notions are of independent interest.

Goh and Jarecki (Eurocrypt 2003) showed how to get a signature scheme from the computational Diffie-Hellman assumption, and they introduced the name EDL for signatures of this type. The corresponding EDL family of signature schemes is remarkable for several reasons: elegance, simplicity and tight security. However, EDL security proofs stand in the random oracle model, and, to the best of our knowledge, extending this family without using an idealization of hash functions has never been successful.

In this paper, we propose a new signature scheme belonging to the EDL family, which is simple, natural and efficient, without using the random oracle model. Our scheme is based on the very same assumption than the Boneh-Boyen scheme, namely the strong Diffie-Hellman assumption, with the precision that our groups are not bound to being bilinear. We also make use of a correlation-intractable hash function, for a particular relation related to discrete-logarithm.

In addition to the theoretical interest of extending the EDL family with- out the random oracle model, our scheme is also one of the very few schemes which achieve discrete-log security properties without relying on pairings.