Practical Lattice-Based Digital Signature Schemes

Digital signatures are an important primitive for building secure systems and are used in most real-world security protocols. However, almost all popular signature schemes are either based on the factoring assumption (RSA) or the hardness of the discrete logarithm problem (DSA/ECDSA). In the case of classical cryptanalytic advances or progress on the development of quantum computers, the hardness of these closely related problems might be seriously weakened. A potential alternative approach is the construction of signature schemes based on the hardness of certain lattice problems that are assumed to be intractable by quantum computers. Due to significant research advancements in recent years, lattice-based schemes have now become practical and appear to be a very viable alternative to number-theoretic cryptography. In this article, we focus on recent developments and the current state of the art in lattice-based digital signatures and provide a comprehensive survey discussing signature schemes with respect to practicality. Additionally, we discuss future research areas that are essential for the continued development of lattice-based cryptography.

« Resolution Search » et problèmes d’optimisation discrète

Thèse réalisée en cotutelle avec l'Université d'Avignon.

Computations in Relative Algebraic K-Groups

Let G be finite group and K a number field or a p-adic field with ring of integers O_K. In the first part of the manuscript we present an algorithm that computes the relative algebraic K-group K_0(O_K[G],K) as an abstract abelian group. We solve the discrete logarithm problem, both in K_0(O_K[G],K) and the locally free class group cl(O_K[G]). All algorithms have been implemented in MAGMA for the case K = \IQ. In the second part of the manuscript we prove formulae for the torsion subgroup of K_0(\IZ[G],\IQ) for large classes of dihedral and quaternion groups.

A concrete certificateless signature scheme without pairings

Certificateless public key cryptography was introduced to avoid the inherent key escrow problem in identity-based cryptography, and eliminate the use of certificates in traditional PKI. Most cryptographic schemes in certificateless cryptography are built from bilinear mappings on elliptic curves which need costly operations. Despite the investigation of certificateless public key encryption without pairings, certificateless signature without pairings received much less attention than what it deserves. In this paper, we present a concrete pairing-free certificateless signature scheme for the first time. Our scheme is more computationally efficient than others built from pairings. The new scheme is provably secure in the random oracle model assuming the hardness of discrete logarithm problem.

Características das Curvas de Regressão da Gonadotrofina Coriônica Pós-mola Hidatiforme Completa

Objetivos: construir a curva de regressão do b-hCG pós-mola hidatiforme completa (MHC) com remissão espontânea e comparar com a curva de regressão pós-MHC com tumor trofoblástico gestacional (TTG). Análise comparativa da curva de regressão do b-hCG das portadoras de MHC, acompanhadas no Serviço, com a curva de regressão observada por outros autores1-3. Métodos: foi realizada avaliação clínica e laboratorial (dosagem sérica de b-hCG), na admissão e no segmento pós-molar, de todas as pacientes com MHC, atendidas entre 1990 e 1998 no Hospital das Clínicas de Botucatu - Unesp. O resultado da determinação seriada do b-hCG foi analisado em curvas log de regressão. A evolução da curva de regressão do b-hCG foi analisada e comparada em MHC com remissão espontânea e MHC com TTG numa curva log de regressão, com intervalo de confiança de 95%. A curva log de regressão do grupo de remissão espontânea foi comparada com curvas consideradas padrão1,2. Foram construídas curvas log individuais de todas as pacientes e classificadas de acordo com os quatro tipos de curva (I, II, III e IV), propostos para o seguimento pós-molar³. Resultados: 61 pacientes com MHC tiveram seguimento pós-molar completo, 50 (82%) apresentaram remissão espontânea e 11 (18%) desenvolveram TTG. No grupo de pacientes com MHC e remissão espontânea, o tempo para alcançar a normalização dos níveis do b-hCG, após o esvaziamento molar, foi até 20 semanas. As pacientes que desenvolveram TTG apresentaram desvio precoce da curva de regressão normal do b-hCG, 4 a 6 semanas após o esvaziamento molar. Nestas pacientes, a quimioterapia foi introduzida em média na 9ª semana pós-esvaziamento molar. Conclusões: a curva de regressão do b-hCG pós-MHC com remissão espontânea apresentou declínio log exponencial, semelhante ao observado por outros autores1,2, e diferente das MHC com TTG. Foram identificados três tipos de curvas de regressão do b-hCG, semelhantes aos de Goldstein³, I, II e IV, e outros dois tipos diferentes de regressão do b-hCG: V (regressão normal) e VI (regressão anormal).

Stochastic scheduling - A flow shop no wait application and solutions

Minimizing the makespan of a flow-shop no-wait (FSNW) schedule where the processing times are randomly distributed is an important NP-Complete Combinatorial Optimization Problem. In spite of this, it can be found only in very few papers in the literature. By considering the Start Interval Concept, this problem can be formulated, in a practical way, in function of the probability of the success in preserve FSNW constraints for all tasks execution. With this formulation, for the particular case with 3 machines, this paper presents different heuristics solutions: by integrating local optimization steps with insertion procedures and by using genetic algorithms for search the solution space. Computational results and performance evaluations are commented. Copyright (C) 1998 IFAC.

