<title>Abstract</title><sec>
<title>Background</title>
Proteins are integral part of all living beings, which are building blocks of many amino acids. To be functionally active, amino acids chain folds up in a complex way to give each protein a unique 3D shape, where a minor error may cause misfolded structure. Genetic disorder diseases i.e. <italic>Alzheimer, Parkinson,</italic> etc. arise due to misfolding in protein sequences. Thus, identifying patterns of amino acids is important for inferring protein associated genetic diseases. Recent studies in predicting amino acids patterns focused on only simple protein misfolded disease i.e. <italic>Chromaffin Tumor</italic>, by association rule mining. However, more complex diseases are yet to be attempted. Moreover, association rules obtained by these studies were not verified by usefulness measuring tools.



</sec><sec>
<title>Results</title>
In this work, we analyzed protein sequences associated with complex protein misfolded diseases (i.e. <italic>Sickle Cell Anemia, Breast Cancer, Cystic Fibrosis, Nephrogenic Diabetes Insipidus,</italic> and <italic>Retinitis Pigmentosa 4</italic>) by association rule mining technique and objective interestingness measuring tools. Experimental results show the effectiveness of our method.


</sec><sec>
<title>Conclusion</title>
Adopting quantitative experimental methods, this work can form more reliable, useful and strong association rules i. e. dominating patterns of amino acid of complex protein misfolded diseases. Thus, in addition to usual applications, the identified patterns can be more useful in discovering medicines for protein misfolded diseases and thereby may open up new opportunities in medical science to handle genetic disorder diseases.


</sec>

Foggy images suffer from low contrast and poor visibility problem along with little color information of the scene. It is imperative to remove fog from images as a pre-processing step in computer vision. The Dark Channel Prior (DCP) technique is a very promising defogging technique due to excellent restoring results for images containing no homogeneous region. However, having a large homogeneous region such as sky region, the restored images suffer from color distortion and block effects. Thus, to overcome the limitation of DCP method, we introduce a framework which is based on sky and non-sky region segmentation and restoring sky and non-sky parts separately. Here, isolation of the sky and non-sky part is done by using a binary mask formulated by floodfill algorithm. The foggy sky part is restored by using Contrast Limited Adaptive Histogram Equalization (CLAHE) and non-sky part by modified DCP. The restored parts are blended together for the resultant image. The proposed method is evaluated using both synthetic and real world foggy images against state of the art techniques. The experimental result shows that our proposed method provides better entropy value than other stated techniques along with have better natural visual effects while consuming much lower processing time.

© 2019, Springer Nature Switzerland AG. Secure Message Transmission (SMT) is a two-party protocol by which the sender can privately transmit a message to the receiver through multiple channels. An adversary can corrupt a subset of channels and makes eavesdropping and tampering over the corrupted channels. Fujita et al. (GameSec 2018) introduced a game-theoretic security notion of SMT, and showed protocols that are secure even if an adversary corrupts all but one of the channels, which is impossible in the standard cryptographic setting. In this work, we study a game-theoretic setting in which all the channels are corrupted by two or more independent adversaries. Specifically, we assume that there are several adversaries who exclusively corrupt subsets of the channels, and prefer to violate the security of SMT with being undetected. Additionally, we assume that each adversary prefers other adversaries’ tampering to be detected. We show that secure SMT protocols can be constructed even if all the channels are corrupted by such rational adversaries. We also study the situation in which both malicious and rational adversaries exist.

© 2018, Springer Nature Switzerland AG. Secure Message Transmission (SMT) is a two-party cryptographic protocol by which the sender can securely and reliably transmit messages to the receiver using multiple channels. It is assumed that an adversary corrupts a subset of the channels, and makes eavesdropping and tampering over the corrupted channels. In this work, we consider a game-theoretic security model for SMT. Specifically, we introduce a rational adversary who has the preference for the outcome of the protocol execution. We show that, under some reasonable assumption on the adversary’s preference, even if the adversary corrupts all but one of the channels, it is possible to construct SMT protocols with perfect security against rational adversaries. More specifically, we consider “timid” adversaries who prefer to violate the security requirement of SMT, but do not prefer the tampering actions to be detected. In the traditional cryptographic setting, perfect SMT can be constructed only when the adversary corrupt a minority of the channels. Our results demonstrate a way of circumventing the impossibility results of cryptographic protocols based on a game-theoretic approach.

