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

(Japanese version released on July 27, 2017)

National Institute of Information and Communications Technology
Nippon Telegraph and Telephone Corporation

Nippon Telegraph and Telephone Corporation (NTT) and NICT, jointly with Karlsruhe Institute of Technology (KIT), have designed a highly secure and interoperable structure-preserving digital signature^*1 (hereafter, structure-preserving signature) scheme for the first time.

It is not necessarily possible to construct secure cryptographic applications^*2 by simply combining cryptographic building blocks. The new structure-preserving signature scheme can be easily combined with other cryptographic building blocks and make it easier to construct highly secure and interoperable cryptographic applications. Moreover, even if the number of users increases, the new structure-preserving signature scheme remain secure without enlarging the size of the security parameter.

The details of this research results will be presented at CRYPTO 2017^*3, which is one of top international conferences organized by the International Association for Cryptologic Research (held in USA, starting August 20).

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)

[画像:Figure 1: Concept of structure-preserving cryptography]

In previous structure-preserving signature schemes, the size of a security parameter must be enlarged to maintain their security when the number of users increases. When the size of a security parameter is enlarged, the size of a signature and the computation cost are also enlarged. Tightly secure cryptography solves this issue because its security does not degrade, even if the number of users increases.

When a cryptographic application is constructed from many cryptographic building blocks, the cryptographic application is not tightly secure if one of the building blocks is not tightly secure. Therefore, interoperable and tightly secure cryptographic building blocks are needed as useful tools for designing efficient cryptographic applications in a modular way. However, it is known that the well-known technique for achieving tight security is not applicable to structure-preserving cryptography, which is a serious problem.

NTT and NICT have been developing interoperable structure-preserving signature schemes. One of their goals is achieving easy modular design of efficient and secure cryptographic applications. Developing an interoperable and tightly secure structure-preserving signature scheme is an important milestone to achieve this goal.

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.

[画像:Figure 2: Advantage of new structure-preserving signature scheme]

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.

[画像:Figure 3: Key facts]

NTT and NICT will develop interoperable and tightly secure cryptographic building blocks and continue to conduct research on cryptography which is essential to achieve secure networks.

*1 A digital signature for document data is generated using a digital signing key of a signer. Anyone can verify the validity of a digital signature by a public verification key.

*2 Applications that use cryptographic schemes as building blocks such as digital signature schemes. For example, electronic voting protocols, electronic cash protocols.

*3 Top international conference organized by International Association for Cryptologic Research (IACR). Cutting-edge cryptographic technology is published.

*4 A mathematical notion that consists of a set and one operation.

Planning Department Spokesperson
Service Innovation Laboratory Group
Nippon Telegraph and Telephone Corporation
E-mail:

Press Office
Public Relations Department
National Institute of Information and Communications Technology
E-mail:
Tel:+81-42-327-6923