A permutation cipher scheme using polynomials over a field is presented. A permutation as well as substitution plays a major role in almost all conventional cryptosystems. But the security of the permutation depends on how symbols are permuted. This paper proposes the use of polynomials for the permutation and show that the scheme satisfies the following security criteria. (1) There are enough encryption keys to defend exhaustive attacks. (2) The permutation moves almost all samples into places which are different from the original places. (3) Most samples are shifted differently by different permutations. The permutation cipher scheme could be regarded as a scheme based on Reed-Solomon codes. The information symbols of the codes compose a key of the permutation cipher scheme.

The rigorous security of Okamoto-Tanaka identity-based key exchange scheme has been open for a decade. In this paper, we show that (1) breaking the scheme is equivalent to breaking the Diffie-Hellman key exchange scheme over Zn, and (2) impersonation is easier than breaking. The second result is obtained by proving that breaking the RSA public-key cryptosystem reduces to breaking the Diffie-Hellman scheme over Zn with respect to the polynomial-time many-one reducibility.

We study an authentication method using secret figures of Pattern Lock, called pass patterns. In recent years, it is important to prevent the leakage of personal and company information on mobile devices. Android devices adopt a login authentication called Pattern Lock, which achieves both high resistance to Brute Force Attack and usability by virtue of pass pattern. However, Pattern Lock has a problem that pass patterns directly input to the terminal can be easily remembered by shoulder-surfing attack. In this paper, we propose a shoulder-surfing resistant authentication using pass pattern of Pattern Lock, which adopts a challenge & response authentication and also uses users' short-term memory. We implement the proposed method as an Android application and measure success rate, authentication time and the resistance against shoulder surfing. We also evaluate security and usability in comparison with related work.

Can we find in polynomial time an elliptic curve of a given order over a finite field? This paper is concerned with this question which is open since 1986. Consider the partial multivalued function that outputs such an elliptic curve. We characterize the difficulty of computing this function, and show that the polynomial time hierarchy collapses if sat reduces to this function with respect to the polynomial time Turing reducibility, where sat is the partial multivalued function that on input a Boolean formula, outputs a satisfying assignment. We also give a problem that is equivalent to the open question under the Extended Riemann Hypothesis.

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 Zn. The difference of the complexity stems from the difference of the timing of dishonest party's sending out and receiving messages.

This paper studies the reduction among cyptographic functions. Our main result is that the prime factoring function IF does not reduce to the certified discrete logarithm function modulo a prime nor its variant with respect to some special reducibility, i.e. the range injection reducibility, under the assumption that the Heath-Brown conjecture is true and IFPF. Since there is no known direct relationship between these functions, this is the first result that could separate these functions. Our approach is based on the notion of the preimage functions.

Computer viruses, hackers, intrusions and ther computer crimes have recently become a serious security problem in information systems. Digital signatures are useful to defend against these threats, especially against computer viruses. This is because a modification of a file can be detected by checking the consistency of the originai file with its accompanying digital signature. But an executable program might have been infected with the viruses before the signature was created. In this case, the infection cannot be detected by signature verification and the origin of the infection cannot be specified either. In this paper, we propose a signature scheme in which one can sign right after the creation of an executable program. That is, when a user compiles a source program, the compiler automatically creates both the executable program and its signature. Thus viruses cannot infect the executable programs without detection. Moreover, we can specify the creator of contaminated executable programs. In our signature scheme, a signature is created from a set of secret integers stored in a compiler, which is calculated from a compiler-maker's secret key. Each compiler is possessed by only one user and it is used only when a secret value is fed into it. In this way a signature of an executable program and the compiler-owner are linked to each other. Despite these measures, an executable program could run abnormally because of an infection in prepro-cessing step, e.g. an infection of library files or included files. An infection of these files is detected by ordinary digital signatures. The proposed signature scheme together with digital signature against infection in the preprocessing step enables us to specify the origin of the infection. The name of the signature creator is not necessary for detecting an infection. So, an owner's public value is not searched in our scheme, and only a public value of a compiler-maker is required for signature verification. Furthermore, no one can use a compiler owned by another to create a proper signature.

