A note on the (Im)possibility of using obfuscators to transform private-key encryption into public-key encryption

Satoshi Hada, Kouichi Sakurai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)


Transforming private-key encryption schemes into public-key encryption schemes is an interesting application of program obfuscation. The idea is that, given a private-key encryption scheme, an obfuscation of an encryption program with a private key embedded is used as a public key and the private key is used for decryption as it is. The security of the resulting public-key encryption scheme would be ensured because obfuscation is unintelligible and the public key is expected to leak no information on the private key. This paper investigates the possibility of general-purpose obfuscators for such a transformation, i.e., obfuscators that can transform an arbitrary private-key encryption scheme into a secure public-key encryption scheme. Barak et al. have shown a negative result, which says that there is a deterministic private-key encryption scheme that is unobfuscatable in the sense that, given any encryption program with a private key embedded, one can efficiently compute the private key. However, it is an open problem whether their result extends to probabilistic encryption schemes, where we should consider a relaxed notion of obfuscators, i.e., sampling obfuscators. Programs obfuscated by sampling obfuscators do not necessarily compute the same function as the original program, but produce the same distribution as the original program. In this paper, we show that there is a probabilistic private-key encryption scheme that can not be transformed into a secure public-key encryption scheme by sampling obfuscators which have a special property regarding input-output dependency of encryption programs. Our intention is not to claim that the required special property is reasonable. Rather, we claim that general-purpose obfuscators for the transformation, if they exist, must be a sampling obfuscator which does NOT have the special property.

Original languageEnglish
Title of host publicationAdvances in Information and Computer Security - Second International Workshop on Security, IWSEC 2007, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540756507
Publication statusPublished - 2007
Event2nd International Workshop on Security, IWSEC 2007 - Nara, Japan
Duration: Oct 29 2007Oct 31 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4752 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd International Workshop on Security, IWSEC 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A note on the (Im)possibility of using obfuscators to transform private-key encryption into public-key encryption'. Together they form a unique fingerprint.

Cite this