A modification of the RSA public-key encryption procedure (Corresp.)

The Rivest, Shamir, and Adleman (RSA) public-key encryption algorithm can be broken if the integerRused as the modulus can be factored. It my however be possible to break this system without factoringR. A modification of the RSA scheme is described. For this modified version it is shown that, if the encryption procedure can be broken in a certain number of operations, thenRcan be factored in only a few more operations. Furthermore, this technique can also be used to produce digital signatures, in much the same manner as the RSA scheme.     

Batch RSA

We present a variant of the RSA algorithm called Batch RSA with two important properties:

Efficient cryptographic schemes provably as secure as subset sum

We show very efficient constructions for a pseudorandom generator and for a universal one-way hash function based on the intractability of the subset-sum problem for certain dimensions. (Pseudorandom generators can be used for private-key encryption and universal one-way hash functions for signature schemes.) The increase in efficiency in our construction is due to the fact that many bits can be generated/hashed with one application of the assumed one-way function.All of our constructions can be implemented in NC using an optimal number of processors.Part of this work was done while both authors were at the University of California at Berkeley and part when the second author was at the IBM Almaden Research Center. Research supported by NSF Grant CCR 88-13632. A preliminary version of this paper appeared in Proc. 30th Symposium on Foundations of Computer Science, 1989.Incumbent of the Morris and Rose Goldman Career Development Chair. Research supported by an Alon Fellowship and a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences.     

Computation of simple and group factors of multivariate polynomials

This paper generalizes a recent result onsimple factorization of 2-variable (2-v) polynomials to simple andgroup factorization ofn-variate (n-v), (n3) polynomials. The emphasis is on developing a reliablenumerical technique for factorization. It is shown that simple as well as group factorization can be achieved by performing singular value decomposition (SVD) on certain matrices obtained from the coefficients of the givenn-v polynomial expressed in a Kronecker product form. For the polynomials that do not have exact simple and/or group factors, the concepts of approximate simple and group factorization are developed. The use of SVD leads to an elegant solution of an approximaten factorization problem. Several nontrivial examples are included to illustrate the results presented in this paper.Research supported by WRDC grant F33615-88-C-3605, NSF grant ECS-9110636, and NSERC of Canada grant A1345.     

Conservative Input–State–Output Systems with Evolution on a Multidimensional Integer Lattice

A fundamental object of study in both operator theory and system theory is a discrete-time conservative system (variously also referred to as a unitary system or unitary colligation). In this paper we introduce three equivalent multidimensional analogues of a unitary system where the time axis , d>1, is multidimensional. These multidimensional formalisms are associated with the names of Roesser, Fornasini and Marchesini, and Kalyuzhniy–Verbovetzky. We indicate explicitly how these three formalisms generate the same behaviors. In addition, we show how the initial-value problem (including the possibility of initial conditions at infinity) can be solved for such systems with respect to an arbitrary shift-invariant sublattice as the analogue of the positive-time axis. Some of our results are new even for the d=1 case.First online version published in May 2005*The authors were supported in part by a grant from the US-Israel Binational Science Foundation.     

Stability analysis of discontinuous dynamical systems using vector Lyapunov functions

In this paper, we establish several stability results for discontinuous dynamical systems defined onR ⁺=[0, ) which make use of vector Lyapunov functions. For the scalar case, these results yield in particular theprincipal Lyapunov stability results for discontinuous dynamical systems reported earlier. We demonstrate the applicability of our results by studying a class of interconnected discontinuous dynamical systems and several specific examples.This research was supported in part by an Alexander von Humboldt Foundation Senior Research Award, Institut für Nachrichtentechnik, Ruhr-Universität Bochum, Germany, and by a Center of Applied Mathematics Fellowship, University of Notre Dame.     

Instantiability of RSA-OAEP Under Chosen-Plaintext Attack

