On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions

Fix a small nonempty set of blockcipher keys  . We say a blockcipher-based hash function is highly-efficient if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from  . Although a few highly-efficient constructions have been proposed, no one has been able to prove their security. In this paper we prove, in the ideal-cipher model, that it is impossible to construct a highly-efficient iterated blockcipher-based hash function that is provably secure. Our result implies, in particular, that the Tweakable Chain Hash (TCH) construction suggested by Liskov, Rivest, and Wagner (Advances in Cryptology–CRYPTO ’02, Lecture Notes in Computer Science, vol. 2442, pp. 31–46, Springer, Berlin, 2002) is not correct under an instantiation suggested for this construction, nor can TCH be correctly instantiated by any other efficient means.     

Polytype Stability and Microstructural Characterization of Silicon Carbide Epitaxial Films Grown on [ {\hbox{11}}\overline{{\hbox{2}}} {\hbox{0}} ]- and [0001]-Oriented Silicon Carbide Substrates

The polytype and surface and defect microstructure of epitaxial layers grown on 4H(), 4H(0001) on-axis, 4H(0001) 8° off-axis, and 6H(0001) on-axis substrates have been investigated. High-resolution x-ray diffraction (XRD) revealed the epitaxial layers on 4H() and 4H(0001) 8° off-axis to have the 4H-SiC (silicon carbide) polytype, while the 3C-SiC polytype was identified for epitaxial layers on 4H(0001) and 6H(0001) on-axis substrates. Cathodoluminescence (CL), Raman spectroscopy, and transmission electron microscopy (TEM) confirmed these results. The epitaxial surface of 4H() films was specular with a roughness of 0.16-nm root-mean-square (RMS), in contrast to the surfaces of the other epitaxial layer-substrate orientations, which contained curvilinear boundaries, growth pits (∼3 × 10⁴ cm⁻²), triangular defects >100 μm, and significant step bunching. Molten KOH etching revealed large defect densities within 4H() films that decreased with film thickness to ∼10⁶ cm⁻² at 2.5 μm, while cross-sectional TEM studies showed areas free of defects and an indistinguishable film-substrate interface for 4H() epitaxial layers.     

A Rate \text{ M }_{\mathrm{T}} Full Diversity STF Block Coded 4\times 4 MIMO-OFDM System with Reduced Complexity

Multiple input multiple output (MIMO) communication systems with orthogonal frequency division multiplexing (OFDM) has a great role to play for 4G broadband wireless communications. In this paper, a space time frequency (STF) code is presented with reduced decoder complexity and to achieve code rate $\text{ M }_\mathrm{T}$ with full diversity of $\text{ M }_{\mathrm{T}} \text{ M }_{\mathrm{R}} \text{ N }_{\mathrm{b}}$ L i.e., product of number of transmit antennas ( $\text{ M }_\mathrm{T}$ ), receive antennas $(\text{ M }_{\mathrm{R}})$ , fading blocks $(\text{ N }_{\mathrm{b}})$ and channel taps (L). The maximum achievable diversity with high rate of STF block coded MIMO-OFDM is analyzed and verified by simulation results. The decoder complexity is resolved by employing several approaches like maximum likelihood (ML), sphere decoder (SD) and array processing. The performance of STF code is compared with existing layered algebraic STF code in terms of decoder complexity and bit error rate (BER). Further, the closed form expressions for BER performance of STFBC MIMO-OFDM systems are derived and evaluated for frequency selective block fading channels with MPSK constellations.     

New Binding-Concealing Trade-Offs for Quantum String Commitment

String commitment schemes are similar to the well-studied bit commitment schemes in cryptography with the difference that the committing party, say , is supposed to commit a long string instead of a single bit to another party, say . Similar to bit commitment schemes, such schemes are supposed to be binding, i.e., cannot change her choice after committing, and concealing, i.e., cannot find ’s committed string before reveals it. Ideal commitment schemes are known to be impossible. Even if some degree of cheating is allowed, Buhrman et al. (, Nov. 2007) have recently shown that there are some binding-concealing trade-offs that any quantum string commitment scheme ( ) must follow. They showed trade-offs both in the scenario of single execution of the protocol and in the asymptotic regime of sufficiently large number of parallel executions of the protocol. We present here new trade-offs in the scenario of single execution of a protocol. Our trade-offs also immediately imply the trade-off shown by Buhrman et al. in the asymptotic regime. We show our results by making a central use of an important information theoretic tool called the substate theorem due to Jain et al. (Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 429–438, 2002). Our techniques are quite different from that of Buhrman et al. (, Nov. 2007) and may be of independent interest.     

Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields

