# Tag Info

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

### Does Grover's algorithm really threaten symmetric security proofs?

Yes, but also no. Grover's algorithm is actually quadratically faster than classical algorithms. However there are a few catches. Quantum computers are slow and expensive. This means that in the near ...
• 281

### Is Poly1305 an information-theoretically secure MAC?

Can the $AES_k(n)$ portion be simply replaced with $k \oplus n$? No, but you're close, it would be replaced with $k + n$, where $+$ is addition modulo $2^{128}$; then it becomes informational ...
• 148k
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 ...
• 49k
Accepted

### Does Grover's algorithm really threaten symmetric security proofs?

Despite the classical security proof, Grover's algorithm threatens symmetric key cryptography. The main reason is that classical security proof assumes that the adversary makes classical queries to ...
• 438

### Does Grover's algorithm really threaten symmetric security proofs?

Does Grover's algorithm really threaten symmetric cryptography? Lov K. Grover's algorithm reduces the key search into $\mathcal{O}(\sqrt{2^n})$ instead of the $\mathcal{O}(2^n)$. What is generally ...
• 49k

### How long to wait to feed hashing using SHA 256?

You should aggregate bits until you have enough seed bits to start your DRBG using an initial seed. Your seed should contain at least 128 bits of entropy (the amount of uncertainty to an attacker). ...
• 93.2k
Accepted

### What is the difference between information-theoretic and perfect types of security?

Information-theoretic security means that any algorithm (even unbounded) has a negligible probability of breaking the security property (in the security parameter). This is the same as unconditional ...
• 20.2k

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

### Does information theoretical security definition imply DDH, RSA, QR does not hold?

Does this mean that the standard definitions for DDH, RSA or QR do no hold in that setting, because the definitions assume some bounds on the computational power of the adversary? That is correct; a ...
• 148k

### Does Grover's algorithm really threaten symmetric security proofs?

I'm going to answer the question in your headline and then go forward. No. Grover's algorithm is a canard and you ought to stop worrying about it. The major reason for this is that Grover reduces the ...
• 2,314

### what is the motivation behind quantum key distribution with Continuous variable?

It's easier to work with a lot of photons in a stream than to work with a single photon at once. This is explained in the paper introducing continuous-variable quantum key distribution. (With ...
• 48.6k

Without proof or even a precise definition: when a random variable has independent outputs with $p$ the probability to output $c$, then an optimal encoding of the source's outputs (one that minimizes ...
• 142k
Accepted

• 46.2k
Accepted

### How to securely combine multiple sources of entropy?

If your keys, taken together, have sufficient entropy to support your desired security level, then HKDF (paper) is a conservative solution here, because it assumes that the input keying material to ...
• 14.5k
Accepted

### Statistics-heavy crypto papers

I am afraid your search for Annals of Stats etc. level of purely statistical theoretical papers in cryptology may not yield too many examples. The field is very applied and the role of statistics is ...
• 22.7k
Accepted

### Is it possible that the entropy of a cipher system to be zero or infinite?

A cryptosystem has a few requirements: It is defined with a messagespace and a ciphertext space. Both of them are usually some finite algebraic structure. Also, the key is chosen from some algebraic ...
• 12.7k

### PRNG output with truly random noise

Usually what you call "information theoretic hardness" is denoted as statistical indistinguishability. And it is pretty much black and white only: Two distributions are distinguishable or not. When ...
• 12.7k

### Would a symmetric cipher with a keylength a big as the data length be information theoretically secure?

No, using any keyed permutation with key length equal to the block size reduces the number of possible plain texts by ~1/3 Assume first that AES reasonably approximates a pseudorandom permutation, ...
• 1,741

### Under what conditions is broadcast possible? (Cryptographically, and in the model of Maurer 2006)

This is a somewhat standard method for generalizing results based on threshold adversaries. Let $n$ be the number of parties and let $\mathcal{C} \subseteq 2^{[n]}$ denote the family of subsets that ...
• 13.5k
Accepted

### Monotonicity of min-entropy

Let's make it slightly simpler by proving the case of two variables with no tuple indexing to clutter it up. Fix two random variables $X$ and $Y$. Is $H_\infty[X] \leq H_\infty[(X, Y)]$? For each \$...
• 48.6k