Jacques Stern - Publications


Books


* Fondements mathématiques de l'informatique
Mac Graw Hill, Paris (1990).

* La science du secret
Editions Odile Jacob, (1998).

Articles


* Characterizations of some classes of regular events
Theor. Comp. Sci. 35 (1985), 17-42.

* Complexity of some problems from the theory of automata
Inform. and Control 66 (1985).

* Polynomial-time construction of codes I:linear codes with almost equal weights
Joint work with G. Lachaud.
Applicable Algebra in Engineering, Communication and Computing,3 (1992), 151-161.

* Improved low-density subset sum algorithms
Joint work with M.J. Coster, A. Joux, B.A. LaMacchia,
Computational Complexity 2 (1992), 11-128.

* Polynomial-time construction of codes II: Spherical codes and the kissing number of spheres
Joint work with G. Lachaud.
IEEE Transactions on Information Theory 40 (4) (1994) 1140-1146.

* The cryptanalysis of a public-key implementation of finite group mappings
Joint work with S. Blackburn & S. Murphy.
J. of Cryptology 8 (1995), 157-166.

* A new paradigm for public key identification
IEEE Transactions on Information Theory, 42 (6) 1996, 1757-1768.

View [PS] [PDF]


* The security of the birational permutation signature schemes
Joint work with D. Coppersmith & S. Vaudenay.
J. of Cryptology (1997), 10 (3), 207-221.

View [PS] [PDF]


* The hardness of approximate optima in lattices, codes and systems of linear equations
Joint work with S. Arora, L. Babai & Z. Sweedyk.
J. of Comp Syst Sci (1997), 54(2), 317-331.

View [PS] [PDF]


* Lattice reduction: a toolbox for the cryptanalyst
Joint work with A. Joux.
J. of Cryptology (1998), 11 (3), 161-185.

View [PS] [PDF]


* The action of a few permutations is quickly r-transitive
Joint work with J. Friedman, A. Joux, J.-P. Tillich & Y. Roichman.
Random Structures and Algorithms, 1998, 12(4), 335-350.

* Security arguments for digital signatures and blind signatures
Joint work with D. Pointcheval.
J. of Cryptology (2000), 13(3), 361-396.

View [PS] [PDF]


* RSA--OAEP is Secure under the RSA Assumption
Joint work with Eiichiro Fujisaki, Tatsuaki Okamoto, and David Pointcheval.
J. of Cryptology, 17(2), 2004, 81--104.

View [PS] [PDF]


* On the Fly Authentication and Signature Schemes Based on Groups of Unknown Order
Joint work with M. Girault, and G. Poupard.
J. of Cryptology, 19(4), 2006, 463-487.

View [PS] [PDF]


Proceedings


* Secret linear congruential generators are not cryptographically secure
Proc of the IEEE Symposium on Foundations of Computer Science (1987), 421-426.

* Equivalence relations on lattices and the complexity of the theory of permutations which commute
Contemporary Mathematics 69(1988), 229-240.

* A method for finding codewords of small weight
Coding Theory and applications, Lecture Notes in Computer Science 388 (1989) Springer-Verlag, 106-113.

* An alternative to the Fiat-Shamir protocol
Eurocrypt 89, Lecture Notes in Computer Science 434 (1989), Springer-Verlag,173-180.

* Cryptanalysis of a public-key cryptosystem based on approximations by rational numbers
Joint work with P. Toffin.
Eurocrypt 90, Lecture Notes in Computer Science 473 (1990), Springer-Verlag, 313-317.

* The cryptanalysis of a new public-keycryptosystem based on modular knapsacks
Joint work with Y. M. Chee & A. Joux.
Crypto 91, Lecture Notes in Computer Science 576 (1991), Springer-Verlag, 204-212.

* Improving the critical density of theLagarias-Odlyzko attack against subset sum problems
Joint work with A. Joux.
Fundamentals of Computation Theory, Lecture Notes in Computer Science (529), Springer-Verlag, 258-264.

