Lattice-based Threshold Signature with Message Block Sharing
Rakyong Choi, Kwangjo Kim · 2014
In this paper, we introduce an interesting tool to construct the k-out-of-N threshold signature schemes, which we call as message block sharing. To achieve our goal, we rst separate an original message with large size into multiple message blocks with random size. Then, we give a partial number of message blocks to N signers with combinatorial approach. We propose an example scheme with our tool by implementing this to the lattice-based group signature scheme by Gordon et al. in ASIACRYPT 2010. from the fact that their security is based on the worst-case hardness assumptions instead of average- case hardness assumptions and the lattice-based cryp- tography remains secure against quantum computers. From these advantages, the range of applications of lat- tices varies in many areas in cryptology recently. Separately, a digital signature scheme is a protocol that one party makes a signature for a message with the private signing key and the other party can verify the signature if he has the public verication key. But if we want to decrease the strength of the signer, the signature should be signed by several members in a group instead of one party. One example is a k-out-of- N threshold signature scheme, which is a protocol that approves any subset of k members among N members to produce a valid signature, but it is impossible to generate a valid signature in case fewer thank members are involved in the protocol. So, any conspiracy of less than k corrupted members cannot produce a valid signature. In the current technology with quantum computer and big data, one interesting issue is how to apply the cryptographic primitive to be robust to quantum com- puter attack and the other is how we distribute the power of the signer so that we can control the message with huge size more carefully. Indeed, our lattice-based threshold signature scheme satises both conditions.