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).
18 questions
76
votes
13
answers
9k
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 ...
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
4
votes
0
answers
601
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 ...
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
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
15
votes
2
answers
1k
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 ...
- 153
12
votes
2
answers
621
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.
...
- 12.3k
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
...
- 25.4k
8
votes
1
answer
579
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 ...
user6671
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" ...
- 647
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
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 ...
- 25.4k
5
votes
2
answers
534
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 $...
- 25.4k
4
votes
0
answers
245
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 ...
- 25.4k
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'...
- 873
2
votes
1
answer
801
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 ...
- 647
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 $\...
- 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(...