Factorizations in the elementary Abelian p-group and their cryptographic significance

Let G be a finite group and let A _i 1 i s, be subsets of G where ¦A _i ¦ 2, 1 i s and s 2. We say that (A₁, A₂,..., A₃) is a factorization of G if and only if for each g G there is exactly one way to express g = a ₁ a ₁ a ₂··· a ₃, where a _j A _i , 1 i s.The problem of finding factorizations of this type was first introduced by Hajos [3] in 1941. Since then a number of papers have appeared on the subject. More recently, Magliveras [6] has applied factorization of permutation groups to cryptography to obtain a private-key cryptosystem. Factorizations in the elementary abelian p-group were exploited (but not explicitly stated in these terms) by Webb [13] to produce a public-key cryptosystem conceptually similar to cryptosystems based on the knapsack problem.Using the result that certain types of factorizations in the elementary abelian p-group are necessarily transversal (a term introduced by Magliveras), this paper shows that the public-key system proposed by Webb is insecure.     

New Approaches to Designing Public Key Cryptosystems Using One-Way Functions and Trapdoors in Finite Groups

A symmetric key cryptosystem based on logarithmic signature s for finite permutation groups was described by the first author in [6], and its algebraic properties were studied in [7]. In this paper we describe two possible approaches to the construction of new public key cryptosystems with message space a large finite group G , using logarithmic signature s and their generalizations. The first approach relies on the fact that permutations of the message space G induced by transversal logarithmic signature s almost always generate the full symmetric group S _G on the message space. The second approach could potentially lead to new ElGamal-like systems based on trapdoor, one-way functions induced by logarithmic signature -like objects we call meshes , which are uniform covers for G .     

Exploiting multi-interface networks: Connectivity and Cheapest Paths

Let G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at least one active interface. In general, every node holds a subset of all the possible k interfaces. Such networks are known as multi-interface networks. In this setting, we study two basic problems: Connectivity and Cheapest Path. The Connectivity problem corresponds to the well-known Minimum Spanning Tree problem in graph theory. In practice, we need to cover a subgraph of G of minimum cost which contains a spanning tree of G. The problem turns out to be APX-hard in general and for many restricted graph classes, however it is possible to provide approximation algorithms: a 2-approximation in general and a (2-\frac1 k)(2-\frac{1}{ k})-approximation for the unit cost interface case, i.e. when the cost of activating an interface is unitary for any interface. We also consider the problem in special graph classes, such as graphs of bounded degree, planar graphs, graphs of bounded treewidth, complete graphs. The Cheapest Path problem corresponds to the well-known Shortest Path problem in graph theory. In the multi-interface setting this problem is still polynomially solvable, and we point out a simple Dijsktra-based algorithm with O(k|E|+k|V|log(k+|V|))O(k|E|+k|V|\log (k+|V|)) runtime in general and O(k(|E| + |V|)) runtime for the unit cost interface case.     

A New and Improved Paradigm for Hybrid Encryption Secure Against Chosen-Ciphertext Attack

We present a new encryption scheme which is secure against adaptive chosen-ciphertext attack (or CCA2-secure) in the standard model (i.e., without the use of random oracle). Our scheme is a hybrid one: it first uses a public-key step (the Key Encapsulation Module or KEM) to encrypt a random key, which is then used to encrypt the actual message using a symmetric encryption algorithm (the Data Encapsulation Module or DEM). Our scheme is a modification of the hybrid scheme presented by Shoup in (Euro-Crypt’97, Springer LNCS, vol. 1233, pp. 256–266, 1997) (based on the Cramer–Shoup scheme in CRYPTO’98, Springer LNCS, vol. 1462, pp. 13–25, 1998). Its major practical advantage is that it saves the computation of one exponentiation and produces shorter ciphertexts.     

Is the Data Encryption Standard a group? (Results of cycling experiments on DES)