In 2008 and 2009, Gaudry and Diem proposed an index calculus method for the resolution of the discrete logarithm on the group of points of an elliptic curve defined over a small degree extension field $\mathbb{F}_{q^{n}}$ . In this paper, we study a variation of this index calculus method, improving the overall asymptotic complexity when $n = \varOmega(\sqrt [3]{\log_{2} q})$ . In particular, we are able to successfully obtain relations on $E(\mathbb{F}_{q^{5}})$ , whereas the more expensive computational complexity of Gaudry and Diem’s initial algorithm makes it impractical in this case. An important ingredient of this result is a variation of Faugère’s Gröbner basis algorithm F4, which significantly speeds up the relation computation. We show how this index calculus also applies to oracle-assisted resolutions of the static Diffie–Hellman problem on these elliptic curves.     

Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves

Efficiently computable homomorphisms allow elliptic curve point multiplication to be accelerated using the Gallant–Lambert–Vanstone (GLV) method. Iijima, Matsuo, Chao and Tsujii gave such homomorphisms for a large class of elliptic curves by working over \mathbbF_p²{\mathbb{F}}_{p^{2}}. We extend their results and demonstrate that they can be applied to the GLV method.     

Four-Dimensional Gallant–Lambert–Vanstone Scalar Multiplication

The GLV method of Gallant, Lambert, and Vanstone (CRYPTO 2001) computes any multiple kP of a point P of prime order n lying on an elliptic curve with a low-degree endomorphism Φ (called GLV curve) over $\mathbb{F}_{p}$ as $$kP = k_1P + k_2\varPhi(P) \quad\text{with } \max \bigl\{ |k_1|,|k_2| \bigr\} \leq C_1\sqrt{n} $$ for some explicit constant C ₁>0. Recently, Galbraith, Lin, and Scott (EUROCRYPT 2009) extended this method to all curves over $\mathbb{F}_{p^{2}}$ which are twists of curves defined over $\mathbb{F}_{p}$ . We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over $\mathbb{F}_{p^{2}}$ , a four-dimensional decomposition together with fast endomorphisms Φ,Ψ over $\mathbb{F}_{p^{2}}$ acting on the group generated by a point P of prime order n, resulting in a proven decomposition for any scalar k∈[1,n] given by $$kP=k_1P+ k_2\varPhi(P)+ k_3\varPsi(P) + k_4\varPsi\varPhi(P) \quad \text{with } \max_i \bigl(|k_i| \bigr)< C_2\, n^{1/4} $$ for some explicit C ₂>0. Remarkably, taking the best C ₁,C ₂, we obtain C ₂/C ₁<412, independently of the curve, ensuring in theory an almost constant relative speedup. In practice, our experiments reveal that the use of the merged GLV–GLS approach supports a scalar multiplication that runs up to 1.5 times faster than the original GLV method. We then improve this performance even further by exploiting the Twisted Edwards model and show that curves originally slower may become extremely efficient on this model. In addition, we analyze the performance of the method on a multicore setting and describe how to efficiently protect GLV-based scalar multiplication against several side-channel attacks. Our implementations improve the state-of-the-art performance of scalar multiplication on elliptic curves over large prime characteristic fields for a variety of scenarios including side-channel protected and unprotected cases with sequential and multicore execution.     

Extruded Bismuth-Telluride-Based <Emphasis Type="Italic">n</Emphasis>-Type Alloys for Waste Heat Thermoelectric Recovery Applications

Thermoelectric (TE) generator modules for a number of waste heat recovery applications are required to operate between room temperature and 500 K, a temperature range for which the composition of bismuth-telluride-based alloys needs to be adjusted to optimize performance. In particular n-type alloys do not perform as well as p-type and require a more systematic study. We have produced, by mechanical alloying followed by hot extrusion, alloys, within the range with fixed carrier concentration () to optimize their TE performance in the temperature range 300 K to 420 K. The optimum composition has been identified to be and which is very close to the composition that also maximizes the ratio of the electron mobility to the lattice component of the thermal conductivity. The optimized alloy performance can be further increased by adjusting the carrier concentration.     

