Card-based Cryptography with Dihedral Symmetry

It is known that secure computation can be done by using a deck of physical cards. This area is called card-based cryptography. Shinagawa et al. (in: Provable security—9th international conference, ProvSec 2015, Kanazawa, Japan, 2015) proposed regular n-sided polygon cards that enable to compute functions over Z/nZ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {Z}}/n{\mathbb {Z}}$$\end{document}. In particular, they designed efficient protocols for linear functions (e.g. addition and constant multiplication) over Z/nZ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {Z}}/n{\mathbb {Z}}$$\end{document}. Here, efficiency is measured by the number of cards used in the protocol. In this paper, we propose a new type of cards, dihedral cards, as a natural generalization of regular polygon cards. Based on them, we construct efficient protocols for various interesting functions such as carry of addition, equality, and greater-than, whose efficient construction has not been known before. Beside this, we introduce a new protocol framework that captures a wide class of card types including binary cards, regular polygon cards, dihedral cards, and so on.