The Data Encryption Standard (DES) defines an indexed set of permutations acting on the message space ={0,1}⁶⁴. If this set of permutations were closed under functional composition, then the two most popular proposals for strengthening DES through multiple encryption would be equivalent to single encryption. Moreover, DES would be vulnerable to a known-plaintext attack that runs in 2²⁸ steps on the average. It is unknown in the open literature whether or not DES has this weakness.Two statistical tests are presented for determining if an indexed set of permutations acting on a finite message space forms a group under functional composition. The first test is a meet-in-the-middle algorithm which uses O(K) time and space, where K is the size of the key space. The second test, a novel cycling algorithm, uses the same amount of time but only a small constant amount of space. Each test yields a known-plaintext attack against any finite, deterministic cryptosystem that generates a small group.The cycling closure test takes a pseudorandom walk in the message space until a cycle is detected. For each step of the pseudorandom walk, the previous ciphertext is encrypted under a key chosen by a pseudorandom function of the previous ciphertext. Results of the test are asymmetrical: long cycles are overwhelming evidence that the set of permutations is not a group; short cycles are strong evidence that the set of permutations has a structure different from that expected from a set of randomly chosen permutations.Using a combination of software and special-purpose hardware, the cycling closure test was applied to DES. Experiments show, with overwhelming confidence, that DES is not a group. Additional tests confirm that DES is free of certain other gross algebraic weaknesses. But one experiment discovered fixed points of the so-called weak-key transformations, thereby revealing a previously unpublished additional weakness of the weak keys.Support for this research was provided in part by the National Science Foundation under contract number MCS-8006938 and by the International Business Machines Corporation.     

Radiation defects in semiconductors under hydrostatic pressure

The effect of hydrostatic pressure on the sensitivity of the electrical properties of irradiated semiconductors as functions of the position of the Fermi level in the band gap of the crystal has been investigated. A numerical analysis of the experimental data has been performed. This analysis is based on a model of the crystal as having an isotropic band gap 〈E _G〉, where 〈E _G〉 is the average energy interval between the conduction band and the valence band. It is shown that varying the pressure results in hardly any change in the position of the radiation defect levels relative to the energy corresponding to the center of the isotropic gap 〈E _G〉/2, which is identical to the value of the “limiting” position of the Fermi level (F _lim) in an irradiated semiconductor. Fiz. Tekh. Poluprovodn. 33, 1290–1294 (November 1999)     

Edge inversion channels and surface leakage currents in high-voltage semiconductor devices

It is shown that the electric field over the surface of semiconductor devices can be sufficient to induce edge inversion channels if the bias voltage is high and the surface charge density Q _s is low. In this case, the edge region of the devices containing the p-n-p structure (e.g., that of thyristors) functions as a planar p-channel MIS transistor with a combined gate and drain and the entire medium over the surface functions as the gate insulator. The current between the source and drain of this “edge MIS transistor” is the surface leakage current of the entire device. An analytical theory describing the current-voltage characteristic in the subthreshold mode is developed. It is shown that this new mechanism controls the total leakage current of high-voltage devices if |Q _s | and temperature T are small enough (|Q _s | < 4 nC/cm², T < 270 K and |Q _s | < 58 nC/cm², T < 600 K for silicon and silicon carbide devices, respectively).     

Function-Private Functional Encryption in the Private-Key Setting

Functional encryption supports restricted decryption keys that allow users to learn specific functions of the encrypted messages. Although the vast majority of research on functional encryption has so far focused on the privacy of the encrypted messages, in many realistic scenarios it is crucial to offer privacy also for the functions for which decryption keys are provided. Whereas function privacy is inherently limited in the public-key setting, in the private-key setting it has a tremendous potential. Specifically, one can hope to construct schemes where encryptions of messages \(\mathsf{m}_1, \ldots , \mathsf{m}_T\) together with decryption keys corresponding to functions \(f_1, \ldots , f_T\), reveal essentially no information other than the values \(\{ f_i(\mathsf{m}_j)\}_{i,j\in [T]}\). Despite its great potential, the known function-private private-key schemes either support rather limited families of functions (such as inner products) or offer somewhat weak notions of function privacy. We present a generic transformation that yields a function-private functional encryption scheme, starting with any non-function-private scheme for a sufficiently rich function class. Our transformation preserves the message privacy of the underlying scheme and can be instantiated using a variety of existing schemes. Plugging in known constructions of functional encryption schemes, we obtain function-private schemes based either on the learning with errors assumption, on obfuscation assumptions, on simple multilinear-maps assumptions, and even on the existence of any one-way function (offering various trade-offs between security and efficiency).     

