Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

If I have to encrypt a 32 bit plaintext in each of Paillier, SSE and OPE, how can I make an estimate of the ciphertext sizes respectively in order to reserve the amount of space in a database?

share|improve this question
add comment

2 Answers

How to know how much space to reserve? There are two ways:

  1. Take an implementation of the scheme, encrypt a 32-bit plaintext, and see how long the resulting ciphertext is. This is the simplest approach.

  2. Understand the scheme at a conceptual level, and then use your understanding of the algorithm to predict how long the ciphertext will be.

Since it sounds like you don't understand the schemes at a conceptual level, my recommendation is that you use the first approach.


Note that your question does not provide enough information to answer your question completely. Here's what I can tell you, given the information in your question:

  • Paillier. Suppose you want security equivalent to that of 2048-bit RSA (a reasonable level of security; anything much shorter won't be very secure). Then Paillier ciphertexts will be 4096 bits wide: twice the length of the length of $n$. That's because a Paillier ciphertext is a number $c$ modulo $n^2$ (i.e., $c$ is between $1$ and $n^2-1$). Even if you just want to encrypt a 32-bit plaintext, the ciphertext will still be 4096 bits long. I know, that is a downside, but that's just the way it is.

  • OPE. Order-Preserving Encryption (OPE) is not a single scheme; it is a goal for a scheme. It's like the difference between "RSA" vs "public-key encryption"; the former is a scheme, the latter is a goal. OPE is analogous to "public-key encryption", not to "RSA". Therefore, I can't tell you how long the ciphertexts will be if you use OPE, because the length of the ciphertexts will depend which OPE scheme you use, and there are many proposed schemes for OPE.

  • SSE. I don't know what the acronym SSE refers to. If SSE refers to Searchable Symmetric Encryption, then there's a similar situation: we can't tell you how long the ciphertext will be, because there are many SSE schemes out there, and without knowing which of those schemes you are intending to use, we can't tell you how long the ciphertexts will be.

share|improve this answer
add comment

All in all (and not looking at the multitude of possible, individual implementations), I would say that you should be somewhat "OK" if you reserve about twice the size of the plaintext, to store your ciphertext in a database. In your case, expect 32 bit plaintext * 2 = 64 bit ciphertext — at least.

share|improve this answer
1  
A Paillier ciphertext will be a lot longer than 64 bits. Probably more like 4096 bits (assuming a 2048-bit key, which is about the level needed to provide good security today, given the state of modern factoring algorithms). –  D.W. Oct 3 '13 at 17:55
    
Similar comments apply to SSE and OPE. It is extremely unlikely that 64 bits will be sufficient for the ciphertexts of SSE and OPE. And, as explained in my answer, the length of the ciphertexts for OPE and SSE depends upon which scheme you use, so there is not one answer to the question (your answer seems to be based upon the erroneous premise that there is only a single algorithm for SSE/OPE). –  D.W. Oct 3 '13 at 18:03
1  
To the OP: If you're curious about ciphertext size for OPE, go to the bottom of page 9 of the paper e-sushi linked. There's a section called 'Choosing the Ciphertext Space Size' that should answer your questions. –  pg1989 Oct 3 '13 at 18:37
1  
@e-sushi I don't think the ciphertext size is exponential to the plaintext size according to the paper you provided. the ciphertext SPACE size is exponential to the plaintext SPACE size. The actual ciphertext is the output of AES according to the paper. –  curious Oct 28 '13 at 18:07
1  
@curious Maybe you should add your own answer to the question. After all, it never hurts getting more answers at Crypto.SE… and it keeps the comment area a bit cleaner too. ;) –  e-sushi Oct 28 '13 at 21:11
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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