密码学中的计算假设.pdf-资料库

ryosai-9628042-16359647630622513432.pdf-第1页.png

第1页 / 共55页

ryosai-9628042-16359647630622513432.pdf-第2页.png

第2页 / 共55页

ryosai-9628042-16359647630622513432.pdf-第3页.png

第3页 / 共55页

ryosai-9628042-16359647630622513432.pdf-第4页.png

第4页 / 共55页

ryosai-9628042-16359647630622513432.pdf-第5页.png

第5页 / 共55页

ryosai-9628042-16359647630622513432.pdf-第6页.png

第6页 / 共55页

ryosai-9628042-16359647630622513432.pdf-第7页.png

第7页 / 共55页

ryosai-9628042-16359647630622513432.pdf-第8页.png

第8页 / 共55页

ICT-2007-216676 ECRYPT II European Network of Excellence in Cryptology II Network of Excellence Information and Communication Technologies Main Computational Assumptions in Cryptography D.MAYA.3 Due date of deliverable: 1 February 2010 Actual submission date: 29 April 2010 Start date of project: 1 August 2008 Duration: 4 years Lead contractor: Katholieke Universiteit Leuven (KUL) Revision 1.0 Project co-funded by the European Commission within the 7th Framework Programme Dissemination Level PU Public PP Restricted to other programme participants (including the Commission services) RE Restricted to a group speciﬁed by the consortium (including the Commission services) CO Conﬁdential, only for members of the consortium (including the Commission services) X ECRYPT IIECRYPT II

Main Computational Assumptions in Cryptography Editor Fr´e Vercauteren (K.U.Leuven) Contributors Naomi Benger (Shannon Institute), Dario Catalano (UNICT), Manuel Charlemagne (Shannon Institute), David Conti (Shannon Institute), Biljana Cubaleska (RUB), Hernando Fernando (Shannon Institute), Dario Fiore (UNICT), Steven Galbraith (RHUL), David Galindo (Uni.Lu), Jens Hermans (K.U.Leuven), Vincenzo Iovino (UNISA), Tibor Jager (RUB), Markulf Kohlweiss (K.U.Leuven), Benoit Libert (UCL), Richard Lindner (TUD), Hans Loehr (RUB), Danny Lynch (Shannon Institute), Richard Moloney (Shannon Institute), Khaled Ouaﬁ (EPFL), Benny Pinkas (University of Haifa), Frantisek Polach (Shannon Institute), Mario Di Raimondo (UNICT), Markus R¨uckert (TUD), Michael Schneider (TUD), Vijay Singh (Shannon Institute), Nigel Smart (UNIVBRIS), Martijn Stam (EPFL), Fr´e Vercauteren (K.U.Leuven), Jorge Villar Santos (UPC), Steve Williams (UNIVBRIS) 29 April 2010 Revision 1.0 The work described in this report has in part been supported by the Commission of the European Com- munities through the ICT program under contract ICT-2007-216676. The information in this document is provided as is, and no warranty is given or implied that the information is ﬁt for any particular purpose. The user thereof uses the information at its sole risk and liability.

Contents 1 Introduction 2 Discrete logarithm problem 1. DLP: discrete logarithm problem . . . . . . . . . . . . . . . . . . . . . . . 2. CDH: computational Diﬃe-Hellman problem . . . . . . . . . . . . . . . . 3. SDH: static Diﬃe-Hellman problem . . . . . . . . . . . . . . . . . . . . . . 4. gap-CDH: Gap Diﬃe-Hellman problem . . . . . . . . . . . . . . . . . . . . 5. DDH: decision Diﬃe-Hellman problem . . . . . . . . . . . . . . . . . . . . 6. Strong-DDH: strong decision Diﬃe-Hellman problem . . . . . . . . . . . . 7. sDDH: skewed decision Diﬃe-Hellman problem . . . . . . . . . . . . . . . 8. PDDH: parallel decision Diﬃe-Hellman problem . . . . . . . . . . . . . . 9. Square-DH: Square Diﬃe-Hellman problem . . . . . . . . . . . . . . . . . 10. l-DHI: l-Diﬃe-Hellman inversion problem . . . . . . . . . . . . . . . . . . 11. l-DDHI: l-Decisional Diﬃe-Hellman inversion problem . . . . . . . . . . 12. REPRESENTATION: Representation problem . . . . . . . . . . . . . . . 13. LRSW: LRSW Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 14. Linear: Linear problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15. D-Linear1: Decision Linear problem (version 1) . . . . . . . . . . . . . . 16. l-SDH: l-Strong Diﬃe-Hellman problem . . . . . . . . . . . . . . . . . . . 17. c-DLSE: Discrete Logarithm with Short Exponents . . . . . . . . . . . . 18. CONF: (conference-key sharing scheme) . . . . . . . . . . . . . . . . . . 19. 3PASS: 3-Pass Message Transmission Scheme . . . . . . . . . . . . . . . 20. LUCAS: Lucas Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 21. XLP: x-Logarithm Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 22. MDHP: Matching Diﬃe-Hellman Problem . . . . . . . . . . . . . . . . . 23. DDLP: Double Discrete Logarithm Problem . . . . . . . . . . . . . . . . 24. rootDLP: Root of Discrete Logarithm Problem . . . . . . . . . . . . . . . 25. n-M-DDH: Multiple Decision Diﬃe-Hellman Problem . . . . . . . . . . . 26. l-HENSEL-DLP: l-Hensel Discrete Logarithm Problem . . . . . . . . . . i 2 3 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 9 9 9 10 10 10 11 11

