In Shamir's (k,n)-threshold secret sharing scheme [1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k ≥ 3 and n is arbitrary. This paper proposes a new fast (3,n)-threshold scheme by using just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret, which is an ideal secret sharing scheme similar to Shamir's scheme. Furthermore, we evaluate the efficiency of the scheme, and show that it is more efficient than Shamir's in terms of computational cost. Moreover, we suggest a fast (k,n)-threshold scheme can be constructed in a similar way by increasing the sets of random numbers constructing pieces of shares.

The number of IT services that use machine learning (ML) algorithms are continuously and rapidly growing, while many of them are used in practice to make some type of predictions from personal data. Not surprisingly, due to this sudden boom in ML, the way personal data are handled in ML systems are starting to raise serious privacy concerns that were previously unconsidered. Recently, Fredrikson et al. [USENIX 2014] [CCS 2015] proposed a novel attack against ML systems called the model inversion attack that aims to infer sensitive attribute values of a target user. In their work, for the model inversion attack to be successful, the adversary is required to obtain two types of information concerning the target user prior to the attack: the output value (i.e., prediction) of the ML system and all of the non-sensitive values used to learn the output. Therefore, although the attack does raise new privacy concerns, since the adversary is required to know all of the non-sensitive values in advance, it is not completely clear how much risk is incurred by the attack. In particular, even though the users may regard these values as non-sensitive, it may be difficult for the adversary to obtain all of the non-sensitive attribute values prior to the attack, hence making the attack invalid. The goal of this paper is to quantify the risk of model inversion attacks in the case when non-sensitive attributes of a target user are not available to the adversary. To this end, we first propose a general model inversion (GMI) framework, which models the amount of auxiliary information available to the adversary. Our framework captures the model inversion attack of Fredrikson et al. as a special case, while also capturing model inversion attacks that infer sensitive attributes without the knowledge of non-sensitive attributes. For the latter attack, we provide a general methodology on how we can infer sensitive attributes of a target user without knowledge of non-sensitive attributes. At a high level, we use the data poisoning paradigm in a conceptually novel way and inject malicious data into the ML system in order to modify the internal ML model being used into a target ML model; a special type of ML model which allows one to perform model inversion attacks without the knowledge of non-sensitive attributes. Finally, following our general methodology, we cast ML systems that internally use linear regression models into our GMI framework and propose a concrete algorithm for model inversion attacks that does not require knowledge of the non-sensitive attributes. We show the effectiveness of our model inversion attack through experimental evaluation using two real data sets.

Secure two-party comparison plays a crucial role in many privacy-preserving applications, such as privacy-preserving data mining and machine learning. In particular, the available comparison protocols with the appropriate input/output configuration have a significant impact on the performance of these applications. In this paper, we firstly describe a taxonomy of secure two-party comparison protocols which allows us to describe the different configurations used for these protocols in a systematic manner. This taxonomy leads to a total of 216 types of comparison protocols. We then describe conversions among these types. While these conversions are based on known techniques and have explicitly or implicitly been considered previously, we show that a combination of these conversion techniques can be used to convert a perhaps less-known two-party comparison protocol by Nergiz et al. (IEEE SocialCom 2010) into a very efficient protocol in a configuration where the two parties hold shares of the values being compared, and obtain a share of the comparison result. This setting is often used in multi-party computation protocols, and hence in many privacy-preserving applications as well. We furthermore implement the protocol and measure its performance. Our measurement suggests that the protocol outperforms the previously proposed protocols for this input/output configuration, when off-line pre-computation is not permitted.

In Shamir's (k,n)-threshold secret sharing scheme (threshold scheme)[1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k and n are arbitrary. This paper proposes a new fast (k,n)-threshold scheme which uses just EXCLUSIVE-OR(XOR) operations to make n shares and recover the secret from k shares. We prove that every combination of k or more participants can recover the secret, but every group of less than k participants cannot obtain any information about the secret in the proposed scheme. Moreover, the proposed scheme is an ideal secret sharing scheme similar to Shamir's scheme, in which every bit-size of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's.

Shamir's (k,n)-threshold secret sharing scheme (threshold scheme) has two problems: a heavy computational cost is required to make shares and recover the secret, and a large storage capacity is needed to retain all the shares. As a solution to the heavy computational cost problem, several fast threshold schemes have been proposed. On the other hand, threshold ramp secret sharing schemes (ramp scheme) have been proposed in order to reduce each bit-size of shares in Shamir's scheme. However, there is no fast ramp scheme which has both low computational cost and low storage requirements. This paper proposes a new (k,L,n)-threshold ramp secret sharing scheme which uses just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret at a low computational cost. Moreover, by proving that the fast (k,n)-threshold scheme in conjunction with a method to reduce the number of random numbers is an ideal secret sharing scheme, we show that our fast ramp scheme is able to reduce each bit-size of shares by allowing some degradation of security similar to the existing ramp schemes based on Shamir's threshold scheme.

