A $((k,n))$ quantum threshold secret sharing (QTS) scheme is a quantum cryptographic protocol for sharing a quantum secret among $n$ parties such that the secret can be recovered by any $k$ or more parties while $k-1$ or fewer parties have no information about the secret. Despite extensive research on these schemes, there has been very little study on optimizing the quantum communication cost during recovery. Recently, we initiated the study of communication efficient quantum threshold secret sharing (CE-QTS) schemes. These schemes reduce the communication complexity in QTS schemes by accessing $d>k$ parties for recovery; here $d$ is fixed ahead of encoding the secret. In contrast to the standard QTS schemes which require $k$ qudits for recovering each qudit in the secret, these schemes have a lower communication cost of $\frac {d}{d-k+1}$ . In this paper, we further develop the theory of communication efficient quantum threshold schemes. Here, we propose universal CE-QTS schemes which reduce the communication cost for all $d>k$ simultaneously. We provide a framework based on ramp quantum secret sharing to construct CE-QTS and universal CE-QTS schemes. We give another construction for universal CE-QTS schemes based on Staircase codes. We derived a lower bound on communication complexity and show that our constructions are optimal. Finally, an information theoretic model is developed to analyse CE-QTS schemes and the lower bound on communication complexity is proved again using this model.A$((k,n))$quantum threshold secret sharing (QTS) scheme is a quantum cryptographic protocol for sharing a quantum secret among$n$parties such that the secret can be recovered by any$k$or more parties while$k-1$or fewer parties have no information about the secret. Despite extensive research on these schemes, there has been very little study on optimizing the quantum communication cost during recovery. Recently, we initiated the study of communication efficient quantum threshold secret sharing (CE-QTS) schemes. These schemes reduce the communication complexity in QTS schemes by accessing$d>k$parties for recovery; here$d$is fixed ahead of encoding the secret. In contrast to the standard QTS schemes which require$k$qudits for recovering each qudit in the secret, these schemes have a lower communication cost of$\frac {d}{d-k+1}$. In this paper, we further develop the theory of communication efficient quantum threshold schemes. Here, we propose universal CE-QTS schemes which reduce the communication cost for all$d>k$simultaneously. We provide a framework based on ramp quantum secret sharing to construct CE-QTS and universal CE-QTS schemes. We give another construction for universal CE-QTS schemes based on Staircase codes. We derived a lower bound on communication complexity and show that our constructions are optimal. Finally, an information theoretic model is developed to analyse CE-QTS schemes and the lower bound on communication complexity is proved again using this model.

arXiv:2101.12419IEEE Transactions on Information TheoryJan 7, 202240 citations

Complexity Theory

Jack D. Hidary

Springer eBooksJan 1, 20192 citations

A new non-entangled quantum secret sharing protocol among different nodes in further quantum networks

Si-Jia Fu, Kejia Zhang, Long Zhang +1 more

As an important branch of quantum secure multi-party computation, quantum secret sharing (QSS) can distribute secret information among dishonest network nodes without revealing the secrets. In this study, a new four-party QSS protocol based on locally indistinguishable orthogonal product (LIOP) states is first proposed for quantum network communication. Then, the general multiparty QSS model based on LIOP states will be expanded. Combined with the property of LIOP states and obfuscating operation, the source node can send the secrets to different destination nodes in the quantum network. Accordingly, it is proven that the destination nodes have to work together to recover the shared secrets against some existing attacks. Furthermore, no entangled resources and complicated operations are required in the presented protocol. We hope the results could make positive effects to the development of quantum secure communication in the future.As an important branch of quantum secure multi-party computation, quantum secret sharing (QSS) can distribute secret information among dishonest network nodes without revealing the secrets. In this study, a new four-party QSS protocol based on locally indistinguishable orthogonal product (LIOP) states is first proposed for quantum network communication. Then, the general multiparty QSS model based on LIOP states will be expanded. Combined with the property of LIOP states and obfuscating operation, the source node can send the secrets to different destination nodes in the quantum network. Accordingly, it is proven that the destination nodes have to work together to recover the shared secrets against some existing attacks. Furthermore, no entangled resources and complicated operations are required in the presented protocol. We hope the results could make positive effects to the development of quantum secure communication in the future.

Frontiers in PhysicsOct 24, 20224 citations

Spectral Approach to the Communication Complexity of Multi-Party Key Agreement

Geoffroy Caillat-Grenier, Andrei Romashchenko

