21

There are two aspect that need to be mentioned. The first is the general idea of defining a PRG by having its output look different than uniform to small circuits. This idea goes back to Yao and is really the strongest possible definition you can ask for when aiming explicitly at pseudo-randomness for computationally-bounded observers. The second ...


19

If I am understanding the problem correctly, it would seem to amount to public flipping a $k$-sided coin. There seem to be lots of ways to do this if you assume bit commitment. One example would be having each party generate a random integer between 0 and $k-1$, using bit commitment to publicly commit to that bit string. Then once each agent has committed, ...


17

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 not the first to think of the idea of trying to base cryptography on NP-complete problems. The problem is that NP-hardness only ensures worst-case hardness, ...


16

The key phrases you are probably looking for are "information-theoretic cryptography" and "quantum cryptography". Searching the literature on these topics will turn up lots of work of the sort you are looking for. Some example highlights below: For confidentiality: the one-time pad, the Wyner wiretap channel, secret sharing, quantum key exchange, etc. For ...


15

As other users have hinted at, this is a well-studied problem in cryptography. It is called "coin-flipping" and is a special case of multiparty computation. What protocol does the job actually depends on the context quite a lot. In the "standalone" setting, the protocol will be run in isolation, without players being involved in other protocols (or ...


15

1) What is meant by necessary is that one way to generate a $k$-wise independent distribution is to break the input in blocks of $k+1$ bits, and let the $(k+1)$th bit of each block be the parity of the other $k$ bits in the block. Obviously this distribution can be broken just by computing parity on $k$ bits. The result you claim follows from the fact that ...


13

The notion of "theoretically sound" pseudorandom generators is not really well defined. After all, no pseudorandom generator has a proof of security. I don't know that we can say that a pseudorandom generator based on the hardness of factoring large integers is "more secure" than, say, using AES as a pseudorandom generator. (In fact, there is a sense that it ...


12

Actually, there is a lot going on in the research of better and faster error correction codes for QKD. The biggest bottleneck of the CASCADE protocol is that it requires a lot of classical communication between Alice and Bob. A lot of work has been done on LDPC codes. You can have a look to the following papers: -Efficient reconciliation protocol for ...


12

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. As Ron points out, this extends to computational complexity under plausible assumptions. Maybe: Nash equilibrium is arguably the flagship problem of "Christos ...


11

Note: please read the comments below. This protocol seems to have problems. I don't know much crypto, but perhaps the following would work. Assuming the $p_j$'s are publicly known, all that's needed to determine the winner is to select a random number from [0,1]. Here's the process: Each agent selects a random vector in $\{0,1\}^b$, where $b$ is the ...


10

I'm one of the authors. Someone pointed me to this question. Based on a quick reading, here's an attempt at answering your concern. What may not be very clear from this version of the description of the simulator (this was the first time I was describing a simulator, and admittedly it reads a bit too much like machine language) is that the view output by ...


10

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 proof of language membership (assuming OWFs exist). To this end, their presented a ZK proof for graph 3-colorability. Later, Bellare and Goldreich (CRYPTO '92) ...


9

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 enabled the attacker to forge two distinct PDF documents that have the same SHA-1 hash value. I.e. They extended a given prefix $p$ with two distinct near-...


9

You seem to be confusing theory with practice. A theoretically sound pseudorandom generator is a bad fit for practical use for several reasons: It's probably very inefficient. The security proof is only asymptotic, and so for the particular security parameter used, the pseudorandom generator may be easy to break. All security proofs are conditional, so in ...


9

No, the intuitive observation "There are about $\sqrt{n}$ prime factors to try" does not imply a lower bound on the complexity of factoring. There is absolutely no reason that a factoring algorithm must try every possible prime factor, or even that the algorithm's behavior should resemble "trying" different factors at all. Even though precisely the same ...


9

I assume you want an efficient algorithm, e.g., one whose running time is polynomial in $n$. (If you don't care about running time, then heuristically about $4n/\lg m$ samples should suffice to uniquely determine $a,b,m,p$, and you can use exhaustive search over all possible $2^{4n}$ parameter choices to find the correct one. Of course, the running time of ...


9

(I am interpreting this question in the following way due to the comments.) In implementations of cryptographic systems, hash functions like the SHA-256 are defined by a deterministic algorithm mapping arbitrary-length bit-strings to some fixed-length bit-strings. This situation is troublesome for formal analyses (reductions) of these systems because, when ...


9

The main thing missing from your list is the beautiful 2006 paper of Klivans and Sherstov. They show there that PAC-learning even depth-2 threshold circuits is as hard as solving the approximate shortest vector problem.


9

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 structure, which we exploit. With no structure, we don't know what to do. With too much structure, the problem becomes efficiently computable (thus useless ...


9

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 finding a solution requires to either: break the soundness of the proof system obtained by applying the Fiat-Shamir heuristic to the famous sumcheck protocol, or ...


8

Polylog independence may not be the only way to fool $AC^{0}$ circuits. To illustrate this example, consider the class of linear polynomials. Any zero set of a linear polynomial is $(n-1)$-wise independent but of course this doesn't fool linear polynomials. Hence, $(n-1)$-wise independent distributions do not fool this class. This of course doesn't mean that ...


8

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 to "something that looks hard to invert to me", but the expert's response is usually more like "something that many smart people have tried to invert but failed"...


8

(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 short, they give proofs of work based on problems like Orthogonal Vectors whose hardness is well understood and to which many problems (e.g., k-SAT) can be reduced ...


8

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 instance) to delegate the computation to an untrusted party without disclosing the input. This doesn't answer exactly your question, since such scheme doesn't map a ...


7

Actually, the problems BBB and BBB-F above are not currently specified as languages or decision problems (the black box is not explicitly given to us as a binary string of some kind, is it?), so these problem cannot be in NP, PP, PSPACE, or even decidable/undecidable. A fundamental property of languages in the computability/complexity sense is that no bit of ...


7

What you want to do is called "Private Set Intersection". You can think of Alice and Bob as each holding sets (the indices for which their strings are "1"), and they want to compute the intersection (the bitwise AND) so that neither of them learns anything about the other's set except what is implied by the intersection itself. This problem is well studied....


7

A good reference is Code-Based Game-Playing Proofs and the Security of Triple Encryption by Bellare & Rogaway. The statement that you are asking about is called the PRF/PRP switching lemma. This paper goes into significant detail about "standard" proofs of this lemma and the subtleties therein. It uses the switching lemma as an illustrative example to ...


7

(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 years ago), trivially reduces from the Extended Learning with Errors (eLWE) problem first introduced in the work Bi-Deniable Public-Key Encryption by O'Neill, ...


7

The LPN problem is indeed believed to be hard, but like most problems we believe are hard, the main reason for it is that many smart people have tried to find an efficient algorithm and failed. The best "evidence" for LPN's hardness comes from the high statistical query dimension of the parity problem. Statistical queries capture most known learning ...


7

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 designed, wherein each proof-of-work shows that two knots are not likely to be equivalent/isotopic. In more detail, as is well known in the Graph Non ...


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