Phase Equilibria of BaO-R2O3-CuO z Systems (R = Y and Lanthanides) under CO2-free Conditions

For applications ranging from phase equilibria to the processing of second-generation high T _c superconductor-coated-conductors, phase diagrams constructed under carbonate-free conditions are needed. Subsolidus phase equilibria of BaO-R₂O₃-CuO _z (R = Ho) have been investigated at (810°C), 21 kPa (875°C) and 0.1 MPa (850 and 930°C) by applying controlled atmosphere methods to minimize the presence of carbonate and CO₂ and H₂O contamination. Under carbonate-free conditions, most of these phase diagrams are different from those reported in the literature. In this paper, we also review and compare the phase diagrams of ten BaO-R₂O₃-CuO _z systems (R = Nd, Sm, Eu, Gd, Dy, Y, Ho, Er, Tm and Yb) that were previously determined in this laboratory under Among these diagrams, a distinct trend of phase formation and tie-line relationships is observed.     

Simpler Session-Key Generation from Short Random Passwords

Goldreich and Lindell (CRYPTO ’01) recently presented the first protocol for password-authenticated key exchange in the standard model (with no common reference string or set-up assumptions other than the shared password). However, their protocol uses several heavy tools and has a complicated analysis. We present a simplification of the Goldreich–Lindell (GL) protocol and analysis for the special case when the dictionary is of the form i.e., the password is a short string chosen uniformly at random (in the spirit of an ATM PIN number). The security bound achieved by our protocol is somewhat worse than the GL protocol. Roughly speaking, our protocol guarantees that the adversary can “break” the scheme with probability at most , whereas the GL protocol guarantees a bound of . We also present an alternative, more natural definition of security than the “augmented definition” of Goldreich and Lindell, and prove that the two definitions are equivalent. An extended abstract of this paper appeared in the First Theory of Cryptography Conference (TCC ’04) [22]. Minh-Huyen Nguyen: Supported by NSF grant CCR-0205423 and ONR grant N00014-04-1-0478. Salil Vadhan: Supported by NSF grant CCR-0205423, a Sloan Research Fellowship, and ONR grant N00014-04-1-0478. Part of this work done while at the Radcliffe Institute for Advanced Study.     

Primality Proving via One Round in ECPP and One Iteration in AKS

In August 2002, Agrawal, Kayal and Saxena announced the first deterministic and polynomial-time primality-testing algorithm. For an input n, the Agarwal-Kayal-Saxena (AKS) algorithm runs in time (heuristic time ). Verification takes roughly the same amount of time. On the other hand, the Elliptic Curve Primality Proving algorithm (ECPP) runs in random heuristic time (some variant has heuristic time complexity ) and generates certificates which can be easily verified. However, it is hard to analyze the provable time complexity of ECPP even for a small portion of primes. More recently, Berrizbeitia gave a variant of the AKS algorithm, in which some primes (of density ) cost much less time to prove than a general prime does. Building on these celebrated results, this paper explores the possibility of designing a randomized primality-proving algorithm based on the AKS algorithm. We first generalize Berrizbeitia's algorithm to one which has higher density ( ) of primes whose primality can be proved in time complexity . For a general prime, one round of ECPP is deployed to reduce its primality proof to the proof of a random easily proved prime, thus we achieve heuristic time complexity for all primes.     

Ab␣Initio Study of Aluminium Impurity and Interstitial-Substitutional Complexes in Ge Using a Hybrid Functional (HSE)