Correlation between the temperature dependence of the band gap and the temperature dependence of the enthalpy of semiconductor crystals

The first-principles pseudopotential method of density-functional theory is used to study electron-phonon interactions in silicon. The temperature shift of the indirect band gap, the phonon spectrum, and the enthalpy are calculated consistently within the density-functional theory. The relationship between the temperature dependence of the energy gap ΔE _g(T) and the temperature dependence of the enthalpy ΔH(T) is ΔH(T)=K|ΔE _g(T)|. The physical origin of this correlation is discussed. Fiz. Tekh. Poluprovodn. 32, 1025–1028 (September 1998)     

基于共扼编码的量子概率加密方案(英文)

We present a quantum probabilistic encryption algorithm for a private-key encryption scheme based on conjugate coding of the qubit string. A probabilistic encryption algorithm is generally adopted in public-key encryption protocols. Here we consider the way it increases the unicity distance of both classical and quantum private-key encryption schemes. The security of quantum probabilistic privatekey encryption schemes against two kinds of attacks is analyzed. By using the no-signalling postulate, we show that the scheme can resist attack to the key. The scheme’s security against plaintext attack is also investigated by considering the information-theoretic indistinguishability of the encryption scheme. Finally, we make a conjecture regarding Breidbart’s attack.     

Efficient,perfect polynomial random number generators

Let N be a positive integer and let P [x] be a polynomial that is nonlinear on the set _N of integers modulo N. If, by choosing x at random in an initial segment of _N , P(x) (mod N) appears to be uniformly distributed in _N to any polynomial-time observer, then it is possible to construct very efficient pseudorandom number generators that pass any polynomial-time statistical test. We analyse this generator from two points of view. A complexity theoretic analysis relates the perfectness of the generator to the security of the RSA-scheme. A statistical analysis proves that the least-significant bits of P(x) (mod N) are statistically random.This research was performed while C. P. Schnorr was visiting the Department of Computer Science of the University of Chicago, who also supported his research. A U.S. patent, based on this work, has been granted.     

A construction of a cipher from a single pseudorandom permutation

We suggest a scheme for a block cipher which uses only one randomly chosen permutation,F. The key, consisting of two blocks,K ₁ andK ₂, is used in the following way. The message block is XORed withK ₁ before applyingF, and the outcome is XORed withK ₂, to produce the cryptogram block. We show that the resulting cipher is secure (when the permutation is random or pseudorandom). This removes the need to store, or generate a multitude of permutations. Shimon Even was supported by the Fund for the Promotion of Research at the Technion, and by Bellcore, Morristown, NJ 07940, U.S.A. Part of the work was done while Yishay Mansour was in the IBM T.J. Watson Research Center.     

Magnetic-field dependence of the hopping conduction of electrostatically disordered quasi-2D semiconductor systems under the conditions for the insulator-metal percolation transition

Lateral conductance G of the metal-nitride-oxide-silicon mesoscopic transistor structures with the inversion n channel and a relatively high (no less than 10¹³ cm⁻²) concentration of integrated charges is studied versus magnetic field (up to 45 T) and potential of field electrode V _g at a temperature of 4.2 K. The characteristics of the saddle regions of the fluctuation electrostatic potential that form the mesoscopic percolation network as point quantum contacts are analyzed in the framework of the Landauer-Büttiker model. The measured features of the magnetic-field dependences of G in the low-inversion region (a transition from the positive magnetoresistive effect at G ≤ e ²/h to a relatively strong (about 100%) negative magnetoresistive effect with an increase in V _g) are related to structural modifications of percolation cluster under the action of the field effect. The dependences of G on magnetic field are in agreement with the dependences of G on V _g.     

Thermoelectric Properties of Co-Doped TiS<Subscript>2</Subscript>

The thermoelectric properties of cobalt-doped compounds Co _x Ti_1−x S₂ (0 ≤ x ≤ 0.3) prepared by solid-state reaction were investigated from 5 K to 310 K. It was found that the electric resistivity ρ and absolute thermopower |S| for all the doped compounds decreased significantly with increasing Co content over the whole temperature range investigated. The increased lattice thermal conductivity of the doped compounds would imply enhancement of the acoustic velocity. Moreover, the ZT value of the doped compounds was improved over the whole temperature range investigated, and specifically reached 0.03 at 310 K for Co_0.3Ti_0.7S₂, being about 66% larger than that of TiS₂.     

Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm

