# Contents

<table><tbody><tr><td>1</td><td>Introduction</td><td>1</td></tr><tr><td>1.1</td><td>Introduction to Cryptology</td><td>1</td></tr><tr><td>1.2</td><td>Modern Cryptography</td><td>2</td></tr><tr><td>2</td><td>Overview of Our Results</td><td>11</td></tr><tr><td>2.1</td><td>Contributions to Elliptic Curve Cryptography</td><td>12</td></tr><tr><td>2.2</td><td>Cryptanalysis of RSA-based Schemes</td><td>19</td></tr><tr><td>2.3</td><td>Other Results</td><td>25</td></tr><tr><td>2.4</td><td>List of Publications</td><td>28</td></tr><tr><td>I</td><td>Contributions to Elliptic Curve Cryptography</td><td>31</td></tr><tr><td>3</td><td>Constant-Time Hashing to Elliptic and Hyperelliptic Curves</td><td>37</td></tr><tr><td>3.1</td><td>Introduction</td><td>37</td></tr><tr><td>3.2</td><td>The Trivial Encoding: Totally Insecure</td><td>38</td></tr><tr><td>3.3</td><td>Try-and-Increment: Why Constant Time Matters</td><td>40</td></tr><tr><td>3.4</td><td>Encoding to Elliptic Curves</td><td>44</td></tr><tr><td>3.5</td><td>Constructing Encodings to Elliptic Curves and Hyperelliptic Curves</td><td>46</td></tr><tr><td>3.6</td><td>Further Work</td><td>59</td></tr><tr><td>4</td><td>Estimating the Size of the Image of Constant-Time Encodings</td><td>63</td></tr><tr><td>4.1</td><td>Introduction</td><td>63</td></tr><tr><td>4.2</td><td>Preliminaries</td><td>64</td></tr><tr><td>4.3</td><td>Proof of Icart's Conjecture</td><td>65</td></tr><tr><td>4.4</td><td>Analogue in Characteristic 2</td><td>68</td></tr><tr><td>4.5</td><td>Analogue for the Simplified Shallue-van de Woestijne-Ulas Encoding</td><td>70</td></tr><tr><td>4.6</td><td>Constructing Surjective Hash Functions</td><td>72</td></tr><tr><td>4.A</td><td>Galois Groups of Quartics</td><td>72</td></tr><tr><td>5</td><td>Indifferentiable Hashing to Elliptic Curves</td><td>75</td></tr><tr><td>5.1</td><td>Introduction</td><td>75</td></tr><tr><td>5.2</td><td>Admissible Encodings and Indifferentiability</td><td>78</td></tr><tr><td>5.3</td><td>Our Main Construction</td><td>81</td></tr><tr><td>5.4</td><td>A More General Construction</td><td>89</td></tr><tr><td>5.5</td><td>Extensions</td><td>93</td></tr><tr><td>5.A</td><td>Composition Lemmas</td><td>95</td></tr><tr><td>6</td><td>Well-Distributed Encodings</td><td>99</td></tr></tbody></table>
<table><tbody><tr><td>6.1</td><td>Introduction</td><td>99</td></tr><tr><td>6.2</td><td>Well-Distributed Encodings</td><td>101</td></tr><tr><td>6.3</td><td>Character Sums on Curves</td><td>104</td></tr><tr><td>6.4</td><td>Examples of Well-Distributed Encodings</td><td>106</td></tr><tr><td>7</td><td>Hashing and Encoding to Odd Hyperelliptic Curves</td><td>115</td></tr><tr><td>7.1</td><td>Introduction</td><td>115</td></tr><tr><td>7.2</td><td>Odd Hyperelliptic Curves</td><td>116</td></tr><tr><td>7.3</td><td>Our New Encoding</td><td>117</td></tr><tr><td>7.4</td><td>Mapping to the Jacobian</td><td>120</td></tr><tr><td>7.5</td><td>Conclusion</td><td>123</td></tr><tr><td>8</td><td>Huff's Model for Elliptic Curves</td><td>125</td></tr><tr><td>8.1</td><td>Introduction</td><td>125</td></tr><tr><td>8.2</td><td>Huff's Model</td><td>127</td></tr><tr><td>8.3</td><td>Generalizations and Extensions</td><td>133</td></tr><tr><td>8.4</td><td>Pairings</td><td>136</td></tr><tr><td>8.5</td><td>Conclusion and Perspectives</td><td>139</td></tr></tbody></table>

<table><tbody><tr><td>II</td><td>Cryptanalysis of RSA-based Schemes</td><td>141</td></tr><tr><td>9</td><td>Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures</td><td>149</td></tr><tr><td>9.1</td><td>Introduction</td><td>149</td></tr><tr><td>9.2</td><td>The ISO/IEC 9796-2 Standard</td><td>151</td></tr><tr><td>9.3</td><td>Previous Attacks</td><td>152</td></tr><tr><td>9.4</td><td>Building Blocks of the New Attack</td><td>155</td></tr><tr><td>9.5</td><td>Attacking ISO/IEC 9796-2</td><td>157</td></tr><tr><td>9.6</td><td>Cost Estimates</td><td>160</td></tr><tr><td>9.7</td><td>Application to EMV Signatures</td><td>162</td></tr><tr><td>9.8</td><td>Conclusion</td><td>164</td></tr><tr><td>9.A</td><td>Optimizing Bernstein's Batch Size</td><td>165</td></tr><tr><td>9.B</td><td>Large Prime Variant: Complexity Analysis</td><td>166</td></tr><tr><td>9.C</td><td>LLL Attack on EMV SDA-IPKD Encoding</td><td>167</td></tr><tr><td>9.D</td><td>EMV Signature Encoding Formats</td><td>169</td></tr><tr><td>9.E</td><td>Fewer Queries</td><td>170</td></tr><tr><td>9.F</td><td>Expected Number of Queries</td><td>171</td></tr><tr><td>10</td><td>Fault Attacks on EMV Signatures</td><td>175</td></tr><tr><td>10.1</td><td>Introduction</td><td>175</td></tr><tr><td>10.2</td><td>Preliminaries on Lattices</td><td>178</td></tr><tr><td>10.3</td><td>Modeling Faults on ISO/IEC 9796-2 Signatures</td><td>182</td></tr><tr><td>10.4</td><td>The Small Root Attack</td><td>183</td></tr><tr><td>10.5</td><td>Our New Multiple-Fault Attack</td><td>185</td></tr><tr><td>10.6</td><td>Simulation Results</td><td>187</td></tr><tr><td>10.7</td><td>Application to EMV Signatures</td><td>188</td></tr><tr><td>10.8</td><td>Proposed Countermeasures</td><td>190</td></tr></tbody></table>
<table><tr><td>11</td><td>Modulus Fault Attacks Against RSA-CRT Signatures</td><td>191</td></tr><tr><td>11.1</td><td>Introduction</td><td>191</td></tr><tr><td>11.2</td><td>The New Attack</td><td>193</td></tr><tr><td>11.3</td><td>Extending the Attack to Unknown Faulty Moduli</td><td>196</td></tr><tr><td>11.4</td><td>Practical Experiments</td><td>200</td></tr><tr><td>11.5</td><td>Countermeasures and Further Research</td><td>202</td></tr><tr><td>11.A</td><td>Laser Fault Injection</td><td>202</td></tr><tr><td>12</td><td>On the Security of PKCS#1 v1.5 Encryption</td><td>209</td></tr><tr><td>12.1</td><td>Introduction</td><td>209</td></tr><tr><td>12.2</td><td>Preliminaries</td><td>210</td></tr><tr><td>12.3</td><td>PKCS#1 v1.5 Encryption</td><td>213</td></tr><tr><td>12.4</td><td>On the OW-CPA-Security of PKCS#1 v1.5</td><td>214</td></tr><tr><td>12.5</td><td>PKCS#1 v1.5 Malleability and Indistinguishability</td><td>216</td></tr><tr><td>12.6</td><td>Broadcast Attack on PKCS#1 v1.5</td><td>219</td></tr><tr><td>12.7</td><td>Conclusion</td><td>226</td></tr><tr><td>13</td><td>Cryptanalysis of the RSA Subgroup Assumption</td><td>229</td></tr><tr><td>13.1</td><td>Introduction</td><td>229</td></tr><tr><td>13.2</td><td>The New Attack</td><td>230</td></tr><tr><td>13.3</td><td>Attack Complexity</td><td>231</td></tr><tr><td>13.4</td><td>Algorithmic Details</td><td>232</td></tr><tr><td>13.5</td><td>Implementation</td><td>233</td></tr><tr><td>13.6</td><td>Conclusion</td><td>235</td></tr><tr><td>13.A</td><td>Bostan's Algorithms</td><td>236</td></tr><tr><td>13.B</td><td>Source Code of the Attack</td><td>237</td></tr></table>

List of Figures

