In this paper, we present a faster (wall-clock time) sorting method for numerical data subjected to fully homomorphic encryption (FHE). Owing to circuit-based construction and the FHE security property, most existing sorting methods cannot be applied to encrypted data without significantly compromising efficiency. The proposed algorithm utilizes the cryptographic single-instruction multiple-data (SIMD) operation, which is supported by most existing FHE algorithms, to reduce the computational overhead. We conducted a careful analysis of the number of required recryption operations, which are the computationally dominant operations in FHE. Accordingly, we verified that the proposed SIMD-based sorting algorithm completes the given task more quickly than existing sorting methods if the number of data items and (or) the maximum bit length of each data item exceed specific thresholds.

In this paper, we propose a true random number generator (TRNG) exploiting jitter and the chaotic behavior in cross ring oscillators (CROs). We make a further study of the feedback ring architecture and cross-connect the XOR gates and inverters to form an oscillator. The CRO utilizes totally digital logic circuits, and gains a high and robust entropy rate, as the jitter in the CRO can accumulate locally between adjacent stages. Two specific working modes of CRO in which the CRO can work in a consistent state and a free-running state respectively are introduced and analyzed both theoretically and experimentally. Finally, different stage lengths of cross ring true random number generators (CRTRNGs) are tested in different Field Programmable Gate Arrays (FPGAs) and test results are analyzed and compared. Especially, random data achieved from a design of 63-stage CRTRNG in Altera Cyclone IV passes both the NIST and Diehard test suites at a rate as high as 240Mbit/s.

Pairing-based cryptography has realized a lot of innovative cryptographic applications such as attribute-based cryptography and semi homomorphic encryption. Pairing is a bilinear map constructed on a torsion group structure that is defined on a special class of elliptic curves, namely pairing-friendly curve. Pairing-friendly curves are roughly classified into supersingular and non supersingular curves. In these years, non supersingular pairing-friendly curves have been focused on from a security reason. Although non supersingular pairing-friendly curves have an ability to bridge various security levels with various parameter settings, most of software and hardware implementations tightly restrict them to achieve calculation efficiencies and avoid implementation difficulties. This paper shows an FPGA implementation that supports various parameter settings of pairings on non supersingular pairing-friendly curves for which Montgomery reduction, cyclic vector multiplication algorithm, projective coordinates, and Tate pairing have been combinatorially applied. Then, some experimental results with resource usages are shown.

With the rapid merger of healthcare business and information technology, more healthcare institutions and medical practices are sharing information. Since these records often contain patients' sensitive personal information, Healthcare Information Systems (HISs) should be properly designed to manage these records in a secure manner. We propose a novel security design for the HIS complying with the security and privacy rules. The proposed system defines protocols to ensure secure delivery of medical records over insecure public networks and reliable management of medical record in the remote server without incurring excessive costs to implement services for security. We demonstrate the practicality of the proposed system through a security analysis and performance evaluation.

Rotation symmetric Boolean functions (RSBFs) that are invariant under circular translation of indices have been used as components of different cryptosystems. In this paper, odd-variable balanced RSBFs with maximum algebraic immunity (AI) are investigated. We provide a construction of n-variable (n=2k+1 odd and n ≥ 13) RSBFs with maximum AI and nonlinearity ≥ 2n-1-¥binom{n-1}{k}+2k+2k-2-k, which have nonlinearities significantly higher than the previous nonlinearity of RSBFs with maximum AI.

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.

In a public-key encryption scheme, if a sender is not concerned about the security of a message and is unwilling to generate costly randomness, the security of the encrypted message can be compromised. In this work, we characterize such lazy parties, who are regarded as honest parties, but are unwilling to perform a costly task when they are not concerned about the security. Specifically, we consider a rather simple setting in which the costly task is to generate randomness used in algorithms, and parties can choose either perfect randomness or a fixed string. We model lazy parties as rational players who behave rationally to maximize their utilities, and define a security game between the parties and an adversary. Since a standard secure encryption scheme does not work in this setting, we provide constructions of secure encryption schemes in various settings.

