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 .
Status of Claims
2. This Office Action is issued in response to the claims filed on 01/01/2025.
Claims 1-12 are pending in this Office Action.
Priority
3. Acknowledgement is made of applicant’s foreign priority claim of French Application No. 2312929 filed on November 23, 2023. However, an attempt by the Office to electronically retrieve, under the priority document exchange program, the foreign application FRANCE 2312929 to which priority is claimed has failed on 02/25/2026.
Information Disclosure Statement
4. The information disclosure statement (IDS) filed on 11/22/2024 has been considered by the Examiner.
Claim Rejections - 35 USC § 112
5. The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
6. Claims 1-12 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
a. Regarding claim 1, it recites:
“1. A decryption method of a secret encrypted by an asymmetric cryptographic key encapsulation mechanism based on a Quasi-Cyclic Moderate-Density Parity-Check corrector code, the cryptographic mechanism using a private key formed by two sparse polynomials, the decryption method being implemented by a receiver and comprising:
the reception of a syndrome polynomial derived from the secret;
the generation of random integers;
the application of a first operation on the first sparse polynomial of the private key, to obtain a first modified sparse polynomial;
the application of a second operation on the second sparse polynomial forming the private key, to obtain a second modified sparse polynomial forming with the first modified sparse polynomial, a modified private key;
the application of a third operation on the syndrome polynomial to obtain a modified syndrome polynomial to be decrypted;
the search for modified error polynomials such as the linear combination of modified error polynomials by the modified private key gives the modified syndrome polynomial to be decrypted; and
the deduction of the shared secret by applying a fourth operation on the first modified error polynomial and a fifth operation on the second modified error polynomial;
the five operations depending on the generated random integers and keeping the weight of the polynomial on which the operation is applied, the weight of a polynomial being the number of non-zero coefficients of the polynomial.”
The emphasized parts lack proper antecedent bases and/or make the intended scope of the claim not clear. Therefore, claim 1 and its dependent claims are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph. For purpose of examination, the Examiner assume claim 1 as follows:
1. A decryption method of a secret encrypted by an asymmetric cryptographic key encapsulation mechanism based on a Quasi-Cyclic Moderate-Density Parity-Check corrector code, the asymmetric cryptographic key encapsulation mechanism using a private key formed by two sparse polynomials, the decryption method being implemented by a receiver and comprising:
receiving a syndrome polynomial derived from the secret;
generating random integers;
applying a first operation on a first sparse polynomial of the two sparse polynomials of the private key, to obtain a first modified sparse polynomial;
applying a second operation on a second sparse polynomial of the two sparse polynomials forming the private key, to obtain a second modified sparse polynomial forming with the first modified sparse polynomial, a modified private key;
applying a third operation on the syndrome polynomial to obtain a modified syndrome polynomial to decrypt;
searching for modified error polynomials including a linear combination of error polynomials and the modified private key to give the modified syndrome polynomial to be decrypted; and
deducing the secret by applying a fourth operation to a first modified error polynomial of the modified error polynomials and a fifth operation to a second modified error polynomial of the modified error polynomials, wherein the five operations depending on the generated random integers and keeping a weight of each respective polynomial on which each respective operation is applied, wherein the weight of each respective polynomial being the number of non-zero coefficients of the respective polynomial.
b. Regarding claim 2, limitation “wherein the five operations compensate each other so that the first error polynomial results from the application of the fourth operation on the first modified error polynomial, and the second error polynomial results from the application of the fifth operation on the second modified error polynomial” is ambiguous because it does not make sense that an error polynomial results from applying an operation on its modified error polynomial. It should be the other way: a modified error polynomial is a result of applying an operation on an error polynomial. Therefore, claim 2 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph. For purpose of examination the Examiner interprets the claim as the five operations compensate each other based on a first error polynomial, the first modified error polynomial, a second error polynomial, and the second modified error polynomial.
c. Regarding claim 3, it recites: “The decryption method of claim 1, wherein each of the five operations is the same function parameterized by at least one integer, at least one integer parameterizing the function dependent on at least one generated random integer.” Element “the same function lacks proper antecedent basis and it is unclear if “at least one integer” is the same or different. Therefore, claim 3 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph. For purpose of examination, the Examiner assumes “the five operations using a same function parameterized by at least one integer, the at least one integer parameterizing the function dependent on at least one generated random integer.”
d. Regarding claim 4, it recites: “The decryption method according to claim 1, wherein at least one integer parameterizing the function is specific to each operation.” The emphasized part lacks proper antecedent basis and makes the claim ambiguous. Therefore, claim 4 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph. For purpose of examination, the Examiner assumes claim 4 depends on claim 3 which recites “function”.
e. Regarding claim 5, it recites: “The decryption method according to claim 1, wherein at least two integers parameterizing the function are linear combinations of two generated random integers.” The emphasized part lacks proper antecedent basis and makes the claim ambiguous. Therefore, claim 5 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph. For purpose of examination, the Examiner assumes claim 5 depends on claim 3 which recites “function”.
f. Regarding claim 8, it recites: “The decryption method according to claim 1, wherein the cryptographic mechanism is a bit flipping key encapsulation algorithm. Limitation “the cryptographic mechanism” makes claim 1 ambiguous as presented above. Therefore, claim 8 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph. For purpose of examination, the Examiner assumes “the cryptographic mechanism” as “the asymmetric cryptographic key encapsulation mechanism.”
g. Regarding claim 10, it recites:
“10. A decryption device for decrypting a secret encrypted by an asymmetric cryptographic key encapsulation mechanism based on a Quasi-Cyclic Moderate-Density Parity-Check corrector code, the cryptographic mechanism using a private key formed by two sparse polynomials and having been shared between a transmitter of which the decryption device is part, the receiver being suitable for receiving a syndrome polynomial derived from the secret, the decryption device being suitable for:
generating random integers,
applying a first operation on the first sparse polynomial of the private key, to obtain a first modified sparse polynomial,
applying a second operation on the second sparse polynomial forming the private key, to obtain a second modified sparse polynomial forming with the first modified sparse polynomial, a modified private key,
applying a third operation on the syndrome polynomial to obtain a modified syndrome polynomial to decrypt,
searching for modified error polynomials such as the linear combination of modified error polynomials by the modified private key gives the modified syndrome polynomial to be decrypted, and
deducing a shared secret by applying a fourth operation to the first modified error polynomial and a fifth operation to the second modified error polynomial, the five operations depending on the generated random integers and keeping the weight of the polynomial on which the operation is applied, the weight of a polynomial being the number of non-zero coefficients of the polynomial.”
The emphasized parts lack proper antecedent bases and/or make the intended scope of the claim not clear. Therefore, claim 10 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph. For purpose of examination, the Examiner assume claim 10 has similar subject matter as claim 1 (Note: the decryption device is a part of the receiver, not the transmitter-see Fig.1 with associated text).
h. Regarding claim 11, it recites: “11. A receiver adapted to receive a syndrome polynomial derived from a secret encrypted by an asymmetric cryptographic key encapsulation mechanism based on a Quasi-Cyclic Moderate-Density Parity-Check corrector code, the cryptographic mechanism using a private key formed by two sparse polynomials and having been shared between a transmitter and the receiver, the receiver comprising a decryption device according to claim 10.” It is unclear if the emphasized elements recited in claim 11 are the same or different with ones recited in claim 10. Therefore, claim 11 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph. For purpose of examination, the Examiner assume claim 10 has similar subject matter as claim 1.
i. Regarding claim 12, it recites: “12. A communication system comprising: a transmitter adapted to encrypt a secret by an asymmetric cryptographic mechanism for encapsulating a key based on a Quasi-Cyclic Moderate-Density Parity-Check corrector code, the cryptographic mechanism using a private key formed by two sparse polynomials, the transmitter being adapted to send a syndrome polynomial derived from the secret, and a receiver according to claim 11.” It is unclear if the emphasized elements recited in claim 11 are the same or different with ones recited in claim 10. Therefore, claim 12 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph. For purpose of examination, the Examiner assume claim 10 has similar subject matter as claim 1.
Allowable Subject Matter
7. Claims 1-12 are allowable over prior art and would be allowable if rewritten to overcome the 35 USC § 112(b) rejections set forth in this Office action.
The following is an examiner’s statement of reasons for allowance:
Regarding independent claims 1 and 10-12:
a. Mazahreh (US 8875001 B1) discloses a decoder including a syndrome polynomial generation circuit, an error polynomial calculation circuit, and a search circuit. The syndrome polynomial generation circuit is configured to generate a syndrome polynomial from a received polynomial. The error polynomial calculation circuit is configured to generate an error location polynomial from the syndrome polynomial. The search circuit is configured to evaluate possible roots of the error polynomial generated by the error polynomial calculation circuit (Col. 2, lines 40-50).
b. Anholt et al. (US 8327242 B1) discloses a method for decoding an Error Correction Code (ECC), comprising: using hardware-implemented logic, producing from a set of bits, which represent data that has been encoded with the ECC, multiple syndromes by applying to the bits vector operations in a vector space; generating, based on the multiple syndromes, an Error Locator Polynomial (ELP) whose roots are indicative of locations of respective errors in the set of bits; and identifying at least some of the roots of the ELP and correcting the errors indicated by the identified roots; wherein each syndrome is produced by applying the vector operations to the set of bits using a respective, different basis of the vector space; wherein each basis is selected such that vector operations used for producing the respective syndrome comprise a multiplication of a sparse matrix; wherein the syndromes are defined over a field having a primitive element, and wherein selecting each basis comprises defining a set of basis elements as respective multiples of a given vector by different powers of the primitive element of the field (Fig.3 with associated text and Col.10, lines 1-7).
The prior arts of record fail to either disclose or sufficiently suggest the combination features as claimed and arranged by applicant. Although the above references teach similar aspects of the independent claims 1 and 10-12, none of these references individually or in reasonable combination discloses all the limitations as claimed in the independent claims and each of these independent claims as a whole is not obvious over these prior arts. Therefore, independent claims 1 and 10-12 are allowable over the prior arts of record and dependent claims are allowable by virtue of their dependence on the independent claims.
Prior Art of Record
8. The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure: see attached PTO-892 Notice of References Cited.
Conclusion
9. Any inquiry concerning this communication or earlier communications from the examiner should be directed to THANH T. LE whose telephone number is (571)270-0279. The examiner can normally be reached on Monday-Friday 8:00 am - 4:30 pm EST.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Farid Homayounmehr can be reached on 571-272-3739. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/THANH T LE/Primary Examiner, Art Unit 2495