宮地 秀至

In recent years, our society has become increasingly information-oriented. For example, paper documents have been digitized, and correspondence by letter is now done by e-mail. In this way, many services that were previously realized in analog form are now realized digitally. While digitized data has the advantage of being easily passed on to others, it also has the disadvantage of being easily seen by anyone. It is therefore inevitable to encrypt the data so that only certain people can see the data. Encrypted data is kept secret until it is decrypted. However, cases frequently arise in which the timing of decryption needs to be controlled. For example, consider an online bidding process in which an organization selects contractors. In this case, the bid values must be kept secret from everyone until all bids have been received. If the organization can see some bids before all bids are submitted, there is a possibility of collusion with other contractors. Commitment scheme allows control of the decoding timing.

Commitment schemes must satisfy: the hiding and the binding properties. Commitment scheme is executed in two phases: a commitment phase and a decommitment phase. In the commitment phase, the sender sends the ciphertext C=E(K,M) which is an encryption of a plaintext M by a key K. In a decommitment phase, the decryption key K is sent from the sender to the receiver. A decommitment phase is executed only at the time of decryption. In other words, in order for the sender to control the timing of decryption, the ciphertext must not be decrypted until the key K is sent to the receiver. This function is called the
hiding property, which corresponds to the security of the receiver. On the other hand, it is necessary that the sender cannot construct a key that enables decryption of a plaintext M' that differs from the plaintext M corresponding to the ciphertext C (the sender cannot compute C=E(K,M)=E(K',M') where K̸=K' and M̸=M'). This function is called the binding property, which corresponds to the security of the sender.

It is an important issue to realize an efficient, compact, and secure commitment scheme. As for security, a commitment scheme should be secure against a quantum machine since the current security assumption such as integer factorization or elliptic discrete logarithm problem can be broken if a quantum machine is achieved. On the other hand, commitment schemes are said to be a fundamental technology for cryptography because of their ability to determine the timing of decryption. We can solve the privacy problems that exist in social media by using the features of the commitment scheme.

In this dissertation, we addressed three technical issues to achieve a practical commitment
scheme.

• A proposal of a commitment scheme with a small output locality using post-quantum cryptography. 
• A proposal of message scalable commitment scheme using post-quantum cryptography (commitment scheme that can send a larger input length for the same output length). 
• A proposal of social media that satisfies unlinkability and disclosure using a commitment scheme.

We focus on the post-quantum commitment scheme which is secure against a quantum machine. In addition, to propose an efficient, compact, and secure commitment scheme, we focus on the notions of output locality and message scalability. The output locality is a natural complexity measure of computational efficiency for Boolean functions. It is known that a Boolean function has output locality k if each output bit depends on a maximum of k input bits. If the commitment scheme satisfies k constant output locality, then it is executed at a constant k depth for any input. In other words, constant low-output locality functions are implementable by low-depth circuits, implying high parallelizability. On the other hand, message scalability means that the input length is large compared to the output length. By realizing a message-scalable
commitment scheme, a compact commitment scheme can be realized.

In the first study, we propose a post-quantum secure commitment scheme with a small output locality. The post-quantum commitment scheme with a constant small output locality can realize parallel commitment schemes, which can realize post-quantum and efficient commitment schemes. This makes it possible to propose efficient applications using proposed commitment schemes. In this proposal, we theoretically propose a commitment scheme with a small output locality using post-quantum cryptography and evaluate its security parameters. In existing research, a random function called randomness extractor is applied to achieve a commitment scheme with an output locality of 4. However, the structure of commitment schemes using a randomness extractor is not simple. Consequently, it is not a suitable method for realizing applications such as online bidding. In this dissertation, we propose the first commitment scheme with output locality 3 without using a randomness extractor. We combine Perfect Randomized Encoding (PRE) with a commitment scheme to realize a commitment scheme with output locality 3. First, we propose a commitment scheme with a small output locality. Then, we prove whether it satisfies both hiding and binding properties or not. By constructing a commitment scheme that satisfies both hiding and binding properties, it can be applied to applications such as online bidding.

In the second study, we propose a message-scalable commitment scheme using post-quantum cryptography. In this research, it can send twice the input length for the same output length of the existing work. In order to achieve the doubled input length, we introduce a new assumptionto prove the binding property. Furthermore, we evaluate the proposed commitment scheme by comparing it with other existing studies. First, we propose a message-scalable commitment scheme. Then, we prove whether it satisfies both hiding and binding properties or not. By constructing the message-scalable commitment scheme that satisfies both hiding and binding properties, it is possible to construct an online bidding system that can send larger messages even in the IoT with a limited output length.

In the third study, we propose a commitment scheme-based social media system, focusing on social media without a commitment scheme. Social media is an important information sharing application currently used by many users. Because social media allows users to send their own information easily, the issue of privacy protection has become an important issue. In 2018, Zhang et al. presented an attack that makes it possible to identify user information from social media posts, and they proposed a way to prevent it by satisfying unlinkability. However, that method does not allow users to disclose information about their own specific posts. We propose the first social media that simultaneously satisfies unlinkability and disclosure by using
a commitment scheme. We show that it is possible to construct a social media that satisfies unlinkability and disclosure by satisfying the hiding and binding properties of the commitment scheme. In addition, we also evaluate the posting time and the capacity of the posting space at the same time.

From now on, we provide a summary of the proposal. We have made the above three proposals in order to realize a secure information-oriented society in response to the social issues mentioned above. In the first study and the second study, we proposed a theoretical proposal and evaluated the security of the system. On the other hand, in the third study, we have proposed a theoretical proposal for social media. We have proposed regarding the privacy of social media. We also implemented and evaluated our social media.