# Tag Info

### 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 ...
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 ...

### 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 ...

### 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 ...

### 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 ...

### 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 ...
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 ...

### 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 ...
Accepted

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 "...
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 ...
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 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 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 ...
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 ...

Only top scored, non community-wiki answers of a minimum length are eligible