Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
EXAMINER’S NOTE: The claims have been reviewed and considered under the new guidance pursuant to the 2019 Revised Patent Subject Matter Eligibility Guidance (PEG 2019) issued January 7, 2019.
This communication is in response to Applicant’s Amendment filed on 03 September 2025. Claims 1, 7, and 13 have been amended. Claims 1-18 remain pending.
Claim Objections
Claims 1, 7, and 13 are objected to because of the following informalities: The word "cyphertexts" located at the end of the second claim limitation appears as a typographical error and should be recited as "ciphertexts". Appropriate correction is required.
Response to Arguments
Applicant’s arguments, see pages 9-13, filed 03 September 2025, with respect to the rejection(s) of claims 1-3, 6-9, 12-15, and 18 in view of Lee et al. (Pub No. 2024/0121076) have been fully considered, but are moot in view of the new grounds of rejection. A new grounds of rejection is hereby presented in view of EOM et al. (Pub No. 2022/0376890).
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-3, 6-9, 12-15, and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Lee et al. (Pub No. 2024/0121076) in view of EOM et al. (Pub No. 2022/0376890).
Referring to the rejection of claim 1, Lee et al. discloses a method operating at a server for homomorphically generating one or more rotation keys useful for homomorphic computation, comprising: (See Lee et al., para. 45 and 95, i.e., a method operating at a server, item 10 for homomorphic computation generating one or more rotation keys (secret key, rotation key, key switching key)
receiving a set of Learning With Errors (LWE) ciphertexts, the set of LWE ciphertexts having been derived at a client with respect to a secret key polynomial, the secret key polynomial having a set of coefficients, each LWE ciphertext having been derived from a coefficient of the secret key polynomial and having a single coefficient; (See Lee et al., para. 75, 86-91, and 115-123, i.e., the homomorphic encryption operation for receiving data in Fig. 7, is performed by the processors defined in Fig. 2, wherein a receiver receive data for performing a homomorphic encryption operation, a processor perform modulus switching by mapping a component of an input ciphertext generated from the data to an odd number, generate the input ciphertext by generating an LWE ciphertext based on the data. The LWE ciphertext, a ciphertext of a message (or a plaintext) m may be expressed as (β, {right arrow over (α)})∈Z.sub.q.sup.n+1 and decrypted as expressed by β+Σ.sub.i=0.sup.n−1α.sub.is.sub.i=m+e(mod q) LWE.sub.{right arrow over (s)}(m) using a secret key {right arrow over (s)})
and processing the set of LWE ciphertexts into a ring variant (R-LWE) ciphertext homomorphically to generate the one or more rotation keys, the R-LWE ciphertext encrypting a polynomial having the set of coefficients of the secret key polynomial (See Lee et al., para. 76-85, 92-93, and 124, i.e., in an RLWE ciphertext, a ciphertext of the message m may be expressed as (a,b)∈R.sub.Q.sup.2. The ciphertext may be decrypted as expressed by a.Math.z+b=m+e(mod Q). In an example, RLWE.sub.z(m) may denote encryption of the message m using a secret key z. A RLWE ciphertext of the message m using the secret key z may be defined as expressed by Equation 1. RLWE(m)=(a,a.Math.z+e+m) Here, a denotes a polynomial on a modulus Q, and e denotes an error polynomial with a small coefficient. When each encryption is performed, a and e may be generated at random. A RLWE′ ciphertext of the message m for a secret key s may be defined as expressed by Equation 2. RLWE′(m)=(RLWE(g.sub.0.Math.m), RLWE(g.sub.1.Math.m), . . . ,RLWE(g.sub.d-1.Math.m)) Here, (g.sub.o, g.sub.1, . . . , g.sub.d-1) may be a vector defined in advance for decomposing an arbitrary integer, and may be set in the form of (1, B, B.sup.2, . . . , B.sup.d-1) for an arbitrary integer B or in the form of (Q.sub.0.Math.[Q.sub.0.sup.−1]q.sub.o, . . . , Q.sub.d-1.Math.[Q.sub.d-1.sup.−1]q.sub.d-1) for Q.sub.i=q.sub.i. The processor performs a blind rotation key operation RLWE ciphertext based on the input ciphertext on which modulus switching is performed. The processor generates a homomorphic encryption operation result by performing key switching based on a result of performing the blind rotation key operation)
However, Lee et al. fail to explicitly disclose wherein a given rotation key corresponds to rotated coefficients of the secret key polynomial used to derive the set of LWE cyphertexts at the client; generating another rotation key corresponding to rotated coefficients of the secret key polynomial wherein the another rotation key is generated independently of other rotation keys.
EOM et al. discloses a method and apparatus for modulus refresh in homomorphic encryption.
EOM et al. discloses wherein a given rotation key corresponds to rotated coefficients of the secret key polynomial used to derive the set of LWE cyphertexts at the client; generating another rotation key corresponding to rotated coefficients of the secret key polynomial wherein the another rotation key is generated independently of other rotation keys. (See EOM et al., para. 14, 25, 67, 91-102, 138, i.e., the second ciphertext is generated based on the second blind rotation key (i.e. another rotation key) on the function f and the secret key s. The secret key s generates the rotated coefficients using the RLWE ciphertext for each rotation key. The operation is described as the processor perform a blind rotation operation based on the LWE vector and generates a second ciphertext (a.sub.3, b.sub.3)∈R.sub.Q.sup.2 by performing an operation using a function ƒ(X)=−Σ.sub.u=−c.sup.cuq.Math.X.sup.u on the preprocessed first (a.sub.2, b.sub.2)∈R.sub.2N.sup.2. The second ciphertext (a.sub.3, b.sub.3)∈R.sub.Q.sup.2 may satisfy a.sub.3.Math.s+b.sub.3=−u.Math.q′+e.sub.3 (mod Q). LUT.sub.ƒ,s({right arrow over (a)}, b) may be an operation of performing a blind rotation operation on the function f and the secret key s. The processor generates another blind rotation key and encryption constant based on a secret key used to generate the first ciphertext and encryption constants s.sub.j.sup.+ and s.sub.j.sup.− for the coefficients s.sub.j∈{−1,0,1} of the secret key s, according to the conditions described below. If s.sub.j=1, the processor generates the encryption constants as s.sub.j.sup.+=1 and s.sub.j.sup.−=0. If s.sub.j=0, the processor may generate the encryption constants as s.sub.j.sup.+=0 and s.sub.j.sup.−=0. If s.sub.j=−1, the processor may generate the encryption constants as s.sub.j.sup.+=0 and s.sub.j.sup.−=1. The processor generate the blind rotation key based on the encryption constant, and perform the blind rotation operation based on the blind rotation key. For example, the processor generate a ring Gentry, Sahai, Waters (RGSW) ciphertext for a polynomial with constant terms s.sub.j.sup.+ and s.sub.j.sup.− and use the RGSW ciphertext as the blind rotation key. The blind rotation key including the RGSW ciphertext may be expressed as {RGSW(s.sub.j.sup.+), RGSW(s.sub.j.sup.−)}.sub.j=[0,N-1]. The RGSW ciphertext using a ring learning with error (RLWE) ciphertext. The RLWE ciphertext of a message m for the secret key s may be defined as RLWE(m)=(a,a.Math.s+e+m). Here, a may be a polynomial with a coefficient on the modulus q, and e may be an error polynomial with a small coefficient. The processor defines an RLWE′ ciphertext of the message m for s as RLWE′(m)=(RLWE(g.sub.0.Math.m), RLWE(g.sub.1.Math.m), . . . , RLWE(g.sub.d-1.Math.m)). Here, (g.sub.0, g.sub.1, . . . , g.sub.d-1) may be a vector defined in advance for decomposing an arbitrary integer, may have the form of (1, B, B.sup.2, . . . , B.sup.d-1) for an arbitrary integer B or may be set to (Q.sub.0.Math.[Q.sub.0.sup.−1].sub.q.sub.0, . . . , Q.sub.d-1.Math.[Q.sub.d-1.sup.−1].sub.q.sub.d-1) for Q.sub.i=Q/q.sub.i. Finally, the processor may define the RGSW ciphertext of the message m for the secret key s as RGSW(m)=(RLWE′(−sm),RLWE′(m)). The processor performs the blind rotation operation on each coefficient u.sub.i using (ā.sub.i, b.sub.i). The processor defines the function ƒ as ƒ(X)=Σ.sub.l=−c.sup.cql.Math.X.sup.l, and perform initialization to ACC.sub.0←ƒ(X).Math.X.sup.b.sup.i. The processor obtains a ciphertext ACC.sub.N=(a.sub.i′, b.sub.i′)∈R.sub.Q.sup.2 for m.sub.i=−qu.sub.i+d.sub.1.Math.X+ . . . +d.sub.N-1.Math.X.sup.N-1 by repeatedly performing ACC.sub.j+1←ACC.sub.j.Math.(1+(X.sup.a.sup.j−1).Math.RGSW(s.sub.j.sup.+)+(X.sup.−a.sup.j−1).Math.RGSW(s.sub.j.sup.−)) for all j∈{0, . . . , N−1}. The processor adds “1” to the loop index i. (i.e., rotated coefficients). The processor generates the second ciphertext by combining or repacking the first ciphertexts on which the blind rotation operation is performed. RePack.sub.i=0 . . . N-1(a.sub.i, b.sub.i) may be an operation of combining a plurality of ciphertext polynomials into one polynomial and obtain ciphertexts for m.sub.0, . . . , m.sub.N-1 by repeating the blind rotation operation N times, and then combine the obtained ciphertexts into the second ciphertext (a.sub.3, b.sub.3)∈R.sub.Q.sup.2 for m=−(qu.sub.0+qu.sub.1X+ . . . +qu.sub.N-1X.sup.N-1).
The processor generates a target ciphertext by correcting the first ciphertext using the second ciphertext, obtain the target ciphertext (a.sub.4, b.sub.4)∈R.sub.Q.sup.2 for (a.sub.1, b.sub.1)∈R.sub.q′.sup.2 and (a.sub.3, b.sub.3)∈R.sub.Q.sup.2. (a.sub.4, b.sub.4)∈R.sub.Q.sup.2 may be expressed as a.sub.4.Math.s+b.sub.4=m+e.sub.1+e.sub.3 (mod Q) and output the target ciphertext with the modulus increased to Q for the message m)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date the claimed invention was made to combine Lee et al.’s apparatus and method with homomorphic encryption modified with EOM et al.’s method and apparatus for modulus refresh in homomorphic encryption.
Motivation for such an implementation would enable creating a secret key to be used for homomorphic generation of rotation keys using a ring learning with error (RLWE) ciphertext that corresponds to the rotated coefficients of the secret key. (See EOM et al., para. 96-97)
Referring to the rejection of claims 2, 8, and 14, (Lee et al. modified by EOM et al.) discloses wherein, prior to processing, a dimension of each LWE ciphertext is expanded to match a dimension of the R-LWE ciphertext. (See Lee et al., para. 83-84, i.e., using the key switching, the ciphertext match the RLWE ciphertext that is homomorphically generated wherein the space of the domain and the codomain are the same (match)
Referring to the rejection of claims 3, 9, and 15, , (Lee et al. modified by EOM et al.) discloses wherein the dimension of each LWE ciphertext is expanded using a switch key received at the server, the switch key having been derived at the client from the secret key polynomial. (See Lee, para. 84-86, i.e., the processor obtains a ciphertext corresponding to a new secret key z.sub.2 from a ciphertext corresponding to a secret key z.sub.1 derived using a key switching operation and obtains a new ciphertext a⊙RLWE′.sub.z.sub.2(s.sub.1)+(0,b)=(a.sub.2,b.sub.2)∈R.sub.Q.sup.2 with z.sub.2 as a secret key using a switching key RLWE′.sub.z.sub.2(z.sub.1), which is a public key, with respect to the input ciphertext RLWE.sub.z.sub.1(u) (a.sub.1,b.sub.2)∈R.sub.Q.sup.2. The processor performs modulus switching on an LWE ciphertext (β′,{right arrow over (α)}′)∈Z.sub.Q′.sup.n+1, and effectively perform a blind rotation operation using the ciphertext on which modulus switching is performed)
Referring to the rejection of claims 6, 12, and 18, , (Lee et al. modified by EOM et al.) discloses further including performing a homomorphic computation using the one or more rotation keys. (See Lee et al., para. 45 and 95, i.e., homomorphic computation is performed by using one or more rotation keys (secret key, rotation key, key switching key)
Referring to the rejection of claim 7, (Lee et al. modified by EOM et al.) discloses an apparatus, comprising: (See Lee et al., Fig. 1, i.e., homomorphic encryption apparatus, item 10)
a processor; (See Lee et al., Fig. 1, i.e., processor, item 200)
computer memory holding computer program instructions executed by the processor to homomorphically generate one or more rotation keys useful for homomorphic computation, the computer program instructions comprising program code configured to: (See Lee et al., Fig. 1, i.e., memory, item 300)
receive a set of Learning With Errors (LWE) ciphertexts, the set of LWE ciphertexts having been derived at a client with respect to a secret key polynomial, the secret key polynomial having a set of coefficients, each LWE ciphertext having been derived from a coefficient of the secret key polynomial and having a single coefficient; (See Lee et al., para. 75, 86-91, and 115-123, i.e., the homomorphic encryption operation for receiving data in Fig. 7, is performed by the processors defined in Fig. 2, wherein a receiver receive data for performing a homomorphic encryption operation, a processor perform modulus switching by mapping a component of an input ciphertext generated from the data to an odd number, generate the input ciphertext by generating an LWE ciphertext based on the data. The LWE ciphertext, a ciphertext of a message (or a plaintext) m may be expressed as (β, {right arrow over (α)})∈Z.sub.q.sup.n+1 and decrypted as expressed by β+Σ.sub.i=0.sup.n−1α.sub.is.sub.i=m+e(mod q) LWE.sub.{right arrow over (s)}(m) using a secret key {right arrow over (s)})
and process the set of LWE ciphertexts into a ring variant (R-LWE) ciphertext homomorphically to generate the one or more rotation keys, the R-LWE ciphertext encrypting a polynomial having the set of coefficients of the secret key polynomial (See Lee et al., para. 76-85, 92-93, and 124, i.e., in an RLWE ciphertext, a ciphertext of the message m may be expressed as (a,b)∈R.sub.Q.sup.2. The ciphertext may be decrypted as expressed by a.Math.z+b=m+e(mod Q). In an example, RLWE.sub.z(m) may denote encryption of the message m using a secret key z. A RLWE ciphertext of the message m using the secret key z may be defined as expressed by Equation 1. RLWE(m)=(a,a.Math.z+e+m) Here, a denotes a polynomial on a modulus Q, and e denotes an error polynomial with a small coefficient. When each encryption is performed, a and e may be generated at random. A RLWE′ ciphertext of the message m for a secret key s may be defined as expressed by Equation 2. RLWE′(m)=(RLWE(g.sub.0.Math.m), RLWE(g.sub.1.Math.m), . . . ,RLWE(g.sub.d-1.Math.m)) Here, (g.sub.o, g.sub.1, . . . , g.sub.d-1) may be a vector defined in advance for decomposing an arbitrary integer, and may be set in the form of (1, B, B.sup.2, . . . , B.sup.d-1) for an arbitrary integer B or in the form of (Q.sub.0.Math.[Q.sub.0.sup.−1]q.sub.o, . . . , Q.sub.d-1.Math.[Q.sub.d-1.sup.−1]q.sub.d-1) for Q.sub.i=q.sub.i. The processor performs a blind rotation key operation RLWE ciphertext based on the input ciphertext on which modulus switching is performed. The processor generates a homomorphic encryption operation result by performing key switching based on a result of performing the blind rotation key operation)
However, Lee et al. fail to explicitly disclose wherein a given rotation key corresponds to rotated coefficients of the secret key polynomial used to derive the set of LWE cyphertexts at the client; generating another rotation key corresponding to rotated coefficients of the secret key polynomial wherein the another rotation key is generated independently of other rotation keys.
EOM et al. discloses a method and apparatus for modulus refresh in homomorphic encryption.
EOM et al. discloses wherein a given rotation key corresponds to rotated coefficients of the secret key polynomial used to derive the set of LWE cyphertexts at the client; generating another rotation key corresponding to rotated coefficients of the secret key polynomial wherein the another rotation key is generated independently of other rotation keys. (See EOM et al., para. 14, 25, 67, 91-102, 138, i.e., the second ciphertext is generated based on the second blind rotation key (i.e. another rotation key) on the function f and the secret key s. The secret key s generates the rotated coefficients using the RLWE ciphertext for each rotation key. The operation is described as the processor perform a blind rotation operation based on the LWE vector and generates a second ciphertext (a.sub.3, b.sub.3)∈R.sub.Q.sup.2 by performing an operation using a function ƒ(X)=−Σ.sub.u=−c.sup.cuq.Math.X.sup.u on the preprocessed first (a.sub.2, b.sub.2)∈R.sub.2N.sup.2. The second ciphertext (a.sub.3, b.sub.3)∈R.sub.Q.sup.2 may satisfy a.sub.3.Math.s+b.sub.3=−u.Math.q′+e.sub.3 (mod Q). LUT.sub.ƒ,s({right arrow over (a)}, b) may be an operation of performing a blind rotation operation on the function f and the secret key s. The processor generates another blind rotation key and encryption constant based on a secret key used to generate the first ciphertext and encryption constants s.sub.j.sup.+ and s.sub.j.sup.− for the coefficients s.sub.j∈{−1,0,1} of the secret key s, according to the conditions described below. If s.sub.j=1, the processor generates the encryption constants as s.sub.j.sup.+=1 and s.sub.j.sup.−=0. If s.sub.j=0, the processor may generate the encryption constants as s.sub.j.sup.+=0 and s.sub.j.sup.−=0. If s.sub.j=−1, the processor may generate the encryption constants as s.sub.j.sup.+=0 and s.sub.j.sup.−=1. The processor generate the blind rotation key based on the encryption constant, and perform the blind rotation operation based on the blind rotation key. For example, the processor generate a ring Gentry, Sahai, Waters (RGSW) ciphertext for a polynomial with constant terms s.sub.j.sup.+ and s.sub.j.sup.− and use the RGSW ciphertext as the blind rotation key. The blind rotation key including the RGSW ciphertext may be expressed as {RGSW(s.sub.j.sup.+), RGSW(s.sub.j.sup.−)}.sub.j=[0,N-1]. The RGSW ciphertext using a ring learning with error (RLWE) ciphertext. The RLWE ciphertext of a message m for the secret key s may be defined as RLWE(m)=(a,a.Math.s+e+m). Here, a may be a polynomial with a coefficient on the modulus q, and e may be an error polynomial with a small coefficient. The processor defines an RLWE′ ciphertext of the message m for s as RLWE′(m)=(RLWE(g.sub.0.Math.m), RLWE(g.sub.1.Math.m), . . . , RLWE(g.sub.d-1.Math.m)). Here, (g.sub.0, g.sub.1, . . . , g.sub.d-1) may be a vector defined in advance for decomposing an arbitrary integer, may have the form of (1, B, B.sup.2, . . . , B.sup.d-1) for an arbitrary integer B or may be set to (Q.sub.0.Math.[Q.sub.0.sup.−1].sub.q.sub.0, . . . , Q.sub.d-1.Math.[Q.sub.d-1.sup.−1].sub.q.sub.d-1) for Q.sub.i=Q/q.sub.i. Finally, the processor may define the RGSW ciphertext of the message m for the secret key s as RGSW(m)=(RLWE′(−sm),RLWE′(m)). The processor performs the blind rotation operation on each coefficient u.sub.i using (ā.sub.i, b.sub.i). The processor defines the function ƒ as ƒ(X)=Σ.sub.l=−c.sup.cql.Math.X.sup.l, and perform initialization to ACC.sub.0←ƒ(X).Math.X.sup.b.sup.i. The processor obtain a ciphertext ACC.sub.N=(a.sub.i′, b.sub.i′)∈R.sub.Q.sup.2 for m.sub.i=−qu.sub.i+d.sub.1.Math.X+ . . . +d.sub.N-1.Math.X.sup.N-1 by repeatedly performing ACC.sub.j+1←ACC.sub.j.Math.(1+(X.sup.a.sup.j−1).Math.RGSW(s.sub.j.sup.+)+(X.sup.−a.sup.j−1).Math.RGSW(s.sub.j.sup.−)) for all j∈{0, . . . , N−1}. The processor adds “1” to the loop index i. (i.e., rotated coefficients). The processor generates the second ciphertext by combining or repacking the first ciphertexts on which the blind rotation operation is performed. RePack.sub.i=0 . . . N-1(a.sub.i, b.sub.i) may be an operation of combining a plurality of ciphertext polynomials into one polynomial and obtain ciphertexts for m.sub.0, . . . , m.sub.N-1 by repeating the blind rotation operation N times, and then combine the obtained ciphertexts into the second ciphertext (a.sub.3, b.sub.3)∈R.sub.Q.sup.2 for m=−(qu.sub.0+qu.sub.1X+ . . . +qu.sub.N-1X.sup.N-1).
The processor generates a target ciphertext by correcting the first ciphertext using the second ciphertext, obtain the target ciphertext (a.sub.4, b.sub.4)∈R.sub.Q.sup.2 for (a.sub.1, b.sub.1)∈R.sub.q′.sup.2 and (a.sub.3, b.sub.3)∈R.sub.Q.sup.2. (a.sub.4, b.sub.4)∈R.sub.Q.sup.2 may be expressed as a.sub.4.Math.s+b.sub.4=m+e.sub.1+e.sub.3 (mod Q) and output the target ciphertext with the modulus increased to Q for the message m)
The rationale for combining Lee et al. in view of EOM et al. is the same as claim 1.
Referring to the rejection of claim 13, , (Lee et al. modified by EOM et al.) discloses a computer program product in a non-transitory computer readable medium, the computer program product holding computer program instructions that, when executed by one or more processors in a host processing system, homomorphically generate one or more rotation keys useful for homomorphic computation, the computer program instructions comprising program code configured to: (See Lee et al., Fig. 1 and para. 129, i.e., a non-transitory computer-readable storage medium, such as a memory, item 300)
receive a set of Learning With Errors (LWE) ciphertexts, the set of LWE ciphertexts having been derived at a client with respect to a secret key polynomial, the secret key polynomial having a set of coefficients, each LWE ciphertext having been derived from a coefficient of the secret key polynomial and having a single coefficient; (See Lee et al., para. 75, 86-91, and 115-123, i.e., the homomorphic encryption operation for receiving data in Fig. 7, is performed by the processors defined in Fig. 2, wherein a receiver receive data for performing a homomorphic encryption operation, a processor perform modulus switching by mapping a component of an input ciphertext generated from the data to an odd number, generate the input ciphertext by generating an LWE ciphertext based on the data. The LWE ciphertext, a ciphertext of a message (or a plaintext) m may be expressed as (β, {right arrow over (α)})∈Z.sub.q.sup.n+1 and decrypted as expressed by β+Σ.sub.i=0.sup.n−1α.sub.is.sub.i=m+e(mod q) LWE.sub.{right arrow over (s)}(m) using a secret key {right arrow over (s)})
and process the set of LWE ciphertexts into a ring variant (R-LWE) ciphertext homomorphically to generate the one or more rotation keys, the R-LWE ciphertext encrypting a polynomial having the set of coefficients of the secret key polynomial (See Lee et al., para. 76-85, 92-93, and 124, i.e., in an RLWE ciphertext, a ciphertext of the message m may be expressed as (a,b)∈R.sub.Q.sup.2. The ciphertext may be decrypted as expressed by a.Math.z+b=m+e(mod Q). In an example, RLWE.sub.z(m) may denote encryption of the message m using a secret key z. A RLWE ciphertext of the message m using the secret key z may be defined as expressed by Equation 1. RLWE(m)=(a,a.Math.z+e+m) Here, a denotes a polynomial on a modulus Q, and e denotes an error polynomial with a small coefficient. When each encryption is performed, a and e may be generated at random. A RLWE′ ciphertext of the message m for a secret key s may be defined as expressed by Equation 2. RLWE′(m)=(RLWE(g.sub.0.Math.m), RLWE(g.sub.1.Math.m), . . . ,RLWE(g.sub.d-1.Math.m)) Here, (g.sub.o, g.sub.1, . . . , g.sub.d-1) may be a vector defined in advance for decomposing an arbitrary integer, and may be set in the form of (1, B, B.sup.2, . . . , B.sup.d-1) for an arbitrary integer B or in the form of (Q.sub.0.Math.[Q.sub.0.sup.−1]q.sub.o, . . . , Q.sub.d-1.Math.[Q.sub.d-1.sup.−1]q.sub.d-1) for Q.sub.i=q.sub.i. The processor performs a blind rotation key operation RLWE ciphertext based on the input ciphertext on which modulus switching is performed. The processor generates a homomorphic encryption operation result by performing key switching based on a result of performing the blind rotation key operation)
However, Lee et al. fail to explicitly disclose wherein a given rotation key corresponds to rotated coefficients of the secret key polynomial used to derive the set of LWE cyphertexts at the client; generating another rotation key corresponding to rotated coefficients of the secret key polynomial wherein the another rotation key is generated independently of other rotation keys.
EOM et al. discloses a method and apparatus for modulus refresh in homomorphic encryption.
EOM et al. discloses wherein a given rotation key corresponds to rotated coefficients of the secret key polynomial used to derive the set of LWE cyphertexts at the client; generating another rotation key corresponding to rotated coefficients of the secret key polynomial wherein the another rotation key is generated independently of other rotation keys. (See EOM et al., para. 14, 25, 67, 91-102, 138, i.e., the second ciphertext is generated based on the second blind rotation key (i.e. another rotation key) on the function f and the secret key s. The secret key s generates the rotated coefficients using the RLWE ciphertext for each rotation key. The operation is described as the processor perform a blind rotation operation based on the LWE vector and generates a second ciphertext (a.sub.3, b.sub.3)∈R.sub.Q.sup.2 by performing an operation using a function ƒ(X)=−Σ.sub.u=−c.sup.cuq.Math.X.sup.u on the preprocessed first (a.sub.2, b.sub.2)∈R.sub.2N.sup.2. The second ciphertext (a.sub.3, b.sub.3)∈R.sub.Q.sup.2 may satisfy a.sub.3.Math.s+b.sub.3=−u.Math.q′+e.sub.3 (mod Q). LUT.sub.ƒ,s({right arrow over (a)}, b) may be an operation of performing a blind rotation operation on the function f and the secret key s. The processor generates another blind rotation key and encryption constant based on a secret key used to generate the first ciphertext and encryption constants s.sub.j.sup.+ and s.sub.j.sup.− for the coefficients s.sub.j∈{−1,0,1} of the secret key s, according to the conditions described below. If s.sub.j=1, the processor generates the encryption constants as s.sub.j.sup.+=1 and s.sub.j.sup.−=0. If s.sub.j=0, the processor may generate the encryption constants as s.sub.j.sup.+=0 and s.sub.j.sup.−=0. If s.sub.j=−1, the processor may generate the encryption constants as s.sub.j.sup.+=0 and s.sub.j.sup.−=1. The processor generate the blind rotation key based on the encryption constant, and perform the blind rotation operation based on the blind rotation key. For example, the processor generate a ring Gentry, Sahai, Waters (RGSW) ciphertext for a polynomial with constant terms s.sub.j.sup.+ and s.sub.j.sup.− and use the RGSW ciphertext as the blind rotation key. The blind rotation key including the RGSW ciphertext may be expressed as {RGSW(s.sub.j.sup.+), RGSW(s.sub.j.sup.−)}.sub.j=[0,N-1]. The RGSW ciphertext using a ring learning with error (RLWE) ciphertext. The RLWE ciphertext of a message m for the secret key s may be defined as RLWE(m)=(a,a.Math.s+e+m). Here, a may be a polynomial with a coefficient on the modulus q, and e may be an error polynomial with a small coefficient. The processor defines an RLWE′ ciphertext of the message m for s as RLWE′(m)=(RLWE(g.sub.0.Math.m), RLWE(g.sub.1.Math.m), . . . , RLWE(g.sub.d-1.Math.m)). Here, (g.sub.0, g.sub.1, . . . , g.sub.d-1) may be a vector defined in advance for decomposing an arbitrary integer, may have the form of (1, B, B.sup.2, . . . , B.sup.d-1) for an arbitrary integer B or may be set to (Q.sub.0.Math.[Q.sub.0.sup.−1].sub.q.sub.0, . . . , Q.sub.d-1.Math.[Q.sub.d-1.sup.−1].sub.q.sub.d-1) for Q.sub.i=Q/q.sub.i. Finally, the processor may define the RGSW ciphertext of the message m for the secret key s as RGSW(m)=(RLWE′(−sm),RLWE′(m)). The processor performs the blind rotation operation on each coefficient u.sub.i using (ā.sub.i, b.sub.i). The processor defines the function ƒ as ƒ(X)=Σ.sub.l=−c.sup.cql.Math.X.sup.l, and perform initialization to ACC.sub.0←ƒ(X).Math.X.sup.b.sup.i. The processor obtains a ciphertext ACC.sub.N=(a.sub.i′, b.sub.i′)∈R.sub.Q.sup.2 for m.sub.i=−qu.sub.i+d.sub.1.Math.X+ . . . +d.sub.N-1.Math.X.sup.N-1 by repeatedly performing ACC.sub.j+1←ACC.sub.j.Math.(1+(X.sup.a.sup.j−1).Math.RGSW(s.sub.j.sup.+)+(X.sup.−a.sup.j−1).Math.RGSW(s.sub.j.sup.−)) for all j∈{0, . . . , N−1}. The processor adds “1” to the loop index i. (i.e., rotated coefficients). The processor generates the second ciphertext by combining or repacking the first ciphertexts on which the blind rotation operation is performed. RePack.sub.i=0 . . . N-1(a.sub.i, b.sub.i) may be an operation of combining a plurality of ciphertext polynomials into one polynomial and obtain ciphertexts for m.sub.0, . . . , m.sub.N-1 by repeating the blind rotation operation N times, and then combine the obtained ciphertexts into the second ciphertext (a.sub.3, b.sub.3)∈R.sub.Q.sup.2 for m=−(qu.sub.0+qu.sub.1X+ . . . +qu.sub.N-1X.sup.N-1).
The processor generates a target ciphertext by correcting the first ciphertext using the second ciphertext, obtain the target ciphertext (a.sub.4, b.sub.4)∈R.sub.Q.sup.2 for (a.sub.1, b.sub.1)∈R.sub.q′.sup.2 and (a.sub.3, b.sub.3)∈R.sub.Q.sup.2. (a.sub.4, b.sub.4)∈R.sub.Q.sup.2 may be expressed as a.sub.4.Math.s+b.sub.4=m+e.sub.1+e.sub.3 (mod Q) and output the target ciphertext with the modulus increased to Q for the message m)
The rationale for combining Lee et al. in view of EOM et al. is the same as claim 1.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 4-5, 10-11, and 16-17 is/are rejected under 35 U.S.C. 103 as being unpatentable over Lee et al. (Pub No. 2024/0121076) and EOM et al. (Pub No. 2022/0376890) in view of Gao et al. (Pub No. 2019/0394019).
The combination of Lee et al. and EOM et al. discloses the invention as described above, however, neither Lee et al. or EOM et al. explicitly disclose processing the set of LWE ciphertexts comprises re-ordering the LWE ciphertexts, and packing the re-ordered LWE ciphertexts using a packing algorithm to generate the R-LWE ciphertext.
Gao et al. discloses a system and method for homomorphic encryption.
Referring to the rejection of claims 4, 10, and 16, (Lee et al. and EOM et al. modified by Gao et al.) discloses wherein processing the set of LWE ciphertexts comprises re-ordering the LWE ciphertexts, and packing the re-ordered LWE ciphertexts using a packing algorithm to generate the R-LWE ciphertext. (See Gao et al., para. 75 and 79, i.e., in order to compute a general function f on the data x=(x.sub.1, x.sub.2, . . . , x.sub.L), one just follows the gates of the circuit of f from input LWE ciphertexts to output LWE ciphertexts. Packing for each group of n LWE ciphers for the bits of the output y=f(x), pack them into one RLWE cipher in R.sub.m,r.sup.2 where m=r/2. Return the list of RLWE ciphers as the encrypted result y=f(x), this method will shuffle the LWE ciphertexts as chosen independent random, which is disclosed as re-ordering)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date the claimed invention was made to combine Lee et al.’s apparatus and method with homomorphic encryption and EOM et al.’s method and apparatus for modulus refresh in homomorphic encryption modified with Gao et al.’s system and method for homomorphic encryption.
Motivation for such an implementation would enable improving fully homomorphic encryption using faster packed homomorphic operations. (See Gao et al., para. 8)
Referring to the rejection of claims 5, 11, and 17, (Lee et al. and EOM et al. modified by Gao et al.) discloses wherein the re-ordered LWE ciphertexts are packed using a key received at the server, the key having been derived at the client from the secret key polynomial. (See Gao et al., para. 71-72 and 75, i.e., the homomorphic computing for unpacking/packing LWE ciphertexts comprises the following - Let x∈{0,1}.sup.L represent a data of a client where L can be large, the data x is encrypted in blocks of length n and derived using the secret key of the client, and stored as a collection of RLWE ciphers in R.sub.n,r.sup.2 as above. Let f: {0, 1}.sup.L♯{0,1}.sup.M be an arbitrary function, given as a circuit (Boolean or arithmetic modulo some integer). We want to compute the ciphertext for y=(y.sub.1, . . . , y.sub.M)=f(x) using the bootstrapping key published by the client. Unpack from each RLWE cipher in R.sub.n,r.sup.2 of x, extract n LWE ciphers in .sub.r.sup.n×.sub.r, all with error size<D.sub.r/4 for the individual bits of x and packing for each group of LWE ciphers for the bits of the output y=f(x), pack them into one RLWE cipher in R.sub.m,r.sup.2 where m=r/2.)
The rationale for combining Lee et al. and EOM et al. in view of Gao et al. is the same as claim 4.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to COURTNEY D FIELDS whose telephone number is (571)272-3871. The examiner can normally be reached IFP M-F 8am-4:30pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, SHEWAYE GELAGAY can be reached at (571)272-4219. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/COURTNEY D FIELDS/Examiner, Art Unit 2436 October 18, 2025
/SHEWAYE GELAGAY/Supervisory Patent Examiner, Art Unit 2436
Prosecution Insights