<table><tr><td>3.1</td><td>The BLS signature scheme.</td><td>39</td></tr><tr><td>3.2</td><td>A randomized variant of the SPEKE protocol.</td><td>43</td></tr><tr><td>3.3</td><td>Icart's encoding.</td><td>51</td></tr><tr><td>3.4</td><td>Icart's binary encoding.</td><td>52</td></tr><tr><td>3.5</td><td>Simplified SWU encoding.</td><td>57</td></tr><tr><td>3.6</td><td>Encoding to odd hyperelliptic curves.</td><td>59</td></tr><tr><td>5.1</td><td>The indifferentiability notion.</td><td>78</td></tr><tr><td>8.1</td><td>Example of a Huff curve (over $\mathbb{R}$).</td><td>128</td></tr></table>
<table><tr><td>9.1</td><td>Summary of the practical attack on ISO/IEC 9796-2.</td><td>161</td></tr><tr><td>9.2</td><td>Distribution of row weights.</td><td>172</td></tr><tr><td>9.3</td><td>Distribution of row weights after reduction.</td><td>173</td></tr><tr><td>11.1</td><td>Architecture of a typical SRAM cell.</td><td>203</td></tr><tr><td>11.2</td><td>Decapsulated chip.</td><td>205</td></tr><tr><td>11.3</td><td>Decapsulated chip (closeup on SRAM).</td><td>205</td></tr><tr><td>11.4</td><td>Exploration process.</td><td>206</td></tr><tr><td>11.5</td><td>1µm laser spot (dotted circle) vs. technology sizes [Pou07].</td><td>207</td></tr><tr><td>11.6</td><td>Laser and target (general overview).</td><td>207</td></tr><tr><td>11.7</td><td>Laser and target (closeup).</td><td>207</td></tr><tr><td>12.1</td><td>Public-key encryption security hierarchy.</td><td>212</td></tr><tr><td>12.2</td><td>PKCS#1 v1.5 security.</td><td>214</td></tr><tr><td>12.3</td><td>Updated security status of PKCS#1 v1.5.</td><td>227</td></tr></table>

List of Tables

<table><tr><td>1.1</td><td>Key size comparison : RSA vs. ECC.</td><td>6</td></tr><tr><td>9.1</td><td>{a, b} values for several RSA challenge moduli.</td><td>157</td></tr><tr><td>9.2</td><td>Estimated cost of the ISO/IEC 9796-2 attack.</td><td>161</td></tr><tr><td>9.3</td><td>EMV message formats.</td><td>164</td></tr><tr><td>9.4</td><td>Improvement factors from the large prime variant.</td><td>167</td></tr><tr><td>10.1</td><td>Attack simulation results using SAGE.</td><td>188</td></tr><tr><td>10.2</td><td>Comparison of the new attack with [CJK+09].</td><td>188</td></tr><tr><td>11.1</td><td>Attack success probability.</td><td>196</td></tr><tr><td>11.2</td><td>Efficiency of the attack with 5 faulty signatures.</td><td>197</td></tr><tr><td>11.3</td><td>Exhaustive search space size.</td><td>198</td></tr><tr><td>11.4</td><td>Success probabilities of the GCD method.</td><td>199</td></tr><tr><td>12.1</td><td>Dimension of the lattice and number of recoverable bits.</td><td>226</td></tr><tr><td>13.1</td><td>Experimental attack running times for 1024-bit moduli.</td><td>233</td></tr></table>
<table><tr><td>13.2 Estimated attack running times for 1024-bit moduli.</td><td>233</td></tr></table>

List of Algorithms

<table><tr><td>3.1 The try-and-increment algorithm.</td><td>42</td></tr><tr><td>3.2 Efficient encoding in characteristic 3.</td><td>58</td></tr><tr><td>5.1 Indifferentiability simulator.</td><td>80</td></tr><tr><td>5.2 Sampling algorithm for the main construction.</td><td>83</td></tr><tr><td>5.3 Sampling algorithm with uniformly random preimages.</td><td>91</td></tr><tr><td>5.4 Sampling algorithm for the general construction.</td><td>92</td></tr><tr><td>7.1 Implementation of the odd hyperelliptic curve encoding.</td><td>120</td></tr><tr><td>8.1 Miller's algorithm.</td><td>136</td></tr><tr><td>13.1 Attack overview.</td><td>232</td></tr><tr><td>13.2 Detailed attack.</td><td>234</td></tr><tr><td>13.3 Bostan's polynomial interpolation.</td><td>236</td></tr><tr><td>13.4 Bostan's polynomial evaluation.</td><td>236</td></tr></table>
<figure><img src="image_34.png" /></figure>
Bibliography

[ABF+02] Christian Aumüller, Peter Bier, Wieland Fischer, Peter Hofreiter, and Jean-Pierre Seifert. Fault attacks on RSA with CRT: Concrete results and practical countermeasures. In Burton S. Kaliski Jr., Çetin Kaya Koç, and Christof Paar, editors, *CHES*, volume 2523 of *Lecture Notes in Computer Science*, pages 260–275. Springer, 2002. 11.1.3

[Ajt02] Miklós Ajtai. Random lattices and a conjectured 0–1 law about their polynomial time computable properties. In *FOCS*, pages 733–742. IEEE Computer Society, 2002. 10.2.4

[Ajt06] Miklós Ajtai. Generating random lattices according to the invariant distribution. Draft, March 2006. 10.2.4, 10.2.4

[ALNR11] Christophe Arène, Tanja Lange, Michael Naehrig, and Christophe Ritzen-
thaler. Faster computation of the Tate pairing. *J. Number Theory*,
131(5):842–857, 2011. 8.1.1

[ANSI X9.44] ANSI X9.44:2007. *Public Key Cryptography for the Financial Services Industry – Key Establishment Using Integer Factorization Cryptography*. ANSI, Washington DC, USA, 2007. 12.1.1

[ANSI X9.62] ANSI X9.62:2005. *Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA)*. ANSI, Washington DC, USA, 2005. I

[ANSI X9.63] ANSI X9.63:2001. *Public Key Cryptography for the Financial Services Industry, Key Agreement and Key Transport Using Elliptic Curve Cryptography*. ANSI, Washington DC, USA, 2001. I

[ANSI X9.98] ANSI X9.98:2010. *Lattice-Based Polynomial Public Key Establishment Algorithm for the Financial Services Industry*. ANSI, Washington DC, USA, 2010. 1.2.2

[B+03] Matthias Brüstle et al. *SOSSE: Simple Operating System for Smartcard Education*, 2003. http://www.mbsks.franken.de/sosse/. 11.A.3
[BBJ+08] Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters. Twisted Edwards curves. In Serge Vaudenay, editor, *AFRICACRYPT*, volume 5023 of *Lecture Notes in Computer Science*, pages 389–405. Springer, 2008. 8.1.1

[BBM00] Mihir Bellare, Alexandra Boldyreva, and Silvio Micali. Public-key encryption in a multi-user setting: Security proofs and improvements. In Bart Preneel, editor, *EUROCRYPT*, volume 1807 of *Lecture Notes in Computer Science*, pages 259–274. Springer, 2000. 12.2.3

[BCCN01] Eric Brier, Christophe Clavier, Jean-Sébastien Coron, and David Naccache. Cryptanalysis of rsa signatures with fixed-pattern padding. In Joe Kilian, editor, *CRYPTO*, volume 2139 of *Lecture Notes in Computer Science*, pages 433–439. Springer, 2001. 2.2.7

[BCDG09] Alexandre Berzati, Cécile Canovas, Jean-Guillaume Dumas, and Louis Goubin. Fault attacks on RSA public keys: Left-to-right implementations are also vulnerable. In Marc Fischlin, editor, *CT-RSA*, volume 5473 of *Lecture Notes in Computer Science*, pages 414–428. Springer, 2009. 11.1.1, 11.1.3

[BCDG10] Alexandre Berzati, Cécile Canovas-Dumas, and Louis Goubin. Public key perturbation of randomized RSA implementations. In Stefan Mangard and François-Xavier Standaert, editors, *CHES*, volume 6225 of *Lecture Notes in Computer Science*, pages 306–319. Springer, 2010. 11.1.1, 11.1.3

[BCG08] Alexandre Berzati, Cécile Canovas, and Louis Goubin. Perturbating RSA public keys: An improved attack. In Elisabeth Oswald and Pankaj Rohatgi, editors, *CHES*, volume 5154 of *Lecture Notes in Computer Science*, pages 380–395. Springer, 2008. 11.1.1, 11.1.3

[BCI+10a] Eric Brier, Jean-Sébastien Coron, Thomas Icart, David Madore, Hugues Randriam, and Mehdi Tibouchi. Efficient indifferentiable hashing into ordinary elliptic curves. In Tal Rabin, editor, *CRYPTO*, volume 6223 of *Lecture Notes in Computer Science*, pages 237–254. Springer, 2010. 2.1.3, 2.4.2, 3.5.1, 3.5.3, 3.5.4, 3.5.4, 4.5, 5.1, 6.1.1, 6.4.1, 6.4.3

[BCI10b] Julien Bringer, Hervé Chabanne, and Thomas Icart. Password based key exchange protocols on elliptic curves which conceal the public parameters. In Jianying Zhou and Moti Yung, editors, *ACNS*, volume 6123 of *Lecture Notes in Computer Science*, pages 291–308, 2010. 2.1.7, 3.6.2

[BCMCC06] Eric Brier, Benoît Chevallier-Mames, Mathieu Ciet, and Christophe Clavier. Why one should also secure RSA public key elements. In Louis Goubin and Mitsuru Matsui, editors, *CHES*, volume 4249 of *Lecture Notes in Computer Science*, pages 324–338. Springer, 2006. 11.1.1, 11.1.3
[BCN$^{+}$10] Aurélie Bauer, Jean-Sébastien Coron, David Naccache, Mehdi Tibouchi, and Damien Vergnaud. On the broadcast and validity-checking security of PKCS#1 v1.5 encryption. In Jianying Zhou and Moti Yung, editors, *ACNS*, volume 6123 of *Lecture Notes in Computer Science*, pages 1–18, 2010. 2.2.4, 2.4.2, 12.1