* Cryptanalysis of another knapsack cryptosystem
Joint work with A. Joux.
Asiacrypt 91, Lecture Notes in Computer Science 739 (1992), Springer-Verlag, 470-476.

* Polynomial-time construction of linear codes with almost equal weights
Joint work with G. Lachaud.
Proceedings of a Conference held in Positano (Italy),Sequences II, Methods in Communications, Security and Computer Science, Springer-Verlag, New York (1991).

* Polynomial-time construction of spherical codes
Joint work with G. Lachaud.
Proceedings of the AAECC-9 Conference, Lecture Notes in Computer Science 539 (1991) Springer-Verlag, 218-223.

* Approximating the number of error locations is NP-complete
Proceedings of the AAECC-10 Conference, Lecture Notes in Computer Science 673 (1992), Springer-Verlag, 323-331.

* Weaknesses of a public key cryptosystem based on factorization of finite groups
Joint work with S. Blackburn & S. Murphy.
Eurocrypt 93, Lecture Notes in Computer Science 765 (1993), Springer-Verlag, 50-54.

* A new identification scheme based on syndrome decoding
Crypto 93, Lecture Notes in Computer Science 773 (1993), Springer-Verlag, 13-21.

View [PS] [PDF]


* Attacks on the birational permutation schemes
Joint work with D. Coppersmith & S. Vaudenay
Crypto 93, Lecture Notes in Computer Science 773 (1993), Springer-Verlag, 435-443.

View [PS] [PDF]


* The hardness of approximating problems defined by linear constraints
Joint work with S. Arora, L. Babai & Z. Sweedyk.
Proc of the IEEE Symposium on Foundations of Computer Science (1993), 586-597.

* On the length of cryptographic hash-values used in cryptographic identification scheme
Joint work with M. Girault.
Proceedings of Crypto 94, Lecture Notes in Computer Science 839 (1994), Springer-Verlag, 202-215.

* Designing identification scheme with keys of short size
Proceedings of Crypto 94, Lecture Notes in Computer Science 839 (1994), Springer-Verlag, 164-173.

View [PS] [PDF]


* Can one design a signature scheme based on error-correcting codes?
Asiacrypt 94, Lecture Notes in Computer Science 917 (1995), Springer-Verlag, 426-428.

View [PS] [PDF]


* The action of a few random permutations on r-tuples and an application to cryptography
Joint work with J. Friedman, A. Joux, J.-P. Tillich & Y. Roichman.
Proceedings of STACS 1996, Grenoble, Lecture Notes in Computer Science 1046 (1996), Springer-Verlag, 375-396.

View [PS] [PDF]


* The validation of cryptographic algorithms
Asiacrypt 96, Lecture Notes in Computer Science 1163 (1996), Springer-Verlag, 301-310.

View [PS] [PDF]


* Security proofs for signature schemes
Joint work with D. Pointcheval.
Eurocrypt 96, Lecture Notes in Computer Science 1070 (1996), Springer-Verlag, 387-398.

View [PS] [PDF]


* A pseudo-random generator provably as secure as syndrome decoding
Joint work with J.-B. Fischer.
Eurocrypt 96, Lecture Notes in Computer Science 1070 (1996), Springer-Verlag, 245-255.

View [PS] [PDF]


* Provably secure blind signature schemes
Joint work with D. Pointcheval.
Asiacrypt 96, Lecture Notes in Computer Science 1163 (1996), Springer-Verlag, 252-265.

View [PS] [PDF]


* The cryptographic security of the syndrome decoding problem for rank distance codes
Joint work with F. Chabaud.
Asiacrypt 96, Lecture Notes in Computer Science 1163 (1996), Springer-Verlag, 368-381.

View [PS] [PDF]


* New blind signatures equivalent to factorisation
Joint work with D. Pointcheval.
Proceedings of the 4th ACM conference on on computer and communication security, ACM press (1997), 92-99.

View [PS] [PDF]


