International Association
for Cryptologic Research

The security of multivariate polynomial cryptography depends on the computational complexity of solving a multivariate quadratic polynomial system (MQ problem). One of the fastest algorithms for solving the MQ problem is F4, which computes a Groebner basis but requires numerous calculations of zero reduction that do not affect the output.The Hilbert-driven algorithm evaluates the number of generators in the Groebner basis of degree $d$ using Hilbert series, then it reduces the number of zero reduction computations. In this paper, we propose a high-speed algorithm designed for randomly generated semi-regular MQ problems. Although the Hilbert-driven algorithm is limited to computing homogeneous ideals, we demonstrate its applicability to semi-regular non-homogeneous ideals in this work. Furthermore, when using the Hilbert-driven algorithm to solve non-homogeneous MQ problems with F4, we demonstrate the efficient achievement of reducing zero reduction for F4. We implemented the proposed algorithm in C++ and report successful decryption of a new record $m=21$ Type VI equations. This was achieved using an AMD EPYC 7742 processor and 2TB RAM, and the decryption process was completed within approximately 9 h.

Homomorphic Encryption (HE) is one of the mainstream cryptographic tools used to enable secure outsourced computation. A typical task is secure matrix computation. Popular HE schemes are all based on the problem of Ring Learning with Errors (RLWE), where the messages are encrypted in a ring. In general, the ring dimension should be large to ensure security, which is often larger than the matrix size. Hence, exploiting the ring structure to make fast homomorphic matrix computation has been an important topic in HE. In this paper, we present a new framework for encoding a matrix and performing multiplication on encrypted matrices. The new framework requires fewer basic homomorphic operations for matrix multiplication. Suppose that the ring dimension is $n$ and the matrix size is $d\times d$ with $d= n^{\rho}$. (1) In the compact case where $\rho \leq \frac{1}{3}$, the multiplication of two encrypted matrices requires $\tilde{O}(1)$ basic homomorphic operations, which include plaintext-ciphertext multiplications, ciphertext-ciphertext multiplications, and homomorphic Galois automorphisms. (2) In the large sized case where $\rho> \frac{1}{3}$, our new method requires $O\big(d^{(1 - \frac{1}{3\rho})\cdot \log_2 7 }\big)$ basic homomorphic operations, which is better than all existing methods. In addition, the new framework reduces the communication cost, since it requires fewer key-switching keys. The number of key-switching keys is reduced from $O(d)$ to $O(\log d)$.

When Satoshi Nakamoto introduced Bitcoin, a central tenet was that the blockchain functions as a timestamping server. In the Ethereum era, smart contracts widely assume on-chain timestamps are mostly accurate. In this paper, we prove this is indeed the case, namely that recorded timestamps do not wildly deviate from real-world time, a property we call timeliness. Assuming a global clock, we prove that all popular mechanisms for constructing blockchains (proof-of-work, longest chain proof-of-stake, and quorum-based proof-of-stake) are timely under honest majority, but a synchronous network is a necessary condition. Next we show that all timely blockchains can be suitably modified, in a black-box fashion, such that all honest parties output exactly the same ledgers at the same round, achieving a property we call supersafety, which may be of independent interest. Conversely, we also show that supersafety implies (perfect) timeliness, completing the circle.

Over the last decades, fault injection attacks have been demonstrated to be an effective method for breaking the security of electronic devices. Some types of fault injection attacks, like clock and voltage glitching, require very few resources by the attacker and are practical and simple to execute. A cost-effective countermeasure against these attacks is the use of a detector circuit which detects timing violations - the underlying effect that glitch attacks rely on. In this paper, we take a closer look at three examples of such detectors that have been presented in the literature. We demonstrate four high-speed clock glitching attacks, which successfully inject faults in systems, where detectors have been implemented to protect. The attacks remain unnoticed by the glitch detectors. We verify our attacks with practical experiments on an FPGA.

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Applications of PCD have sparked keen interest within the applied community and industry.

Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, these constructions do not come with security analyses that yield useful concrete security bounds, leaving practitioners in the dark about how to securely instantiate PCD constructions.

In this work we study the concrete security of recursive composition, with the goal of enabling practitioners to set efficient parameters for certain PCD constructions of practical interest. Our main result is that PCD obtained from SNARKs with \emph{straightline knowledge soundness} has essentially the same security as the underlying SNARK. In this setting, recursive composition incurs no security loss.