We show that the widely deployed RSA-OAEP encryption scheme of Bellare and Rogaway (Eurocrypt 1994), which combines RSA with two rounds of an underlying Feistel network whose hash ( i.e., round) functions are modeled as random oracles, meets indistinguishability under chosen-plaintext attack (IND-CPA) in the standard model based on simple, non-interactive, and non-interdependent assumptions on RSA and the hash functions. To prove this, we first give a result on a more general notion called “padding-based” encryption, saying that such a scheme is IND-CPA if (1) its underlying padding transform satisfies a “fooling" condition against small-range distinguishers on a class of high-entropy input distributions, and (2) its trapdoor permutation is sufficiently lossy as defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satisfies condition (1) if its hash function is t-wise independent for t roughly proportional to the allowed message length. We clarify that this result requires the hash function to be keyed, and for its key to be included in the public key of RSA-OAEP. We also show that RSA satisfies condition (2) under the \(\Phi \)-Hiding Assumption of Cachin et al. (Eurocrypt 1999). This is the first positive result about the instantiability of RSA-OAEP. In particular, it increases confidence that chosen-plaintext attacks are unlikely to be found against the scheme. In contrast, RSA-OAEP’s predecessor in PKCS #1 v1.5 was shown to be vulnerable to such attacks by Coron et al. (Eurocrypt 2000).     

A design of a fast pipelined modular multiplier based on a diminished-radix algorithm

We present a new serial-parallel concurrent modular-multiplication algorithm and architecture suitable for standard RSA encryption. In the new scheme, multiplication is performed modulo a multiple of the RSA modulus n, which has a diminished-radix form 2 ^k -v, where k and v are positive integers and v < n. This design is the first concurrent modular multiplier to use a diminished-radix algorithm and to pipeline concurrent modular-reduction to optimize the clock rate. For a modular multiplier of order ranging from 1 to 10 (number of multiplier bits per clock cycle), a faster clock rate and throughput is possible than with other known designs including those of Brickell, Morita, Sedlak and Golze, and Miyaguchi. Throughput estimates for 512-bit RSA decryption range from 100 kbit/s in a serial mode to 650 kbit/s with a modular multiplier of order 10, at a clock rate of 20 MHz on 1.5 m CMOS.     

Control of bifurcation in current-programmed dc/dc converters: An alternative viewpoint of ramp compensation

This paper reexamines the conventional current-mode control strategy as applied to dc/dc converters in the light of avoiding bifurcation. This alternative viewpoint permits convenient selection of parameter values to guarantee stable operation. The traditional slope compensation is viewed as a means to keep the system sufficiently remote from the first bifurcation point. It is shown that excessive bifurcation clearance is accompanied by undesirably slow dynamical response. A variable ramp compensation is proposed to dynamically adjust the slope magnitude so that the system is kept clear of bifurcation, yet responds sufficiently fast during transients. The results have been confirmed by experimental measurements.Work supported in part by the Hong Kong Research Grant Council under a competitive earmarked grant (no. PolyU5131/99E) and a Hong Kong Polytechnic University research grant (no. A-PB29).     

Quantitative analysis for linear hybrid cellular automata and LFSR as built-in self-test generators for sequential faults

This paper presents a combinatorial method of evaluating the effectiveness of linear hybrid cellular automata (LHCA) and linear feedback shift registers (LFSR) as generators for stimulating faults requiring a pair of vectors. We provide a theoretical analysis and empirical comparisons to see why the LHCA are better than the LFSRs as generators for sequential-type faults in a built-in self-test environment. Based on the concept of a partner set, the method derives the number of distinctk-cell substate vectors which have 2^2k , 1k[n/2], transition capability for ann-cell LHCA and ann-cell LFSR with maximum length cycles. Simulation studies of the ISCAS85 benchmark circuits provide evidence of the effectiveness of the theoretrical metric.This work was supported in part by Reserach Grants No. 5711 and No. 39409 and a Strategic Grant from the Natural Sciences and Engineering Research Council of Canada and by an equipments loan from the Canadian Microelectronics Corporation.A preliminary version of this paper is partially presented at theIEEE ISCAS'94, May 1994.     

Mobility degradation effects in CMOS differential pair transconductors

