# 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 ...
• 27.6k

### 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 ...
• 11.6k

### 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 ...
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 ...
• 47.6k
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 ...
• 27.6k
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, ...
• 11.6k

### 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 ...
• 45.9k
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$ ...
• 27.6k
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 ...
• 11.6k
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 ...
• 145k
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 ...
• 19.1k

### 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 ...
• 11.6k

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

### LWE and pseudorandom functions

This is my understanding so far, please correct if applicable. We can construct PRF from any one-way function. Inefficient and require deep circuits. We can construct PRF from LWR assumption (...
• 63
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 ...
• 27.6k
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 ...
• 145k
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 ...
• 11.6k
Accepted

### Questions regarding the pseudorandom function construction of Banerjee, Peikert, and Rosen

First, there has been followup work to BPR, including a practical PRF and PRG. Here "practical" means extremely fast --- ~5 cycles per byte, (and as small as ~3 for the PRG iirc). This is ...
• 11.6k
Accepted

### Assumptions on zero-knowledge proofs without trusted setup

Strongly unforgeable digital signatures exist from one-way function, so they are indeed a Minicrypt assumption, even though most efficient construction use public key cryptography. For succinct zero-...
• 19.1k

### Let $X$ be the set of 256-bit strings and $x \rightarrow H(x)$ a map on this set, where $H$ is SHA-256. How often is $H^-1(y)$ empty?

If we model SHA-256 as a random function, then we would expect $H^{-1}(x)$ to be empty with probability about $e^{-1} = 0.36787944.$. To put it another way, we would expect that about $2^{256}/e$ of ...
• 145k
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 ...
• 11.6k
Accepted

### How to construct a circuit in zkSNARK

is there any specific definition or feature for the problem, and could all problems, which can be verified, be converted into circuits and use zk-snark to generate proofs? Problem should be in NP ...
• 327
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, ...
• 91.8k

### Complexity of Gaussian Elimination over a Finite Field

The classic Gaussian Elimination algorithm is $O(n^3)$ runtime regardless of specific field and the Matrix, so in this case a finite field $F_q$ of order $q$ doesn't play a role in the complexity. ...

• 11.6k
Accepted

### Private key encryption based on NP-complete problem

We do not have such an encryption. One of the challenges is the gap between worst case and average case. When we build an encryption based on a well known problem it is not sufficient to reduce the ...
• 11.7k