We give a characterization for the intractability of hyperelliptic discrete logarithm problem from a viewpoint of computational complexity theory. It is shown that the language of which complexity is equivalent to that of the hyperelliptic discrete logarithm problem is in NP co-AM, and that especially for elliptic curves, the corresponding language is in NP co-NP. It should be noted here that the language of which complexity is equivalent to that of the discrete logarithm problem defined over the multiplicative group of a finite field is also characterized as in NP co-NP.

Weakness of a block cipher, which has provable immunity against linear cryptanalysis, is investigated. To this end, the round transformation used in MISTY, which is a data encryption algorithm recently proposed by M. Matsui from Mitsubishi Electric Corporation, is compared to the round transformation of DES from the point of view of pseudrandom generation. An important property of the MISTY cipher is that, in terms of theoretically provable resistance against linear and differential cryptanalysis, which are the most powerful cryptanalytic attacks known to date, it is more robust than the Data Encryption Standard or DES. This property can be attributed to the application of a new round transform in the MISTY cipher, which is obtained by changing the location of the basic round-function in a transform used in DES. Cryptograohic roles of the transform used in the MISTY cipher are the main focus of this paper. Our research reveals that when used for constructiong pseudorandom permutations, the transform employed by the MISTY cipher is inferior to the transform in DES, though the former is superior to the latter in terms of strength against linear and differential attacks. More specifically, we show that a 3-round (4-round, respectively) concatenation of transforms used in the MISTY cipher is not a pseudorandom (super pseudorandom, respectively) permutation.

In this paper, we examine the effectiveness of clock control in protecting stream ciphers from a distinguishing attack, and show that this form of control is effective against such attacks. We model two typical clock-controlled stream ciphers and analyze the increase in computational complexity for these attacks due to clock control. We then analyze parameters for the design of clock-controlled stream ciphers, such as the length of the LFSR used for clock control. By adopting the design criteria described in this paper, a designer can find the optimal length of the clock-control sequence LFSR.

In [1] it was proved that 20 of 64 PGV hash functions based on block cipher are collision-resistant and one-way in the black-box model of the underlying block cipher. Here, we generalize the definition of PGV-hash function into a hash family and we will prove that, aside from the previously reported 20 hash functions, we have 22 more collision-resistant and one-way hash families. As all these 42 families are keyed hash family, these are also target-collision-resistant. All these 42 hash families have tight upper and lower bounds on (target) collision-resistant and one-way-ness.

We discuss multidoubling methods for efficient elliptic scalar multiplication. The methods allows computation of 2k P directly from P without computing the intermediate points, where P denotes a randomly selected point on an elliptic curve. We introduce algorithms for elliptic curves with Montgomery form and Weierstrass form defined over finite fields with characteristic greater than 3 in terms of affine coordinates. These algorithms are faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves and analyze computational complexity. As a result of our implementation with respect to the Montgomery and Weierstrass forms in terms of affine coordinates, we achieved running time reduced by 28% and 31%, respectively, in the scalar multiplication of an elliptic curve of size 160-bit over finite fields with characteristic greater than 3.

In this paper, we consider a class of the languages that have (constant round) perfect zero-knowledge interactive proofs without assuming any complexity assumptions. Especially, we investigate the interactive protocol with the restricted prover who runs in probabilistic polynomial time and knows the complete factorization as a trapdoor information of the integer associated with the input. We give a condition of the existence of constant round perfect zero-knowledge interactive proofs without assuming any complexity assumptions. The bit commitment based on the quadratic residuosity has an important role in our protocol and the simulation is based on the technique developed by Bellare, Micali, and Ostrovsky in Ref. (9), so call double running process. However, the proof of perfect zero-knowledgeness needs a more powerful simulation technique. Our simulation extracts more knowledge, the complete factorization of the integer associated with the input, from a (cheating) verifier than Bellare-Micali-Ostrovsky's simulation does. Furthermore, our main result implies that Blum integer has a five move perfect zero-knowledge interactive proof without assuming any complexity assumptions. (All previous known zero-knowledge protocols for Blum integer required either unproven cryptographic assumptions or unbounded number of rounds of message exchange.)

We show that a randomized addition-sub-traction chains countermeasure against side channel attacks is vulnerable to an SPA attack, which is a kind of side channel attack, under distinguishability between addition and doubling. The side channel attack takes advantage of information leaked during execution of a cryptographic procedure. The randomized addition-subtraction chains countermeasure was proposed by Oswald-Aigner, and is based on a random decision inserted into computations. However, the question of its immunity to side channel attacks is still controversial. The randomized addition-subtraction chains countermeasure has security flaw in timing attacks, another kind of side channel attack. We have implemented the proposed attack algorithm, whose input is a set of AD sequences, which consist of the characters "A" and "D" to indicate addition and doubling, respectively. Our program has clarified the effectiveness of the attack. The attack algorithm could actually detect secret scalars for given AD sequences. The average time to detect a 160-bit scalar was about 6 milliseconds, and only 30 AD sequences were enough to detect such a scalar. Compared with other countermeasures against side channel attacks, the randomized addition-subtraction chains countermeasure is much slower.

In this paper, we investigate the discrepancy between a serial version and a parallel version of zero-knowledge protocols, and clarify the information "leaked" in the parallel version, which is not zero-knowledge unlike the case of the serial version. We consider two sides: one negative and the other positive in the parallel version of zero-knowledge protocols, especially of the Fiat-Shamir scheme.

Current Public Key Infrastructures suffer from a scaling problem, and some may have security problems, even given the topological simplification of bridge certification authorities. This paper analyzes the security problems in Bridge Certificate Authorities (BCA) model by using the concept of "impersonation risk," and proposes a new modified BCA model, which enhances its security, but is a bit more complex incertification path building and implementation than the existing one.

