Lattice-based Multi-signature with Linear Homomorphism
Rakyong Choi, Kwangjo Kim · 2016
This paper extends the lattice-based linearly homomorphic signature to have multiple signers with the security proof. In our construction, we assume that there are one trusted dealer and either single signer or multiple signers for a message. The dealer pre-shares the message vector v during the set-up phase and issues a pre-shared vector vi to each signer. Then, from partial signatures i of vi signed by each signer, one obtains a valid signature of v by combining all partial signatures i of vi. We use well-known lattice-based algorithms like trapdoor generation algorithm and extracting basis algorithm to distribute dierent secret keys to each signer. Our signature holds multi-unforgeability and weakly context hiding property and is shown to be provably secure in the random oracle model under k-Small Integer Solution problem assuming the soundness of Boneh and Freeman's signature.