Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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(...
Turbo's user avatar
  • 13.9k
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,...
joro's user avatar
  • 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 $\...
joro's user avatar
  • 25.4k
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$, ...
joro's user avatar
  • 25.4k
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(...
Joseph Van Name's user avatar
10 votes
3 answers
3k views

Reduction from factoring to solving Pell equation

The paper Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem claims There are reductions from factoring to solving Pell’s equation, and from solving Pell’s ...
joro's user avatar
  • 25.4k