ii 27. DLP(Inn(G)): Discrete Logarithm Problem over Inner Automorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Group 28. IE: Inverse Exponent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29. TDH: The Twin Diﬃe-Hellman Assumption . . . . . . . . . . . . . . . . 30. XTR-DL: XTR discrete logarithm problem . . . . . . . . . . . . . . . . . 31. XTR-DH: XTR Diﬃe-Hellman problem . . . . . . . . . . . . . . . . . . . 32. XTR-DHD: XTR decision Diﬃe-Hellman problem . . . . . . . . . . . . . 33. CL-DLP: discrete logarithms in class groups of imaginary quadratic orders 34. TV-DDH: Tzeng Variant Decision Diﬃe-Hellman problem . . . . . . . . 35. n-DHE: n-Diﬃe-Hellman Exponent problem . . . . . . . . . . . . . . . . 3 Factoring 36. FACTORING: integer factorisation problem . . . . . . . . . . . . . . . . 37. SQRT: square roots modulo a composite . . . . . . . . . . . . . . . . . . 38. CHARACTERd: character problem . . . . . . . . . . . . . . . . . . . . . 39. MOVAd: character problem . . . . . . . . . . . . . . . . . . . . . . . . . 40. CYCLOFACTd: factorisation in Z[θ] 41. FERMATd: factorisation in Z[θ] 42. RSAP: RSA problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43. Strong-RSAP: strong RSA problem . . . . . . . . . . . . . . . . . . . . . 44. Diﬀerence-RSAP: Diﬀerence RSA problem . . . . . . . . . . . . . . . . . 45. Partial-DL-ZN2P: Partial Discrete Logarithm problem in Z∗ 46. DDH-ZN2P: Decision Diﬃe-Hellman problem over Z∗ 47. Lift-DH-ZN2P: Lift Diﬃe-Hellman problem over Z∗ 48. EPHP: Election Privacy Homomorphism problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . n2 n2 n2 49. AERP: Approximate e-th root problem . . . . . . . . . . . . . . . . . . . 50. l-HENSEL-RSAP: l-Hensel RSA . . . . . . . . . . . . . . . . . . . . . . . 51. DSeRP: Decisional Small e-Residues in Z∗ 52. DS2eRP: Decisional Small 2e-Residues in Z∗ 53. DSmallRSAKP: Decisional Reciprocal RSA-Paillier in Z∗ 54. HRP: Higher Residuosity Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . n2 n2 n2 11 12 12 13 13 13 13 14 14 15 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 21 21

