IEEE 1363.1 : 2008

PUBLIC KEY CRYPTOGRAPHIC TECHNIQUES BASED ON HARD PROBLEMS OVER LATTICES

Institute of Electrical & Electronics Engineers

More details

More info

1 Overview
  1.1 Scope
  1.2 Purpose
2 Normative references
3 Definitions, acronyms, and abbreviations
  3.1 Definitions
  3.2 Acronyms and abbreviations
4 Types of cryptographic techniques
  4.1 General model
  4.2 Schemes
  4.3 Additional methods
  4.4 Algorithm specification conventions
5 Mathematical notation
6 Polynomial representation and operations
  6.1 Introduction
  6.2 Polynomial representation
  6.3 Polynomial operations
      6.3.1 Polynomial multiplication
      6.3.2 Reduction of a polynomial mod q
      6.3.3 Inversion in (Z/qZ)[X]/(X[N] - 1)
7 Data types and conversions
  7.1 Bit strings and octet strings
  7.2 Converting between integers and bit strings (I2BSP and BS2IP)
      7.2.1 Integer to bit string primitive (I2BSP)
      7.2.2 Bit string to integer primitive (BS2IP)
  7.3 Converting between integers and octet strings (I2OSP
      and OS2IP)
      7.3.1 Integer to octet string primitive (I2OSP)
      7.3.2 Octet string to integer primitive (OS2IP)
  7.4 Converting between bit strings and right-padded octet
      strings (BS2ROSP and ROS2BSP)
      7.4.1 Bit string to right-padded octet string primitive
            (BS2ROSP)
      7.4.2 Right-padded octet string to bit string primitive
            (ROS2BSP)
  7.5 Converting between ring elements and bit strings
      (RE2BSP and BS2REP)
      7.5.1 Ring element to bit string primitive (RE2BSP)
      7.5.2 Bit string to ring element primitive (BS2REP)
  7.6 Converting between ring elements and octet strings
      (RE2OSP and OS2REP)
      7.6.1 Ring element to octet string primitive (RE2OSP)
      7.6.2 Octet string to ring element primitive (OS2REP)
8 Supporting algorithms
  8.1 Overview
  8.2 Hash functions
  8.3 Encoding methods
      8.3.1 General
      8.3.2 Blinding polynomial generation methods (BPGM)
  8.4 Supporting algorithms
      8.4.1 Mask generation functions
      8.4.2 Index generation function
9 Short vector encryption scheme (SVES)
  9.1 Encryption scheme (SVES) overview
  9.2 Encryption scheme (SVES) operations
      9.2.1 Key generation
      9.2.2 Encryption operation
      9.2.3 Decryption operation
      9.2.4 Key pair validation methods
      9.2.5 Public key validation
Annex A (informative) Security considerations
      A.1 Lattice security: background
          A.1.1 Lattice definitions
          A.1.2 Hard lattice problems
          A.1.3 Theoretical complexity of hard lattice problems
          A.1.4 Lattice reduction algorithms
          A.1.5 The Gaussian heuristic and the closest vector
                 problem
          A.1.6 Modular lattices: definition
          A.1.7 Modular lattices and quotient polynomial rings
          A.1.8 Balancing CVP in modular lattices
          A.1.9 Fundamental CVP ratios in modular lattices
          A.1.10 Creating a balanced CVP for modular lattices
                 containing a short vector
          A.1.11 Modular lattices containing (short) binary vectors
          A.1.12 Convolution modular lattices
          A.1.13 Heuristic solution time for CVP in modular lattices
          A.1.14 Zero-forcing
      A.2 Experimental solution times for NTRU lattices - full
          key recovery
          A.2.1 Experimental solution times for NTRU lattices
                using BKZ reduction
          A.2.2 Alternative target vectors
      A.3 Combined lattice and combinatorial attacks on LBP-PKE
          keys and messages
          A.3.1 Overview
          A.3.2 Lattice strength
          A.3.3 Reduced lattices and the "cliff"
          A.3.4 Combinatorial strength
          A.3.5 Summary
      A.4 Other security considerations for LBP-PKE encryption
          A.4.1 Entropy requirements for key and salt generation
          A.4.2 Reduction mod q
          A.4.3 Selection of N
          A.4.4 Relationship between q and N
          A.4.5 Form of q
          A.4.6 Leakage of m'(1)
          A.4.7 Relationship between p, q, and N
          A.4.8 Adaptive chosen ciphertext attacks
          A.4.9 Invertibility of g in R[q]
          A.4.10 Decryption failures
          A.4.11 OID
          A.4.12 Use of hash functions by supporting functions
          A.4.13 Generating random numbers in [0, N - 1]
          A.4.14 Attacks based on variation in decryption times
          A.4.15 Choosing to attack r or m
          A.4.16 Quantum computers
          A.4.17 Other considerations
      A.5 A parameter set generation algorithm
      A.6 Possible parameter sets
          A.6.1 Size-optimized
          A.6.2 Cost-optimized
          A.6.3 Speed-optimized
      A.7 Security levels of parameter sets
          A.7.1 Assumed security levels versus current knowledge
          A.7.2 Potential research
Annex B (informative) Bibliography

Abstract

Presents specifications of common public key cryptographic techniques based on hard problems over lattices supplemental to those considered in IEEE Std 1363[TM]-2000 and IEEE Std 1363a[TM]-2004, including mathematical primitives for secret value (key) derivation, public key encryption, identification and digital signatures, and cryptographic schemes based on those primitives.