Search by date:
1998
|
1999
|
2000
|
2001
|
2002
|
2003
|
2004
|
2005
|
2006
|
2007
|
2008
|
2009
|
2010
|
2011
|
2012
|
2013
|
2014
|
2016
|
2017
|
2018
|
2019
| Forthcoming
If you wish to be informed about our seminars by email,
please contact Francesco Berti, Olivier Pereira or François-Xavier Standaert .
Seminars for the year 2003
January 2003
January 13, 11:00 - Multi-exponentiation in cryptography
by Roberto Maria Avanzi
| Date: | January 13, 2003 - 11:00 |
| Location: | Unspecified location |
| Abstract: | Multi-exponentiation, that is the computation of the products of
powers of several bases, is an important component of some key
cryptographic protocols, such as the generation and batch verification of digital signatures.
Research in the topic has usually focused on asymptotic results, and only rarely with the cases of relatively small exponents. But we should not forget that cryptography is usually about very small numbers indeed!
Recently some papers have appeared, combining ideas of the past to bring complexity advantages exactly for exponentiations with exponents of the size used in cryptography. Whereas there's been a lot of activity towards fast single exponentiation with a small amount of precomputations, there's not been much work on efficient multi-exponentiation in restricted environments.
We describe and analyse some new combinations of multi-exponentiation algorithms with representations of the exponents, focussing on the case where the inversion of group elements is fast: This is true for example for elliptic curves, groups of rational divisor classes of hyperelliptic
curves, trace zero varieties and XTR.
These methods are most attractive with exponents in the range from 80 to 256 bits, and can also be used for computing single exponentiations in groups which admit an automorphism satisfying a monic equation of small degree over the integers. They match and sometimes improve on the running time of the best double exponentiation techniques in the aforementioned range, but with smaller memory requirements. Some of the
resulting methods are thus particularly suitable to memory constrained environments such as smart cards. |
| Link: | |
January 16, 16:00 - High Security SW Protection and SW License Management
by Ulf Carlsen
| Date: | January 16, 2003 - 16:00 |
| Location: | Unspecified location |
| Abstract: | High security SW protection can be achieved by code execution in a tamper-proof environment. This talk presents challenges encountered during development of the SLP SW protection system which uses smart card microcontrollers as external execution environment for SW applications. The solution incorporates a smart card operating system with a high-performance virtual machine, comprehensive software licensing mechanisms and smart card application development tools. |
| Link: | |
January 17, 10:00 - Certificate verification trees to implement asynchronous large-scale certification
by Josep Domingo-Ferrer
| Date: | January 17, 2003 - 10:00 |
| Location: | Unspecified location |
| Abstract: | Good public-key infrastructures (PKIs) are essential to make
electronic commerce secure.
Certificate verification trees (CVTs) have been
introduced as a tool for implementation of large-scale
certification authorities (CAs). In most aspects, the CVT approach outperforms previous approaches like X.509 and certificate revocation lists, SDSI/SPKI, certificate revocation trees, etc.
However, there is a tradeoff between manageability for the CA and response time for the user: CVT-based certification as initially proposed is synchronous, i.e. certificates are only issued and revoked at the end of a CVT update period (typically once a day). Assuming that the user is represented by a smart card, we present here solutions that preserve all advantages of CVTs while relaxing the aforementioned synchronization equirement.
If short-validity certificates are used, implicit revocation provided by the proposed solutions completely eliminates the need for the signature verifier to check any revocation information (CRLs, CRTs, etc.).
|
| Link: | |
January 21, 12:00 - Un petit problème de crytanalyse
| Date: | January 21, 2003 - 12:00 |
| Location: | Unspecified location |
| Abstract: | Dans un premier temps, nous présenterons la "square attack", une attaque rigolote sur les chiffrements pas blocs, certainement moins technique que les cryptanalyses linéaires et différentielles. Pour se faire, nous prendrons l'exemple de l'algorithme Skipjack.
Nous montrerons ensuite comment cette attaque peut être appliquée à Safer++ (candidat Nessie). Là où cela devient intéressant, c'est qu'une tentative de généralisation (permettant d'attaquer plus de rounds) de cette attaque sur Safer++ se réduit à un problème mathématique (ou mathématico-algorithmique) très simple à formuler (même les moins matheux d'entre vous s'y retrouveront (peut-être pas Sylvie, mais nous savons tous qu'elle a bien d'autres qualités...)), mais apparemment assez compliqué à résoudre; mes tentatives sont restées infructueuses. Si l'un d'entre vous trouve une solution satisfaisante, il pourra vraisemblablement ajouter un papier à sa liste de publications... |
| Link: | |
January 29, 15:00 - Elliptic Curve Cryptography and Side-Channel Analysis
by Dr. Marc Joye
| Date: | January 29, 2003 - 15:00 |
| Location: | Unspecified location |
| Abstract: | Side-channel analysis is a powerful technique re-discovered by
P. Kocher in 1996. The principle consists in monitoring some
side-channel information like the running time, the power consumption, or the electromagnetic radiation. Next, from the monitored data, the attacker tries to deduce the inner-workings
of the algorithm and thereby to retrieve some secret information.
When there is a single measurement, the process is referred to as a simple side-channel analysis; and when there are several
measurements handled together with statistical tools, the process is referred to as differential side-channel analysis.
This talk is aimed at studying the resistance of elliptic curve
cryptosystems against those two classes of attacks. In particular, we survey the various strategies proposed so far to
prevent side-channel attacks. |
| Link: | |
February 2003
February 06, 10:00 - Secret-Ballot Receipts and Transparent Integrity
by David Chaum
| Date: | February 06, 2003 - 10:00 |
| Location: | Unspecified location |
| Abstract: | Receipts showing exactly who you voted for -- just what is generally wanted and expected today -- have been outlawed to prevent vote selling and other abuses. A new kind of receipt cannot be abused. It also lets you be sure that your votes are correctly included in the final tally, even if all the computers used to run the election are compromised!
Receipts are printed on two-layer media by a modified version of familiar receipt printers. You can read them clearly in the booth; but before leaving, you must separate the layers and choose which one to keep. Either one you take has coded in it the vote information you saw, though your choices can now only be read using keys divided among computers run by election officials.
The layer you take is supplied by the voting machine for publication on an official election website, where you can verify that it is posted. After deriving the tally from the posted receipts, a lotto-like draw selects parts that must be decrypted for inspection, but not so many parts that privacy is compromised. Anyone with a computer can simply check all the decryptions, which should also be published on the website,
and thereby verify that the final tally must be correct.
The printers and media are practical and under development. The overall system cost is lower than with today’s voting machines and the hardware can additionally be used for other purposes year round. Current election system functionality, including write-ins and provisional ballots, is fully supported and can be extended significantly. A variety of public policy issues are raised. (See www.vreceipt.com.)
|
| Link: | |
February 11, 12:00 - L'hypothèse de Riemann
| Date: | February 11, 2003 - 12:00 |
| Location: | Unspecified location |
| Abstract: | Nous décrirons l'hypothèse de Riemann, qui est au coeur de nombreux problèmes de théorie des nombres et indirectement de cryptographie. |
| Link: | Aucune pour les non matheux. Venez à mon exposé, j'essaierai d'éviter les technicalités. |
March 2003
March 04, 12:00 - Non-linear approximation in cryptanalysis
| Date: | March 04, 2003 - 12:00 |
| Location: | Unspecified location |
| Abstract: | Linear cryptanalysis is a powerful cryptanalytic technique that
makes use of a linear approximation over some rounds of a cipher,combined with one (or two) round(s) of key guess. This key guess is usually performed by a partial decryption over every possible key. In this paper, we investigate a particular class of non-linear boolean functions that allows to mount key-dependent approximations of s-boxes. Replacing the classical key guess by these key-dependent approximations allows to quickly distinguish a set of keys including the correct one. By combining different relations, we can make up a system of equations whose solution is the correct key. The resulting attack allows larger flexibility and improves the success rate in some contexts. We apply it to the block cipher Q. In parallel, we propose a chosen-plaintext attack against Q that reduces the required number of plaintext-ciphertext pairs from 2^{97} to 2^{87}. |
| Link: | le rapport technique 1 en 2003 |
April 2003
April 08, 12:30 - Timing Attack on GPS
| Date: | April 08, 2003 - 12:30 |
| Location: | Unspecified location |
| Abstract: | We investigate side-channel attacks where the attacker only needs the Hamming weights of several secret exponents to guess a
long-term secret. Such weights can often be recovered by SPA, EMA, or simply timing attack. We apply this principle to propose a timing attack on the GPS identification scheme. We consider implementations of GPS where the running time of the
exponentiation (commitment phase) leaks the exponent's Hamming
weight, which is for example typical of a square and multiply
algorithm. We show that only 750 time measures allow the attacker to find the private key in few seconds on a PC. Besides its efficiency, two other interesting points in our attack are its resistance to some classical countermeasures against timing attacks, and the fact that it works whether the Chinese Remainder
Theorem is used or not.
|
| Link: | |
April 17, 10:30 - Cryptography in smart cards: current directions to improve hardware performances
by Jean-François Dhem
| Date: | April 17, 2003 - 10:30 |
| Location: | Unspecified location |
| Abstract: | Since the Kocher's first publication in 1996, a major concern in the smart card domain lies in security improvements in term of robustness against side channel attacks like (e.g. DPA, SPA, EMA...) or fault attacks. This should nevertheless not occult the hardware functionalities on which the final software cryptographic libraries will run.
Today, various "second generation" modular multiplication cryptographic hardware based on modular reduction algorithms like the one of Montgomery, Barrett, Quisquater or Sedlak cohabit with a (triple)-DES or elliptic curve accelerator. Most of the major smart card founders (e.g. Infineon, STM, Philips, Atmel,...) also propose high-end 32-bit chips. Some of them have
even chosen to no longer include a dedicated cryptographic hardware accelerator but to improve the instruction set to keep good speed performances.
In our presentation, we will quickly recall the various modular reduction algorithms and the way they could be implemented in hardware. We will then try to compare the advantages and disadvantages of the various implementations and the overall performances of them. Not only performances and security constrains are leading the smart card market. In the GSM/3G
market, for example, (very)-low power consumption is a main constraint but with important computing power and important storage capabilities. In the transport market however, the main constrain is their cost. All this leads to various optimizations and several type of cards depending on the market.
This also may imply the use of "lower cost" cryptographic algorithms like elliptic curves on low cost cards. Finally, we will try to depict, in some way, these various constraints on the smart card hardware.
|
| Link: | |
May 2003
May 20, 12:30 - Répétition de thèse: "Aspects of Fast and Secure Arithmetics on Elliptic Curve Cryptography".
| Date: | May 20, 2003 - 12:30 |
| Location: | Unspecified location |
| Abstract: | We deal with the arithmetic of elliptic curves; with
speedup techniques and secure implementations against side-channel
analysis. We propose some new fast exponentiation methods, most of them
based on efficient endomorphisms. We generalize faults attacks and finally
present new countermeasures for simple and differential side-channel
analysis against elliptic curve implementations. The performance penalty of
these countermeasures is generally very small and sometime . Then,
alternatively some secure implementations with similar performance to
unprotected ones are presented.
|
| Link: | |
May 22, 16:00 - Affine Equivalence Detection - A Useful Tool for the Analysis of
S-Boxes
by Christophe De Cannière
| Date: | May 22, 2003 - 16:00 |
| Location: | Unspecified location |
| Abstract: | Substitution boxes (S-boxes) play an important role in many symmetric
encryption algorithms. In the last decade, much effort has been focused
on the analysis and the design of cryptographically strong S-boxes.
Criteria have been developed to estimate the resistance of S-boxes
against different types of attacks such as differential and linear
cryptanalysis. Currently, researchers are facing the problem of
evaluating the strength of S-boxes with respect to possible algebraic
attacks. Many interesting properties of S-boxes are invariant under
affine transformations and a natural way to simplify their analysis is
to study the equivalence classes defined by these transformations. In
this talk, we will present different efficient algorithms for detecting
linear and affine equivalence relations and we will show how they can
be used to classify S-boxes. |
| Link: | |
May 27, 14:30 - Transitive signatures based on factoring and RSA
by Gregory Neven
| Date: | May 27, 2003 - 14:30 |
| Location: | Unspecified location |
| Abstract: | Transitive signatures are a special flavor of digital signatures in
which the signer authenticates a dynamically growing graph by signing
edges between nodes, with the additional property that given two
signatures for adjacent edges {i,j} and {j,k}, anyone can compute a
third signature for the direct connection {i,k} without needing the
signer's help.
Micali and Rivest introduced the concept of transitive signatures and
proposed a first realization based on the hardness of discrete
logarithms. In this presentation, we'll introduce a new scheme based on
the hardness of factoring large composite integers, and we answer an
open question raised by Micali and Rivest regarding the security of an
RSA-based scheme by proving it transitively unforgeable under adaptive
chosen-message attack assuming the hardness of the hardness of the
one-more RSA problem. Finally, we present hash-based modifications of
these schemes that are provably secure in the random oracle model and
that result in performance improvements.
This is joint work with Mihir Bellare from University of California at
San Diego and has been published at ASIACRYPT 2002 (paper available at
http://www.cs.kuleuven.ac.be/~gregory/ts.ps). |
| Link: | |
June 2003
June 23, 16:30 - Cryptanalyse PDRC des systèmes par blocs et résultats récents pour l'AES
by Eric Filiol
| Date: | June 23, 2003 - 16:30 |
| Location: | Unspecified location |
| Abstract: | La réutilisation d'une clef secrète dans le cadre du chiffrement
(symétrique) par flot a des effets non-négligeables sur la sécurité générale d'un tel système. Cela impose, pour les chiffreurs et les gestionnaires du chiffre des contraintes comptables fortes sur les éléments secrets, qui peuvent occasionner des compromissions cryptologiques de trafic. L'évolution de la cryptographie moderne a tenté de répondre à cette problématique générale de gestion de clefs de deux manières différentes :
par utilisation de système à clef publique.
Les problèmes de réutilisation de clefs ne se posent plus (sauf quelques cas à la marge pour des systèmes faibles). Les contraintes de gestion des clefs se sont transformées en des
contraintes de génération de clefs puisque ces systèmes réclament des propriétés assez fortes pour les éléments secrets.
utilisation de système par blocs (notamment en mode ECB).
La clef secrète est réutilisée pour chaque bloc du message (actuellement 128 bits). Dans cette présentation, après avoir rappelé les faiblesses provenant de la réutilisation de la clef secrète pour le chiffrement par flot, il sera montré que cette réutilisation peut s'avérer dangereuse dans le cadre du
chiffrement par bloc et dégrader la sécurité générale d'un tel système, ce en utilisant des codes correcteurs à répétition. Des résultats récents sur l'AES, provenant de 200 cryptanalyses réelles, seront présentés. Ils permettent de retrouver trois bits d'information sur la clef en n'utilisant que 231 blocs de chiffré, à la condition que ce chiffré ait été produit à
partir de texte codé en ascii. La technique est gébéralisable à d'autres sous-ensembles de clair. |
| Link: | |
October 2003
October 10, 11:00 - Verifiable Democracy - a protocol to secure a virtual legislature
| Date: | October 10, 2003 - 11:00 |
| Location: | Unspecified location |
| Abstract: | The concept of digital signatures is supposed to replace handwritten ones.
Verifiable Democracy is the virtual version of handwritten legislature. It
seems that the concept of Threshold Signatures addresses this.
(In threshold signatures the secret key is distributed
so that only authorized subsets can combine their shares to form a
signature. Any non-authorized subset gains no information about the
signature.)
However, a problem that occurs is that -- even in the case of virtual
legislature -- lawmakers may be absent. In many democratic organizations the
number of users vary temporally and so the meaning of what a majority is. The
manner in which a legislature votes is similar to a threshold signature
scheme, and the power to sign is similar to possessing shares to sign. The
fact that members are absent implies the need for transfer of power to
sign. Schemes for redistribution shares have been developed. However, these
solutions require parties to delete their shares, which is often an
unrealistic assumption. Here we provide a model for democratic bodies and
solve the related problem of assuring an orderly and verifiable transfer of
power as the size of the body varies.
This presentation is based on joint work with Brian King. |
| Link: | http://www.cs.fsu.edu/~desmedt/ |
October 16, 10:00 - The Cryptanalytical Time-Memory Trade-Off: how fast can you go?
by Philippe Oechslin
| Date: | October 16, 2003 - 10:00 |
| Location: | Unspecified location |
| Abstract: | Since Martin Hellman introduced the Cryptanalytical Time-Memory
Trade-Off in 1980, only few optimisation have been suggested. At Lasec
we have developed a new way of organizing the trade-off which makes it
an order of magnitude faster. Moreover the new trade-off has a more
regular structure, which reduces precomputation time, allows for a
better analysis of its performance and opens up possibilities for
other improvements.
We will present the original trade-off, the new version that was
presented at Crypto '03 (with the 5 second windows password cracker
demo) and new directions for creating an even more efficient
trade-off. |
| Link: | |
October 21, 12:30 - Cryptanalyse du protocole DVD-CSS
| Date: | October 21, 2003 - 12:30 |
| Location: | Unspecified location |
| Abstract: | DVD-CSS est le système mis au point par l'industrie du DVD pour
protéger... ben les DVD, c'est malin! D'un design gardé jalousement
secret par ses concepteurs, ce système s'est fait tailler en pièces
peu de temps après son déploiement.
Il ne s'agit donc pas d'un sujet de recherche: cet algorithme est
cassé, re-cassé et irréparable. Il me semble cependant intéressant à
regarder pour diverses raisons:
- c'est l'un des systèmes de chiffrement les plus répandus, et les
plus connus du grand public, ça ne peut donc pas faire de tort pour la
culture générale;
- il permet de réexaminer quelques techniques de cryptanalyse simples,
comme un divide and conquer contre LFSR;
- c'est rigolo: à plusieurs endroits, on est ébahi par les efforts
qu'ils ont fait pour choisir la pire solution possible. |
| Link: | |
November 2003
November 10, 12:30 - Hardware-Based Implementations of Factoring Algorithms
| Date: | November 10, 2003 - 12:30 |
| Location: | Unspecified location |
| Abstract: | Il s'agira d'un exposé sur TWIRL (la machine à factoriser de Shamir). Le but est d'arriver à comprendre et analyser le design de TWIRL, à partir des transparents de Shamir (Crypto 2003). L'objectif à long terme est de parvenir à evaluer la faisabilité d'un tel design sur FPGA. |
| Link: | |
November 17, 09:30 - Optimal Exploitation of Side-Channel Information
by Werner Schindler
| Date: | November 17, 2003 - 09:30 |
| Location: | Unspecified location |
| Abstract: | Many papers on side-channel attacks present remarkable ideas but lack of sound mathematical methods. In particular, only parts of the overall side-channel information are used which lowers the efficiency of the attack. However, in `real life'
side-channel measurements may not be available in unlimited numbers, at least they may be costly.
Minimizing the error probabilities for the guesses of the particular key parts (for a given number of measurements) or
vice versa, minimizing the number of necessary measurements (for fixed error probability) is clearly desirable for a
potential attacker. On the other side, however, this enables the system designer to rate the risk potential and the efficiency of the proposed countermeasures.
Side-channel information can be interpreted as values assumed by random variables where the relevant information is covered by noise. Often this can be modelled as a stochastic process, and the attack can be viewed as a sequence of statistical decision problems. Roughly speaking, an optimal decision strategy minimizes the expected loss of a decision problem which primarily depends on the probabilities for wrong guesses
but also on the consequences of errors. Depending on the concrete situation certain types of errors may be easier to detect and correct than others.
In this way the efficiency of a particular timing attack presented at Cardis '98 could be improved by factor 50, for instance. Some side-channel attacks were not detected without stochastical methods. The talk introduces into the subject matter at some examples where the belonging mathematical models, the applied stochastical methods and the main results are sketched. |
| Link: | |
December 2003
December 10, 12:30 - Cryptanalysis of a Verifiably Committed Signature Scheme based on GPS and RSA
| Date: | December 10, 2003 - 12:30 |
| Location: | Unspecified location |
| Abstract: | Les schémas de "committed signature" permettent de construire des protocoles de fair exchange, pour que des entités n'ayant pas confiance entre elles puissent s'échanger des informations et des objets à distance. Nous présenterons une attaque contre un schéma de "committed signature" présenté à Financial Crypto 2001. L'attaque permet d'extraire des signatures complètes à partir de signatures partielles. J'essaierai de montrer pourquoi construire un protocole à partir de GPS et RSA peut être risqué. |
| Link: | Lire: "Optimistic Fair Exchange with Transparent Signature Recovery", O.Markowitch et S. Saeednia, Financial Crypto 2001 |
December 15, 12:30 - Algorithmes d'inversion modulaire
| Date: | December 15, 2003 - 12:30 |
| Location: | Unspecified location |
| Abstract: | L'inversion modulaire est une opération arithmétique essentielle
pour la cryptographie à clef publique. Nous nous limiterons à
l'inversion dans des corps en caractéristique première (GF(p)).
Nous présenterons les grands classiques tels l'algorithme
d'Euclide, le théorème de Fermat et quelques variantes ainsi
que l'idée plus récente du "GCD-Free". |
| Link: | |
See also:
