An efficient way to access an array at a secret index

Timothy Atkinson; Marius C.  Silaghi

Paper 2006/157

An efficient way to access an array at a secret index

Timothy Atkinson and Marius C. Silaghi

Abstract

We propose cryptographic primitives for reading and assigning the (shared) secret found at a secret index in a vector of secrets. The problem can also be solved in constant round with existing general techniques based on arithmetic circuits and the ``equality test'' in [Damgard.et.al 05]. However the proposed technique requires to exchange less bits. The proposed primitives require a number of rounds that is independent of the size N of the vector, and only depends (linearly) on the number t of computing servers. A previously known primitive for reading a vector at a secret index works only for 2-party computations. Our primitives work for any number of computing participants/servers. The proposed techniques are secure against passive attackers, and zero knowledge proofs are provided to show that exactly one index of the array is read/written. The techniques work both with multiparty computations based on secret sharing and with multiparty computations based on threshold homomorphic encryption.

Metadata

Available format(s): PDF PS
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): msilaghi @ fit edu
History: 2006-05-19: last of 2 revisions; 2006-05-03: received; See all versions
Short URL: https://ia.cr/2006/157
License: CC BY

BibTeX

@misc{cryptoeprint:2006/157,
      author = {Timothy Atkinson and Marius C.  Silaghi},
      title = {An efficient way to access an array at a secret index},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/157},
      year = {2006},
      url = {https://eprint.iacr.org/2006/157}
}