Card-Based Secure Sorting Protocols Based on the Sorting Networks

EasyChair Preprint 15171

Abstract

Card-based cryptography enables us to realize secure computation using physical cards with simple manual operations. The efficiency of a card-based protocol is evaluated by the number of shuffles and cards. The Haga et al. (IWSEC2022) is the only work to address card-based secure sorting. They proposed two protocols: a Las Vegas protocol and a finite-runtime protocol. The finite-runtime means that the number of shuffles is deterministic. In this paper, we propose a general converter that transforms an arbitrary sorting network into a finite-runtime card-based sorting protocol. The converter uses Haga et al.'s finite-runtime protocol for n=2 as its building block. Furthermore, we show card-based sorting protocol obtained by applying the converter to the AKS sorts. As a result, we improve the number of additional cards from O(n^2+m) to O(n+m) compared to Haga et al. On the other hand, the number of shuffles increases from O(nm) to O(nmlog n).

Keyphrases: Card-based cryptography, Secure Sorting Protocol, sorting network

@booklet{EasyChair:15171,
  author    = {Kota Kato and Takeshi Nakai and Koutarou Suzuki},
  title     = {Card-Based Secure Sorting Protocols Based on the Sorting Networks},
  howpublished = {EasyChair Preprint 15171},
  year      = {EasyChair, 2024}}