International Association
for Cryptologic Research

The Learning with Errors (LWE) problem has been widely utilized as a foundation for numerous cryptographic tools over the years. In this study, we focus on an algebraic variant of the LWE problem called Group ring LWE (GR-LWE). We select group rings (or their direct summands) that underlie specific families of finite groups constructed by taking the semi-direct product of two cyclic groups. Unlike the Ring-LWE problem described in \cite{lyubashevsky2010ideal}, the multiplication operation in the group rings considered here is non-commutative. As an extension of Ring-LWE, it maintains computational hardness and can be potentially applied in many cryptographic scenarios. In this paper, we present two polynomial-time quantum reductions. Firstly, we provide a quantum reduction from the worst-case shortest independent vectors problem (SIVP) in ideal lattices with polynomial approximate factor to the search version of GR-LWE. This reduction requires that the underlying group ring possesses certain mild properties; Secondly, we present another quantum reduction for two types of group rings, where the worst-case SIVP problem is directly reduced to the (average-case) decision GR-LWE problem. The pseudorandomness of GR-LWE samples guaranteed by this reduction can be consequently leveraged to construct semantically secure public-key cryptosystems.

In recent years, quantum computers and Shor’s quantum algorithm have been able to effectively solve NP (Non-deterministic Polynomial-time) problems such as prime factorization and discrete logarithm problems, posing a threat to current mainstream asymmetric cryptography, including RSA and Elliptic Curve Cryptography (ECC). As a result, the National Institute of Standards and Technology (NIST) in the United States call for Post-Quantum Cryptography (PQC) methods that include lattice-based cryptography methods, code-based cryptography methods, multivariate cryptography methods, and hash-based cryptography methods for resisting quantum computing attacks. Therefore, this study proposes a PQC neural network (PQC-NN) that maps a code-based PQC method to a neural network structure and enhances the security of ciphertexts with non-linear activation functions, random perturbation of ciphertexts, and uniform distribution of ciphertexts. The main innovations of this study include: (1) constructing a neural network structure that complies with code-based PQC, where the weight sets between the input layer and the ciphertext layer can be used as a public key for encryption, and the weight sets between the ciphertext layer and the output layer can be used as a private key for decryption; (2) adding random perturbations to the ciphertext layer, which can be removed during the decryption phase to restore the original plaintext; (3) constraining the output values of the ciphertext layer to follow a uniform distribution with a significant similarity by adding the cumulative distribution function (CDF) values of the chi-square distribution to the loss function, ensuring that the neural network produces sufficiently uniform distribution for the output values of the ciphertext layer. In practical experiments, this study uses cellular network signals as a case study to demonstrate that encryption and decryption can be performed by the proposed PQC neural network with the uniform distribution of ciphertexts. In the future, the proposed PQC neural network could be applied to various applications.

VOX has been submitted to the NIST Round 1 Additional Signature of the Post-Quantum Signature Competition in June 2023. VOX is a strengthened variant of UOV which uses the Quotient-Ring (QR) setting to reduce the public-key size. At the end of August 2023, Furue and Ikamatsu posted on the NIST mailing-list a post, indicating that the parameters of VOX can be attacked efficiently using the rectangular attack in the QR setting.

In this note, we explain the attack in the specific case of VOX, we detail the complexity, and show that as Furue and Ikematsu indicated, the attack can be completely avoided by adding one more constraint on the parameter selection. Finally, we show that this constraint does not increase the sizes of the public keys or signature.

This note presents attacks on the lightweight hash function TS-Hash proposed by Tsaban, including a polynomial-time preimage attack for short messages (at most n/2 bits), high-probability differentials, a general subexponential-time preimage attack, and linearization techniques.

Multi-signatures allow for compressing many signatures for the same message that were generated under independent keys into one small aggregated signature. This primitive is particularly useful for proof-of-stake blockchains, like Ethereum, where the same block is signed by many signers, who vouch for the block's validity. Being able to compress all signatures for the same block into a short string significantly reduces the on-chain storage costs, which is an important efficiency metric for blockchains.

In this work, we consider multi-signatures in the synchronized setting, where the signing algorithm takes an additional time parameter as input and it is only required that signatures for the same time step are aggregatable. The synchronized setting is simpler than the general multi-signature setting, but is sufficient for most blockchain related applications, as signers are naturally synchronized by the length of the chain.

We present Chipmunk, a concretely efficient lattice-based multi-signature scheme in the synchronized setting that allows for signing an a-priori bounded number of messages. Chipmunk allows for non-interactive aggregation of signatures and is secure against rogue-key attacks. The construction is plausibly secure against quantum adversaries as our security relies on the assumed hardness of the short integer solution problem.