We describe how straightline knowledge soundness is achieved by SNARKs in several oracle models, including SNARKs that are deployed in practice. Crucially, SNARKs in these settings can be \emph{relativized}, allowing us to construct PCD without instantiating the SNARK's oracle explicitly. This results in a highly efficient security analysis of PCD that makes black-box use of the SNARK's oracle.

As a notable application, our work offers an idealized model that provides useful, albeit heuristic, guidance for setting the security parameters of \emph{recursive STARKs} currently used in blockchain systems.

In 2019, Wan, Liao, Yan and Tsai proposed an article ``Discrete Sliding Mode Control for Chaos Synchronization and Its Application to an Improved ElGamal Cryptosystem''. However, Wan et al. just renamed the variable names without modified the core algorithm. Their paper passed review phase and then published. For this case, it is difficult to detect this situation by computer/digital forensics techniques. In this paper the authors would like to point out this dilemmas.

Domain Generation Algorithms (DGAs) are used by malware to generate pseudorandom domain names to establish communication between infected bots and Command and Control servers. While DGAs can be detected by machine learning (ML) models with great accuracy, offering DGA detection as a service raises privacy concerns when requiring network administrators to disclose their DNS traffic to the service provider. We propose the first end-to-end framework for privacy-preserving classification as a service of domain names into DGA (malicious) or non-DGA (benign) domains. We achieve this through a combination of two privacy-enhancing technologies (PETs), namely secure multi-party computation (MPC) and differential privacy (DP). Through MPC, our framework enables an enterprise network administrator to outsource the problem of classifying a DNS domain as DGA or non-DGA to an external organization without revealing any information about the domain name. Moreover, the service provider's ML model used for DGA detection is never revealed to the network administrator. Furthermore, by using DP, we also ensure that the classification result cannot be used to learn information about individual entries of the training data. Finally, we leverage the benefits of quantization of deep learning models in the context of MPC to achieve efficient, secure DGA detection. We demonstrate that we achieve a significant speed-up resulting in a 15% reduction in detection runtime without reducing accuracy.

In the ever-evolving landscape of Information Technologies, private decentralized computing on an honest yet curious server has emerged as a prominent paradigm. While numerous schemes exist to safeguard data during computation, the focus has primarily been on protecting the confidentiality of the data itself, often overlooking the potential information leakage arising from the function evaluated by the server. Recognizing this gap, this article aims to address the issue by presenting and implementing an innovative solution for ensuring the privacy of both the data and the program. We introduce a novel approach that combines the power of Fully Homomorphic Encryption with the concept of the Turing Machine model, resulting in the first fully secure practical, non-interactive oblivious Turing Machine. Our Oblivious Turing Machine construction is based on only three hypothesis, the hardness of the Ring Learning With Error problem, the ability to homomorphically evaluate non-linear functions and the capacity to blindly rotate elements of a data structure. Only based on those three assumptions, we propose an implementation of an Oblivious Turing Machine relying on the TFHE cryptosystem and present some implementation results.

Fully homomorphic encryption is a promising solution for privacy-preserving computation. For BFV, BGV, and CKKS, three state-of-the-art fully homomorphic encryption schemes, the so-called key switching is one of the primary bottlenecks when evaluating homomorphic circuits. While a large body of work explores optimal selection for scheme parameters such as the polynomial degree or the ciphertext modulus, the realm of key switching parameters is relatively unexplored.

This work closes this gap, formally exploring the parameter space for BGV-like key switching. We introduce a new asymptotic bound for key switching complexity, thereby providing a new perspective on this crucial operation. We also explore the parameter space for the recently proposed double-decomposition technique by Kim et al. [24], which outperforms current state-of-the-art only in very specific circumstances. Furthermore, we revisit an idea by Gentry, Halevi, and Smart [19] switching primes in and out of the ciphertext and find novel opportunities for constant folding, speeding up key switching by up to 50% and up to 11.6%, respectively.

Symmetric Private Information Retrieval (SPIR) is a protocol that protects privacy during data transmission. However, the existing SPIR focuses only on the privacy of the data to be requested on the server, without considering practical factors such as the payload that may be present during data transmission. This could seriously prevent SPIR from being applied to many complex data scenarios and hinder its further expansion. To solve such problems, we propose a primitive (PSKPIR) for symmetric private keyword information retrieval based on private set intersection (PSI) that supports payload transmission and batch keyword search. Specifically, we combine probe-and-XOR of strings (PaXoS) and Oblivious Programmable PRF (OPPRF) to construct PSI with payload (PSI-Payload) not only satisfies client privacy and server privacy, but also facilitates efficient payload transmission. The client can efficiently generate symmetric keys locally using keywords in the intersection, and receive payloads with matching labels in batches. In addition, we provide security definitions for PSKPIR and use the framework of universal composability (UC) to prove security. Finally, we implement PSKPIR with sublinear communication costs in both LAN and WAN settings. Experimental results show that our payload transfer speed is 10× faster than previous work on sufficiently large data sets.

