A note on relativized log space

It is shown that there is a recursive oracleD such that, thereby answering an open question of Ladner and Lynch [5]. Here and denote the class of languages accepted in deterministic, respectively nondeterministic, space logn. This work was supported by NSF Grant MCS-8001963.     

A relationship between difference hierarchies and relativized polynomial hierarchies

Chang and Kadin have shown that if the difference hierarchy over NP collapses to levelk, then the polynomial hierarchy (PH) is equal to thekth level of the difference hierarchy over ₂ ^p . We simplify their poof and obtain a slightly stronger conclusion: if the difference hierarchy over NP collapses to levelk, then PH collapses to (P _(k–1) ^NP )^NP, the class of sets recognized in polynomial time withk – 1 nonadaptive queries to a set in NP^NP and an unlimited number of queries to a set in NP. We also extend the result to classes other than NP: For any classC that has _m ^p -complete sets and is closed under _conj ^p -and _m ^NP -reductions (alternatively, closed under _disj ^p -and _m ^co-NP -reductions), if the difference hierarchy overC collapses to levelk, then PH ^C = (P _(k–1)–tt ^NP ) ^C . Then we show that the exact counting class C_P is closed under _disj ^p - and _m ^co-NP -reductions. Consequently, if the difference hierarchy over C_P collapses to levelk, then PH^PP(= PH^C_P) is equal to (P _(k–1)–tt ^NP )^PP. In contrast, the difference hierarchy over the closely related class PP is known to collapse.Finally we consider two ways of relativizing the bounded query class P _k–tt ^NP : the restricted relativization P _k–tt ^{NP C} and the full relativization (P _k–tt ^NP ) ^C . IfC is NP-hard, then we show that the two relativizations are different unless PH ^C collapses.Richard Beigel was supported in part by NSF Grants CCR-8808949 and CCR-8958528. Richard Chang was supported in part by NSF Research Grant CCR 88-23053. This work was done while Mitsunori Ogiwara was at the Department of Information Science, Tokyo Institute of Technology, Tokyo, Japan.     

A complexity tradeoff in ranking-function termination proofs

To prove that a program terminates, we can employ a ranking function argument, where program states are ranked so that every transition decreases the rank. Alternatively, we can use a set of ranking functions with the property that every cycle in the program’s flow-chart can be ranked with one of the functions. This “local” approach has gained interest recently on the grounds that local ranking functions would be simpler and easier to find. The current study is aimed at better understanding the tradeoffs involved, in a precise quantitative sense. We concentrate on a convenient setting, the Size-Change Termination framework (SCT). In SCT, programs are replaced by an abstraction whose termination is decidable. Moreover, sufficient classes of ranking functions (both global and local) are known. Our results show a tradeoff: either exponentially many local functions of certain simple forms, or an exponentially complex global function may be required for proving termination.     

Nest sets and relativized closure properties

A nest set is the language generated by a context-free grammar whose rules are $\text{A → aB}\text{a}\text{?}\text{C}$ or A → ? (where a, ā are paired terminal symbols, and A, B, C are nonterminal symbols). They can be seen as the one-dimensional expressions of the recognizable sets of binary trees. We study their closure properties under relativized operations with respect to the Dyck set, which is the maximum set in the class. The operations considered are relativized versions of AFL operations, quotient, direct product, shuffle product, and some others. As an application we prove various closure properties of generalized parenthesis languages.     

A brief history of cryptography

In this section the author gives a very short history of cryptography focusing on the key techniques that were used for encipherment purposes. These include polyalphabetic ciphers and the earliest generations of cipher machines such as Enigma.     

A time-space tradeoff for language recognition

We define a languageL and show that its time and space complexitiesT andS must satisfyT ² S cn ³ even allowing machines with multiple (non random) access to the input.The second author was supported in part by the Israel Commission for Basic Research.     

Randomness in cryptography

Although more formal definitions of randomness exist, a colloquial one will suffice here: a random process is one whose consequences are unknown. Intuitively, this is why randomness is crucial in cryptographic applications - because it provides a way to create information that an adversary can't learn or predict. It's then the task of a good protocol designer to leverage this power in the best possible way to protect data and communication. In this paper, we'll look at some basic uses of randomness in cryptography and briefly review the process of securely generating randomness.     

Visual cryptography: A brief survey

Visual cryptography is an emerging technology to address the concerns regarding privacy of images. It is a powerful technique combining both the impeccable ciphers and secret sharing in cryptography with that of the raster graphics. Visual cryptography divides the secret image into shares or shadows during encryption. The term “visual” in visual cryptography stands for the fact that during decryption phase, a user can perceive the recovered secret with his/her visual system, without the intervention of machines. Various visual cryptography techniques have been discussed extensively in this survey. The metrics used to analyse the effectiveness of visual cryptography techniques have been briefed. The significant applications of visual cryptography have also been summarized in the survey.     

UP and the low and high hierarchies: A relativized separation

