As the Internet becomes more and more indispensable in our society, the issue of personal information handling between consumers and businesses is recognized as a critical one in building a secure and efficient social system on the Internet. In handling personal information, consumers generally want their privacy to be protected, but businesses need reliable personal information and an access channel to consumers for e-commerce. Clearly these demands must be satisfied to establish sound e-commerce. However, most existing approaches for personal information handling can not satisfy all of them. This paper proposes the idea of the Personal Information Market (PIM), which can satisfy all of these demands. A protocol that supports the PIM and an implementation in the form of personalized advertisement service are described.