Multivariate public key cryptosystems (MPKC) are constructed based on the problem of solving multivariate quadratic equations (MQ problem). Among various multivariate schemes, UOV is an important signature scheme since it is underlying some signature schemes such as MAYO, QR-UOV, and Rainbow which was a finalist of NIST PQC standardization project. To analyze the security of a multivariate scheme, it is necessary to analyze the first fall degree or solving degree for the system of polynomial equations used in specific attacks. It is known that the first fall degree or solving degree often relates to the Hilbert series of the ideal generated by the system. In this paper, we study the Hilbert series of the UOV scheme, and more specifically, we study the Hilbert series of ideals generated by quadratic polynomials used in the central map of UOV. In particular, we derive a prediction formula of the Hilbert series by using some experimental results. Moreover, we apply it to the analysis of the reconciliation attack for MAYO.

Recently, H. Liu et al. [H. Liu, M. Liang, and H. Sun, A secure and efficient certificateless aggregate signature scheme, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, vol.E97-A, no.4, pp.991-915, 2014] proposed a new certificateless aggregate signature (CLAS) scheme and demonstrated that it was provably secure in the random oracle model. However, in this letter, we show that their scheme cannot provide unforgeability, i.e., an adversary having neither the user's secret value nor his/her partial private key can forge a legal signature of any message.

At Indocrypt 2005, Coglianese and Goi [1] suggested a new public key cryptosystem, MaTRU, which is a variant of NTRU. MaTRU is defined over ring M of k×k matrices whose elements are in the quotient ring R = Z[X]/(Xn-1). In addition, five example parameter sets suitable for this new structure were proposed. In this paper, we prove that it is impossible to generate appropriate key pairs for four parameter sets among the five proposed in [1] according to the key generation procedure described in [1]. The only parameter set where key pair generation is possible is when p, one of the parameters of MaTRU, is 2 and df, another parameter, is odd. Even with this parameter set, however, the decryption operation defined in [1] cannot recover an original plaintext from a given ciphertext because the value of another parameter, q, has been defined too small in [1]. Therefore, we propose an alternative method for key generation and suggest corrected parameter sets. In addition, a refined analysis for the key security of MaTRU is provided, and it is demonstrated that the key security may be significantly lower than that of the original analysis.

In this letter, we propose an improvement on a knapsack probabilistic encryption scheme [B. Wang, Q. Wu, Y. Hu, Information Sciences 177 (2007)], which was shown vulnerable to attacks due to Youssef [A.M. Youssef, Information Sciences 179 (2009)] and Lee [M.S. Lee, Information Sciences 222 (2013)], respectively. The modified encryption scheme is secure against Youssef's and Lee's attacks only at the costs of slightly compromising the efficiency of the original proposal.

Keith Salvin presented a key exchange protocol using matrices in the general linear group, GL(r,Zn), where n is the product of two distinct large primes. The system is fully specified in the US patent number 7346162 issued in 2008. In the patent claims, it is argued that the best way to break this system is to factor n. Furthermore, for efficiency reasons, it is suggested to use r=2. In this letter, we show that this cryptosystem can be easily broken by solving a set of consistent homogeneous r2 linear equations in 2r unknowns over Zn.

In this paper, we present a fault analysis of the original NTRU public key cryptosystem. The fault model in which we analyze the cipher is the one in which the attacker is assumed to be able to fault a small number of coefficients of the polynomial input to (or output from) the second step of the decryption process but cannot control the exact location of injected faults. For this specific original instantiation of the NTRU encryption system with parameters (N,p,q), our attack succeeds with probability≈ and when the number of faulted coefficients is upper bounded by t, it requires O((pN)t) polynomial inversions in Z/p Z[x]/(xN-1).

Sanitizable signatures allow sanitizers to delete some pre-determined parts of a signed document without invalidating the signature. While ordinary sanitizable signatures allow verifiers to know how many subdocuments have been sanitized, invisibly sanitizable signatures do not leave any clue to the sanitized subdocuments; verifiers do not know whether or not sanitizing has been performed. Previous invisibly sanitizable signature scheme was constructed based on aggregate signature with pairings. In this article, we present the first invisibly sanitizable signature without using pairings. Our proposed scheme is secure under the RSA assumption.