[BD92] Jørgen Brandt and Ivan Damgård. On generation of probable primes by incremental search. In Ernest F. Brickell, editor, *CRYPTO*, volume 740 of *Lecture Notes in Computer Science*, pages 358–370. Springer, 1992. 2.3.2

[BD00] Dan Boneh and Glenn Durfee. Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$. *IEEE Transactions on Information Theory*, 46(4):1339, 2000. 2.2.6, II

[BDL91] Jørgen Brandt, Ivan Damgård, and Peter Landrock. Speeding up prime number generation. In Hideki Imai, Ronald L. Rivest, and Tsutomu Matsumoto, editors, *ASIACRYPT*, volume 739 of *Lecture Notes in Computer Science*, pages 440–449. Springer, 1991. 2.3.2

[BDL97] Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. On the importance of checking cryptographic protocols for faults (extended abstract). In *EUROCRYPT*, pages 37–51, 1997. 10.1.1, 11.1.1

[BDL01] Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. On the importance of eliminating errors in cryptographic computations. *J. Cryptology*, 14(2):101–119, 2001. 2.2.2, II, 10.1, 10.1.1, 11.1.1

[BECN$^{+}$06] Hagai Bar-El, Hamid Choukri, David Naccache, Michael Tunstall, and Claire Whelan. The sorcerer's apprentice guide to fault attacks. *Proc. IEEE*, 94(2):370–382, 2006. 11.A.1, 11.A.1

[Ber68] Elwyn R. Berlekamp. *Algebraic Coding Theory*. McGraw-Hill, 1968. 5.3.1

[Ber04a] Daniel J. Bernstein. How to find smooth parts of integers. http://cr.yp.to/papers.html#smoothparts, May 2004. 2.2.1, 9.4, 9.4.1

[Ber04b] Daniel J. Bernstein. Scaled remainder trees. http://cr.yp.to/papers.html#scaledmod, August 2004. 9.4.1, 9.5.2

[Ber08] Daniel J. Bernstein. Fast multiplication and its applications. In *Algebraic number theory: lattices, number fields, curves and cryptography*, volume 44 of *Math. Sci. Res. Inst. Publ.*, pages 325–384. Cambridge Univ. Press, Cambridge, 2008. 9.4.1, 13.3
[BF01] Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. In Joe Kilian, editor, *CRYPTO*, volume 2139 of *Lecture Notes in Computer Science*, pages 213–229. Springer, 2001. 1.2.2, 2.1.1, I, 3.1.1, 3.4.2, 5.1.1, 5.1.4, 5.2.2, 5.A.2, 7.1.2, 7.2

[BGLS03] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Eli Biham, editor, *EUROCRYPT*, volume 2656 of *Lecture Notes in Computer Science*, pages 416–432. Springer, 2003. 3.1.1, 5.1.1

[BGV11] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. Fully homomorphic encryption without bootstrapping. Cryptology ePrint Archive, Report 2011/277, 2011. http://eprint.iacr.org/. 2.3.1

[BJ07] Aurélie Bauer and Antoine Joux. Toward a rigorous variation of copersmith's algorithm on three variables. In Moni Naor, editor, *EUROCRYPT*, volume 4515 of *Lecture Notes in Computer Science*, pages 361–378. Springer, 2007. 2.2.6

[BK01] Paulo S. L. M. Barreto and Hae Yong Kim. Fast hashing onto elliptic curves over fields of characteristic 3. Cryptology ePrint Archive, Report 2001/098, 2001. http://eprint.iacr.org/. 3, 3.5.4

[BL07a] Daniel J. Bernstein and Tanja Lange. Faster addition and doubling on elliptic curves. In Kaoru Kurosawa, editor, *ASIACRYPT*, volume 4833 of *Lecture Notes in Computer Science*, pages 29–50. Springer, 2007. 8.1.1

[BL07b] Daniel J. Bernstein and Tanja Lange. Inverted Edwards coordinates. In Serdar Boztas and Hsiao feng Lu, editors, *AAECC*, volume 4851 of *Lecture Notes in Computer Science*, pages 20–27. Springer, 2007. 8.1.1

[BL08] Daniel J. Bernstein and Tanja Lange. Explicit-formulas database, 2008. http://www.hyperelliptic.org/EFD/. 8.1.1

[Ble98] Daniel Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In Hugo Krawczyk, editor, *CRYPTO*, volume 1462 of *Lecture Notes in Computer Science*, pages 1–12. Springer, 1998. 2.2.4, II, 9.1.1, 12.1.1, 12.3.2, 12.5.2, 12.7

[BLF08] Daniel J. Bernstein, Tanja Lange, and Reza Rezaian Farashahi. Binary Edwards curves. In Elisabeth Oswald and Pankaj Rohatgi, editors, *CHES*, volume 5154 of *Lecture Notes in Computer Science*, pages 244–265. Springer, 2008. 8.1.1

[BLP08] Daniel J. Bernstein, Tanja Lange, and Christiane Peters. Attacking and defending the McEliece cryptosystem. In Johannes Buchmann and Jintai Ding, editors, *PQCrypto*, volume 5299 of *Lecture Notes in Computer Science*, pages 31–46. Springer, 2008. 9.E
[BLS01] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. In Colin Boyd, editor, *ASIACRYPT*, volume 2248 of *Lecture Notes in Computer Science*, pages 514–532. Springer, 2001. 2.1.1, 3.1.1, 3.2.1, 3.2.2, 3.3, 3.3.1, 5.1.1

[BLS03] Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott. On the selection of pairing-friendly groups. In Mitsuru Matsui and Robert J. Zuccherato, editors, *Selected Areas in Cryptography*, volume 3006 of *Lecture Notes in Computer Science*, pages 17–25. Springer, 2003. 8.4.2

[BLS04a] Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott. Efficient implementation of pairing-based cryptosystems. *J. Cryptology*, 17(4):321–334, 2004. 8.4.1

[BLS04b] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. *J. Cryptology*, 17(4):297–319, 2004. 2

[Blu70] Leo I. Bluestein. A linear filtering approach to the computation of the discrete Fourier transform. *IEEE Trans. Electroacoustics*, 18:451–455, 1970. 13.4

[BMN01] Colin Boyd, Paul Montague, and Khanh Quoc Nguyen. Elliptic curve based password authenticated key exchange protocols. In Vijay Varadarajan and Yi Mu, editors, *ACISP*, volume 2119 of *Lecture Notes in Computer Science*, pages 487–501. Springer, 2001. 3.3.2

[BMP00] Victor Boyko, Philip D. MacKenzie, and Sarvar Patel. Provably secure password-authenticated key exchange using Diffie-Hellman. In Bart Preneel, editor, *EUROCRYPT*, volume 1807 of *Lecture Notes in Computer Science*, pages 156–171. Springer, 2000. 3.1.1, 5.1.1

[BN05] Paulo S. L. M. Barreto and Michael Naehrig. Pairing-friendly elliptic curves of prime order. In Bart Preneel and Stafford E. Tavares, editors, *Selected Areas in Cryptography*, volume 3897 of *Lecture Notes in Computer Science*, pages 319–331. Springer, 2005. 2

[BNNT11a] Éric Brier, David Naccache, Phong Q. Nguyen, and Mehdi Tibouchi. Modulus fault attacks against RSA signatures. In Bart Preneel and Tsuyoshi Takagi, editors, *CHES*, volume 6917 of *Lecture Notes in Computer Science*. Springer, 2011. To appear. 2.2.3, 2.4.2, 11.1

[BNNT11b] Éric Brier, David Naccache, Phong Q. Nguyen, and Mehdi Tibouchi. Modulus fault attacks against RSA signatures. *J. Cryptographic Engineering*, 1(3), 2011. To appear. 2.2.3, 2.4.1, 11.1
[BNP07] Arnaud Boscher, Robert Naciri, and Emmanuel Prouff. CRT-RSA algorithm protected against fault attacks. In Damien Sauveron, Constantinos Markantonakis, Angelos Bilas, and Jean-Jacques Quisquater, editors, *WISTP*, volume 4462 of *Lecture Notes in Computer Science*, pages 229–243. Springer, 2007. 11.1.3

[BNT09] Eric Brier, David Naccache, and Mehdi Tibouchi. Factoring unbalanced moduli with known bits. In Donghoon Lee and Seokhie Hong, editors, *ICISC*, volume 5984 of *Lecture Notes in Computer Science*, pages 65–72. Springer, 2009. 2.2.6, 2.4.2

[Bol03] Alexandra Boldyreva. Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme. In Yvo Desmedt, editor, *Public Key Cryptography*, volume 2567 of *Lecture Notes in Computer Science*, pages 31–46. Springer, 2003. 3.1.1, 5.1.1

[Bom66] Enrico Bombieri. On exponential sums in finite fields. In *Les Tendances Géom. en Algèbre et Théorie des Nombres*, pages 37–41. Éditions du Centre National de la Recherche Scientifique, Paris, 1966. 2.1.4, 6.1.2

[Bon99] Dan Boneh. Twenty years of attacks on the RSA cryptosystem. *Notices Amer. Math. Soc.*, 46(2):203–213, 1999. II, 12.2.3

[Bos03] Alin Bostan. *Algorithmique efficace pour des opérations de base en calcul formel*. PhD thesis, École polytechnique, 2003. In English. 13.4, 13.5

