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).
13 questions from the last 365 days
-1
votes
0
answers
73
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
0
votes
0
answers
138
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
+50
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
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
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
0
votes
0
answers
122
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
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 ...
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 ...
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
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
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
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