Paper 2016/997

Efficient Commitments and Zero-Knowledge Protocols from Ring-SIS with Applications to Lattice-based Threshold Cryptosystems

Carsten Baum and Ivan Damgård and Sabine Oechsner and Chris Peikert

Abstract

We present an additively homomorphic commitment scheme with hardness based on the Ring-SIS problem. Our construction is statistically hiding as well as computationally binding and allows to commit to a vector of ring elements at once. We show how to instantiate efficient zero-knowledge protocols that can be used to prove a number of relations among these commitments, and apply these in the context of lattice-based threshold cryptosystems: we give a generic transformation that can be used with certain (Ring-)LWE-based encryption schemes to make their algorithms actively secure. We show how this transformation can be used to implement distributed decryption with malicious security as well as maliciously secure threshold key generation in an efficient way.

Note: Improved version of our previous construction.