An authenticated encryption scheme is a symmetric encryption scheme whose goal is to provide both privacy and integrity. We consider two possible notions of authenticity for such schemes, namely integrity of plaintexts and integrity of ciphertexts, and relate them, when coupled with IND-CPA (indistinguishability under chosen-plaintext attack), to the standard notions of privacy IND-CCA and NM-CPA (indistinguishability under chosen-ciphertext attack and nonmalleability under chosen-plaintext attack) by presenting implications and separations between all notions considered. We then analyze the security of authenticated encryption schemes designed by “generic composition,” meaning making black-box use of a given symmetric encryption scheme and a given MAC. Three composition methods are considered, namely Encrypt-and-MAC, MAC-then-encrypt, and Encrypt-then-MAC. For each of these and for each notion of security, we indicate whether or not the resulting scheme meets the notion in question assuming that the given symmetric encryption scheme is secure against chosen-plaintext attack and the given MAC is unforgeable under chosen-message attack. We provide proofs for the cases where the answer is “yes” and counter-examples for the cases where the answer is “no.” M. Bellare’s work was supported in part by a 1996 Packard Foundation Fellowship in Science and Engineering, NSF CAREER Award CCR-9624439, NSF grants CNS-0524765 and CNS-0627779, and a gift from Intel Corporation. C. Namprempre’s work was supported in part by grants of the first author and the Thailand Research Fund.     

Specific features of conductivity of γ-irradiated TlGaTe<Subscript>2</Subscript> crystals with nanochain structure

Temperature dependences of electrical conductivity σ(T) and current-voltage characteristics of one-dimensional TlGaTe₂ single crystals subjected to various doses of γ-ray radiation in both geometries of the experiment-along nanochains parallel to the tetragonal axis of the crystal (σ_|) and perpendicular to these nanochains (σ_⊥)-are studied. It is shown that the dependence σ(T) measured in the ohmic region of the current-voltage characteristic is the shape typical of the hopping mechanism and can be described in terms of the Mott approximation. The values of the densities of localized states N _F, the activation energy E _a, the hop lengths R, the difference between the energies of states ΔE in the vicinity of the Fermi level, and the concentrations of deep traps N _t are determined. The current-voltage characteristics in the region of a more abrupt increase in the current are also studied. It is shown that this region of current-voltage characteristics is described in the context of the Pool-Frenkel thermal-field effect. Concentrations of ionized centers N _f , the free-path lengths λ, the Frenkel coefficients β, and the shape of the potential well in initial and irradiated (with 250 Mrad) TlGaTe₂ crystals are determined. It is shown that anisotropy of electrical conductivity changes under the effect of irradiation, which brings about translational ordering of nanochains.     

OAEP Reconsidered

The OAEP encryption scheme was introduced by Bellare and Rogaway at Eurocrypt '94. It converts any trapdoor permutation scheme into a public key encryption scheme. OAEP is widely believed to provide resistance against adaptive chosen ciphertext attack. The main justification for this belief is a supposed proof of security in the random oracle model, assuming the underlying trapdoor permutation scheme is one way. This paper shows conclusively that this justification is invalid. First, it observes that there appears to be a non-trivial gap in the OAEP security proof. Second, it proves that this gap cannot be filled, in the sense that there can be no standard ``black box' security reduction for OAEP. This is done by proving that there exists an oracle relative to which the general OAEP scheme is insecure. The paper also presents a new scheme OAEP+ , along with a complete proof of security in the random oracle model. OAEP+ is essentially just as efficient as OAEP. It should be stressed that these results do not imply that a particular instantiation of OAEP, such as RSA-OAEP, is insecure. They simply undermine the original justification for its security. In fact, it turns out—essentially by accident, rather than by design—that RSA-OAEP is secure in the random oracle model; however, this fact relies on special algebraic properties of the RSA function, and not on the security of the general OAEP scheme.     

Efficient Amplification of the Security of Weak Pseudo-Random Function Generators