55. ECSQRT: Square roots in elliptic curve groups over Z/nZ . . . . . . . . 56. RFP: Root Finding Problem . . . . . . . . . . . . . . . . . . . . . . . . . 57. phiA: PHI-Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58. C-DRSA: Computational Dependent-RSA problem . . . . . . . . . . . . 59. D-DRSA: Decisional Dependent-RSA problem . . . . . . . . . . . . . . . 60. E-DRSA: Extraction Dependent-RSA problem . . . . . . . . . . . . . . . 61. DCR: Decisional Composite Residuosity problem . . . . . . . . . . . . . 62. CRC: Composite Residuosity Class problem . . . . . . . . . . . . . . . . 63. DCRC: Decisional Composite Residuosity Class problem . . . . . . . . . 64. GenBBS: generalised Blum-Blum-Shub assumption . . . . . . . . . . . . 4 Product groups 65. co-CDH: co-Computational Diﬃe-Hellman Problem . . . . . . . . . . . . 66. XDDH: External Decision Diﬃe-Hellman Problem . . . . . . . . . . . . . 67. D-Linear2: Decision Linear Problem (version 2) . . . . . . . . . . . . . . 68. FSDH: Flexible Square Diﬃe-Hellman Problem . . . . . . . . . . . . . . 69. KSW1: Assumption 1 of Katz-Sahai-Waters . . . . . . . . . . . . . . . . 5 Pairings 70. BDHP: Bilinear Diﬃe-Hellman Problem . . . . . . . . . . . . . . . . . . 71. DBDH: Decision Bilinear Diﬃe-Hellman problem . . . . . . . . . . . . . 72. l-BDHI: l-Bilinear Diﬃe-Hellman Inversion Problem . . . . . . . . . . . . 73. l-DBDHI: l-Bilinear Decision Diﬃe-Hellman Inversion Problem . . . . . 74. l-wBDHI: l-weak Bilinear Diﬃe-Hellman Inversion Problem . . . . . . . 75. l-wDBDHI: l-weak Decisional Bilinear Diﬃe-Hellman Inversion Problem 76. KSW2: Assumption 2 of Katz-Sahai-Waters . . . . . . . . . . . . . . . . 77. MSEDH: Multi-sequence of Exponents Diﬃe-Hellman Assumption . . . . 6 Lattices 6.1 Main Lattice Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78. SVPγ 79. CVPp p: (Approximate) Shortest vector problem . . . . . . . . . . . . . . γ: (Approximate) Closest vector problem . . . . . . . . . . . . . . . iii 22 22 22 23 23 23 23 24 24 24 25 25 25 26 26 27 27 27 28 29 29 30 30 31 31 32 32 32 32

iv 80. GapSVPp γ: Decisional shortest vector problem . . . . . . . . . . . . . . . γ: Decisional closest vector problem . . . . . . . . . . . . . . . . 6.2 Modular Lattice Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81. GapCVPp 82. SISp(n, m, q, β): Short integer solution problem . . . . . . . . . . . . . . 83. ISISp(n, m, q, β): Inhomogeneous short integer solution problem . . . . . 6.3 Miscellaneous Lattice Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 84. USVPp(n, γ): Approximate unique shortest vector problem . . . . . . . . 85. SBPp(n, γ): Approximate shortest basis problem . . . . . . . . . . . . . . 86. SLPp(n, γ): Approximate shortest length problem . . . . . . . . . . . . . 87. SIVPp(n, γ): Approximate shortest independent vector problem . . . . . 88. hermiteSVP: Hermite shortest vector problem . . . . . . . . . . . . . . . 89. CRP: Covering radius problem . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Ideal Lattice Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90. 91. Ideal-SISf,p Ideal-SVPf,p γ : (Approximate) Ideal shortest vector problem / Shortest polynomial problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . q,m,β: Ideal small integer solution problem . . . . . . . . . . . . 7 Miscellaneous Problems 92. KEA1: Knowledge of Exponent assumption . . . . . . . . . . . . . . . . 93. MQ: Multivariable Quadratic equations . . . . . . . . . . . . . . . . . . . 94. CF: Given-weight codeword ﬁnding . . . . . . . . . . . . . . . . . . . . . 95. ConjSP: Braid group conjugacy search problem . . . . . . . . . . . . . . 96. GenConjSP: Generalised braid group conjugacy search problem . . . . . 97. ConjDecomP: Braid group conjugacy decomposition problem . . . . . . . 98. ConjDP: Braid group conjugacy decision problem . . . . . . . . . . . . . 99. DHCP: Braid group decisional Diﬃe-Hellman-type conjugacy problem . 100. ConjSearch: (multiple simlutaneous) Braid group conjugacy search prob- lem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101. SubConjSearch: subgroup restricted Braid group conjugacy search prob- lem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102. LINPOLY : A linear algebra problem on polynomials . . . . . . . . . . 103. HFE-DP: Hidden Field Equations Decomposition Problem . . . . . . . 33 33 34 34 34 35 35 35 35 36 36 37 37 37 38 38 38 39 39 39 40 40 40 41 41 42 42 43

资料库

密码学中的计算假设.pdf

相关推荐

安全技术

热门标签

最新资料