18
votes
Accepted
Password hashing using NP complete problems
Unfortunately, this doesn't seem to work (see below for details), and it seems hard to find a way to make this kind of idea yield a provably secure scheme.
The problem with your general idea
You're ...
- 11.7k
11
votes
PPAD and Quantum
Two answers that I learnt while writing a blog post about this question
No: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. ...
- 111
9
votes
Accepted
State of research on SHA-1 Collision Attacks
SHA-1 was SHattered by Stevens et al. They demonstrated that collisions in SHA-1 are practical. They give the first instance of a collision for SHA-1.
It is an identical-prefix collision attack that ...
- 206
9
votes
Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?
There are essentially only two algorithms that I'm aware of:
Use repeated-squaring, along the lines you mentioned.
Factor $n$ using a state-of-the-art algorithm, then use the Chinese remainder ...
- 11.7k
9
votes
PPAD and Quantum
I will attempt to elaborate a bit on why CHKPRR shows that $\mathsf{PPAD}$ is plausibly hard for quantum computers.
At a high level, CHKPRR builds a distribution over end-of-line instances where ...
- 818
8
votes
Is it possible to encrypt a CNF?
The application you mention is called "proof of useful work" in the literature, see for instance this article.
You can use a fully homomorphic encryption scheme (where the plaintext is the CNF ...
- 1,551
8
votes
Accepted
Can any computational challenge be transformed to proof-of-work?
(Note: Andreas Björklund suggested a solution in the comments that I believe is better than the one described below. See http://eprint.iacr.org/2017/203, by Ball, Rosen, Sabin, and Vasudevan. In ...
- 1,204
8
votes
Accepted
Learning with (Signed) Errors
(wow! after three years of time passing, this is now easy to answer. funny how that goes! --Daniel)
This "Learning with (Signed) Errors" (LWSE) problem, as invented-and-stated above by me (three ...
- 5,961
8
votes
Knot Recognition as a Proof of Work
If there is an Arthur-Merlin protocol for knottedness similar to the [GMW85] and [GS86] Arthur-Merlin protocols for Graph Non Isomorphism, then I believe such a cryptocurrency proof-of-work could be ...
- 1,063
7
votes
Accepted
Quantum Hardness of Approximating Lattice Problems
The answer to your question is the same as with many other such assumptions in cryptography: despite a lot of effort no one has found any substantially faster quantum algorithms for lattice problems. ...
- 4,788
7
votes
Accepted
Is it possible to encrypt quantum states under reasonable assumptions?
One can encrypt an n-qubit state using a 2n-bit classical secret key. The idea is to use the key to select a random Pauli operator, and apply that operator to the secret as an encryption. (The inverse ...
- 878
6
votes
Accepted
Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise
Here is the problem: if $M$ has low entropy (for example, if the attacker has side information that narrows $M$ down to just two possible messages), then conditioned on $M+K$, the key $K$ also has low ...
- 878
6
votes
Accepted
Why is the security of lattice cryptosystems not provable from $P \neq NP$?
To expand somewhat on Sasho Nikolov's comment...
LWE is at least as hard as finding approximate solutions to SVP, but the approximation factors for which the reduction from SVP to LWE works are ...
- 5,961
6
votes
Accepted
Is it possible to encrypt a CNF?
Feigenbaum in, Encrypting Problem Instances, proposes a definition (Def. 1) of encryption function for NP-complete problems which satisfies your requirements. She proves that the NP-complete problem ...
- 20.8k
6
votes
Accepted
Is a "complete" cipher possible?
Yes, you can use Levin universal search to construct a "universal one-way function" (e.g., these lecture notes). From this one-way function you can then construct symmetric-key encryption primitives (...
- 2,799
6
votes
What is the state of the art in online voting?
This question is probably too broad to be answerable here, because the answer depends on what kinds of security requirements you have, what the threat model is, and what assumptions we're willing to ...
- 11.7k
5
votes
Accepted
Is it possible to MAC a quantum state with a classical key under reasonable assumption?
Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, Alain Tapp. "Authentication of Quantum Messages", FOCS 2002.
http://www.cse.psu.edu/~ads22/pubs/PS-CSAIL/BCGST02-focs-final.pdf
As with ...
- 878
5
votes
Is a theoretically secure key exchange possible?
I believe you are talking about the existence of information-theoretically (unconditionally) secure key agreement schemes. You can prove that such schemes cannot be achieved with only authenticated ...
- 51
5
votes
Accepted
If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'
There are 4 possibilities, name them e1-e4:
e1 neither match
e2 a only matches
e3 b only matches
e4 both match
Now I restate what you want to prove: Suppose:
...
- 7,595
5
votes
Accepted
Q: Trusting program output from an untrusted machine
It is possible in standard cryptographic assumptions (like, existence of cryptographic hash functions), and proofs can be made non-interactive in a random oracle model.
Modern zero knowledge proofs ...
- 166
4
votes
The factoring problem reduces to order finding or is it the other way around?
Both!
You may want to read the answers to this related question, and the 1987 paper of Heather Woll, Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179 cited ...
4
votes
Is there a candidate for a post-quantum one-way group action?
Yes, there is an old proposal for this due to Couveignes, which was independently rediscovered by Rostovtsev and Stolbunov.
In both cases, the set of elliptic curves with some common endomorphism ...
- 156
3
votes
Consequences of OWFs for Complexity
This is a late response.
First, to correct what you wrote:
Cryptographic pseudorandomness (the one obtained from OWFs) doesn't have enough stretch to derandomize "naturally defined" computational ...
- 351
3
votes
Accepted
Problems equivalent to the existence of secure cryptosystems?
One-way functions are implied by all of these things, and known to imply symmetric encryption and digital signatures. These equivalences are indeed found in (theoretically-focused) text books.
The ...
- 878
3
votes
Password checking algorithm
As much as you're being downvoted and attacked, your idea is absolutely right, correct, and valid.
You've nearly reinvented bcrypt.
Let's say we have encryption algorithm (doesn't matter which one):
...
- 131
3
votes
Alternatives to Diffie Hellman
The Wikipedia page on "Post-quantum cryptography" provides a list of proposals for PKE resistant to quantum attacks. Quantum algorithms can solve DL in finite abelian groups (as well as a few ...
- 878
3
votes
Accepted
What is the state of the art in online voting?
(Summarizing the discussion in the comments)
A mechanism to defend against bribes/coercion:
The simplest variant is, make the voter enter a password in order to vote, but do not provide an ...
- 2,151
3
votes
Accepted
Cryptography protocols using graph problem instances
Number theory (along with neighboring "algebraic" areas like lattices and group theory) gets used for public-key crypto because the problems for which we know distributions on instances that (a) are ...
- 878
3
votes
Accepted
Would an NP-complete public key cryptosystem imply NP=co-NP?
Your argument is correct about the FACTORING problem, but it does not automatically generalize to all public-key cryptosystems.
Here's an excerpt from an exercise by Dominique Unruh, showing ...
- 16.5k
3
votes
If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'
So I found a simple proof, but the proof is a bit fastidious to write (the symmetries make it easy to check however). If you have a more elegant/fundamental way to prove it, let me know! Or if it's a ...
- 173
Only top scored, non community-wiki answers of a minimum length are eligible