The results of an ab?initio modelling of aluminium substitutional impurity (\({\hbox {Al}}_{\rm Ge}\)), aluminium interstitial in Ge [\({\hbox {I}}_{\rm Al}\) for the tetrahedral (T) and hexagonal (H) configurations] and aluminium interstitial-substitutional pairs in Ge (\({\hbox {I}}_{\rm Al}{\hbox {Al}}_{\rm Ge}\)) are presented. For all calculations, the hybrid functional of Heyd, Scuseria, and Ernzerhof in the framework of density functional theory was used. Defects formation energies, charge state transition levels and minimum energy configurations of the \({\hbox {Al}}_{\rm Ge}\), \({\hbox {I}}_{\rm Al}\) and \({\hbox {I}}_{\rm Al}{\hbox {Al}}_{\rm Ge}\) were obtained for ?2, ?1, 0, \(+\)1 and \(+\)2 charge states. The calculated formation energy shows that for the neutral charge state, the \({\hbox {I}}_{\rm Al}\) is energetically more favourable in the T than the H configuration. The \({\hbox {I}}_{\rm Al}{\hbox {Al}}_{\rm Ge}\) forms with formation energies of ?2.37 eV and ?2.32 eV, when the interstitial atom is at the T and H sites, respectively. The \({\hbox {I}}_{\rm Al}{\hbox {Al}}_{\rm Ge}\) is energetically more favourable when the interstitial atom is at the T site with a binding energy of 0.8 eV. The \({\hbox {I}}_{\rm Al}\) in the T configuration, induced a deep donor (\(+\)2/\(+1\)) level at \(E_{\mathrm {V}}+0.23\) eV and the \({\hbox {Al}}_{\rm Ge}\) induced a single acceptor level (0/?1) at \(E_{\mathrm {V}}+0.14\) eV in the band gap of Ge. The \({\hbox {I}}_{\rm Al}{\hbox {Al}}_{\rm Ge}\) induced double-donor levels are at \(E_{\rm V}+0.06\) and \(E_{\rm V}+0.12\) eV, when the interstitial atom is at the T and H sites, respectively. The \({\hbox {I}}_{\rm Al}\) and \({\hbox {I}}_{\rm Al}{\hbox {Al}}_{\rm Ge}\) exhibit properties of charge state-controlled metastability.     

Direct Digital Frequency Synthesis Based on a Two-Level Table-Lookup Scheme

In this work, a new direct digital frequency synthesizer (DDFS) is proposed, which is based on a new two-level table-lookup (TLTL) scheme combined with Taylor’s expansion. This method only needs a lookup-table size of total bits, one multiplier, one n × 3n/4-bit multiplier and two additional smaller multipliers, to generate both sine and cosine values (where n is the output precision). Compared with several notable DDFS’s, the new design has a smaller lookup-table size and higher SFDR (Spurious Free Dynamic Range) for high-precision output cases, at comparable multiplier and adder complexities. The DDFS is verified by FPGA and EDA tools using Synopsys Design Analyzer and UMC 0.25 μm cell library, assuming 16-bit output precision. The designed 16-bit DDFS has a small gate count of 2,797, and a high SFDR of 110 dBc.

---

     

On the Values of Kloosterman Sums

Given a prime $p$ and a positive integer $n$ , we show that the shifted Kloosterman sums $$sum _{x in BBF _{p^{n}}} psi (x + ax^{p^{n}-2}) = sum _{xin BBF _{p^{n}}^{ast }} psi(x + ax^{-1}) + 1, quad a inBBF _{p^{n}}^{ast }$$ where $psi$ is a nontrivial additive character of a finite field $BBF _{p^{n}}$ of $p^{n}$ elements, do not vanish if $a$ belongs to a small subfield $BBF_{p^{m}} subseteq BBF _{p^{n}}$. This complements recent results of P. Charpin and G. Gong which in turn were motivated by some applications to bent functions.      

The $$\mathbb {}$$-curve Construction for Endomorphism-Accelerated Elliptic Curves

We give a detailed account of the use of \(\mathbb {Q}\)-curve reductions to construct elliptic curves over \(\mathbb {F}_{p^2}\) with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant–Lambert–Vanstone (GLV) and Galbraith–Lin–Scott (GLS) endomorphisms. Like GLS (which is a degenerate case of our construction), we offer the advantage over GLV of selecting from a much wider range of curves and thus finding secure group orders when \(p\) is fixed for efficient implementation. Unlike GLS, we also offer the possibility of constructing twist-secure curves. We construct several one-parameter families of elliptic curves over \(\mathbb {F}_{p^2}\) equipped with efficient endomorphisms for every \(p > 3\), and exhibit examples of twist-secure curves over \(\mathbb {F}_{p^2}\) for the efficient Mersenne prime \(p = 2^{127}-1\).     