[Boy03] Xavier Boyen. Multipurpose identity-based signcryption (a Swiss army knife for identity-based cryptography). In Dan Boneh, editor, *CRYPTO*, volume 2729 of *Lecture Notes in Computer Science*, pages 383–399. Springer, 2003. 3.1.1, 5.1.1

[BP96] Eric Bach and René Peralta. Asymptotic semismoothness probabilities. *Math. Comp.*, 65(216):1701–1715, 1996. 9.4, 9.4.2, 9.6

[BPS00] Olivier Baudron, David Pointcheval, and Jacques Stern. Extended notions of security for multicast public key cryptosystems. In Ugo Montanari, José D. P. Rolim, and Emo Welzl, editors, *ICALP*, volume 1853 of *Lecture Notes in Computer Science*, pages 499–511. Springer, 2000. 12.2.3

[BR93] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In *ACM Conference on Computer and Communications Security*, pages 62–73, 1993. 1.2.3, 3.1.1, 5.1.1, 5.2.1, 9.1.1

[BR94] Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption. In *EUROCRYPT*, pages 92–111, 1994. 1.2.3, 9.1.1, 12.1.1
[BR96]
Mihir Bellare and Phillip Rogaway. The exact security of digital signatures: How to sign with RSA and Rabin. In *EUROCRYPT*, pages 399–416, 1996. 1.2.3, 9.1.1, 10.1.1, 10.8, 11.1.1

[BS05]
Alin Bostan and Éric Schost. Polynomial evaluation and interpolation on special sets of points. *J. Complexity*, 21(4):420–446, 2005. 2.2.5, 13.3, 13.4

[BSS05]
Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart. *Advances in Elliptic Curve Cryptography*, volume 317 of *London Mathematical Society Lecture Note Series*, chapter V. Cambridge University Press, 2005. 8.2.3

[BV11]
Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic encryption from Ring-LWE and security for key dependent messages. In Phillip Rogaway, editor, *CRYPTO*, volume 6841 of *Lecture Notes in Computer Science*, pages 505–524. Springer, 2011. 2.3.1

[BZ04]
Joonsang Baek and Yuliang Zheng. Identity-based threshold decryption. In Feng Bao, Robert H. Deng, and Jianying Zhou, editors, *Public Key Cryptography*, volume 2947 of *Lecture Notes in Computer Science*, pages 262–276. Springer, 2004. 3.1.1, 5.1.1

[Can09]
Gaëtan Canivet. *Analyse des effets d'attaques par fautes et conception sécurisée sur plate-forme reconfigurable*. PhD thesis, Institut polytechnique de Grenoble, 2009. 11.A.1

[CC03]
Jae Choon Cha and Jung Hee Cheon. An identity-based signature from gap Diffie-Hellman groups. In Yvo Desmedt, editor, *Public Key Cryptography*, volume 2567 of *Lecture Notes in Computer Science*, pages 18–30. Springer, 2003. 3.1.1, 5.1.1

[CCG+08]
Don Coppersmith, Jean-Sébastien Coron, François Grieu, Shai Halevi, Charanjit S. Jutla, David Naccache, and Julien P. Stern. Cryptanalysis of ISO/IEC 9796-1. *J. Cryptology*, 21(1):27–51, 2008. II, 9.1.1

[CGH04]
Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited. *J. ACM*, 51(4):557–594, 2004. 5.1.1

[CGIP11]
Jean-Sébastien Coron, Aline Gouget, Thomas Icart, and Pascal Paillier. Supplemental access control (PACE v2): Security analysis of PACE Integrated Mapping. Cryptology ePrint Archive, Report 2011/058, 2011. http://eprint.iacr.org/. 2.1.7, 3.6.2

[CJ05]
Mathieu Ciet and Marc Joye. Practical fault countermeasures for Chinese remaindering based cryptosystems. In L. Breveglieri and I. Koren, editors, *FDTC*, pages 124–131, 2005. 11.1.3
[CJK+09] Jean-Sébastien Coron, Antoine Joux, Ilya Kizhvatov, David Naccache, and Pascal Paillier. Fault attacks on RSA signatures with partially unknown messages. In Christophe Clavier and Kris Gaj, editors, *CHES*, volume 5747 of *Lecture Notes in Computer Science*, pages 444–456. Springer, 2009. 2.2.2, 10.1, 10.1.2, 10.1.3, 10.3.2, 10.4, 10.4.1, 10.4.2, 10.6, 10.6, 10.2, 10.7.2, 13.6

[CJM+11] Jean-Sébastien Coron, Antoine Joux, Avradip Mandal, David Naccache, and Mehdi Tibouchi. Cryptanalysis of the RSA subgroup assumption from TCC 2005. In Dario Catalano, Nelly Fazio, Rosario Gennaro, and Antonio Nicolosi, editors, *Public Key Cryptography*, volume 6571 of *Lecture Notes in Computer Science*, pages 147–155. Springer, 2011. 2.2.5, 2.4.2, 13.1

[CJNP00] Jean-Sébastien Coron, Marc Joye, David Naccache, and Pascal Paillier. New attacks on PKCS#1 v1.5 encryption. In Bart Preneel, editor, *EUROCRYPT*, volume 1807 of *Lecture Notes in Computer Science*, pages 369–381. Springer, 2000. II, 9.1.1, 12.1.1, 12.3.2, 12.7

[CJNP02] Jean-Sébastien Coron, Marc Joye, David Naccache, and Pascal Paillier. Universal padding schemes for RSA. In Moti Yung, editor, *CRYPTO*, volume 2442 of *Lecture Notes in Computer Science*, pages 226–241. Springer, 2002. 12.4, 12.4

[CK11] Jean-Marc Couveignes and Jean-Gabriel Kammerer. The geometry of flex tangents to a cubic curve and its parameterizations. Cryptology ePrint Archive, Report 2011/033, 2011. http://eprint.iacr.org/. 2.1.7, 3.5.2

[CM05] Benoît Chevallier-Mames. An efficient CDH-based signature scheme with a tight security reduction. In Victor Shoup, editor, *CRYPTO*, volume 3621 of *Lecture Notes in Computer Science*, pages 511–526. Springer, 2005. 3.1.1

[CM09] Jean-Sébastien Coron and Avradip Mandal. PSS is secure against random fault attacks. In Mitsuru Matsui, editor, *ASIACRYPT*, volume 5912 of *Lecture Notes in Computer Science*, pages 653–666. Springer, 2009. 10.8

[CMNT11] Jean-Sébastien Coron, Avradip Mandal, David Naccache, and Mehdi Tibouchi. Fully homomorphic encryption over the integers with shorter public keys. In Phillip Rogaway, editor, *CRYPTO*, volume 6841 of *Lecture Notes in Computer Science*, pages 487–504. Springer, 2011. 2.3.1, 2.4.2

[CND+06] Jean-Sébastien Coron, David Naccache, Yvo Desmedt, Andrew M. Odlyzko, and Julien P. Stern. Index calculation attacks on RSA signature and encryption. *Des. Codes Cryptography*, 38(1):41–53, 2006. 9.3.1
[CNS99] Jean-Sébastien Coron, David Naccache, and Julien P. Stern. On the security of RSA padding. In Michael J. Wiener, editor, *CRYPTO*, volume 1666 of *Lecture Notes in Computer Science*, pages 1-18. Springer, 1999. 2.2.1, 9.1, 9.1.2, 9.3.2, 9.4.1, 10.8

[CNT10] Jean-Sébastien Coron, David Naccache, and Mehdi Tibouchi. Fault attacks against EMV signatures. In Josef Pieprzyk, editor, *CT-RSA*, volume 5985 of *Lecture Notes in Computer Science*, pages 208-220. Springer, 2010. 2.2.2, 2.4.2, 10.1

[CNT11a] Jean-Sébastien Coron, David Naccache, and Mehdi Tibouchi. Another look at RSA signatures with affine padding. Cryptology ePrint Archive, Report 2011/057, 2011. http://eprint.iacr.org/. 2.2.7, 2.4.4

[CNT11b] Jean-Sébastien Coron, David Naccache, and Mehdi Tibouchi. Optimization of fully homomorphic encryption. Cryptology ePrint Archive, Report 2011/440, 2011. http://eprint.iacr.org/. 2.3.1, 2.4.4

[CNTW09] Jean-Sébastien Coron, David Naccache, Mehdi Tibouchi, and Ralf-Philipp Weinmann. Practical cryptanalysis of ISO/IEC 9796-2 and EMV signatures. In Shai Halevi, editor, *CRYPTO*, volume 5677 of *Lecture Notes in Computer Science*, pages 428-444. Springer, 2009. 2.2.1, 2.4.2, 9.1, 10.8

[Con07] Keith Conrad. Galois groups of cubics and quartics in all characteristics, 2007. http://www.math.uconn.edu/~kconrad/blurbs/galoistheory/cubicquarticchar2.pdf. 4.4, 4.A

[Cop94] Don Coppersmith. Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. *Math. Comp.*, 62(205):333-350, 1994. 9.5.2

[Cop96] Don Coppersmith. Finding a small root of a univariate modular equation. In *EUROCRYPT*, pages 155-165, 1996. 12.6.2

[Cop97] Don Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. *J. Cryptology*, 10(4):233-260, 1997. 2.2.2, II, 10.1, 10.1.2, 12.6

[Cor00] Jean-Sébastien Coron. On the exact security of Full Domain Hash. In Mihir Bellare, editor, *CRYPTO*, volume 1880 of *Lecture Notes in Computer Science*, pages 229-235. Springer, 2000. 1

