How to Solve Millionaires’ Problem with Two Kinds of Cards
Autor: | Yuto Misawa, Kazuo Ohta, Takeshi Nakai, Mitsugu Iwamoto, Yuuki Tokushige |
---|---|
Rok vydání: | 2021 |
Předmět: |
021110 strategic
defence & security studies Theoretical computer science Shuffling Computer Networks and Communications Computer science business.industry Computation 0211 other engineering and technologies Cryptography 02 engineering and technology Theoretical Computer Science Permutation Hardware and Architecture 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Fork (file system) business Bitwise operation Protocol (object-oriented programming) Software Randomness |
Zdroj: | New Generation Computing. 39:73-96 |
ISSN: | 1882-7055 0288-3635 |
Popis: | Card-based cryptography, introduced by den Boer aims to realize multiparty computation (MPC) by using physical cards. We propose several efficient card-based protocols for the millionaires’ problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in most of existing card-based cryptography. Shuffle is a useful randomization technique by exploiting the property of card shuffling, but it requires a strong assumption from the viewpoint of arithmetic MPC because shuffle assumes that public randomization is possible. On the other hand, private randomness can be used in PPs, which enables us to design card-based protocols taking ideas of arithmetic MPCs into account. Actually, we show that Yao’s millionaires’ protocol can be easily transformed into a card-based protocol by using PPs, which is not straightforward by using shuffles because Yao’s protocol uses private randomness. Furthermore, we propose entirely novel and efficient card-based millionaire protocols based on PPs by securely updating bitwise comparisons between two numbers, which unveil a power of PPs. As another interest of these protocols, we point out they have a deep connection to the well-known logical puzzle known as “The fork in the road.” |
Databáze: | OpenAIRE |
Externí odkaz: |