Index Calculus (IC) algorithm is the most effective probabilistic algorithm for solving discrete logarithms over finite fields of prime numbers, and it has been widely applied to cryptosystems based on elliptic curves. Since the IC algorithm was proposed in 1920, the research on it has never stopped, especially discretization of prime numbers on the finite fields, both the algorithm itself and its application have been greatly developed. Of course, there has been some research on elliptic...

RSA is widely used in modern cryptographic practice, with certain RSA-based protocols relying on the secrecy of $p$ and $q$. A common approach is to use secure multiparty computation to address the privacy concerns of $p$ and $q$. Specifically constrained to distributed RSA modulus generation protocols, the biprimality test for Blum integers $N=pq$, where $p\equiv q\equiv 3 \mod4$ are two primes, proposed by Boneh and Franklin ($2001$) is the most commonly used. Over the past $20 $ years,...

An RSA generalization using complex integers was introduced by Elkamchouchi, Elshenawy, and Shaban in 2002. This scheme was further extended by Cotan and Teșeleanu to Galois fields of order $n \geq 1$. In this generalized framework, the key equation is $ed - k (p^n-1)(q^n-1) = 1$, where $p$ and $q$ are prime numbers. Note that, the classical RSA, and the Elkamchouchi \emph{et al.} key equations are special cases, namely $n=1$ and $n=2$. In addition to introducing this generic family, Cotan...

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). To our knowledge, it is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem; the circuit also achieves sublinear depth and nearly linear gate count. We build on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du...