In PQCrypto 2013, Yasuda, Takagi and Sakurai proposed a new signature scheme as one of multivariate public key cryptosystems (MPKCs). This scheme (called YTS) is based on the fact that there are two isometry classes of non-degenerate quadratic forms on a vector space with a prescribed dimension. The advantage of YTS is its efficiency. In fact, its signature generation is eight or nine times faster than Rainbow of similar size. For the security, it is known that the direct attack, the IP attack and the min-rank attack are applicable on YTS, and the running times are exponential time for the first and the second attacks and sub-exponential time for the third attack. In the present paper, we give a new attack on YTS whose approach is to use the diagonalization of matrices. Our attack works in polynomial time and it actually recovers equivalent secret keys of YTS having 140-bits security against min-rank attack in around fifteen seconds.

We construct the first fully homomorphic encryption (FHE) scheme that encrypts matrices and supports homomorphic matrix addition and multiplication. This is a natural extension of packed FHE and thus supports more complicated homomorphic operations. We optimize the bootstrapping procedure of Alperin-Sheriff and Peikert (CRYPTO 2014) by applying our scheme. Our optimization decreases the lattice approximation factor from Õ(n3) to Õ(n2.5). By taking a lattice dimension as a larger polynomial in a security parameter, we can also obtain the same approximation factor as the best known one of standard lattice-based public-key encryption without successive dimension-modulus reduction, which was essential for achieving the best factor in prior works on bootstrapping of standard lattice-based FHE.

Due to the fact that natural images are approximately sparse in Discrete Cosine Transform (DCT) or wavelet basis, the Compressive Sensing (CS) can be employed to decode both the host image and watermark with zero error, despite not knowing the host image. In this paper, Limited-Random Sequence (LRS) matrix is utilized to implement the blind CS detection, which benefits from zero error and lower complexity. The performance in Bit Error Rate (BER) and error-free detection probability confirms the validity and efficiency of the proposed scheme.

Assume that Alice, Bob, and Carol, each of whom privately holds a one-bit input, want to learn the output of some Boolean function, say the majority function, of their inputs without revealing more of their own secret inputs than necessary. In this paper, we show that such a secure three-input function evaluation can be performed with a deck of real cards; specifically, the three players can learn only the output of the function using eight physical cards — four black and four red cards — with identical backs.

In this letter, we derive two lower bounds for the number of terms in a double-base number system (DBNS), when the digit set is {1}. For a positive integer n, we show that the number of terms obtained from the greedy algorithm proposed by Dimitrov, Imbert, and Mishra [1] is $Thetaleft(rac{log n}{log log n} ight)$. Also, we show that the number of terms in the shortest double-base chain is Θ(log n).

In this paper, we improve a width-3 joint sparse form proposed by Okeya, Katoh, and Nogami. After the improvement, the representation can attain an asymtotically optimal complexity found in our previous work. Although claimed as optimal by the authors, the average computation time of multi-scalar multiplication obtained by the representation is 563/1574n+o(n)≈0.3577n+o(n). That number is larger than the optimal complexity 281/786n+o(n)≈0.3575n+o(n) found in our previous work. To optimize the width-3 joint sparse form, we add more cases to the representation. After the addition, we can show that the complexity is updated to 281/786n+o(n)≈0.3575n+o(n), which implies that the modified representation is asymptotically optimal. Compared to our optimal algorithm in the previous work, the modified width-3 joint sparse form uses less dynamic memory, but it consumes more static memory.

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.

Field Programmable Gate Array (FPGA) implementation of Elliptic Curve Cryptography (ECC) over GF(p) is commonly not fast enough to meet the request of high-performance applications. There are three critical factors to determine the performance of ECC processor over GF(p): multiplication structure, modular multiplication algorithm, and scalar point multiplication scheduling. This work proposes a novel multiplication structure which is a two-stage pipeline on the basis of Karatsuba-Ofman algorithm. With the proposed multiplication structure, we design a 256-bit modular multiplier based on Improved Barret Modular Multiplication algorithm. Upon the modular multiplier, we finish the scalar point multiplication scheduling and implement a high-performance ECC processor on FPGA. Compared with the previous modular multipliers, our modular multiplier reduces the 256-bit modular multiplication time by 28% at least. Synthesis result on Altera Stratix II shows that our ECC processor can complete a 256-bit ECC scalar point multiplication in 0.51ms, which is at least 1.3 times faster than the currently reported FPGA ECC processors over GF(p).

