Skip to main content
15 votes

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 ...
Gordon Davisson's user avatar
15 votes

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 ...
Oscar Smith's user avatar
13 votes

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 ...
poncho's user avatar
  • 148k
13 votes
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 ...
kelalaka's user avatar
  • 49k
13 votes
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 ...
Hhan's user avatar
  • 438
11 votes

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 ...
kelalaka's user avatar
  • 49k
10 votes

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). ...
Maarten Bodewes's user avatar
  • 93.2k
9 votes
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 ...
Geoffroy Couteau's user avatar
9 votes

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 ...
Ilmari Karonen's user avatar
8 votes
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 ...
poncho's user avatar
  • 148k
8 votes

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 ...
Jon Callas's user avatar
  • 2,314
7 votes

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 ...
Squeamish Ossifrage's user avatar
7 votes

Doubt about Shannon entropy

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 ...
fgrieu's user avatar
  • 142k
6 votes
Accepted

Security of Carter-Wegman polynomial authenticators, and their concatenation?

Tight security bound for elementary attack model: Well, here's the general theory; suppose the attacker had a valid message, MAC pair $(m_{1,...,l}, H)$ with $$H=s+\sum_{i=1}^l m_{(l+1-i)}\cdot {r}^...
poncho's user avatar
  • 148k
6 votes

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

Yes, it does. Any cryptosystem relying on factoring being hard (RSA, Paillier, Rabin, etc.) is immediately broken by an unbounded adversary, because he can just try out all smaller prime factors to ...
tylo's user avatar
  • 12.7k
6 votes
Accepted

Information theoretical lower limit on the size of public and private keys

The private key can be reduced to $k$-bit in any asymmetric cryptosystem (encryption or signature) with a resistance to brute force of $O(2^k)$ steps (on a conventional, non-quantum computer). Proof ...
fgrieu's user avatar
  • 142k
5 votes
Accepted

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

Since the question was labelled unclear, I’ll first clarify my understanding of the question, and then give various motivations (academics, then practical). This answer turned out to be quite long ...
Frédéric Grosshans's user avatar
5 votes
Accepted

How long to wait to feed hashing using SHA 256?

There are three classes of random number generators (my own informal classes), dependant on the relative entropies that flow in and out:- Class 1. Hout < Hin, which is a true random number ...
Paul Uszak's user avatar
  • 15.5k
5 votes
Accepted

Proof that any key exchange protocol is vulnerable to MitM attacks in the absence of shared information or trust

It has nothing to do with information theoretic. You just need to construct an adversary and argue that it works. In this case, the adversary is simple. Let $A$ and $B$ be parties with no secret ...
Yehuda Lindell's user avatar
5 votes

How well is it understood mathematically why encryption schemes are hard to crack?

...I know that encryption is all based on two principles of "confusion" and "diffusion" Symmetric algorithms such as block ciphers, hash functions, and stream ciphers are based on these principles. ...
Ella Rose's user avatar
  • 19.7k
4 votes
Accepted

Is Poly1305 an information-theoretically secure MAC?

So in this scenario the $k$, $r$ and $n$ are unique and truly random per message sent. […] Now given that this construction creates the Poly1305 tag: $$\textsf{Poly1305}_r(m, \textsf{AES}_k(n))$$ Can ...
Ilmari Karonen's user avatar
4 votes
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 ...
Luis Casillas's user avatar
4 votes
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 ...
kodlu's user avatar
  • 22.7k
3 votes
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 ...
tylo's user avatar
  • 12.7k
3 votes

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 ...
tylo's user avatar
  • 12.7k
3 votes

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, ...
Richard Thiessen's user avatar
3 votes

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 ...
Mikero's user avatar
  • 13.5k
3 votes
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 $...
Squeamish Ossifrage's user avatar
3 votes
Accepted

Oblivious transfer impossible from noiseless channels

Information theoretic OT cannot be achieved because OT can compute any function in a two party setting, that is, OT is complete (meaning, it is among the hardest problems in its complexity class) as ...
Karan Veer's user avatar

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