The low and high hierarchies within NP were introduced by Schöning in order to classify sets in NP. It is not known whether the low and high hierarchies include all sets in NP. In this paper, using the circuit lower-bound techniques of Håstad and Ko, we construct an oracle set relative to which UP contains a language that is not in any level of the low hierarchy and such that no language in UP is in any level of the high hierarchy. Thus, in order to prove that UP contains languages that are in the high hierarchy or that UP is contained in the low hierarchy, it is necessary to use nonrelativizable proof techniques. Since it is known that UP^A is low for PP^A for all setsA, our result also shows that the interaction between UP and PP is crucial for the lowness of UP for PP; changing the base class to any level of the polynomial-time hierarchy destroys the lowness of UP.     

A tutorial on public key cryptography

Public key cryptography provides the means for establishing instantaneous, secure communication between any two persons or any two computers. The prior exchange of a secret quantity, called the cryptographic key, is not necessary. In this paper, the underlying mathematical principles of public key (PK) cryptography are informally introduced and two realizations of the concept are described.     

基于DNA密码的一次一密加密算法

作为不可破译的密码,一次一密密码是信息安全领域的一个重要研究课题,但密钥生成、存储和分配时存在较大困难,使得一次一密密码很难实现。以生物分子为基础的DNA计算,因其巨大的信息存储能力和高度的并行计算能力,可用于一次一密密码。非特异性杂交反应严重影响了加密过程和解密过程,通过PCR实现密钥分配,通过电子计算机实现异或运算,有效消除了非特异性杂交反应对加密结果和解密结果的影响。     

A nondeterministic space-time tradeoff for linear codes

We are interested in proving exponential lower bounds on the size of nondeterministic D-way branching programs computing functions in linear time, that is, in time at most kn for a constant k. Ajtai has proved such lower bounds for explicit functions over domains D of size about n, and Beame, Saks and Thathachar for functions over domains of size about k²². We prove an exponential lower bound ²Ω(n/ck) for an explicit function over substantially smaller domain D of size about k². Our function is a universal function of linear codes.     

A bandwidth latency tradeoff for broadcast and reduction

The “fractional tree” algorithm for broadcasting and reduction is introduced. Its communication pattern interpolates between two well known patterns—sequential pipeline and pipelined binary tree. The speedup over the best of these simple methods can approach two for large systems and messages of intermediate size. For networks which are not very densely connected the new algorithm seems to be the best known method for the important case that each processor has only a single (possibly bidirectional) channel into the communication network.     

A time-space tradeoff for sorting on non-oblivious machines

A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n².     

A sensitivity tradeoff for plants with time delay

In this paper we show that the sensitivity function of a scalar feedback system must satisfy an integral constraint when the open-loop transfer function is strictly proper and contains a time delay. The integral constraint is identical to the classical Bode sensitivity integral, which holds provided the open-loop gain has greater than a one-pole rolloff. The design implications of the two constraints are somewhat different, however, and this difference is discussed. The relation between open-loop phase and a conflict between bandwidth and sensitivity properties is explored.     

Quantum cryptography

Though most people think they are science fiction, quantum cryptography systems are now operational, with prototypes protecting Internet traffic across metropolitan areas. These systems are so novel that we can consider quantum cryptography, or more properly, quantum key distribution (QKD), as the third and final insight to transform cryptography in the 20th century.     

A new visual cryptography with multi-level encoding

Visual secret sharing (VSS) is a visual cryptography scheme which decodes secret messages into several enlarged shares, and distributes them to different participants. The participants can recover the secret messages by stacking their shares, and then secret message can be revealed by human visual sensitivity. Afterward some researchers start to research size invariant scheme, and apply to encode grayscale images such as scenic photos or pictures, not only binary messages. Owing to the gray values distribution of pictures are different, extreme distribution may cause blurred revealed image. In this paper, we proposed a size invariant VSS scheme which is suitable for different distribution of image's gray values. Experiment results show that the reconstructed images of our method, for brighter, darker, and normal images, have clearer and higher contrast, and without apparent artifact and unexpected contour.     

一种安全的随机网格视觉密码方案

随机网格视觉密码体制与传统视觉密码体制相比,其数据量得到极大的降低.但这种视觉密码的安全性能却不理想.在传统随机网格体制基础上,提出了一种新的随机网格视觉密码方案.该方案与传统随机网格视觉密码相比,只增加了很少的数据量,却极为有效地提高了随机网格视觉密码的安全性能.     

Quantum-safe cryptography:crossroads of coding theory and cryptography

We present an overview of quantum-safe cryptography (QSC) with a focus on post-quantum cryptography (PQC) and information-theoretic security.From a cryptographi...     

A differential cryptanalysis of Yen-Chen-Wu multimedia cryptography system

Recently, Yen et al. presented a new chaos-based cryptosystem for multimedia transmission named “multimedia cryptography system” (MCS). No cryptanalytic results have been reported so far. This paper presents a differential attack to break MCS, which requires only seven chosen plaintexts. The complexity of the attack is O(N), where N is the size of plaintext. Experimental results are also given to show the real performance of the proposed attack.