A discrete logarithm implementation of perfect zero-knowledge blobs

Brassard and Crépeau [BCr] introduced a simple technique for producing zero-knowledge proof systems based on blobs. As is to be expected, their implementation rests on an unproven cryptographic assumption, specifically, that it is easy to generate numbers that are difficult to factor. In this paper we present an implementation of blobs based on a different cryptographic assumption, specifically, that it is easy to generate primes p over which it is difficult to compute discrete logarithms. If, in addition, we can produce a generator for Z _p ^* , this implementation then has the advantage that it leads to proof systems which are perfect zeroknowledge, rather than only almost perfect zero-knowledge.The relationship between factoring and finding discrete logarithms is not well understood, although Bach [Bac1] is an important contribution. Given our current state of number theoretic knowlege, there is no reason to prefer the cryptographic assumption required by one of these implementations over that required by the other. In any event, we introduce the notion of a product blob, whose favorable properties depend only on at least one of these assumptions holding.The first author was supported in part by NSA Grant MDA 904-84-H-00171. The second author was supported in part by NSF Grant DCR-8602562.     

Bit commitment using pseudorandomness

We show how a pseudorandom generator can provide a bit-commitment protocol. We also analyze the number of bits communicated when parties commit to many bits simultaneously, and show that the assumption of the existence of pseudorandom generators suffices to assure amortized O(1) bits of communication per bit commitment.Part of this work was done while the author was at the University of California at Berkeley. This research was supported by NSF Grant CCR 88-13632.     

Definitions and properties of zero-knowledge proof systems