[Cor02] Jean-Sébastien Coron. Optimal security proofs for PSS and other signature schemes. In Lars R. Knudsen, editor, *EUROCRYPT*, volume 2332 of *Lecture Notes in Computer Science*, pages 272-287. Springer, 2002. 10.1.1, 11.1.1
[Cox04] David A. Cox. Galois theory. Pure and Applied Mathematics. Wiley-Interscience, 2004. 4.A

[CS03] Ronald Cramer and Victor Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput., 33(1):167-226, 2003. 12.1.1

[CT11] Hervé Chabanne and Mehdi Tibouchi. Securing e-passports with elliptic curves. IEEE Security & Privacy, 9(2):75-78, 2011. 2.1.7, 2.4.3, 3.6.2

[DBP+02] Frédéric Darracq, Thomas Beauchene, Vincent Pouget, Hervé Lapuyade, Dean Lewis, Pascal Fouillat, and André Touboul. Single-event sensitivity of a single SRAM cell. IEEE Trans. Nuclear Sci., 49:1486-1490, 2002. 11.A.1, 11.A.1

[DGK07] Ivan Damgård, Martin Geisler, and Mikkel Krøigaard. Efficient and secure comparison for on-line auctions. In Josef Pieprzyk, Hossein Ghodosi, and Ed Dawson, editors, ACISP, volume 4586 of Lecture Notes in Computer Science, pages 416-430. Springer, 2007. 13.2

[Dic30] Karl Dickman. On the frequency of numbers containing prime factors of a certain relative magnitude. Arkiv för matematik, astronomi och fysik, 22A(10):1-14, 1930. 9.4.2

[DJ11] Julien Devigne and Marc Joye. Binary Huff curves. In Aggelos Kiayias, editor, CT-RSA, volume 6558 of Lecture Notes in Computer Science, pages 340-355. Springer, 2011. 2.1.7, 8.5

[dJC85] Wiebren de Jonge and David Chaum. Attacks on some RSA signatures. In Hugh C. Williams, editor, CRYPTO, volume 218 of Lecture Notes in Computer Science, pages 18-27. Springer, 1985. 2.2.7

[DO85] Yvo Desmedt and Andrew M. Odlyzko. A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes. In Hugh C. Williams, editor, CRYPTO, volume 218 of Lecture Notes in Computer Science, pages 516-522. Springer, 1985. 2.2.1, 9.1.2

[DS08] M. Prem Laxman Das and Palash Sarkar. Pairing computation on twisted Edwards form elliptic curves. In Steven D. Galbraith and Kenneth G. Paterson, editors, Pairing, volume 5209 of Lecture Notes in Computer Science, pages 192-210. Springer, 2008. 8.1.1

[Edw07] Harold M. Edwards. A normal form for elliptic curves. Bull. Am. Math. Soc., New Ser., 44(3):393-422, 2007. 8.1.1

[EGA III.1] Alexander Grothendieck and Jean Dieudonné. Éléments de géométrie algébrique III. Étude cohomologique des faisceaux cohérents, première partie. Publ. Math. IHES, 11:5-167, 1961. 5.3.3
[EMV]
EMV. Integrated circuit card specifications for payment systems. Book 2. Security and key management. Version 4.2, June 2008. http://www.emvco.com/. II, 9.7, 9.7.1, 10.1.2, 10.3.1, 10.7.1

[EMV TC]
EMV. EMVCo type approval terminal level 2 test cases. Version 4.2a., April 2009. http://www.emvco.com/. 10.7.1

[Far11]
Reza Rezaeian Farashahi. Hashing into hessian curves. In Abderrahmane Nitaj and David Pointcheval, editors, *AFRICACRYPT*, volume 6737 of *Lecture Notes in Computer Science*, pages 278–289. Springer, 2011. 2.1.7, 3.5.2, 6.1.1

[FFS<sup>+</sup>11]
Reza R. Farashahi, Pierre-Alain Fouque, Igor E. Shparlinski, Mehdi Tibouchi, and J. Felipe Voloch. Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. *Math. Comput.*, 2011. To appear. 2.1.4, 2.4.1, 6.1.2

[FIPS186-3]
FIPS PUB 186-3. *Digital Signature Standard (DSS)*. NIST, USA, 2009. I, 5.5.3

[FJ05]
Michael D. Fried and Moshe Jarden. *Field arithmetic*, volume 11 of *Ergebnisse der Mathematik und ihrer Grenzgebiete*. Springer-Verlag, Berlin, second edition, 2005. 4.3.2

[FKT03]
Eisaku Furukawa, Mitsuru Kawazoe, and Tetsuya Takahashi. Counting points for hyperelliptic curves of type $y^2 = x^5 + ax$ over finite prime fields. In Mitsuru Matsui and Robert J. Zuccherato, editors, *Selected Areas in Cryptography*, volume 3006 of *Lecture Notes in Computer Science*, pages 26–41. Springer, 2003. 3.5.3, 3.5.4, 7.1.2, 7.2

[FOPS04]
Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern. RSA-OAEP is secure under the RSA assumption. *J. Cryptology*, 17(2):81–104, 2004. 12.1.1

[FS11]
David Mandell Freeman and Takakazu Satoh. Constructing pairing-friendly hyperelliptic curves using Weil restriction. *J. Number Theory*, 131(5):959–983, 2011. 7.1.2, 7.2

[FSV10]
Reza R. Farashahi, Igor E. Shparlinski, and José Felipe Voloch. On hashing into elliptic curves. *J. Math. Cryptology*, 3:353–360, 2010. 4.1.2, 6.4.1, 6.4.1

[FT10a]
Pierre-Alain Fouque and Mehdi Tibouchi. Deterministic encoding and hashing to odd hyperelliptic curves. In Marc Joye, Atsuko Miyaji, and Akira Otsuka, editors, *Pairing*, volume 6487 of *Lecture Notes in Computer Science*, pages 265–277. Springer, 2010. 2.1.5, 2.4.2, 3.5.3, 6.4.1, 6.4.3, 7.1
[FT10b] Pierre-Alain Fouque and Mehdi Tibouchi. Estimating the size of the image of deterministic hash functions to elliptic curves. In Michel Abdalla and Paulo S. L. M. Barreto, editors, *LATINCRYPT*, volume 6212 of *Lecture Notes in Computer Science*, pages 81–91. Springer, 2010. 2.1.2, 2.4.2, 4.1

[FT11] Pierre-Alain Fouque and Mehdi Tibouchi. Close to uniform prime number generation with fewer random bits. Cryptology ePrint Archive, Report 2011/481, 2011. http://eprint.iacr.org/. 2.3.2, 2.4.4