This paper proposes a method to construct a basis conversion matrix between two given bases in Fpm. In the proposed method, Gauss period normal basis (GNB) works as a bridge between the two bases. The proposed method exploits this property and construct a basis conversion matrix mostly faster than EDF-based algorithm on average in polynomial time. Finally, simulation results are reported in which the proposed method compute a basis conversion matrix within 30 msec on average with Celeron (2.00 GHz) when mlog p≈160.

The efficient squaring algorithm is an important role in large integer arithmetic. All multiplication algorithms can be used for squaring large integers, but their performance can be greatly improved by using the standard squaring algorithm. The standard squaring algorithm is quite well-known, but unfortunately there is an improper carry handling bug in it. Recently, Guajardo and Paar proposed a modified squaring algorithm to fix the bug in the standard squaring algorithm. In this paper, we first point out that there is still an error-indexing bug in the Guajardo-Paar squaring algorithm. Then, we propose a new efficient squaring algorithm that not only avoids the bugs in both the standard squaring algorithm and the Guajardo-Paar squaring algorithm but also improves the performance in squaring computation. Our analyses and our simulations indicate that the proposed squaring algorithm is about 2.5 times faster in comparison with the standard multiplication algorithm in Pentium Series CPU. The performance of 1024-bit RSA cryptosystem can be saved 34.3% by using the proposed squaring algorithm to replace the standard multiplication.

This paper presents an efficient public-key protocol for mutual authentication and key exchange designed for mobile information services in UMTS. Certain modifications to the ASPeCT registration protocol is proposed to introduce Temporary Mobile User Certificate in UMTS environments. Proposed Temporary Mobile User Certificate, digitally-signed by the private signing key of the TTP located in the user's visiting domain, will be issued to the user during the registration protocol. ASPeCT AIP protocol can be modified to reduce communication overhead and speed up verification process using Temporary Mobile User Certificate between the user and the Value-Added Service Provider (VASP) located in the user's visiting domain. Furthermore, Temporary Mobile User Certificate can provide anonymity for a mobile user during the ASPeCT AIP protocol.

Recently the study and implementation of elliptic curve cryptosystems (ECC) have developed rapidly and its achievements have become a center of attraction. ECC has the advantage of high-speed processing in software even on restricted environments such as smart cards. In this paper, we concentrate on complete software implementation of ECC over a prime field on a 16-bit microcomputer M16C (10 MHz). We propose a new type of prime characteristic of base field suitable for small and fast implementation, and also improve basic elliptic arithmetic formulas. We report a small and fast software implementation of a cryptographic library which supports 160-bit elliptic curve DSA (ECDSA) signature generation, verification and SHA-1 on the processor. This library also includes general integer arithmetic routines for applicability to other cryptographic algorithms. We successfully implemented the library in 4 Kbyte code/data size including SHA-1, and confirmed a speed of 150 msec for generating an ECDSA signature and 630 msec for verifying an ECDSA signature on M16C.

This paper proposes a secure electronic sealed-bid auction protocol (SEAP) that provides an auction service on the Internet by combining three providers: an auction service provider, a key service provider, and a time service provider. The SEAP uses public key cryptography and the concept of a time-key certificate. The most important property of this protocol is that time-dependent security requirements can be strictly satisfied. The SEAP satisfies the following nine security requirements: (a) no one can deny having made a bid; (b) the protocol should be secure against malicious acts; (c) no bidder can act for another bidder; (d) no one can know who else is bidding until the time comes for the bids to be opened; (e) no one can discover the contents of any of the bids until the time comes for the bids to be opened; (f) the successful bid must have been submitted before the bidding deadline; (g) all bidders can verify that the auction policy has been correctly implemented; (h) the successful bidder can be identified without being required to make himself or herself known; and (i) the bidding contents cannot be altered. The protocol consists of three subprotocols: the Registration Subprotocol, the Bidding Subprotocol, and the Auction Subprotocol. The protocol parameters and algorithm are described in detail.

The technique of common-multiplicand multiplication, CMM, is modified and the similar approach is utilized to enhance the performance of a recently proposed fast exponentiation algorithm by exponent decomposition. On average, the improved exponentiation, its original version, and the traditional right to left binary exponentiation algorithm take 1.292m+11,1.375m+3, and 1.5m multiplications, respectively where m is the bit length of the exponent. Finally, it is shown how to improve the overall performance of an exponentiation by employing the improved exponentiation algorithm, the improved CMM algorithm , and any general purpose fast multiplication algorithm.