All Questions
Tagged with cryptography reference-request
16 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
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
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
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
3
votes
0
answers
151
views
determine degree of boolean polynomial given as black box
I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
- 103
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
0
votes
1
answer
643
views
A good approximation for collision probability between (two) sets of random variables
We face many places to find the collision probability of two sets (or more) in my case the cryptographic hash functions. We can formalize as;
Given two sets of random variables $\mathbf{A}$ and $\...
- 115
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
1
vote
0
answers
212
views
Generate algorithmically an elliptic curve with its exact class group structure?
Is it possible to generate an elliptic curve $E$ (randomly), together with knowing its class group $\mathrm{Cl}(\mathcal{O})$ structure? where $\mathcal{O}$ is its endomorphism rings $\mathsf{End}(E)$ ...
- 181
3
votes
1
answer
137
views
Subexponential algorithms that apply only one of factoring and discrete logarithm?
Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants.
What are the subexponential ...
- 13.9k
4
votes
1
answer
288
views
Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?
The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...
- 13.9k
6
votes
1
answer
441
views
Minimum number of operations necessary to arrive at any configuration
Let $k \geq 2$ and $N_1, N_2, ..., N_k$ be positive integers.
Let $S=\{(a_1,a_2,...,a_k) \in \mathbb{Z}^k:1 \leq a_i \leq N_i\}$ and $A=\{1,2,...,\prod_{i=1}^{k} N_{i}\}$.
Given a bijective map $f:...
- 3,153
5
votes
0
answers
317
views
Elliptic curve sequences needed for universal forgery
Elliptic Curve Digital Signature Algorithm (ECDSA) admits universal forgery (UF) if the Attacker can solve the equation
$$z=\frac{f_{k-1}(x,y)f_{k+1}(x,y)}{f_{k}(x,y)^2},$$
where $k$ is unknown, $f_{k}...
- 12.3k
2
votes
1
answer
204
views
Is there a security analysis of the GQ digital signature scheme?
I'm doing summer cryptography research and I am have been looking for a security analysis of the Guillou-Quisquater (GQ) digital signature scheme, but I have been unable to find one.
Since this is not ...
- 1,441
3
votes
3
answers
337
views
Cryptography and iterations
Hi,
Here is a question in cryptography which is probably naive, and a reference request.
I was wondering about the following key-exchange scheme, which is a variant on Diffie-Hellman. Consider a ...
- 2,287