Private Set Intersection (PSI) is a cryptographic primitive that allows two parties to obtain the intersection of their private input sets while revealing nothing more than the intersection. PSI and its numerous variants, which compute on the intersection of items and their associated weights, have been widely studied. In this paper, we revisit the problem of finding the best item in the intersection according to weight sum introduced by Beauregard et al. (SCN '22), which is a special...

Public key cryptography can be based on integer factorization and the discrete logarithm problem (DLP), applicable in multiplicative groups and elliptic curves. Regev’s recent quantum algorithm was initially designed for the factorization and was later extended to the DLP in the multiplicative group. In this article, we further extend the algorithm to address the DLP for elliptic curves. Notably, based on celebrated conjectures in Number Theory, Regev’s algorithm is asymptotically...

NTRU is one of the most extensively studied lattice-based schemes. Its flexible design has inspired different proposals constructed over different rings, with some aiming to enhance security and others focusing on improving performance. The literature has introduced a line of noncommutative NTRU-like designs that claim to offer greater resistance to existing attacks. However, most of these proposals are either theoretical or fall short in terms of time and memory requirements when compared...

The Leftover Hash Lemma (LHL) is a powerful tool for extracting randomness from an entropic distribution, with numerous applications in cryptography. LHLs for discrete Gaussians have been explored in both integer settings by Gentry et al. (GPV, STOC'08) and algebraic ring settings by Lyubashevsky et al. (LPR, Eurocrypt'13). However, the existing LHLs for discrete Gaussians have two main limitations: they require the Gaussian parameter to be larger than certain smoothing parameters, and they...

The Jacobi Symbol is an essential primitive in cryptographic applications such as primality testing, integer factorization, and various encryption schemes. By exploring the interdependencies among modular reductions within the algorithmic loop, we have developed a refined method that significantly enhances computational efficiency. Our optimized algorithm, implemented in the Rust language, achieves a performance increase of 72% over conventional textbook methods and is twice as fast as the...

We conjecture new elementary formulas for computing the greatest common divisor (GCD) of two integers, alongside an elementary formula for extracting the prime factors of semiprimes. These formulas are of fixed-length and require only the basic arithmetic operations of: addition, subtraction, multiplication, division with remainder, and exponentiation. Our GCD formulas result from simplifying a formula of Mazzanti and are derived using Kronecker substitution techniques from our earlier...

Problems in the complexity class $NP$ are not all known to be solvable, but are verifiable given the solution, in polynomial time by a classical computer. The complexity class $BQP$ includes all problems solvable in polynomial time by a quantum computer. Prime factorization is in $NP$ class, and is also in $BQP$ class, owing to Shor's algorithm. The hardest of all problems within the $NP$ class are called $NP$-complete. If a quantum algorithm can solve an $NP$-complete problem in polynomial...

In this note, we improve the space-efficient variant of Regev's quantum factoring algorithm [Reg23] proposed by Ragavan and Vaikuntanathan [RV24] by constant factors in space and/or size. This allows us to bridge the significant gaps in concrete efficiency between the circuits by [Reg23] and [RV24]; [Reg23] uses far fewer gates, while [RV24] uses far fewer qubits. The main observation is that the space-efficient quantum modular exponentiation technique by [RV24] can be modified to...

In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multi-dimensional version of Shor's algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in $(\mathbb{Z}/N\mathbb{Z})^{\times}$ that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such...

Since its invention in 1978 by Rivest, Shamir and Adleman, the public key cryptosystem RSA has become a widely popular and a widely useful scheme in cryptography. Its security is related to the difficulty of factoring large integers which are the product of two large prime numbers. For various reasons, several variants of RSA have been proposed, and some have different arithmetics such as elliptic and singular cubic curves. In 2018, Murru and Saettone proposed another variant of RSA based on...

A recent work by Ball, Li, Lin, and Liu [Eurocrypt'23] presented a new instantiation of the arithmetic garbling paradigm introduced by Applebaum, Ishai, and Kushilevitz [FOCS'11]. In particular, Ball et al.'s garbling scheme is the first constant-rate garbled circuit over large enough bounded integer computations, inferring the first constant-round constant-rate secure two-party computation (2PC) over bounded integer computations in the presence of semi-honest adversaries. The main source...

This paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings in various models. - In the classical generic group model (GGM), we find simple alternative proofs for the lower bounds of variants of the discrete logarithm (DL) problem: the multiple-instance DL and one-more DL problems (and their mixture). We also re-prove the unknown-order GGM lower bounds, such as the order finding, root extraction, and repeated squaring. -...

This paper focuses on the optimization of the number of logical qubits in quantum algorithms for factoring and computing discrete logarithms in $\mathbb{Z}_N^*$. These algorithms contain an exponentiation circuit modulo $N$, which is responsible for most of their cost, both in qubits and operations. In this paper, we show that using only $o(\log N)$ work qubits, one can obtain the least significant bits of the modular exponentiation output. We combine this result with May and Schlieper's...

This work introduces several algorithms related to the computation of orientations in endomorphism rings of supersingular elliptic curves. This problem boils down to representing integers by ternary quadratic forms, and it is at the heart of several results regarding the security of oriented-curves in isogeny-based cryptography. Our main contribution is to show that there exists efficient algorithms that can solve this problem for quadratic orders of discriminant $n$ up to $O(p^{4/3})$....

The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup $G\rtimes \mathrm{End}(G)$ for a finite semigroup $G$. Given $g\in G, \sigma\in \mathrm{End}(G)$, and $h=\prod_{i=0}^{t-1}\sigma^i(g)$ for some integer $t$, the SDLP$(G,\sigma)$, for $g$ and $h$, asks to determine $t$. As Shor's algorithm crucially depends on commutativity, it is believed not to be applicable to the SDLP. Previously, the...

The splitting field $F$ of the polynomial $Y^n-2$ is an extension over $\mathbb{Q}$ generated by $\zeta_n=\exp(2 \pi \sqrt{-1} /n)$ and $\sqrt[n]{2}$. In this paper, we lay the foundation for applying the Order-LWE in the integral ring $\mathcal{R}=\mathbb{Z}[\zeta_n, \sqrt[n]{2}]$ to cryptographic uses when $n$ is a power-of-two integer. We explicitly compute the Galois group $\text{Gal}\left(F/\mathbb{Q} \right)$ and the canonical embedding of $F$, based on which we study the properties of...

We extend the known pseudorandomness of Ring-LWE to be based on lattices that do not correspond to any ideal of any order in the underlying number field. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more...

We show that under a mild number-theoretic conjecture, recovering an integer from its Jacobi signature modulo $N = p^2 q$, for primes $p$ and $q$, is as hard as factoring $N$. This relates, for the first time, the one-wayness of a pseudorandom generator that Damgård proposed in 1988, to a standard number-theoretic problem. In addition, we show breaking the Jacobi pseudorandom function is no harder than factoring.

We give a new approach for finding large smooth twins. Those twins whose sum is a prime are of interest in the parameter setup of certain isogeny-based cryptosystems such as SQIsign. The approach to find such twins is to find two polynomials in $\mathbb{Q}[x]$ that split into a product of small degree factors and differ by $1$. Then evaluate them on a particular smooth integer. This was first explored by Costello, Meyer and Naehrig at EUROCRYPT'21 using polynomials that split completely into...

We provide two improvements to Regev's quantum factoring algorithm (arXiv:2308.06572), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one...

In the context of circuits leaking the internal state due to hardware side-channels, the $p$-random probing model has an adversary who can see the value of each wire with probability $p$. In this model, for a fixed $p$, it is possible to reach an arbitrary security by 'expanding' a stateless circuit via iterated compilation, reaching a security of $2^{-\kappa}$ with a polynomial size in $\kappa$. An artifact of the existing proofs of the expansion is that the worst security is assumed for...

The number-theoretic literature has long studied the question of distributions of sequences of quadratic residue symbols modulo a prime number. In this paper, we present an efficient algorithm for generating primes containing chosen sequences of quadratic residue symbols and use it as the basis of a method extending the functionality of additively homomorphic cryptosystems. We present an algorithm for encoding a chosen Boolean function into the public key and an efficient two-party...

Fully Homomorphic Encryption has known impressive improvements in the last 15 years, going from a technology long thought to be impossible to an existing family of encryption schemes able to solve a plethora of practical use cases related to the privacy of sensitive information. Recent results mainly focus on improving techniques within the traditionally defined framework of GLWE-based schemes, but the recent CPU implementation improvements are mainly incremental. To keep improving this...

The Number Field Sieve (NFS) is the state-of-the art algorithm for integer factoring, and sieving is a crucial step in the NFS. It is a very time-consuming operation, whose goal is to collect many relations. The ultimate goal is to generate random smooth integers mod $N$ with their prime decomposition, where smooth is defined on the rational and algebraic sides according to two prime factor bases. In modern factorization tool, such as \textsf{Cado-NFS}, sieving is split...

The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic $p$ given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key...

Verifiable Computation (VC) schemes provide a mechanism for verifying the output of a remotely executed program. These are used to support computing paradigms wherein a computationally restricted client, the Verifier, wishes to delegate work to a more powerful but untrusted server, the Prover. The Verifier wishes to detect any incorrect results, be they accidental or malicious. The current state-of-the-art is only close-to-practical, usually because of a computationally demanding setup...

Digital signatures are one of the most basic cryptographic building blocks which are utilized to provide attractive security features like authenticity, unforgeability, and undeniability. The security of existing state of the art digital signatures is based on hardness of number theoretic hardness assumptions like discrete logarithm and integer factorization. However, these hard problems are insecure and face a threat in the quantum world. In particular, quantum algorithms like Shor’s...

In recent years, mixed integer linear programming (MILP, in short) gradually becomes a popular tool of automated cryptanalyses in symmetric ciphers, which can be used to search differential characteristics and linear approximations with high probability/correlation. A key problem in the MILP method is how to build a proper model that can be solved efficiently in the MILP solvers like Gurobi or Cplex. It is known that a MILP problem is NP-hard, and the numbers of variables and inequalities...

Evaluating exact computational resources necessary for factoring large integers by Shor algorithm using an ideal quantum computer is difficult because simplified circuits were used in past experiments, in which qubits and gates were reduced as much as possible by using the features of the integers, though 15 and 21 were factored on quantum computers. In this paper, we implement Shor algorithm for general composite numbers, and factored 96 RSA-type composite numbers up to 9-bit using a...

The use of traditional cryptography based on symmetric keys has been replaced with the revolutionary idea discovered by Diffie and Hellman in 1976 that fundamentally changed communication systems by ensuring a secure transmission of information over an insecure channel. Nowadays public key cryptography is frequently used for authentication in e-commerce, digital signatures and encrypted communication. Most of the public key cryptosystems used in practice are based on integer factorization...

We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally $(N, N)$-split for each integer $N \leq 11$. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime $p$ is 100 bits, the attack is sped up by a factor $25{\tt x}$; when the underlying prime is 200 bits, the attack is sped up by a...

In this work we extend the known pseudorandomness of Ring-LWE (RLWE) to be based on ideal lattices of non Dedekind domains. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the...

We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo $n$, where $n$ is the integer whose factorization is sought. The algorithm has subexponential runtime $\exp(O(\sqrt{\log n \log \log n}))$ (or $\exp(O( (\log n)^{1/3} (\log \log n)^{2/3} ))$ with the addition of a number field sieve), but requires...

Since the formalization of Verifiable Delay Functions (VDF) by Boneh et al. in 2018, VDFs have been adopted for use in blockchain consensus protocols and random beacon implementations. However, the impending threat to VDF-based applications comes in the form of Shor’s algorithm running on quantum computers in the future which can break the discrete logarithm and integer factorization problems that existing VDFs are based on. Clearly, there is a need for quantum-secure VDFs. In this paper, we...

In this paper, we perform a systematic study of functions $f: \mathbb{Z}_{p^e} \to \mathbb{Z}_{p^e}$ and categorize those functions that can be represented by a polynomial with integer coefficients. More specifically, we cover the following properties: necessary and sufficient conditions for the existence of an integer polynomial representation; computation of such a representation; and the complete set of equivalent polynomials that represent a given function. As an application, we use...

The celebrated LLL algorithm for Euclidean lattices is central to cryptanalysis of well- known and deployed protocols as it provides approximate solutions to the Shortest Vector Problem (SVP). Recent interest in algebrically structured lattices (e.g., for the efficient implementation of lattice- based cryptography) has prompted adapations of LLL to such structured lattices, and, in particular, to module lattices, i.e., lattices that are modules over algebraic ring extensions of the integers....

The history of equations dates back to thousands of years ago, though the equals sign "=" was only invented in 1557. We formalize the processes of "decomposition" and "restoration" in mathematics and physics by defining "discrete exponential equations" and "noisy equation systems" over an abstract structure called a "land", which is more general than fields, rings, groups, and monoids. Our abstract equations and systems provide general languages for many famous computational problems such as...

We give a probabilistic polynomial time algorithm for high F_ell-rank subset product problem over the order O_K of any algebraic field K with O_K a principal ideal domain and the ell-th power residue symbol in O_K polynomial time computable, for some rational prime ell.

We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Lyubashevsky et al. (Crypto 2022) together with an improved, over prior lattice-based one-out-of-many proofs, recursive procedure, and a novel rejection sampling proof that allows to use the efficient bimodal rejection sampling throughout the...

The question whether one way functions (i.e., functions that are easy to compute but hard to invert) exist is arguably one of the central problems in complexity theory, both from theoretical and practical aspects. While proving that such functions exist could be hard, there were quite a few attempts to provide functions which are one way "in practice", namely, they are easy to compute, but there are no known polynomial time algorithms that compute their (generalized) inverse (or that...

Homomorphic encryption (HE) has opened an entirely new world up in the privacy-preserving use of sensitive data by conducting computations on encrypted data. Amongst many HE schemes targeting computation in various contexts, Cheon--Kim--Kim--Song (CKKS) scheme is distinguished since it allows computations for encrypted real number data, which have greater impact in real-world applications. CKKS scheme is a levelled homomorphic encryption scheme, consuming one level for each homomorphic...

We present an efficient key recovery attack on the Supersingular Isogeny Diffie-Hellman protocol (SIDH). The attack is based on Kani's "reducibility criterion" for isogenies from products of elliptic curves and strongly relies on the torsion point images that Alice and Bob exchange during the protocol. If we assume knowledge of the endomorphism ring of the starting curve then the classical running time is polynomial in the input size (heuristically), apart from the factorization of a small...

In recent years, the number of applications of the repeated squaring assumption has been growing rapidly. The assumption states that, given a group element $x$, an integer $T$, and an RSA modulus $N$, it is hard to compute $x^{2^T} \mod N$---or even decide whether $y\stackrel{?}{=}x^{2^T} \mod N$---in parallel time less than the trivial approach of computing $T$ sequential squarings. This rise has been driven by efficient interactive proofs for repeated squaring, opening the door to more...

Quantum computers will break cryptographic primitives that are based on integer factorization and discrete logarithm problems. SABER is a key agreement scheme based on the Learning With Rounding problem that is quantum-safe, i.e., resistant to quantum computer attacks. This article presents a high-speed silicon implementation of SABER in a 65nm technology as an Application Specific Integrated Circuit. The chip measures 1$mm^2$ in size and can operate at a maximum frequency of 715$MHz$ at a...

We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works arXiv:1612.01011 and arXiv:1612.02689, we show that taking probabilistic mixtures of channels to solve fallback (arXiv:1409.3552) and magnitude approximation problems saves factor of two in approximation costs. In particular,...

Fully homomorphic encryption (FHE) provides a natural solution for privacy-preserving cloud computing, but a straightforward FHE protocol may suffer from high computational overhead and a large ciphertext expansion rate, especially for computation-intensive tasks over large data, which are the main obstacles toward practical privacy-preserving cloud computing. In this paper, we present HEAD, a generic privacy-preserving cloud computing protocol that can be based on most mainstream (typically...

Many currently deployed public-key cryptosystems are based on the difficulty of the discrete logarithm and integer factorization problems. However, given an adequately sized quantum computer, these problems can be solved in polynomial time as a function of the key size. Due to the future threat of quantum computing to current cryptographic standards, alternative algorithms that remain secure under quantum computing are being evaluated for future use. As a part of this evaluation,...

The RSA cryptosystem comprises of two important features that are needed for encryption process known as the public parameter $e$ and the modulus $N$. In 1999, a cryptanalysis on RSA which was described by Boneh and Durfee focused on the key equation $ed-k\phi(N)=1$ and $e$ of the same magnitude to $N$. Their method was applicable for the case of $d<N^{0.292}$ via Coppersmith’s technique. In 2012, Kumar et al. presented an improved Boneh-Durfee attack using the same equation which is valid...

The public parameters of the RSA cryptosystem are represented by the pair of integers $N$ and $e$. In this work, first we show that if $e$ satisfies the Diophantine equation of the form $ex^2-\phi(N)y^2=z$ for appropriate values of $x, y$ and $z$ under certain specified conditions, then one is able to factor $N$. That is, the unknown $\frac{y}{x}$ can be found amongst the convergents of $\frac{\sqrt{e}}{\sqrt{N}}$ via continued fractions algorithm. Consequently, Coppersmith's theorem is...

We describe a technique to backdoor a prime factor of a composite odd integer $N$, so that an attacker knowing a possibly secret factor base $\mathcal{B}$, can efficiently retrieve it from $N$. Such method builds upon Complex Multiplication theory for elliptic curves, by generating primes $p$ associated to $\mathcal{B}$-smooth order elliptic curves over $\mathbb{F}_p$. When such primes $p$ divide an integer $N$, the latter can be efficiently factored using a generalization of Lenstra's...

$\newcommand{\Z}{\mathbb{Z}} \newcommand{\basis}{B}$We study the computational problem of finding a shortest non-zero vector in a rotation of $\Z^n$, which we call $\Z$SVP. It has been a long-standing open problem to determine if a polynomial-time algorithm for $\Z$SVP exists, and there is by now a beautiful line of work showing how to solve it efficiently in certain very special cases. However, despite all of this work, the fastest known algorithm that is proven to solve $\Z$SVP is still...

Many currently deployed public-key cryptosystems are based on the difficulty of the discrete logarithm and integer factorization problems. However, given an adequately sized quantum computer, these problems can be solved in polynomial time as a function of the key size. Due to the future threat of quantum computing to current cryptographic standards, alternative algorithms that remain secure under quantum computing are being evaluated for future use. One such algorithm is CRYSTALS-Dilithium,...

We initiate the study of a problem called the Polynomial Independence Distinguishing Problem (PIDP). The problem is parameterized by a set of polynomials $\mathcal{Q}=(q_1,\ldots, q_m)$ where each $q_i:\mathbb{R}^n\rightarrow \mathbb{R}$ and an input distribution $\mathcal{D}$ over the reals. The goal of the problem is to distinguish a tuple of the form $\{ q_i,q_i(\mathbf{x})\}_{i\in [m]} $ from $\{ q_i,q_i(\mathbf{x}_i)\}_{i\in [m]} $ where $\mathbf{x}, \mathbf{x}_1,\ldots ,...

A natural and recurring idea in the knapsack/lattice cryptography literature is to start from a lattice with remarkable decoding capability as your private key, and hide it somehow to make a public key. This is also how the code-based encryption scheme of McEliece (1978) proceeds. This idea has never worked out very well for lattices: ad-hoc approaches have been proposed, but they have been subject to ad-hoc attacks, using tricks beyond lattice reduction algorithms. On the other hand the...

We argue that for all integers $N \geq 2$ and $g \geq 1$ there exist "multiradical" isogeny formulae, that can be iteratively applied to compute $(N^k, \ldots, N^k)$-isogenies between principally polarized $g$-dimensional abelian varieties, for any value of $k \geq 2$. The formulae are complete: each iteration involves the extraction of $g(g+1)/2$ different $N$th roots, whence the epithet multiradical, and by varying which roots are chosen one computes all $N^{g(g+1)/2}$ extensions to an...

To factor an integer $N$ we construct $n$ triples of $p_n$-smooth integers $u,v,|u-vN|$ for the $n$-th prime $p_n$. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice $\mathcal L(\mathbf R_{n, f})$ with basis matrix $\mathbf R_{n, f} \in \mathbb R^{(n+1)\times(n+1)}$ where $f\colon [1, n]\to[1, n]$ is a permutation of $[1, 2, \ldots, n]$ and $(f(1),\ldots,f(n),N'\ln N)$ is the diagonal and $(N' \ln p_1,\ldots, N' \ln p_n,N' \ln N)$ for $N' =...

Digital signature is one of the most important public key cryptographic primitive for message authentication. In a digital signature scheme, receiver of a message-signature pair gets assurance about the fact that the message belongs to the sender and neither receiver nor any third party can manipulate the message. In the current state of art, most of the existing digital signatures' security relies on classical cryptographic assumption based hard problems, such as discrete log, integer...

Machine Learning (ML) algorithms, especially deep neural networks (DNN), have proven themselves to be extremely useful tools for data analysis, and are increasingly being deployed in systems operating on sensitive data, such as recommendation systems, banking fraud detection, and healthcare systems. This underscores the need for privacy-preserving ML (PPML) systems, and has inspired a line of research into how such systems can be constructed efficiently. We contribute to this line of...

The idea of hybrid homomorphic encryption (HHE) is to drastically reduce bandwidth requirements when using homomorphic encryption (HE) at the cost of more expensive computations in the encrypted domain. To this end, various dedicated schemes for symmetric encryption have already been proposed. However, it is still unclear if those ideas are already practically useful, because (1) no cost-benefit analysis was done for use cases and (2) very few implementations are publicly available. We...

The advent of a full-scale quantum computer will severely impact most currently-used cryptographic systems. The most well-known aspect of this impact lies in the computational-hardness assumptions that underpin the security of most current public-key cryptographic systems: a quantum computer can factor integers and compute discrete logarithms in polynomial time, thereby breaking systems based on these problems. However, simply replacing these problems by other which are (believed to be)...

Secure multiparty generation of an RSA biprime is a challenging task, which increasingly receives attention, due to the numerous privacy-preserving applications that require it. In this work, we construct a new protocol for the RSA biprime generation task, secure against a malicious adversary, who can corrupt any subset of protocol participants. Our protocol is designed for generic MPC, making it both platform-independent and allowing for weaker security models to be assumed (e.g., honest...

Revocable hierarchical identity-based encryption (RHIBE) is an extension of hierarchical identity-based encryption (HIBE) supporting the key revocation mechanism. In this paper, we propose a generic construction of RHIBE from HIBE with the complete subtree method. Then, we obtain the first RHIBE schemes under the quadratic residuosity assumption, CDH assumption without pairing, factoring Blum integers, LPN assumption, and code-based assumption, and the first almost tightly secure RHIBE...

The Ring-LWE over two-to-power cyclotomic integer rings has been the hard computational problem for lattice cryptographic constructions. Its hardness and the conjectured hardness of approximating ideal SIVP for ideal lattices in two-to-power cyclotomic fields have been the fundamental open problems in lattice cryptography and the computational number theory. In our previous paper we presented a general theory of subset attack on the Ring-LWE with not only the Gaussian error distribution but...

We construct public-coin time- and space-efficient zero-knowledge arguments for $\mathbf{NP}$. For every time $T$ and space $S$ non-deterministic RAM computation, the prover runs in time $T \cdot \mathrm{polylog}(T)$ and space $S \cdot \mathrm{polylog}(T)$, and the verifier runs in time $n \cdot \mathrm{polylog}(T)$, where $n$ is the input length. Our protocol relies on hidden order groups, which can be instantiated with a trusted setup from the hardness of factoring (products of safe...

To factor an integer $N$ we construct $n$ triples of $p_n$-smooth integers $u,v,|u-vN|$ for the $n$-th prime $p_n$. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice $\mathcal{L}(\mathbf{R}_{n,f})$ with basis matrix $\mathbf{R}_{n,f} \in \mathbb{R}^{(n+1)\times (n+1)}$ where $f : [1,n] \rightarrow [1,n]$ is a permutation of $[1,2,...,n]$ and $(f(1),...,f(n), N'\ln N)$ is the diagonal and (N'\ln p_1, \ldots, N'\ln p_n, N'\ln N) for...

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. This would jeopardize IT security as we know it. In this work, we investigate two quantum-safe, hash-based signature schemes published by the Internet Engineering Task Force and submitted to the National Institute of Standards and Technology for use...

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. All currently used, public-key cryptography algorithms would be deemed insecure in a post-quantum setting. In response, the United States National Institute of Standards and Technology has initiated a process to standardize quantum-resistant...

Prime integers are the backbone of most public key cryptosystems. Attacks often go after the primes themselves, as in the case of all factoring and index calculus algorithms. Primes are time sensitive cryptographic material and should be periodically changed. Unfortunately many systems use fixed primes for a variety of reasons, including the difficulty of generating trusted, random, cryptographically secure primes. This is particularly concerning in the case of discrete log based...

We present a two-message oblivious transfer protocol achieving statistical sender privacy and computational receiver privacy based on the RLWE assumption for cyclotomic number fields. This work improves upon prior lattice-based statistically sender-private oblivious transfer protocols by reducing the total communication between parties by a factor $O(n\log q)$ for transfer of length $O(n)$ messages. Prior work of Brakerski and Döttling uses transference theorems to show that either a...

We give a sieving algorithm for finding pairs of consecutive smooth numbers that utilizes solutions to the Prouhet-Tarry-Escott (PTE) problem. Any such solution induces two degree-$n$ polynomials, $a(x)$ and $b(x)$, that differ by a constant integer $C$ and completely split into linear factors in $\mathbb{Z}[x]$. It follows that for any $\ell \in \mathbb{Z}$ such that $a(\ell) \equiv b(\ell) \equiv 0 \bmod{C}$, the two integers $a(\ell)/C$ and $b(\ell)/C$ differ by 1 and necessarily contain...

Modern public-key cryptography is a crucial part of our contemporary life where a secure communication channel with another party is needed. With the advance of more powerful computing architectures – especially Graphics Processing Units (GPUs) – traditional approaches like RSA and Di&#64259;e-Hellman schemes are more and more in danger of being broken. We present a highly optimized implementation of Lenstra’s ECM algorithm customized for GPUs. Our implementation uses state-of-the-art...

The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is currently the most efficient method to perform approximate homomorphic computations over real and complex numbers. Although the CKKS scheme can already be used to achieve practical performance for many advanced applications, e.g., in machine learning, its broader use in practice is hindered by several major usability issues, most of which are brought about by relatively high approximation errors and the complexity of dealing with...

Approx-SVP is a well-known hard problem on lattices, which asks to find short vectors on a given lattice, but its variant restricted to ideal lattices (which correspond to ideals of the ring of integers $\mathcal{O}_{K}$ of a number field $K$) is still not fully understood. For a long time, the best known algorithm to solve this problem on ideal lattices was the same as for arbitrary lattice. But recently, a series of works tends to show that solving this problem could be easier in ideal...

Shor's quantum algorithm, running in quantum computers, can efficiently solve integer factorization problem and discrete logarithm problem in polynomial time. This poses an urgent and serious threat to long-term security with recent accelerated evolution of quantum computing. However, National Institute of Standards and Technology (NIST) plans to release its standard of post-quantum cryptography between 2022 and 2024. It is crucially important to propose an early solution, which is...

A common approach to bootstrapping a new cryptocurrency is an airdrop, an arrangement in which existing users give away currency to entice new users to join. But current airdrops offer no recipient privacy: they leak which recipients have claimed the funds, and this information is easily linked to off-chain identities. In this work, we address this issue by defining a private airdrop and describing concrete schemes for widely-used user credentials, such as those based on ECDSA and RSA. ...

In their seminal work, Ben-Or and Linial (1985) introduced the full information model for collective coin-tossing protocols involving $n$ processors with unbounded computational power using a common broadcast channel for all their communications. The design and analysis of coin-tossing protocols in the full information model have close connections to diverse fields like extremal graph theory, randomness extraction, cryptographic protocol design, game theory, distributed protocols, and...

We construct a practical lattice-based zero-knowledge argument for proving multiplicative relations between committed values. The underlying commitment scheme that we use is the currently most efficient one of Baum et al. (SCN 2018), and the size of our multiplicative proof ($9$KB) is only slightly larger than the $7$KB required for just proving knowledge of the committed values. We additionally expand on the work of Lyubashevsky and Seiler (Eurocrypt 2018) by showing that the...

This work introduces novel techniques to improve the translation between arithmetic and binary data types in secure multi-party computation. We introduce a new approach to performing these conversions using what we call extended doubly-authenticated bits (edaBits), which correspond to shared integers in the arithmetic domain whose bit decomposition is shared in the binary domain. These can be used to considerably increase the efficiency of non-linear operations such as truncation, secure...

Quantum computers promise to solve hard mathematical problems such as integer factorization and discrete logarithms in polynomial time, making standardized public-key cryptography (such as digital signature and key agreement) insecure. Lattice-Based Cryptography (LBC) is a promising post-quantum public-key cryptographic protocol that could replace standardized public-key cryptography, thanks to the inherent post-quantum resistant properties, efficiency, and versatility. A key mathematical...

The $e$-th power residue symbol $\left(\frac{\alpha}{\mathfrak{p}}\right)_e$ is a useful mathematical tool in cryptography, where $\alpha$ is an integer, $\mathfrak{p}$ is a prime ideal in the prime factorization of $p\mathbb{Z}[\zeta_e]$ with a large prime $p$ satisfying $e \mid p-1$, and $\zeta_e$ is an $e$-th primitive root of unity. One famous case of the $e$-th power symbol is the first semantic secure public key cryptosystem due to Goldwasser and Micali (at STOC 1982). In this paper,...

The Lyness map is a birational map in the plane which provides one of the simplest discrete analogues of a Hamiltonian system with one degree of freedom, having a conserved quantity and an invariant symplectic form. As an example of a symmetric Quispel-Roberts-Thompson (QRT) map, each generic orbit of the Lyness map lies on a curve of genus one, and corresponds to a sequence of points on an elliptic curve which is one of the fibres in a pencil of biquadratic curves in the plane. We...

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. All currently used public key algorithms would be deemed insecure in a post-quantum (PQ) setting. In response, the National Institute of Standards and Technology (NIST) has initiated a process to standardize quantum-resistant crypto algorithms,...

Microarchitecture based side-channel attacks are common threats nowadays. Intel SGX technology provides a strong isolation from an adversarial OS, however, does not guarantee protection against side-channel attacks. In this paper, we analyze the security of the mbedTLS binary GCD algorithm, an implementation that offers interesting challenges when compared for example with OpenSSL, due to the usage of very tight loops in the former. Using practical experiments we demonstrate the mbedTLS...

The Supersingular Isogeny-based Diffie-Hellman key exchange protocol (SIDH) was introduced by Jao an De Feo in 2011. SIDH operates on supersingular elliptic curves defined over quadratic extension fields of the form GF($p^2$), where $p$ is a large prime number of the form $p = 4^{e_A} 3^{e_B} - 1,$ where $e_A, e_B$ are positive integers such that $4^{e_A} \approx 3^{e_B}.$ In this paper, a variant of the SIDH protocol that we dubbed extended SIDH (eSIDH) is presented. The eSIDH variant ...

We introduce a framework generalizing lattice reduction algorithms to module lattices in order to practically and efficiently solve the $\gamma$-Hermite Module-SVP problem over arbitrary cyclotomic fields. The core idea is to exploit the structure of the subfields for designing a doubly-recursive strategy of reduction: both recursive in the rank of the module and in the field we are working in. Besides, we demonstrate how to leverage the inherent symplectic geometry existing in the tower of...

The recent advances and attention to quantum computing have raised serious security concerns among IT professionals. The ability of a quantum computer to efficiently solve (elliptic curve) discrete logarithm, and integer factorization problems poses a threat to current public key exchange, encryption, and digital signature schemes. Consequently, in 2016 NIST initiated an open call for quantum-resistant crypto algorithms. This process, currently in its second round, has yielded nine...

A {\em blackbox} secret sharing (BBSS) scheme works in exactly the same way for all finite Abelian groups $G$; it can be instantiated for any such group $G$ and {\em only} black-box access to its group operations and to random group elements is required. A secret is a single group element and each of the $n$ players' shares is a vector of such elements. Share-computation and secret-reconstruction is by integer linear combinations. These do not depend on $G$, and neither do the privacy and...

We show a reduction of integer (semiprimes) factorization problem to a $NP$-complete problem related to coding. Our results rigorously imply the existence of a quantum computer could possibly devastate existing security system relies on NP-hard problem.

Let $N=pq$ be an RSA modulus and $e$ be a public exponent. Numerous attacks on RSA exploit the arithmetical properties of the key equation $ed-k(p-1)(q-1)=1$. In this paper, we study the more general equation $eu-(p-s)(q-r)v=w$. We show that when the unknown integers $u$, $v$, $w$, $r$ and $s$ are suitably small and $p-s$ or $q-r$ is factorable using the Elliptic Curve Method for factorization ECM, then one can break the RSA system. As an application, we propose an attack on Demytko's...

The arbitrary-centered discrete Gaussian sampler is a fundamental subroutine in implementing lattice trapdoor sampling algorithms. However, existing approaches typically rely on either a fast implementation of another discrete Gaussian sampler or pre-computations with regards to some specific discrete Gaussian distributions with fixed centers and standard deviations. These approaches may only support sampling from standard deviations within a limited range, or cannot efficiently sample from...

A hash function family is called correlation intractable if for all sparse relations, it hard to find, given a random function from the family, an input output pair that satisfies the relation. Correlation intractability (CI) captures a strong Random Oracle like property of hash functions. In particular, when security holds for all sparse relations, CI suffices for guaranteeing the soundness of the Fiat-Shamir transformation from any constant round, statistically sound interactive proof to a...

Till now, the only reduction from the module learning with errors problem (MLWE) to the ring learning with errors problem (RLWE) is given by Albrecht $et\ al.$ in ASIACRYPT $2017$. Reductions from search MLWE to search RLWE were satisfactory over power-of-$2$ cyclotomic fields with relative small increase of errors. However, a direct reduction from decision MLWE to decision RLWE leads to a super-polynomial increase of errors and does not work even in the most special cases-\ -power-of-$2$...

In this work, we discuss our successful efforts for industry deployment of a cryptographic secure computation protocol. The problem we consider is privately computing aggregate conversion rate of advertising campaigns. This underlying functionality can be abstracted as Private Intersection-Sum (PI-Sum) with Cardinality. In this setting two parties hold datasets containing user identifiers, and one of the parties additionally has an integer value associated with each of its user identifiers....

We develop exact formulas for the distribution of quadratic residues and non-residues in sets of the form $a+X=\{(a+x)\bmod n\mid x\in X\}$, where $n$ is a prime or the product of two primes and $X$ is a subset of integers with given Jacobi symbols modulo prime factors of $n$. We then present applications of these formulas to Cocks' identity-based encryption scheme and statistical indistinguishability.

We present a fully homomorphic encryption scheme continuing the line of works of Ducas and Micciancio (2015, [DM15]), Chillotti et al. (2016, [CGGI16a]; 2017, [CGGI17]; 2018, [CGGI18a]), and Gao (2018,[Gao18]). Ducas and Micciancio (2015) show that homomorphic computation of one bit operation on LWE ciphers can be done in less than a second, which is then reduced by Chillotti et al. (2016, 2017, 2018) to 13ms. According to Chillotti et al. (2018, [CGGI18b]), the cipher expansion for TFHE is...

In this paper, we describe an attack on RSA cryptosystem which is based on Euclid's algorithm. Given a public key $(n,e)$ with corresponding private key $d$ such that $e$ has the same order of magnitude as $n$ and one of the integers $k = (ed-1)/\phi(n)$ and $e-k$ has at most one-quarter as many bits as $e$, it computes the factorization of $n$ in deterministic time $O((\log n)^2)$ bit operations.