No description available.

Title: The knapsack and its applications Author: Romana Linkeová Department: Department of Algebra Supervisor: doc. Mgr. Pavel Příhoda, Ph.D., Department of Algebra Abstract: This thesis is focused on various aspects of cryptosystems based on NP (non-deterministic polynomial) complete knapsack problem. From the theory of complexity point of view, the less known parts of the proof of knapsack problem NP completeness are shown in detail. From the cryptographical point of view, a demonstration of breaking of the Merkle-Hellman cryptosystem (the basic de- sign of knapsack-type cryptosystems) is provided, showing that poor parameters choice can lead to easy obtaining of the whole private key. Another contribution of this thesis consists in a presented proposal of a new cryptosystem concept based on the matrix 0-1 knapsack problem. This concept was developed in order to prevent known attacks, however, in the thesis we provide a proof analogous to J. C. Lagarias and A. M. Odlyzko, 1985, which shows that an attack based on the LLL algorithm will be successful on the majority of the matrix 0-1 kna- psack problem cryptosystems. Finally, a list of modern cryptosystems based on the knapsack problem is provided and a cryptanalysis thereof is given. Keywords: knapsack problem, NP complete problems, LLL algorithm 1

El hierro es un elemento imprescindible para los seres vivos. En la naturalezase encuentra fundamentalmente en forma de Fe(lll) formando parte de sales ehidróxidos de muy baja solubilidad, lo que lo hace biológicamente inaccesible para losseres vivos mediante mecanismos simples de asimilación. En su forma reducida, elFe(ll) es mucho más soluble, pero también muy inestable, pasando immediatamentea Fe(lll) en presencia de oxígeno. Por otro lado, el hierro puede resultar tóxico para lacélula a concentraciones superiores a las requeridas por ésta, hecho éste que haforzado en la célula el desarrollo de mecanismos de incorporación del hierroaltamente regulados. El primer paso en la asimilación del hierro por S. cerevisiaeimplica la reducción del Fe(lll) extracitoplasmático a Fe(ll), estado en el cual el hierroes captado y transportado al citoplasma celular. En S. cerevisiae se han descrito dossistemas para la entrada de hierro en la célula. El sistema de baja afinidad, pococaracterizado hasta el momento, funciona cuando el hierro extracelular es abundante,siendo FET4 el gen que codifica para el transportador del hierro en estascondiciones, el único elemento genético de este sistema que ha sido caracterizado.Cuando el hierro es deficiente en el medio entra en funcionamiento el sistema de altaafinidad, en el que intervienen dos ferro-reductasas de membrana, productos de losgenes FRE1 y FRE2, que reducen el Fe(lll) extracitoplasmático a Fe(ll), el cual escaptado por una oxidasa de membrana, producto del gen F£T3, que se encarga depasarlo de nuevo a Fe(lll) y transportarlo al citoplasma. Resultados nuestros y deotros autores demuestran que la expresión de estos tres genes depende del productodel gen RCS1 (también denominado AFT1). RCS1 es un gen de S. cerevisiae quehabía sido parcialmente secuenciado con anterioridad; mutantes con una delecciónparcial en el mismo tenían un tamaño celular superior al de la cepa salvaje. En estetrabajo se ha completado la secuencia del gen RCS1 y se han construido mutantesnulos, esto es, portadores de una delección total del gen. Las células carentes deRCS1 no crecen en fuentes de carbono respirables como el etanol/glicerol, lo cualhizo pensar ¡nicialmente que RCS1 tuviese un papel en la desrepresión por glucosa.El análisis de la expresión de genes como ADH2 e ICL1, sometidos a represión porglucosa y necesarios para el crecimiento en este medio, ha revelado que dichaexpresión no está afectada en el muíante. La identidad de RCS1 con el gen AFT1implicado en la asimilación de hierro por otros autores nos llevó a intentar relacionarla incapacidad de los mutantes RCS1 para crecer sobre fuentes de carbonorespirables con su deficiente asimilación de hierro. Así, se ha comprobado que laausencia de crecimiento del muíante en etanol/glicerol como únicas fuentes decarbono puede suprimirse adicionando hierro en exceso al medio. Por otro lado, elcrecimiento en etanol/glicerol no requiere la inducción del sistema de alta afinidad,hecho que permite sugerir un papel adicional para RCS1 al anteriormente descrito,bien como responsable de mantener unos niveles de actividad ferro-reductasa y deentrada de hierro suficientes para el crecimiento en dicho medio, bien comoresponsable de la inducción de nuevos elementos implicados en la entrada de hierroque serían necesarios en esas condiciones, o bien porque sea necesario para unfuncionamiento eficiente del sistema de baja afinidad. La sobreexpresión de RCS1produce una detención homogénea del crecimiento celular en la fase G1 del ciclocelular, efecto no suprimible ni por privación ni por adición de hierro. El uso de lagenética de dominancia para contrarrestar este efecto podrá dar luz acerca de otrosgenes con interacción funcional con RCS1. En este trabajo se demuestra que Rcs1es o forma parte de un factor transcripcional activo sobre el promotor de FRE1. Así, laproteína Rcs1 unida al dominio de unión a DNA de la proteína Gal4 es capaz detransactivar dos sistemas reporteros (GAL1-HIS3 y GAL1-lacZ). En relación con ello,mediante estudios de retardamiento en gel, se ha podido comprobar que Rcs1 esnecesaria, en condiciones deficitarias de hierro, para la estabilidad del complejo quereconoce la zona del promotor de FRE1 responsable de su regulación por hierro. Laobtención de anticuerpos anti-Rcsl para su immunodetección ha permitido hacer unseguimiento de la proteína en diferentes condiciones. Así, se ha podido comprobarque dicha proteína está sujeta a una modificación postraduccional por fosforilación,que se produce en situaciones de detención del crecimiento celular. Estudios concepas portadoras de mutaciones en diferentes elementos de la vía Ras han permitidodescartar una implicación de la proteína quinasa A dependiente de cAMP en lafosforilación de Rcsl Asimismo, se ha visto que ósta es también independiente delas proteína quinasas producto de los genes YAK1 (que codifica para una quinasaantagónica de la proteína quinasa A) o SNF1 (quinasa necesaria para la desrepresiónpor glucosa). La fosforilación de Rcs1 parece corresponderse con una inactivación dela proteína y podría constituir un mecanismo para adaptar la entrada de hierro alestado metabólico de la célula.

