多田 充

In [13], we proposed new decision problems related to lattices, and proved their NP-completeness. In this paper, we present a new public-key identification scheme and a digital signature scheme based on one of the problems in [13]. We also prove the security of our schemes under certain assumptions, and analyze the efficiency of ours.

We proposed a one-way trapdoor permutation f based multi-signature scheme which can keep tighter reduction rate. Assuming the underlying hash functions are ideal, our proposed scheme is not only provably secure, but are so in a tight. An ability to forge multisignatures with a certain amount of computational resources implies the ability to invert a one-way trapdoor permutation f (on the same size modulus) with about the same computational effort. The proposed scheme provides the exact security against Adaptive-Chosen-Message-Attack and Adaptive-Insider-Attack by F [10]. F can also attack in key generation phase, and act in collusion with corrupted signers.

In this paper, we propose a fast signature scheme which is derived from three-pass identification scheme. Our signature scheme would require a modular exponentiation as preprocessing. However, no multiplication is used in the actual (i.e. on-line) signature generation. This means that the phase involves only a hashing operation, addition and a modular reduction. So far, some fast signature schemes called on the fly signatures were proposed. In those schemes the modular reduction is eliminated in the on-line phase. Therefore, our approach to obtain the fast on-line signature is different from theirs. This paper is the first approach for the fast signature scheme without on-line modular multiplication.Financial cryptography : 6th International Conference, FC 2002, Southampton, Bermuda, March 11-14, 2002 : reveised papers / Matt Blaze (ed.)

Up to present, we have yet seen no multi-signature schemes based on RSA secure against active attacks proposed. We have examined the possibility of simulation of signatures in the MM scheme [7] in order to investigate whether that scheme has the security against active attacks. The MM scheme cannot be shown secure against active attacks. We have constructed the RSA-based multi-signature scheme in order to overcome the problem that the MM scheme has. The proposed scheme provides the security against adaptive chosen message insider attack targeting one signer, and can keep tighter reduction rate.

In this paper, we propose a multi-signature scheme, in which each signer can express her intention associating with the message to be signed. Signers' intentions mean a kind of information which can be newly attached to a signature in signers' generating it. However, we have been introduced any multi-signature scheme dealing with intentions without loss of its efficiency. First, we consider a multi-signature scheme realizing the concept of signers' intentions by utilizing existing schemes, and name it primitive method. After that, we introduce the proposed multi-signature scheme which are more efficient in view of the computational cost for verification and in view of the signature size than the primitive method. The proposed multi-signature scheme is shown to be secure even against adaptive chosen message insider attacks.Information security and cryptology : ICISC 2001 : 4th International Conference, Seoul, Korea, December 6-7, 2001 : proceedings / Kwangjo Kim (ed.).

署名者の意思を反映する事ができ, しかも効率的で安全性の証明も可能な意思付多重署名方式を提案する.署名者の意思とは, 各署名者が文書に署名する際, 新たに付加して送ることのできるある種の情報である.しかし現在までに, 効率性を悪化させることなく新たな情報を付加することのできる多重署名方式は未だ提案されていない.まず, 既存の多重署名モデルを利用しこの概念を実現する方式をPrimitiveモデルと呼び, その後, 署名サイズや検証コストにおいてPrimitiveモデルよりも優れた方式を意思付提案意思付多重署名モデルとして提案する.この意思付多重署名方式のベースとなる意思付複数ラウンド認証方式が健全性とゼロ知識性を兼ね備えているならば, 安全性を証明することができる.

In 1999, Poupard and Stern proposed on the fly signature scheme (PS-scheme), which aims at minimizing the on-line computational work for a signer. In this paper, we propose more efficient on the fly signature schemes by improving the PS-scheme. In PS-scheme, the size of secret-key is fixed by modulus n, so that this feature leads to some drawbacks in terms of both the computational work and the communication load. The main idea of our schemes is to reduce the size of secret-key in PS-scheme by using a public element g which has a specific structure. Consequently, our schemes are improved with respect to the computational work (which means the computational cost for "precomputation", "(on-line) signature generation" and "verification") and the data size such as a secret-key and a signature.Progress in cryptology - INDOCRYPT 2001 : Second International Conference on Cryptology in India, Chennai, India, December 16-20, 2001 : proceedings / C. Pandu Rangan, Cunsheng Ding (eds.).

In this paper, we describe how to construct an efficient and unconditionally secure verifiable threshold changeable scheme, in which any participants can verify whether the share given by the dealer is correct or not, in which the combiner can verify whether the pooled shares are correct or not, and in which the threshold can be updated plural times to the values determined in advance. An optimal threshold changeable scheme was defined and given by Martin et. al., and an unconditionally secure verifiable threshold scheme was given by Pedersen. Martin's scheme is based on Blakley's threshold scheme whereas Pedersen's is based on Shamir's. Hence these two schemes cannot directly be combined. Then we first construct an almost optimal threshold changeable scheme based on Shamir's, and after that using Pedersen's scheme, construct a unconditionally secure verifiable threshold scheme in which the threshold can be updated plural times, say N times. Furthermore, our method can decrease the amount of information the dealer has to be publish, comparing with simply applying Pedersen's scheme N times.Information security and privacy : 6th Australasian Conference, ACISP 2001, Sydney, Australia, July 11-13, 2001 : proceedings / Vijay Varadharajan, Yi Mu (eds.).

As far as the knowledge of authors, the rigorous security of Okamoto-Tanaka identity-based key exchange scheme was shown in [4] for the first time since its invention. However, the analysis deals with only the passive attack. In this paper, we give several models of active attacks against the scheme and show the rigorous security of the scheme in these models. We prove several relationships among attack models, including that (1) breaking the scheme in one attack model is equivalent to breaking the RSA public-key cryptosystem and (2) breaking the scheme in another attack model is equivalent to breaking the Diffie-Hellman key exchange scheme over Z_n. The difference of the complexity stems from the difference of the timing of dishonest party's sending out and receiving messages.

サークルの新メンバー募集等で希望者が名前を記入出来る(署名する)ポスターを目にすることがあるが、このような署名に対して多重署名方式が有効であることはよく知られている。しかし、署名者が名前以外の情報も付加した場合では、効率的な署名方式は提案されていない。そこで、我々は、そのような付加情報を「署名者の意思」と呼び、この概念を包含できる、既存の多重署名方式を利用する原始的な方法と新たな署名方式を提案する。そして、我々の署名方式が効率的で、署名者の意思を考慮する署名方式に固有の偽造に対して安全であることを示す。尚、本提案は離散対数問題に基づく多くの多重署名方式に適応可能である。

順序付き多重署名方式は署名者の集合だけでなく、その署名順序まで検証できるシステムである。本論文では、安全性の数学的な証明がされている、ある順序付き多重署名方式において、ある状況においては不正者がその秘密鍵を意図的に決定し登録することにより、他の署名者の同意がなくとも、あたかもその署名者が署名したかのような署名を作成することができることを指摘し、その修正方式を述べる。

It is known that division by some constant m is provably total in the theory S20, if and only if the constant m is of the form 2n for some n. In this paper, we prove that also in the theory S2+0 which is a little stronger than S20, the same statement holds by using the Johannsen's method on the division in S2+0.