We significantly improve upon the previously best known construction in this setting by Fleischhacker, Simkin, and Zhang (CCS 2022). Our aggregate signature size is $5.6 \times$ smaller and for $112$ bits of security our construction allows for compressing 8192 individual signatures into a multi-signature of size around $136$ KB. We provide a full implementation of Chipmunk and provide extensive benchmarks studying our construction's efficiency.

In their seminal work, Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC`07) presented the MPC-in-the-Head paradigm, which shows how to design Zero-Knowledge Proofs (ZKPs) from secure Multi-Party Computation (MPC) protocols. This paradigm has since then revolutionized and modularized the design of efficient ZKP systems, with far-reaching applications beyond ZKPs. However, to the best of our knowledge, all previous instantiations relied on fully-secure MPC protocols, and have not been able to leverage the fact that the paradigm only imposes relatively weak privacy and correctness requirements on the underlying MPC.

In this work, we extend the MPC-in-the-Head paradigm to game-based cryptographic primitives supporting homomorphic computations (e.g., fully-homomorphic encryption, functional encryption, randomized encodings, homomorphic secret sharing, and more). Specifically, we present a simple yet generic compiler from these primitives to ZKPs which use the underlying primitive as a black box. We also generalize our paradigm to capture commit-and-prove protocols, and use it to devise tight black-box compilers from Interactive (Oracle) Proofs to ZKPs, assuming One-Way Functions (OWFs).

We use our paradigm to obtain several new ZKP constructions:

1. The first ZKPs for NP relations $\mathcal{R}$ computable in (polynomial-time uniform) $NC^1$, whose round complexity is bounded by a fixed constant (independent of the depth of $\mathcal{R}$'s verification circuit), with communication approaching witness length (specifically, $n\cdot poly\left(\kappa\right)$, where $n$ is the witness length, and $\kappa$ is a security parameter), assuming DCR. Alternatively, if we allow the round complexity to scale with the depth of the verification circuit, our ZKPs can make black-box use of OWFs.

2. Constant-round ZKPs for NP relations computable in bounded polynomial space, with $O\left(n\right)+o\left(m\right)\cdot poly\left(\kappa\right)$ communication assuming OWFs, where $m$ is the instance length. This gives a black-box alternative to a recent non-black-box construction of Nassar and Rothblum (CRYPTO`22).

3. ZKPs for NP relations computable by a logspace-uniform family of depth-$d\left(m\right)$ circuits, with $n\cdot poly\left(\kappa,d\left(m\right)\right)$ communication assuming OWFs. This gives a black-box alternative to a result of Goldwasser, Kalai and Rothblum (JACM).

We build the first unleveled fully homomorphic signature scheme in the standard model. Our scheme is not constrained by any a-priori bound on the depth of the functions that can be homomorphically evaluated, and relies on subexponentially-secure indistinguishability obfuscation, fully-homomorphic encryption and a non-interactive zero-knowledge (NIZK) proof system with composable zero-knowledge. Our scheme is also the first to satisfy the strong security notion of context-hiding for an unbounded number of levels, ensuring that signatures computed homomorphically do not leak the original messages from which they were computed. All building blocks are instantiable from falsifiable assumptions in the standard model, avoiding the need for knowledge assumptions. The main difficulty we overcome stems from the fact that bootstrapping, which is a crucial tool for obtaining unleveled fully homomorphic encryption (FHE), has no equivalent for homomorphic signatures, requiring us to use novel techniques.

This paper describes a way to protect medications against falsification, a long-standing problem in the world.

We combine several existing technologies to achieve the stated goal. The building-blocks used are inherent physical randomness generated during the packaging process, artificial vision, short digital signatures and QR-codes.

Decentralized payment system gradually get more attention in recent years. By removing the trusted third party used for accounting ledgers, it fundamentally empowers users to control their own assets. As the privacy concerns grow, some cryptocurrencies is proposed to preserve the privacy of users. However, those cryptocurrencies cause illegal transactions such as money laundering, fraudulent trading and so on. So it is necessary to design a auditing scheme. To solve this problem, many privacy-preserving and audit scheme was proposed. But there exists no scheme that effectively solve the issue of privacy-preserving and auditing on both user identity and transaction content. In this paper, we propose a design for a decentralized payment system with privacy preserving and auditing. We use cryptographic accumulators based on Merkle trees for accounting and use a combination of Twist ElGamal, NIZK (Non-Interactive Zero-Knowledge), Bulletproofs, and zk-SNARKs for privacy preserving and auditing.

