On complete one-way functions

Complete constructions play an important role in theoretical computer science. However, in cryptography complete constructions have so far been either absent or purely theoretical. In 2003, L.A. Levin presented the idea of a combinatorial complete one-way function. In this paper, we present two new one-way functions based on semi-Thue string rewriting systems and a version of the Post correspondence problem. We also present the properties of a combinatorial problem that allow a complete one-way function to be based on this problem. The paper also gives an alternative proof of Levin’s result.     

Statistical Zero Knowledge and quantum one-way functions

One-way functions are a fundamental notion in cryptography, since they are the necessary condition for the existence of secure encryption schemes. Most examples of such functions, including Factoring, Discrete Logarithm or the RSA function, however, can be inverted with the help of a quantum computer. Hence, it is very important to study the possibility of quantum one-way functions, i.e. functions which are easily computable by a classical algorithm but are hard to invert even by a quantum adversary. In this paper, we provide a set of problems that are good candidates for quantum one-way functions. These problems include Graph Non-Isomorphism, Approximate Closest Lattice Vector and Group Non-Membership. More generally, we show that any hard instance of Circuit Quantum Sampling gives rise to a quantum one-way function. By the work of Aharonov and Ta-Shma [D. Aharonov, A. Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, in: Proceedings of STOC02 — Symposium on the Theory of Computing, 2001], this implies that any language in Statistical Zero Knowledge which is hard-on-average for quantum computers leads to a quantum one-way function. Moreover, extending the result of Impagliazzo and Luby [R. Impagliazzo, M. Luby, One-way functions are essential for complexity based cryptography, in: Proceedings of FOCS89 — Symposium on Foundations of Computer Science, 1989] to the quantum setting, we prove that quantum distributionally one-way functions are equivalent to quantum one-way functions.     

Absolute results concerning one-way functions and their applications

A new approach to one-way functions is considered. A one-way function is defined to be a function which is easy to compute but hard to invert in the sense that its inverse is not inDTIME(n ^k ) for fixed largek. While this is weaker than the usual definition of one-way functions it requires no complexity-theoretic assumptions. Some of these functions are proved to exist, while the existence of other, stronger functions is shown to bear upon open problems in complexity theory. An application to public-key cryptosystems is given.This work was supported in part by NSA Grant MDA904-87-H-2003 and by NSF Grant MIP-8608137.     

A survey of one-way functions in complexity theory

In complexity theory a one-way function is defined to be a one-one, honest, function that is computable in polynomial time whose inverse is not computable in polynomial time. We examine relationships between the complexity of functional computational problems and ordinary set recognition problems. The complexity of inverting one-way functions follows from these relationships. Then we survey various forms of one-way functions that have arisen in relationship to some cryptographic investigations and in relationship to the isomorphism problem.The author acknowledges support by the National Science Foundation under Grant CCR-9002292.     

On time computability of functions in one-way cellular automata

The capability of one-way (space-bounded) cellular automata (OCA) to time-compute functions is investigated. That means given a constant input of length a distinguished cell has to enter a distinguished state exactly after time steps. The family of such functions ((OCA)) is characterized in terms of formal language recognition. Several functions are proved to be time-computable and properties of (OCA) are given. The time-computation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time. Received: 25 April 1997 / 10 June 1997     

Access control in a hierarchy using one-way hash functions

This paper presents a cryptographic key management solution to solve the access control problem in a hierarchy. Based on one-way hash functions, an efficient key assignment and derivation method is proposed. This solution uses limited number of keys and hash functions. Also, the dynamic access control problems, such as adding/deleting nodes, or modifying relationships between nodes in the hierarchy are considered and can be resolved.     

A new strong-password authentication scheme using one-way hash functions

Recently, Sandirigama et al. have proposed an authentication scheme by the name of SAS and have claimed that it has the lowest storage, processing, and transmission overhead. In 2001, Lin et al. showed that the protocol is insecure and proposed an optimal strong-password authentication protocol called the OSPA protocol. However, Chen and Ku pointed out that both SAS and OSPA are vulnerable to stolen-verifier attack in 2002. Later, Lin, Shen, and Hwang proposed a modified OSPA protocol to repair the security law of OSPA protocol. In this paper, we propose a new strong-password authentication protocol that not only can withstand many possible attacks including a stolen-verifier attack, but that is also more efficient than the modified OSPA protocol. The text was submitted by the authors in English.     

Vulnerabilities of generalized MQV key agreement protocol without using one-way hash functions

The MQV protocol is the first authenticated key agreement protocol which uses a digital signature to sign Diffie–Hellman public keys without using any one-way hash functions. Based on the MQV protocol, Harn and Lin proposed an authenticated multiple-key agreement protocol that enables two parties to establish multiple common secret keys in a single protocol run. But the protocol was subsequently found to be flawed. Tseng proposed a new generalized MQV key agreement protocol without using one-way hash functions to overcome the weaknesses of Harn–Lin's protocol. Recently, Shao showed that Teng's protocol is insecure against signature forgery attacks and then proposed an improved authenticated multiple-key agreement protocol to resist the attacks. In this paper we show that Shao's protocol is vulnerable to unknown key-share attacks. We also point out its another potential weakness.     

Security of robust generalized MQV key agreement protocol without using one-way hash functions