In this paper, we review the problem of private batch equality test (PriBET) that was proposed by Saha and Koshiba (3rd APWConCSE 2016). They described this problem to find the equality of an integer within a set of integers between two parties who do not want to reveal their information if they do not equal. For this purpose, they proposed the PriBET protocol along with a packing method using the binary encoding of data. Their protocol was secured by using ring-LWE based somewhat homomorphic encryption (SwHE) in the semi-honest model. But this protocol is not fast enough to address the big data problem in some practical applications. To solve this problem, we propose a base-N fixed length encoding based PriBET protocol using SwHE in the same semi-honest model. Here we did our experiments for finding the equalities of 8–64-bit integers. Furthermore, our experiments show that our protocol is able to evaluate more than one million (resp. 862 thousand) of equality comparisons per minute for 8-bit (resp. 16-bit) integers with an encoding size of base 256 (resp. 65536). Besides, our protocol works more than 8–20 in magnitude than that of Saha and Koshiba.

We demonstrate physical implementation of information-theoretic secure oblivious transfer based on bounded observability using optical correlated randomness in semiconductor lasers driven by common random light broadcast over optical fibers. We demonstrate that the scheme can achieve one-out-of-two oblivious transfer with effective key generation rate of 110 kb/s. The results show that this scheme is a promising approach to achieve information-theoretic secure oblivious transfer over long distances for future applications of secure computation such as privacy-preserving database mining, auctions and electronic-voting.

Short Message Service (SMS) is one of the most popular services in the Global System for Mobile (GSM) and many challenges for security arise from the development of message transmission among the broadband network. Recently, an interesting technique called signcryption has been proposed, in which both the properties of signature (ownership) and encryption are simultaneously implemented, with better performance than the traditional signature-then-encryption approach. For the secure mobile computing, we propose a new method for two groups of users that send encrypted signed data by using SMS. We propose a new primitive called verifiable hash convergent group signcryption (VHCGS) by adding the properties of group signcryption and the verification facilities for the third party called the service provider. This research targets toward the type of applications in mobile computing and communication device concerning about SMS.

We propose two secure protocols namely private equality test (PET) for single comparison and private batch equality test (PriBET) for batch comparisons of l-bit integers. We ensure the security of these secure protocols using somewhat homomorphic encryption (SwHE) based on ring learning with errors (ring-LWE) problem in the semi-honest model. In the PET protocol, we take two private integers input and produce the output denoting their equality or non-equality. Here the PriBET protocol is an extension of the PET protocol. So in the PriBET protocol, we take single private integer and another set of private integers as inputs and produce the output denoting whether single integer equals at least one integer in the set of integers or not. To serve this purpose, we also propose a new packing method for doing the batch equality test using few homomorphic multiplications of depth one. Here we have done our experiments at the 140-bit security level. For the lattice dimension 2048, our experiments show that the PET protocol is capable of doing any equality test of 8-bit to 2048-bit that require at most 107 milliseconds. Moreover, the PriBET protocol is capable of doing about 600 (resp., 300) equality comparisons per second for 32-bit (resp., 64-bit) integers. In addition, our experiments also show that the PriBET protocol can do more computations within the same time if the data size is smaller like 8-bit or 16-bit.

In PKC 2014, Langlois et al. proposed the first lattice-based group signature scheme with the verifier-local revocability. The security of their scheme is selfless anonymity, which is weaker than the security model defined by Bellare, Micciancio and Warinschi (EUROCRYPT 2003). By using the technique in the group signature scheme proposed by Ling et al. ( PKC 2015), we propose a group signature scheme with the verifier-local revocability. For the security discussion of our scheme, we adapt the BMW03 model to cope with revocation queries, since the BMW03 model is for static groups. Then, we show that our scheme achieves the full anonymity in the adapted BMW03 model.

We consider secure pattern matching for some alphabet set, where gaps are represented by the character '*'. Generally, we know that a wildcard character '*' in the pattern is used to replace zero or more letters in the text. Yasuda et al. (ACISP 2014) proposed a new packing method for somewhat homomorphic encryption for handling wildcards pattern where the wildcards replace one letter in the text. We extend the secure pattern matching so that the wildcards are replaced with any sequences. We propose a method for privacy-preserving wildcards pattern matching using somewhat homomorphic encryption in the semi-honest model. At the same time, we also propose another packing method for executing homomorphic operations between plaintext and encrypted wildcards pattern in three homomorphic multiplications rather than 3k multiplications required by Yasuda et al. method to handle k sub-patterns. Moreover, we have been able to improve the communication complexity of Yasuda et al. method by a factor k denoting the total number of sub-patterns appearing in the pattern. In addition, our practical implementation shows that our method is about k-times faster than that of Yasuda et al. Here, we show some applications of our packing method to computing secure Hamming and Euclidean distances.

