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).
203 questions
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
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
-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 ...
- 87
1
vote
1
answer
207
views
A candidate for one-way functions
For every $n \geq 3$ consider a bipartite random $3$-regular graph $G_n$ with two parts $X=\{x_1, \dotsc, x_n\}$ and $Y=\{y_1, \dotsc, y_n\}$. For any $i \leq n$ assign either 0 or 1 to each vertex $...
- 11
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
15
votes
1
answer
1k
views
A cipher proposed by Littlewood
In J. E. Littlewood's, "A Mathematicians Miscellany" there is the following passage about ciphers. I found it interesting for a couple of reasons.
First of all the "legend that every ...
6
votes
0
answers
130
views
Bent vectors and $\pm 1$ eigenvectors with respect to non-Sylvester Hadamard matrices
A Hadamard matrix is an $n\times n$-matrix $H$ where each entry in $H$ is $\pm 1$ and where $H/\sqrt{n}$ is orthogonal. It is well-known that if $H$ is an $n\times n$-Hadamard matrix, then $n<3$ or ...
2
votes
0
answers
78
views
Partitions of bent vectors
Let $H=\frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1 \\ 1 & -1\end{bmatrix}.$ Let $A^{\otimes N}$ denote the tensor product of the matrix $A$ with itself taken $N$ times. We say that a vector $v$ of ...
3
votes
1
answer
271
views
Why do we get a connected 2-regular graph?
In reading "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES" by Rostovtsev and Stolbunov, they claim on page 8 that the set $U=\{E_i(\mathbb{F}_p)\}$ of elliptic curves with a specific prime $l$ ...
- 33
10
votes
2
answers
633
views
Knot Diffie–Hellman
Here's an idea for a knot-based Diffie–Hellman exchange:
Public: random (oriented) knot $P$.
Private: random (oriented) knots $A$ and $B$.
Exchange: Alice sends (randomized or canonical ...
- 609
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
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
4
votes
1
answer
289
views
Is there a category theoretic definition of a cryptographic commitment scheme?
I'm trying to come up with a composeable framework for cryptographic commitment schemes, where inclusion proofs can be combined in different ways. I'm thinking this can be done with category theory, ...
- 153
5
votes
0
answers
110
views
Equidistribution of Hecke points and Steinitz classes
Let $K$ be a number field and $\mathcal{P}$ be a prime ideal of $K$. Let $k_{\mathcal{P}}$ be the residue field $\mathcal{O}_K/\mathcal{P}$.
Consider the following construction used very often in ...
- 885
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 ...
68
votes
8
answers
43k
views
Example of a good Zero Knowledge Proof
I am working on my zero knowledge proofs and I am looking for a good example of a real world proof of this type. An even better answer would be a Zero Knowledge Proof that shows the statement isn't ...
- 699
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\{...
- 13.9k
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 \...
- 591
1
vote
0
answers
133
views
Select random point on elliptic curve
If I have an elliptic curve $E$ over some finite field $F_p$ what is a step by step algorithm to pick a random point that lays on this curve? There is definitely a naive approach to brute force all ...
- 11
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
4
votes
0
answers
143
views
Road map for learning about the computational/general theory of modular curves/isogenies of abelian varieties for cryptography
I am a graduate math/crypto student. So I've had some free time last year and I heard about elliptic curves in cryptography and how a resilient cryptosystem got demolished by a spectacular attack ...
- 41
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 ...
- 11
2
votes
0
answers
116
views
Pollard's rho algorithm for ECDLP using supersingular elliptic curves over a field with characteristic equal to a Mersenne prime
I have been playing with Pollard's rho algorithm for elliptic curves over finite fields. I have noticed after some experimenting, that the algorithm almost always 'fails' for supersingular elliptic ...
- 121
2
votes
0
answers
50
views
Counting permutations of $X^2$ that induce 4 quasigroup operations up to isotopy
Let $X$ be a finite set. Recall that a binary operation $\ast$ on $X$ is said to be a quasigroup operation if there are binary operations $/,\backslash$ where $(x/y)\ast y=(x\ast y)/y=x$ and $x\ast(x\...
1
vote
2
answers
324
views
Distribution of "good" and "bad" basis in lattice families?
I'm trying to learn more about lattice based cryptosystems.
One of the fundamental ideas behind lattice based cryptosystems is that there can be many equivalent basis for a single lattice.
Formally, ...
- 61
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 ...
- 73
3
votes
0
answers
67
views
Efficiently finding solutions to the Rainbow cryptosystem using quotient spaces
Repost of a mathematics stackexchange question here as this concerns my research and it went unanswered on there.
In this paper, Ward Beullens gives another way to look at the Rainbow cryptosystem. In ...
- 173
1
vote
2
answers
278
views
Method to solve system of exponential sums of the form $a^x+b^x=c$ given more equations than variables [closed]
Cross post with mse
For example, let's say I have the following equations.
\begin{gather*}
a^{x-1}+b^{x-1}=337 \\
a^{x}+b^{x}=1267 \\
a^{x+1}+b^{x+1}=4825 \\
a^{x+2}+b^{x+2}=18751.
\end{gather*}
What ...
- 13
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
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
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
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 ...
- 111
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 ...
- 73
2
votes
0
answers
91
views
A variant of hidden subgroup problem (HSP)
I read some materials more general about HSP such as 1,2,3. I wonder that if it would be possible to have a faster quantum algorithm when our goal was just to find a non-trivial element of the hidden ...
- 253
1
vote
0
answers
56
views
Over a given finite field, how many couples of matrices there are, for which their minimal polynomials are co-prime?
Let ${\mathbb F}_{q}$ be a given finite field. How many couples of $n\times n$ matrices $\left(A,B\right)$ over ${\mathbb F}_{q}$, such that $\gcd\left(\mu_{A}\left(\lambda\right),\mu_{B}\left(\lambda\...
- 21
2
votes
1
answer
98
views
Proving that a function is a trapdoor function
I am working on a problem that involves an iterative application of a function I think might be a trapdoor function.
Formally, I have a function $f:X \to X$ that can be described as
$$
[x_{1,N+1}, ...,...
- 151
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
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(...
2
votes
0
answers
38
views
Criterion for unicity and existence of pre-image in multivariate cryptography
Repost from math.stackexchange since no one could help me there and it concerns my research.
I am reading Ding's Multivariate Public Key Cryptosystems and in the book the author explains the so-called ...
- 173
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
2
votes
2
answers
546
views
A p-adic logarithm as a limit of discrete logs
I've been searching for something similar to the argument below for about a week now and I just must be missing out on the right key words. Can someone point me in the right direction and/or let me ...
- 2,235
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
2
votes
0
answers
132
views
Solving efficiently a quadratic equation in a large finite field of characteristic two
I'm trying to solve efficiently a quadratic equation in the finite field $\text{GF}(2^{128})$ represented as $(\mathbb{Z}/2\mathbb{Z})[x] / (x^{128} + x^7 + x^2 + x + 1)$.
Until now, I came across ...
- 21
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
1
vote
0
answers
109
views
Why is the kernel cyclic if and only if the walk does not backtrack?
I'm reading Mathematics of Isogeny Based Cryptography by Luca De Feo. At some point (pg. 32), he says
"A walk of length $e_A$ in the $l_A$-isogeny graph corresponds to a kernel of size $l_A^{e_A};...
- 73
1
vote
0
answers
95
views
Reference request: Time and proofs of shared pasts
Is there research about structures for notions of time with distributed systems of information, as with blockchains?
I am thinking of tuples $(I, T, P, A, \prec, s, \eta, u)$ where
$I$, $T$ and $P$ ...
- 3,249
4
votes
0
answers
137
views
Lattice reduction of basis with non-integer coefficients
Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$.
I would like to perform lattice ...
- 554
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 ...
- 13.9k
0
votes
1
answer
123
views
Are there trapdoor functions breakable by moderate polynomial degree complexity algorithm?
Trapdoor function
is a function $f$ that is easy to compute in one direction,
yet difficult to compute in the opposite direction (finding its inverse)
$f^{-1}$ without special information, called the &...
- 25.4k