Questions tagged [cryptography]

Questions concerning the mathematics of secure communication. Relevant topics include elliptic curve cryptography, secure key exchanges, and public-key cryptography (eg. the RSA cryptosystem).

Filter by
Sorted by
Tagged with
77 votes
13 answers
8k views

What computational problems would be good proof-of-work problems for cryptocurrency mining?

What computational mathematics problems that could be used as proof-of-work problems for cryptocurrencies? To make this question easier to answer, I want proof-of-work systems that work in ...
Joseph Van Name's user avatar
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 ...
joro's user avatar
  • 24.2k
4 votes
0 answers
589 views

What solutions to useful computational problems could be rewarded through cryptocurrency smart contracts?

What kinds of cryptocurrency smart contracts could be used to reward people for solving specific kinds of useful computational problems? Background In this question, I asked for proposals for useful ...
Joseph Van Name's user avatar
2 votes
0 answers
86 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
  • 24.2k
2 votes
0 answers
94 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
  • 24.2k
15 votes
2 answers
938 views

Factorization when a factor is partially known

Let's say that I have a very large number of the order ($10^{250+}$) which is composite. I have been given one of its factor partially to a significant amount of digits (say 75+). Then, how can I ...
Student's user avatar
  • 153
12 votes
2 answers
617 views

“The Two Sheriffs” puzzle -2: threshold for security

I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects. ...
Alexey Ustinov'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
  • 24.2k
8 votes
1 answer
574 views

Inverting a function

I posted this question on crypto.SE but got no answer: Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$ Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-i} } $ be the ...
user avatar
7 votes
1 answer
1k views

Modular polynomials for elliptic curves point counting

The Schoof-Elkies-Atkin (SEA) algorithm (for counting points on elliptic curves over a finite field) performs computations over polynomials modulo some modular polynomials. Originally the "classical" ...
Calodeon's user avatar
  • 637
5 votes
1 answer
337 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 ...
joro's user avatar
  • 24.2k
5 votes
2 answers
495 views

Diffie Hellman cryptography based on graph isomorphism?

We got a cryptographic algorithm and computer implementation based on graph isomorphism. An isomorphism between two graphs is a bijection between their vertices that pre serves the edges. For a graph $...
joro's user avatar
  • 24.2k
5 votes
1 answer
554 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 ...
joro's user avatar
  • 24.2k
4 votes
0 answers
237 views

Can we make cryptography signature algorithm based on hardness of isomorphism?

In public key cryptography, Alice knows functions $f$ and its inverse $f^{-1}$. $f$ is public and $f^{-1}$ is secret. To sign a message $m$, she gives $(m,a=f^{-1}(m))$. To verify a signature, the ...
joro's user avatar
  • 24.2k
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'...
Gray Taylor's user avatar
2 votes
1 answer
734 views

Canonical lifts from $\mathbb F_q$ and CM-theory

One knows that (ordinary) Jacobians of hyperelliptic curves over a finite field $\mathbb F_q$ (mostly of genus 1 (elliptic curves) and 2) are extensively studied by cryptographers, as a platform for ...
Calodeon's user avatar
  • 637
1 vote
0 answers
131 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
1 vote
0 answers
97 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
  • 24.2k