[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, *STOC*, pages 169–178. ACM, 2009. 2.3.1

[GH11] Craig Gentry and Shai Halevi. Implementing Gentry’s fully-homomorphic encryption scheme. In Kenneth G. Paterson, editor, *EUROCRYPT*, volume 6632 of *Lecture Notes in Computer Science*, pages 129–148. Springer, 2011. 2.3.1

[Gir06] Christophe Giraud. An RSA implementation resistant to fault attacks and to simple power analysis. *IEEE Trans. Computers*, 55(9):1116–1120, 2006. 10.8, 11.1.3

[GKZ07] Pierrick Gaudry, Alexander Kruppa, and Paul Zimmermann. A GMP-based implementation of Schönhage-Strassen’s large integer multiplication algorithm. In Dongming Wang, editor, *ISSAC*, pages 167–174. ACM, 2007. 9.4.1

[GM82] Shafi Goldwasser and Silvio Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In *STOC*, pages 365–377. ACM, 1982. 1.2.3

[GM84] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. *J. Comput. Syst. Sci.*, 28(2):270–299, 1984. 1.2.3

[GM97] Marc Girault and Jean-François Misarsky. Selective forgery of RSA signatures using redundancy. In *EUROCRYPT*, pages 495–507, 1997. 2.2.7

[GMR84] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A “paradoxical” solution to the signature problem. In *FOCS*, pages 441–448. IEEE, 1984. 1.2.3

[GMR88] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. *SIAM J. Comput.*, 17(2):281–308, 1988. 1.2.3
[Gri00] François Grieu. A chosen messages attack on the ISO/IEC 9796-1 signature scheme. In Bart Preneel, editor, *EUROCRYPT*, volume 1807 of *Lecture Notes in Computer Science*, pages 70–80. Springer, 2000. II, 9.1.1

[Gro05] Jens Groth. Cryptography in subgroups of $Z_N^*$. In Joe Kilian, editor, *TCC*, volume 3378 of *Lecture Notes in Computer Science*, pages 50–65. Springer, 2005. 2.2.5, II, 13.1, 13.1.1, 13.1.2, 13.1, 13.5, 13.6

[Gro08] The PARI Group. *PARI/GP, Version 2.3.4*, 2008. http://pari.math.u-bordeaux.fr. 9.5.2

[GS02] Craig Gentry and Alice Silverberg. Hierarchical ID-based cryptography. In Yuliang Zheng, editor, *ASIACRYPT*, volume 2501 of *Lecture Notes in Computer Science*, pages 548–566. Springer, 2002. 3.1.1, 5.1.1

[H$^+$09] William B. Hart et al. *Multi Precision Integers and Rationals library*, 2009. http://www.mpir.org. 9.5.2, 9.5.2

[Har77] Robin Hartshorne. *Algebraic Geometry*, volume 52 of *Graduate Texts in Mathematics*. Springer, 1977. 5.3.2, 5.3.3

[Has36] Helmut Hasse. Zur Theorie der abstrakten elliptischen Funktionenkörper III. Die Struktur des Meromorphismenrings; die Riemannsche Vermutung. *J. Reine Angew. Math.*, 175:193–208, 1936. 3.3.1

[Hås88] Johan Håstad. Solving simultaneous modular equations of low degree. *SIAM J. Comput.*, 17(2):336–341, 1988. 2.2.4, II, 12.6

[Hel76] Whitfield Diffie Martin Hellman. New directions in cryptography. *IEEE Transactions on Information Theory*, 22(6):644–654, 1976. 1.2.1, 1.2.2, II

[HG97] Nick Howgrave-Graham. Finding small roots of univariate modular equations revisited. In Michael Darnell, editor, *IMA Int. Conf.*, volume 1355 of *Lecture Notes in Computer Science*, pages 131–142. Springer, 1997. 12.6.2, 12.2

[HH$^+$10] William B. Hart, David Harvey, et al. *Fast Library for Number Theory*, 2010. http://www.flintlib.org. 13.5

[HKT05] Mitsuhiro Haneda, Mitsuru Kawazoe, and Tetsuya Takahashi. Suitable curves for genus-4 HCC over prime fields. In Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, and Moti Yung, editors, *ICALP*, volume 3580 of *Lecture Notes in Computer Science*, pages 539–550. Springer, 2005. 3.5.3, 3.5.4, 7.1.2, 7.2
[HL02] Jeremy Horwitz and Ben Lynn. Toward hierarchical identity-based encryption. In Lars R. Knudsen, editor, *EUROCRYPT*, volume 2332 of *Lecture Notes in Computer Science*, pages 466-481. Springer, 2002. 3.1.1, 5.1.1

[HM08] Mathias Herrmann and Alexander May. Solving linear equations modulo divisors: On factoring given any bits. In Josef Pieprzyk, editor, *ASI-ACRYPT*, volume 5350 of *Lecture Notes in Computer Science*, pages 406-424. Springer, 2008. 10.1.2, 10.1

[HQZ04] Guillaume Hanrot, Michel Quercia, and Paul Zimmermann. The middle product algorithm I. *Appl. Algebra Eng. Commun. Comput.*, 14(6):415-438, 2004. 13.3

[Huf48] Gerald B. Huff. Diophantine problems in geometry and elliptic ternary forms. *Duke Math. J.*, 15:443-453, 1948. 2.1.6, 8.1.1, 8.1

[HWCD08] Hüseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson. Twisted Edwards curves revisited. In Josef Pieprzyk, editor, *ASIACRYPT*, volume 5350 of *Lecture Notes in Computer Science*, pages 326-343. Springer, 2008. 8.1.1

[Ica09] Thomas Icart. How to hash into elliptic curves. In Shai Halevi, editor, *CRYPTO*, volume 5677 of *Lecture Notes in Computer Science*, pages 303-316. Springer, 2009. 2.1.1, 2.1.2, 3.5.2, 3.6.1, 4.1, 4.2.1, 4.2.2, 4.6, 5.3, 5.3.2, 5.3.3, 6.1.1, 6.4.1

[ICAO10] ISO/IEC JTC1 SC17 WG3/TF5. *Supplemental Access Control for Machine Readable Travel Documents, version 1.01*. International Civil Aviation Organization, 2010. http://mrtd.icao.int/. I, 3.6.2

[IEEE P1363] IEEE P1363-2000. *Standard Specifications For Public Key Cryptography*. IEEE, 2000. 11.1.3

[IJ08] Sorina Ionica and Antoine Joux. Another approach to pairing computation in Edwards coordinates. In Dipanwita Roy Chowdhury, Vincent Rijmen, and Abhijit Das, editors, *INDOCRYPT*, volume 5365 of *Lecture Notes in Computer Science*, pages 400-413. Springer, 2008. 8.1.1

[ISO18033-2] ISO/IEC 18033-2:2006. *Information technology - Security techniques - Encryption algorithms - Part 2: Asymmetric ciphers*. ISO, Geneva, Switzerland, 2006. 1.2.3, I, 12.1.1

[ISO8825-1] ISO/IEC 8825-1:2002. *Information technology - ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)*. ISO, Geneva, Switzerland, 2002. 10.7.1
[ISO9796-1] ISO/IEC 9796-1. *Information Technology - Security Techniques - Digital signature scheme giving message recovery, Part 1: Mechanisms using redundancy*. ISO, Geneva, Switzerland, 1999. 1.2.3, 9.1, 9.1.1

[ISO9796-2] ISO/IEC 9796-2. *Information Technology - Security Techniques - Digital signature scheme giving message recovery, Part 2: Mechanisms using a hash-function*. ISO, Geneva, Switzerland, 1997. 1.2.3, 2.2.1, 9.1, 9.1.1, 9.1.2, 9.2, 10.3.1

[ISO9796-2:2010] ISO/IEC 9796-2:2010. *Information Technology - Security Techniques - Digital signature scheme giving message recovery, Part 2: Integer factorization based mechanisms*. ISO, Geneva, Switzerland, 2010. 2.2.1, 9.1, 9.2, 9.8

[ISO9796-2:2002] ISO/IEC 9796-2:2002. *Information Technology - Security Techniques - Digital signature scheme giving message recovery, Part 2: Integer factorization based mechanisms*. ISO, Geneva, Switzerland, 2002. 2.2.1, 2.2.1, II, 9.1, 9.1.1, 9.1.2, 9.2, 10.1.2, 10.3.1

[Jab96] David P. Jablon. Strong password-only authenticated key exchange. *SIGCOMM Comput. Commun. Rev.*, 26:5–26, October 1996. 3.1.1, 3.3.2, 5.1.1

[Jab97] David P. Jablon. Extended password key exchange protocols immune to dictionary attacks. In *WETICE*, pages 248–255. IEEE Computer Society, 1997. 3.3.2

[JLQ99] Marc Joye, Arjen K. Lenstra, and Jean-Jacques Quisquater. Chinese remaindering based cryptosystems in the presence of faults. *J. Cryptology*, 12(4):241–245, 1999. 10.1.1

[JM06] Ellen Jochemsz and Alexander May. A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants. In Xuejia Lai and Kefei Chen, editors, *ASIACRYPT*, volume 4284 of *Lecture Notes in Computer Science*, pages 267–282. Springer, 2006. 2.2.4, 12.6.1, 12.6.2

[JNT07] Antoine Joux, David Naccache, and Emmanuel Thomé. When *e*-th roots become easier than factoring. In Kaoru Kurosawa, editor, *ASIACRYPT*, volume 4833 of *Lecture Notes in Computer Science*, pages 13–28. Springer, 2007. II, 9.1.1

[Jou00] Antoine Joux. A one round protocol for tripartite Diffie-Hellman. In Wieb Bosma, editor, *ANTS*, volume 1838 of *Lecture Notes in Computer Science*, pages 385–394. Springer, 2000. 1.2.2, I
[Jou02] Antoine Joux. The Weil and Tate pairings as building blocks for public key cryptosystems. In Claus Fieker and David R. Kohel, editors, *ANTS*, volume 2369 of *Lecture Notes in Computer Science*, pages 20–32. Springer, 2002. 3.5.4, 7.2, 7.2

[JP06] Marc Joye and Pascal Paillier. Fast generation of prime numbers on portable devices: An update. In Louis Goubin and Mitsuru Matsui, editors, *CHES*, volume 4249 of *Lecture Notes in Computer Science*, pages 160–173. Springer, 2006. 2.3.2

[JPV00] Marc Joye, Pascal Paillier, and Serge Vaudenay. Efficient generation of prime numbers. In Çetin Kaya Koç and Christof Paar, editors, *CHES*, volume 1965 of *Lecture Notes in Computer Science*, pages 340–354. Springer, 2000. 2.3.2

[JPY01] Marc Joye, Pascal Paillier, and Sung-Ming Yen. Secure evaluation of modular functions. In R. J. Hwang and C. K. Wu, editors, *2001 International Workshop on Cryptology and Network Security*, pages 227–229, Taipei, Taiwan, 2001. 10.8

[JTV10] Marc Joye, Mehdi Tibouchi, and Damien Vergnaud. Huff's model for elliptic curves. In Guillaume Hanrot, François Morain, and Emmanuel Thomé, editors, *ANTS*, volume 6197 of *Lecture Notes in Computer Science*, pages 234–250. Springer, 2010. 2.1.6, 2.4.2, 8.1

[KAF$^{+}$10] Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Joppe W. Bos, Pierrick Gaudry, Alexander Kruppa, Peter L. Montgomery, Dag Arne Osvik, Herman J. J. te Riele, Andrey Timofeev, and Paul Zimmermann. Factorization of a 768-bit RSA modulus. In Tal Rabin, editor, *CRYPTO*, volume 6223 of *Lecture Notes in Computer Science*, pages 333–350. Springer, 2010. II, 13.5

[KJJ99] Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In Michael J. Wiener, editor, *CRYPTO*, volume 1666 of *Lecture Notes in Computer Science*, pages 388–397. Springer, 1999. II

[KKM11] Ann Hibner Koblitz, Neal Koblitz, and Alfred Menezes. Elliptic curve cryptography: The serpentine course of a paradigm shift. *J. Number Theory*, 131(5):781–814, 2011. I

