4 ms·
> It seems like they're using "secure cryptography" kind of narrowly, as AFAIK a one-time pad could still be secure without any kind of one-way function. The s
by q-big 5y ago
> It seems like they're using "secure cryptography" kind of narrowly, as AFAIK a one-time pad could still be secure without any kind of one-way function.
The security of OTP is much more restricted than most cryptography books admit.
OTP's security can be proved in the following cases:
* the set of secrets (plaintexts) is finite,
* the set of secrets (plaintexts) is the uncountable sets of streams, say, N -> {0,1}.
What one is interested in for cryptography is if the set of secrets is a countable domain, say the a set of strings (e.g. {0,1}^*).
Bad news:
"[N]o perfect private-key encryption schemes, over the set of all strings, exist. Stated informally, this means that there is no way to perfectly encrypt all strings without revealing information about their length."
This quote is taken from the abstract of
Chor, B., Kushilevitz, E. Secret sharing over infinite domains. J. Cryptology 6, 87–95 (1993). https://doi.org/10.1007/BF02620136 https://doi.org/10.1007/BF02620136
> https://link.springer.com/article/10.1007/BF02620136 https://link.springer.com/article/10.1007/BF02620136 (website of paper)
> https://link.springer.com/content/pdf/10.1007/BF02620136.pdf https://link.springer.com/content/pdf/10.1007/BF02620136.pdf (PDF)
- kadoban 5y agoIsn't leaking the length pretty harmless? You can make that leak arbitrarily small by adding randomized amounts of padding with various distributions as well, right?
- q-big 5y ago> Isn't leaking the length pretty harmless? Whether this is harmless or not is up to a debate. But it is a clear violation of the "information-theoretic security" property that (nearly) every textbook about cryptography mentions or proves for OTP. Just to be clear: these proofs are correct, they just do not work when OTP is applied to a countable set of secrets - which is actually the situation that "everybody" is interested in.
- ganzuul 5y agoToomanysecrets.
- cjg 5y agoI would argue that it is not harmless. Let's say that you have a P2P application for sharing MP3s. There are many millions of MP3s, but if an attacker sees a download of a particular size, then they have a pretty good idea of which MP3 has been downloaded.
- jychang 5y agoWell, can you tell me if you got accepted into a college based off the size of the letter you got?
- nybble41 5y agoNot if the college is deliberately trying to hide that information—they'll make the acceptance and rejection letters the same size. Most systems have a finite limit to the sizes of the messages they can handle. (If nothing else there are practical limits to both the maximum transfer rate and the operators' patience.) It's inefficient, but you can pad all messages to that length regardless of the size of the plaintext.