Criptografia e curvas elípticas

Pós-graduação em Matemática Universitária - IGCE

Incerteza intervalar em otimização e controle

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

The Performance of Elliptic Curve Based Group Diffie-Hellman Protocols for Secure Group Communication over Ad Hoc Networks

The security of the two party Diffie-Hellman key exchange protocol is currently based on the discrete logarithm problem (DLP). However, it can also be built upon the elliptic curve discrete logarithm problem (ECDLP). Most proposed secure group communication schemes employ the DLP-based Diffie-Hellman protocol. This paper proposes the ECDLP-based Diffie-Hellman protocols for secure group communication and evaluates their performance on wireless ad hoc networks. The proposed schemes are compared at the same security level with DLP-based group protocols under different channel conditions. Our experiments and analysis show that the Tree-based Group Elliptic Curve Diffie-Hellman (TGECDH) protocol is the best in overall performance for secure group communication among the four schemes discussed in the paper. Low communication overhead, relatively low computation load and short packets are the main reasons for the good performance of the TGECDH protocol.

MATHEMATICAL MODELS AND POLYHEDRAL STUDIES FOR INTEGRAL SHEET METAL DESIGN

We deal with the optimization of the production of branched sheet metal products. New forming techniques for sheet metal give rise to a wide variety of possible profiles and possible ways of production. In particular, we show how the problem of producing a given profile geometry can be modeled as a discrete optimization problem. We provide a theoretical analysis of the model in order to improve its solution time. In this context we give the complete convex hull description of some substructures of the underlying polyhedron. Moreover, we introduce a new class of facet-defining inequalities that represent connectivity constraints for the profile and show how these inequalities can be separated in polynomial time. Finally, we present numerical results for various test instances, both real-world and academic examples.

Formulations and Algorithms for Routing Problems

Combinatorial Optimization is a branch of optimization that deals with the problems where the set of feasible solutions is discrete. Routing problem is a well studied branch of Combinatorial Optimization that concerns the process of deciding the best way of visiting the nodes (customers) in a network. Routing problems appear in many real world applications including: Transportation, Telephone or Electronic data Networks. During the years, many solution procedures have been introduced for the solution of different Routing problems. Some of them are based on exact approaches to solve the problems to optimality and some others are based on heuristic or metaheuristic search to find optimal or near optimal solutions. There is also a less studied method, which combines both heuristic and exact approaches to face different problems including those in the Combinatorial Optimization area. The aim of this dissertation is to develop some solution procedures based on the combination of heuristic and Integer Linear Programming (ILP) techniques for some important problems in Routing Optimization. In this approach, given an initial feasible solution to be possibly improved, the method follows a destruct-and-repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in an attempt to find a new improved solution.

A public key cryptosystem based on block upper triangular matrices

We propose a public key cryptosystem based on block upper triangular matrices. This system is a variant of the Discrete Logarithm Problem with elements in a finite group, capable of increasing the difficulty of the problem while maintaining the key size. We also propose a key exchange protocol that guarantees that both parties share a secret element of this group and a digital signature scheme that provides data authenticity and integrity.

Vector Combinatorial Problems in a Space of Combinations with Linear Fractional Functions of Criteria

The paper considers vector discrete optimization problem with linear fractional functions of criteria on a feasible set that has combinatorial properties of combinations. Structural properties of a feasible solution domain and of Pareto–optimal (efficient), weakly efficient, strictly efficient solution sets are examined. A relation between vector optimization problems on a combinatorial set of combinations and on a continuous feasible set is determined. One possible approach is proposed in order to solve a multicriteria combinatorial problem with linear- fractional functions of criteria on a set of combinations.

Matrix Power S-box Analysis

* Work supported by the Lithuanian State Science and Studies Foundation.

Visualization of predictive distributions for discrete spatial-temporal log Cox processes approximated with MCMC

An important aspect of decision support systems involves applying sophisticated and flexible statistical models to real datasets and communicating these results to decision makers in interpretable ways. An important class of problem is the modelling of incidence such as fire, disease etc. Models of incidence known as point processes or Cox processes are particularly challenging as they are ‘doubly stochastic’ i.e. obtaining the probability mass function of incidents requires two integrals to be evaluated. Existing approaches to the problem either use simple models that obtain predictions using plug-in point estimates and do not distinguish between Cox processes and density estimation but do use sophisticated 3D visualization for interpretation. Alternatively other work employs sophisticated non-parametric Bayesian Cox process models, but do not use visualization to render interpretable complex spatial temporal forecasts. The contribution here is to fill this gap by inferring predictive distributions of Gaussian-log Cox processes and rendering them using state of the art 3D visualization techniques. This requires performing inference on an approximation of the model on a discretized grid of large scale and adapting an existing spatial-diurnal kernel to the log Gaussian Cox process context.