1
$\begingroup$

I would like to know if

given a public-key encryption scheme (PKES) with ciphertext expansion close to 1, and an integer N greater than or equal to 2

there exists a method for constructing a PKES with ciphertext expansion: 

size(ciphertext) = size(plaintext) x N

Preferably, the constructed PKES would be similar to the given PKES in terms of security and efficiency.

Thank you.

Edit [about padding][@poncho]: I work with two different entities represented as bitstrings. Let's call them large and small. 

size(large) = size(small) x N

Let encryption and decryption functions of the PKES be (E,D).

I receive many large bitstrings, and there is a need to store the small bitstrings which are derived as follows:

smallInstance = D(largeInstance)

At a later point, largeInstance should be recoverable using the public key:

E(smallInstance) = largeInstance

The problem I see with padding here is that it is not possible to use a constant padding for all the associated small bitstrings, and it is not desirable to store all the different paddings $pad_i$ obtained from:

smallInstance_i || pad_i = D(largeInstance_i)
Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Well, you could construct a PKES by having the ciphertext consist of the original (nonexpanded) ciphertext, followed by (N-1) x size(plaintext) random bits. However, I suspect that wouldn't meet your requirements; so, what problem are you trying to solve? $\endgroup$ Commented Jan 20, 2018 at 18:11

1 Answer 1

Reset to default
1
$\begingroup$

From your expanded comments, it appears that you hope to use encryption to do data compression; that is, you have an $N$ Megabyte input, and hope to store it in a 1 Megabyte storage, and later recover it in toto.

Sorry, but that's (probably) impossible. If there are $2^n$ possible largeInstance's, then you cannot store them in less than $n$ bits, and be able to recover it later.

The only case where it might be achievable is if the largeInstance's have a great deal of redundancy (and so that even though they are $n \times N$ bits long, only $2^n$ values are actually possible); if so, you'd be better off looking at a data compression method, rather than an encryption method.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I've read somewhere that there is this McEliece cryptosystem which does something similar (I thought). I didn't really think how it would work: (disallow some values on the larger side? information in keys help?) When you put it like that, 2^n possibilities and less than n bits, it does look impossible. So after your answer I've checked the wiki page for McEliece and noticed that its encryption is probabilistic. So recovering original values would not be possible I suppose... $\endgroup$ Commented Jan 23, 2018 at 9:26
  • $\begingroup$ @ZemnodTremnavic McEliece works like this: You have some data vector, you run that through a matrix to get about 1.28 times larger ciphertext vector and then you add bit errors at about one hundred random positions. On decryption you then take this ciphertext and apply your error-correction scheme to get the original message back. $\endgroup$ Commented Aug 21, 2018 at 9:39

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.