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 ...
- 27.6k
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 ...
- 11.6k
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 ...
- 608
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 ...
- 47.6k
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 ...
- 27.6k
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, ...
- 11.6k
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 ...
- 45.9k
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$ ...
- 27.6k
7
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 ...
- 11.6k
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 ...
- 145k
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 ...
- 19.1k
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 ...
- 11.6k
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 ...
- 159
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 (...
- 63
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 ...
- 27.6k
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 ...
- 145k
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 ...
- 11.6k
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 ...
- 11.6k
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-...
- 19.1k
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 ...
- 145k
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 ...
- 11.6k
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 ...
- 327
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, ...
- 91.8k
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. ...
- 97
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 $...
- 261
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 ...
- 21.9k
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 ...
- 11.6k
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 ...
- 11.7k
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 ...
- 19.1k
Only top scored, non community-wiki answers of a minimum length are eligible