# Tag Info

## Hot answers tagged cr.crypto-security

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 ...
• 10.5k

### Complexity classes for proofs of knowledge

This is not an actual answer; I'm just sharing some results (which do not fit in one comment). Goldreich, Micali and Wigderson (J. ACM, 1991) proved that every language in NP has a zero-knowledge ...
• 16.4k

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

### Why does most cryptography depend on large prime number pairs, as opposed to other problems?

Boaz Barak addressed this in a blog post My takeaway from his post (roughly speaking) is that we only know how to design cryptographic primitives using computational problems that have some amount of ...
• 4,228
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

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

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

### 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 ...
• 842

### Candidates for One-Way Function

Here is a "canned" answer that might be useful, but has no cryptographic depth (hopefully we get answers with depth as well). What makes for a good candidate OWF? The naive answer tends to boil down ...
• 7,090
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,973
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 ...

### 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
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,493
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
Accepted

### Cryptographic systems that don't leak linear combinations of encrypted bits

Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing. ...
• 10.5k

### Why does most cryptography depend on large prime number pairs, as opposed to other problems?

All of what I am going to say is well-known (all the links are to Wikipedia), but here it goes: The approach used in RSA using pairs of primes can also be applied in a more general framework of ...
• 13.2k
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,789
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,973
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
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 ...

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

### Information-theoretic Diffie-Hellman

No, there is no information-theoretic analog that is secure against computationally-unbounded adversaries. To form an analog, we'd need an injection $\varphi$ that maps $x$ in fine representation to \$...
• 10.5k

### Why SHA-224 and SHA-256 use different initial values?

This We called Domain Separation, when we use same algorithm for different output size. Separation is necessary because if i found two messages which have hash value (SH256), differs only in last ...
• 51
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

### 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 ...
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,090
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 ...

### Candidates for One-Way Function

As for your last question, the are several candidates for combinatorial one-way functions. This paper by Kojevnikov and Nikolenko lists three combinatorial complete one-way functions that are based ...

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