Electronic device and controlling method for increasing an operation speed of homomorphic encrypted data

Patent metadata

Field	Value
Publication number	US-12574238-B2
Application number	US-202418421363-A
Country	US
Kind code	B2
Filing date	Jan 24, 2024
Priority date	Jan 25, 2023
Publication date	Mar 10, 2026
Grant date	Mar 10, 2026

Abstract

Disclosed are an electronic device and a controlling method. The method of controlling an electronic device includes: converting a first polynomial into a first sub-polynomial based on each term and coefficient of a first polynomial, and converting a second polynomial into a second sub-polynomial based on each term and coefficient of a second polynomial; acquiring a calculated sub-polynomial by performing a multiplication operation on the converted first sub-polynomial and the converted second sub-polynomial; removing coefficients greater than or equal to a preset number of digits from coefficients of the calculated sub-polynomial divided based on each term unit of the first polynomial and the second polynomial; and determining coefficients of a sub-polynomial from which the coefficients greater than or equal to the preset number of digits divided based on each term unit of the first polynomial and the second polynomial are removed as coefficients of a polynomial acquired by the multiplication operation of the first polynomial and the second polynomial.

First claim

What is claimed is:

1 . A method of controlling an electronic device, comprising:
receiving a first polynomial and a second polynomial via a communication interface of the electronic device; converting the first polynomial into a first sub-polynomial based on each term and coefficient of a first polynomial, and converting the second polynomial into a second sub-polynomial based on each term and coefficient of a second polynomial; acquiring a calculated sub-polynomial by performing a multiplication operation on the converted first sub-polynomial and the converted second sub-polynomial; removing coefficients greater than or equal to a preset number of digits from coefficients of the calculated sub-polynomial divided based on each term unit of the first polynomial and the second polynomial; and determining coefficients of a sub-polynomial from which the coefficients greater than or equal to the preset number of digits divided based on each term unit of the first polynomial and the second polynomial are removed as coefficients of a polynomial acquired by the multiplication operation of the first polynomial and the second polynomial; and transmitting, via the communication interface, the polynomial acquired by the multiplication operation to an external electronic device.

2 . The method as claimed in claim 1 , wherein each coefficient of the first sub-polynomial and the second sub-polynomial is set to less than or equal to a preset q bit.

3 . The method as claimed in claim 2 , further comprising:
rearranging the calculated coefficients of the sub-polynomial when the calculated coefficients of the sub-polynomial exceed the preset q bit.

4 . The method as claimed in claim 2 , wherein a highest difference of the first sub-polynomial and the second sub-polynomial is set to k, and the k is set to an integer where q k >NQ 2 so that a modulo operation does not occur during the multiplication operation,
wherein N denotes a highest difference of the first polynomial and the second polynomial, and Q is a prime number and denotes a modulo number at which the modulo operation is performed when a highest difference of operation results of the first polynomial and the second polynomial exceeds Q.

5 . The method as claimed in claim 2 , wherein the first sub-polynomial and the second sub-polynomial are elements included in a set of polynomials of modulo B, and the B is set to a prime number with B>kNq 2 so that a modulo operation does not occur during the multiplication operation,
wherein k denotes a highest difference of the first sub-polynomial and the second sub-polynomial, and N denotes a highest difference of the first polynomial and the second polynomial.

6 . An electronic device, comprising:
a communication interface configured to receive a first polynomial and a second polynomial; a memory configured to store programs that run on the electronic device; and a processor, wherein the processor is configured to convert the first polynomial into a first sub-polynomial based on each term and coefficient of a first polynomial stored in the memory, and convert the second polynomial into a second sub-polynomial based on each term and coefficient of a second polynomial stored in the memory, acquire a calculated sub-polynomial by performing a multiplication operation on the converted first sub-polynomial and the converted second sub-polynomial, remove coefficients greater than or equal to a preset number of digits from coefficients of the calculated sub-polynomial divided based on each term unit of the first polynomial and the second polynomial, determine coefficients of a sub-polynomial from which the coefficients greater than or equal to the preset number of digits divided based on each term unit of the first polynomial and the second polynomial are removed as coefficients of a polynomial acquired by the multiplication operation of the first polynomial and the second polynomial, and transmit, via the communication interface, the polynomial acquired by the multiplication operation to an external electronic device.

7 . The electronic device as claimed in claim 6 , wherein the processor is configured to set each coefficient of the first sub-polynomial and the second sub-polynomial to less than or equal to a preset q bit.

8 . The electronic device as claimed in claim 7 , wherein the processor is configured to rearrange the calculated coefficients of the sub-polynomial when the calculated coefficients of the sub-polynomial exceed the preset q bit.

9 . The electronic device as claimed in claim 7 , wherein the processor is configured to set a highest difference of the first sub-polynomial and the second sub-polynomial to k, and the k is set to an integer where q k >NQ 2 so that a modulo operation does not occur during the multiplication operation,
wherein N denotes a highest difference of the first polynomial and the second polynomial, and Q is a prime number and denotes a modulo number at which the modulo operation is performed when a highest difference of operation results of the first polynomial and the second polynomial exceeds Q.

10 . The electronic device as claimed in claim 7 , wherein the first sub-polynomial and the second sub-polynomial are elements included in a set of polynomials of modulo B, and the processor is configured to set the B to a prime number with B>kNq 2 so that a modulo operation does not occur during the multiplication operation,
wherein k denotes a highest difference of the first sub-polynomial and the second sub-polynomial, and N denotes a highest difference of the first polynomial and the second polynomial.

11 . A non-transitory computer-readable storage medium in which a program performing a method of controlling an electronic device is recorded, wherein the method includes:
receiving a first polynomial and a second polynomial via a communication interface of the electronic device; converting the first polynomial into a first sub-polynomial based on each term and coefficient of the first polynomial, and converting the second polynomial into a second sub-polynomial based on each term and coefficient of the second polynomial; acquiring a calculated sub-polynomial by performing a multiplication operation on the converted first sub-polynomial and the converted second sub-polynomial; removing coefficients greater than or equal to a preset number of digits from coefficients of the calculated sub-polynomial divided based on each term unit of the first polynomial and the second polynomial; determining coefficients of a sub-polynomial from which the coefficients greater than or equal to the preset number of digits divided based on each term unit of the first polynomial and the second polynomial are removed as coefficients of a polynomial acquired by the multiplication operation of the first polynomial and the second polynomial; and transmitting, via the communication interface, the polynomial acquired by the multiplication operation to an external electronic device.

12 . The non-transitory computer-readable storage medium as claimed in claim 11 , wherein each coefficient of the first sub-polynomial and the second sub-polynomial is set to less than or equal to a preset q bit.

13 . The non-transitory computer-readable storage medium as claimed in claim 12 , wherein the method further includes:
rearranging the calculated coefficients of the sub-polynomial when the calculated coefficients of the sub-polynomial exceed the preset q bit.

14 . The non-transitory computer-readable storage medium as claimed in claim 12 , wherein a highest difference of the first sub-polynomial and the second

Assignees

• Crypto Lab Inc
• Seoul Nat Univ R&Db Foundation

Inventors

• Cheon Jung Hee
• Cho Wonhee
• Kim Taekyung

Classifications

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L9/3093 Primary

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title