In this paper, we investigate constant round zero knowledge interactive proofs (ZKIP) of knowledge comparing them with the ones for membership of languages. Our result is that there exist non-trivial problems that have five move perfect ZKIP's of knowledge without any unproven assumption. To do this, we construct a knowledge extractor for a five move zero knowledge protocol, which was proposed as the membership of the language of graph isomorphism by Bellare, Micali, and Ostrovsky.

We consider the problems of access control and encrypted keyword search for cryptographic cloud storage in such a way that they can be implemented for a multiple users setting. Our fine-grained access control aware multi-user secure keyword search approach interdependently harmonizes these two security notions, access control and encrypted keyword search. Owing to the shrinkage of the cloud server's search space to the user's decryptable subset, the proposed scheme both decreases information leakage and is shown to be efficient by the results of our contrastive performance simulation.

When two parties connect via a possibly unreliable network, ensuring fairness becomes a serious problem. To solve this problem, a lot of Certified E-mail systems are proposed. However, user's privacy including confidentiality and anonymity is not considered in almost all of these systems. In this paper, we propose two private message board systems using an electronic notice board to solve Certified mail problem.

The research communitiy has shown considerable interest in studying access control in single Trusted Operating Systems (TOS). However, interactions among multiple TOSs have attracted relatively little attention. In this paper, we propose a Collaborative Role-Based Access Control (C-RBAC) model for distributed systems in which accesses across system domain boundaries are allowed. Access entities in a TOS vary in time. The changes in the organizational structure of the access entities in one system may influence other cooperating systems. In addition, policy-freeness, domain and rule conflicts are possible. These problems restrict the flexibility and scalability of coordination. We propose drafting a meta-component to play the role of a coordinator in multi-domain role-based access control. It is then possible to impart flexibility and scalability in a secure fashion. Experimental studies of the proposed model with the Network File System and SELinux system support our conclusion.

The computational performance of cryptographic protocols using an elliptic curve strongly depends on the efficiency of the scalar multiplication. Some elliptic curve based cryptographic protocols, such as signature verification, require computation of multi scalar multiplications of kP+lQ, where P and Q are points on an elliptic curve. An efficient way to compute kP+lQ is to compute two scalar multiplications simultaneously, rather than computing each scalar multiplication separately. We introduce new efficient algorithms for simultaneous scalar multiplication on an elliptic curve. We also give a detailed analysis of the computational efficiency of our proposed algorithms.

Due to the fast development of Internet and the related IT technologies, it becomes more and more easier to access a large amount of data. k-means clustering is a powerful and frequently used technique in data mining. Many research papers about privacy-preserving k-means clustering were published. In this paper, we analyze the existing privacy-preserving k-means clustering schemes based on the cryptographic techniques. We show those schemes will cause the privacy breach and cannot output the correct results due to the faults in the protocol construction. Furthermore, we analyze our proposal as an option to improve such problems but with intermediate information breach during the computation.

We propose an untraceable electronic money system. Our system uses the partially blind signature based on the discrete logarithm problem, and applies secret key certificates to the payment protocol.

Smart contracts are becoming more and more popular in financial scenarios like medical insurance. Rather than traditional schemes, using smart contracts as a medium is a better choice for both participants, as it is fairer, more reliable, more efficient, and enables real-time payment. However, medical insurance contracts need to input the patient's condition information as the judgment logic to trigger subsequent execution. Since the blockchain is a closed network, it lacks a secure network environment for data interaction with the outside world. The Data feed aims to provide the service of the on-chain and off-chain data interaction. Existing researches on the data feed has solved the security problems on it effectively, such as Town Crier, TLS-N and they have also taken into account the privacy-preserving problems. However, these schemes cannot actually protect privacy because when the ciphertext data is executed by the contract, privacy information can still be inferred by analyzing the transaction results, since states of the contract are publicly visible. In this paper, based on zero-knowledge proof and Hawk technology, a on-and-off-chain complete smart contract data feed privacy-preserving scheme is proposed. In order to present our scheme more intuitively, we combined the medical insurance compensation case to implement it, which is called MIPDF. In our MIPDF, the patient and the insurance company are parties involved in the contract, and the hospital is the data provider of data feed. The patient's medical data is sent to the smart contract under the umbrella of the zero-knowledge proof signature scheme. The smart contract verifies the proof and calculates the insurance premium based on the judgment logic. Meanwhile, we use Hawk technology to ensure the privacy of on-chain contract execution, so that no information will be disclosed due to the result of contract execution. We give a general description of our scheme within the Universal Composability (UC) framework. We experiment and evaluate MIPDF on Ethereum for in-depth analysis. The results show that our scheme can securely and efficiently support the functions of medical insurance and achieve complete privacy-preserving.

The multivariate public key cryptosystem (MPKC), which is based on the problem of solving a set of multivariate systems of quadratic equations over a finite field, is expected to be secure against quantum attacks. Although there are several existing schemes in MPKC that survived known attacks and are much faster than RSA and ECC, there have been few discussions on security against physical attacks, aside from the work of Okeya et al. (2005) on side-channel attacks against Sflash. In this study, we describe general fault attacks on MPKCs including Big Field type (e.g. Matsumoto-Imai, HFE and Sflash) and Stepwise Triangular System (STS) type (e.g. UOV, Rainbow and TTM/TTS). For both types, recovering (parts of) the secret keys S,T with our fault attacks becomes more efficient than doing without them. Especially, on the Big Field type, only single fault is sufficient to recover the secret keys.