In this paper a new type of public-key cryptosystem, proxy cryptosystem, is studied. The proxy cryptosystem allows an original decryptor to transform its ciphertext to a ciphertext for a designated decryptor, proxy decryptor. Once the ciphertext transformation is executed, the proxy decryptor can compute a plaintext in place of the original decryptor. Such a cryptosystem is very useful when an entity has to deal with large amount of decrypting operation. The entity can actually speed-up the decrypting operation by authorizing multiple proxy decyptors. Concrete proxy cryptosystems are constructed for the ElGamal cryptosystem and the RSA cryptosystem. A straightforward construction of the proxy cryptosystem is given as follows. The original decryptor decrypts its ciphertext and re-encrypts an obtained plaintext under a designated proxy decryptor's public key. Then the designated proxy decryptor can read the plaintext. Our constructions are more efficient than such consecutive execution of decryption and re-encryption. Especially, the computational work done by the original decryptor is reduced in the proxy cryptosystems.

By the deployment of Internet of Things, embedded systems using microcontroller are nowadays under threats through the network and incorporating security measure to the systems is highly required. Unfortunately, microcontrollers are not so powerful enough to execute standard security programs and need light-weight, high-speed and secure cryptographic libraries. In this paper, we port NaCl cryptographic library to ARM Cortex-M0(M0+) Microcontroller, where we put much effort in fast and secure implementation. Through the evaluation we show that the implementation achieves about 3 times faster than AVR NaCl result and reduce half of the code size.

To the authors' knowledge, there are not many cryptosystems proven to be as difficult as or more difficult than the discrete logarithm problem. Concerning problems related to the discrete logarithm problem, there are problems called the double discrete logarithm problem and the e-th root of the discrete logarithm problem. These two problems are likely to be difficult and they have been utilized in cryptographic protocols such as verifiable secret sharing scheme and group signature scheme. However, their exact complexity has not been clarified, yet. Related to the e-th root of the discrete logarithm problem, we can consider a square root of the discrete logarithm problem. Again, the exact complexity of this problem has not been clarified, yet. The security of cryptosystems using these underlying problems deeply depends on the difficulty of these underlying problems. Hence it is important to clarify their difficulty. In this paper we prove reductions among these fundamental problems and show that under certain conditions, these problems are as difficult as or more difficult than the discrete logarithm problem modulo a prime.

Broadcasting with secrecy of messages is important in a situation such as pay television. In pay television only a broadcasting station broadcasts a message. On the other hand, broadcast communication is also important. Broadcast communication means any user in a whole group can broadcast a message to any subset of the group. In this paper the efficiency of secure broadcast communication is discussed in terms of the length of messages sent and the encryption speed. We prove that the length of the broadcast messages is not kept less than O(n), where n is the number of receivers, when a broadcast system has a form of a single system which is defined as the generalized form of an individual key method and a master key method. In contrast, the proposed secure broadcast communication method, a multi-dimension method, keeps the length of messages sent O(mmn), where m is the number of the dimension used in the multi-dimension method. At the same time the encryption speed was reduced from O(n(log(n+C2)+C3)) of the master key method to O(mn(logmn+C1)) of the multi-dimension method.

In this paper a public key certification scheme, which protects privacy of user of the public key certificate, is proposed. In the proposed scheme a certification authority issues anonymous public key certificates, with which a certificate user having his/her own secret key can make use of public key cryptography and a certificate verifier can confirm the authenticity of the cryptographic communication of the certificate user. The anonymity of their users is preserved against the verifier. In general, user's activities should not be linked each other from the viewpoint of privacy protection. The use of the same certificate results in the linkage of the cryptographic communications. So, ideally, a certificate should be used only once, and such a certificate is called a one-time certificate. In the proposed scheme one-time certificates are realized with low cost of communication and computation for the certificate user. Multiple certificates can be issued without interaction between CA and the user. The additional computation of the user to obtain a new anonymous public key certificate is one modular exponentiation. In addition, only one secret key is required for multiple certificates. Therefore, the proposed scheme is useful for applications which require anonymity, unlinkability, and efficiency.

We describe our implementation of the Hypercube variation of the Multiple Polynomial Quadratic Sieve (HMPQS) integer factorization algorithm on a Parsytec GC computer with 128 processors. HMPQS is a variation on the Quadratic Sieve (QS) algorithm which inspects many quadratic polynomials looking for quadratic residues with small prime factors. The polynomials are organized as the nodes of an n-dimensional cube. We report on the performance of our implementations on factoring several large numbers for the Cunningham Project.