* xmx, a firm-ware oriented block cipher based on modular multiplications
Joint work with D. M'Raïhi, D. Naccache & S. Vaudenay.
Proceedings of Fast Sofware Encryption 97, Lecture Notes in Computer Science 1267 (1997), Springer-Verlag, 166-171.

View [PS] [PDF]


* A new public key cryptosystem
Joint work with D. Naccache.
Proceedings of Eurocrypt 97, Lecture Notes in Computer Science 1233, (1997), Springer-Verlag, 27-36.

View [PS] [PDF]


* SVP: A flexible micropayment system
Joint work with S. Vaudenay.
Financial Cryptography Conference 1997, Lecture Notes in Computer Science 1318, (1997), Springer-Verlag, 166-171.

View [PS] [PDF]


* Merkle-Hellman Revisited: a Cryptanalysis of the Qu-Vanstone Cryptosystem Based on Group Factorizations
Joint work with P. Nguyen.
Proceedings of Crypto 974, Lecture Notes in Computer Science 1294 (1997), Springer-Verlag,198-212.

View [PS] [PDF]


* CS-Cipher
Joint work with S. Vaudenay.
Proceedings of Fast Software Encryption, Lecture Notes in Computer Science 1372 (1998), 189-205.

View [PS] [PDF]


* Cryptanalysis of a Fast Public KeyCryptosystem Presented at SAC '97
Joint work with P. Nguyen.
Proceedings of SAC 98, Lecture Notes in Computer Science (1998), Springer-Verlag.

View [PS] [PDF]


* Security Analysis of a Practical "on the fly" Authentication and Signature Generation
Joint work with G. Poupard.
Proceedings of Eurocrypt 98, Lecture Notes in Computer Science 1403 (1998), Springer-Verlag, 422-434.

View [PS] [PDF]


* Cryptanalysis of the Ajtai-Dwork Cryptosystem
Joint work with P. Nguyen.
Proceedings of Crypto 98, Lecture Notes in Computer Science 1462 (1998), Springer-Verlag, 223-242.

View [PS] [PDF]


* Decorrelated Fast Cipher: an AES Candidate(Extended Abstract)
Joint work with Henri Gilbert, Marc Girault, Philippe Hoogvorst, Fabrice Noilhan, Thomas Pornin, Guillaume Poupard & Serge Vaudenay.
Proceedings of the First Advanced Encryption Standard Candidate Conference, National Institute of Standards and Technology (NIST), (1998).

View [PS] [PDF]


* Lattices and cryptography: an overview
Proceedings of PKC 98, Lecture Notes in Computer Science (1998), Springer-Verlag.

View [PS] [PDF]


* The Béguin-Quisquater Server-Aided RSA Protocol from Crypto '95 is not Secure
Joint work with P. Nguyen,
Proceedings of Asiacrypt 98, Lecture Notes in Computer Science 1514 (1998), Springer-Verlag,372-379.

View [PS] [PDF]


* Generation of Shared RSA Keys by Two Parties
Joint work with G. Poupard.
Proceedings of Asiacrypt 98, Lecture Notes in Computer Science 1514 (1998), Springer-Verlag,11-24.

View [PS] [PDF]


* A new cryptosystem based on higher residues
Joint work with D. Naccache.
Proceedings of the 5th ACM conference on on computer and communication security, ACM press (1998), 59-66.

View [PS] [PDF]


* The Effectiveness of Lattice Attacks Against Low-Exponent RSA
Joint work with C. Coupé & P. Nguyen.
Proceedings of PKC 99, Lecture Notes in Computer Science (1999), Springer-Verlag.

View [PS] [PDF]


* Report on the AES candidates
Joint work with Olivier Baudron, Henri Gilbert, Louis Granboulan, Helena Handschuh, Antoine Joux, Phong Nguyen, Fabrice Noilhan, David Pointcheval, Thomas Pornin, Guillaume Poupard & Serge Vaudenay.
Proceedings of the Second Advanced Encryption Standard Candidate Conference, National Institute of Standards and Technology (NIST), Rome (1999), 53-67.