Multiple group setting schemes have recently become important for enabling deduplication for cloud servers. We consider a new primitive, cross-group deduplication, allowing the multiple groups by the group signature features. We propose a new framework DDUP-MUG (deduplication for the multiple-group signature scheme) that allows one or more groups to access a file such that the cloud storage server can avoid duplicates according to the ownership of the file. The main goal of the primitive is allowing to multiple groups with individual management and several clients from different groups who attempt to store an identical message on the server. In this paper, the group managers mainly manage the new entities and produce revocation lists for clients and the server respectively. We use Message Lock Encryption (MLE) as an ingredient for deduplication and we provide new three protocols, namely UPL-Dup (for uploading a new message), EDT-Dup (for editing the existing message) and DEL-Dup (for eliminating the existing message) in the DDUP-MUG framework.

In this paper, we propose an efficient protocol to process a private conjunctive query over encrypted data in the cloud using the somewhat homomorphic encryption (SwHE) scheme with a batch technique. In 2016, Cheon, Kim, and Kim (CKK) [IEEE Trans. Inf. Forensics Security] showed conjunctive query processing over encrypted data using search-and-compute circuits and an SwHE scheme and mentioned that their scheme should be improved in performance. To improve the performance of processing a private conjunctive query, we also propose a new packing method to support an efficient batch computation for our protocol using a few multiplications. Our implementation shows that our protocol works more than 50 times as fast as the CKK protocol for conjunctive query processing. In addition, the security level of our protocol is better than the security level of the CKK protocol.

As Big Data cloud storage servers are becoming popular the shortage of disk space in the cloud becomes a problem. Data deduplication is a method to control the explosion growth of data on the cloud and most of the storage providers are finding more secure and efficient methods for their sensitive data. Recently, an interesting technique called signcryption has been proposed, in which both the properties of signature (ownership) and encryption are simultaneously implemented, with better performance than the traditional signature-then-encryption approach. According to the deduplication, we introduce a new method for a group of users that can eliminate redundant encrypted data owned by different users. Furthermore, we generate the tag which will be the key component of big data management. We propose a new primitive group signcryption for deduplication called verifiable hash convergent group signcryption (VHCGS) by adding the properties of group signcryption and the verification facilities for the storage server (third party).

We consider the problem of processing private database queries over encrypted data in the cloud. To do this, we propose a protocol for conjunctive query and another for disjunctive query processing using somewhat homomorphic encryption in the semi-honest model. In 2016, Kim et al. [IEEE Trans. on Dependable and Secure Comput.] showed an FHE-based query processing with equality conditions over encrypted data. We improve the performance of processing private conjunctive and disjunctive queries with the low-depth equality circuits than Kim et al.’s circuits. To get the low-depth circuits, we modify the packing methods of Saha and Koshiba [APWConCSE 2016] to support an efficient batch computation for our protocols with a few multiplications. Our implementation shows that our protocols work faster than Kim et al.’s protocols for both conjunctive and disjunctive query processing along with a better security level. We are also able to provide security to both attributes and values appeared in the predicate of the conjunctive and disjunctive queries whereas Kim et al. provided the security to the values only.

With the widespread development of biometrics, concerns about security and privacy are increasing. In biometrics, template protection technology aims to protect the confidentiality of biometric templates (i.e., enrolled biometric data) by certain conversion. The fuzzy commitment scheme gives a practical way to protect biometric templates using a conventional error-correcting code. The scheme has both concealing and binding of templates, but it has some privacy problems. Specifically, in case of successful matching, stored biometric templates can be revealed. To address such problems, we improve the scheme. Our improvement is to coat with two error-correcting codes. In particular, our scheme can conceal stored biometric templates even in successful matching. Our improved scheme requires just conventional error-correcting codes as in the original scheme, and hence it gives a practical solution for both template security and privacy of biometric templates.

