12
votes
Cryptography based on uncomputable problems?
It is impossible to build a cryptographic algorithm using uncomputable problems because you cannot compute them. It would be impossible to execute the encryption. In order to use a problem for ...
- 121
11
votes
Accepted
Cryptography based on uncomputable problems?
Encryption, signatures, etc., can always be broken in NP.
You can break any encryption scheme if you can solve the following decision problem: "does there exist a secret key and encryption ...
- 12k
3
votes
Can we find pairs $(c,m)$ with $f(c)=f(m)=true$ in $c = AES(m,K)$ with a fixed known Key $K$ significantly faster than brute force?
OK, you have asked a lot of questions in this vein, and they've mostly been answered, sometimes in great detail.
This is really not much different than the rest. You do seem to understand the idea of ...
- 21.2k
3
votes
Average- and worst-case complexity
It might be worth actually answering your questions
What do they mean when they say certain problems (like lattices) have an average-case to worst-case relationship? Do they mean there is a ...
- 11.6k
2
votes
Average- and worst-case complexity
Forget about cryptography and anything to do with secrets. Let's talk about sorting, a classic problem where we compare the efficiency between algorithms.
A problem is a specification of how each ...
- 232
2
votes
Average- and worst-case complexity
The most questions are answered by the link in the comment of @EugeneStyer. But one question is not addressed well there.
why don't we consider best-case or simplest-case? Why there is no attention ...
- 2,581
2
votes
Accepted
Circuits for general computing
A loop can be transformed into a circuit. The circuit might be bigger, but any polynomial-time program you can think of can be converted into a polynomial-size boolean circuit. Garbled circuits ...
- 19.1k
2
votes
Asymptotic efficiency of modular multiplication
This seems to be the case for generic moduli $n$ and generic exponents. See the preprint of a chapter entitled "Efficient Modular Multiplication" (available here) from the book Computational ...
- 21.2k
2
votes
Accepted
A problem related to two bitwise sums of rotations of two different bitstrings
There's a very easy way to find a solution with $t=u=v=0$ and $w=1$ say. First note that the parity of the Hamming weights of $B_1$ and $B_2$ are the same and hence the Hamming weight of $B_1\oplus ...
- 21.9k
2
votes
Can we find pairs $(c,m)$ with $f(c)=f(m)=true$ in $c = AES(m,K)$ with a fixed known Key $K$ significantly faster than brute force?
It is easy to see that for some $f$, such solutions will be easy to find. Indeed, denote the message space for AES with $\mathcal{P}$ and AES encryption under the fixed key $K$ with $E_K$ and assume ...
- 554
1
vote
How to prove that an algorithm is the time optimal algorithm for implementing a problem?
Since you stated interest in how to prove an algorithm is time-optimal, a telescopic summary:
This requires proving lower bounds on complexity, which is very difficult in general. I will use "...
- 21.2k
1
vote
Cryptography based on uncomputable problems?
It is certainly conceivable. The big issue is, most undecidable problems are of the form "create an algorithm which, for all possible inputs ...". Many of these problems are easy to solve ...
- 51
1
vote
State recovery algorithm for Xorshift128 given modular outputs
This is a hard problem. Your solution is clever and possibly the best option. You may have to bite the bullet and use quite a lot of memory (although sorted data structures + SSD might work)
Here's ...
- 1,701
1
vote
Average- and worst-case complexity
For decryption, there is another important measure: What percentage of messages can be decrypted in some fixed time?
We don’t actually care about the cost of decryption, but whether we can do it with ...
- 1,108
1
vote
How does the security of AES change if we allow multiple uses in a row? How does it change if we limit the key space? And introduce a filter function?
If you want to prevent meet-in-the-middle attacks, the most straight-forward approach would to make the 'forward' direction noninvertable, such as:
$$f_{n+1} = AES( f_n, k_n ) \oplus f_n$$
From what I ...
- 145k
1
vote
Circuits for general computing
We have to think about the cost of realizing a specific kind of circuit complexity.
We can say that a general program executing some kind of interactive command can't be converted in a feasible ...
- 628
Only top scored, non community-wiki answers of a minimum length are eligible