This paper presents a chosen-IV (Initial Vector) correlation power analysis on the international standard stream cipher KCipher-2 together with an effective countermeasure. First, we describe a power analysis technique which can reveal the secret key (initial key) of KCipher-2 and then evaluate the validity of the CPA with experiments using both FPGA and ASIC implementations of KCipher-2 processors. This paper also proposes a masking-based countermeasure against the CPA. The concept of the proposed countermeasure is to mask intermediate data which pass through the non-linear function part including integer addition, substitution functions, and internal registers L1 and L2. We design two types of masked integer adders and two types of masked substitution circuits in order to minimize circuit area and delay, respectively. The effectiveness of the countermeasure is demonstrated through an experiment on the same FPGA platform. The performance of the proposed method is evaluated through the ASIC fabricated by TSMC 65nm CMOS process technology. In comparison with the conventional design, the design with the countermeasure can be achieved by the area increase of 1.6 times at most.

Guess-and-Determine (GD) attacks have recently been proposed for the effective analysis of word-oriented stream ciphers. This paper discusses GD attacks on clock-controlled stream ciphers, which use irregular clocking for a non-linear function. The main focus is the analysis of irregular clocking for GD attacks. We propose GD attacks on a typical clock-controlled stream cipher AA5, and calculate the process complexity of our proposed GD attacks. In the attacks, we assume that the clocking of linear feedback shift registers (LFSRs) is truly random. An important consideration affecting the practicality of these attacks is the question of whether these assumptions are realistic. Because in practice, the clocking is determined by the internal states. We implement miniature ciphers to evaluate the proposed attacks, and show that they are applicable. We also apply the GD attacks to other clock controlled stream ciphers and compare them. Finally, we discuss some properties of GD attacks on clock-controlled stream ciphers and the effectiveness of the clock controllers. Our research results contain information that are useful in the design of clock-controlled stream ciphers.

Time-sequence data is high dimensional and contains a lot of information, which can be utilized in various fields, such as insurance, finance, and advertising. Personal data including time-sequence data is converted to anonymized datasets, which need to strike a balance between both privacy and utility. In this paper, we consider low-rank matrix factorization as one of anonymization methods and evaluate its efficiency. We convert time-sequence datasets to matrices and evaluate both privacy and utility. The record IDs in time-sequence data are changed at regular intervals to reduce re-identification risk. However, since individuals tend to behave in a similar fashion over periods of time, there remains a risk of record linkage even if record IDs are different. Hence, we evaluate the re-identification and linkage risks as privacy risks of time-sequence data. Our experimental results show that matrix factorization is a viable anonymization method and it can achieve better utility than existing anonymization methods.

This paper reports on an evaluation result of current obfuscation techniques for Java byte code, such as Collberg's techniques in terms of mutational capability, real-time applicability, and program size increase. We suggest effective obfuscation techniques for random and real-time obfuscation (RR obfuscation). In the evaluation results, the combination of some obfuscation techniques was found to be useful for RR obfuscation, and some obfuscation techniques makes little or no difference after a certain threshold.

Program analysis techniques have improved steadily over the past several decades, and software obfuscation schemes have come to be used in many commercial programs. A software obfuscation scheme transforms an original program or a binary file into an obfuscated program that is more complicated and difficult to analyze, while preserving its functionality. However, the security of obfuscation schemes has not been properly evaluated. In this paper, we analyze obfuscation schemes in order to clarify the advantages of our scheme, the XOR-encoding scheme. First, we more clearly define five types of attack models that we defined previously, and define quantitative resistance to these attacks. Then, we compare the security, functionality and efficiency of three obfuscation schemes with encoding variables: (1) Sato et al.'s scheme with linear transformation, (2) our previous scheme with affine transformation, and (3) the XOR-encoding scheme. We show that the XOR-encoding scheme is superior with regard to the following two points: (1) the XOR-encoding scheme is more secure against a data-dependency attack and a brute force attack than our previous scheme, and is as secure against an information-collecting attack and an inverse transformation attack as our previous scheme, (2) the XOR-encoding scheme does not restrict the calculable ranges of programs and the loss of efficiency is less than in our previous scheme.

Establishment of a practical software protection method is a major issue in software distribution. There are several approaches to the issue; however, no practical, secure method for mobile phone applications has been proposed. In this paper, we propose a new software protection scheme combined with a tamper-proof device (TPD) in order to achieve computational security against illegal analysis and copying of the target program. Our scheme achieves a reasonable level of security for encoding the data and variables in a program. The program on a mobile phone deals only with encoded data that is difficult to compromise, and the TPD plays a role of decoding execution results. We implemented the proposed scheme on a 3G mobile phone and a user identification module (UIM). An analysis and copying of the protected program impose exponential computation complexities under our attack model.

