Zero-knowledge authenticated order queries and order statistics on a list

Abstract

An order query takes as input a set of elements from a list (ordered sequence) L, and asks for this set to be ordered using the total order induced by L. We introduce two formal models for answering order queries on a list in a verifiable and private manner. Our first model, called zero-knowledge list (ZKL), generalizes the standard twoparty model of membership queries on a set to order queries on a list in zero-knowledge. We present a construction of ZKL based on zeroknowledge sets and a homomorphic integer commitment. Our second model, privacy-preserving authenticated list (PPAL), extends authenticated data structures by adding a zero-knowledge privacy requirement. This is a three-party mo..