View [PS] [PDF]


* DFC Update
Joint work with Olivier Baudron, Henri Gilbert, Louis Granboulan, Helena Handschuh, Robert Harley, Antoine Joux, Phong Nguyen, Fabrice Noilhan, David Pointcheval, Thomas Pornin, Guillaume Poupard & Serge Vaudenay.
Proceedings of the Second Advanced Encryption Standard Candidate Conference, NationalInstitute of Standards and Technology (NIST), Rome (1999), 187-199.

View [PS] [PDF]


* Probing Attacks on Tamper-Resistant Devices
Joint work with H. Handschuh, P. Paillier.
Proceedings of CHES 99, Lecture Notes in Computer Science (1999), Springer-Verlag, 303-315.

View [PS] [PDF]


* The Hardness of the Hidden Subset Sum Problem and its Cryptographic Implications
Joint work with P. Nguyen.
Proceedings of Crypto 99, Lecture Notes in Computer Science (1999), Springer-Verlag, 31-46.

View [PS] [PDF]


* On The Fly Signatures based on Factoring
Joint work with G. Poupard.
Proceedings of the 6th ACM conference on computer and communication security, ACM press (1999), 37-45.

View [PS] [PDF]


* Short Proofs of Knowledge for Factoring
Joint work with G. Poupard.
Proceedings of PKC 2000, Lecture Notes in Computer Science 1751 (2000), Springer-Verlag, 147-166.

View [PS] [PDF]


* Sharing Decryption in the Context of Voting or Lotteries
Joint work with P.-A. Fouque & G. Poupard.
Proceedings of Financial Cryptography 2000, Lecture Notes in Computer Science.

View [PS] [PDF]


* Signing on a postcard
Joint work with D. Naccache.
Proceedings of Financial Cryptography 2000, Lecture Notes in Computer Science, Springer-Verlag.

View [PS] [PDF]


* Fair Encryption of RSA Keys
Joint work with G. Poupard.
Eurocrypt 2000, Lecture Notes in Computer Science 1807 (2000), Springer-Verlag,172-189.

View [PS] [PDF]


* Extended notions of security for multicast public-key cryptosystems
Joint work with O. Baudron & D. Pointcheval.
Proceedings of the 27th International Conference on Automata, Languages and programming, Lecture Notes in Computer Science 1853 (2000), Springer-Verlag, 499-511.

View [PS] [PDF]


* Distribution of Modular Sums and the Security of the Server Aided Exponentiation
Joint work with P. Nguyen & I. Shparlinski.
Proceedings of the workshop on Computer Numebr Theoryand Cryptography, CCNT '99, Birkhauser.

View [PS] [PDF]


* Software-Hardware Trade-offs; Application to A5/1 Cryptanalysis
Joint work with T. Pornin.
Proceedings of CHES 99, Lecture Notes in Computer Science (2000), Springer-Verlag, 318-327.

View [PS] [PDF]


* Lattice Reduction in Cryptology: An Update
Joint work with P. Nguyen.
Proceedings of ANTS IV, Lecture Notes in Computer Science 1838 (2000), Springer-Verlag,85-112.

View [PS] [PDF]


* Non-interactive Private Auctions
Joint work with O. Baudron.
Proceedings of Financial Cryptography 2001, Lecture Notes in Computer Science 2339, Springer-Verlag, 364-377.

View [PS] [PDF]


* One Round Threshold Discrete-Log Key Generation without Private Channels
Joint work with P.-A. Fouque.
Proceedings of 4th International Workshop on Practice and Theory in Public Key Cryptography, PKC2001, Lecture Notes in Computer Science 1992 (2001), Springer-Verlag, 190-206.

View [PS] [PDF]


* Practical Multi-candidates Election System
Joint work with O. Baudron, P.-A. Fouque, D .Pointcheval & G. Poupard.
Proceedings of the 20th ACM Symposium on Principles of Distributed Computing (2001), ACM Press, 274-283.