KCipher-2 is a word-oriented stream cipher and an ISO/IEC 18033 standard. It is listed as a CRYPTREC cryptographic algorithm for Japanese governmental use. It consists of two feedback shift registers and a non-linear function. The size of each register in KCipher-2 is 32 bits and the non-linear function mainly applies 32-bit operations. Therefore, it can be efficiently implemented as software. SNOW-family stream ciphers are also word-oriented stream ciphers, and their high performance has already been demonstrated.We propose optimised implementations of KCipher-2 and compare their performance to that of the SNOW-family and other eSTREAM portfolios. The fastest algorithm is SNOW 2.0 and KCipher-2 is the second fastest despite the complicated irregular clocking mechanism. However, KCipher-2 is the fastest of the feasible algorithms, as SNOW 2.0 has been shown to have a security flaw. We also optimise the hardware implementation for the Virtex-5 field-programmable gate array (FPGA) and show two implementations. The first implementation is a rather straightforward optimisation and achieves 16,153 Mbps with 732 slices. In the second implementation, we duplicate the non-linear function using the structural advantage of KCipher-2 and we achieve 17,354 Mbps with 813 slices. Our implementation of KCipher-2 is around three times faster than those of the SNOW-family and efficiency, which is evaluated by “Throughput/Area (Mbps/slice)”, is 3.6-times better than that of SNOW 2.0 and 8.5-times better than that of SNOW 3G. These syntheses are performed using Xilinx ISE version 12.4.

Oblivious RAM (ORAM) schemes, the concept introduced by Goldreich and Ostrovsky, are very useful technique for protecting users' privacy when storing data in remote untrusted servers and running software on untrusted systems. However they are usually considered impractical due to their huge overhead. In order to reduce overhead, many improvements have been presented. Thanks to these improvements, ORAM schemes can be considered practical on cloud environment where users can expect huge storage and high computational power. Especially for private information retrieval (PIR), some literatures demonstrated they are usable. Also dedicated PIRs have been proposed and shown that they are usable in practice. Yet, they are still impractical for protecting software running on untrusted systems. We first survey recent researches on ORAM and PIR. Then, we present a practical software-based memory protection scheme applicable to several environments. The main feature of our scheme is that it records the history of accesses and uses the history to hide the access pattern. We also address implementing issues of ORAM and propose practical solutions for these issues.

We propose a new lattice-based digital signature scheme MLWRSign by modifying Dilithium, which is one of the second-round candidates of NIST's call for post-quantum cryptographic standards. To the best of our knowledge, our scheme MLWRSign is the first signature scheme whose security is based on the (module) learning with rounding (LWR) problem. Due to the simplicity of the LWR, the secret key size is reduced by approximately 30% in our scheme compared to Dilithium, while achieving the same level of security. Moreover, we implemented MLWRSign and observed that the running time of our scheme is comparable to that of Dilithium.

The hardness in solving the shortest vector problem (SVP) is a fundamental assumption for the security of lattice-based cryptographic algorithms. In 2010, Micciancio and Voulgaris proposed an algorithm named the Gauss Sieve, which is a fast and heuristic algorithm for solving the SVP. Schneider presented another algorithm named the Ideal Gauss Sieve in 2011, which is applicable to a special class of lattices, called ideal lattices. The Ideal Gauss Sieve speeds up the Gauss Sieve by using some properties of the ideal lattices. However, the algorithm is applicable only if the dimension of the ideal lattice n is a power of two or n+1 is a prime. Ishiguro et al. proposed an extension to the Ideal Gauss Sieve algorithm in 2014, which is applicable only if the prime factor of n is 2 or 3. In this paper, we first generalize the dimensions that can be applied to the ideal lattice properties to when the prime factor of n is derived from 2, p or q for two primes p and q. To the best of our knowledge, no algorithm using ideal lattice properties has been proposed so far with dimensions such as: 20, 44, 80, 84, and 92. Then we present an algorithm that speeds up the Gauss Sieve for these dimensions. Our experiments show that our proposed algorithm is 10 times faster than the original Gauss Sieve in solving an 80-dimensional SVP problem. Moreover, we propose a rotation-based Gauss Sieve that is approximately 1.5 times faster than the Ideal Gauss Sieve.

