1、IEEE Std 1363.1-2008IEEE Standard Specification for PublicKey Cryptographic Techniques Basedon Hard Problems over Lattices IEEE3 Park Avenue New York, NY 10016-5997, USA10 March 2009IEEE Computer SocietySponsored by theMicroprocessor Standards Committee 1363.1TMIEEE Standard Specification for Public
2、 Key Cryptographic Techniques Based on Hard Problems over Lattices Sponsor Microprocessors and Microcomputers Committee of the IEEE Computer Society Approved 10 December 2008 IEEE-SA Standards Board Abstract: Specifications of common public key cryptographic techniques based on hard problems over la
3、ttices supplemental to those considered in IEEE Std 1363-2000 and IEEE Std 1363a-2004, including mathematical primitives for secret value (key) derivation, public key encryption, identification and digital signatures, and cryptographic schemes based on those primitives are provided. Also presented a
4、re specifications of related cryptographic parameters, public keys, and private keys. Class of computer and communications systems is not restricted. Keywords: encryption, lattice-based cryptography, public key cryptography The Institute of Electrical and Electronics Engineers, Inc. 3 Park Avenue, N
5、ew York, NY 10016-5997, USA Copyright 2009 by the Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Published 10 March 2009. Printed in the United States of America. IEEE is a registered trademark in the U.S. Patent +1 978 750 8400. Permission to photocopy portions of any
6、individual standard for educational classroom use can also be obtained through the Copyright Clearance Center. iv Copyright 2009 IEEE. All rights reserved. Introduction This introduction is not part of IEEE Std 1363.1-2008, IEEE Standard Specification for Public Key Cryptographic Techniques Based on
7、 Hard Problems over Lattices. The IEEE P1363 project started as the “Standard for Rivest-Shamir-Adleman, Diffie-Hellman, and Related Public Key Cryptography” with its first meeting in January 1994, following a strategic initiative by the Microprocessor Standards Committee to develop standards for cr
8、yptography. Over the next eight years, the working group produced a broad standard reflecting the state of the art in public key cryptography, including techniques from three major families of hard problems. In addition, the working group drafted an addendum that provides additional techniques from
9、those three major families. A more thorough history of the IEEE P1363 working group and its contributions beyond IEEE Std 1363-2000 are given in the Introduction to IEEE Std 1363-2000. At the same time, new cryptographic research was producing additional families of cryptographic techniques such as
10、the family of techniques based on hard problems over lattices. These techniques enjoy operating characteristics that make them attractive in certain implementation environments, and thus they have received considerable scrutiny and deployment. As a result, the working group proposed a new project to
11、 standardize techniques from this family. This project was approved by the Microprocessors and Microcomputers Standards Committee, and this current standard is the result of this project. Notice to users Laws and regulations Users of these documents should consult all applicable laws and regulations
12、. Compliance with the provisions of this standard does not imply compliance to any applicable regulatory requirements. Implementers of the standard are responsible for observing or referring to the applicable regulatory requirements. IEEE does not, by the publication of its standards, intend to urge
13、 action that is not in compliance with applicable laws, and these documents may not be construed as doing so. Copyrights This document is copyrighted by the IEEE. It is made available for a wide variety of both public and private uses. These include both use, by reference, in laws and regulations, a
14、nd use in private self-regulation, standardization, and the promotion of engineering practices and methods. By making this document available for use and adoption by public authorities and private users, the IEEE does not waive any rights in copyright to this document. v Copyright 2009 IEEE. All rig
15、hts reserved. Updating of IEEE documents Users of IEEE standards should be aware that these documents may be superseded at any time by the issuance of new editions or may be amended from time to time through the issuance of amendments, corrigenda, or errata. An official IEEE document at any point in
16、 time consists of the current edition of the document together with any amendments, corrigenda, or errata then in effect. In order to determine whether a given document is the current edition and whether it has been amended through the issuance of amendments, corrigenda, or errata, visit the IEEE St
17、andards Association web site at http:/ieeexplore.ieee.org/xpl/standards.jsp, or contact the IEEE at the address listed previously. For more information about the IEEE Standards Association or the IEEE standards development process, visit the IEEE-SA web site at http:/standards.ieee.org. Errata Errat
18、a, if any, for this and all other standards can be accessed at the following URL: http:/standards.ieee.org/reading/ieee/updates/errata/index.html. Users are encouraged to check this URL for errata periodically. Interpretations Current interpretations can be accessed at the following URL: http:/stand
19、ards.ieee.org/reading/ieee/interp/ index.html. Patents Attention is called to the possibility that implementation of this standard may require use of subject matter covered by patent rights. By publication of this standard, no position is taken with respect to the existence or validity of any patent
20、 rights in connection therewith. The IEEE is not responsible for identifying Essential Patent Claims for which a license may be required, for conducting inquiries into the legal validity or scope of Patents Claims or determining whether any licensing terms or conditions provided in connection with s
21、ubmission of a Letter of Assurance, if any, or in any licensing agreements are reasonable or non-discriminatory. Users of this standard are expressly advised that determination of the validity of any patent rights, and the risk of infringement of such rights, is entirely their own responsibility. Fu
22、rther information may be obtained from the IEEE Standards Association. Participants At the time this standard was submitted to the IEEE-SA Standards Board for approval, the P1363 Working Group had the following membership: William Whyte, Chair Don Johnson, Vice Chair Matthew Ball Xavier Boyen Mike B
23、renner Daniel Brown Mark Chimley Andy Dancer David Jablon Satoru Kanno David Kravitz Michael Markowitz Luther Martin Jim Randall Roger Schlafly Ari Singer Terence Spies Yongge Wang IEEE Std 1363.1- 2008 IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over L
24、attices vi Copyright 2009 IEEE. All rights reserved. The following members of the individual balloting committee voted on this standard. Balloters may have voted for approval, disapproval, or abstention. Ed Addario Butch Anton Matthew Ball H. Stephen Berger Martin J. Bishop Juan Carreon Keith Chow K
25、evin Coggins Geoffrey Darnton James Davis Thomas Dineen Andrew Fieldsend Michael Geipel Randall Groves Werner Hoelzl Atsushi Ito Mark Jaeger Susan Land David J. Leciston Daniel Lindberg Edward McCall Avygdor Moise Michael S. Newman Ulrich Pohl Robert Robinson Randall Safier Bartien Sayogo Thomas Sta
26、rai Walter Struppler Gerald Stueve Mark Sturza Vincent Tume William Whyte Paul Work Oren Yuen Wenhao Zhu When the IEEE-SA Standards Board approved this standard on 10 December 2008, it had the following membership: Robert M. Grow, Chair Thomas Prevost, Vice Chair Steve M. Mills, Past Chair Judith Go
27、rman, Secretary Victor Berman Richard DeBlasio Andy Drozd Mark Epstein Alexander Gelman William R. Goldbach Arnold M. Greenspan Kenneth S. Hanus Jim Hughes Richard H. Hulett Young Kyun Kim Joseph Koepfinger* John Kulick David J. Law Glenn Parsons Ronald C. Petersen Chuck Powers Narayanan Ramachandra
28、n Jon Walter Rosdahl Robby Robson Anne-Marie Sahazizia Malcolm V. Thaden Howard L. Wolfman Don Wright *Member Emeritus Also included are the following nonvoting IEEE-SA Standards Board liaisons: Satish K. Aggarwal, NRC Representative Michael Janezic, NIST Representative Don Messina IEEE Standards Pr
29、ogram Manager, Document Development Malia Zaman IEEE Standards Program Manager, Technical Program Development vii Copyright 2009 IEEE. All rights reserved. Contents 1. Overview 1 1.1 Scope . 1 1.2 Purpose 1 2. Normative references 2 3. Definitions, acronyms, and abbreviations 2 3.1 Definitions . 2 3
30、.2 Acronyms and abbreviations . 9 4. Types of cryptographic techniques. 11 4.1 General model 11 4.2 Schemes. 11 4.3 Additional methods 12 4.4 Algorithm specification conventions. 12 5. Mathematical notation 13 6. Polynomial representation and operations 15 6.1 Introduction . 15 6.2 Polynomial repres
31、entation . 15 6.3 Polynomial operations . 15 6.3.1 Polynomial multiplication 15 6.3.2 Reduction of a polynomial mod q 15 6.3.3 Inversion in (Z/qZ)X/(XN 1) 15 7. Data types and conversions 18 7.1 Bit strings and octet strings 18 7.2 Converting between integers and bit strings (I2BSP and BS2IP) 18 7.2
32、.1 Integer to bit string primitive (I2BSP) . 18 7.2.2 Bit string to integer primitive (BS2IP). 19 7.3 Converting between integers and octet strings (I2OSP and OS2IP) 19 7.3.1 Integer to octet string primitive (I2OSP) 19 7.3.2 Octet string to integer primitive (OS2IP). 19 7.4 Converting between bit s
33、trings and right-padded octet strings (BS2ROSP and ROS2BSP). 20 7.4.1 Bit string to right-padded octet string primitive (BS2ROSP) 20 7.4.2 Right-padded octet string to bit string primitive (ROS2BSP) 20 7.5 Converting between ring elements and bit strings (RE2BSP and BS2REP) . 21 7.5.1 Ring element t
34、o bit string primitive (RE2BSP) 21 7.5.2 Bit string to ring element primitive (BS2REP) 21 7.6 Converting between ring elements and octet strings (RE2OSP and OS2REP) . 22 7.6.1 Ring element to octet string primitive (RE2OSP) 22 7.6.2 Octet string to ring element primitive (OS2REP) 22 8. Supporting al
35、gorithms 22 8.1 Overview . 22 8.2 Hash functions . 23 8.3 Encoding methods . 23 8.3.1 General. 23 8.3.2 Blinding polynomial generation methods (BPGM) . 23 8.4 Supporting algorithms . 24 8.4.1 Mask generation functions. 24 8.4.2 Index generation function 25 9. Short vector encryption scheme (SVES) 28
36、 9.1 Encryption scheme (SVES) overview . 28 9.2 Encryption scheme (SVES) operations 28 9.2.1 Key generation. 28 9.2.2 Encryption operation 29 9.2.3 Decryption operation 31 9.2.4 Key pair validation methods 33 9.2.5 Public key validation 33 viii Copyright 2009 IEEE. All rights reserved. Annex A (info
37、rmative) Security considerations . 35 A.1 Lattice security: background. 35 A.1.1 Lattice definitions . 35 A.1.2 Hard lattice problems 36 A.1.3 Theoretical complexity of hard lattice problems. 36 A.1.4 Lattice reduction algorithms 36 A.1.5 The Gaussian heuristic and the closest vector problem. 37 A.1
38、.6 Modular lattices: definition . 38 A.1.7 Modular lattices and quotient polynomial rings 38 A.1.8 Balancing CVP in modular lattices . 38 A.1.9 Fundamental CVP ratios in modular lattices. 39 A.1.10 Creating a balanced CVP for modular lattices containing a short vector 39 A.1.11 Modular lattices cont
39、aining (short) binary vectors 40 A.1.12 Convolution modular lattices 41 A.1.13 Heuristic solution time for CVP in modular lattices . 41 A.1.14 Zero-forcing 42 A.2 Experimental solution times for NTRU latticesfull key recovery. 42 A.2.1 Experimental solution times for NTRU lattices using BKZ reductio
40、n 42 A.2.2 Alternative target vectors 44 A.3 Combined lattice and combinatorial attacks on LBP-PKE keys and messages 44 A.3.1 Overview. 44 A.3.2 Lattice strength 44 A.3.3 Reduced lattices and the “cliff”. 45 A.3.4 Combinatorial strength 48 A.3.5 Summary . 50 A.4 Other security considerations for LBP
41、-PKE encryption. 50 A.4.1 Entropy requirements for key and salt generation. 50 A.4.2 Reduction mod q . 50 A.4.3 Selection of N 50 A.4.4 Relationship between q and N. 50 A.4.5 Form of q. 50 A.4.6 Leakage of m(1). 51 A.4.7 Relationship between p, q, and N 51 A.4.8 Adaptive chosen ciphertext attacks. 5
42、1 A.4.9 Invertibility of g in Rq. 52 A.4.10 Decryption failures 52 A.4.11 OID . 52 A.4.12 Use of hash functions by supporting functions . 53 A.4.13 Generating random numbers in 0, N 1. 53 A.4.14 Attacks based on variation in decryption times. 53 A.4.15 Choosing to attack r or m 54 A.4.16 Quantum com
43、puters 54 A.4.17 Other considerations 54 A.5 A parameter set generation algorithm. 54 A.6 Possible parameter sets . 55 A.6.1 Size-optimized 55 A.6.2 Cost-optimized 57 A.6.3 Speed-optimized 60 A.7 Security levels of parameter sets. 62 A.7.1 Assumed security levels versus current knowledge 62 A.7.2 Po
44、tential research 63 Annex B (informative) Bibliography 64 1 Copyright 2009 IEEE. All rights reserved. IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices IMPORTANT NOTICE: This standard is not intended to ensure safety, security, health, or enviro
45、nmental protection in all circumstances. Implementers of the standard are responsible for determining appropriate safety, security, environmental, and health practices or regulatory requirements. This IEEE document is made available for use subject to important notices and legal disclaimers. These n
46、otices and disclaimers appear in all publications containing this document and may be found under the heading “Important Notice” or “Important Notices and Disclaimers Concerning IEEE Documents.” They can also be obtained on request from IEEE or viewed at http:/standards.ieee.org/IPR/disclaimers.html
47、. 1. Overview 1.1 Scope This standard provides specifications of common public key cryptographic techniques based on hard problems over lattices supplemental to those considered in IEEE Std 1363-2000 B471and IEEE Std 1363a-2004 B48, including mathematical primitives for secret value (key) derivation
48、, public key encryption, identification and digital signatures, and cryptographic schemes based on those primitives. Specifications of related cryptographic parameters, public keys, and private keys are also presented. Class of computer and communications systems is not restricted. 1.2 Purpose The t
49、ransition from paper to electronic media brings with it the need for electronic privacy and authenticity. Public key cryptography offers fundamental technology addressing this need. Many alternative public key techniques have been proposed, each with its own benefits. IEEE Std 1363-2000 B47 and IEEE Std 1363a-2004 B48 have produced a comprehensive reference defining a range of common public key 1The numbers in brackets correspond to those of the bibliography in Annex B. IEEE Std 1363.1- 2008 IEEE Standard Specification for Public Key Cryptographic
