Patent ID: 11937078
Assignee: CRYPTO LAB INC.
Field: Digital communication (Electrical engineering)
Classification: CPC H | IPC H

Claim 8:
9. A non-transitory recording medium storing a program code for performing a route overlap detecting method of a terminal apparatus, the route overlap detecting method comprising:
calculating and storing location information of the mobile device;
performing homomorphic encryption on a plurality of pieces stored location information and generating movement path information of the mobile device;
transmitting the movement path information to a server apparatus;
based on operation result data obtained by operating based on the movement path information and comparison target path information being received from the server apparatus, decrypting the operation result data;
outputting a message notifying whether a route overlaps the comparison target path information based on a decrypted result; and
wherein the generating the movement path information comprises encoding the plurality of pieces of location information to each element in a plaintext space of a homomorphic ciphertext, calculating a polynomial configured with each encoded element, and performing homomorphic encryption on the calculated polynomial fA(x) to generate the movement path information,
the polynomial, f
      A
     
     (
     x
     )
    
    ⁢
       
    is
    ⁢
       
    
     
      f
      A
     
     (
     x
     )
    
   
   =
   
    
     
      
       ∏
        
      
      
        
       
        i
        =
        1
       
      
      
        
       n
      
     
     ⁢
     
      (
      
       x
       -
       
        a
        
         i
          
        
       
      
      )
     
    
    ∈
    
     
      Z
      p
     
     [
     x
     ]
    
   
  
  ,, and
wherein, x represents a variable, Zp[x] represents the plaintext space, and ai represents an i-th element in the plaintext space,
the operation result data is Enc (rA(x)·fA(x)+rg(x)·fB(x)),
wherein, rA(x) and rb(x) represent random polynomials, and fB(x) represents a polynomial obtained by encoding the comparison target path information, and
the outputting the message comprises:
calculating a greatest common denominator of g(x)=rA(x)·fA(x)+rB(x)·fB(x) obtained by decrypting the operation result data and the fA(x) based on the greatest common denominator being, ∏
      
    
    
      
     
      i
      =
      1
     
    
    
      
     n
    
   
   ⁢
   
    (
    
     x
     -
     
      b
      
       i
        
      
     
    
    )
   
  
  ,, detecting that the route overlaps at a point where the mobile device is located at time ti that biis decrypted, and based on the greatest common denominator being 1, detecting that the route does not overlap; and
generating and outputting a message corresponding to a detection result.