The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.

Proxy cryptosystems are classified into proxy decryption systems and proxy re-encryption systems on the basis of a proxy's role. In this paper, we propose an ID-based proxy cryptosystem with revocability and hierarchical confidentialities. In our scheme, on receiving a ciphertext, the proxy has the rights to perform the following three tasks according to the message confidentiality levels of the sender's intention: (1) to decrypt the ciphertext on behalf of the original decryptor; (2) to re-encrypt the ciphertext such that another user who is designated by the original decryptor can learn the message; (3) to do nothing except for forwarding the ciphertext to the original decryptor. Our scheme supports revocability in the sense that it allows proxy's decryption and re-encryption rights to be revoked even during the valid period of the proxy key without changing the original decryptor's public information. We prove that our proposal is indistinguishable against chosen identity and plaintext attacks in the standard model. We also show how to convert it into a system against chosen identity and ciphertext attacks by using the Fujisaki-Okamoto transformation.

In this paper a new type of digital proxy signature is proposed. The proxy signature allows a designated person, called a proxy signer, to sign on behalf of an original signer. Classification of the proxy signatures is shown from the point of view of the degree of delegation, and the necessary conditions of a proxy signature are clarified. The proposed proxy signature scheme is based on either the discrete logarithm problem or the problem of taking the square root modulo of a composite number. Compared to the consecutive execution of the ordinary digital signature schemes, it has a direct from, and a verifier does not need a public key of a user other than the original signer in the verification stage. Moreover, it requires less computational work than the consecutive execution of the signature schemes. Due to this efficiency together with the delegation property, an organization, e.g. a software company, can very efficiently create many signatures of its own by delegating its signing power to multiple employees. Another attractive feature is that the proxy signature based on the discrete logarithm problem is highly applicable to other ordinary signature schemes based on the same problem, For instance, designated confirmer proxy signatures can be constructed. As a stronger form of proxy signature for partial delegation, another type of proxy signature scheme is proposed in which even an original signer cannot create a proxy signature. Furthermore, using a proposed on-line proxy updating protocol, the orignal signer can revoke proxies of dishonest proxy signers.

Verifying the signing order is sometimes very important in multisignature schemes. A multisignature scheme in which the signing order can be verified is called structured multisignature scheme and many such schemes have been proposed so far. However, there are not many structured multisignature schemes utilizing an algebraic structure of underlying algebraic operation. Ohmori, Chida, Shizuya and Nishizeki have proposed a structured multisignature scheme by utilizing a non-commutative ring homomorphism. Since their scheme does not fully reflect the structure of signers and its rigorous security analysis is not provided, we construct an improved structured multisignature scheme overcoming these problems by utilizing the non-commutative ring homomorphism in a different way and discuss its rigorous security against various attacks, including signer structure forgery, rogue key attack and attack-0 under the discrete logarithm assumption. As far as we know, the scheme in [30], which does not use non-commutative ring homomorphism, guarantees the most rigorous security but the number of signers is restricted in order to prevent attack-0. In contrast, our scheme overcomes attack-0 by virtue of a ring homomorphism and no restriction is imposed on the number of signers.

A key distribution system is a system in which users securely generate a common key. One kind of identity-based key distribution system was proposed by E. Okamoto. Its security depends on the difficulty of factoring a composite number of two large primes like RSA public-key cryptosystem. Another kind of identity-based key distribution system was proposed by K. Nyberg, R. A. Rueppel. Its security depends on the difficulty of the discrete logarithm problem. On the other hand, Koblitz and Miller described how a group of points on an elliptic curve over a finite field can be used to construct a public key cryptosystem. In 1997, we proposed an ID-based key distribution system over an elliptic curve, as well as those over the ring Z/nZ. Its security depends on the difficulty of factoring a composite number of two large primes. We showed that this system over an elliptic curve is more suitable for the implementation than those over the ring Z/nZ. In this paper, we apply the Nyberg-Rueppel ID-based key distribution system to an elliptic curve. It provides relatively small block size and high security. This public key distribution system can be efficiently implemented. However the Nyberg-Rueppel's scheme requires relatively large data transmission. As a solution to this problem, we improve the scheme. This improved scheme is very efficient since data transferred for the common key generation is reduced to half of those in the Nyberg-Rueppel's scheme.