TY - GEN
T1 - Necessary and sufficient numbers of cards for securely computing two-bit output functions
AU - Francis, Danny
AU - Aljunid, Syarifah Ruqayyah
AU - Nishida, Takuya
AU - Hayashi, Yu Ichi
AU - Mizuki, Takaaki
AU - Sone, Hideaki
N1 - Funding Information:
We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. This work was supported by JSPS KAKENHI Grant Number 26330001.
Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - In 2015, Koch et al. proposed a five-card finite-runtime committed protocol to compute securely the AND function, showing that their protocol was optimal: there is no protocol computing the AND function with four cards in finite-runtime fashion and committed format. Thus, necessary and sufficient numbers of cards for computing single-bit output functions are known. However, as for two-bit output functions, such an exact characterization is unknown. This paper gives a six-card (or less) protocol for each of all two-bit output functions and proves that our finite-runtime committed protocols are optimal by providing a lower bound. In other words, we give the necessary and sufficient number of cards for any two-bit output function to be computed by a finite-runtime committed protocol. Our lower bound can also be applied to any function which outputs more than two bits.
AB - In 2015, Koch et al. proposed a five-card finite-runtime committed protocol to compute securely the AND function, showing that their protocol was optimal: there is no protocol computing the AND function with four cards in finite-runtime fashion and committed format. Thus, necessary and sufficient numbers of cards for computing single-bit output functions are known. However, as for two-bit output functions, such an exact characterization is unknown. This paper gives a six-card (or less) protocol for each of all two-bit output functions and proves that our finite-runtime committed protocols are optimal by providing a lower bound. In other words, we give the necessary and sufficient number of cards for any two-bit output function to be computed by a finite-runtime committed protocol. Our lower bound can also be applied to any function which outputs more than two bits.
UR - http://www.scopus.com/inward/record.url?scp=85026777593&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85026777593&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-61273-7_10
DO - 10.1007/978-3-319-61273-7_10
M3 - Conference contribution
AN - SCOPUS:85026777593
SN - 9783319612720
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 193
EP - 211
BT - Paradigms in Cryptology – Mycrypt 2016
A2 - Phan, Raphael C.-W.
A2 - Yung, Moti
PB - Springer Verlag
T2 - 2nd International Conference on Cryptology and Malicious Security, Mycrypt 2016
Y2 - 1 December 2016 through 2 December 2016
ER -