We propose a linear algebraic method, rooted in the spectral properties of graphs, that can be used to prove lower bounds in communication complexity. Our proof technique effectively marries spectral bounds with information-theoretic inequalities. The key insight is the observation that, in specific settings, even when data sets $X$ and $Y$ are closely correlated and have high mutual information, the owner of $X$ cannot convey a reasonably short message that maintains substantial mutual information with $Y$ . In essence, from the perspective of the owner of $Y$ , any sufficiently brief message $m=m(X)$ would appear nearly indistinguishable from a random bit sequence. We employ this argument in several problems of communication complexity. Our main result concerns cryptographic protocols. We establish a lower bound for communication complexity of multi-party secret key agreement with unconditional, i.e., information-theoretic security. Specifically, for one-round protocols (simultaneous messages model) of secret key agreement with three participants we obtain an asymptotically tight lower bound. This bound implies optimality of the previously known omniscience communication protocol (this result applies to a non-interactive secret key agreement with three parties and input data sets with an arbitrary symmetric information profile). We consider communication problems in one-shot scenarios when the parties' inputs are not produced by any i.i.d. sources, and there are no ergodicity assumptions on the input data. In this setting, we found it natural to present our results using the framework of Kolmogorov complexity.We propose a linear algebraic method, rooted in the spectral properties of graphs, that can be used to prove lower bounds in communication complexity. Our proof technique effectively marries spectral bounds with information-theoretic inequalities. The key insight is the observation that, in specific settings, even when data sets $X$ and $Y$ are closely correlated and have high mutual information, the owner of $X$ cannot convey a reasonably short message that maintains substantial mutual information with $Y$. In essence, from the perspective of the owner of $Y$, any sufficiently brief message $m=m(X)$ would appear nearly indistinguishable from a random bit sequence. We employ this argument in several problems of communication complexity. Our main result concerns cryptographic protocols. We establish a lower bound for communication complexity of multi-party secret key agreement with unconditional, i.e., information-theoretic security. Specifically, for one-round protocols (simultaneous messages model) of secret key agreement with three participants we obtain an asymptotically tight lower bound. This bound implies optimality of the previously known omniscience communication protocol (this result applies to a non-interactive secret key agreement with three parties and input data sets with an arbitrary symmetric information profile). We consider communication problems in one-shot scenarios when the parties' inputs are not produced by any i.i.d. sources, and there are no ergodicity assumptions on the input data. In this setting, we found it natural to present our results using the framework of Kolmogorov complexity.

arXiv:2305.01355Leibniz international proceedings in informaticsMay 2, 20230 citations

Information indistinguishability and nonlocality

Cássio Sozinho Amorim

Bulletin of the American Physical SocietyMar 8, 20180 citations

((k,n))

quantum threshold secret sharing (QTS) scheme is a quantum cryptographic protocol for sharing a quantum secret among

n

parties such that the secret can be recovered by any

k

or more parties while

k-1

or fewer parties have no information about the secret. Despite extensive research on these schemes, there has been very little study on optimizing the quantum communication cost during recovery. Recently, we initiated the study of communication efficient quantum threshold secret sharing (CE-QTS) schemes. These schemes reduce the communication complexity in QTS schemes by accessing

d>k

parties for recovery; here

d

is fixed ahead of encoding the secret. In contrast to the standard QTS schemes which require

k

qudits for recovering each qudit in the secret, these schemes have a lower communication cost of

\frac {d}{d-k+1}

. In this paper, we further develop the theory of communication efficient quantum threshold schemes. Here, we propose universal CE-QTS schemes which reduce the communication cost for all

d>k

simultaneously. We provide a framework based on ramp quantum secret sharing to construct CE-QTS and universal CE-QTS schemes. We give another construction for universal CE-QTS schemes based on Staircase codes. We derived a lower bound on communication complexity and show that our constructions are optimal. Finally, an information theoretic model is developed to analyse CE-QTS schemes and the lower bound on communication complexity is proved again using this model.

X

and

Y

are closely correlated and have high mutual information, the owner of

X

cannot convey a reasonably short message that maintains substantial mutual information with

Y

. In essence, from the perspective of the owner of

Y

, any sufficiently brief message

m=m(X)

would appear nearly indistinguishable from a random bit sequence. We employ this argument in several problems of communication complexity. Our main result concerns cryptographic protocols. We establish a lower bound for communication complexity of multi-party secret key agreement with unconditional, i.e., information-theoretic security. Specifically, for one-round protocols (simultaneous messages model) of secret key agreement with three participants we obtain an asymptotically tight lower bound. This bound implies optimality of the previously known omniscience communication protocol (this result applies to a non-interactive secret key agreement with three parties and input data sets with an arbitrary symmetric information profile). We consider communication problems in one-shot scenarios when the parties' inputs are not produced by any i.i.d. sources, and there are no ergodicity assumptions on the input data. In this setting, we found it natural to present our results using the framework of Kolmogorov complexity.