Somewhat homomorphic encryption is public key encryption supporting a limited number of both additions and multiplications on encrypted data, which is useful for performing fundamental computations with protecting the data confidentiality. In this paper, we focus on the scheme proposed by Lauter, Naehrig and Vaikuntanathan (ACM CCSW 2011), and present two types of packed ciphertexts based on their packing technique. Combinations of two types of our packing method give practical size and performance for wider computations such as statistical analysis and distances. To demonstrate its efficiency, we implemented the scheme with our packing method for secure Hamming distance, which is often used in privacy-preserving biometrics. For secure Hamming distance between two binary vekoshiba@mail.saitama-u.ac.jpctors of 2048-bit, it takes 5.31ms on an Intel Xeon X3480 at 3.07 GHz. This gives the best performance in the state-of-the-art work using homomorphic encryption.

The basic pattern matching problem is to find the locations where a pattern occurs in a text. We give several computations enabling a client to obtain matching results from a database so that the database can not learn any information about client's queried pattern. For such computations, we apply the symmetric-key variant scheme of somewhat homomorphic encryption proposed by Brakerski and Vaikuntanathan (CRYPTO 2011), which can support a limited number of both polynomial additions and multiplications on encrypted data. We also utilize the packing method introduced by Yasuda et al. (CCSW 2013) for efficiency. While they deal with only basic problems for binary vectors, we address more complex problems such as the approximate and wildcards pattern matching for non-binary vectors. To demonstrate the efficiency of our method, we implemented the encryption scheme for secure wildcards pattern matching of DNA sequences. Our implementation shows that a client can privately search real-world genomes of length 16,500 in under one second on a general-purpose PC.

Blind quantum computation is a new quantum secure protocol, which enables Alice who does not have enough quantum technology to delegate her computation to Bob who has a fully fledged quantum power without revealing her input, output, and algorithm. So far, blind quantum computation has been considered only for the circuit model and the measurement-based model. Here we consider the possibility and the limitation of blind quantum computation in the ancilla-driven model, which is a hybrid of the circuit and the measurement-based models.

We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is "secure" against any polynomial-time quantum adversary. Our problem, QSCD(ff), is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show that QSCD(ff) has three properties of cryptographic interest: (i) QSCD(ff) has a trapdoor; (ii) the average-case hardness of QSCD(ff) coincides with its worst-case hardness; and (iii) QSCD(ff) is computationally at least as hard as the graph automorphism problem in the worst case. These cryptographic properties enable us to construct a quantum public-key cryptosystem which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCD(ff), called QSCD(cyc), and introduce a multi-bit encryption scheme that relies on similar cryptographic properties of QSCD(cyc).

Secure message transmission (SMT) is a two-party protocol between a sender and a receiver over a network in which the sender and the receiver are connected by 71 disjoint channels and t out of n channels can be controlled by an adaptive adversary with unlimited computational resources. If a public discussion channel is available to the sender and the receiver to communicate with each other then a secure and reliable communication is possible even when n &gt;= t + 1. The round complexity is one of the important measures for the efficiency for SMT. In this paper, we revisit the optimality and the impossibility for SMT with public discussion and discuss the limitation of SMT with the "unidirectional" public channel, where either the sender or the receiver can invoke the public channel, and show that the "bidirectional" public channel is necessary for SMT.

We provide a quantum bit commitment scheme which has statistically-hiding and computationally-binding properties from any approximable-preimage-size quantum one-way function, which is a generalization of perfectly-hiding quantum bit commitment scheme based on quantum one-way permutation due to Dumais, Mayers and Salvail. in the classical case, statistically-hiding bit commitment scheme is constructible from any one-way function. However, it is known that the round complexity of the classical statistically-hiding bit commitment scheme is Omega(n/ log n) for the security parameter n. Our quantum scheme as well as the Dumais-Mayers-Salvail scheme is non-interactive, which is advantageous over the classical schemes.

We study the distributed oblivious transfer first proposed by Naor and Pinkas in ASIACRYPT 2000, and generalized by Blundo et al. originally in SAC 2002 and Nikov et al. in INDOCRYPT 2002. One major objective of distributed oblivious transfer is to achieve information theoretic security under specified conditions through the distribution of the functions of traditional oblivious transfer to a set of neutral parties. In this paper we revise the definition of distributed oblivious transfer in order to deal with stronger adversaries and clarify possible ambiguities. Under the new definition, we observe some impossibility results and derive the tipper bounds for the system parameters (with respect to the size of coalition). The weak points of previously proposed schemes based on threshold secret sharing schemes using polynomial interpolation are reviewed and resolved. We generalize the results and prove that, by adjusting some technical details, a previous scheme proposed by Nikov et al. is unconditionally secure. This protocol is efficient and achieves the parameter bounds at the same time.