In this work, we consider the problem of secure key leasing, also known as revocable cryptography (Agarwal et. al. Eurocrypt' 23, Ananth et. al. TCC' 23), as a strengthened security notion of its predecessor put forward in Ananth et. al. Eurocrypt' 21. This problem aims to leverage unclonable nature of quantum information to allow a lessor to lease a quantum key with reusability for evaluating a classical functionality. Later, the lessor can request the lessee to provably delete the key and then the lessee will be completely deprived of the capability to evaluate the function. In this work, we construct a secure key leasing scheme to lease a decryption key of a (classical) public-key, homomorphic encryption scheme from standard lattice assumptions. Our encryption scheme is exactly identical to the (primal) version of Gentry-Sahai-Waters homomorphic encryption scheme with a carefully chosen public key matrix. We achieve strong form of security where:

* The entire protocol (including key generation and verification of deletion) uses merely classical communication between a classical leaser (client) and a quantum lessee (server).

* Assuming standard assumptions, our security definition ensures that every computationally bounded quantum adversary could only simultaneously provide a valid classical deletion certificate and yet distinguish ciphertexts with at most negligible probability.

Our security relies on the hardness of learning with errors assumption. Our scheme is the first scheme to be based on a standard assumption and satisfying the two properties mentioned above.

The main technical novelty in our work is the design of an FHE scheme that enables us to apply elegant analyses done in the context of classically verifiable proofs of quantumness from LWE (Brakerski et. al.(FOCS'18, JACM'21) and its parallel amplified version in Radian et. al.(AFT'21)) to the setting of secure leasing. This connection leads to a modular construction and arguably simpler proofs than previously known. An important technical component we prove along the way is an amplified quantum search-to-decision reduction: we design an extractor that uses a quantum distinguisher (who has an internal quantum state) for decisional LWE, to extract secrets with success probability amplified to almost one. This technique might be of independent interest.

This paper re-analyzes the algorithm proposed by Guedes, Assis, and Lula in 2012, which they claimed that the algorithm can break Blum-Micali Pseudorandom number generator in polynomial time. We used a 5×5 transformation matrix instead of the original 2×2 transformation matrix, which can include terms that they missed in their analysis. We proved that their proposed algorithm cannot break the pseudorandom number generator, because during the amplitude amplification process, two iterations of the circuit is the same as an identity gate. To solve this problem, we proposed a corrected algorithm based on Grover’s Search Algorithm for NP-complete problems, which breaks the Blum-Micali Pseudorandom number generator in \(\mathcal{O}(n^4 2^{n/2})\). We conclude that the Blum-Micali Pseudorandom number generator is still quantum resistant. This study indicates that the discrete logarithm problem and prime factorization could still be the foundations of quantum-resistant cryptographical applications.

In this short note, we show that under a mild number-theoretic conjecture, recovering an integer from its Jacobi signature modulo $N = p^2q$, for primes $p$ and $q$, is as hard as factoring $N$.

The lattice-based post-quantum cryptosystem NTRU is used by Google for protecting Google’s internal communication. In NTRU, polynomial multiplication is one of bottleneck. In this paper, we explore the interactions between polynomial multiplication, Toeplitz matrix–vector product, and vectorization with architectural insights. For a unital commutative ring $R$, a positive integer $n$, and an element $\zeta \in R$, we reveal the benefit of vector-by-scalar multiplication instructions while multiplying in $R[x] / \langle x^n - \zeta \rangle$. We aim at designing an algorithm exploiting no algebraic and number–theoretic properties of $n$ and $\zeta$. An obvious way is to multiply in $R[x]$ and reduce modulo $x^n - \zeta$. Since the product in $R[x]$ is a polynomial of degree at most $2n − 2$, one usually chooses a polynomial modulus $g$ such that (i) $deg(g) \geq 2n − 1$, and (ii) there exists a well-studied fast polynomial multiplication algorithm f for multiplying in $R[x] / \langle g \rangle$. We deviate from common approaches and point out a novel insight with dual modules and vector-by-scalar multiplications. Conceptually, we relate the module-theoretic dual of $R[x] / \langle x^n - \zeta \rangle$ and $R[x] / \langle g \rangle$ with Toeplitz matrix-vector products, and demonstrate the benefit of Toeplitz matrix-vector products with vector-by-scalar multiplication instructions. It greatly reduces the register pressure, and allows us to multiply with essentially no permutation instructions that are commonly used in vectorized implementation. We implement the ideas for the NTRU parameter sets ntruhps2048677 and ntruhrss701 on a Cortex-A72 implementing the Armv8.0-A architecture with the single-instruction-multiple-data (SIMD) technology Neon. For polynomial multiplications, our implementation is 2.18× and 2.23× for ntruhps2048677 and ntruhrsss701 than the state-of-the-art optimized implementation. We also vectorize the polynomial inversions and sorting network by employing existing techniques and translating AVX2-optimized implementations into Neon. Compared to the state-of-the-art optimized implementation, our key generation, encapsulation, and decapsulation for ntruhps2048677 are 7.67×, 2.48×, and 1.77× faster, respectively. For ntruhrss701, our key generation, encapsulation, and decapsulation are 7.99×, 1.47×, and 1.56× faster, respectively.

Circuit-based Private Set Intersection (circuit-PSI) enables two parties, a client and a server, with their input sets $X$ and $Y$ respectively, to securely compute a function $f$ on the intersection $X \cap Y$, while keeping $X \cap Y$ secret from both parties. Although several computationally efficient circuit-PSI protocols have been proposed recently, they most focus on the balanced scenario where $|X|$ is similar to $|Y|$. However, in many realistic scenarios, a circuit-PSI protocol may be performed in the unbalanced case where $|X|$ is remarkably smaller than $|Y|$ (e.g., the client is a constrained device holding a small set, while the server is a service provider holding a large set). Directly applying existing protocols to this scenario will lead to significant efficiency issues because the communication complexity of the protocols scales at least linearly with the size of the larger set, i.e., $\max(|X|, |Y|)$.

In this work, we put forth efficient constructions for unbalanced circuit-PSI with sublinear communication complexity in the size of the larger set. The main insight is that we formalize unbalanced circuit-PSI as obliviously retrieving values corresponding to keys from a set of key-value pairs. To this end, we present a new functionality called Oblivious Key-Value Retrieval (OKVR) and design the OKVR protocol from a new notion called sparse Oblivious Key-Value Stores (sparse OKVS). We conduct extensive experiments and the results show that our constructions remarkably outperform the state-of-the-art circuit-PSI schemes (EUROCRYPT'19, PETs'22, CCS'22), i.e., $1.84 \sim 48.86 \times$ communication improvement and $1.50 \sim39.81 \times$ faster computation. Very recently, Son and Jeong (AsiaCCS'23) also present unbalanced circuit-PSI protocols, and our constructions outperform them by $1.18 \sim 15.99 \times$ and $1.22 \sim 10.44 \times$ in communication and computation overhead, respectively, depending on set sizes and network environments.

We consider the problem of creating, or issuing, zero-knowledge proofs obliviously. In this setting, a prover interacts with a verifier to produce a proof, known only to the verifier. The resulting proof is transferable and can be verified non-interactively by anyone. Crucially, the actual proof cannot be linked back to the interaction that produced it.

This notion generalizes common approaches to designing blind signatures, which can be seen as the special case of proving "knowledge of a signing key", and extends the seminal work of Camenisch and Stadler ('97). We propose a provably secure construction of oblivious proofs, focusing on discrete-logarithm representation equipped with AND-composition.

We also give three applications of our framework. First, we give a publicly verifiable version of the classical Diffie-Hellman based Oblivious PRF. This yields new constructions of blind signatures and publicly verifiable anonymous tokens. Second, we show how to "upgrade" keyed-verification anonymous credentials (Chase et al., CCS'14) to also be concurrently secure blind signatures on the same set of attributes. Crucially, our upgrade maintains the performance and functionality of the credential in the keyed-verification setting, we only change issuance. We observe that the existing issuer proof that the credential is well-formed may be verified by anyone; creating it with our framework makes it a blind signature, adding public verifiability to the credential system. Finally, we provide a variation of the U-Prove credential system that is provably one-more unforgeable with concurrent issuance sessions. This constitutes a fix for the attack illustrated by Benhamouda et al. (EUROCRYPT'21).

Beyond these example applications, as our results are quite general, we expect they may enable modular design of new primitives with concurrent security, a goal that has historically been challenging to achieve.

The BUFF transform is a generic transformation for digital signature schemes, with the purpose of obtaining additional security properties beyond standard unforgeability, e.g., exclusive ownership and non-resignability. In the call for additional post-quantum signatures, these were explicitly mentioned by the NIST as ``additional desirable security properties'', and some of the submissions indeed refer to the BUFF transform with the purpose of achieving them, while some other submissions follow the design of the BUFF transform without mentioning it explicitly.

In this work, we show the following negative results regarding the non-resignability property in general, and the BUFF transform in particular. In the plain model, we observe by means of a simple attack that any signature scheme for which the message has a high entropy given the signature does not satisfy the non-resignability property (while non-resignability is trivially not satisfied if the message can be efficiently computed from its signature). Given that the BUFF transform has high entropy in the message given the signature, it follows that the BUFF transform does not achieve non-resignability whenever the random oracle is instantiated with a hash function, no matter what hash function.

When considering the random oracle model (ROM), the matter becomes slightly more delicate since prior works did not rigorously define the non-resignability property in the ROM. For the natural extension of the definition to the ROM, we observe that our impossibility result still holds, despite there having been positive claims about the non-resignability of the BUFF transform in the ROM. Indeed, prior claims of the non-resignability of the BUFF transform rely on faulty argumentation.

On the positive side, we prove that a salted version of the BUFF transform satisfies a slightly weaker variant of non-resignability in the ROM, covering both classical and quantum attacks, if the entropy requirement in the (weakened) definition of non-resignability is statistical; for the computational variant, we show yet another negative result.

Ring signature (RS) allows users to demonstrate to verifiers their membership within a specified group (ring) without disclosing their identities. Based on this, RS can be used as a privacy protection technology for users' identities in blockchain. However, there is currently a lack of RS schemes that are fully applicable to the blockchain applications: Firstly, users can only spend a UTXO once, and the current RS schemes are not yet perfect in a one-time manner. At the same time, the current RS schemes are not sufficiently developed in terms of regulation. Secondly, the size of the current RS is mostly linearly related to the number of ring members. When there are many members, the transaction processing speed is slow. We propose a one-time and revocable ring signature with logarithmic size in blockchain based on the Sigma-Protocols. Our scheme compresses the RS size and enables users to sign in the blockchain transactions. The scheme allows two RS generated with the same private key for a same UTXO to be linked together. Additionally, it allows regulatory authority to recover the signer's identity at any time. A security model was presented, and its security properties, namely, unforgeability, anonymity, one-time, revocability, and non-slanderability were proven in the random oracle model. Our scheme compresses the RS size to where is the number of ring users, enabling blockchain transactions to have better processing speeds. And it can prevent double-spending attacks in blockchain and allows regulatory authority to recover the identity of the signer.

The algebraic degree of a vectorial Boolean function is one of the main parameters driving the cost of its hardware implementation. Thus, finding decompositions of functions into sequences of functions of lower algebraic degrees has been explored to reduce the cost of implementations. In this paper, we consider such decompositions of permutations over $\mathbb{F}_{2^n}$. We prove the existence of decompositions using quadratic and linear power permutations for all permutations when $2^n-1$ is a prime, and we prove the non-existence of such decompositions for power permutations of differential uniformity strictly lower than $16$ when $4|n$. We also prove that any permutation admits a decomposition into quadratic power permutations and affine permutations of the form $ax+b$ if $4 \nmid n$. Furthermore, we prove that any permutation admits a decomposition into cubic power permutations and affine permutations. Finally, we present a decomposition of the PRESENT S-Box using the power permutation $x^7$ and affine permutations.

Symmetric Private Information Retrieval (SPIR) is a stronger PIR protocol that ensures both client and server privacy. In many cases, the client needs authorization from the data subject before querying data. However, this also means that the server can learn the identity of the data subject. To solve such problems, we propose a new SPIR primitive, called authorized symmetric keyword information retrieval protocol (ASKPIR). Specifically, we designed an efficient DID identification algorithm based on the Pedersen Commitment, which is used to solve the identity management and privacy problems of data subject when data is shared by multiple parties in a distributed environment. Then, we present a novel authorization algorithm combining NIZK proof and DID, which can preserve client privacy. Finally, to improve the efficiency of client retrieval, our protocol constructs PSI-Payload with mqRPMT and OTE so as to support batch keyword searches. In addition, we provide a formal security analysis for the anonymity and unforgeability of the protocol and demonstrate that ASKPIR can achieve malicious security under the UC framework. Theoretical analysis and experimental results show that the ASKPIR protocol is more efficient than other related works and solves the problem of incompatibility between data subject authorization and client privacy.