Higher order universal one-way hash functions from the subset sum assumption

Universal One-Way Hash Functions (UOWHFs) may be used in place of collision-resistant functions in many public-key cryptographic applications. At Asiacrypt 2004, Hong, Preneel and Lee introduced the stronger security notion of higher order UOWHFs to allow construction of long-input UOWHFs using the Merkle-Damgård domain extender. However, they did not provide any provably secure constructions for higher order UOWHFs. We show that the subset sum hash function is a kth order Universal One-Way Hash Function (hashing n bits to m < n bits) under the Subset Sum assumption for k = O(log m). Therefore we strengthen a previous result of Impagliazzo and Naor, who showed that the subset sum hash function is a UOWHF under the Subset Sum assumption. We believe our result is of theoretical interest; as far as we are aware, it is the first example of a natural and computationally efficient UOWHF which is also a provably secure higher order UOWHF under the same well-known cryptographic assumption, whereas this assumption does not seem sufficient to prove its collision-resistance. A consequence of our result is that one can apply the Merkle-Damgård extender to the subset sum compression function with ‘extension factor’ k+1, while losing (at most) about k bits of UOWHF security relative to the UOWHF security of the compression function. The method also leads to a saving of up to m log(k+1) bits in key length relative to the Shoup XOR-Mask domain extender applied to the subset sum compression function.

Homogeneous bent functions of degree n in 2n variables do not exist for n>3

We prove that homogeneous bent functions f:GF(2)^2n --> GF(2) of degree n do not exist for n>3. Consequently homogeneous bent functions must have degree 3.

The eight variable homogeneous degree three bent functions

We determine the affine equivalence classes of the eight variable degree three homogeneous bent functions using a new algorithm. Our algorithm applies to general bent functions and can systematically determine the automorphism groups. We provide a partial verification of the enumeration of eight variable degree three homogeneous bent functions obtained by Meng et al. We determine the affine equivalence classes of these functions.

Demonstration of nonlinear absorption in Au semi-continuous film by electrical measurement

We have demonstrated the nonlinear absorption at 532 nm wavelength in an Au semi-continuous film (SF) resulting from smearing of the Fermi distribution and diffusion of conduction electrons into the substrate. The Au SF was irradiated by a pulsed laser with 8 ns pulse width at 532 nm in near resonance with the interband transition of the Au. We determined the temperature increase in the SF for different intensities by electrical measurement. We calculated the temperature increase by using a 1D heat transport equation; comparing the results of the calculation with measured values for the temperature increase, revealed the nonlinear absorption in the Au SF. We employed this deviation from linear behaviour to determine the nonlinear absorption coefficient.

Shared generation of pseudo-random functions

In Crypto’95, Micali and Sidney proposed a method for shared generation of a pseudo-random function f(·) among n players in such a way that for all the inputs x, any u players can compute f(x) while t or fewer players fail to do so, where 0⩽tfunctions, among the n players, each player gets a subset of S, in such a way that any u players together hold all the secret seeds in S while any t or fewer players will lack at least one element from S. The pseudo-random function is then computed as where fsi(·)'s are poly-random functions. One question raised by Micali and Sidney is how to distribute the secret seeds satisfying the above condition such that the number of seeds, d, is as small as possible. In this paper, we continue the work of Micali and Sidney. We first provide a general framework for shared generation of pseudo-random function using cumulative maps. We demonstrate that the Micali–Sidney scheme is a special case of this general construction. We then derive an upper and a lower bound for d. Finally we give a simple, yet efficient, approximation greedy algorithm for generating the secret seeds S in which d is close to the optimum by a factor of at most u ln 2.

Shared generation of pseudo-random functions with cumulative maps

In Crypto’95, Micali and Sidney proposed a method for shared generation of a pseudo-random function f(·) among n players in such a way that for all the inputs x, any u players can compute f(x) while t or fewer players fail to do so, where 0 ≤ t < u ≤ n. The idea behind the Micali-Sidney scheme is to generate and distribute secret seeds S = s1, . . . , sd of a poly-random collection of functions, among the n players, each player gets a subset of S, in such a way that any u players together hold all the secret seeds in S while any t or fewer players will lack at least one element from S. The pseudo-random function is then computed as where f s i (·)’s are poly-random functions. One question raised by Micali and Sidney is how to distribute the secret seeds satisfying the above condition such that the number of seeds, d, is as small as possible. In this paper, we continue the work of Micali and Sidney. We first provide a general framework for shared generation of pseudo-random function using cumulative maps. We demonstrate that the Micali-Sidney scheme is a special case of this general construction.We then derive an upper and a lower bound for d. Finally we give a simple, yet efficient, approximation greedy algorithm for generating the secret seeds S in which d is close to the optimum by a factor of at most u ln 2.

