TY - GEN
T1 - Secret Key Amplification from Uniformly Leaked Key Exchange Complete Graph
AU - Sasaki, Tatsuya
AU - Agbor, Bateh Mathias
AU - Masuda, Shingo
AU - Hayashi, Yu-Ichi
AU - Mizuki, Takaaki
AU - Sone, Hideaki
N1 - Funding Information:
Acknowledgement. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. We thank Mr. Shigehiro Matsuda for his valuable discussions. This work was supported by JSPS KAKENHI Grant Number 15K11983.
Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.
PY - 2018
Y1 - 2018
N2 - We assume that every pair of n players has shared a one-bit key in advance, and that each key has been completely exposed to an eavesdropper, Eve, independently with a fixed probability p (and, thus, is perfectly secure with a probability of 1-p). Using these pre-shared, possibly leaked keys, we want two designated players to share a common one-bit secret key in cooperation with other players so that Eve’s knowledge about the generated secret key will be as small as possible. The existing protocol, called the st-flow protocol, achieves this, but the specific probability that Eve knows the generated secret key is unknown. In this study, we answer this problem by showing the exact leak probability as a polynomial in p for any number n of players.
AB - We assume that every pair of n players has shared a one-bit key in advance, and that each key has been completely exposed to an eavesdropper, Eve, independently with a fixed probability p (and, thus, is perfectly secure with a probability of 1-p). Using these pre-shared, possibly leaked keys, we want two designated players to share a common one-bit secret key in cooperation with other players so that Eve’s knowledge about the generated secret key will be as small as possible. The existing protocol, called the st-flow protocol, achieves this, but the specific probability that Eve knows the generated secret key is unknown. In this study, we answer this problem by showing the exact leak probability as a polynomial in p for any number n of players.
KW - Key agreement protocol
KW - Key exchange graph
KW - Network reliability problem
KW - Privacy amplification
KW - st-numbering
UR - http://www.scopus.com/inward/record.url?scp=85043306250&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85043306250&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-75172-6_3
DO - 10.1007/978-3-319-75172-6_3
M3 - Conference contribution
AN - SCOPUS:85043306250
SN - 9783319751719
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 20
EP - 31
BT - WALCOM
A2 - Rahman, M. Sohel
A2 - Sung, Wing-Kin
A2 - Uehara, Ryuhei
PB - Springer Verlag
T2 - 12th International Conference and Workshop on Algorithms and Computation, WALCOM 2018
Y2 - 3 March 2018 through 5 March 2018
ER -