Patent ID: 8160256

Claim:
A method of calculating a key using a processor in a key calculation apparatus, the method comprising: generating two keys using the processor; calculating, using the processor, one or more first values based on coefficients having an identical coefficient value among coefficients included in each of the two keys, such that a first value is calculated for each coefficient value, excluding 0; and performing, based on the calculating of the one of more first values, using the processor, one of a coordinates operation key calculation and a exponentiation operation key calculation, wherein: in the coordinates operation key calculation: each of the two keys includes at most one coefficient, excluding 0, among a consecutive w number of coefficients, the at most one coefficient being an integer that has an absolute value of less than or equal to q w /2 and is indivisible by q; q is a prime number or a power exponent of the prime number; w is a natural number greater than or equal to 2; and the generating of the two keys comprises: selecting, for each of the two keys, a t number of groups from an m−(w−1)*(t−1) number of groups, where m and t are positive integers; substituting each of the selected t number of groups with a string, the string listing a w−1 number of 0s and one or more integers that have an absolute value of less than or equal to q w /2 and are indivisible by q; and substituting an unselected group with 0; and in the exponentiation operation key calculation: each of the two keys includes at most one coefficient, excluding 0, among a consecutive w number of coefficients, the at most one coefficient being a positive odd number less than or equal to 2 w ; w is a natural number greater than or equal to 2; and the generating of the two keys comprises: selecting, for each of the two keys, a t number of groups from an m−(w−1)*t number of groups, where m and t are positive integers; substituting each of the selected t number of groups with a string, the string listing a w−1 number of 0s and one or more positive odd numbers less than or equal to 2 w ; and substituting an unselected group with 0.