Research On Several Key Technology Of Private Information Retrieval

Secure Multi-party Computation is research on the problem where two or more parties want to jointly to compute a task, in the process of computing, it must ensure the privacy of participants, and at last each of the participants know the output of the task. The Problem was first proposed by A.C.Yao in1982, and in1987, O.Goldreich and S.Micali proposed the protocol of secure multi-party computation which is cryptography security, this protocol can compute any function. But O. Goldreich pointed out in1988that using general protocol to solve specific problem in secure multi-party computation can not reach ideal effect. To these specific problems we should design corresponding security protocol, which can solve problem efficiently. Under the pushing of this thought and the further research of scholars, secure multi-party computation derivative out a lot of research direction, such as: privacy-preservation computational geometry, private information retrieval, electronic voting, electronic sale, statistical analysis and so on. All these promote secure multi-party computation can solve more realistic problem. Private information retrieval is an important and realistic problem, which has significant application in military field, commercial field and so on.The problem of Private information retrieval(PIR) is refers to that the server Bob has a database which has n data d1,d2,…, dn, client Alice want to retrieve the data of d, from server’s n data, while keeping the value of i private to Bob. This is the first PIR, later it develops into symmetrically-private information retrieval (SPIR) which also protects the privacy of server’s data as well as client’s privacy in PIR scheme, and it means that Alice can not get any other information except for di. There are many private information retrieval schemes, according to privacy requirements are divided into three types:First, information-theoretic private information retrieval protocol, it is absolutely safe, this PIR provide a strong safety concept, it can guarantee the user’s privacy is perfectly protected under the assumption that the attacker’s computing power is unlimited. Second, computationally private information retrieval, it is relatively safe, this PIR does not have strong safety concept, in this environment, and the attacker’s computing power is limited in polynomial time. It usually based on calculation difficult problem in cryptology, and had practical significance. Third, private information retrieval protocol based on safety hardware, these protocol has some safety hardware as auxiliary facilities, which can provide safety environment, processor and safety storage space with complete equipment, so it has high efficiency. Moreover, we can divide private information retrieval into malicious model private information retrieval and semi-honest model private information retrieval, according to participants is honest whether or not. Private information retrieval is an important branch of the secure multi-party computation, and it has widely application in real life, such as oblivious transfer, anonymous authentication, locally decodable codes, and secure query scheme and so on.This paper is mainly research on the computationally secure private information retrieval under the semi-honest model. Specifically focuses on the following two aspects:Firstly, we introduce several typical private information retrieval scheme based on keyword, and then put forward some questions with then, at last we give a summary.Secondly, privacy-preserving fuzzy keyword search in cloud computing. Most of the previous private information retrieval scheme is search through physical address instead of keyword search. We further research on private information retrieval which support keyword search. As Cloud Computing becomes prevalent, Cloud service has become more and more popular, but cloud security is still the first important factor that user concerned. In this paper, to solve the problem of searching in encrypted database, we propose a new method, which using locality-sensitive hashing and Chinese remainder theorem to implement fuzzy keyword search in encrypted database safely, and utilizing bloom filter to authenticate the legality of users. Theoretical analysis shows that the method is correct and safe. In this paper, for the first time we resolve the problem of user’s authentication while maintaining computational complexity and communication complexity, especially its pre-storage space is smaller than existing program. The scheme can applied to many fields, such as medicine, patent and business, etc.Thirdly, privacy-preserving scheme for calculating intersect-area of two ellipses. We put symmetrically private information retrieval simplified, in fact it is the problem that all participator’s privacy are protected, and at the same time it get the desired result. After us expending this concept, we concern privacy-preservation computational geometry in secure multi-party computation. Privacy-preservation computational geometry is one of research field of secure multi-party computation. Attalla and Due had do some work in privacy-preserving geometric computations. They mentioned many specific problems of geometric computations, and proposed a research framework in this field. We proposed the problem of calculating intersect-area of two ellipses privacy-preserving; it has a strong application background. To this problem, by using Monte Carlo and oblivious transfer, we proposed two schemes to solve it. And the correctness, security and complexity are analyzed. The proposed scheme can be applied in many fields, such as military field and commerce field.