4 - Sacs à dos orthogonaux et sacs à dos divisibles

Show full item record

Files in this item

PDF 004.PDF TEXTE.pdf 531.6Kb

Pour citer ce document :
URI: http://hdl.handle.net/2042/1796
Title: 4 - Sacs à dos orthogonaux et sacs à dos divisibles
Author: HARARI (S.)
Abstract: Ce travail introduit deux nouvelles familles de sacs à dos décodables: les sacs à dos orthogonaux et les sacs à dos divisibles. Ils constituent une généralisation des sacs à dos de Graham Shamir [1]. Pour ces familles, la décodabilité est obtenue par une propriété de divisibilité sur les termes de la suite. Les algorithmes de décodage correspondants sont ensuite exposés ainsi qu'une nouvelle classe de transformations, définie pour chacune des deux familles, à valeurs dans la classe des sacs à dos généraux. Ces transformations rendent ces sacs à dos susceptibles d'être utilisés dans des applications cryptographiques
Description: In this work two new families of knapsacks are itroduced . They are orthogonal and divisible knapsacks . They are a generalization of Graham Shamir knapsacks . For those families the decodability is obtained through a divisibility property of each of the terras of the sequence defining them. The corresponding decoding algorithms are presented as well as a new class of transformations, defined on each of the families with values in the class of general knapsacks . These transformation make these knapsacks eligible for use in cryptographie applications . Two publics key cryptographie protocols are presented, one for each class . A study of the cardinality of each class is done, then a generalization to polynomials is sketched . The cryptographie strength of each class is studied through the notion of amplitude of a knapsack which is introduced evaluated and justified . This strength is confirmed through experimental results .
Subject: Cryptographie; Problème sac à dos; Algorithme; Décodage; Chiffrement
Publisher: GRETSI, Saint Martin d'Hères, France
Date: 1992

This item appears in the following Collection(s)

Show full item record





Advanced Search