Presently, many identity-based proxy signature (IBPS) schemes have been proposed, but most of them require high computational costs and the proposed security model for IBPS is not enough complete. To overcome this weakness, Gu et al. recently proposed a framework and a detailed security model for IBPS. They also proposed an efficient IBPS scheme and proved the unforgeability of their scheme in the standard model. However, in this letter, we demonstrate that Gu et al.'s scheme fails to satisfy the property of unforgeability because it can not resist the following attacks: after getting a private key, an adversary behaving as a malicious signer can forge a private key on any identity without the help of the private key generator (PKG); after getting a delegation, an adversary behaving as a malicious proxy signer can forge a proxy signing key on any delegation without the agreement of the original signer; after getting a signature, an adversary behaving as a malicious user can forge a signature on any identity without the private key or forge a proxy signature on any warrant without the proxy signing key.

An aggregate signature scheme,which is an extension of ordinary signature, allows anyone to compress n signatures of n messages from n signers into a single short signature for reducing the size multiple individual signatures. Recently, Liu et al. proposed an efficient certificateless aggregate signature scheme with shorter public key size, constant AS size and with constant pairing computations. Although they proved that the scheme has existential unforgeability against adaptive chosen messages attacks. However, in this paper, two concrete attacks are proposed to show that Liu et al.'s scheme actually does not reach the security as they claimed.

Rainbow is one of signature schemes based on the problem solving a set of multivariate quadratic equations. While its signature generation and verification are fast and the security is presently sufficient under suitable parameter selections, the key size is relatively large. Recently, Quaternion Rainbow — Rainbow over a quaternion ring — was proposed by Yasuda, Sakurai and Takagi (CT-RSA'12) to reduce the key size of Rainbow without impairing the security. However, a new vulnerability emerges from the structure of quaternion ring; in fact, Thomae (SCN'12) found that Quaternion Rainbow is less secure than the same-size original Rainbow. In the present paper, we further study the structure of Quaternion Rainbow and show that Quaternion Rainbow is one of sparse versions of the Rainbow. Its sparse structure causes a vulnerability of Quaternion Rainbow. Especially, we find that Quaternion Rainbow over even characteristic field, whose security level is estimated as about the original Rainbow of at most 3/4 by Thomae's analysis, is almost as secure as the original Rainbow of at most 1/4-size.

This paper presents an efficient method for differential fault analysis (DFA) on substitution-permutation network (SPN)-based block ciphers. A combination of a permutation cancellation and an algebraic key filtering technique makes it possible to reduce the computational cost of key filtering significantly and therefore perform DFAs with new fault models injected at an earlier round, which defeats conventional countermeasures duplicating or recalculating the rounds of interest. In this paper, we apply the proposed DFA to the LED block cipher. Whereas existing DFAs employ fault models injected at the 30th round, the proposed DFA first employs a fault model injected at the 29th round. We demonstrate that the proposed DFA can obtain the key candidates with only one pair of correct and faulty ciphertexts in about 2.1h even from the 29th round fault model and the resulting key space is reduced to 24.04

This paper briefly deals with a wide range of topics in information-theoretic cryptography. First, we focus on the results on symmetric-key encryption and authentication codes, since these protocols are fundamental in the field and well studied in the frameworks by Shannon and Simmons, respectively. Secondly, we explain several existing assumptions and security criteria whose merit mainly lies in realizing cryptographic protocols with short/weak shared secret-keys, correlated weak secret-keys, or no shared secrets. Thirdly, we consider research themes by three aspects for further development of information-theoretic cryptography. Finally, we refer to trends of technical approaches in information-theoretic cryptography and explain our recent results brought by using the approach.