NTT, NICT and Karlsruhe Institute of Technology design highly secure and interoperable digital signature scheme

Various types of information are currently used over networks. Some contain privacy information or highly confidential information. For example, credit cards are used on online shopping sites. To protect such information and guarantee the security of networks, cryptographic applications which consist of various cryptographic building blocks are used. However, it is not necessarily possible to construct secure cryptographic applications by simply combining secure cryptographic building blocks. Moreover, it is not necessarily easy to combine cryptographic building blocks because their input-output formats are not compatible. Structure-preserving cryptography was invented to solve this issue. Structure-preserving cryptographic schemes preserve a group^*4 structure of inputs, and their outputs also have the group structure. Therefore, their input-output formats are compatible with those of many cryptographic building blocks. This property makes it possible to construct a simple combination of cryptographic building blocks and secure cryptographic applications (modular design). Structure-preserving cryptography has such interoperability. (Figure 1)

The main feature of the new structure-preserving signature scheme is that it has both interoperability and tight security. (Figure 2)

To construct efficient and secure cryptographic applications, efficient and secure cryptographic building blocks that enable modular design are essential. The new digital signature scheme has interoperability and enables modular design of cryptographic applications because it is a structure-preserving signature scheme. 

Moreover, the new structure-preserving signature scheme is tightly secure, which means that the number of users does not affect the security. The number of users affects the security of many cryptographic schemes. In such schemes, the size of a security parameter must be enlarged to maintain their security when the number of users increases. In tightly secure cryptographic schemes, there is no need to enlarge the size of a security parameter when the number of users increases. Therefore, the data size that cryptographic applications store and their computation cost are small. Tightly secure cryptographic building blocks are useful tools for constructing cryptographic applications and adequate for modular design. 

Only the partitioning technique, which partitions a set of bit strings according to a static strategy, is known for achieving tight security. This technique has been used to construct various tightly secure cryptographic schemes since it was proposed in 1997. However, the technique is not applicable to structure-preserving cryptography because data in such cryptography are group elements. In the new structure-preserving signature scheme, a new encoding method between bit strings and group elements was developed. However, it is impossible to partition a set of group elements by using the known static strategy. By considering the equivalence of some group elements as one-bit information, a new partitioning technique based on adaptive strategy was developed in this research (Figure 3). The group-element-based adaptive partitioning technique enables tight security in structure-preserving signature schemes.

The new structure-preserving signature scheme might be useful for easy construction of highly secure and efficient cryptographic applications that satisfy requirements from developers. For example, an individual or an organization publishes their cryptographic applications on some app stores. They might not be confident that user information used in their applications will be secure because they have neither many resources nor much knowledge about cryptography. In such cases, the new structure-preserving signature scheme might be helpful for developers to easily construct secure cryptographic applications.