The Blum-Kalai-Wasserman algorithm (BKW) is an algorithm for solving the learning parity with noise problem, which was then adapted for solving the learning with errors problem (LWE) by Albrecht et al. Duc et al. applied BKW also to the learning with rounding problem (LWR). The number of blocks is a parameter of BKW. By optimizing the number of blocks, we can minimize the time complexity of BKW. However, Duc et al. did not derive the optimal number of blocks theoretically, but they searched for it numerically. Duc et al. also showed that the required number of samples for BKW for solving LWE can be dramatically decreased using Lyubashevsky's idea. However, it is not shown that his idea is also applicable to LWR. In this paper, we theoretically derive the asymptotically optimal number of blocks, and then analyze the minimum asymptotic time complexity of the algorithm. We also show that Lyubashevsky's idea can be applied to LWR-solving BKW, under a heuristic assumption that is regularly used in the analysis of LPN-solving BKW. Furthermore, we derive an equation that relates the Gaussian parameter σ of LWE and the modulus p of LWR. When σ and p satisfy the equation, the asymptotic time complexity of BKW to solve LWE and LWR are the same.

Password-based authenticated key exchange protocols are more convenient and practical, since users employ human-memorable passwords that are simpler to remember than cryptographic secret keys or public/private keys. Abdalla, Fouque, and Pointcheval proposed the password-based authenticated key exchange protocol in a 3-party model (GPAKE) in which clients trying to establish a secret do not share a password between themselves but only with a trusted server. On the other hand, Canetti presented a general framework, which is called universally composable (UC) framework, for representing cryptographic protocols and analyzing their security. In this framework, the security of protocols is maintained under a general protocol composition operation called universal composition. Canetti also proved a UC composition theorem, which states that the definition of UC-security achieves the goal of concurrent general composition. A server must manage all the passwords of clients when the 3-party password-based authenticated key exchange protocols are realized in large-scale networks. In order to resolve this problem, we propose a hierarchical hybrid authenticated key exchange protocol (H2AKE). In H2AKE, forwarding servers are located between each client and a distribution server, and the distribution server sends the client an authentication key via the forwarding servers. In H2AKE, public/private keys are used between servers, while passwords are also used between clients and forwarding servers. Thus, in H2AKE, the load on the distribution server can be distributed to the forwarding servers concerning password management. In this paper, we define hierarchical hybrid authenticated key exchange functionality. H2AKE is the universal form of the hierarchical (hybrid) authenticated key exchange protocol, which includes a 3-party model, and it has the characteristic that the construction of the protocol can flexibly change according to the situation. We also prove that H2AKE is secure in the UC framework with the security-preserving composition property.

Privacy remains an issue for IT services. Users are concerned that their history of service use may be traceable since each user is assigned a single identifier as a means of authentication. In this paper, we propose a perfectly anonymous attribute authentication scheme that is both unidentifiable and untraceable. Then, we present the evaluation results of a prototype system using a PC and mobile phone with the scheme. The proposed scheme employs a self-blindable certificate that a user can change randomly; thus the certificate is modified for each authentication, and the authentication scheme is unidentifiable and untraceable. Furthermore, our scheme can revoke self-blindable certificates without leaks of confidential private information and check the revocation status without online access.

This paper proposes a ternary subset difference method (SD method) that is resistant to coalition attacks. In order to realize a secure ternary SD method, we design a new cover-finding algorithm, label assignment algorithm and encryption algorithm. These algorithms are required to revoke one or two subtrees simultaneously while maintaining resistance against coalition attacks. We realize this two-way revocation mechanism by creatively using labels and hashed labels. Then, we evaluate the efficiency and security of the ternary SD method. We show that the number of labels on each client device can be reduced by about 20.4 percent. The simulation results show that the proposed scheme reduces the average header length by up to 15.0 percent in case where the total number of devices is 65,536. On the other hand, the computational cost imposed on a client device stays within O(log n). Finally, we prove that the ternary SD method is secure against coalition attacks.

Pairing based cryptosystems can accomplish novel security applications such as ID-based cryptosystems, which have not been constructed efficiently without the pairing. The processing speed of the pairing based cryptosystems is relatively slow compared with the other conventional public key cryptosystems. However, several efficient algorithms for computing the pairing have been proposed, namely Duursma-Lee algorithm and its variant ηT pairing. In this paper, we present an efficient implementation of the pairing over some mobilephones. Moreover, we compare the processing speed of the pairing with that of the other standard public key cryptosystems, i.e. RSA cryptosystem and elliptic curve cryptosystem. Indeed the processing speed of our implementation in ARM9 processors on BREW achieves under 100 milliseconds using the supersingular curve over F397. In addition, the pairing is more efficient than the other public key cryptosystems, and the pairing can be achieved enough also on BREW mobilephones. It has become efficient enough to implement security applications, such as short signature, ID-based cryptosystems or broadcast encryption, using the pairing on BREW mobilephones.