Diffusion of Selenium in Liquid-Phase Epitaxy–Grown Hg<Subscript>0.78</Subscript>Cd<Subscript>0.22</Subscript>Te

We present preliminary results on Se diffusion in liquid-phase epitaxy (LPE)–grown HgCdTe epilayers. The LPE Hg_0.78Cd_0.22Te samples were implanted with Se of 2.0 × 10¹⁴/cm² at 100 keV and annealed at 350–450°C in mercury saturated vapor. Secondary ion mass spectrometry (SIMS) profiles were obtained for each sample. From a Gaussian fit, we find that the Se diffusion coefficient D _Se is about 1–2 orders of magnitude smaller than that of arsenic. The as-implanted Se distribution is taken into account in case of small diffusion length in Gaussian fitting. The D _Se was found to satisfy the Arrhenius relationship .     

Multivariable backward-shift-invariant subspaces and observability operators

It is well known that subspaces of the Hardy space over the unit disk which are invariant under the backward shift occur as the image of an observability operator associated with a discrete-time linear system with stable state-dynamics, as well as the functional-model space for a Hilbert space contraction operator. We discuss two multivariable extensions of this structure, where the classical Hardy space is replaced by (1) the Fock space of formal power series in a collection of d noncommuting indeterminates with norm-square-summable vector coefficients, and (2) the reproducing kernel Hilbert space (often now called the Arveson space) over the unit ball in with reproducing kernel ). In the first case, the associated linear system is of noncommutative Fornasini–Marchesini type with evolution along a free semigroup with d generators, while in the second case the linear system is a standard (commutative) Fornasini–Marchesini-type system with evolution along the integer lattice . An abelianization map (or symmetrization of the Fock space) links the first case with the second. The second case has special features depending on whether the operator-tuple defining the state dynamics is commutative or not. The paper focuses on multidimensional state-output linear systems and the associated observability operators; followup papers Ball, Bollotnikov, and Fang (2007a, 2007b) use the results here to extend the analysis to represent observability-operator ranges as reproducing kernel Hilbert spaces with reproducing kernels constructed from the transfer function of a conservative multidimensional (noncommutative or commutative) input-state-output linear system.      

Effect of Thermal Aging on the Microstructure Evolution and Solder Joint Reliability in Hard Disk Drive Under Mechanical Shock

The effect of thermal aging on the microstructure evolution and solder joint reliability in hard disk drive (HDD) under mechanical shock was investigated. Significant coarsening of ${hbox {Ag}}_{3} {hbox {Sn}}$ particles was found in SnAgCu solder, and ${rm AuSn}_{4}$ intermetallic compound (IMC) changed from needle-type to layer-type during aging. For as-soldered SnAgCu solder joints after mechanical shock, the cracks were initiated in ${hbox {AuSn}}_{4}$ at the corner of the solder joints, and mainly propagated along the thin ${hbox {Ni}}_{3} {hbox {Sn}}_{4}$ IMC layer. After aging at 150 $^circ$C for 21 days, the cracks were mainly propagated along the solder, ${hbox {Ni}}_{3} {hbox {Sn}}_{4}$, Au–Sn–Ni–Cu, and Au–Cu–Sn. The significant coarsening of microstructure was found in SnPb solder joints, and only microcracks were found on the surfaces of as-soldered and aged solder joints after mechanical shock.      

Extended Robust \mathcal{H}_{2} and \mathcal{H}_{\infty} Filter Design for Discrete Time-Invariant Linear Systems with Polytopic Uncertainty

This paper is concerned with the problem of robust $\mathcal{H}_{2}$ and $\mathcal{H}_{\infty}$ filter design for discrete-time linear time-invariant systems with polytopic parameter uncertainties. Less conservative robust $\mathcal{H}_{2}$ and $\mathcal{H}_{\infty}$ filter design procedures are proposed in terms of single-parameter minimization problems with linear matrix inequality constraints. To this end, we generalize the filter structures available in the literature to date in such a way that the filter’s next state is built by summing the filter’s states over several samples from the past to the present. For stability of the filtering error system, the homogeneous polynomial parameter-dependent Lyapunov functions are employed. Finally, illustrative examples are given to demonstrate the merits of the proposed methods.