In recent years, neural networks and cryptographic schemes have come together in war and peace; a cross-impact that forms a dichotomy deserving a comprehensive review study. Neural networks can be used against cryptosystems; they can play roles in cryptanalysis and attacks against encryption algorithms and encrypted data. This side of the dichotomy can be interpreted as a war declared by neural networks. On the other hand, neural networks and cryptographic algorithms can mutually support each other. Neural networks can help improve the performance and the security of cryptosystems, and encryption techniques can support the confidentiality of neural networks. The latter side of the dichotomy can be referred to as the peace. There are, to the best of our knowledge, no current surveys that take a comprehensive look at the many ways neural networks are currently interacting with cryptography. This survey aims to fill that niche by providing an overview on the state of the cross-impact between neural networks and cryptography systems. To this end, this paper will highlight the current areas where progress is being made as well as the aspects where there is room for future research to be conducted.

Recently, many researchers have been interested in the application of chaos in cryptography. Specifically, numerous research works have been focusing on chaotic image encryption. A comprehensive survey can highlight existing trends and shed light on less-studied topics in the area of chaotic image encryption. In addition to such a survey, this paper studies the main challenges in this field, establishes an ecosystem for chaotic image encryption, and develops a future roadmap for further research in this area.

Due to the expansion of data generation, more and more natural language processing (NLP) tasks are needing to be solved. For this, word representation plays a vital role. Computation-based word embedding in various high languages is very useful. However, until now, low-resource languages such as Bangla have had very limited resources available in terms of models, toolkits, and datasets. Considering this fact, in this paper, an enhanced BanglaFastText word embedding model is developed using Python and two large pre-trained Bangla models of FastText (Skip-gram and cbow). These pre-trained models were trained on a collected large Bangla corpus (around 20 million points of text data, in which every paragraph of text is considered as a data point). BanglaFastText outperformed Facebook’s FastText by a significant margin. To evaluate and analyze the performance of these pre-trained models, the proposed work accomplished text classification based on three popular textual Bangla datasets, and developed models using various machine learning classical approaches, as well as a deep neural network. The evaluations showed a superior performance over existing word embedding techniques and the Facebook Bangla FastText pre-trained model for Bangla NLP. In addition, the performance in the original work concerning these textual datasets provides excellent results. A Python toolkit is proposed, which is convenient for accessing the models and using the models for word embedding, obtaining semantic relationships word-by-word or sentence-by-sentence; sentence embedding for classical machine learning approaches; and also the unsupervised finetuning of any Bangla linguistic dataset.

<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.

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 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.

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.

統計力学的な観点で提案されてきた計算の解析手法や計算に関する問題について，計算論的な観点から検討を行った。その結果，問題例の計算困難さの変化に関して，これまでの枠組みでは捉えられていなかった困難さの変化を明らにすることに成功し，計算困難さの変化を研究するための新しい，より頑健な枠組みを提案した。この結果は，暗号の安全性の基礎にもなる。一方，解の構造の特徴付けや，解の数え上げ問題など，統計力学の基本問題に関しても，効率的アルゴリズムの開発や，その基礎となる知見を得ることができた。

量子対話型証明の一般化モデルを提案し完全問題の存在やBabaiの崩壊定理の量子版などの計算量的構造を明らかにした。半環上の行列積およびグラフ上の三角形発見問題に対して高速量子アルゴリズムを構築し解析方法を発展させ量子分散プロトコルを構築した。観測系と計算系が分離可能な補助キュービット駆動型モデルでも量子ブラインド計算が実現することを示した。計算量クラスBQPの古典計算量クラスAWPPに対し事後選択の概念を利用した量子計算量クラスによる特徴付けを与えた。AWPPがBQPの最良上界である自然な理由を与えAWPPの研究への量子計算量理論的アプローチの可能性を切り拓いた。

本研究では，ユーザが複数存在するネットワークにおける量子通信技術について研究を行った．特に，従来技術が苦手とする情報理論的な秘匿性について，量子通信技術をベースに研究した．情報理論的安全性を実現するには多くの場合、秘匿性増強とよばれる情報処理を符号を用いて行うが，先行研究では，１つの符号の長さの有限性を考慮した安全性評価は不十分であったため，それを明らかにした．さらに，秘匿性を保持した形で計算を依頼する秘匿依頼計算についても情報理論的安全性の枠組みで研究し，測定型量子計算の枠組みで具体的な手法を提案し，その計算結果の正しさを保証する枠組みを与えた．

一般的に観測ベース量子計算モデルで議論されるブラインド量子計算の特別形として観測に適した系と計算に適した系が存在し観測は観測系でのみ行う計算モデルとして補助キュービット駆動量子計算がある．当該モデルにおいてブラインド量子計算が可能であるための十分条件を導出し，実際にその十分条件を満たす方法を与えた．暗号理論においては，他のプロトコルの部品として利用しても安全性を維持する性質は汎用結合可能性と呼ばれる．ブラインド量子計算の方式には様々な方式があるが，クライアントが観測を行うタイプのFujii-Morimae方式は汎用結合可能であることを証明した．

量子情報理論と量子計算量理論の融合技術を発展させて,対話型証明,暗号理論,ネットワーク理論などの諸問題に対して適用した.量子対話型証明に関しては,複数証明者間の量子エンタングルメントの効果を追究し,量子対話型証明の理論を発展させた.また,ネットワーク符号化における量子通信の可能性を検討し,効率化通信手法の提案を行った.従来の古典暗号の枠組みでは証明困難であったハードコア述語に対して量子暗号理論を介することでその証明を構築可能にした.量子暗号理論へのフィードバックを行うため,様々な古典暗号プロトコルの考案を行った.

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

量子情報処理を遂行できる実体の可能性・将来性について,対話型証明・暗号理論・アルゴリズム理論の観点から考察し,対話型証明においては量子エンタングルメントが有効であることを確認し,暗号理論においては非対話型のビット委託方式の提案を行い,アルゴリズム理論においては代表的な問題である隠れ部分群問題に対する量子アルゴリズムの限界を導出した.

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