The MQV key agreement protocol has been adopted by IEEE P1363 Committee to become a standard, which uses a digital signature to sign the Diffie–Hellman public keys without using any one-way hash function. Based on the MQV protocol, Harn and Lin proposed a generalized key agreement protocol to enable two parties to establish multiple common secret keys in a single round of message exchange. However, the Harn–Lin protocol suffers from the known-key attack if all the secret keys established are adopted. Recently, Tseng proposed a new generalized MQV key agreement protocol without using one-way hash functions. Tseng claimed that the proposed protocol is robust since the new protocol can withstand the forgery attack and the known-key attack. In this paper we show that this protocol is not secure since the receiver can forge signatures. We also propose an improved authenticated multiple-key agreement protocol, which is secure against the forgery attack and the known-key attack.     

Separability of unimodal polygons

A conjecture that any three unimodal polygons are sequentially separable is, by means of a counterexample, shown to be false.     

Developing the concept of one-way functions for cryptographic security systems using achievements in chaotic dynamics

The paper shows that an “informal” interpretation of one-way functions in modern cryptography is inadequate and defines such functions in terms of information theory. This combination of complexity and information theories opens new opportunities for constructing one-way functions, whose one-way transformation is based on the ambiguity of their inverse mappings. It is shown that random mappings are promising candidates for constructing such functions. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 136–146, November–December 2006.     

Circular Separability of Polygons

Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk does not intersect the other set. This paper studies two problems related to circular separability. A linear-time algorithm is proposed to decide if two polygons are circularly separable. The algorithm outputs the smallest separating circle. The second problem asks for the largest circle included in a preprocessed, convex polygon, under some point and/ or line constraints. The resulting circle must contain the query points and it must lie in the halfplanes delimited by the query lines. Received October 25, 1998; revised April 21, 1999.     

Shrinking one-way cellular automata

We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time one-way cellular automata (\(\text{OCA}\)) with the additional property that during a computation any cell of the \(\text{OCA}\) has the ability to dissolve itself, so-called shrinking one-way cellular automata (\(\text{SOCA}\)). It turns out that real-time \(\text{SOCA}\) are more powerful than real-time \(\text{OCA}\), since they can accept certain linear-time \(\text{OCA}\) languages. On the other hand, linear-time \(\text{OCA}\) are more powerful than real-time \(\text{SOCA}\), which is witnessed even by a unary language. Additionally, a construction is provided that enables real-time \(\text{SOCA}\) to accept the reversal of real-time iterative array languages. Finally, restricted real-time \(\text{SOCA}\) are investigated. We distinguish two limitations for the dissolving of cells. One restriction is to bound the total number of cells that are allowed to dissolve by some function. In this case, an infinite strict hierarchy of language classes is obtained. The second restriction is inspired by an approach to limit the amount of nondeterminism in \(\text{OCA}\). Compared with the first restriction, the total number of cells that may dissolve is still unbounded, but the number of time steps at which a cell may dissolve is bounded. The possibility to dissolve is allowed only in the first k time steps, where \(k\ge 0\) is some constant. For this mode of operation an infinite, tight, and strict hierarchy of language classes is obtained as well.     

盲分离问题的可分性理论

对盲信号分离的基本理论问题进行了探讨,给出了从混叠信号中分离出源信号的充要条件,并回答了源信号能提取的数量问题.同时,还给出了基于该理论的盲分离算法,该方法适应于病态混叠情形下的提取.且就几种不同的情况进行了计算机仿真.仿真结果表明了所提理论的正确性及相应算法的有效性.     

N维系统可分性的充要判据

本文给出了N维Roesser模型和一般二维系统模型可分的充要判据,并将所得结果应用于可分系统的稳定性问题,得到了相应的判据。     

Separability of scalar random multisine signals

Random multisines have successfully been used as input signals in many system identification experiments. In this paper, it is shown that scalar random multisine signals with a flat amplitude spectrum are separable of order one. The separability property means that certain conditional expectations are linear and it implies that random multisines can easily be used to obtain accurate estimates of the linear time-invariant part of a Hammerstein system. Furthermore, higher order separability is investigated.     

A note on one-way and two-way automata

The purpose of this note is to show that there exist non-regular languages whose memory requirements for recognition by one-way and two-way automata differ by a double exponential and that this difference cannot be exceeded.     

基于边界点的可分离性度量及特征选择

提出了一种新的面向高维数据的特征选择方法,在特征子集搜索上采用遗传算法进行随机搜索,在特征子集评价上采用基于边界点的可分性度量作为评价指标及适应度。实验结果表明,该算法可有效地找出具有较好的可分离性的特征子集,从而实现降维并提高分类 精度。     

基于类间区分度的属性约简方法

属性约简是粗糙集理论中最重要的研究问题之一。近年来,粗糙集理论下的属性约简问题引发了学者们广泛的关注。然而,大多数属性约简方法都是基于不可分辨或可分辨关系所提出的,属性约简的性能仅仅取决于等价类或近似集的变化,却忽略了不具有等价关系的对象所在的不同类簇间关系的变化情况。因此,引入了类间区分度的概念,相较于等价类和上下近似集而言,它可以反映类簇区分程度随属性变化而变化的情况。对类间重合度和类间区分度进行了解释及定义,并结合启发式搜索策略,提出了一种基于类间区分度的属性约简方法,实验验证了所提方法的有效性。