A gachapon ‘blind box’ for private information retrieval
Gachapon is a capsule toy, widely popular in Japan and elsewhere, that is dispensed through a vending machine equipped with a roulette mechanism. The mechanism enhances the fun, since it makes receiving an item random and unpredictable for customers. Standing before a gachapon machine that shows a variety of possible toys, a customer has no idea which toy actually will be dispensed. Because gachapons are typically packaged in identical opaque 3-inch spheres, they are also called “blind boxes.” The covers of blind boxes are identical in every way—nobody, including the manufacturer, knows what exactly is inside until the customer opens the packaging.
The gachapon also has a digital form; the concept is being adapted as a random-type item for online games and 3D printing. Now Professor Sennur Ulukus (ECE/ISR) and her Ph.D. student Zhusheng Wang (ECE) are considering the gachapon’s usefulness for Random Symmetric Private Information Retrieval (RSPIR). Their new paper, Digital Blind Box: Random Symmetric Private Information Retrieval, introduces the idea.
In canonical Private Information Retrieval (PIR), a user downloads a message out of K messages from N non-colluding and replicated databases in such a way that no database can know which message the user has downloaded (user privacy). In Symmetric Private Information Retrieval (SPIR), the privacy is symmetric, in that, not only that the databases cannot know which message the user has downloaded, the user itself cannot learn anything further than the particular message it has downloaded (database privacy).
In RSPIR, different from SPIR, the user does not have an input to the databases. That is, the user does not send any queries to the databases. The user does not pick a speciﬁc message to download and instead is content with any one of the random messages received. In RSPIR, databases need to send symbols to the user in such a way that the user is guaranteed to download a message correctly (random reliability), the databases do not know which message the user has received (user privacy), and the user does not learn anything further than the one message it has received (database privacy).
Published June 24, 2022