View [PS] [PDF]


* Group Signatures with Efficient Revocation
Joint work with E. Bresson.
Proceedings of 4th International Workshop on Practice and Theory in Public Key Cryptography, PKC2001, Lecture Notes in Computer Science 1992 (2001), Springer-Verlag, 190-206.

View [PS] [PDF]


* Twin Signatures: An alternative to the hash-and-sign paradigm
Joint work with D. Naccache & D. Pointcheval.
Proceedings of the 8th ACM conference on on computer and communication security (2001), ACM press, 20-27.

View [PS] [PDF]


* The two faces of lattices in cryptology
Joint work with P. Nguyen,
Proceedings of CALC '01, Lecture Notes in Computer Science 2146 (2001), Springer-Verlag, 146-180.

View [PS] [PDF]


* RSA-OAEP is Secure under the RSA Assumption
Joint work with E. Fujisaki, T. Okamoto & D. Pointcheval,
Proceedings of Crypto 2001, Lecture Notes in Computer Science 2139 (2001), Springer-Verlag, 260-274.

View [PS] [PDF]


* Fully distributed threshold RSA under standard assumptions
Joint work with P.-A. Fouque.
Proceedings of Asiacrypt 2001, Lecture Notes in Computer Science (2001), Springer-Verlag, 310-330.

View [PS] [PDF]


* Cryptanalysis of the NTRU signature scheme NSS
Joint work with C. Gentry, J. Jonsson & M. Szydlo.
Proceedings of Asiacrypt 2001, Lecture Notes in Computer Science (2001), Springer-Verlag, 1-20.

View [PS] [PDF]


* CryptoComputing with Rationals
Joint work with P.-A. Fouque & G.-J. Wackers.
Proceedings of Financial Cryptography 2002, Lecture Notes in Computer Science (2002), Springer-Verlag.

View [PS] [PDF]


* Flaws in Applying Proof Methodologies to Signature Schemes
Joint work with D. Pointcheval, J. Malone-Lee & N.P. Smart.
Proceedings of Crypto 2002, Lecture Notes in Computer Science 2442 (2002), Springer-Verlag, 93-110.

View [PS] [PDF]


* Threshold Ring Signatures for Ad-hoc Groups.
Joint work with E. Bresson & M. Szydlo.
Proceedings of Crypto 2002, Lecture Notes in Computer Science 2442 (2002), Springer-Verlag, 465-480.

View [PS] [PDF]


* Proofs of Knowledge for Non-Monotone Discrete-Log Formulae and Applications.
Joint work with E. Bresson.
Proceedings of Information Security Conference 2002, Lecture Notes in Computer Science 2433 (2002), Springer-Verlag, 272-288.

View [PS] [PDF]


* The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm.
Joint work with D. Catalano & P. Nguyen.
Proceedings of Asiacrypt 2002, Lecture Notes in Computer Science 2501 (2002), Springer-Verlag, 299-310.

View [PS] [PDF]


* Cryptanalysis of the OTM signature scheme from FC'02.
Joint work with Julien P. Stern.
Proceedings of Financial Cryptography 2003, Lecture Notes in Computer Science 2742 (2003), Springer-Verlag, 138--148.

View [PS] [PDF]


* New attacks against standardized MACs.
Joint work with A. Joux & G. Poupard.
Proceedings of Fast Software Encryption, Lecture Notes in Computer Science 2887 (2003), Springer-Verlag, 170-181.

View [PS] [PDF]


* Why Provable Security Matters.
Proceedings of Eurocrypt 03, Lecture Notes in Computer Science 2656 (2003), 449--461.

View [PS] [PDF]


* Cryptography and the Methodology of Provable Security.
Proceedings of AAECC-15, Lecture Notes in Computer Science 2643 (2003), 1--5.

View [PS] [PDF]


* Almost uniform density of power residues and the provable security of ESIGN.
Joint work with T. Okamoto.
Proceedings of Asiacrypt 2003, Lecture Notes in Computer Science 2894 (2003), 287--301.

