An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions

We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum et al. [5]. Until recently there was a sizable polynomial gap between the most efficient noninteractive proofs for NP based on general complexity assumptions [11] versus those based on specific algebraic assumptions [7]. Recently, this gap was reduced to a polylogarithmic factor [17]; we further reduce the gap to a constant factor. Our proof system relies on the existence of one-way permutations (or trapdoor permutations for bounded provers). Our protocol is stated in the hidden bit model introduced by Feige et al. [11]. We show how to prove that an n -gate circuit is satisfiable, with error probability 1/n ^O(1) , using only O(n lg n) random committed bits. For this error probability, this result matches to within a constant factor the number of committed bits required by the most efficient known interactive proof systems. Received 20 November 1995 and revised 7 October 1996     

CBC MAC for Real-Time Data Sources

The Cipher Block Chaining (CBC) Message Authentication Code (MAC) is an authentication method which is widely used in practice. It is well known that the use of the CBC MAC for variable length messages is not secure, and a few rules of thumb for the correct use of the CBC MAC are known by folklore. The first rigorous proof of the security of CBC MAC, when used on fixed length messages, was given only recently by Bellare et al.[3]. They also suggested variants of CBC MAC that handle variable-length messages but in these variants the length of the message has to be known in advance (i.e., before the message is processed). We study CBC authentication of real-time applications in which the length of the message is not known until the message ends, and furthermore, since the application is real-time, it is not possible to start processing the authentication until after the message ends. We first consider a variant of CBC MAC, that we call the encrypted CBC MAC (EMAC), which handles messages of variable unknown lengths. Computing EMAC on a message is virtually as simple and as efficient as computing the standard CBC MAC on the message. We provide a rigorous proof that its security is implied by the security of the underlying block cipher. Next, we argue that the basic CBC MAC is secure when applied to a prefix-free message space. A message space can be made prefix-free by also authenticating the (usually hidden) last character which marks the end of the message. Received 16 September 1997 and revised 24 August 1999 Online publication 2 June 2000     

Integrating generations with advanced reference counting garbage collectors

We propose the use of generations with modern reference counting. A reference counting collector is well suited to collect the old generation, containing a large fraction of live objects that are modified infrequently. Such a collector can be combined with a tracing collector to collect the young generation, typically containing a small fraction of live objects. We have designed such a collector appropriate for running on a multiprocessor. As our building blocks, we used the sliding‐views on‐the‐fly collectors. We have implemented the new collector on the Jikes Research Java Virtual Machine (Jikes RVM) and compared it with the concurrent reference counting collector supplied with the Jikes RVM package. Our measurements demonstrate short pause times, retaining those of the original on‐the‐fly collectors and a gain in application throughput time. It turns out that a modern reference counting collector may benefit from the use of generations. Copyright © 2006 John Wiley & Sons, Ltd.     

Quantifying knowledge complexity

One of the many contributions of the paper of Goldwasser, Micali and Rackoff is the introduction of the notion of knowledge complexity. Knowledge complexity zero (also known as zero-knowledge) has received most of the attention of the authors and all the attention of their followers. In this paper, we present several alternative definitions of knowledge complexity and investigate the relations between them. Received: July 22, 1997.     

Phase rotation methods in filtering correlation coefficients for ultrasound speckle tracking

In speckle-tracking-based myocardial strain imaging, large interframe/volume peak-systolic strains cause peak hopping artifacts separating the highest correlation coefficient peak from the true peak. A correlation coefficient filter was previously designed to minimize peak hopping artifacts. For large strains, however, the correlation coefficient filter must follow the strain distribution to remove peak hopping effectively. This processing usually means interpolation and high computational load. To reduce the computational burden, a narrow band approximation using phase rotation is developed in this paper to facilitate correlation coefficient filtering. Correlation coefficients are first phase rotated to increase coherence, then filtered. Rotated phase angles are determined by the local strain and spatial position. This form of correlation coefficient filtering enhances true correlation coefficient peaks in large strain applications if decorrelation due to deformation does not completely destroy the coherence among neighboring correlation coefficients. The assumed strain used in the filter can also deviate from the true strain and still be effective. Further improvement in displacement estimation can be expected by combining correlation coefficient filtering with a new Viterbi-based displacement estimator.     

Is code equivalence easy to decide?

We study the computational difficulty of deciding whether two matrices generate equivalent linear codes, i.e., codes that consist of the same codewords up to a fixed permutation on the codeword coordinates. We call this problem code equivalence. Using techniques from the area of interactive proofs, we show on the one hand, that under the assumption that the polynomial-time hierarchy does not collapse, code equivalence is not NP-complete. On the other hand, we present a polynomial-time reduction from the graph isomorphism problem to code equivalence. Thus if one could find an efficient (i.e., polynomial-time) algorithm for code equivalence, then one could settle the long-standing problem of determining whether there is an efficient algorithm for solving graph isomorphism     

Reduced peak-hopping artifacts in ultrasonic strain estimation using the Viterbi algorithm

Internal strain resulting from tissue deformation can be estimated by correlation processing of speckle patterns within complex (i.e., radio frequency) ultrasound images acquired during deformation. At large deformations, the magnitude of the correlation coefficient peak can be significantly lower than unity, so that random speckle correlations will exceed the true peak. This effect is called ?peak hopping? and causes significant errors in displacement and deformation estimates. Here we investigate the Viterbi algorithm, a dynamic programming procedure, to overcome peak-hopping artifacts by finding the most likely sequence of hidden states in a sequence of observed events. It is well suited to motion estimation in elasticity- imaging studies because adjacent tissue elements remain adjacent following deformation. Particularly, tissue elements along an ultrasonic beam in one image lie along a 3-D continuous curve in the next image instant. The observed event in this case is the correlation coefficient of a pixel at a certain displacement. Radio-frequency data were generated before and after deformation with an average strain of 6%. Simulations were performed for a homogenous medium and for a medium with a stiffer inclusion. Results show that Viterbi processing of speckle-tracking outputs can significantly reduce peak-hopping artifacts.     

The hardness of approximation: Gap location

We refine the complexity analysis of approximation problems by relating it to a new parameter calledgap location. Many of the results obtained so far for approximations yield satisfactory analysis with respect to this refined parameter, but some known results (e.g.,max-k-colorability, max 3-dimensional matching andmax not-all-equal 3sat) fall short of doing so. As a second contribution, our work fills the gap in these cases by presenting new reductions.Next, we present definitions and hardness results of new approximation versions of some NP-complete optimization problems. The problems we treat arevertex cover (for which we define a different optimization problem from the one treated in Papadimitriou & Yannakakis 1991),k-edge coloring, andset splitting.