The influence of the mobility reduction factor on the dominant third-harmonic distortion and effective transconductance in CMOS differential pair transconductors is examined. Analytical expressions are developed which are suitable for hand calculation and generate realistic estimates for distortion and transconductance. The results produced have been tested against SPICE simulations over a wide range of parameter values and show excellent agreement. The analysis highlights the importance of mobility degradation and reveals that the linearity of the source-coupled differential pair is actually improved as the mobility reduction factor increases. This surprising finding suggests that where 0.15, for example, acceptably low distortion levels (<60 dB for V _i =1 V _pp ) should be achievable with the basic long-tailed pair and that complex linearization schemes may be unnecessary.This work is supported by a grant of the Science and Engineering Research Council.     

Universal approximation capability of EBF neural networks with arbitrary activation functions

The purpose of this paper is to investigate the approximation capability of elliptic basis function (EBF) neural networks. The main results are: (1) A necessary and sufficient condition for a functionS (R ¹) to be qualified as an activation function in the hidden layer of an EBF neural network is given. (2) Every nonzero functionG L ²(R ⁿ ) is qualified to be an activation function in the elliptic neural network to approximate any function in L²(Rⁿ). (3) As applications, we give new proofs of the theorems concerning the approximation capability of affine basis function (ABF) neural networks and generalized radial basis function (GRBF) neural networks (including radial basis function neural networks) with arbitrary activation functions. In particular, we solve the problem of the approximation capability of sigma-pi neural networks.Work was supported in part by CNSF, the Shanghai Science Foundations and Doctoral Program of Education Commissions of China.     

Functional inversion and communication complexity

We study the relationship between the multiparty communication complexity of functions over certain communication topologies and the complexity of inverting those functions. We show that if a function ofn variables has aring-protocol or atree-protocol of communication complexity bounded by ϕ, then there is a circuit of size that computes an inverse of the function. Consequently, we prove that although invertingNC ⁰ Boolean circuits isNP-hard, planarNC ¹ Boolean circuits can be inverted inNC, and hence in polynomial time. From the ring-protocol theorem, we derive an ω(n logn) lower bound on the VLSI area required to lay out any one-way function. Our results on inverting boolean circuits can be extended to algebraic circuits over finite rings. We prove that on certain topologies no one-way function can be computed with low communication complexity. The preliminary version of this paper appeared inCRYPTO 91. This work was supported in part by National Science Foundation Grant DCR-8713489. Part of this work was done while the author was at the School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, U.S.A. Current address: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, U.S.A.     

Verifiable Distributed Oblivious Transfer and Mobile Agent Security

The mobile agent is a fundamental building block of the mobile computing paradigm. In mobile agent security, oblivious transfer (OT) from a trusted party can be used to protect the agent’s privacy and the hosts’ privacy. In this paper, we introduce a new cryptographic primitive called Verifiable Distributed Oblivious Transfer (VDOT), which allows us to replace a single trusted party with a group of threshold trusted servers. The design of VDOT uses a novel technique called consistency verification of encrypted secret shares. VDOT protects the privacy of both the sender and the receiver against malicious attacks of the servers. We also show the design of a system to apply VDOT to protect the privacy of mobile agents. Our design partitions an agent into the general portion and the security-sensitive portion. We also implement the key components of our system. As far as we know, this is the first effort to implement a system that protects the privacy of mobile agents. Our preliminary evaluation shows that protecting mobile agents not only is possible, but also can be implemented efficiently. This work was supported in part by the DoD University Research Initiative (URI) program administered by the Office of Naval Research under grant N00014-01-1-0795. Sheng Zhong was supported by ONR grant N00014-01-1-0795 and NSF grants ANI-0207399 and CCR-TC-0208972. Yang Richard Yang was supported in part by NSF grant ANI-0207399. A preliminary version of this paper was presented at the DialM-POMC Joint Workshop on Foundations of Mobile Computing in 2003. Sheng Zhong received his Ph.D. in computer science from Yale University in the year of 2004. He holds an assistant professor position at SUNY Buffalo and is currently on leave for postdoctoral research at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS). His research interests, on the practical side, are security and incentives in data mining, databases, and wireless networks. On the theoretical side, he is interested in cryptography and game theory. Yang Richard Yang is an Assistant Professor of Computer Science at Yale University. His research interests include computer networks, mobile computing, wireless networking, sensor networks, and network security. He leads the LAboratory of Networked Systems (LANS) at Yale. His recent awards include a Schlumberger Fellowship and a CAREER Award from the National Science Foundation. He received his B.E. degree from Tsinghua University (1993), and his M.S. and Ph.D. degrees from the University of Texas at Austin (1998 and 2001).     