Thesis (D. Min.)--Northern Baptist Theological Seminary, 2006. / Abstract. Includes bibliographical references (leaves 163-171).

Thesis (MSc. (Biochemistry)) --University of Limpopo, 2016 / The ever increasing cost of fossil-based fuels and the accompanying concerns about their impact on the environment is driving research towards clean and renewable sources of energy. Bioethanol has the potential to be a replacement for liquid transportation fuels. In addition to its near zero nett carbon dioxide emissions, bio-ethanol has a high energy to weight ratio and can easily be stored in high volumes. To produce bioethanol at economically competitive prices, the major cost in the production process needs to be addressed. The addition of enzymes to hydrolyse the lignocellulosic fraction of the agricultural waste to simple sugars is considered to be the major contributor to high production cost. A consolidated bioprocess (CBP) which ideally combines all the steps that are currently accomplished in different reactors by different microorganisms into a single process step would be a more economically feasible solution. In this study the potential of yeast hybridization with a CBP approach was used. In order to evaluate the reduction or elimination of the addition of cellulolytic and hemi-cellulolytic enzymes to the ethanol production process. High cellobiohydrolase I secreting progeny from hybridization of an industrial bioethanol yeast strain, S. cerevisiae M0341, and a laboratory strain S. cerevisiae Y294 were isolated. In order to determine if this characteristic was specific to cellobiohydrolase I secretion, these strains were evaluated for their ability to secrete other relevant recombinant hydrolase enzymes for CBP-based ethanol production. A total of seven S. cerevisiae strains were chosen from a progeny pool of 28 supersecreting hybrids and reconstructed to create two parental strains; S. cerevisiae M0341 and S. cerevisiae Y294, together with their hybrid segregants strains H3M1, H3M28, H3H29, H3K27 and H3O23. Three episomal plasmids namely pNS201, pNS202 and pNS203 were constructed; these plasmids together with two already available plasmids, namely pRDH166 and pRDH182 contained genes for different reporter enzymes, namely β-glucosidase I, xylanase II, endoglucanase lll, cellobiohydrolase l and α-glucuronidase. To allow for selection of the episomal plasmids, homologous recombination was used to replace the functional URA3 gene of selected strains, with the non-functional ura3 allele from the Y294 strain. Enzyme activity was used as an indicator of the amount of enzyme secreted. Fermentation studies in a bioreactor were used to determine the metabolic burden imposed on the segregants expressing the cellobiohydrolase at high levels. In addition all segregants were tested for resistance to inhibitors commonly found in pre-treated lignocellulosic material. The M28_Cel7A was found to be the best secretor of Cel7A (Cellobiohydrolase l); however it seems as though this phenomenon imposes a significant metabolic burden on the yeast. The supersecreting hybrid strains cannot tolerate lignocellulosic inhibitors at concentrations commonly produced during pretreatment / The National Research Foundation - Renewable Energy Scholarship (NRF-RSES)

