# Tag Info

15

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 there isn't enough information there to give you any idea (any information about) what the answer is. That's what's meant by information-theoretic security. (...

14

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 the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run ...

12

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 theoretic. Here's why: Poly1305 is based on a polynomial universal hash. This is a hash where we select a finite field $GF(p^i)$, select a private value $x \in GF(p^... 10 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). Then you could either add the bits as additional seed when you get it or you could first aggregate some entropy. With only an update rate of about 8 bits per ... 9 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 right one). But without enough information (e.g. the key in OTP, or enough shares in SSS) you would still have no way of telling which of the solutions is the ... 8 First of all there does exist information theoretically secure message authentication codes suitable for use with a one time pad. An HMAC is not one of those information theoretically secure. As far as I recall the first article presenting such a construction is the 1981 article by Wegman and Carter: New hash functions and their use in authentication and ... 8 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 computationally unbounded adversary could trivially solve any of these problems. For example, to solve the DDH problem ("given,$g, g^x, g^y, g^z$, does$g^{xy}...

7

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 apologies for the paywall. Ms. Greene, tear down this wall! Or read the arXiv preprint if you're not a rebel.) P.S. I originally answered the question as follows, ...

7

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 the expected number of bits consumed to encode all successive values of a large number of outputs, including order) will use on average $-\log_2(p)$ bit to ...

6

The term unconditional security was (as far as I know) coined by Diffie and Hellman in their seminal paper New Directions in Cryptography. Here is the snippet [... ] a system which can resist any cryptanalytic attack, no matter how much computation is allowed, is called unconditionally secure. Unconditionally secure systems are discussed in  and  ...

6

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 factorize a given modulus. For DDH (or similar methods in finite groups) it's basically the same, he can just try all possible exponents when there are finitely ...

6

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}^i$$ and he selects a different pair $(m'_{1, ..., l}, H')$. His pair would authenticate if: $$H'=s+\sum_{i=1}^l m'_{(l+1-i)}\cdot {r}^i$$ or, if $r$ happens ...

6

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 sketch: replace the RNG used for key generation by a PRNG with at least $k$-bit security and seeded with a $k$-bit key. And that bound can't be much improved ...

6

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 security: it does not rely on any computational assumption, and is not limited to probabilistic polytime adversaries. A perfectly secure protocol is such that ...

5

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 generator (the most secure and best) such as those by Swiss company ID Quantique. This is the class of generator that can be used for creating one time pad material. ...

5

For a scheme to be information-theoretically secure, you need that $$\Pr[M=m\mid C=c]=\Pr[M=m\mid C=c^\prime]$$ for all $c,c^\prime$ (that is, any ciphertext has the same probability $M=m$, so the ciphertext doesn't change the probability $M=m$). Let's suppose we have a $c$ and a $c^\prime$. Both of them have the same number of ones and zeroes, because both ...

5

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 information. An adversary $C$ playing man-in-the-middle interacts with $A$ pretending to be $B$, and interacts with $B$ pretending to be $A$. At the end, $C$ ...

5

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 Full disclosure: I am an academic who has worked on continuous variable quantum cryptography since my PhD thesis (defended in 2003), so I am biased towards this ...

5

...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. One Time Pads are not. And asymmetric algorithms are not built from these principles, though they may end up possessing them anyways. ... but these are very ...

4

I'm not aware of any attacks on SHA-512 this way. I would create a small function to validate that the input size to SHA-512 is indeed identical to the seed size though, just in case. Even without that the function should be secure. Kind of related is my question about KDF1 and KDF2. Note that implementation of HKDF-expand from a hash should be pretty easy, ...

4

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 the HKDF-extract might not be uniformly distributed. The most conservative way of using it in your case would be to supply the concatenation of your keys as the ...

3

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 the $\textsf{AES}_k(n)$ portion be simply replaced with $k \oplus n$? Yes, but it's still needlessly complicated. As long as each 128-bit key $k$ is random ...

3

Since you are looking for an algorithm that guarantees entropy for the output if the input it entropic, you are not actually looking for a PRNG, which would expand a seed to a longer random output, but only a transformation from a binary sequence to arbitrary values. You can achieve this using arithmetic coding, or range encoding, which is the same thing in ...

3

I'll further explain the comment of @CodesInChaos and then give a simple example: Explanation When the correctness requirement is weakened the encryption scheme can omit part of the message $m$ (of length $|m|$) to be encrypted and just "loose" it in a way that the cipher (the output of the Encrypt method) is totally independent of that part. Thus the ...

3

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 you ask "how much harder", you already drift into the area of computational indistinguishability. There are plenty of ressources for that keyword, including most ...

3

Imagine a one-bit message $m$. Attacker knows that $m = 0$ with probability $p$ and $m=1$ with probability $1-p$. (In many cases, $p=0.5$.) With one-time pad (Vernam's cipher) encryption, the attacker can't guess anything. If the ciphertext is 0, the plaintext is 0 with probability $p$ (and the plaintext is 1 with the probability $1-p$). Attacker can't ...

3

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, for each block of the message, the attacker (assuming unbounded computing power) can calculate the plain text for all keys. This is equivalent to throwing 2^128 ...

3

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 structure, and for symmetric ciphers that's usually finite. For asymmetric ciphers, usually a certain length (e.g. for RSA) is set, which also restricts the ...

3

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 the adversary can corrupt. For example, in the case of honest majority, $\mathcal{C} = \{ C \subseteq [n] : |C| < n/2 \}$. $\mathcal{C}$ has the Q2 property ...

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