Reducing the minimum assumptions needed to construct various cryptographic primitives is an important and interesting task in theoretical cryptography Oblivious transfer, one of the most basic cryptographic building blocks, could be also studied under this scenario. Reducing the minimum assumptions for oblivious transfer seems not an easy task, as there are a few impossibility results under black-box reductions
Until recently, it is widely believed that oblivious transfer Can he constructed with trapdoor permutations Goldrech pointed out some flaw in the folklore and introduced some enhancement to cope with the flaw Haitner then revised the enhancement more properly. As a consequence they showed that some additional properties for trapdoor permutations are necessary to construct oblivious transfers In this paper, we discuss possibilities of basing not on trapdoor permutations but on trapdoor functions in general We generalize previous results and give an oblivious transfer protocol based on a collection of trapdoor functions with some extra properties with respect to the length-expansion and the pre- image size. We discuss that our reduced assumption is almost minimal and show the necessity for the extra properties.

Consider the scenario where we are given an ideal functionality of oblivious transfer (OT), and we wish to construct a larger OT by invoking the above functionality as a black box. How many invocations of an ideal OT functionality are necessary? In tackling this problem, some lower bounds were derived using entropy previously. In this paper, we manage to achieve tighter lower bounds by employing a combinatorial approach. This new approach yields lower bounds which are two times larger than the existing bounds. © 2008 IEEE.

It is known that string (1, 2)-OT and Rabin's OT are equivalent. Actually, there have been many reductions between them. Many of them use the privacy amplification technique as a basic tool. The privacy amplification technique essentially involves some post-processing of sending random objects (e.g., random indices of pairwise independent hash functions) per each invocation of Rabin's OT is necessary. In this paper, we show a simple direct reduction of string (1, 2)-OT to Rabin's OT by using a deterministic randomness extractor for bit-fixing sources. Our reduction can be realized without privacy amplification and thus our protocol is simpler and more efficient with respect to the communication complexity than the previous reductions.

Recently, a public-key cryptosystem based on Cheby-shev polynomials has been proposed, but it has been later analyzed and shown insecure. This paper addresses some unanswered questions about the cryptosystem. We deal with the issue of computational precision. This is important for two reasons. Firstly, the cryptosystem is defined on. real numbers, but any practical data communication channel can only transmit a limited number of digits. Any real number can only be specified to some precision level, and we study the effect of that. Secondly, we show that the precision issue is related to its security. In particular, the algorithm previously proposed to break the cryptosystem may not work in some situations. Moreover, we introduce another method to break the cryptosystem with general precision settings. We extend the method to show that a certain class of cryptosystems is insecure. Our method is based on the known techniques on the shortest vector problem in lattice and linear congruences.

The low-density attack proposed by Lagarias and Odlyzko is a powerful algorithm against the subset sum problem. The improvement algorithm due to Coster et al. would solve almost all the problems of density < 0.9408... in the asymptotical sense. On the other hand, the subset sum problem itself is known as an NP-hard problem, and a lot of efforts have been paid to establish public-key cryptosystems based on the problem. In these cryptosystems, densities of the subset sum problems should be higher than 0.9408... in order to avoid the low-density attack. For example, the Chor-Rivest cryptosystem adopted subset sum problems with relatively high densities. In this paper, we further improve the low-density attack by incorporating an idea that integral lattice points can be covered with polynomially many spheres of shorter radius and of lower dimension. As a result, the success probability of our attack can be higher than that of Coster et al.'s attack for fixed dimensions. The density bound is also improved for fixed dimensions. Moreover, we numerically show that our improved low-density attack makes the success probability higher in case of low Hamming weight solution, such as the Chor-Rivest cryptosystem, if we assume SVP oracle calls.

Shor's algorithms for the integer factorization and the discrete logarithm problems can be regarded as a negative effect of the quantum mechanism on public-key cryptography. From the computational point of view, his algorithms illustrate that quantum computation could be more powerful. It is natural to consider that the power of quantum computation could be exploited to withstand even quantum adversaries. Over the last decade, quantum cryptography has been discussed and developed even from the computational complexity-theoretic point of view. In this paper, we will survey what has been studied in quantum computational cryptography.

