Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols /

Date: received 25 Apr 2006, last revised 19 May 2006

Contact author: msilaghi at fit edu

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20060519:210918 (All versions of this report)

Discussion forum: Show discussion | Start new discussion