# Tag Info

11

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 ... 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 [3] and [4] ...

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

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

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

3

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 $x$, we have $$\Pr[X = x] = \sum_y \Pr[X = x, Y = y].$$ Note that since probability masses are always positive, $\max \Pr[\cdots] \leq \sum \Pr[\cdots]$; then ...

2

If you have a keyed family of $2^b$ distinct permutations $E_k(p) : \{0,1\}^b \times \{0,1\}^b \to \{0,1\}^b$ over $b$-bit blocks, and select an independent, uniform random key for each plaintext block, then your proposed mode is perfectly secure for the same reason that one-time pads are: for any candidate plaintext/ciphertext pair $(p, c)$, there exists a ...

2

AFAIK, no one has proven that AES on a single 128-bit block with a true-random 128-bit key does not provide information theoretic security (such a proof would probably be the end of AES as it would demonstrate a weakness). OTOH, no one has proven that it does. I suppose it is possible that it does, but such a proof is likely to be extremely difficult. Just ...

2

The question asks for an entropy extractor suitable for a particular camera, that is information-theoretically secure, but rejects hash on the rationale that hash functions are not perfectly secure. I'm afraid that for the same definition of secure in these statements, there's nothing on the book; perhaps nothing possible. A method considered in the ...

2

For Shamir's Secret Sharing, with a secret of size $n$, instead of having a finite field of order $n$, can we just use Shamir's Secret Sharing $n$ times, once for each bit, using a field of order $2$? If you are asking whether Shamir Secret Sharing works over the field $GF(2)$, well, no it doesn't (unless we have exactly one share); the problem is that, for ...

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