An Id-Based Multi Signature Scheme Using Interval Maps

The object of this presentation is to introduce a new multi signature scheme relying on a strong problem, not yet used in cryptography, associated to a family of interval maps on the unit interval. The new multi signature scheme can be Id-based without altering the computational characteristics. We introduce a particular family of interval maps. The mappings of this family will be iterated n times. To these mappings are associated a decisional problem and a computational problem, that are strong by cryptographic standards. Their parameters will be studied. The particular maps have a functional relation allowing the deduction of a single signer signature scheme. The scheme is shown to be solid if the interval maps are iterated a sufficient number of times. It also allows the deduction of a multi signature scheme without having to rely on bilinear maps. The multi signature scheme can be Id-based. A bijective transformation for transforming a bit string to a real number less than 1 is also given.