In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol solely composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox-simulation zero-knowledge implies auxiliary-input zero-knowledge (which in turn implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e., we proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-input zero-knowledge and can be used for cryptographic applications such as those in [GMW2].We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las Vegas zero-knowledge proof system necessarily belongs to RP. We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input zero-knowledge proofs.This research was partially supported by the Fund for Basic Research Administered by the Israeli Academy of Sciences and Humanities. Preliminary versions of this work have appeared in [O1] and [O2].     

PBGA packaging reliability assessments under random vibrations for space applications

In this study, experimental and numerical analyses on the solder joint reliability of plastic ball grid array under harsh random vibration and thermal loadings were presented. The chips were assembled on the daisy chained circuit boards for the test samples preparation, and a half of the samples were processed for underfill to investigate the underfill effects on the solder failures. Two consequential steps of the random vibrations, named as acceptance level and qualification level, were applied. Overall required root mean square (rms) of the power spectrum densities of the steps were 22.48 grms for one minutes and 31.78 grms for two minutes, respectively. A thermal shock test was then performed after the vibration tests. It was found that the samples did not show any solder failure under the test requirements, demonstrating the robustness of the packaging structure for potential space applications. The samples were further tested to induce the failures, and finite element analyses were performed to analyze the sample vibration behaviors and the solder stresses to compare the results with the test data. Finally, a simple analytical calculation for the natural frequency estimations was introduced to overcome the complex finite element modeling efforts.     

On the communication complexity of zero-knowledge proofs

The fact that there are zero-knowledge proofs for all languages in NP (see [15], [6], and [5]) has, potentially, enormous implications to cryptography. For cryptographers, the issue is no longer “which languages in NP have zeroknowledge proofs” but rather “which languages in NP have practical zeroknowledge proofs.” Thus, the concrete complexity of zero-knowledge proofs for different languages must be established. In this paper we study the concrete complexity of the known general methods for constructing zero-knowledge proofs. We establish that circuit-based methods, which can be applied in either the GMR or the BCC model, have the potential of producing proofs which can be used in practice. Then we introduce several techniques which greatly reduce the concrete complexity of circuit-based proofs, and we show that these techniques lead to zero-knowledge proofs of knowledge. Finally, we show how to combine the techniques of Kilian, Micali, and Ostrovsky, for designing zero-knowledge proofs with only two envelopes, with some of our techniques for reducing the number of bits which the prover must commit to. Supported in part by NSA Grant No. MDA90488-H-2006. Supported in part by NSF Grant No. CCR-8909657.     

Divertible and Subliminal-Free Zero-Knowledge Proofs for Languages

Divertible proofs are extensions of interactive proofs in which an active eavesdropper, the warden, makes the prover and the verifier untraceable. The warden is transparent to both the prover and the verifier. With subliminal-free proofs the warden controls subliminal messages. In this paper we present divertible and subliminal-free zero-knowledge proofs for various languages. We consider both graph isomorphism and Received September 1992 and revised September 1995 and May 1997     

Practical zero-knowledge proofs: Giving hints and using deficiencies

New zero-knowledge proofs are given for some number-theoretic problems. All of the problems are in NP, but the proofs given here are much more efficient than the previously known proofs. In addition, these proofs do not require the prover to be superpolynomial in power. A probabilistic polynomial-time prover with the appropriate trapdoor knowledge is sufficient. The proofs are perfect or statistical zero-knowledge in all cases except one.This research was supported in part by NSA Grant No. MDA904-88-H-2006.In this paper it will at times be convenient to think of the verifier as being named Vic, and the prover being named Peggy. Thus, he will refer to the verifier and she will refer to the prover.     

Certifying Permutations: Noninteractive zero-knowledge based on any trapdoor permutation

In cryptographic protocols it is often necessary to verify/certify the tools in use. This work demonstrates certain subtleties in treating a family of trapdoor permutations in this context, noting the necessity to check certain properties of these functions. The particular case we illustrate is that of noninteractive zero-knowledge. We point out that the elegant recent protocol of Feige, Lapidot, and Shamir for proving NP statements in noninteractive zero-knowledge requires an additional certification of the underlying trapdoor permutation, and suggest a method for certifying permutations which fills this gap.A preliminary version of this paper appeared in Advances in Cryptology—Crypto 92 Proceedings, Lecture Notes in Computer Science, Vol. 740, E. Brickell, ed., Springer-Verlag, Berlin, 1992. This work was done while Mihir Bellare was at the IBM T.J. Watson Research Center, Yorktown Heights, NY.     

Two-dimensional random projection

As an alternative to adaptive nonlinear schemes for dimensionality reduction, linear random projection has recently proved to be a reliable means for high-dimensional data processing. Widespread application of conventional random projection in the context of image analysis is, however, mainly impeded by excessive computational and memory requirements. In this paper, a two-dimensional random projection scheme is considered as a remedy to this problem, and the associated key notion of concentration of measure is closely studied. It is then applied in the contexts of image classification and sparse image reconstruction. Finally, theoretical results are validated within a comprehensive set of experiments with synthetic and real images.     

Random lasing from dye doped polymer within biological source scatters: The pomponia imperatorial cicada wing random nanostructures

Photonic structures found in biological organisms are often startling in their complexity and surprising in their optical function. In this paper we explore whether biologically derived nanostructures can be utilized to form the resonator structures of organic dye doped polymer lasers. Surprisingly, we find that the random nanostructures on the wing of the pomponia imperatoria cicada can support coherent random lasing when covered with a layer of dye doped polymer film. Due to the scattering role of cicada wing nanostructures, the device emits a resonant multimode peak centered at a wavelength of 605 nm with a mode linewidth of <0.55 nm and exhibits a threshold excitation intensity as low as 70.4 mW/cm². Our results indicate that abundant, naturally occurring biological nanostructures can provide effective platforms for the study of random lasing, and that the laser properties may provide insight into the degree of disorder exhibited by these natural structures.     

随机均衡器的计算机辅助最优化设计

本文提供了一种实用的随机均衡器的计算机辅助设计方法.以二元件均衡器为链接模型,以非线性最小二乘法为最优化方式,解决了多节均衡器链接中初始参数值的选取问题.讨论了0.618法在非单一极值区间的应用.并且通过实例计算说明这一方法的有效性和实用性.     

谱聚类划分随机森林算法在图像识别中的应用

随机森林是近些年发展起来的新集成学习算法,具有较好的分类准确率。针对该算法计算复杂度较高的不足,提出了一种基于谱聚类划分的随机森林算法。首先,利用聚类效果较好的谱聚类算法对原始样本集的每一类进行聚类处理。然后,在每一聚类簇中随机选取一个样本作为代表,组成新训练样本集合。最后,在新训练样本集上训练随机森林分类器。该算法通过谱聚类技术对原始样本进行了初步划分,将位置相近的多个样本用簇内的一个样本代表,较大程度地减少了训练样本的个数。在Corel Image图像识别数据集上的实验表明,算法可以用较少的分类时间达到较高的分类精度。     

The zeros of random polynomials: further results and applications

We consider the density of the zeros of random polynomials with nonzero mean correlated Gaussian coefficients. We show that for most communication problems the original result by Hammersley (1956) can be expressed in a simpler form. In order to illustrate the usefulness of the presented theory, two applications are considered. First, the zeros of frequency-selective Ricean fading channels are investigated. Second, the zeros of the transfer function corresponding to channel impulse response estimates obtained by a least-squares approach are calculated. For both applications implications for equalizer design are discussed     

A uniform-complexity treatment of encryption and zero-knowledge

We provide a treatment of encryption and zero-knowledge in terms of uniform complexity measures. This treatment is appropriate for cryptographic settings modeled by probabilistic polynomial-time machines. Our uniform treatment allows the construction of secure encryption schemes and zero-knowledge proof systems (for allNP) using only uniform complexity assumptions. We show that uniform variants of the two definitions of security, presented in the pioneering work of Goldwasser and Micali, are in fact equivalent. Such a result was known before only for nonuniform formalization. Nonuniformity is implicit in all previous treatments of zero-knowledge in the sense that a zero-knowledge proof is required to “leak no knowledge” onall instances. For practical purposes, it suffices to require that it isinfeasible to find instances on which a zero-knowledge proof “leaks knowledge.” We show how to construct such zero-knowledge proof systems for every language inNP, using only a uniform complexity assumption. Properties of uniformly zero-knowledge proofs are investigated and their utility is demonstrated. This research was partially supported by the Fund for Basic Research Administered by the Israeli Academy of Sciences and Humanities. Revision of this work was supported by Grant No. 89-00312 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel.     

Progressive random sampling: a multiperiod estimation techniquewith applications

A number of applications, including claims made under Federal social welfare programs, require retrospective sampling over multiple time periods. A common characteristic of such samples is that population members could appear in multiple time periods. When this occurs, and when the marginal cost of obtaining multiperiod information is minimum for a member appearing in the sample of the period being actively sampled, then a method which is herein called progressive random sampling (PRS) may be applied. The proposed method serves to either improve sampling estimates or reduce sample sizes, as demonstrated by two example applications     

How to construct constant-round zero-knowledge proof systems for NP

Constant-round zero-knowledge proof systems for every language in are presented, assuming the existence of a collection of claw-free functions. In particular, it follows that such proof systems exist assuming the intractability of either the Discrete Logarithm Problem or the Factoring Problem for Blum integers.     

JOINT RANDOM OPTIMIZED THREE—STEP SEARCH ALGORITHM BASED—ON GRAY AND CHROMATIC INFORMATION

In this letter,an improved three-step search algorithm is presented,which uses both gray and chromatic information to boost the performance with random optimization and converge the motion vectors to global optima.Experimental results show that this algorithm can efficiently improve the PSNR after motion compensation.     

Truly random number generators based on a non-autonomous chaotic oscillator

A non-autonomous chaotic circuit which is suitable for high-frequency integrated circuit (IC) realization is presented. Simulation and experimental results verifying the feasibility of the circuit are given. We have numerically verified that the bit streams obtained from the stroboscopic Poincaré map of the system passed the four basic tests of FIPS-140-2 test suite. We also have verified that the binary data obtained from the hardware realization of this continuous-time chaotic oscillator in the same way pass the full NIST random number test suite. Then, in order to increase the output throughput and the statistical quality of the generated bit sequences, we propose a TRNG design which uses a dual oscillator architecture with the proposed continuous-time chaotic oscillator. Finally, we have experimentally verified that the binary data obtained by this oscillator sampling technique pass the tests of full NIST random number test suite without Von Neumann processing for a higher throughput speed while compared with the previous one where the proposed continuous-time chaotic oscillator is used alone.     

Locally optimum detection of signals in a generalized observationmodel: the random signal case

Locally optimum detectors for weak random signals are derived for a generalized observation model incorporating signal-dependent and multiplicative noise. It is shown that the locally optimum random-signal detectors in the generalized observation model are interesting generalizations of those that would be obtained in the purely additive noisy signal model. Examples of explicit results for the locally optimum detector test statistics are given for some typical cases. Both asymptotic and finite sample-size performances of the locally optimum detectors are considered and compared with those of other standard detector structures     

A random sequence generator based on chaotic circuits

In this paper, a random sequence generator based on chaotic circuits is presented. Fundamental principle and experimental circuit have been carried out in case of Chua's circuit. The statistical results are in good agreement with probability characteristics of random sequence.