# Tag Info

25

@Suresh: following your advice, here is my "answer". The status of circuit lower bounds is quite depressing. Here are the "current records": $4n-4$ for circuits over $\{\land,\lor,\neg\}$, and $7n-7$ for circuits over $\{\land,\neg\}$ and $\{\lor,\neg\}$ computing $\oplus_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n$; Redkin (1973). These bounds are tight. ...

22

Here's an argument that one-way functions should be hard to invert. Suppose there is a class of 3-SAT problems with planted solutions that are hard to solve. Consider the following map: $$(x, r) \rightarrow s$$ where $x$ is any string of bits, $r$ is a string of bits (you could use these to seed a random number generator, or you can ask for as many random ...

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

18

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

17

If $N=pq$, the period $r$ will always be a divisor of $\phi(N)=\mathrm{lcm}(p-1,q-1)$. If you choose $p-1=2p'$ and $q-1=2q'$ for $p',q'$ prime, then unless you are incredibly lucky, we will have $r \geq p'q' \approx N/4$. I also believe that we can efficiently find primes $p$ with $p=2p'+1$ by choosing candidates randomly and ...

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

This is called the known-plaintext attack. Any cipher algorithm which is prone to this type of attack is considered very weak. Therefore, AFAIK, no present-day cipher (e.g. AES) has this weakness. Even DES needs 243 known plaintexts to be broken under linear cryptanalysis. (see this topic on Wikipedia). On the other hand, all hope is not lost. Weak ciphers ...

13

I'll give a short answer: The existence of seemingly-hard problems, such as FACTORING or DISCRETE LOG made theorists believe that OWF exist. In particular, they tried for decades (since 1970s) to find efficient (probabilistic polynomial-time) algorithms for such problems, but no attempt succeeded. This reasoning is very similar to why most researchers ...

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

11

The technique of "hopping" from one game to another, and proving the security through a "sequence of games" is not new. In particular, there are several papers which discuss these techniques, and exemplify them through various security proofs. The famous examples are: Sequences of Games; A Tool for Taming Complexity in Security Proofs by Victor Shoup (2006) ...

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

There are several techniques which prove the nonexistence of black-box reductions. They are all inspired by the seminal work of Impagliazzo & Rudich. Let me describe the Impagliazzo-Rudich (IR) technique at a high level. In crypto, it is well-known how to construct a secure secret-key exchange protocol from trapdoor one-way permutations. However, all ...

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

There are many types of cryptanalytic attacks: Linear approximations, Algebraic attacks, Time-memory-data-tradeoff attacks, fault attacks. For example you can read the survey: "Algebraic Attacks On Stream Ciphers (Survey)" Abstract: Most stream ciphers based on linear feedback shift registers (LFSR) are vulnerable to recent algebraic attacks. In this ...

9

Hardness of NP-complete problems is not sufficient for cryptography. Even if NP-complete problems are hard in the worst-case (P≠NP ), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using the $P \ne NP$ ...

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

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

8

There is a significant gap even when it comes to basic primitives such as pseudorandom generators. Consider for example pseudorandom functions. In practice people use things like AES, which differ from theoretical candidates (Goldreich, Goldwasser, Micali; Naor, Reingold; etc.) along several dimensions: First, the parameters are completely different, e.g. ...

8

Unlike the other answers, this is more along the lines of "things we should worry about when saying something is 'provably secure'" as opposed to places where TCS has been used in security. Thus, it addresses the first question of security concerns when working with theory. As hackers say, theoretical results are often tangential to real-world security. ...

8

Some functions are conjectured to have that property, aptly called moderately hard. They were first proposed in the context of spam fighting, and then found their ways into more complicated applications, such as concurrent zero knowledge and timed commitment. They usually use a function of the form $f(x) = g^{2^{2^x}} \bmod N$, first suggested by Rivest, ...

8

The Feige-Fiat-Shamir (FFS) identification protocol is a proof of knowledge (PoK), in which the prover (Peggy) proves her knowledge the square roots of the given input to the verifier (Victor). FFS want to discriminate PoK from proofs of language membership, in which Peggy proves that the input has some property (more formally, the input belongs to a ...

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