[KL99] Erich Kaltofen and Austin A. Lobo. Distributed matrix-free solution of large sparse linear systems over finite fields. *Algorithmica*, 24(3-4):331–348, 1999. 9.5.2

[KLR10] Jean-Gabriel Kammerer, Reynald Lercier, and Guénaël Renault. Encoding points on hyperelliptic curves over finite fields in deterministic
polynomial time. In Marc Joye, Atsuko Miyaji, and Akira Otsuka, editors, *Pairing*, volume 6487 of *Lecture Notes in Computer Science*, pages 278–297. Springer, 2010. 2.1.1, 3.5.2, 3.5.3, 3.5.3, 6.4.2, 6.4.2, 6.4.2, 7.1.1

[KM11] Neal Koblitz and Alfred Menezes. Another look at security definitions. *Cryptology ePrint Archive*, Report 2011/343, 2011. http://eprint.iacr.org/. 2

[Kob87] Neal Koblitz. Elliptic curve cryptosystems. *Math. Comp.*, 48:203–209, 1987. 1.2.2, I

[Koc96] Paul C. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Neal Koblitz, editor, *CRYPTO*, volume 1109 of *Lecture Notes in Computer Science*, pages 104–113. Springer, 1996. II

[KQ07] Chong Hee Kim and Jean-Jacques Quisquater. Fault attacks for CRT based RSA: New attacks, new results, and new countermeasures. In Damien Sauveron, Constantinos Markantonakis, Angelos Bilas, and Jean-Jacques Quisquater, editors, *WISTP*, volume 4462 of *Lecture Notes in Computer Science*, pages 215–228. Springer, 2007. 10.8

[KS00] David R. Kohel and Igor Shparlinski. On exponential sums and group generators for elliptic curves over finite fields. In Wieb Bosma, editor, *ANTS*, volume 1838 of *Lecture Notes in Computer Science*, pages 395–404. Springer, 2000. 6.3, 7.4.2

[KT08] Mitsuru Kawazoe and Tetsuya Takahashi. Pairing-friendly hyperelliptic curves with ordinary jacobians of type $y^2 = x^5 + ax$. In Steven D. Galbraith and Kenneth G. Paterson, editors, *Pairing*, volume 5209 of *Lecture Notes in Computer Science*, pages 164–177. Springer, 2008. 3.5.4, 7.1.2, 7.2

[KW89] Luise-Charlotte Kappe and Bette Warren. An elementary test for the Galois group of a quartic polynomial. *Amer. Math. Monthly*, 96(2):133–137, 1989. 4.5, 4.A

[KW03] Jonathan Katz and Nan Wang. Efficiency improvements for signature schemes with tight security reductions. In Sushil Jajodia, Vijayalakshmi Atluri, and Trent Jaeger, editors, *ACM Conference on Computer and Communications Security*, pages 155–164. ACM, 2003. 1

[LJMP90] Arjen K. Lenstra, Hendrik W. Lenstra Jr., Mark S. Manasse, and John M. Pollard. The number field sieve. In *STOC*, pages 564–572. ACM, 1990. 1.2.2, II
[LL93] Arjen K. Lenstra and Hendrik W. Lenstra, Jr., editors. *The development of the number field sieve*, volume 1554 of *Lecture Notes in Mathematics*. Springer-Verlag, Berlin, 1993. II

[LLL82] Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. *Math. Ann.*, 261(4):515–534, 1982. 9.7.2, 10.2.4, 2, 12.6.2

[Lob95] Austin A. Lobo. *WLSS2: an implementation of the homogeneous block Wiedemann algorithm*, 1995. http://www4.ncsu.edu/~kaltofen/software/wiliss. 9.5.2

[LQ04] Benoît Libert and Jean-Jacques Quisquater. Efficient signcryption with key privacy from gap Diffie-Hellman groups. In Feng Bao, Robert H. Deng, and Jianying Zhou, editors, *Public Key Cryptography*, volume 2947 of *Lecture Notes in Computer Science*, pages 187–200. Springer, 2004. 3.1.1, 5.1.1

[Mau89] Ueli M. Maurer. Fast generation of secure RSA-moduli with almost maximal diversity. In *EUROCRYPT*, pages 636–647, 1989. 2.3.2

[Mau95] Ueli M. Maurer. Fast generation of prime numbers and secure public-key cryptographic parameters. *J. Cryptology*, 8(3):123–155, 1995. 2.3.2

[McE78] Robert J. McEliece. A public-key cryptosystem based on algebraic coding theory. *The Deep Space Network Progress Report*, 42-44:114–116, 1978. 1.2.2

[MDT+10] Amir Pasha Mirbaha, Jean-Max Dutertre, Assia Tria, Michel Agoyan, Anne-Lise Ribotta, and David Naccache. Study of single-bit fault injection techniques by laser on an AES cryptosystem. In D. Gizopoulos and A. Chatterjee, editors, *IOLTS*, 2010. 11.4

[MH78] Ralph C. Merkle and Martin E. Hellman. Hiding information and signatures in trapdoor knapsacks. *IEEE Transactions on Information Theory*, 24(5):525–530, 1978. 1.2.2

[Mih94] Preda Mihailescu. Fast generation of provable primes using search in arithmetic progressions. In Yvo Desmedt, editor, *CRYPTO*, volume 839 of *Lecture Notes in Computer Science*, pages 282–293. Springer, 1994. 2.3.2

[Mil85] Victor S. Miller. Use of elliptic curves in cryptography. In Hugh C. Williams, editor, *CRYPTO*, volume 218 of *Lecture Notes in Computer Science*, pages 417–426. Springer, 1985. 1.2.2, I

[Mil04] Victor S. Miller. The Weil pairing, and its efficient calculation. *J. Cryptology*, 17(4):235–261, 2004. 8.4.1
[Min96] Hermann Minkowski. *Geometrie der Zahlen*. Teubner-Verlag, 1896. 10.2.4

[Mis98] Jean-François Misarsky. How (not) to design RSA signature schemes. In Hideki Imai and Yuliang Zheng, editors, *Public Key Cryptography*, volume 1431 of *Lecture Notes in Computer Science*, pages 14–28. Springer, 1998. 9.1.2, 9.3.1

[MOV93] Alfred Menezes, Tatsuaki Okamoto, and Scott A. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field. *IEEE Transactions on Information Theory*, 39(5):1639–1646, 1993. 1.2.2

[MRH04] Ueli M. Maurer, Renato Renner, and Clemens Holenstein. Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In Moni Naor, editor, *TCC*, volume 2951 of *Lecture Notes in Computer Science*, pages 21–39. Springer, 2004. 2.1.3, 3.3.1, 5.1.3, 5.2.1, 5.1, 5.2.1

[Mui06] James A. Muir. Seifert’s RSA fault attack: Simplified analysis and generalizations. In Peng Ning, Sihan Qing, and Ninghui Li, editors, *ICICS*, volume 4307 of *Lecture Notes in Computer Science*, pages 420–434. Springer, 2006. 11.1.1, 11.1.3

[MVO91] Alfred Menezes, Scott A. Vanstone, and Tatsuaki Okamoto. Reducing elliptic curve logarithms to logarithms in a finite field. In *STOC*, pages 80–89. ACM, 1991. 1.2.2

[MWZ98] Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato. An elementary introduction to hyperelliptic curves. In Neal Koblitz, editor, *Algebraic Aspects of Cryptography*, volume 3 of *Algorithms and Computation in Mathematics*, pages 155–178. Springer, 1998. 7.4.1

[Ngu09] Phong Q. Nguyen. Public-key cryptanalysis. In I. Luengo, editor, *Recent Trends in Cryptography*, volume 477 of *Contemporary Mathematics*. AMS–RSME, 2009. 10.2, 11.2.2

[NS97] Phong Q. Nguyen and Jacques Stern. Merkle-Hellman revisited: A cryptoanalysis of the Qu-Vanstone cryptosystem based on group factorizations. In Burton S. Kaliski Jr., editor, *CRYPTO*, volume 1294 of *Lecture Notes in Computer Science*, pages 198–212. Springer, 1997. 2.2.2, II, 10.1.3, 10.5, 10.5, 11.1.2, 11.2.2, 11.2.2, 2

[NS98] Phong Q. Nguyen and Jacques Stern. Cryptanalysis of a fast public key cryptosystem presented at SAC ’97. In Stafford E. Tavares and Henk Meijer, editors, *Selected Areas in Cryptography*, volume 1556 of *Lecture Notes in Computer Science*, pages 213–218. Springer, 1998. 2.2.2, 10.1.3, 11.2.2
[NS01] Phong Q. Nguyen and Jacques Stern. The two faces of lattices in cryptology. In Joseph H. Silverman, editor, *CaLC*, volume 2146 of *Lecture Notes in Computer Science*, pages 146–180. Springer, 2001. 11.2.2

[NSA05] National Security Agency. The case for elliptic curve cryptography, 2005. http://www.nsa.gov/business/programs/ellipticcurve.shtml. 1.2.2, I

[NT11] Phong Q. Nguyen and Mehdi Tibouchi. Lattice-based fault attacks on signatures. In Marc Joye and Michael Tunstall, editors, *Fault Analysis in Cryptography*. Springer, 2011. To appear. 2.4.3

[P+09] Christof Paar et al. *COPACOBANA: A codebreaker for DES and other ciphers*, 2009. http://www.copacobana.org. 9.5.2

[Pee54] William D. Peeples, Jr. Elliptic curves and rational distance sets. *Proc. Am. Math. Soc.*, 5:29–33, 1954. 8.1.1