<p> Solving the integer least squares problem min ||Hs- x|| 2 , where the unknown vector s is comprised of integers, the coefficient matrix H and given vector x are comprised of real numbers arises in many applications and is equivalent to find the closest lattice point to a given one known as NP-hard. In multiple antenna systems, the received signal represented by vector xis not arbitrary, but an lattice point perturbed by an additive noise vector whose statistical properties are known. It has been shown the Sphere Decoding, in which the lattice points inside a hyper-sphere are generated and the closest lattice point to the received signal is determined, together with Maximum Likelihood (ML) method often yields a near-optimal performance on average (cubic) while the worst case complexity is still exponential. By using lattice basis reduction as pre-processing step in the sub-optimum decoding algorithms, we can show that the lattice reduction aided sphere decoding (LRSD) achieves a better performance than the maximum likelihood sphere decoding (MLSD) in terms of symbol error rate (SER) and average algorithm running time. In the FIR (Finite Impulse Response) MIMO channel, the channel matrix is Toeplitz and thus gives us the leverage to use the fact that all its column vectors all linearly independent and the matrix itself is often well-conditioned. </p> <p> In this thesis, we will develop a lattice reduction added sphere decoding algorithm along with an improved LLL algorithm, and provide the simulations to show that this new algorithm achieves a better performance than the maximum likelihood sphere decoding. </p> <p> In chapter 1, we define our system model and establish the foundations for understanding of mathematical model - namly the integer least squares problem, and thus the choice of the simulation data. In chapter 2, we explain the integer least squares problems and exploit serveral ways for solving the problems, then we introduce the sphere decoding and maximum likelihood at the end. In chapter 3, we explore the famous LLL reduction algorithm named after Lenstra, Lenstra and Lovasz in details and show an example how to break Merkle-Hellman code using the LLL reduction algorithm. Finally, in chapter 4 we give the LLL reduction aided sphere decoding algorithm and the experiment setup as well as the simulation results against the MLSD and conclusions, further research directions. </p> / Thesis / Master of Science (MSc)

