Secure multi-party computation (MPC) allows participating parties to jointly compute a function over their inputs while keeping them private. In particular, MPC based on additive secret sharing has been widely studied as a tool to obtain efficient protocols secure against a dishonest majority, including the important two-party case. In this paper, we propose a two-party protocol for an exponentiation functionality based on an additive secret sharing scheme. Our proposed protocol aims to securely compute a public base exponentiation ax mod p for an odd prime p, where the exponent x ∈ ℤp is a (shared) secret and the base a ∈ ℤp is public. Our protocol is based on a new simple but efficient approach involving quotient transfer that allows the parties to perform the most expensive part of the computation locally, but requires the base a ∈ ℤp to be a quadratic residue. To address scenarios where the base does not fulfill this, we combine our exponentiation protocol with a new efficient modulus conversion protocol which might be of independent interest. Even taking into account a potential modulus conversion, our exponentiation protocol only requires 3 rounds and 4 invocations of multiplication.Secure multi-party computation (MPC) allows participating parties to jointly compute a function over their inputs while keeping them private. In particular, MPC based on additive secret sharing has been widely studied as a tool to obtain efficient protocols secure against a dishonest majority, including the important two-party case. In this paper, we propose a two-party protocol for an exponentiation functionality based on an additive secret sharing scheme. Our proposed protocol aims to securely compute a public base exponentiation ax mod p for an odd prime p, where the exponent x ∈ ℤp is a (shared) secret and the base a ∈ ℤp is public. Our protocol is based on a new simple but efficient approach involving quotient transfer that allows the parties to perform the most expensive part of the computation locally, but requires the base a ∈ ℤp to be a quadratic residue. To address scenarios where the base does not fulfill this, we combine our exponentiation protocol with a new efficient modulus conversion protocol which might be of independent interest. Even taking into account a potential modulus conversion, our exponentiation protocol only requires 3 rounds and 4 invocations of multiplication.

IEICE Transactions on Information and SystemsAug 20, 20250 citations

Efficient Covert Two-Party Computation

Stanisław Jarecki

Lecture notes in computer scienceJan 1, 201813 citations

Perfect state transfer on quotient graphs

Rachel Elizabeth Bachman, Eric Fredette, Jessica Fuller +4 more

We prove new results on perfect state transfer of quantum walks on quotient graphs. Since a graph G has perfect state transfer if and only if its quotient G/\pi, under any equitable partition \pi, has perfect state transfer, we exhibit graphs with perfect state transfer between two vertices but which lack automorphism swapping them. This answers a question of Godsil (Discrete Mathematics 312(1):129-147, 2011). We also show that the Cartesian product of quotient graphs \Box_{k} G_{k}/\pi_{k} is isomorphic to the quotient graph \Box_{k} G_{k}/\pi, for some equitable partition \pi. This provides an algebraic description of a construction due to Feder (Physical Review Letters 97, 180502, 2006) which is based on many-boson quantum walk.We prove new results on perfect state transfer of quantum walks on quotient graphs. Since a graph G has perfect state transfer if and only if its quotient G/\pi, under any equitable partition \pi, has perfect state transfer, we exhibit graphs with perfect state transfer between two vertices but which lack automorphism swapping them. This answers a question of Godsil (Discrete Mathematics 312(1):129-147, 2011). We also show that the Cartesian product of quotient graphs \Box_{k} G_{k}/\pi_{k} is isomorphic to the quotient graph \Box_{k} G_{k}/\pi, for some equitable partition \pi. This provides an algebraic description of a construction due to Feder (Physical Review Letters 97, 180502, 2006) which is based on many-boson quantum walk.

arXiv:1108.0339Quantum Information and ComputationMar 1, 201230 citations

Classical vs. quantum communication in XOR games

Marius Junge, Carlos Palazuelos, Ignacio Villanueva

In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games $G$ when Alice and Bob are allowed to use a limited amount of one-way classical communication $ω_{o.w.-c}(G)$ (resp. one-way quantum communication $ω_{o.w.-c}^*(G)$ ), where $c$ denotes the number of bits (resp. qubits). The key quantity here is the quotient $ω_{o.w.-c}^*(G)/ω_{o.w.-c}(G)$ . We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient $ω_{o.w.-c}^*(G)/ω_{o.w.-2c}(G)$ is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information $c$ . Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games $G$ when Alice and Bob are allowed to use a limited amount of one-way classical communication $ω_{o.w.-c}(G)$ (resp. one-way quantum communication $ω_{o.w.-c}^*(G)$), where $c$ denotes the number of bits (resp. qubits). The key quantity here is the quotient $ω_{o.w.-c}^*(G)/ω_{o.w.-c}(G)$. We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient $ω_{o.w.-c}^*(G)/ω_{o.w.-2c}(G)$ is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information $c$. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.

arXiv:1706.02653Jun 8, 20170 citations

Efficient Three-Party Computation from Cut-and-Choose

Seung Geol Choi, Jonathan I. Katz, Alex J. Malozemoff +1 more

Lecture notes in computer scienceJan 1, 201436 citations

In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games

G

when Alice and Bob are allowed to use a limited amount of one-way classical communication

ω_{o.w.-c}(G)

(resp. one-way quantum communication

ω_{o.w.-c}^*(G)

), where

c

denotes the number of bits (resp. qubits). The key quantity here is the quotient

ω_{o.w.-c}^*(G)/ω_{o.w.-c}(G)

. We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient

ω_{o.w.-c}^*(G)/ω_{o.w.-2c}(G)

is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information

c

. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.