Questions tagged [cryptography]
Questions concerning the mathematics of secure communication. Relevant topics include elliptic curve cryptography, secure key exchanges, and public-key cryptography (e.g. the RSA cryptosystem).
218 questions
2 votes
1 answer
54 views
Recovery of $\phi(N)$ from "threshold" Paillier encryption key ($\phi(N)(\phi(N)^{-1} \mod N)$)
I am implementing threshold Paillier encryption scheme. In the "regular" Paillier scheme, the decryption key is defined as $d = \phi(N)$ whereas in the instantiation of threshold Paillier I ...
- 21
4 votes
1 answer
311 views
Motivation for Jacobian coordinates (elliptic curves)
In cryptography, it seems to be a common choice to use the so-called Jacobian coordinates to represent a point of an elliptic curve (see e.g. Elliptic Curves: Number Theory and Cryptography, L. C. ...
- 371
2 votes
1 answer
140 views
Existence of an "optimal" short free family in an euclidean lattice
We define the successive minima in a lattice $L$ of rank $n$ as in Daniele Micciancio and Shafi Goldwasser, Complexity of lattice problems. A cryptographic perspective, The Kluwer International Series ...
- 41
2 votes
0 answers
552 views
How to find a suitable Input point for Satoh’s Miller’s inversion algorithms when subfield point compression is used with bn curves?
First, remember bn curves is a class of elliptic curves defined over curve $y^2=x^3+3$ with embedding degree 12 and $\mathbb G_2$ points lying over the curve twist $\frac {Y^2 = X^3 + 3}{i+9}$ defined ...
- 67
1 vote
0 answers
107 views
How to find a root of unity satsifying the following equation for tate/ate pairing inversion?
The aim is for pairing inversion where miller inversion can only work if an equation is satisfied. So given a finite field modulus $q$ having degree $k$ ; and a finite field element $z$ having ...
- 67
2 votes
0 answers
189 views
Are there smarter ways to lift the Finite Field ᴅʟᴘ to the ecdlp than using pairing inversion?
Let it be a finite field $FF$ with 2 finite field elements having their discrete logarithm in a large prime subgroup $s$ of $FF$… Will the only way to map the discrete logarithm of $FF$ always be to ...
- 67
-3 votes
2 answers
679 views
Primality test using the Golden Ratio [closed]
Background and Motivation The golden ratio, $$ \phi = \frac{1 + \sqrt{5}}{2}, $$ is a well-known irrational constant that appears frequently in geometry, algebra, and in the Fibonacci and Lucas ...
- 559
1 vote
0 answers
212 views
Reduce linear code minimum distance to lattice closest vector (CVP)
There are many NP-complete problems, e.g. SAT, CVP, SIS, graph colouring, Minesweeper etc. By definition there are polynomial time reductions from one to another of these, at least in their decision ...
- 263
2 votes
1 answer
130 views
Lattice reduction in 3-dimensions with real basis vectors
There are several algorithms for lattice reductions in $n$-dimensions, LLL, etc. Here the lattice in question is in ${\mathbb R}^n$ and the basis vectors $b_1, \ldots, b_n$ are usually assumed to be ...
- 1,426
1 vote
1 answer
102 views
Can the CVP -> OptCVP reduction be extended to lattices with real basis?
In Theorem 8 of Micciancio’s lecture notes, a reduction from the Closest Vector Problem (CVP) to its optimization version (OptCVP) is given under the assumption that the lattice basis $B \in \mathbb{Z}...
- 21
1 vote
1 answer
224 views
On deterministic point halving related to discrete logarithm
We got some unexpected to us results. Let $E$ be an elliptic curve over a finite field of large characteristic. For positive integer $k$, let $D=2^k$ and assume the order of $E$ is $\rho=D t$ with $t$ ...
- 25.7k
3 votes
1 answer
347 views
Explicit formulas of cardinal on an elliptic curve
During my research, I came across this question. Let $p>11$ a prime number with $a=\text{card}\{(x,y) \in \mathbb Z/ p \mathbb Z: y^2=x^3+1\}$ and $b=\dfrac 1 {((p-1)/2)! \times ((p-1)/3)! \times ((...
- 5,881
1 vote
0 answers
109 views
Is the NH hash family $\varepsilon$-AXU?
As context, I'll start with summarizing and simplifying the section of "UMAC: Fast and Secure Message Authentication", by Black et al.(https://www.cs.ucdavis.edu/~rogaway/papers/umac-full....
- 111
3 votes
0 answers
140 views
How fast can we solve SVP using an SVP$_{\gamma}$ subroutine?
An $n$ dimensional lattice is the set of integer linear combinations of $n$ linearly independent vectors in $\mathbb{R}^{d}$ ($d\le n$). The $n$ independent vectors are called the basis of the lattice,...
- 169
2 votes
0 answers
127 views
Discrete Fourier Transform using not the n-th roots of unity, but the 2n-th primitive roots of unity
I should start with stating that my question stems from the proof of lemma 6 in the following paper: Jung Hee Cheon, Hyeongmin Choe, Julien Devevey, Tim Güneysu, Dongyeon Hong, Markus Krausz, Georg ...
- 21
2 votes
0 answers
151 views
Is it possible to transform a univariate congruence equation into a multivariable system of congruence equations for solving?
Considering a quadratic congruence equation $$ x^2 = d \pmod{p} \label{1}\tag{1} $$ I have a strange idea: what if we construct a system of congruence equations in multiple variables based on the ...
- 109
1 vote
0 answers
226 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 ...
- 129
2 votes
0 answers
162 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}−...
- 129
3 votes
0 answers
109 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 ...
- 129
1 vote
1 answer
248 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
243 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 ...
- 129
6 votes
0 answers
158 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
99 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
98 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 ...
- 1
3 votes
1 answer
324 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
4 votes
0 answers
125 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 ...
- 183
5 votes
0 answers
146 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
1 vote
0 answers
194 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
4 votes
1 answer
330 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
2 votes
0 answers
162 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
4 votes
0 answers
229 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
0 votes
0 answers
132 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\{...
- 1
2 votes
0 answers
214 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(...
- 1
4 votes
0 answers
206 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
119 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
67 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\...
2 votes
0 answers
61 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
3 votes
0 answers
89 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
0 answers
117 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.7k
2 votes
0 answers
111 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.7k
2 votes
0 answers
116 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.7k
1 vote
0 answers
101 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
1 vote
2 answers
458 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, ...
- 211
2 votes
0 answers
125 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
1 answer
262 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
4 votes
1 answer
472 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
11 votes
2 answers
780 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 ...
- 639
1 vote
0 answers
163 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
2 votes
0 answers
143 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.7k