[PKCS#1 v1.5] Burton S. Kaliski et al. *PKCS#1: RSA Encryption Standard, Version 1.5*. RSA Laboratories, November 1993. 1.2.3, II, 9.1.1, 10.1.1, 12.1.1

[PKCS#1 v2.0] Burton S. Kaliski et al. *PKCS#1: RSA Encryption Standard, Version 2.0*. RSA Laboratories, September 1998. 12.1.1

[PKCS#1 v2.1] Burton S. Kaliski et al. *PKCS#1: RSA Encryption Standard, Version 2.1*. RSA Laboratories, June 2002. 1.2.3, 9.2, 11.1.3

[Poi05] David Pointcheval. Provable security for public key schemes. In *Contemporary cryptology*, Adv. Courses Math. CRM Barcelona, pages 133–190. Birkhäuser, Basel, 2005. 12.2.2

[Pou07] Vincent Pouget. Test et analyse par faisceau laser: Plateforme et applications. Technical report, Journée thématique du GDR SOCSIP, 2007. http://www.lirmm.fr/soc_sip/6fev/GCT_R1_Pouget.pdf. 11.5, 13.6

[PP99] Pascal Paillier and David Pointcheval. Efficient public-key cryptosystems provably secure against active adversaries. In Kwok-Yan Lam, Eiji Okamoto, and Chaoping Xing, editors, *ASIACRYPT*, volume 1716 of *Lecture Notes in Computer Science*, pages 165–179. Springer, 1999. 13.2

[PWGP03] Jan Pelzl, Thomas J. Wollinger, Jorge Guajardo, and Christof Paar. Hyperelliptic curve cryptosystems: Closing the performance gap to elliptic curves. In Colin D. Walter, Çetin Kaya Koç, and Christof Paar, editors, *CHES*, volume 2779 of *Lecture Notes in Computer Science*, pages 351–365. Springer, 2003. 3.5.3
[RAD78]
Ron L. Rivest, Leonard M. Adleman, and Michael L. Dertouzos. On data banks and privacy homomorphisms. In Richard A. DeMillo, editor, *Foundations of Secure Computation*, pages 169–180. Academic Press, 1978. 2.3.1

[Riv09]
Matthieu Rivain. Securing RSA against fault analysis by double addition chain exponentiation. In Marc Fischlin, editor, *CT-RSA*, volume 5473 of *Lecture Notes in Computer Science*, pages 459–480. Springer, 2009. 11.1.3

[Ros02]
Michael Rosen. *Number Theory in Function Fields*, volume 210 of *Graduate Texts in Mathematics*. Springer, 2002. 6.3

[RSA78]
Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. *Commun. ACM*, 21(2):120–126, 1978. 1.2.1, 1.2.2, II, 9.1.1, 11.1.1, 12.2.3

[RSR69]
Lawrence R. Rabiner, Ronald W. Schafer, and Charles M. Rader. The chirp z-transform algorithm and its application. *Bell System Tech. J.*, 48:1249–1292, 1969. 13.4

[RSS11]
Thomas Ristenpart, Hovav Shacham, and Thomas Shrimpton. Careful with composition: Limitations of the indifferentiability framework. In Kenneth G. Paterson, editor, *EUROCRYPT*, volume 6632 of *Lecture Notes in Computer Science*, pages 487–506. Springer, 2011. 2.1.3, 4, 3.4.1, 5.1.3, 5.2.1

[S+10a]
Nigel P. Smart et al. ECRYPT II yearly report on algorithms and key lengths. Technical report, European Network of Excellence in Cryptology II, March 2010. http://www.ecrypt.eu.org/documents/D.SPA.13.pdf. 1.1

[S+10b]
W.A. Stein et al. *Sage Mathematics Software (Version 4.4)*. The Sage Development Team, 2010. http://www.sagemath.org. 9.5.2, 11.2.4

[SA02]
Sergei P. Skorobogatov and Ross J. Anderson. Optical fault induction attacks. In Burton S. Kaliski Jr., Çetin Kaya Koç, and Christof Paar, editors, *CHES*, volume 2523 of *Lecture Notes in Computer Science*, pages 2–12. Springer, 2002. 11.A.1

[Sat09]
Takakazu Satoh. Generating genus two hyperelliptic curves over large characteristic finite fields. In Antoine Joux, editor, *EUROCRYPT*, volume 5479 of *Lecture Notes in Computer Science*, pages 536–553. Springer, 2009. 3.5.3, 3.5.4, 7.1.2, 7.2, 7.2

[Sch85]
René Schoof. Elliptic curves over finite fields and the computation of square roots mod $p$. *Math. Comp.*, 44(170):483–494, 1985. 2.1.1, 3.4.3
[Sei05] Jean-Pierre Seifert. On authenticated computing and RSA-based authentication. In Vijay Atluri, Catherine Meadows, and Ari Juels, editors, *ACM Conference on Computer and Communications Security*, pages 122–127. ACM, 2005. 11.1.1

[SH09] Hisayoshi Sato and Keisuke Hakuta. An efficient method of generating rational points on elliptic curves. *J. Math-for-Industry*, 1(A):33–44, 2009. 2.1.1, 3.5.1

[Sha73] Daniel Shanks. Five number-theoretic algorithms. In *Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972)*, pages 51–70. Congressus Numerantium, No. VII. Utilitas Math., 1973. 3.5.1

[Sha95] Adi Shamir. RSA for paranoids. *CryptoBytes Technical Newsletter*, 1(3):1–4, 1995. 2.2.6

[Sha99] Adi Shamir. Method and apparatus for protecting public key schemes from timing and fault attacks. US Patent #5,991,415, November 1999. Presented at the rump session of EUROCRYPT '97. 10.8

[Sho97] Victor Shoup. Lower bounds for discrete logarithms and related problems. In *EUROCRYPT*, pages 256–266, 1997. 2.1.7

[Sil86] Joseph H. Silverman. *The Arithmetic of Elliptic Curves*, volume 106 of *Graduate Texts in Mathematics*, chapter III. Springer-Verlag, 1986. 8.1

[Ska05] Mariusz Skałba. Points on elliptic curves over finite fields. *Acta Arith.*, 117:293–301, 2005. 2.1.1, 3.5.1, 3.2

[SS04] Andrejz Schinzel and Mariusz Skałba. On equations $y^2 = x^n + k$ in a finite field. *Bull. Pol. Acad. Sci. Math.*, 52(3):223–226, 2004. 3.4.3, 3.1, 3.5.1

[SS10] Damien Stehlé and Ron Steinfeld. Faster fully homomorphic encryption. In Masayuki Abe, editor, *ASIACRYPT*, volume 6477 of *Lecture Notes in Computer Science*, pages 377–394. Springer, 2010. 2.3.1

[SV07] Nigel P. Smart and Frederik Vercauteren. On computable isomorphisms in efficient asymmetric pairing-based systems. *Discrete Applied Mathematics*, 155(4):538–547, 2007. 2

[SV10] Nigel P. Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. In Phong Q. Nguyen and David Pointcheval, editors, *Public Key Cryptography*, volume 6056 of *Lecture Notes in Computer Science*, pages 420–443. Springer, 2010. 2.3.1
[SvdW06] Andrew Shallue and Christiaan van de Woestijne. Construction of rational points on elliptic curves over finite fields. In Florian Hess, Sebastian Pauli, and Michael E. Pohst, editors, *ANTS*, volume 4076 of *Lecture Notes in Computer Science*, pages 510–524. Springer, 2006. 2.1.1, 3.5.1, 3.5.4, 4.1, 6.1.1, 7.3.2

[Tib11] Mehdi Tibouchi. A Nagell algorithm in any characteristic. In David Naccache, editor, *Festschrift Jean-Jacques Quisquater*, volume 6805 of *Lecture Notes in Computer Science*. Springer, 2011. To appear. 2.4.3

[Ula07] Maciej Ulas. Rational points on certain hyperelliptic curves over finite fields. *Bull. Pol. Acad. Sci. Math.*, 55(2):97–104, 2007. 2.1.1, 3.5.1, 3.3, 3.5.3, 4.5, 6.1.1, 7.1.1

[vDGHV10] Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In Henri Gilbert, editor, *EUROCRYPT*, volume 6110 of *Lecture Notes in Computer Science*, pages 24–43. Springer, 2010. 2.3.1

[Vig08] David Vigilant. RSA with CRT: A new cost-effective solution to thwart fault attacks. In Elisabeth Oswald and Pankaj Rohatgi, editors, *CHES*, volume 5154 of *Lecture Notes in Computer Science*, pages 130–145. Springer, 2008. 11.1.3

[Wei95] André Weil. *Basic number theory*. Classics in Mathematics. Springer-Verlag, Berlin, 1995. Reprint of the second (1973) edition. 2.1.4, 6.1.2, 6.3

[WF10] Hongfeng Wu and Rongquan Feng. Elliptic curves in Huff’s model. Cryptology ePrint Archive, Report 2010/390, 2010. http://eprint.iacr.org/. 8.5

[Wie90] Michael J. Wiener. Cryptanalysis of short RSA secret exponents. *IEEE Transactions on Information Theory*, 36(3):553–558, 1990. II

[ZK02] Fangguo Zhang and Kwangjo Kim. ID-based blind signature and ring signature from pairings. In Yuliang Zheng, editor, *ASIACRYPT*, volume 2501 of *Lecture Notes in Computer Science*, pages 533–547. Springer, 2002. 3.1.1, 5.1.1