4

Why don't most encryption algorithms use perfect secrecy? Perfect secrecy can only achievable if the $\text{key size} \geq \text{message size}$ and the key is never re-used. It is not suitable for modern usage, where a lot of messages are sent/received and that is impractical since one has to send the key beforehand in a secure channel and this is not ...


3

How many non-trivial*, interesting perfect secrecy systems are there other than the one-time-pad? Infinitely many. Let $\mathbb G$ be a group (written multiplicatively). Then $\operatorname{KeyGen}(1^n)=k\stackrel{\$}{\gets}\mathbb G^n$, that is the key is a vector of $n$ independently random group elements. $\operatorname{Enc}(k,m):\mathbb G^n\times \...


2

The answer to your question in the title is No. For example, let's modify a little the one-bit OTP considered in your question description (with a one-bit message space $M=\{0,1\}$). Instead of using a one-bit key $K=\{0,1\}$, we can use a two-bit key $K=\{00,01,10,11\}$ and discard its last bit when doing the xor. It's easy to see that perfect secrecy holds ...


2

I don't think the statement is true, and I will come to a counterexample later. Formalization One possible formalization of the statement could look like this: Let $\mathcal{M}$ be the message space, and $\mathcal{C}$ the ciphertext space. We define two arbitrary distributions over $\mathcal{M}$: $M_a$ and $M_b$, where $\Pr_{m \in \mathcal{M}}[M_a = m] = p^\...


1

I don't think the question makes much sense. Let's look at the measure a bit closer: First, the measure is the limit of the density. That means, the things measured by this are infinite subsets of the natural numbers. It does not measure single elements in any way. And all finite sets have measure 0. The additive property only holds for disjunct subsets of ...


1

"…let the key be chosen using the asymptotic density measure…" Well, as far as practicality goes, there's your first problem. The asymptotic density of any bounded set of integers is, by definition, zero. So, the probability of your key being shorter than one gigabyte? Zero. The probability of you owning enough disk space to store the key? Zero....


1

Let the key, message, and ciphertext spaces all be $\mathbb{Z}$, which is in bijection with $\mathbb N$. I'm going to pick a specific bijection by making the non-negative integers map to evens and the negative integers map to odds, and let $\mu$ be the asymptotic density measure applied to $\mathbb{Z}$ using this bijection. We can then construct a one-time ...


1

@fgrieu's answer uses a stateful oracle, which I think is cheating a bit. The problem is impossible with stateless oracles (and perfect correctness). Suppose the encryption algorithm is written as $E^{\mathcal O}(pk,m;r)$ where $\mathcal O$ is any stateless oracle; $pk$ is the public key; $m$ is the plaintext; $r$ is the randomness; $E$ is a deterministic ...


1

Yes, it is possible to have perfectly secure public-key cryptography with oracles (though the oracles I'll exhibit do not seem quite reducible to those of the question). As pointed in the question, there can't be a completely public encryption procedure that works (in the sense that decryption is possible with the appropriate secret) and is perfectly secure ...


1

What you're saying is unclear... If you have uncountably many possible keys, if the scheme is computationally secure in the normal case (you're using an already-secure algorithm), your algorithm would fit your definition of being perfectly secure - the computation required to break it goes up with the key size, effectively creating an infinite search time ...


1

If I understand correctly, your input to HMAC is the ciphertext $c$, padded with null bytes (to a multiple of 16 bytes): # pad to a multiple of 16 bytes if self._len_ct & 0x0F: self._auth.update(bytes(16 - (self._len_ct & 0x0F))) As a concrete example, suppose the ciphertext is $c=$ deadbeef00, then you will compute the HMAC tag as $t ...


1

It is helpful to first define what a perfectly secure block cipher is. In the ideal case there are n different keys where each key uniquitely indexes one of the permutations mapping {0,1}^k to {0,1}^k. In this case we have n=(2^k)! Possible permutations/keys. Perfect security typically means that no information is revealed at all. Not even against an ...


1

So there is already PFS in phase I by design. Each time someone establishes a new IPsec VPN tunnel, a new DH shared secret g^xy will be used to compute SKEYID_d, right? Hence, the session key in phase II will also be unique. This is PFS right there? No, you do not recompute a fresh SKEYID_d for every Quick Mode; instead, a value for SKEYID_d is assigned ...


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