4
$\begingroup$

I'm wondering, suppose we have a public key cryptosystem $P = (pk,sk)$ such that $$pk: \{0,1\}^n \to \{0,1\}^{n^2},$$ that is, the ciphertexts are $n$ times longer than the plaintexts (here, $n$ is supposed to be the security parameter). My question is

Does this imply some weakness of any kind on the cryptosystem (as $n$ grows)?

It's not that I have the intuition that there may be an issue, it's just a particular property that makes me think.

BACKGROUND

We're developing a PK cryptosystem based in multivariate polynomial equations. So far, our ciphertexts were as long as our plaintexts, but now we have this situation, where the ciphertext / plaintext length ratio is not constant. This has its own consequences in the algebraic point of view, but in the cryptographic setting... does it have any implication? Thanks!

Improve this question
$\endgroup$
8
  • $\begingroup$ Having a cipher-text longer than a plaintext is actually a feature, as it allows you to introduce randomness and check values to dodge CPA and CCA attacks. $n^2$ is a bit too much though. Ideally you'd aim for something like $n+384$ or maybe 512 (both in bits). $\endgroup$
    – SEJPM
    Commented Jul 7, 2016 at 20:00
  • $\begingroup$ @SEJPM $n + \text{constant}$ would be simply great, but we can't allow a constant in our case. Anyway, real parameters for our cryptosystem are $n\approx 50$ so $n^2 - n = 2450$. Too much, isn't it? $\endgroup$
    – Daniel
    Commented Jul 7, 2016 at 20:09
  • $\begingroup$ Well, it would require you to use like 7.5k bits to encode something like a 128-bit (150) symmetric key for hybrid encryption, which doesn't sound terribly efficient to me... (but usually there are no negative side effects to ciphertext expansion except that the ciphertext is terribly large) $\endgroup$
    – SEJPM
    Commented Jul 7, 2016 at 20:15
  • $\begingroup$ Note that for IND-CPA of any public-key encryption scheme (or even, symmetric encryption scheme with stateless encryption), ciphertexts must be usually longer than plaintexts. ​ (You might have had a secure trapdoor permutation family.) ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Jul 7, 2016 at 20:38
  • $\begingroup$ If it's asymmetric crypto, you can simply use a KEM-DEM approach, where you only use your fancy crypto to encrypt a value you derive a symmetric key from, which you use for the actual data. $\endgroup$
    – CodesInChaos
    Commented Jul 7, 2016 at 21:02

1 Answer 1

Reset to default
2
$\begingroup$

No. ​ ​ ​ ​ Also, note that by hybrid encryption, ciphertext overhead will always be
at most ​ ​ + poly(security_parameter) , ​ ​ no matter how long the message is.


For IND-CPA of any

public-key encryption scheme, or even
symmetric encryption scheme with stateless encryption

, ciphertexts for non-empty messages must be
overwhelmingly likely to be longer than plaintexts.


Your most recent comment suggests it was broken even in the following context, but otherwise you might have had a secure trapdoor permutation family whose domains are exactly the binary strings whose length equals the length chosen during key generation.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.