View [PS] [PDF]


* Cryptography and the French Banking Cards: Past, Present, Future.

Proceedings of Financial Cryptography 04, Lecture Notes in Computer Science, to appear.

View [PS] [PDF]


* Projective Coordinates Leak.
Joint work with D. Naccache & N. P. Smart.
Proceedings of Eurocrypt 04, Lecture Notes in Computer Science 3027, 257--267.

View [PS] [PDF]


* Differential Cryptanalysis for Multivariate Schemes.
Joint work with P.-A. Fouque & L. Granboulan.
Proceedings of Eurocrypt 05, Lecture Notes in Computer Science 3494, 341--353.

View [PS] [PDF]


* Adapting Density Attacks to Low-Weight Knapsacks.
Joint work with P. Q. Nguyen.
Proceedings of ASIACRYPT 2005, Lecture Notes in Computer Science 3788, 41--58.

View [PS] [PDF]


* Cryptanalysis of an Efficient Proof of Knowledge of Discrete Logarithm.
Joint work with S. Kunz-Jacques, G. Martinet & G. Poupard.
Proceedings of Public Key Cryptography 2006, Lecture Notes in Computer Science 3958, 27--43.

View [PS] [PDF]


* Hardness of Distinguishing the MSB or LSB of Secret Keys in Diffie-Hellman Schemes
Joint work with P.-A. Fouque, D. Pointcheval & S. Zimmer.
Proceedings of ICALP 2006, Part II, Lecture Notes in Computer Science 4052, 240--251.

View [PS] [PDF]


* An Efficient Provable Distinguisher for HFE.
Joint work with V. Dubois & L. Granboulan.
Proceedings of ICALP 2006, Part II, Lecture Notes in Computer Science 4052, 56--167.

View [PS] [PDF]


* Inverting HFE Is Quasipolynomial.
Joint work with A. Joux & L. Granboulan.
Proceedings of Crypto 2006, Lecture Notes in Computer Science 4117, 345-356.

View [PS] [PDF]


* Cryptanalysis of HFE with Internal Perturbation.
Joint work with V. Dubois & L. Granboulan.
Proceedings of Public Key Cryptography 2007, Lecture Notes in Computer Science 4450, 249-265.

View [PS] [PDF]


* Cryptanalysis of SFLASH with Slightly Modified Parameters
Joint work with V. Dubois & P.-A. Fouque.
Proceedings of Eurocrypt 2007, Lecture Notes in Computer Science 4515, 264--275.

View [PS] [PDF]


* Practical Cryptanalysis of SFLASH
Joint work with V. Dubois, P.-A. Fouque & A. Shamir.
Proceedings of Crypto 2007, Lecture Notes in Computer Science 4622, 1--12.

View [PS] [PDF]


* Linear Cryptanalysis of Non Binary Ciphers
Joint work with T. Baignères & S. Vaudenay.
Selected Areas in Cryptography 2007, Lecture Notes in Computer Science 4876, 184--211.

View [PS] [PDF]


* Total Break of the l-IC Signature Scheme.
Joint work with P.-A. Fouque, G. Macario-Rat & L. Perret.
Public Key Cryptography 2008, Lecture Notes in Computer Science 4939, 1--17.

View [PS] [PDF]


* Key Recovery on Hidden Monomial Multivariate Schemes.
Joint work with P.-A. Fouque & G. Macario-Rat.
Proceedings of Eurocrypt 2009, Lecture Notes in Computer Science 4965, 19--30.

View [PS] [PDF]


* Cryptanalysis of Tweaked Versions of SMASH and Reparation.
Joint work with P.-A. Fouque & S. Zimmer.
Selected Areas in Cryptography 2008, Lecture Notes in Computer Science

View [PS] [PDF]


* Linear Bandwith Naccache-Stern Encryption.
Joint work with B. Chevallier-Mames & D. Naccache.
Security and Cryptography for Networks 2008, Lecture Notes in Computer Science

View [PS] [PDF]