Lattice reduction aided techniques have been successfully applied to a wide range of applications. Efficient and robust lattice basis reduction algorithms are valuable. In this thesis, we present an O(n^4 logB) hybrid Jacobi method for lattice basis reduction, where n is the dimension of the lattice and B is the maximum length of the input lattice basis vectors. Building upon a generic Jacobi method for lattice basis reduction, we integrate the size reduction into the algorithm to improve its performance. To ensure the convergence and the efficiency of the algorithm, we introduce a parameter to the Lagrange reduction. To improve the quality of the computed bases, we impose a condition on the size reduction, delay the structure restoration, and include a postprocessing in the hybrid method. Our experiments on random matrices show that the proposed algorithm produces better reduced bases than the well-known LLL algorithm and BKZ 2.0 algorithm, measured by both the orthogonality defect and the condition number of the basis matrix. Moreover, our hybrid method consistently runs faster than the LLL algorithm, although they have the same theoretical complexity. We have also investigated two potential applications of the hybrid method. The application simulations show that the hybrid method can improve the stability of the communication channels for Multi-Input Multi-Output systems, and can partially discover the plain text when attacking the GGH cryptosystem. / Thesis / Doctor of Philosophy (PhD) / Lattice reduction aided techniques have been successfully applied to a wide range of applications. Efficient and robust lattice basis reduction algorithms are valuable. In this thesis, we present an O(n^4 logB) hybrid Jacobi method for lattice basis reduction, where n is the dimension of the lattice and B is the maximum length of the input lattice basis vectors. Our experiments on random matrices show that the proposed algorithm produces better reduced bases than the well-known LLL algorithm and BKZ 2.0 algorithm, measured by both the orthogonality defect and the condition number of the basis matrix. We have also investigated two potential applications in MIMO systems and cryptosystems.