The Saccharomyces cerevisiae RNA-binding protein Rbp29 functions in cytoplasmic mRNA metabolism

Here we report that the Saccharomyces cerevisiae RBP29 (SGN1, YIR001C) gene encodes a 29-kDa cytoplasmic protein that binds to mRNA in vivo. Rbp29p can be co-immunoprecipitated with the poly(A) tail-binding protein Pab1p from crude yeast extracts in a dosageand RNA-dependent manner. In addition, recombinant Rbp29p binds preferentially to poly(A) with nanomolar binding affinity in vitro. Although RBP29 is not essential for cell viability, its deletion exacerbates the slow growth phenotype of yeast strains harboring mutations in the eIF4G genes TIF4631 and TIF4632. Furthermore, overexpression of RBP29 suppresses the temperaturesensitive growth phenotype of specific tif4631, tif4632, and pab1 alleles. These data suggest that Rbp29p is an mRNA-binding protein that plays a role in modulating the expression of cytoplasmic mRNA.

Independent functions of yeast Pcf11p in pre-mRNA 3' end processing and in transcription termination

Pcf11p, an essential subunit of the yeast cleavage factor IA, is required for pre‐mRNA 3′ end processing, binds to the C‐terminal domain (CTD) of the largest subunit of RNA polymerase II (RNAP II) and is involved in transcription termination. We show that the conserved CTD interaction domain (CID) of Pcf11p is essential for cell viability. Interestingly, the CTD binding and 3′ end processing activities of Pcf11p can be functionally uncoupled from each other and provided by distinct Pcf11p fragments in trans. Impaired CTD binding did not affect the 3′ end processing activity of Pcf11p and a deficiency of Pcf11p in 3′ end processing did not prevent CTD binding. Transcriptional run‐on analysis with the CYC1 gene revealed that loss of cleavage activity did not correlate with a defect in transcription termination, whereas loss of CTD binding did. We conclude that Pcf11p is a bifunctional protein and that transcript cleavage is not an obligatory step prior to RNAP II termination.

Three-dimensional analysis of budding sites and released virus suggests a revised model for HIV-1 morphogenesis

Current models of HIV-1 morphogenesis hold that newly synthesized viral Gag polyproteins traffic to and assemble at the cell membrane into spherical protein shells. The resulting late-budding structure is thought to be released by the cellular ESCRT machinery severing the membrane tether connecting it to the producer cell. Using electron tomography and scanning transmission electron microscopy, we find that virions have a morphology and composition distinct from late-budding sites. Gag is arranged as a continuous but incomplete sphere in the released virion. In contrast, late-budding sites lacking functional ESCRT exhibited a nearly closed Gag sphere. The results lead us to propose that budding is initiated by Gag assembly, but is completed in an ESCRT-dependent manner before the Gag sphere is complete. This suggests that ESCRT functions early in HIV-1 release-akin to its role in vesicle formation-and is not restricted to severing the thin membrane tether.

Computational strategies for surface fitting using thin plate spline finite element methods

Thin plate spline finite element methods are used to fit a surface to an irregularly scattered dataset [S. Roberts, M. Hegland, and I. Altas. Approximation of a Thin Plate Spline Smoother using Continuous Piecewise Polynomial Functions. SIAM, 1:208--234, 2003]. The computational bottleneck for this algorithm is the solution of large, ill-conditioned systems of linear equations at each step of a generalised cross validation algorithm. Preconditioning techniques are investigated to accelerate the convergence of the solution of these systems using Krylov subspace methods. The preconditioners under consideration are block diagonal, block triangular and constraint preconditioners [M. Benzi, G. H. Golub, and J. Liesen. Numerical solution of saddle point problems. Acta Numer., 14:1--137, 2005]. The effectiveness of each of these preconditioners is examined on a sample dataset taken from a known surface. From our numerical investigation, constraint preconditioners appear to provide improved convergence for this surface fitting problem compared to block preconditioners.