Abstract. We show that given a PRFG (pseudo-random function generator) G that is (1/n ^c ) -partially secure there exists a polynomial p such that the construction g ₁ (x ⊕ r ₁) ⊕ · ⊕ g _p(n) (x ⊕ r _p(n) ) produces a strongly secure PRFG, where g _i ∈ G and r _i are strings of random bits, and the key for the new PRFG is composed of the r _i 's and keys for the g _i 's. This is the first ``natural' construction of a (totally secure) PRFG from a partially secure PRFG. Using results of Luby and Rackoff, this result also demonstrates how to construct a PRPG ``naturally' from a partially secure PRPG.     

New op-amp-RC to G m -C transformation method

A new transformation method is proposed and used to transform op-amp-RC circuits to G _m -C ones with only grounded capacitors. The proposed method enables the generation of high-performance G _m -C filters that benefit from the advantages of good and well-known op-amp-RC structures and at the same time feature electronic tunability, high frequency capability and monolithic integration ability. An attractive feature of the proposed method is that it results in G _m -C structures with only grounded capacitors in spite of the presence of floating capacitors in the original op-amp-RC circuits. Ahmed M. Soliman was born in Cairo Egypt, on November 22, 1943. He received the B.Sc. degree with honors from Cairo University, Cairo, Egypt, in 1964, the M.S. and Ph.D. degrees from the University of Pittsburgh, Pittsburgh, PA, U.S.A., in 1967 and 1970, respectively, all in Electrical Engineering. He is currently Professor Electronics and Communications Engineering Department, Cairo University, Egypt. From September 1997–September 2003, Dr. Soliman served as Professor and Chairman Electronics and Communications Engineering Department, Cairo University, Egypt. From 1985–1987, Dr. Soliman served as Professor and Chairman of the Electrical Engineering Department, United Arab Emirates University, and from 1987–1991 he was the Associate Dean of Engineering at the same University. He has held visiting academic appointments at San Francisco State University, Florida Atlantic University and the American University in Cairo. He was a visiting scholar at Bochum University, Germany (Summer 1985) and with the Technical University of Wien, Austria (Summer 1987). In November 2005, Dr. Soliman gave a lecture at Nanyang Technological University, Singapore. Dr. Soliman was also invited to visit Taiwan and gave lectures at Chung Yuan Christian University and at National Central University of Taiwan. In 1977, Dr. Soliman was decorated with the First Class Science Medal, from the President of Egypt, for his services to the field of Engineering and Engineering Education. Dr. Soliman is a Member of the Editorial Board of the IEE Proceedings Circuits, Devices and Systems. Dr. Soliman is a Member of the Editorial Board of Analog Integrated Circuits and Signal Processing. Dr. Soliman served as Associate Editor of the IEEE Transactions on Circuits and Systems I (Analog Circuits and Filters) from December 2001 to December 2003 and is Associate Editor of the Journal of Circuits, Systems and Signal Processing from January 2004–Now.     

Translucent Cryptography—An Alternative to Key Escrow, and Its Implementation via Fractional Oblivious Transfer

We present an alternative to the controversial ``key-escrow' techniques for enabling law enforcement and national security access to encrypted communications. Our proposal allows such access with probability p for each message, for a parameter p between 0 and 1 to be chosen (say, by Congress) to provide an appropriate balance between concerns for individual privacy, on the one hand, and the need for such access by law enforcement and national security, on the other. (For example, with p=0.4 , a law-enforcement agency conducting an authorized wiretap which records 100 encrypted conversations would expect to be able to decrypt (approximately) 40 of these conversations; the agency would not be able to decrypt the remaining 60 conversations at all.) Our scheme is remarkably simple to implement, as it requires no prior escrowing of keys. We implement translucent cryptography based on noninteractive oblivious transfer. Extending the schemes of Bellare and Micali [2], who showed how to transfer a message with probability ?, we provide schemes for noninteractive fractional oblivious transfer, which allow a message to be transmitted with any given probability p . Our protocol is based on the Diffie—Hellman assumption and uses just one El Gamal encryption (two exponentiations), regardless of the value of the transfer probability p . This makes the implementation of translucent cryptography competitive, in efficiency of encryption, with current suggestions for software key escrow. Received 19 September 1996 and revised 1 November 1997