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).
217 questions
2 votes
1 answer
60 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
340 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
141 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
580 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
108 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
192 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
688 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
216 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 ...
- 273
2 votes
1 answer
138 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
104 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
229 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
348 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 ((...
- 6,003
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
143 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
129 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