The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, although the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we affirmatively settle their conjecture and complete a necessary and sufficient condition for quantum one-way permutations. The necessary and sufficient condition can be regarded as a universal test for quantum one-way permutations, since the condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators. (c) 2005 Published by Elsevier B.V.

We introduce a problem of distinguishing between two quantum states as a new underlying problem to build a computational cryptographic scheme that is "secure" against quantum adversary. Our problem is a natural generalization of the distinguishability problem between two probability distributions, which are commonly used in computational cryptography. More precisely, our problem QSCD(ff) is the computational distinguishability problem between two types of random coset states with a hidden permutation over the symmetric group. We show that (i) QSCD(ff) has the trapdoor property; (ii) the average-case hardness of QSCD(ff) coincides with its worst-case hardness; and (iii) QSCD(ff) is at least as hard in the worst case as the graph automorphism problem. Moreover, we show that QSCD(ff) cannot be efficiently solved by any quantum algorithm that naturally extends Shor's factorization algorithm. These cryptographic properties of QSCD(ff) enable us to construct a public-key cryptosystem, which is likely to withstand any attack of a polynomial-time quantum adversary.

In this paper, we give a theoretical analysis of chi(2) attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose a method of security evaluation against chi(2) attack precisely including key dependency by introducing a method "Transition Matrix Computing." Previously, no theoretical security evaluation against chi(2) attack was known, it has been done by computer experiments. We should note that it is the first result concerning the way of security evaluation against chi(2) attack is shown theoretically.

The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, though the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we relax their sufficient condition and give a new condition that is necessary and sufficient for quantum one-way permutations. Our condition can be regarded as a universal test for quantum one-way permutations, since our condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators.

In this paper, we study short exponent Diffie-Hellman problems, where significantly many lower bits are zeros in the exponent. We first prove that the decisional version of this problem is as hard as two well known hard problems, the standard decisional Diffie-Hellman problem (DDH) and the short exponent discrete logarithm problem. It implies that we can improve the efficiency of ElGamal scheme and Cramer-Shoup scheme under the two widely accepted assumptions. We next derive a similar result for the computational version of this problem.

In this paper, we give a theoretical analysis Of chi(2) attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose the method of security evaluation against chi(2) attack precisely including key dependency by introducing a method "Transition Matrix Computing." Previously, no theoretical security evaluation against chi(2) attack was known, it has been done by computer experiments. We should note that this is the first results that a theoretical evaluation against chi(2) attack is shown.

In this paper, we apply multiple linear cryptanalysis to a reduced round RC6 block cipher. We show that 18-round RC6 with weak key is breakable by using the multiple linear attack.

In this paper, we consider what condition is sufficient for random inputs to secure probabilistic public-key encryption schemes. Although a framework given in [16] enables us to discuss uniformly and comprehensively security notions of public-key encryption schemes even for the case where cryptographically weak pseudorandom generator is used as random nonce generator to encrypt single plaintext messages, the results are rather theoretical. Here we naturally generalize the framework in order to handle security for the situation where we want to encrypt many messages with the same key. We extend some results w.r.t. single message security in [16] – separation results between security notions and a non-trivial sufficient condition for the equivalence between security notions – to multiple messages security. Besides the generalization, we show another separation between security notions for k-tuple messages and for (k+1)-tuple messages. The natural generalization, obtained here, rather improves to understand the security of public-key encryption schemes and eases the discussion of the security of practical public-key encryption schemes. In other words, the framework contributes to elucidating the role of randomness in public-key encryption scheme. As application of results in the generalized framework, we consider compatibility between the ElGamal encryption scheme and some sequence generators. Especially, we consider the applicability of the linear congruential generator (LCG) to the ElGamal encryption scheme.

This paper examines similarities between the Decision Diffie-Hellman (DDH) assumption and the Quadratic Residuosity (QR) assumption. In addition, we show that many cryptographic protocols based on the QR assumption can be reconstructed using the DDH assumption.

In this paper, we introduce a framework in which we can uniformly and comprehensively discuss security notions of public-key encryption schemes even for the case where some weak generator producing seemingly random sequences is used to encrypt plaintext messages. First, we prove that indistinguishability and semantic security are not equivalent in general. On the other hand, we derive some sufficient condition for the equivalence and show that polynomial-time pseudo-randomness is not always necessary for the equivalence.

Two quantum finite automata are equivalent if for any string x the two automata accept x with equal probability. This paper gives a polynomial-time algorithm for determining whether two measure-once one-way quantum finite automata are equivalent. The paper also gives a polynomial-time algorithm for determining whether two measure-many one-way quantum finite automata are equivalent.

