TY - GEN
T1 - An Expressive (Zero-Knowledge) Set Accumulator
AU - Zhang, Yupeng
AU - Katz, Jonathan
AU - Papamanthou, Charalampos
N1 - Funding Information:
This research was supported in part by an NSF award #1514261 and by a NIST grant.
Publisher Copyright:
© 2017 IEEE.
PY - 2017/6/28
Y1 - 2017/6/28
N2 - We present a new construction of an expressive set accumulator. Unlike existing cryptographic accumulators, ours provides succinct proofs for a large collection of operations over accumulated sets, including intersection, union, set difference, SUM, COUNT, MIN, MAX, and RANGE, as well as arbitrary nestings of the above. We also show how to extend our accumulator to be zero-knowledge. The security of our accumulator is based on extractability assumptions and other assumptions that hold in the generic group model. Our construction has asymptotically optimal verification complexity and proof size, constant update complexity, and public verifiability/updatability - namely, any client who knows the public key and the last accumulator value can verify the supported operations and update the accumulator. The expressiveness of our accumulator comes at the cost of quadratic prover time. However, we show that the cryptographic operations involved are cheap compared to those incurred by generic approaches (e.g., SNARKs) that are equally expressive: our prover runs faster for sets of up to 5 million items. Our accumulator serves as a powerful cryptographic tool with many applications. For example, it can be applied to efficiently support verification of a rich collection of SQL queries when used as a drop-in replacement in existing verifiable database systems (e.g., IntegriDB, CCS 2015).
AB - We present a new construction of an expressive set accumulator. Unlike existing cryptographic accumulators, ours provides succinct proofs for a large collection of operations over accumulated sets, including intersection, union, set difference, SUM, COUNT, MIN, MAX, and RANGE, as well as arbitrary nestings of the above. We also show how to extend our accumulator to be zero-knowledge. The security of our accumulator is based on extractability assumptions and other assumptions that hold in the generic group model. Our construction has asymptotically optimal verification complexity and proof size, constant update complexity, and public verifiability/updatability - namely, any client who knows the public key and the last accumulator value can verify the supported operations and update the accumulator. The expressiveness of our accumulator comes at the cost of quadratic prover time. However, we show that the cryptographic operations involved are cheap compared to those incurred by generic approaches (e.g., SNARKs) that are equally expressive: our prover runs faster for sets of up to 5 million items. Our accumulator serves as a powerful cryptographic tool with many applications. For example, it can be applied to efficiently support verification of a rich collection of SQL queries when used as a drop-in replacement in existing verifiable database systems (e.g., IntegriDB, CCS 2015).
KW - cryptographic accumulators
KW - verifiable set operations
KW - zero-knowledge accumulators
UR - http://www.scopus.com/inward/record.url?scp=85026647618&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85026647618&partnerID=8YFLogxK
U2 - 10.1109/EuroSP.2017.35
DO - 10.1109/EuroSP.2017.35
M3 - Conference contribution
AN - SCOPUS:85026647618
T3 - Proceedings - 2nd IEEE European Symposium on Security and Privacy, EuroS and P 2017
SP - 158
EP - 173
BT - Proceedings - 2nd IEEE European Symposium on Security and Privacy, EuroS and P 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2nd IEEE European Symposium on Security and Privacy, EuroS and P 2017
Y2 - 26 April 2017 through 28 April 2017
ER -