1
$\begingroup$

We're developing a public key cryptosystem whose ciphertexts are actually much more long than the plaintexts (which, according to this question, is more a benefit than an issue).

However, we have a particular property. Most part of the public key can be chosen by the user. More precisely (in a high level explanation), the public key is $n+n^2$ bytes long where $n^2$ of them are chosen at random and the other $n$ bytes are certain function of these values and the secret key.

I was thinking that maybe we could choose these values not at random, but with certain structure: as we wish. For instance, it could be user's mail address or some function of it (expansion function, since $n^2$ is not small). I think this is close to ID-based encryption, but I don't understand this concept so deeply to state a relation. Moreover, not all the public key can be chosen so I'm not sure whether or not this is useful at all, or meet any requirements.

Is this property useful in any sense? can we get something good from this?

Having so long public keys is a storage problem, that we would like to balance with a good property from this "free choice" fact.

Improve this question
$\endgroup$
9
  • $\begingroup$ This is pretty much exactly ID-based encryption. $\endgroup$
    – fkraiem
    Commented Jul 8, 2016 at 23:34
  • $\begingroup$ @fkraiem : ​ That result would be very-much publishable, since any PKE scheme can be trivially modified to have the property described in this question. ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Jul 8, 2016 at 23:36
  • $\begingroup$ @RickyDemer How do you give this property to any PKE? the only trivial way to do this that comes to my mind is using some random "seed" to generate the private key and then computing the real public key from this secret key, and then append the seed to the pk. (I use this constructor since in Multivariate PKC, usually pk's are consequences of sk's choices). $\endgroup$
    – Daniel
    Commented Jul 8, 2016 at 23:44
  • $\begingroup$ @SolidSnake ​ ​ ​ (This might by what you're trying to describe, but anyway:) ​ rest_of_public_key_ ignores the public randomness and outputs the public key generated by the underlying scheme with the private key as randomness. ​ Encryption just ignores the public randomness. ​ Decryption is done with the underlying scheme's decryption algorithm using as private key the private key generated by underlying scheme with the actual private key as randomness. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Jul 8, 2016 at 23:53
  • $\begingroup$ @RickyDemer Exactly, but indeed, that's actually very trivial! I could claim that our construction is not trivial, since it heavily uses the (what I call in my comment) "seed". However, at first glance, one can not say a difference between our construction and the trivial one in terms of usability... $\endgroup$
    – Daniel
    Commented Jul 8, 2016 at 23:57

1 Answer 1

Reset to default
2
$\begingroup$

That property lets a trusted n2-byte random string be
enough to make the rest of public keys fit into n bytes.
In particular, forward secrecy can be more efficient if the sender can store such a string, since the string can have been generated by the same party as generates the rest of the public keys.



Also, if for random private keys and independent n2-byte random strings r0 and r1,


the distributions
$\langle$ rest_of_public_key_(r0,priv_key) , r0 $\rangle$ ​ ​ ​ , ​ ​ ​ $\langle$ rest_of_public_key_(r1,priv_key) , r0 $\rangle$
are indistinguishable

and

"encryptions" with ​ ​ $\langle$ rest_of_public_key_(r1,priv_key) , r0 $\rangle$
provide confidentiality even against the private key holder


, ​ ​ then you get a one-message-in-each-direction
oblivious transfer protocol against semi-honest receivers.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the answer! Ok, so let's see if I get it. Let's begin with the first paragraph, which I'm not understanding quite perfectly. Are you suggesting that we could fix our free_part and generate several public keys with this? actually, I was thinking in using different free_part for each user, but this idea is interesting. About your forward secrecy comment, I'm really not getting it... at all. Could you clarify this part please? $\endgroup$
    – Daniel
    Commented Jul 9, 2016 at 0:05
  • $\begingroup$ Yes. ​ For normal PKE schemes with $\left(\hspace{-0.02 in}n\hspace{-0.02 in}\hspace{-0.03 in}+\hspace{-0.05 in}\left(\hspace{-0.02 in}n^{\hspace{.02 in}2}\hspace{-0.05 in}\right)\hspace{-0.05 in}\right)\hspace{-0.02 in}$-byte public keys, to get forward secrecy, the receiver would have to send $n\hspace{-0.02 in}\hspace{-0.03 in}+\hspace{-0.05 in}\left(\hspace{-0.02 in}n^{\hspace{.02 in}2}\hspace{-0.05 in}\right)$ public-key bytes for each exchange. ​ (continued ...) ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Jul 9, 2016 at 0:31
  • $\begingroup$ (... continued) ​ For yours, if the sender can store the random-part between exchanges, then the receiver will only need to send $n$ public-key bytes for each subsequent exchange. ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Jul 9, 2016 at 0:32
  • $\begingroup$ Ok, I get it, $n$ new pk-bytes generated by the new sk-bytes using the same random_part. Now, the properties you mention about indistinguishability seem to be satisfied in our case (at first glance, it looks like they do). However, I really don't know what those concepts are (I wish I'd know more cryptography than I do now :( ). I will take a look at these links, but, is there any short comment you can give about it? thanks! (btw, I think your answer has a typo: shouldn't it be $r_1$ in both appearances in the right side? the same with the "encryptions" part). $\endgroup$
    – Daniel
    Commented Jul 9, 2016 at 0:39
  • $\begingroup$ For the first 2, replacing the right-entry r$_0$s with r$_1$s would give a trivially equivalent condition. ​ For the "encryptions" part, correctness explicitly requires that the result of replacing r$_0$ with r$_1$ most definitely not provide confidentiality against the private key holder. ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Jul 9, 2016 at 0:49

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.