Questions tagged [computational-complexity-theory]
A subfield of theoretical computer science one of whose primary goals is to classify and compare the practical difficulty of solving problems about finite combinatorial objects
74 questions
0
votes
1
answer
90
views
Is Diffie-Hellman in $\mathsf{NP}\cap\mathsf{coNP}$ without discrete log witness?
Given prime $p$, generator $g$ of $\mathbb Z_p^*$ and $h_1,h_2,h_3\in\mathbb Z_p^*$ is $$\log_ph_3=(\log_ph_1)(\log_ph_2)$$ where at every $i\in\{1,2,3\}\mbox{ }g^{\log_ph_i}\equiv h_i\bmod p$ holds?
...
- 1,199
1
vote
0
answers
112
views
NP-hardness of ECDLP
Qi Cheng proved that the minimum distance for elliptic linear codes (AG codes for genus 1 curves) is NP-hard (see https://arxiv.org/abs/cs/0507026).
Any instance of ECDLP for an elliptic curve $E/\...
- 261
3
votes
1
answer
184
views
Is LWE even an NP language?
I can define LWE with $m$ samples, $n$ dimensions of secret, modulus $q$, secret distribution $\chi_s$ and error distribution $\chi_e$. The LWE problem asks: given a uniformly random matrix $A$ and $b=...
- 1,920
1
vote
0
answers
82
views
What’s the complexity of solving the ᴇᴄᴅʟᴘ using this minors based las vegas algorithm?
I was reading this paper. The almost principal minor (apm) case sounds to yield a subexponential algorithm for solving the ecdlp both in number of matrice rows and kernel count, yet they talk about ...
- 283
0
votes
1
answer
77
views
Why is the original Adleman’s index calculus complexity constant relative to the size modulus's size instead of the size of multiplicative subgroups?
According to the original paper by Adleman the complexity is stated to be $e^\sqrt{log_eq×log_elog_eq}$, but since the algorithm operates in a similar fashion than the Pohlig Hellman (on each prime ...
- 283
0
votes
1
answer
95
views
Does the ability to solve modular square roots without factorization would allow factorizing semiprime in a more efficent way than using the gnfs?
The gnfs is a fast sieving method for factorizing integers, but as soon as the integer to factor is more than 900 bits long factoring tends to become too costly.
I just read having a modular square ...
- 283
2
votes
1
answer
2k
views
Does the paper “A Heuristic Proof of P ≠ NP” actually prove that P ≠ NP?
I saw a paper on eprint that says 'A Heuristic Proof of P ≠ NP', does this mean that P ≠ NP has been proven? The URL of the paper is: https://eprint.iacr.org/2024/2035.
- 137
2
votes
1
answer
74
views
About [PS19]'s Claim of Decryption of LWE is in $\mathsf{NC}_1$
In the paper of Peikert and Shiesian [PS19], they have the following remark (I lined the part I am confused in red below):
However, I am not convinced that decrypting LWE-based encryption is in $\...
- 61
1
vote
0
answers
139
views
Probabilistic Turing Machine and Cryptography
Lecture notes I am reading says:
An issue with characterizing efficiency in terms of P is that the
feasibility of a problem is thus considered in terms of its worst-case
complexity only. For ...
- 11
2
votes
1
answer
214
views
probabilistic polynomial-time Turing machine with one-way function
Suppose that there exists a function $𝑓:\{0,1\}^𝑛 → \{0,1\}^𝑛$
such that, 𝑓 is computable in polynomial time; and the following task cannot be computed in polynomial time (that is, there are $𝑥 ∈ ...
- 45
3
votes
3
answers
1k
views
How can we know how good a TRNG is?
Imagine that a perfect TRNG generates 100 bits, which are then fed into a high quality PRNG such as ChaCha20, which generates 1000 bits.
How many bits of entropy is in the 1000 bits? Depends on who is ...
- 163
1
vote
1
answer
122
views
Why doesn't the existence of the Quadratic Sieve algorithm imply that integer factorization is in the class SUBEXP?
SUBEXP is defined as the intersection of DTIME(2^n^c) over all c>0. The order of the Quadratic Sieve algorithm is O(exp((k+o(1))(logN)^1/2(loglogN)^1/2)). Doesn't this imply that the decision ...
- 13
0
votes
3
answers
123
views
Is it possible to construct a (pseudo-)continuous PRF or MAC?
Is it possible to construct an efficient-to-compute function $F: X \rightarrow Y$ such that
Given samples $(x_1, F(x_1))...(x_n, F(x_n))$, any efficient adversary ($F$ itself is kept secret) can't ...
- 41
0
votes
0
answers
102
views
Key-dependent cipher generation
Is there any cryptanalysis possible if the cipher itself is deterministically derived from key material?
For example, suppose you have n building blocks (ARX primitives, AES ops, other primitives) and ...
user113099
1
vote
3
answers
710
views
(Complexity Theory) Given a large non-semiprime, is there a hard to compute but easy to verify problem?
Let's say I had an arbitrary number that was large, say 512 bits or bigger, but wasn't necessarily a semiprime. What is a computation that I could do on this number that would give me a unique ...