There are many public key cryptosystems that require random inputs to encrypt messages and their security is always discussed assuming that random objects are ideally generated. Since cryptosystems run on computers, it is quite natural that these random objects are computationally generated. One theoretical solution is the use of pseudorandom generators in the Yao's sense [16]. Informally saying, the pseudorandom generators are polynomial-time algorithms whose outputs are computationally indistinguishable from the uniform distribution. Since if we use the Yao's generators then it takes much more time to generate pseudorandom objects than to encrypt messages in public key cryptosystems, we relax the conditions of pseudorandom generators to fit public key cryptosystems and give a minimal requirement for pseudorandom generators within public key cryptosystems. As an example, we discuss the security of the El-Gamal cryptosystem [7] with some well-known generators (e.g., the linear congruential generator). We also propose a new pseudorandom number generator, for random inputs to the ElGamal cryptosystem, that satisfies the minimal requirement. The newly proposed generator is based on the linear congruential generator. We show some evidence that the ElGamal cryptosystem with the proposed generator is secure.

In this paper, we show a practical solution to the problems where one-wayness of hash functions does not guarantee cryptographic systems to be secure enough. We strengthen the notion of one-wayness of hash functions and construct strongly one-way hash functions from any one-way hash function or any one-way function.

The D-ABDUCTOR system was originally developed as a diagram-based idea organizer with facilities for visualization and manipulation of a large class of graphs. It has since been enhanced to improve its extensibility, and now function exchange-ability, functional independence, and configurability without programming have become important features. The enhanced system and its features are illustrated with several examples of its application.

We consider the problem of learning deterministic even linear languages from positive examples, We show that, for any nonnegative integer k, the class of LR(k) even linear languages is not learnable from positive examples while there is a subclass called LRS(k), which is a natural subclass of LR(k) in the strong sense, learnable from positive examples. Our learning algorithm identifies this subclass in the limit with almost linear time in updating conjectures. As a corollary, in terms of even linear grammars, we have a learning algorithm for k-reversible languages that is more efficient than the one proposed by Angluin.

The rapid growth of data in large databases, such as text databases and scientific databases, requires efficient computer methods for automating analyses of the data with the goal of acquiring knowledges or making discoveries. Because the analyses of data are generally so expensive, most parts in databases remains as raw, unanalyzed primary data. Technology from machine learning (ML) will offer efficient tools for the intelligent analyses of the data using generalization ability. Generalization is an important ability specific to inductive learning that will predict unseen data with high accuracy based on learned concepts from training examples.
In this article, we apply ML to text-database analyses and knowledge acquisitions from text databases. We propose a completely new approach to the problem of text classification and extracting keywords by using ML techniques. We introduce a class of representations for classifying text data based on decision trees; (i.e., decision trees over attributes on strings) and present an algorithm for learning them inductively. Our algorithm has the following features: It does not need any natural language processing technique and it is robust for noisy data. We show that our learning algorithm can be used for automatic extraction of keywords for text retrieval and automatic text categorization. We also demonstrate some experimental results using our algorithm on the problem of classifying bibliographic data and extracting keywords in order to show the effectiveness of our approach.

In this paper, we introduce the notion of the local strategy of constructing decision trees that includes the information theoretic entropy algorithm in ID3 (or C4.5) and any other local algorithms. Simply put, given a sample, a local algorithm constructs a decision tree in the top-down manner using an evaluation function. We propose a new local algorithm that is very different from the entropy algorithm. We analyze behaviors of the two algorithms on a simple model. Based on these analyses, we propose a learning system of decision trees which can change an evaluation function while constructing decision trees, and verify the effect of the system by experiments with real databases. The system not only achieves a high accuracy, but also produces well-balanced decision trees, which have the advantage of fast classification.

We investigated computational problems studied in the statistical physics for developing a new approach in computational complexity theory. We examined a framework proposed in the statistical physics for understanding the computational hardness transition phenomena, and we discovered and mathematically proved a new type of hardness transition, which lead us to propose a new and robust framework for investigating the computational hardness transitions. This framework can be used as a new basis of discussing the security of cryptographic primitives. We also studied the structure of solutions and the number of solutions of various computational problems that have been discussed in the statistical physics, and found several fundamental properties for developing efficient algorithms for solving these problems.