The evolution of quantum algorithms threatens to break public key cryptography in polynomial time. The development of quantum-resistant algorithms for the post-quantum era has seen a significant growth in the field of post quantum cryptography (PQC). Polynomial multiplication is the core of Ring Learning with Error (RLWE) lattice based cryptography (LBC) which is one of the most promising PQC candidates. In this work, we present the design of fast and energy-efficient pipelined Number Theoretic Transform (NTT) based polynomial multipliers and present synthesis results on a Field Programmable Gate Array (FPGA) to evaluate their efficacy. NTT is performed using the pipelined R2SDF and R22SDF Fast Fourier Transform (FFT) architectures. In addition, we propose an energy efficient modified architecture (Modr2). The NTT-based designed polynomial multipliers employs the Modr2 architecture that achieve on average 2× better performance over the R2SDF FFT and 2.4× over the R22SDF FFT with similar levels of energy consumption. The proposed polynomial multiplier with Modr2 architecture reaches 12.5× energy efficiency over the state-ofthe-art convolution-based polynomial multiplier and 4× speedup over the systolic array NTT based polynomial multiplier for polynomial degrees of 1024, demonstrating its potential for practical deployment in future designs.

Attribute-Based Encryption is widely recognized as a leap forward in the field of public key encryption. It allows to enforce an access control on encrypted data. Decryption time in ABE schemes can be long depending on the number of attributes and pairing operations. This drawback hinders their adoption on a broader scale.

In this paper, we propose a non-monotone CP-ABE scheme that has no restrictions on the size of attribute sets and policies, allows fast decryption and is adaptively secure under the CBDH-3 assumption. To achieve this, we approached the problem from a new angle, namely using a set membership relation for access structure. We have implemented our scheme using the Java Pairing-Based Cryptography Library (JPBC) and the source code is available on GitHub.

The Department of Combinatorics and Optimization in the Faculty of Mathematics at the University of Waterloo invites applications for three tenure-track faculty positions at the rank of Assistant Professor. Appointments at the level of Associate or Full Professor with tenure will be considered in special cases that substantially enhance the reputation of the department. Stellar candidates in the research areas of algebraic combinatorics, continuous optimization, cryptography, discrete optimization, and graph theory, who can greatly enhance the research and teaching profile of the department, are welcome to apply. Cryptography and optimization are the focus areas for these positions, and within optimization, continuous optimization is a priority area.

A Ph.D. degree and evidence of excellence in research and teaching are required. Successful applicants are expected to maintain an active program of research, to attract and supervise graduate students, and to participate in undergraduate and graduate teaching.

The salary range for the position is $105,000 to $155,000. Negotiations beyond this salary range will be considered for exceptionally qualified candidates. The anticipated start date is July 1, 2024. Interested individuals should apply using the MathJobs site (https://www.mathjobs.org/jobs/list/23241). Applications should include a curriculum vitae, research and teaching statements, and up to three reprints/preprints. In addition, at least three reference letters should be submitted.

The deadline for applications is December 4, 2023. Applications received by December 4, will be given full consideration. However, applications will continue to be reviewed until the position is filled.

Closing date for applications:

Contact: Chaitanya Swamy, Chair, Department of Combinatorics and Optimization

More information: https://www.mathjobs.org/jobs/list/23241

Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to $t=n-1$ malicious corruptions and terminates in $O(\min\{f^2,t+1\})$ rounds for any execution with $f\leq t$ actual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require honest majority or tolerate only up to $t=(1-\epsilon)n$ malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.

The Number Theoretic Transform (NTT) plays a central role in efficient implementations of cryptographic primitives selected for Post Quantum Cryptography. Although it certainly exists, academic papers that cite the NTT omit the connection between the NTT and residues of a polynomial modulo factors of $X^{2^d} + 1$ and mention only the final expressions of what the NTT computes. This short paper establishes that connection and, in doing so, elucidates key aspects of computing the NTT. Based on this, the specific instantiations of the NTT function used in CRYSTALS-Kyber and CRYSTALS-Dilithium are derived.

The Fujisaki-Okamoto (FO) transformation is used in most proposals for post-quantum secure key encapsulation mechanisms (KEMs) like, e.g., Kyber [BDK+18]. The security analysis of FO in the presence of quantum attackers has made huge progress over the last years. Recently, [HHM22] made a particular improvement by giving a security proof that is agnostic towards how invalid ciphertexts are being treated: in contrast to previous proofs, it works regardless whether invalid ciphertexts are rejected by reporting decryption failure explicitly or implicitly (by returning pseudorandom values).

The proof in [HHM22] involves a new correctness notion for the encryption scheme that is used to encapsulate the keys. This allows in principle for a smaller additive security related to decryption failures, but requires to analyze this new notion for the encryption scheme on which a concrete KEM at hand is based.

This note offers a trade-off between [HHM22] and its predecessors: it offers a bound for both rejection variants, being mostly based on [HHM22], but uses a more established correctness notion.

Blind Signatures are a useful primitive for privacy preserving applications such as electronic payments, e-voting, anonymous credentials, and more. However, existing practical blind signature schemes based on standard assumptions require either pairings or lattices. We present the first construction of a round-optimal blind signature in the random oracle model based on standard assumptions without resorting to pairings or lattices. In particular, our construction is secure under the strong RSA assumption and DDH (in pairing-free groups). For our construction, we provide a NIZK-friendly signature based on strong RSA, and efficiently instantiate Fischlin's generic framework (CRYPTO'06). Our Blind Signature scheme has signatures of size 4.28 KB and communication cost 62.19 KB. On the way, we develop techniques that might be of independent interest. In particular, we provide efficient relaxed range-proofs with subversion zero-knowledge and compact commitments to elements of arbitrary groups.

