2022 Developer Survey is open! Take survey.
22 votes

(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 ...
user avatar
15 votes

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 ...
user avatar
14 votes

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 ...
user avatar
  • 8,424
14 votes
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, ...
user avatar
  • 131k
13 votes
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 ...
user avatar
  • 43.1k
11 votes
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 ...
user avatar
10 votes
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, ...
user avatar
  • 8,424
9 votes

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 ...
user avatar
8 votes
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$ ...
user avatar
7 votes
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 ...
user avatar
  • 131k
6 votes
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 ...
user avatar
5 votes

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 ...
user avatar
  • 8,424
4 votes

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) ...
user avatar
  • 2,051
4 votes

(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 ...
user avatar
4 votes
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 ...
user avatar
  • 131k
4 votes
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 ...
user avatar
4 votes
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 ...
user avatar
  • 8,424
4 votes
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 ...
user avatar
  • 8,424
3 votes
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 ...
user avatar
  • 8,424
3 votes
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, ...
user avatar
  • 84.7k
3 votes

Computational Complexity Of Breaking Information Theoretic Security

To me the key mental image with information theoretic security is that given a ciphertext ($c$), for any possible plaintext ($p$) there will be a key ($k$) to decrypt the ciphertext to it. So given a $...
user avatar
3 votes
Accepted

Reductionist proofs of computational problems to decisional

A classic example of this sort of thing would be the Goldreich-Levin hard-core bit for an arbitrary one-way function. The proof of security for the Goldreich-Levin construction involves showing that ...
user avatar
  • 35.3k
3 votes

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. ...
user avatar
3 votes
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 ...
user avatar
  • 8,424
3 votes
Accepted

What exactly does "Extension of a polynomial" mean?

The distinction here is that $g$ maps from $\mathbb F^v\to \mathbb F$. The Boolean values 0 and 1 can be naturally identified with the additive and multiplicative identities in any field to make the ...
user avatar
  • 9,816
3 votes
Accepted

What does it mean for public keys to be in coNP

NP is the set of decision problems that are efficiently verifiable. Given an instance $x$ of the decision problem, there is a short "proof" $w$ that, given the pair $(x, w)$, one can ...
user avatar
  • 8,424
2 votes
Accepted

Yao's theorem for the uniform case

At the end of Section 2 of the lecture notes that you cite, it explicitly states "We note that an analogue of this result holds for uniform distinguishers and predictors, provided that we change ...
user avatar
2 votes

Computational Complexity Of Breaking Information Theoretic Security

Information-theoretic security means that knowing the ciphertext doesn't help you find the plaintext. Knowing all $b$ bits of a single Shamir share tells you as much about the secret as knowing $0$ of ...
user avatar
  • 471
2 votes

what's the reason of the notational difference between statistical and computational indistinguishabilities?

You can define statistical security directly in terms of the statistical properties of different distributions. For example, you could define two distributions to be statistically close if their ...
user avatar
  • 3,707

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