A comparison of techniques for the reconstruction of leaf surfaces from scanned data

The foliage of a plant performs vital functions. As such, leaf models are required to be developed for modelling the plant architecture from a set of scattered data captured using a scanning device. The leaf model can be used for purely visual purposes or as part of a further model, such as a fluid movement model or biological process. For these reasons, an accurate mathematical representation of the surface and boundary is required. This paper compares three approaches for fitting a continuously differentiable surface through a set of scanned data points from a leaf surface, with a technique already used for reconstructing leaf surfaces. The techniques which will be considered are discrete smoothing D2-splines [R. Arcangeli, M. C. Lopez de Silanes, and J. J. Torrens, Multidimensional Minimising Splines, Springer, 2004.], the thin plate spline finite element smoother [S. Roberts, M. Hegland, and I. Altas, Approximation of a Thin Plate Spline Smoother using Continuous Piecewise Polynomial Functions, SIAM, 1 (2003), pp. 208--234] and the radial basis function Clough-Tocher method [M. Oqielat, I. Turner, and J. Belward, A hybrid Clough-Tocher method for surface fitting with application to leaf data., Appl. Math. Modelling, 33 (2009), pp. 2582-2595]. Numerical results show that discrete smoothing D2-splines produce reconstructed leaf surfaces which better represent the original physical leaf.

Role of the N-terminal region in G protein-coupled receptor functions : negative modulation revealed by 5-HT2B receptor polymorphisms

The putative role of the N-terminal region of rhodopsin-like 7 transmembrane biogenic amine receptors in agonist-induced signaling has not yet been clarified despite recent advances in 7 transmembrane receptor structural biology. Given the existence of N-terminal nonsynonymous polymorphisms (R6G;E42G) within the HTR2B gene in a drug-abusing population, we assessed whether these polymorphisms affect 5-hydroxytryptamine 2B (5-HT2B) receptor in vitro pharmacologic and coupling properties in transfected COS-7 cells. Modification of the 5-HT2B receptor N terminus by the R6G;E42G polymorphisms increases such agonist signaling pathways as inositol phosphate accumulation as assessed by either classic or operational models. The N-terminal R6G;E42G mutations of the 5-HT2B receptor also increase cell proliferation and slow its desensitization kinetics compared with the wild-type receptor, further supporting a role for the N terminus in transduction efficacy. Furthermore, by coexpressing a tethered wild-type 5-HT2B receptor N terminus with a 5-HT2B receptor bearing a N-terminal deletion, we were able to restore original coupling. This reversion to normal activity of a truncated 5-HT2B receptor by coexpression of the membrane-tethered wild-type 5-HT2B receptor N terminus was not observed using a membrane-tethered 5-HT2B receptor R6G;E42G N terminus. These data suggest that the N terminus exerts a negative control over basal as well as agonist-stimulated receptor activity that is lost in the R6G;E42G mutant. Our findings reveal a new and unanticipated role of the 5-HT2B receptor N terminus as a negative modulator, affecting both constitutive and agonist-stimulated activity. Moreover, our data caution against excluding the N terminus and extracellular loops in structural studies of this 7 transmembrane receptor family

Representation of facial expression categories in continuous arousal-valence space: Feature and correlation

Representation of facial expressions using continuous dimensions has shown to be inherently more expressive and psychologically meaningful than using categorized emotions, and thus has gained increasing attention over recent years. Many sub-problems have arisen in this new field that remain only partially understood. A comparison of the regression performance of different texture and geometric features and investigation of the correlations between continuous dimensional axes and basic categorized emotions are two of these. This paper presents empirical studies addressing these problems, and it reports results from an evaluation of different methods for detecting spontaneous facial expressions within the arousal-valence dimensional space (AV). The evaluation compares the performance of texture features (SIFT, Gabor, LBP) against geometric features (FAP-based distances), and the fusion of the two. It also compares the prediction of arousal and valence, obtained using the best fusion method, to the corresponding ground truths. Spatial distribution, shift, similarity, and correlation are considered for the six basic categorized emotions (i.e. anger, disgust, fear, happiness, sadness, surprise). Using the NVIE database, results show that the fusion of LBP and FAP features performs the best. The results from the NVIE and FEEDTUM databases reveal novel findings about the correlations of arousal and valence dimensions to each of six basic emotion categories.