Algorithm hardness can be described by 5 categories: hardness in computation, in sequential computation, in memory, in energy consumption (or bandwidth), in code size. Similarly, hardness can be a concern for solving or for verifying, depending on the context, and can depend on a secret trapdoor or be universally hard. Two main lines of research investigated such problems: cryptographic puzzles, that gained popularity thanks to blockchain consensus systems (where solving must be moderately hard, and verification either public or private), and white box cryptography (where solving must be hard without knowledge of the secret key). In this work, we improve upon the classification framework proposed by Biryukov and Perrin in Asiacypt 2017 and offer a united hardness framework, PURED, that can be used for measuring all these kinds of hardness, both in solving and verifying. We also propose three new constructions that fill gaps previously uncovered by the literature (namely, trapdoor proof of CMC, trapdoor proof of code, and a hard challenge in sequential time trapdoored in verification), and analyse their hardness in the PURED framework.

DCT is a beyond-birthday-bound~(BBB) deterministic authenticated encryption~(DAE) mode proposed by Forler et al. in ACISP 2016, ensuring integrity by redundancy. The instantiation scheme of DCT employs the BRW polynomial, which is more efficient than the usual polynomial function in GCM by reducing half of the multiplication operations. However, we show that DCT suffers from a small stretch problem similar to GCM. When the stretch length $\tau$ is small, choosing a special $m$-block message, we can reduce the number of queries required by a successful forgery to $\mathcal{O}(2^{\tau}/m)$. We emphasize that this attack efficiently balances space and time complexity, but does not contradict the security bounds of DCT. Finally, we propose an improved scheme named Robust DCT~(RDCT) with a minor change to DCT, which improves the security when $\tau$ is small and makes it resist the above attack.

Graph convolutional networks (GCNs) are gaining popularity due to their powerful modelling capabilities. However, guaranteeing privacy is an issue when evaluating on inputs that contain users’ sensitive information such as financial transactions, medical records, etc. To address such privacy concerns, we design Entrada, a framework for securely evaluating GCNs that relies on the technique of secure multiparty computation (MPC). For efficiency and accuracy reasons, Entrada builds over the MPC framework of Tetrad (NDSS’22) and enhances the same by providing the necessary primitives. Moreover, Entrada leverages the GraphSC paradigm of Araki et al. (CCS’21) to further enhance efficiency. This entails designing a secure and efficient shuffle protocol specifically in the 4-party setting, which to the best of our knowledge, is done for the first time and may be of independent interest. Through extensive experiments, we showcase that the accuracy of secure GCN evaluated via Entrada is on par with its cleartext counterpart. We also benchmark efficiency of Entrada with respect to the included primitives as well as the framework as a whole. Finally, we showcase Entrada’s practicality by benchmarking GCN-based fraud detection application.

In ASIACRYPT 2016, Bellare et al. first demonstrated that it is impossible to achieve subversion soundness and standard zero knowledge simultaneously. Subsequently, there have been lots of effort to construct zero-knowledge succinct non interactive arguments of knowledge protocols (zk-SNARKs) that satisfy subversion zero knowledge (S-ZK) and standard soundness from the zk-SNARK in the common reference string (CRS) model. The various constructions could be regarded secure in the bare public key (BPK) model because of the equivalence between S-ZK in the CRS model, and uniform non-black-box zero knowledge in the BPK model has been proved by Abdolmaleki et al. in PKC 2020.

In this study, We proposed the first publicly verifiable non-uniform ZK zk-SNARK scheme in the BPK model maintaining comparable efficiency with its conventional counterpart, which can also be compatible with the well-known transformation proposed by Bitansky et al. in TCC 2013 to obtain an efficient designated-verifier zk-SNARK. We achieve this goal by only adding a constant number of elements into the CRS, and using an unconventional but natural method to transform Groth’s zkSNARK in EUROCRYPT 2016. In addition, we propose a new speed-up technique that provides a trade-off. Specifically, if a logarithmic number of elements are added into the CRS, according to different circuits, the CRS verification time in our construction could be approximately 9%-23% shorter than that in the conventional counterpart.