The design and implementation of a private message service for mobile computers

Even as wireless networks create the potential for access to information from mobile platforms, they pose a problem for privacy. In order to retrieve messages, users must periodically poll the network. The information that the user must give to the network could potentially be used to track that user. However, the movements of the user can also be used to hide the user's location if the protocols for sending and retrieving messages are carefully designed. We have developed a replicated memory service which allows users to read from memory without revealing which memory locations they are reading. Unlike previous protocols, our protocol is efficient in its use of computation and bandwidth. In this paper, we will show how this protocol can be used in conjunction with existing privacy preserving protocols to allow a user of a mobile computer to maintain privacy despite active attacks.The work reported was supported by ARPA/ONR grant N00014-92-J-1866 and a grant by Siemens Corp. The views expressed herein are those of the authors and do not represent the opinions of ARPA/ONR or Siemens Corp.This paper is a revised and extended version of Preserving Privacy in a Network of Mobile Computers presented at the 1995 IEEE Symposium on Security and Privacy.     

Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities

We show how to find sufficiently small integer solutions to a polynomial in a single variable modulo N, and to a polynomial in two variables over the integers. The methods sometimes extend to more variables. As applications: RSA encryption with exponent 3 is vulnerable if the opponent knows two-thirds of the message, or if two messages agree over eight-ninths of their length; and we can find the factors of N=PQ if we are given the high order bits of P. Received 21 December 1995 and revised 11 August 1996     

On the Chor—Rivest knapsack cryptosystem

Among all public-key cryptosystems that depend on the knapsack problem, the system proposed by Chor and Rivest (IEEE Trans. Inform. Theory 34 (1988), 901–909) is one of the few that have not been broken. The main difficulty in implementing their system is the computation of discrete logarithms in large finite fields. In this note we describe the powerline system, which is a modification of the Chor-Rivest system that does not have this shortcoming. The powerline system, which is not a knapsack system, is at least as secure as the original Chor-Rivest system.The author was supported by NSF under Grant Nos. DMS 87-06176 and DMS 90-02939, and by NSA/MSP under Grant No. MDA90-H-4043.     

Layered Access Control Schemes on Watermarked Scalable Media

Intellectual Property (IP) protection is a critical element in multimedia transmission and delivery systems. Conventional IP protection on multimedia data can be categorized into encryption and watermarking. In this paper, a structure to perform layered access control on scalable media by combining encryption and robust watermarking is proposed, implemented, and verified. By taking advantages of the nature of both encryption and watermarking, copyrights of multimedia contents can be well protected and at the same time, multiple-grade services can be provided. In the summated examples, we assume a scalable transmission scheme over the broadcasting environment and use it to test the effectiveness of proposed method. When the embedded watermark is extracted with high confidence, the key to decrypt the next layer can be perfectly recovered. Then, the media contents are reconstructed and the copyrights are assured. The application examples also demonstrate the practicality of the proposed system.

Index two linear time varying singular systems of differential equations

Linear time varying singular systems of differential equations of the formA(t)x(t) + B(t)x(t)=f(t) whereA(t) is singular and the system has index at most two are considered. Recent results on their analytic solution are improved on. Examples are given that show these results are not easily extended.This work was supported in part by the National Science Foundation under Grant No. DMS-8318026 and the Air Force Office of Scientific Research under Grant No. 84-0240.     

A Public Key Cryptosystem Based on Non-abelian Finite Groups

We present a new approach to designing public-key cryptosystems based on covers and logarithmic signatures of non-abelian finite groups. Initially, we describe a generic version of the system for a large class of groups. We then propose a class of 2-groups and argue heuristically about the system’s security. The system is scalable, and the proposed underlying group, represented as a matrix group, affords significant space and time efficiency. This work was partially supported by a Federal Earmark grant for Research in Secure Telecommunication Networks (2004-05).