All Questions
Tagged with cryptography nt.number-theory
69 questions
2
votes
0
answers
110
views
How to apply Pohlig Hellman using a very limited set of auxiliary inputs in that case?
So I was reading about Talotti, Paier, and Miculan - ECC’s Achilles’ Heel: Unveiling Weak Keys in Standardized Curves. The underlying idea is to lift the discrete logarithm problem to $\mathrm{prime}−...
- 87
0
votes
0
answers
141
views
State of the art on attempts to solve the elliptic curve discrete logarithm problem through transfering the problem to a weaker curve
Let an elliptic curve $E$, and 2 points on such curve $P$ and $O$ the methods I’m talking about consist in creating a weaker elliptic curve $F$ and mapping $P$ and $O$ to $F$ while successfully ...
- 87
-1
votes
0
answers
74
views
Why is there in theory no morphism/isogenies when enlarging a prime field sharing a common suborder/subgroup? [closed]
Simple question : I have a prime field having modulus $p$ where $p−1$ contains $O$ as prime factor, and I have a larger prime field $q$ also having $O$ as its suborder/subgroup. Why are there no ...
- 12.9k
1
vote
0
answers
69
views
Is it in theory possible to perform general Miller’s algorithm inversion as used with the optimal ate pairing with large trace in subexponential time?
Let’s I have the following :
2 curves $G_1$ defined on $F_p$ and $G_2$ being the $G_1$ curve’s twist defined on $F_p^2$ both having the same prime order ; a large trace ; and $F_p^{12}$ as their ...
- 87
0
votes
0
answers
123
views
Is it in theory possible to create a subexponential algorithm for solving discrete logarithms in multiplicative subgroups or within an Integer range?
As far I understand, when it comes to finite fields, Pollard rho and Pollard’s lambda are still the best algorithm for solving discrete logarithms in a multiplicative subgroup/suborder…
Index calculus ...
- 87
1
vote
0
answers
69
views
If we allow DH operations in addition to exponentiation and multiplication can we get a lower bound for discrete logarithm?
In https://crypto.stackexchange.com/questions/72969/proof-dlog-is-hard-in-generic-group-model/ it is shown if we allow only exponentiation and multiplication we can get an exponential complexity lower ...
- 13.9k
0
votes
0
answers
103
views
On MSB and LSB of Diffie Hellman
Given generator $g$ of multiplicative cyclic group modulo $p$ a prime and two elements $h_1$ and $h_2$ such that there are $x_1$ and $x_2$ respectively satisfying $g^{x_i}=h_i\bmod p$ at every $i\in\{...
- 12.9k
3
votes
0
answers
85
views
When is the number-theoretic transform of small vectors again small?
I am currently working on an idea in the context of lattice-based cryptography, but the problem that I am currently stuck on seems to have almost nothing to do with lattices anymore.
In particular, my ...
- 131
4
votes
0
answers
169
views
Square hidden number problem
Suppose I have a mystery number $m$ modulo $p$ that I wish to find. I know the value of $m+x_i^2$ where $x_i$ is randomly chosen modulo $p$ for some large number of different $x_i$, $N$ many, $N \gg \...
2
votes
0
answers
184
views
Will Coppersmith's method work for this bivariate modular polynomial shape?
I have a bivariate modular polynomial of shape
$$f(x,y)=x^2y-g(x)\equiv 0\bmod q$$
where
$q=(2p-1)(2p+1)$ is a product of two primes $2p-1$ and $2p+1$,
$g(x)\in\mathbb Z[x]$ is of degree four and
$f(...
- 13.9k
1
vote
0
answers
102
views
Question on definition of inverse number theoretic transformation
In the paper Porkodi and Arumuganathan - Public key cryptosystem based on number theoretic transforms I found the following statement on the second page regarding the Inverse Number Theoretic ...
- 12.9k
2
votes
0
answers
87
views
Complexity of finding solutions of trapdoored polynomial?
Related to this question Cryptography signature scheme based on hardness of finding points on varieties.
Working over $K=\mathbb{Q}[x_1,...,x_n,y_1,...y_m]$.
By abuse of notation, for polynomial $f$, ...
- 25.4k
1
vote
0
answers
98
views
Hardness of solving $0=\sum_{i=1}^k \operatorname{linear}_i(x_1,\ldots,x_n)^D$ over the rationals
This is related to cryptography and this question
and another question.
In short, we are asking about decomposing multivariate polynomial
as sum of perfect powers of linear polynomials.
Working over $\...
2
votes
0
answers
96
views
Cryptography signature scheme based on hardness of finding points on varieties?
Related to this question Complexity of finding solutions of trapdoored polynomial.
I am trying to build signature scheme based on hardness
of finding points on varieties.
Let $K$ be field and $M=K[x_1,...
- 25.4k
1
vote
1
answer
185
views
Deduce kernel of isogeny from action on torsion points
I'm stuck with the following problem:
In Petit's work "Faster Algorithms for Isogeny Problems using Torsion Point Images", p. 8, he says that we can deduce $\ker \psi_{N_2}$ knowing the ...
- 12.9k
4
votes
1
answer
363
views
What is meant by a meet-in-the-middle approach?
I'm studing C. Petit's work "Faster algorithms for isogeny problems using torsion point images" (link) and he talks about meet-in-the-middle approach/strategy for solve some isogenies ...
- 188k
2
votes
0
answers
123
views
On choosing the correct square root of $g^{4n}$ modulo primes
Let $p$ be prime congruent to $3$ modulo $4$.
The discrete logarithm problem asks: given $g,a,p$
such that $g^x \equiv a \pmod{p}$, find $x$.
Assume $g$ is of maximal multiplicative order.
In an ...
- 25.4k
2
votes
0
answers
145
views
Showing that a crypto hash function is not permutation, possibly conditionally?
Let $f$ be some crypto hash function, say MD5 with output $n$ bits. Restrict the input to $n$ bits.
Cryptographer told me it is open problem if such restricted collision
exists, i.e. $f(x)=f(y),x \ne ...
CommunityBot
- 1
1
vote
0
answers
133
views
The security of one-time digital signatures from a solution to a diophantine equations
I wonder how well arbitrary Diophantine equations can be used to make one time digital signature schemes.
For our one-time digital signature scheme, the public key is a collection of polynomials $f_1(...
16
votes
4
answers
3k
views
Zero-knowledge proof of positivity
If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?
My bounty is ending ...
- 1,446
2
votes
1
answer
172
views
On roots of irreducible quadratics modulo composites
Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$
Is this problem equivalent to any hardness results?
- 13.9k
6
votes
1
answer
566
views
Public key cryptography based on non-invertible matrices?
Added Wed 13 Apr 2022
I have written a short note with experimental data,
which shows not all pseudo keys are good keys.
Public key cryptography based on non-invertible matrices
We got public key ...
- 25.4k
-1
votes
1
answer
186
views
Public key cryptography based on non-invertible matrices, part II
Closely related to this question
and extending comment
of R. van Dobben de Bruyn.
Working over $\mathbb{F}_p$ and all matrices of square $n \times n$.
Alice chooses invertible $X_A$ and non-...
- 12.9k
6
votes
1
answer
418
views
Groups in which Computational Diffie Hellman is in $P$ but Discrete Logarithm is not known to be in $P$
The Computational Diffie Hellman (CDH) problem is to compute $g^{XY}$ given $g^X$ and $g^Y$ where $g$ generates the group. The Discrete Logarithm (DLOG) problem is to compute $X$ given $g^X$. The ...
- 2,183
3
votes
3
answers
4k
views
Recovering $\Phi(n)$ from a multiple?
I've been attending a series of lectures on Cryptography from an engineering perspective, which means that most of the assertions made are supplied without proof... here's one that the lecturer couldn'...
3
votes
1
answer
266
views
p-adic logarithms with fixed precision
Probably this is easy, but we would like to see it on paper.
Let $p$ be prime and $D,g,n$ positive integers.
Let $A=g^n \bmod p^D$.
Let $\log(p,a,D)$ be the p-adic logarithm with precision $D$.
In ...
CommunityBot
- 1
5
votes
1
answer
359
views
Discrete logarithm and the sequence $a(n)=(g^n \bmod p)^{p-1} \bmod p^2$
Let $p$ be prime and $g,n$ integers.
Define $a(n)=(g^n \bmod p)^{p-1} \bmod p^2$
By mod p we don't mean congruence, but the reduction modulo $p$ operator. $A \bmod ...
- 34.4k
2
votes
2
answers
235
views
On fixed point probability in discrete logarithm
Fix an integer $n>2$.
Question. What is the probability that, for a given $h\in\Bbb Z_n,$ there is no $$x\in[0,\varphi(n)-1]\cap\Bbb Z$$ such that
$h^{x\bmod\varphi(n)}\equiv x\bmod n$?
- 66.3k
2
votes
1
answer
262
views
Are there any homomorphic analog error correction code?
Are there any analog error correction codes that are additively and multiplicatively homomorphic?
- 12.3k
0
votes
0
answers
135
views
Can factorization of very large numbers be aided by associating them with a series (described below) of quadratic polynomials?
My name is J. Calvin Smith. I graduated in 1979 with a Bachelor of Arts in Mathematics from Georgia College in Milledgeville, Georgia. My Federal career (1979-2012) in the US Department of Defense led ...
- 63.9k
3
votes
2
answers
360
views
Reference describing supersingular elliptic curves over algebraically closed field in characteristic 2
I'm looking for a reference for the fact that over an algebraically closed field of characteristic two, there is (essentially) only one supersingular elliptic curve.
This fact appears on Wikipedia, ...
- 879
10
votes
4
answers
1k
views
Number theory in symmetric cryptography
One of the most famous application of number theory is the RSA cryptosystem, which essentially initiated asymmetric cryptography.
I wonder if there are applications of number theory also in symmetric ...
- 4,943
3
votes
1
answer
137
views
Subexponential algorithms that apply only one of factoring and discrete logarithm?
Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants.
What are the subexponential ...
- 879
4
votes
1
answer
103
views
On the average density of non-zero digits of NAFs of fixed length
An NAF is a non-adjacent form of a positive integer $k$.
One of the five properties of NAFs is "The average density of non-zero digits among all NAFs of length $l$ is approximately $1/3$."
...
- 85.6k
3
votes
1
answer
138
views
Given $n, c$ find $a>1,b$ such that $b ^ a \equiv c \pmod n$
Given a natural number $n$ (of unknown factorization) and an arbitrary number $c \in \mathbb{Z}^*_n$ (the set of natural numbers smaller than $n$ and coprime to it), is there an efficient algorithm ...
- 271
1
vote
0
answers
212
views
Generate algorithmically an elliptic curve with its exact class group structure?
Is it possible to generate an elliptic curve $E$ (randomly), together with knowing its class group $\mathrm{Cl}(\mathcal{O})$ structure? where $\mathcal{O}$ is its endomorphism rings $\mathsf{End}(E)$ ...
- 63.9k
20
votes
1
answer
1k
views
Cryptography and elliptic curves
Cryptography sometimes uses elliptic curves over finite fields. Does cryptography also use elliptic curves over $\mathbb{Q}$ or rational points on them?
- 7,377
2
votes
0
answers
121
views
How to choose a prime p s.t. n-th cyclotomic polynomial splits into as much as possible irreducible polynomials while p is almost constant size?
The reason I ask this question is that cyclotomic polynomial is critical to the construction of lattice-based cryptography. In most of the existing lattice-based cryptographic schemes, $n$ is usually ...
- 33
0
votes
1
answer
431
views
Reason Coppersmith fails here?
Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$.
$P$ has a binary expansion and so does $Q$. We can set the binary $0/1$ variables to be $x_1$ through $x_{\lceil\log P\rceil}$ and $...
CommunityBot
- 1
1
vote
0
answers
276
views
Method of Coppersmith optimal for multivariate?
It is shown that Coppersmith method yields optimal integer root extraction for univariate polynomials in https://arxiv.org/abs/1605.08065 and a follow up work attempts this for bivariate polynomials ...
- 13.9k
4
votes
1
answer
288
views
Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?
The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...
- 218
4
votes
1
answer
448
views
Density of integers with a large rough divisor
Let $N < 2^a$ be a positive integer chosen uniformly at random. Let $\tilde{N}$ be the result of removing from $N$ all its prime factors less than $2^b$. What is the probability that $\tilde{N}$ is ...
1
vote
1
answer
142
views
Cryptography with general RSA type integers?
Denote $\mathcal N_r=\{n\in\mathbb Z:\exists\mbox{ distinct equal bit primes }p_1,\dots,p_r:n=p_1p_2\dots p_{r-1}p_r\}$.
$\mathcal N_1$ refers to primes and $\mathcal N_2$ referes to balanced ...
- 10.4k
4
votes
1
answer
425
views
Is it hard to decide whether a matrix is a square of another matrix?
According to the well-know quadratic residue (QR) theory over integers, we know that it is hard to decide whether a given integer $m\in\mathbb Z_N$ is a quadratic residue (i.e., a square of another ...
CommunityBot
- 1
1
vote
1
answer
138
views
How to compute the Müller modular polynomials?
According to R.A.Kazmi's dissertation "Isogenies and Cryptography" (Page 22), given an isogeny degree $l$, the Müller modular polynomials are defined as
$$G_l(x,y)=\sum_{r=0}^{l+1}\sum_{k=0}^{v}a_{...
- 5,407
5
votes
0
answers
317
views
Elliptic curve sequences needed for universal forgery
Elliptic Curve Digital Signature Algorithm (ECDSA) admits universal forgery (UF) if the Attacker can solve the equation
$$z=\frac{f_{k-1}(x,y)f_{k+1}(x,y)}{f_{k}(x,y)^2},$$
where $k$ is unknown, $f_{k}...
- 12.3k
44
votes
1
answer
17k
views
Conjecturally unsafe RSA primes $p=27a^2+27a+7$
We got strong numerical evidence that primes of the form $p=27a^2+27a+7$
are unsafe for cryptographic purposes since they can be found in the factorization.
Consider the following generic factoring ...
- 25.4k
3
votes
0
answers
215
views
Why we are interested in p>3 Schoof's algorithm
In the Schoof's algorithm we are particularly interested in $char(K)>3$, where $K$ is the field. I know Schoof's algorithm is mostly used over large prime fields. Also, when we are transforming ...
- 17.6k
2
votes
0
answers
88
views
Example of action of an infinitely countable group that has important ergodic/statistical property?
I work in probability and I am looking for an important example of action of an amenable countable group in other areas of math for which the (pointwise) ergodic theorem is actually quite important. ...
- 1,583
4
votes
3
answers
5k
views
modular exponentation for RSA, why is 2^16 + 1 commonly chosen?
I know that the number 216 + 1 is commonly used for RSA, since 0b 1 0000 0000 0000 0001 only contains two 1 bits. Many sites explain that this makes modular exponentiation faster, but I haven't come ...