De nombreuses méthodes de traitement du signal reposent sur des résultats puissants d'approximation numérique. Un exemple significatif en est l'utilisation de l'approximation de type Chebyshev pour l'élaboration de filtres numériques.En pratique, le caractère fini des formats numériques utilisés en machine entraîne des difficultés supplémentaires pour la conception de filtres numériques (le traitement audio et le traitement d'images sont deux domaines qui utilisent beaucoup le filtrage). La majorité des outils actuels de conception de filtres ne sont pas optimisés et ne certifient pas non plus la correction de leurs résultats. Notre travail se veut un premier pas vers un changement de cette situation.La première partie de la thèse traite de l'étude et du développement de méthodes relevant de la famille Remez/Parks-McClellan pour la résolution de problèmes d'approximation polynomiale de type Chebyshev, en utilisant l'arithmétique virgule-flottante.Ces approches sont très robustes, tant du point de vue du passage à l'échelle que de la qualité numérique, pour l'élaboration de filtres à réponse impulsionnelle finie (RIF).Cela dit, dans le cas des systèmes embarqués par exemple, le format des coefficients du filtre qu'on utilise en pratique est beaucoup plus petit que les formats virgule flottante standard et d'autres approches deviennent nécessaires.Nous proposons une méthode (quasi-)optimale pour traîter ce cas. Elle s'appuie sur l'algorithme LLL et permet de traiter des problèmes de taille bien supérieure à ceux que peuvent traiter les approches exactes. Le résultat est ensuite utilisé dans une couche logicielle qui permet la synthèse de filtres RIF pour des circuits de type FPGA.Les résultats que nous obtenons en sortie sont efficaces en termes de consommation d'énergie et précis. Nous terminons en présentant une étude en cours sur les algorithmes de type Remez pour l'approximation rationnelle. Ce type d'approches peut être utilisé pour construire des filtres à réponse impulsionnelle infinie (RII) par exemple. Nous examinons les difficultés qui limitent leur utilisation en pratique. / The field of signal processing methods and applications frequentlyrelies on powerful results from numerical approximation. One suchexample, at the core of this thesis, is the use of Chebyshev approximationmethods for designing digital filters.In practice, the finite nature of numerical representations adds an extralayer of difficulty to the design problems we wish to address using digitalfilters (audio and image processing being two domains which rely heavilyon filtering operations). Most of the current mainstream tools for thisjob are neither optimized, nor do they provide certificates of correctness.We wish to change this, with some of the groundwork being laid by thepresent work.The first part of the thesis deals with the study and development ofRemez/Parks-McClellan-type methods for solving weighted polynomialapproximation problems in floating-point arithmetic. They are veryscalable and numerically accurate in addressing finite impulse response(FIR) design problems. However, in embedded and power hungry settings,the format of the filter coefficients uses a small number of bits andother methods are needed. We propose a (quasi-)optimal approach basedon the LLL algorithm which is more tractable than exact approaches.We then proceed to integrate these aforementioned tools in a softwarestack for FIR filter synthesis on FPGA targets. The results obtainedare both resource consumption efficient and possess guaranteed accuracyproperties. In the end, we present an ongoing study on Remez-type algorithmsfor rational approximation problems (which can be used for infinite impulseresponse (IIR) filter design) and the difficulties hindering their robustness.

Submitted by Ana Paula Macedo (ensino@ioc.fiocruz.br) on 2013-10-03T12:26:40Z No. of bitstreams: 1 Carolina Valença Messias.pdf: 1326403 bytes, checksum: adde2666bf9c1e45634b4ea4926b6090 (MD5) / Made available in DSpace on 2013-10-03T12:26:40Z (GMT). No. of bitstreams: 1 Carolina Valença Messias.pdf: 1326403 bytes, checksum: adde2666bf9c1e45634b4ea4926b6090 (MD5) Previous issue date: 2012 / Fundação Oswaldo Cruz. Instituto Oswaldo Cruz. Rio de Janeiro, RJ, Brasil / A leucemia linfoblástica aguda de células T (LLA-T) e o linfoma linfoblástico de células T (LL-T) são proliferações malignas de precursores de células T em diferentes estágios de maturação. LLA-T e LL-T são considerados atualmente duas formas de uma mesma doença, a leucemia/linfoma linfoblástico de células T (LLL-T), por compartilharem características morfológicas, imunofenotípicas e genéticas. Como os blastos de LLL-T apresentam características similares às de timócitos normais, moléculas envolvidas na migração destas células podem também estar envolvidas na migração ou homing dos linfoblastos no curso da doença. Neste sentido, foi demonstrado recentemente que o receptor 1 de esfingosina-1-fosfato (S1P1) é essencial para a saída de timócitos do timo. No presente estudo, decidimos avaliar a expressão e o papel do S1P1 na migração de quatro linhagens celulares de LLA-T (HPB-ALL, MOLT-4, CEM e JURKAT) em resposta ao seu ligante fisiológico, a esfingosina-1-fosfato (S1P). Observamos que a linhagem HPB-ALL apresentou baixa expressão de RNAm de S1P1, enquanto MOLT-4 e JURKAT apresentaram uma expressão mediana e CEM apresentou altos níveis de expressão de RNAm para este receptor. Em ensaios funcionais de migração celular observamos que a capacidade migratória das linhagens frente a S1P foi diretamente relacionada ao nível de expressão gênica do receptor. A S1P induziu a migração das linhagens analisadas em diferentes concentrações até 100 nM, e inibiu a migração quando aplicada em altas concentrações (1000 nM). As respostas migratórias foram acompanhadas pela modulação do citoesqueleto de actina. Dependendo da concentração de S1P utilizada, observamos polimerização (menores concentrações) ou despolimerização (maiores concentrações) da actina. Além disso, o prétratamento das células com W146 (inibidor de S1P1) bloqueou a migração das linhagens frente à S1P em menores concentrações e induziu a migração frente à S1P em altas concentrações, sugerindo que a migração seja especificamente mediada por S1P1. Nossos resultados sugerem que as interações mediadas por S1P/S1P1 modulam a migração não apenas de precursores de células T normais, mas também de linfoblastos de LLL-T. Desta forma, a interação S1P/S1P1 pode ser considerada como alvo para possíveis estratégias terapêuticas frente a estas neoplasias. / T-cell acute lymphoblastic leukemia (T-ALL) and T-cell lymphoblastic lymphoma (TLBL) are malignant proliferations of T cell precursors at different stages of normal development. T-ALL and T-LBL are presently believed to represent two different forms of a single disease, the T-cell lymphoblastic leukemia/lymphoma (T-LLL), as they share morphological, immunophenotypic and genetic features. As T-LLL lymphoblasts present similar characteristics of normal T cell precursors, molecules involved on the migration of these cells might also be associated with migration and homing of T-ALL/LBL. In this context, the sphingosine-1-phosfate receptor 1 (S1P1), has been described as essential for mouse thymocyte migration and thymic egress. Herein, we evaluated the expression and role of S1P1 in four T-ALL cell lines (HPBALL, MOLT-4, CEM e JURKAT) in response to its physiological ligand, the sphingosine-1-phophate (S1P). We observed that HPB-ALL cells presented low expression levels of S1P1 mRNA, whereas MOLT-4 and JURKAT had medium levels and CEM showed high levels of S1P1 expression. In functional migration assays, we observed that the migratory response of the cells towards S1P was directly related with their expression levels of the receptor. S1P induced the migration of the cell lines analyzed in different concentrations up to 100 nM and inhibited cell migration at higher concentrations (1000 nM). Moreover, migratory responses were accompanied by the modulation of actin cytoskeleton. Depending on S1P concentrations, we observed actin polymerization (lower concentrations) or depolymerization (higher concentrations). Pre-treatment of the cells with W146 (a S1P1 inhibitor) blocked S1Pinduced migration at lower concentrations but induced migration towards S1P at high concentrations, suggesting that the migration is specifically mediated by S1P1. Our results suggest that interactions mediated by S1P/S1P1 can modulate cell migration of T-LLL blasts similarly to their normal T cell precursor counterparts. Accordingly, immune intervention upon this ligand/receptor interaction may be envisioned as a potential therapeutic strategy for these malignancies.

Le 10ème problème de Hilbert, consistant à trouver les solutions entières d'équations polynomiales est un problème crucial en cryptanalyse. Si ce dernier a été prouvé indécidable, Coppersmith publia en 1996 une méthode basée sur la réduction de réseaux permettant de trouver efficacement l'ensemble des petites solutions de certaines équations polynomiales. De nombreuses applications de cette méthode ont vu le jour dans le domaine de la cryptanalyse à clé publique, notamment lorsque le cryptosystème est exécuté sur un système embarqué et qu'une partie de la clé secrète est dévoilée par la réalisation d'attaques physiques sur le dispositif. Dans ce contexte, nous proposons une attaque physique sur le schéma de signature RSA en mode CRT où une application de la méthode de Coppersmith permet de compléter l'information obtenue par l'attaque physique. Nous proposons également un nouvel algorithme déterministe basé sur la méthode de Coppersmith pour factoriser les entiers de la forme $N=p^rq^s$ en temps polynomial lorsque $r$ ou $s$ sont suffisamment grands. Enfin, si les applications de la méthode de Coppersmith sont nombreuses, en pratique, du fait que les réseaux à réduire soient gigantesques, les petites solutions ne peuvent être retrouvées que jusqu'à une borne qui est plus petite que la borne théorique annoncée. Aussi, une autre contribution de cette thèse consiste en la proposition de deux méthodes permettant une accélération du temps d'exécution de l'algorithme de Coppersmith. Lorsque les deux méthodes sont combinées, le nouvel algorithme s'effectue des centaines de fois plus rapidement pour des paramètres typiques, permettant ainsi dans de nombreux cas d'atteindre la borne théorique. / The 10th Hilbert problem, which consists in finding integer solutions to polynomial equations is a crucial problem in cryptanalysis, which has been proven to be undecidable. However, Coppersmith published in 1996 a method based on lattice reduction, which allows to efficiently find all small solutions to some polynomial equations. Many applications of this method have risen in public key cryptanalysis, especially when the cryptosystem is executed on embedded systems and part of the secret key is revealed through physical attacks performed on the device. In this context, we propose in this thesis a physical attack on the RSA signature scheme when the CRT mode is used, where an application of Coppersmith's method allows to complete the information previously obtained by the physical attack. We also propose a new deterministic algorithm based on Coppersmith's method for factoring integers of the form $N=p^rq^s$ in polynomial time, under the condition that $r$ and/or $s$ are sufficiently large.Finally, if the applications of Coppersmith's method are numerous, in practice, since the lattices to be reduced are huge, the small solutions can only be recovered until a bound which is smaller than the enounced theoretical bound. Thus, another contribution of this thesis lies in the proposition of two methods which allow to speed up the execution time of Coppersmith's algorithm. When both speedups are combined, the new algorithm performs hundreds of times faster for typical parameters, which allows to reach the theoretical bound in many cases.