We propose a generalized model of quantum interactive proof systems and show the existence of complete problems and a quantum version of Babai's collapse theorem. We construct efficient quantum algorithms for matrix multiplication of semi-rings and for finding triangles in graphs and develop their analysis to obtain their quantum distribution protocols. In ancilla-driven model where computation systems and measurement systems are separable, we show that quantum blind computation is achievable. We characterize a classical computational complexity class AWPP, which corresponds to a quantum computational complexity class BQP, by using the notion of post-selection. We give a natural reason why AWPP is the tightest upper bound of BQP and develop a quantum complexity theoretic approach to the study of AWPP.

We have studied quantum communication technology on a multi-user network. Especially, we have studied the information theoretic security based on quantum communication technology because its realization is not easy for existing communication technology. The information theoretic security is usually realized by privacy amplification based on a code. We have clarified the effect by the finiteness of the length of the code while it had not been studied sufficiently. Further, we have investigated the blind computation based on quantum communication, which enables the client to ask the server the difficult computation without informing the server the knowledge of the request, whose security can be guaranteed information theoretically. We have derived the formula for guaranteeing the correctness of the computation result with a given significance level.

Quantum blind computation can be discussed in the measurement-based quantum computation model. As a special case, ancilla-driven quantum computation is defined as computation where measurements are made only on the measurement system and computation is carried on the computational system and those two system are separated. In the ancilla-driven computation model, we derive sufficient conditions for the blindness and show a bind protocol. In cryptography, the universal composability guarantees that a prococol can be used as a part of larger cryptosystems. We show that Fujii-Morimae blind computation, where only the client makes measurements, is universally composable.

We developed useful techniques in quantum information theory and quantum computational complexity theory and applied them to interactive proof systems, cryptography, network theory and so on. With respect to quantum interactive proof systems, we investigated effects of quantum entanglements among multiple provers. Moreover, we considered the possibility of quantum communication in network coding and proposed efficient protocols. We proved the hard-core property of a function by the quantum computational complexity theory, while it had not been proved from the classical theory. Furthermore, we proposed several classical cryptographic protocols, which bring some ideas to quantum cryptography.

本研究課題では,アルゴリズム構築の新しいパラダイムとして「脱量子化手法」を確立することが目的であるが,前年度に着目した古典計算暗号技術でよく用いられているインタラクティブハッシングと呼ばれる技術とBB84量子鍵配送プロトコルで用いられているBB84量子状態との関係について,本年度はその応用研究を行った.両者の関係は量子化・脱量子化の関係にあり,まず,古典暗号理論における重要な定理の一つであるインタラクティブハッシュ定理の量子版として,非対話量子ハッシュ定理を導いた.これを応用し,量子一方向性関数に基づいて非対話形式の統計的秘匿性を持つ非対話の量子ビット委託プロトコルを構成することに成功した.古典暗号理論においては,ビット委託と紛失通信は大きく異なるプロトコルとして認識されているが,量子暗号においてはその親和性を示す状況証拠が得られていた.特に,F-束縛と呼ばれる特殊な束縛性を持つ文字列委託の存在を仮定した場合,量子紛失通信が得られることが知られており,F-束縛な文字列委託プロトコルをどのように構成すればよいのかは未解決問題のまま残されていた.量子一方向性関数に基づく非対話形式統計的秘匿ビット委託プロトコルを並列化することにより,F-束縛な文字列委託プロトコルを構成出来ることを示し,結果として,量子一方向性関数から量子紛失通信プロトコルを構成することに成功した.量子紛失通信は量子マルチパーティ計算につながると予想されるため,量子暗号理論においては量子一方向性関数の存在という妥当な仮定から高度な暗号プロトコルが構成できることを示唆するものとなっている.

We investigated the potential abilities of quantum information processing from the viewpoints of interactive proofs, theory of cryptography and algorithms. We showed that quantum entanglement is effective in multi-prover systems, proposed a non-interactive bit commitment scheme, and derived a limitation of quantum algorithms for the hidden subgroup problem.

Ring LWE (Learning With Error)問題に基づく準同型暗号に対してデータ符号化法を工夫することで，ベクトルを暗号化したままの状態で内積計算の高速計算を実現する方法（報告者の既存研究成果）がある。この技術を応用し，暗号化データベース内の複数データエントリに対して，論理和や論理積を用いて構造的な条件を満たすデータを高速に抽出できるような方法を開発し，従来手法と計算機比較実験をすることで新手法の実効性を実証した。