Private Outsourcing of Matrix Multiplication over Closed Semi-rings

Mikhail J. Atallah, Keith B Frikken, Shumiao Wang

2012

Abstract

Many protocols exist for a client to outsource the multiplication of matrices to a remote server without revealing to the server the input matrices or the resulting product, and such that the server does all of the super-linear work whereas the client does only work proportional to the size of the input matrices. These existing techniques hinge on the existence of additive and multiplicative inverses for the familiar matrix multiplication over the (+,∗) ring, and they fail when one (or both) of these inverses do not exist, as happens for many practically important algebraic structures (including closed semi-rings) when one or both of the two operations in the matrix multiplication is the “min” or “max” operation. Such matrix multiplications are very common in optimization. We give protocols for the cases of (+,min) multiplication, (min,max) multiplication, and of (min,+) multiplication; the last two cases are particularly important primitives in many combinatorial optimization problems.

Paper Citation

in Harvard Style

J. Atallah M., B Frikken K. and Wang S. (2012). Private Outsourcing of Matrix Multiplication over Closed Semi-rings . In Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2012) ISBN 978-989-8565-24-2, pages 136-144. DOI: 10.5220/0004054101360144

in Bibtex Style

@conference{secrypt12,
author={Mikhail J. Atallah and Keith B Frikken and Shumiao Wang},
title={Private Outsourcing of Matrix Multiplication over Closed Semi-rings},
booktitle={Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2012)},
year={2012},
pages={136-144},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004054101360144},
isbn={978-989-8565-24-2},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2012)
TI - Private Outsourcing of Matrix Multiplication over Closed Semi-rings
SN - 978-989-8565-24-2
AU - J. Atallah M.
AU - B Frikken K.
AU - Wang S.
PY - 2012
SP - 136
EP - 144
DO - 10.5220/0004054101360144