tag:blogger.com,1999:blog-3722233.post116292941029307315..comments2023-03-27T02:45:06.501-05:00Comments on Computational Complexity: PIR UpdateLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-1163048832424056392006-11-08T23:07:00.000-06:002006-11-08T23:07:00.000-06:00The main interest in having additional servers in ...The main interest in having additional servers in the PIR definition was reduced complexity -- not greater reliability. Even with the new Mersenne prime results, all of the solutions with constant numbers of databases are very expensive compared with the non-private solution of querying a single bit. <BR/><BR/>An 'any 2 of 3' requirement makes 3 servers at least as expensive as 2 servers, which seems to be a step in the wrong direction for complexity.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1162999397347456252006-11-08T09:23:00.000-06:002006-11-08T09:23:00.000-06:00Anonymous: That's the case for PIR which only guar...Anonymous: That's the case for PIR which only guarantees anonymity if only one of the 3 databases collude, however there are schemes which are secure if two of the 3 databases collude. In practice, you'd really like to use a scheme where only a small number of a large number of databases have to be trusted.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1162961897281162582006-11-07T22:58:00.000-06:002006-11-07T22:58:00.000-06:00Bram, I think you are confused: if one database ge...Bram, I think you are confused: if one database gets two of the three requests, then the user's anonymity may no longer be guaranteed.<BR/><BR/>PS: In practice, you would never model a database as an n-bit string...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1162961207980756182006-11-07T22:46:00.000-06:002006-11-07T22:46:00.000-06:00You don't make clear what m of n security each of ...You don't make clear what m of n security each of these is. Isn't the new mersenne prime related technique only for 2 of n? Does its construction fit the model of the 2-DB lower bound? Trivially, if 3 of 3 can be done with some efficiency then 2 of 2 can be done with the same efficiency simply by giving two of the three requests to the same server.<BR/><BR/>In actual practice, of course, you would never use a mersenne prime greater than 31, and possibly not even greater than 7.Anonymousnoreply@blogger.com