Integer Reconstruction Public-Key Encryption

In [AJPS18], Aggarwal, Joux, Prakash & Santha described an elegant public-key encryption (\(\mathsf {AJPS}\)-1) mimicking NTRU over the integers. This algorithm relies on the properties of Mersenne primes instead of polynomial rings.

A later ePrint [BCGN17] by Beunardeau et al. revised \(\mathsf {AJPS}\)-1’s initial security estimates. While lower than initially thought, the best known attack on \(\mathsf {AJPS}\)-1 still seems to leave the defender with an exponential advantage over the attacker [dBDJdW17]. However, this lower exponential advantage implies enlarging \(\mathsf {AJPS}\)-1’s parameters. This, plus the fact that \(\mathsf {AJPS}\)-1 encodes only a single plaintext bit per ciphertext, made \(\mathsf {AJPS}\)-1 impractical. In a recent update, Aggarwal et al. overcame this limitation by extending \(\mathsf {AJPS}\)-1’s bandwidth. This variant (\(\mathsf {AJPS}\hbox {-}\mathsf {ECC}\)) modifies the definition of the public-key and relies on error-correcting codes.

This paper presents a different high-bandwidth construction. By opposition to \(\mathsf {AJPS}\hbox {-}\mathsf {ECC}\), we do not modify the public-key, avoid using error-correcting codes and use backtracking to decrypt. The new algorithm is orthogonal to \(\mathsf {AJPS}\hbox {-}\mathsf {ECC}\) as both mechanisms may be concurrently used in the same ciphertext and cumulate their bandwidth improvement effects. Alternatively, we can increase \(\mathsf {AJPS}\hbox {-}\mathsf {ECC}\)’s information rate by a factor of 26 for the parameters recommended in [AJPS18].

The obtained bandwidth improvement and the fact that encryption and decryption are reasonably efficient, make our scheme an interesting post-quantum candidate.

1. 1.

   A, B or \(A,B_1,B_2\).

2. 2.

   Except W.

3. 3.

   Note that in AJPS-1/ECC given G one can compute F and vice versa.

4. 4.

   Where \(\mathcal {H},\mathcal {H}'\)s are hash functions and \(\mathcal {F}\) is a block-cipher.

5. 5.

   Note that \(\mathcal {B}_1(W,\emptyset ,0)=\mathcal {B}_2(W,\emptyset ,0,\text{ ID })\).

6. 6.

   Link \(B_0,\ldots ,B_{t-1}\) in a way allowing the recovery of all the \(B_i\) if one of them is known (e.g. define \(B_i=\mathcal {F}_i(\text{ seed })\) where \(\mathcal {F}_k(m)\) is a block-cipher encrypting into \(\mathfrak {H}_{n,h}\)). Use the \(A_i\) to transport entropy or information. One successful decryption reveals the seed \(\Rightarrow \) open all the \(B_i\)s \(\Rightarrow \) all the t information containers \(A_i\).

7. 7.

   Take F, G coprime in \(\mathsf {Setup}\).

8. 8.

   Again, “natural” \(\mathtt{11}\)s may be already present in the LSBs of \(\omega \), \(\mathtt{11}+\mathtt{01}\) may destroy an \(\mathtt{11}\), \(\mathtt{10}+\mathtt{01}\) may create fake \(\mathtt{11}\)s etc.

9. 9.

   ePrint version 20170530:072202.

10. 10.

    We consider m to be beyond exhaustive search, typically 160 bits.

11. 11.

    Note that reading is circular i.e. wrapping around \(CG \bmod p\).

12. 12.

    The possibly rotated.

13. 13.

    Accidental similar-size prime factors may come from \(AF+GB\) as well, but those are few and hence easy to filter.

14. 14.

    Note that as backtracking proceeds the SNR improves. In this paper SNR stands for the SNR at the beginning of the backtracking process.

15. 15.

    i.e. where the sender encrypts by \(C\leftarrow Lm+B \bmod p\) this is insecure) or a similar trick.

The authors thank Waïss Azizian, Sarah Houdaigoui and Qu\(\acute{\hat{\text {o}}}\)c Tún Lê for the development and the simulation of different backtracking strategies.

Authors and Affiliations

1. Département d’informatique de l’ENS, ENS, CNRS, PSL University, 45 rue d’Ulm, 75230, Paris Cedex 05, France

   David Naccache

2. Department of Computing, The Hong Kong Polytechnic University (PolyU), Hung Hom, Hong Kong

   Houda Ferradi

Corresponding author

Correspondence to Houda Ferradi .

Editors and Affiliations

1. Fujian Normal University, Fuzhou, China

   Yi Mu

2. Singapore Management University, Singapore, Singapore

   Robert H. Deng

3. Fujian Normal University, Fuzhou, China

   Xinyi Huang

A Appendix: A Broken Scheme Target for Repair

While designing the algorithms in this paper we broke the following variant that we mention here as a fixing target. Let R be a secret n-bit number of the form: \(R\leftarrow \text{ random }|v_\ell |\text{ random }\) where \(v_{\ell }\) is defined as in Pattern identification, and define the auxiliary public-key \(L \leftarrow R/G\bmod p\). Note that this modifies the complexity assumption on which the scheme rests.

Encrypt by \(C\leftarrow AH+B+Lm\bmod p\) and decrypt by \(W\leftarrow GC=AF+GB+Rm \bmod p\). This offers a (noisy) visibility window on m allowing to extract and error-correct m.

The problem here is the equation defining L from which G can be revealed using LLL. It is unclear if this can be fixed using modifications in the encryption process and/or in parameter sizes. It is also interesting to determine if secure H-less variants^{Footnote 15} can be designed.

Assuming that the above could be repaired, the following is for readers fond of dangerous games.

A dangerous game, that we do not recommend, reduces noise in the visibility window. If A, B, G, F are generated in a biased way by shifting more Hamming weight into the MSBs and the LSBs as shown in Fig. 5, then the result of the multiplication modulo p of two such numbers results in a number of the form shown in Figs. 6 and 7. Those densities are illustrated in Figs. 8 and 9. This reduces the noise in the reading window and allows an easier recovery of m. It must be stressed that this increases the vulnerability of the public-key to the partition attacks of [BCGN17] as the attacker can better zoom on the information-rich part of F and G. This might be compensated by a higher h. Note that weight shifting does not necessarily need to be similar in all four variables A, B, F, G and that several weight shifting schemes are circularly equivalent because of the multiplication modulo p.

Unbalanced weight of A, B, F, G before multiplication.

Full size image

Unbalanced weight of \(AF\bmod p\) and \(BG\bmod p\) after multiplication.

Full size image

Unbalanced weight of \(AF+BG\bmod p\) after addition.

Full size image

Unbalanced A and F for \(\{n,h,\varDelta \}=\{2^{14},32,6\}\).

Full size image

Unbalanced \(AF\bmod p\) for \(\{n,h,\varDelta \}=\{2^{14},32,6\}\). Note the relatively lower dot density at the middle of the diagram.

Full size image

Reprints and permissions

© 2019 Springer Nature Switzerland AG

Policies and ethics