Skip to main content
21 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 ...
Yehuda Lindell's user avatar
16 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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
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 ...
Gordon Davisson's user avatar
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 ...
kelalaka's user avatar
  • 49k
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 ...
Yehuda Lindell's 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, ...
Mark Schultz-Wu's user avatar
  • 13.5k
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 ...
Ilmari Karonen's user avatar
8 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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
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$ ...
Yehuda Lindell's 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 ...
poncho's user avatar
  • 148k
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 ...
Geoffroy Couteau's 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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
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 ...
Quuxplusone's user avatar
4 votes

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 (...
DP2040's user avatar
  • 73
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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
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 ...
poncho's user avatar
  • 148k
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 ...
Yehuda Lindell's user avatar
4 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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
4 votes
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-...
Geoffroy Couteau's user avatar
4 votes

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 ...
poncho's user avatar
  • 148k
3 votes
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 ...
Hypatia's user avatar
  • 365
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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
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. ...
Curious Cat's user avatar
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, ...
Maarten Bodewes's user avatar
  • 93.2k
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 $...
Anonymous20DB28's user avatar
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 ...
Daniel S's user avatar
  • 24.1k
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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
3 votes
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 ...
Meir Maor's user avatar
  • 11.8k
3 votes

Is there a notion of information theoretic one-way function?

There are multiple notions of one-way functions which do provide information-theoretic security guarantees. I will cover three things that come to mind, but there are others. (1) The first example ...
Geoffroy Couteau's user avatar
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 ...
Mark Schultz-Wu's user avatar
  • 13.5k

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