2022 Developer Survey is open! Take survey.

# Tag Info

### (updated) Utilizing a non-computable function to create a one-way function

The main fundamental issue with this approach, as with approaches that attempt to base cryptography on NP-completeness, is that the hardness you refer to is worst case hardness, and not average case ...
• 26.9k

### Computational Complexity Of Breaking Information Theoretic Security

Here's an simpler but analogous problem that may illustrate what's going on: Given that $X=Y+Z$ and $Y=5$, compute $X$. The problem isn't that the answer is difficult to compute, the problem is that ...

### Meaning of "Security can be reduced to a problem"

You are (mostly) right. Reductions are an algorithmic notion — $P$ reduces to $Q$ if the ability to solve $Q$ allows you to solve $P$. There are many ways to formalize this, but the one that you ...
• 8,424
Accepted

### Are post-quantum cryptographic ciphers *also* secure if the P=NP conjecture holds true?

Do the post-quantum ciphers also automag/tically address the 1st problem? Not really, however to explore that in any detail, we need to explore what the 1st problem is. If $P=NP$ is proven true, ...
• 131k
Accepted

### Computational Complexity Of Breaking Information Theoretic Security

This is about the Theory of Computability not the Theory of Complexity. The halting problem is a decision problem in CS. From Wikipedia's introduction; In computability theory, the halting problem is ...
• 43.1k
Accepted

### Why Zero-Knowledge protocols are used for NP problems if IP is the class of interactive proof systems where they come from?

The reason is that essentially, the class of languages in $\mathcal IP$ that are not in $\mathcal NP$ cannot be proven with an efficient prover. Since we are typically interested in the cryptographic ...
• 26.9k
Accepted

### Notion of elementary operation when complexities in the form of $2^{128}$

For other algorithms, the big-O notation usually hides the constant factors, making the exact elementary operation an unimportant detail. But the cryptographic papers state the complexities exact, ...
• 8,424

### Computational Complexity Of Breaking Information Theoretic Security

As others have noted, information-theoretic security really has no connection to computational complexity. Yes, with sufficient computing power, you could enumerate all the solutions (including the ...
• 44.3k
Accepted

### Is Indistinguishability Obfuscation Real?

First, the wikipedia article stated that the assumption required a PRG with an exponential stretch. This is not correct, and I have edited the article. Rather, the requirement is for a PRG in $NC_0$ ...
• 26.9k
Accepted

### RSA decryption using CRT: How does it affect the complexity?

There is an efficient variant of the RSA using the CRT Actually, by the way we generally use terms, it is not a 'variant', instead it is an alternative implementation. That is, the only changes made ...
• 131k
Accepted

### Has anyone implemented a public-key encryption scheme using a universal one-way function?

We don't know of any construction of PKE based on a universal OWF. Actually, we do not even have any plausible candidate PKE that would be based on an arbitrary OWF. Obtaining such constructions is a ...
• 16.6k

### How to ethically publish the result in case we prove that $P = NP$?

I'll try to answer what I view to be a much easier question to answer, while still (in my view) capturing the "essence" of the problem. How can one "prove" that they have an ...
• 8,424

### Reductionist proofs of computational problems to decisional

Such reductions I know are the reductions in hardcore predicates/functions from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, the reductions in (provably-secure) ...
• 2,051

### (updated) Utilizing a non-computable function to create a one-way function

take the data you want to hide and use it to seed some large but manageable number of Turing Machines with random rulesets. You let them run for up to 𝑡 steps, and then see which ones have halted by ...
• 159
Accepted

### Why the differential cryptanalysis complexity is linear with inverse of the probability while linear cryptanalysis is quadratic with the bias inverse?

What I don’t get is why the complexity became quadratic in linear case? Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that ...
• 131k
Accepted

### A question regarding next-bit predictors

[SEE UPDATE BELOW] This is a very interesting question. Basically what it means is that if there exists a next-bit predictor, then there is a canonical distinguisher $D$ that outputs the $k$th bit and ...
• 26.9k
Accepted

### Consequences of P=NP for Authentication

I'll try to answer what I believe to be what you are asking, namely: If $P = NP$, can one "fix" cryptography by replacing constructions with interactive protocols? This is a natural enough ...
• 8,424
Accepted

### LWE and pseudorandom functions

You can. There is a certain caveat that should be mentioned here --- the LWE problems hardness is controlled (in part) by the size of the modulus $q$. Two important parameter regimes are $q$ being ...
• 8,424
Accepted

### How expensive would running a practical application on full homomorphic encryption be?

This will likely be rather expensive. This is because the problem you describe seems like it would be hard to express as a shallow arithmetic circuit, which is a rough estimate of how difficult the ...
• 8,424
Accepted

### How to estimate the maximum computational cost bound for Key Derivation Functions (KDFs) before it becomes useless security-wise?

Generally we look at strength by looking at the order $O$ that it adds to the password search when an attacker is trying to guess passwords. That's just the same as the number of iterations basically, ...
• 84.7k