Patent ID: 11888968
Assignee: NIPPON TELEGRAPH AND TELEPHONE CORPORATION
Field: Digital communication (Electrical engineering)
Classification: CPC G  H | IPC G  H

Claim 8:
9. The verification device according to claim 8,
wherein the signature is sig indicated in Formula 5, and
wherein the verification data is c indicated in formula 6, sig
      =
      
       (
       
        
         s
         
          *
          
           (
           0
           )
          
         
        
        ,
        …
          
        ,
        
         s
         
          *
          
           (
           
            m
            +
            1
           
           )
          
         
        
       
       )
      
     
    
   
   
    
     [
     
      Formula
      ⁢
         
      5
     
     ]
    
   
  
 

 
  	
  where
 

 
  	
  
   
    
     s
     
      *
      
       (
       0
       )
      
     
    
    =
    
     
      ξ
      ⁢
      
       k
       
        *
        
         (
         0
         )
        
       
      
     
     +
     
      r
      
       *
       
        (
        0
        )
       
      
     
    
   
   ,
  
 

 
  
   
    s
    
     *
     
      (
      j
      )
     
    
   
   =
   
    
     
      
       ξΩ
       j
      
      ⁢
      
       k
       
        *
        
         (
         
          ρ
          ⁡
          (
          j
          )
         
         )
        
       
      
     
     +
     
      
       σ
       j
       ′
      
      (
      
       
        b
        
         *
         
          (
          
           1
           ,
           1
          
          )
         
        
       
       +
       
        
         ρ
         ⁡
         (
         j
         )
        
        ⁢
        
         b
         
          *
          
           (
           
            1
            ,
            2
           
           )
          
         
        
       
      
      )
     
     +
     
      
       Ω
       j
       ″
      
      ⁢
      
       b
       
        *
        
         (
         
          1
          ,
          3
         
         )
        
       
      
     
     +
     
      
       Ω
       j
       ′
      
      ⁢
      
       b
       
        *
        
         (
         
          1
          ,
          4
         
         )
        
       
      
     
     +
     
      
       r
       
        *
        
         (
         j
         )
        
       
      
      ⁢
         
      for
      ⁢
         
      j
     
    
    ∈
    
     [
     m
     ]
    
   
  
  ,
 

 
  	
  
   
    
     s
     
      *
      
       (
       
        m
        +
        1
       
       )
      
     
    
    =
    
     
      ξ
      ⁡
      (
      
       
        k
        
         *
         
          (
          
           
            n
            +
            1
           
           ,
           1
          
          )
         
        
       
       +
       
        
         H
         ⁡
         (
         
          MSG
          ⁢
          
           
            ❘
            "\[LeftBracketingBar]"
           
           
            ❘
            "\[RightBracketingBar]"
           
          
          ⁢
          𝕊
         
         )
        
        ⁢
        
         k
         
          *
          
           (
           
            
             n
             +
             1
            
            ,
            2
           
           )
          
         
        
       
      
      )
     
     +
     
      r
      
       *
       
        (
        
         m
         +
         1
        
        )
       
      
     
    
   
   ,
  
 

 
  	
  
   ξ
   ,
   
    
     σ
     j
     ′
    
    
     ⟵
     U
    
    
     𝔽
     q
    
   
   ,
  
 

 
  	
  
   
    
     
      r
      
       *
       
        (
        0
        )
       
      
     
     
      ⟵
      U
     
     SPAN
    
    ⁢
    
     〈
     
      b
      
       *
       
        (
        
         0
         ,
         3
        
        )
       
      
     
     〉
    
   
   ,
   
    
     
      r
      
       *
       
        (
        j
        )
       
      
     
     
      ⟵
      U
     
     SPAN
    
    ⁢
    
     〈
     
      
       b
       
        *
        
         (
         
          1
          ,
          11
         
         )
        
       
      
      ,
      
       b
       
        *
        
         (
         
          1
          ,
          12
         
         )
        
       
      
     
     〉
    
   
   ,
  
 

 
  	
  
   
    
     
      r
      
       *
       
        (
        
         m
         +
         1
        
        )
       
      
     
     
      ⟵
      U
     
     SPAN
    
    ⁢
    
     〈
     
      
       b
       
        *
        
         (
         
          2
          ,
          5
         
         )
        
       
      
      ,
      
       b
       
        *
        
         (
         
          2
          ,
          6
         
         )
        
       
      
     
     〉
    
   
   ,
  
 

 
  	
  
   
    (
    
     
      
       (
       
        Ω
        j
        ′
       
       )
      
      
       j
       ∈
       
        [
        m
        ]
       
      
     
     ,
     
      
       (
       
        Ω
        j
        ″
       
       )
      
      
       j
       ∈
       
        [
        m
        ]
       
      
     
    
    )
   
   
    ⟵
    U
   
   
    
     (
     
      𝔽
      q
      m
     
     )
    
    2
   
  
 

 
  	
  
   
    
     such
     ⁢
        
     that
     ⁢
        
     
      
       ∑
        
      
      
       j
       ∈
       
        [
        m
        ]
       
      
     
     ⁢
     
      (
      
       
        
         Ω
         j
         ′
        
        ⁢
        
         
          y
          →
         
         
          (
          j
          )
         
        
       
       +
       
        
         Ω
         j
         ″
        
        ⁢
        
         
          z
          →
         
         
          (
          j
          )
         
        
       
      
      )
     
    
    =
    
     
      0
      →
     
     L
    
   
   ,
  
 

 
  
   k
   
    *
    
     (
     0
     )
    
   
  
  ,
  …
    
  ,
  
   k
   
    *
    
     (
     n
     )
    
   
  
  ,
  
   k
   
    *
    
     (
     
      
       n
       +
       1
      
      ,
      1
     
     )
    
   
  
  ,
  
   
    k
    
     *
     
      (
      
       
        n
        +
        1
       
       ,
       2
      
      )
     
    
   
   ⁢
      
   are
   ⁢
      
   elements
   ⁢
      
   of
   ⁢
      
   a
   ⁢
      
   signature
   ⁢
      
   key
  
  ,
 

 
  	
  
   
    
     k
     
      *
      
       (
       0
       )
      
     
    
    =
    
     
      (
      
       ω
       ,
       0
       ,
       
        ϕ
        0
       
       ,
       0
      
      )
     
     
      𝔹
      0
      *
     
    
   
   ,
  
 

 
  	
  
   
    
     k
     
      *
      
       (
       ι
       )
      
     
    
    =
    
     
      (
      
       
        
         σ
         ι
        
        (
        
         1
         ,
         ι
        
        )
       
       ,
       
        ω
        ⁡
        (
        
         1
         ,
         
          x
          ι
         
        
        )
       
       ,
       
        
         0
         →
        
        6
       
       ,
       
        
         ϕ
         →
        
        
         (
         ι
         )
        
       
       ,
       
        
         0
         →
        
        2
       
      
      )
     
     
      𝔹
      1
      *
     
    
   
   ,
  
 

 
  	
  
   
    
     k
     
      *
      
       (
       
        
         n
         +
         1
        
        ,
        1
       
       )
      
     
    
    =
    
     
      
       
        (
        
         
          ω
          ⁡
          (
          
           1
           ,
           0
          
          )
         
         ,
         
          
           0
           →
          
          2
         
         ,
         
          
           ϕ
           →
          
          
           (
           
            
             n
             +
             1
            
            ,
            1
           
           )
          
         
         ,
         
          
           0
           →
          
          2
         
        
        )
       
       
        𝔹
        2
        *
       
      
      ⁢
         
      for
      ⁢
         
      ι
     
     ∈
     
      [
      n
      ]
     
    
   
   ,
  
 

 
  	
  
   
    
     k
     
      *
      
       (
       
        
         n
         +
         1
        
        ,
        2
       
       )
      
     
    
    =
    
     
      (
      
       
        ω
        ⁡
        (
        
         1
         ,
         0
        
        )
       
       ,
       
        
         0
         →
        
        2
       
       ,
       
        
         ϕ
         →
        
        
         (
         
          
           n
           +
           1
          
          ,
          2
         
         )
        
       
       ,
       
        
         0
         →
        
        2
       
      
      )
     
     
      𝔹
      2
      *
     
    
   
   ,
  
 

 
  	
  
   
    
     ω
     
      ⟵
      U
     
     
      𝔽
      q
     
    
    ⁢
    \
    ⁢
    
     {
     0
     }
    
   
   ,
   
    
     ϕ
     0
    
    
     ⟵
     U
    
    
     𝔽
     q
    
   
   ,
  
 

 
  	
  
   
    
     for
     ⁢
        
     ι
    
    ∈
    
     
      [
      n
      ]
     
     ⁢
     
      
       
        σ
        ι
       
       
        ⟵
        U
       
       
        𝔽
        q
       
      
      ⁢
      \
      ⁢
      
       {
       0
       }
      
     
    
   
   ,
   
    
     ϕ
     →
    
    
     (
     ι
     )
    
   
   ,
   
    
     ϕ
     →
    
    
     (
     
      
       n
       +
       1
      
      ,
      1
     
     )
    
   
   ,
   
    
     
      ϕ
      →
     
     
      (
      
       
        n
        +
        1
       
       ,
       2
      
      )
     
    
    
     ⟵
     
         
      U
     
    
    
     𝔽
     q
     2
    
   
   ,
  
 

 
  
   H
   ⁢
      
   is
   ⁢
      
   a
   ⁢
      
   hash
   ⁢
      
   function
  
  ,
  
   MSG
   ⁢
      
   is
   ⁢
      
   a
   ⁢
      
   message
  
  ,
  and
  ,
  
   
    b
    *
   
   ⁢
      
   is
   ⁢
      
   a
   ⁢
      
   basis
   ⁢
      
   vector
   ⁢
      
   of
   ⁢
      
   a
   ⁢
      
   basis
   ⁢
      
   
    B
    *
   
  
 

 
  
   
    
     	
     
      c
      =
      
       (
       
        
         c
         
          (
          0
          )
         
        
        ,
        …
          
        ,
        
         c
         
          (
          
           m
           +
           1
          
          )
         
        
       
       )
      
     
    
   
   
    
     [
     
      Formula
      ⁢
         
      6
     
     ]
    
   
  
 

 
  	
  where
 

 
  	
  
   
    c
    
     (
     0
     )
    
   
   =
   
    
     (
     
      
       
        -
        u
       
       -
       
        u
        L
       
      
      ,
      0
      ,
      0
      ,
      
       η
       0
      
     
     )
    
    
     𝔹
     0
    
   
  
 

 
  	
  
   
    c
    
     (
     j
     )
    
   
   =
   
    
     
      
       (
       
        
         
          μ
          j
         
         (
         
          
           ρ
           ⁡
           (
           j
           )
          
          ,
          
           -
           1
          
         
         )
        
        ,
        
         (
         
          
           s
           j
           ′
          
          ,
          
           s
           j
          
         
         )
        
        ,
        
         
          0
          →
         
         6
        
        ,
        
         
          0
          →
         
         2
        
        ,
        
         
          η
          →
         
         
          (
          j
          )
         
        
       
       )
      
      
       𝔹
       1
      
     
     ⁢
        
     for
     ⁢
        
     j
    
    ∈
    
     [
     m
     ]
    
   
  
 

 
  	
  
   
    c
    
     (
     
      m
      +
      1
     
     )
    
   
   =
   
    
     (
     
      
       (
       
        
         u
         -
         
          κ
          ⁢
          
           H
           ⁡
           (
           
            MSG
            ⁢
            
             
              ❘
              "\[LeftBracketingBar]"
             
             
              ❘
              "\[RightBracketingBar]"
             
            
            ⁢
            𝕊
           
           )
          
         
        
        ,
        κ
       
       )
      
      ,
      
       
        0
        →
       
       2
      
      ,
      
       
        0
        →
       
       2
      
      ,
      
       
        η
        →
       
       
        (
        
         m
         +
         1
        
        )
       
      
     
     )
    
    
     𝔹
     2
    
   
  
 

 
  	
  
   
    
     u
     →
    
    =
    
     
      (
      
       
        u
        1
       
       ,
       …
         
       ,
       
        u
        L
       
      
      )
     
     
      ⟵
      U
     
     
      𝔽
      q
      L
     
    
   
   ,
  
 

 
  	
  
   
    
     
      for
      ⁢
         
      j
     
     ∈
     
      
       [
       m
       ]
      
      ⁢
      
       s
       j
      
     
    
    =
    
     
      u
      →
     
     ·
     
      
       y
       →
      
      
       (
       j
       )
      
     
    
   
   ,
   
    
     s
     j
     ′
    
    =
    
     
      u
      →
     
     ·
     
      
       z
       →
      
      
       (
       j
       )
      
     
    
   
   ,
  
 

 
  	
  
   u
   ,
   
    η
    0
   
   ,
   
    κ
    
     ⟵
     U
    
    
     𝔽
     q
    
   
   ,
   
    
     
      
       μ
       j
      
      
       ⟵
       U
      
      
       𝔽
       d
      
     
     ⁢
        
     for
     ⁢
        
     j
    
    ∈
    
     [
     m
     ]
    
   
   ,
  
 

 
  	
  
   
    
     η
     →
    
    
     (
     j
     )
    
   
   ,
   
    
     
      
       η
       →
      
      
       (
       
        m
        +
        1
       
       )
      
     
     
      ⟵
      U
     
     
      𝔽
      q
      2
     
    
    .