The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces
Identifieur interne : 001342 ( Istex/Curation ); précédent : 001341; suivant : 001343The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces
Auteurs : Edwin El Mahassni [Australie] ; Phong Q. Nguyen [France] ; Igor E. Shparlinski [Australie]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2001.
English descriptors
- KwdEn :
- Algorithm, Cauchy inequality, Closest vector problem, Digital signature algorithm, Exponential, Exponential sums, Hash function, Inequality, Integer, Large integer, Lattice, Lattice attacks, Lattice basis reduction, Lattice reduction, Lattice reduction algorithm, Least bits, Lemma, Macquarie university, Message recovery, Modulo, Multiplicative, Multiplicative order, Nguyen, Nonce, Number problem, Number theory, Numerical results, Other signature schemes, Phong, Practical applications, Probabilistic polynomial time algorithm, Rational function, Shparlinski, Signature, Signature scheme, Signature schemes, Small number.
- Teeft :
- Algorithm, Cauchy inequality, Closest vector problem, Digital signature algorithm, Exponential, Exponential sums, Hash function, Inequality, Integer, Large integer, Lattice, Lattice attacks, Lattice basis reduction, Lattice reduction, Lattice reduction algorithm, Least bits, Lemma, Macquarie university, Message recovery, Modulo, Multiplicative, Multiplicative order, Nguyen, Nonce, Number problem, Number theory, Numerical results, Other signature schemes, Phong, Practical applications, Probabilistic polynomial time algorithm, Rational function, Shparlinski, Signature, Signature scheme, Signature schemes, Small number.
Abstract
Abstract: It has recently been proved by Nguyen and Shparlinski that the Digital Signature Algorithm (DSA) is insecure when a few consecutive bits of the random nonces k are known for a reasonably small number of DSA signatures. This result confirmed the efficiency of some heuristic lattice attacks designed and numerically verified by Howgrave-Graham and Smart. Here, we extend the attack to the Nyberg-Rueppel variants of DSA. We use a connection with the hidden number problem introduced by Boneh and Venkatesan and new bounds of exponential sums which might be of independent interest.
Url:
DOI: 10.1007/3-540-44670-2_9
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001342
Links to Exploration step
ISTEX:676A6FBB287C9E9A1411106504803A833C464D25Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces</title>
<author><name sortKey="Mahassni, Edwin El" sort="Mahassni, Edwin El" uniqKey="Mahassni E" first="Edwin El" last="Mahassni">Edwin El Mahassni</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computing, Macquarie University, 2109, NSW, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>Department of Computing, Macquarie University, 2109, NSW</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: eelmaha@ics.mq.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
<author><name sortKey="Nguyen, Phong Q" sort="Nguyen, Phong Q" uniqKey="Nguyen P" first="Phong Q." last="Nguyen">Phong Q. Nguyen</name>
<affiliation wicri:level="1"><mods:affiliation>Département d’Informatique, École Normale Supérieure, 45 rue d’Ulm, 75005, Paris, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Département d’Informatique, École Normale Supérieure, 45 rue d’Ulm, 75005, Paris</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: pnguyen@ens.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Shparlinski, Igor E" sort="Shparlinski, Igor E" uniqKey="Shparlinski I" first="Igor E." last="Shparlinski">Igor E. Shparlinski</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computing, Macquarie University, 2109, NSW, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>Department of Computing, Macquarie University, 2109, NSW</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: igor@ics.mq.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:676A6FBB287C9E9A1411106504803A833C464D25</idno>
<date when="2001" year="2001">2001</date>
<idno type="doi">10.1007/3-540-44670-2_9</idno>
<idno type="url">https://api.istex.fr/document/676A6FBB287C9E9A1411106504803A833C464D25/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001342</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001342</idno>
<idno type="wicri:Area/Istex/Curation">001342</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces</title>
<author><name sortKey="Mahassni, Edwin El" sort="Mahassni, Edwin El" uniqKey="Mahassni E" first="Edwin El" last="Mahassni">Edwin El Mahassni</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computing, Macquarie University, 2109, NSW, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>Department of Computing, Macquarie University, 2109, NSW</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: eelmaha@ics.mq.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
<author><name sortKey="Nguyen, Phong Q" sort="Nguyen, Phong Q" uniqKey="Nguyen P" first="Phong Q." last="Nguyen">Phong Q. Nguyen</name>
<affiliation wicri:level="1"><mods:affiliation>Département d’Informatique, École Normale Supérieure, 45 rue d’Ulm, 75005, Paris, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Département d’Informatique, École Normale Supérieure, 45 rue d’Ulm, 75005, Paris</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: pnguyen@ens.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Shparlinski, Igor E" sort="Shparlinski, Igor E" uniqKey="Shparlinski I" first="Igor E." last="Shparlinski">Igor E. Shparlinski</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computing, Macquarie University, 2109, NSW, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>Department of Computing, Macquarie University, 2109, NSW</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: igor@ics.mq.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2001</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Cauchy inequality</term>
<term>Closest vector problem</term>
<term>Digital signature algorithm</term>
<term>Exponential</term>
<term>Exponential sums</term>
<term>Hash function</term>
<term>Inequality</term>
<term>Integer</term>
<term>Large integer</term>
<term>Lattice</term>
<term>Lattice attacks</term>
<term>Lattice basis reduction</term>
<term>Lattice reduction</term>
<term>Lattice reduction algorithm</term>
<term>Least bits</term>
<term>Lemma</term>
<term>Macquarie university</term>
<term>Message recovery</term>
<term>Modulo</term>
<term>Multiplicative</term>
<term>Multiplicative order</term>
<term>Nguyen</term>
<term>Nonce</term>
<term>Number problem</term>
<term>Number theory</term>
<term>Numerical results</term>
<term>Other signature schemes</term>
<term>Phong</term>
<term>Practical applications</term>
<term>Probabilistic polynomial time algorithm</term>
<term>Rational function</term>
<term>Shparlinski</term>
<term>Signature</term>
<term>Signature scheme</term>
<term>Signature schemes</term>
<term>Small number</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term>
<term>Cauchy inequality</term>
<term>Closest vector problem</term>
<term>Digital signature algorithm</term>
<term>Exponential</term>
<term>Exponential sums</term>
<term>Hash function</term>
<term>Inequality</term>
<term>Integer</term>
<term>Large integer</term>
<term>Lattice</term>
<term>Lattice attacks</term>
<term>Lattice basis reduction</term>
<term>Lattice reduction</term>
<term>Lattice reduction algorithm</term>
<term>Least bits</term>
<term>Lemma</term>
<term>Macquarie university</term>
<term>Message recovery</term>
<term>Modulo</term>
<term>Multiplicative</term>
<term>Multiplicative order</term>
<term>Nguyen</term>
<term>Nonce</term>
<term>Number problem</term>
<term>Number theory</term>
<term>Numerical results</term>
<term>Other signature schemes</term>
<term>Phong</term>
<term>Practical applications</term>
<term>Probabilistic polynomial time algorithm</term>
<term>Rational function</term>
<term>Shparlinski</term>
<term>Signature</term>
<term>Signature scheme</term>
<term>Signature schemes</term>
<term>Small number</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: It has recently been proved by Nguyen and Shparlinski that the Digital Signature Algorithm (DSA) is insecure when a few consecutive bits of the random nonces k are known for a reasonably small number of DSA signatures. This result confirmed the efficiency of some heuristic lattice attacks designed and numerically verified by Howgrave-Graham and Smart. Here, we extend the attack to the Nyberg-Rueppel variants of DSA. We use a connection with the hidden number problem introduced by Boneh and Venkatesan and new bounds of exponential sums which might be of independent interest.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001342 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 001342 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Asie |area= AustralieFrV1 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:676A6FBB287C9E9A1411106504803A833C464D25 |texte= The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |