All Questions
Tagged with cryptography nt.number-theory
69 questions
6
votes
5
answers
6k
views
Analog to the Chinese Remainder Theorem in groups other than Z_n.
The idea hit me when I was in my Elliptic Curve Cryptography class. $Z_n \leftrightarrow Z_{f_1} \times Z_{f_2} \times ...$ where $f_1 \times f_2 \times ... = n$ and $\{f_1, f_2, ...\}$ are pairwise ...
CommunityBot
- 1
1
vote
0
answers
459
views
Textbook on Cryptography [closed]
I am proposing (and will be teaching next year) a new math elective on Cryptography in our curriculum here at Illinois State University. In addition to standard topics including RSA public key and ...
- 575
4
votes
2
answers
501
views
Breaking the RSA encryption based on a $(e,N)$ given an integer $w \neq 0$ such that $e^w = 1 \mod(N)$?
In his book 'Forcing with Random Variables and Proof Complexity' Jan Krajíček claims (p.154) that it is possible to break the RSA encryption with public key $(e,N)$ if one has has an integer $w \neq ...
- 47.8k
1
vote
1
answer
799
views
Finding cyclic subgroups of points on elliptic curves for isogeny based cryptography
Isogeny based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is a theorem:
Elliptic curves ...
CommunityBot
- 1
2
votes
1
answer
258
views
Does this modification of the General Number Field Sieve factor integers?
The General Number Field Sieve
factors composite $n$ basically this way.
Select homogeneous polynomials with integer coefficients $f(x,y),g(x,y)$
s.t. $f(x,1),g(x,1)$ have common root modulo $n$ but ...
CommunityBot
- 1
3
votes
1
answer
382
views
Equivalence between Diffie Hellman and Discrete Log
For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?
Is there any group for which we suspect them to be different?
Could there be a finite ...
- 25.4k
3
votes
1
answer
164
views
Mestre-type algorithm for higher-genus curves?
Is there an analogous algorithm for genus $g>2$ curves that, given a complete set of invariants, outputs a curve with those invariants?
(I'm interested in particular in $g=3$.)
Any references ...
CommunityBot
- 1
9
votes
3
answers
576
views
"Most Similar Vector Problem" on an Integer Lattice?
I am currently working on problem that I think could be expressed as an integer lattice problem.
Given $u \in \mathbb{R}^n$ and a bounded integer lattice $L = \mathbb{Z}^n \cap [-M,M]^n$ I would like ...
- 131
23
votes
5
answers
1k
views
Securing privacy of "who communicates with whom" under Orwell-like conditions
Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...
2
votes
1
answer
162
views
DL-problem on abelian variety
Let $A$ be an abelian variety over $\mathbb{F_q}$ with dimension $n$. Let $q$ be a constant.
Is there polynomial algorithm of finding discrete logarithm in $A$?
UPD: really I don't undestend: can we ...
- 30.5k
0
votes
1
answer
748
views
Pairing on elliptic curve
Let $E(\mathbb{F_q})$ - elliptic curve.
$G_1 = E(\mathbb{F_q})[r]$. $|G_1| = r$.
$k$ is minimal such $r | q^k - 1$.
$\pi_q$ - $q$-power Frobenius endomorphism.
$G_2 = E(\mathbb{F_{q^k}})[r] \cap ...
CommunityBot
- 1
1
vote
0
answers
343
views
Diophantine approximation
Say absolute values of $a,b,c$ is $O(log^{k}{n})$ for some positive constant $k$.
Given positive integer $n$ that is reasonably large, we cannot always find integers $a,b,c$ such that $|a{b^{c}} - n|$ ...
- 188k
2
votes
3
answers
398
views
Generating a set of integer passwords that can be securely authenticated
First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.
My question is as follows.
Given a positive integer $k$, determine a set of properties $S$ ...
- 1
4
votes
0
answers
214
views
factorising an integer with certain bound on the factors
Can we count the no. of $x$ where $ p^{\alpha -1} < x < p^{\alpha}$ , $gcd(x, 2p)=1$ and if $d |x$ and $d < p ^{\beta}$ for some $1< \beta<\alpha-1$ then $ \frac {x} {d} > p^{\alpha -...
- 39.9k
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
...
1
vote
1
answer
288
views
Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without "being able to know" one of the discrete logs involved (formal definition given in question)?
Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, ...
CommunityBot
- 1
2
votes
0
answers
688
views
Elliptic Curves and cryptography. Recommended Reading [closed]
I have been studying RSA cryptography and want to extend this to ECC. I am interested in any books on the topic, that start off with basic principles of elliptic curves as I have almost zero knowledge ...
CommunityBot
- 1
26
votes
4
answers
6k
views
Discrete logs vs. factoring
One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction ...
0
votes
0
answers
562
views
Reducing two variable linear Diophantine equation to modular inversion
I'm in the field of secure multiparty computation using Homomrphic encryption or secret sharing. I want to implement a secure protocol to compute the GCD of two encrypted numbers.
To calculate the ...
- 193