iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10623-022-01075-7
A gapless code-based hash proof system based on RQC and its applications | Designs, Codes and Cryptography Skip to main content
Springer Nature Link
Log in

A gapless code-based hash proof system based on RQC and its applications

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

Cramer and Shoup introduced at Eurocrypt’02 the concept of hash proof system, also designated as smooth projective hash functions. Since then, they have found several applications, from building CCA-2 encryption as they were initially created for, to being at the core of several authenticated key exchange or even allowing witness encryption. In the post-quantum setting, the very few candidates use a language based on ciphertexts to build their hash proof system. This choice seems to inherently introduce a gap, as some elements outside the language could not be distinguish from those in the language. This creates a lawless zone, where an adversary can possibly mount an undetectable attack, particularly problematic when trying to prove security in the UC framework (Canetti in A new paradigm for cryptographic protocols. In: 42nd 980 FOCS. IEEE Computer Society Press, pp. 136–145). We show that this gap could be completely withdrawn using code-based cryptography. Starting from RQC (Aguilar-Melchor et al in Rank quasi-cyclic (RQC)), a candidate selected for the second round of the National Institute of Standards and Technology (NIST) post-quantum cryptography standardization project, we show how to build such a hash proof system from code-based cryptography and present a way, based on a proof of knowledge, to fully negate the gap. We propose two applications of our construction, a witness encryption scheme and a password authenticated key exchange (PAKE).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. possibly depending on the word W

References

  1. Abdalla M., Benhamouda F., Pointcheval D.: Disjunctions for hash proof systems: New constructions and applications. In: Oswald E., Fischlin M. (eds.) EUROCRYPT 2015 Part II, vol. 9057 of LNCS, pp. 69–100. Springer, Heidelberg (2015).

    Google Scholar 

  2. Abdalla M., Chevalier C., Pointcheval D.: Smooth projective hashing for conditionally extractable commitments. In: Halevi S. (ed.) CRYPTO 2009, vol. 5677 of LNCS, pp. 671–689. Springer, Heidelberg (2009).

    Chapter  Google Scholar 

  3. Aguilar-Melchor C., Aragon N., Bettaieb S., Bidoux L., Blazy O., Bos J., Deneuville J.-C., Gaborit P., Persichetti E., Robert J.-M., Véron P., Zémor G. Hamming quasi-cyclic (HQC).

  4. Aguilar-Melchor C., Aragon N., Bettaieb S., Bidoux L., Blazy O., Couvreur A., Deneuville J.-C., Gaborit P., Hauteville A., Zémor G.: Rank quasi-cyclic (RQC)

  5. Aguilar-Melchor C., Blazy O., Deneuville J.-C., Gaborit P., Zémor G.: Efficient encryption from random quasi-cyclic codes. IEEE Trans. Inf. Theory 64(5), 3927–3943 (2018).

    Article  MathSciNet  MATH  Google Scholar 

  6. Alamélou Q., Blazy O., Cauchie S., Gaborit P.: A practical group signature scheme based on rank metric. In International Workshop on the Arithmetic of Finite Fields, pp. 258–275. Springer (2016)

  7. Alekhnovich, M.: More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (2003), IEEE, pp. 298–307.

  8. Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.-P.: A new algorithm for solving the rank syndrome decoding problem. In 2018 IEEE International Symposium on Information Theory (ISIT) (2018), IEEE, pp. 2421–2425.

  9. Bardet, M., Briaud, P., Bros, M., Gaborit, P., Neiger, V., Ruatta, O., Tillich, J.-P.: An algebraic attack on rank metric code-based cryptosystems. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2020), Springer, pp. 64–93.

  10. Bardet, M., Bros, M., Cabarcas, D., Gaborit, P., Perlner, R., Smith-Tone, D., Tillich, J.-P., Verbel, J.: Improvements of algebraic attacks for solving the rank decoding and minrank problems. In International Conference on the Theory and Application of Cryptology and Information Security (2020), Springer, pp. 507–536.

  11. Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated key exchange secure against dictionary attacks. In EUROCRYPT 2000 (May 2000), B. Preneel, Ed., vol. 1807 of LNCS, Springer, Heidelberg, pp. 139–155.

  12. Bellovin, S. M., and Merritt, M.: Encrypted key exchange: Password-based protocols secure against dictionary attacks. In 1992 IEEE Symposium on Security and Privacy (May 1992), IEEE Computer Society Press, pp. 72–84.

  13. Benhamouda, F.: Diverse modules and zero-knowledge. PhD thesis, PSL Research University - ENS, July 2016.

  14. Benhamouda, F., Blazy, O., Chevalier, C., Pointcheval, D., Vergnaud, D.: New techniques for SPHFs and efficient one-round PAKE protocols. In CRYPTO 2013, Part I (Aug. 2013), R. Canetti and J. A. Garay, Eds., vol. 8042 of LNCS, Springer, Heidelberg, pp. 449–475.

  15. Benhamouda, F., Blazy, O., Ducas, L., and Quach, W.: Hash proof systems over lattices revisited. In PKC 2018, Part II (Mar. 2018), M. Abdalla and R. Dahab, Eds., vol. 10770 of LNCS, Springer, Heidelberg, pp. 644–674.

  16. Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory 24, 3 (1978), 384–386.

  17. Blazy, O., Chevalier, C.: Generic construction of UC-secure oblivious transfer. In ACNS 15 (June 2015), T. Malkin, V. Kolesnikov, A. B. Lewko, and M. Polychronakis, Eds., vol. 9092 of LNCS, Springer, Heidelberg, pp. 65–86.

  18. Blazy, O., Chevalier, C., Germouty, P.: Adaptive oblivious transfer and generalization. In ASIACRYPT 2016, Part II (Dec. 2016), J. H. Cheon and T. Takagi, Eds., vol. 10032 of LNCS, Springer, Heidelberg, pp. 217–247.

  19. Blazy, O., Chevalier, C., Vu, Q. H.: Post-quantum UC-secure oblivious transfer in the standard model with adaptive corruptions. In Proceedings of the 14th International Conference on Availability, Reliability and Security (2019), pp. 1–6.

  20. Canetti, R.: Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd FOCS (Oct. 2001), IEEE Computer Society Press, pp. 136–145.

  21. Chen, K.: A new identification algorithm. In Cryptography: Policy and Algorithms (Berlin, Heidelberg, 1996), E. Dawson and J. Golić, Eds., Springer Berlin Heidelberg, pp. 244–249.

  22. Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In EUROCRYPT 2002 (Apr. / May 2002), L. R. Knudsen, Ed., vol. 2332 of LNCS, Springer, Heidelberg, pp. 45–64.

  23. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO’86 (Aug. 1987), A. M. Odlyzko, Ed., vol. 263 of LNCS, Springer, Heidelberg, pp. 186–194.

  24. Gabidulin E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985).

    MathSciNet  MATH  Google Scholar 

  25. Gaborit, P., Murat, G., Ruatta, O., Zémor, G.: Low rank parity check codes and their application to cryptography. In Proceedings of the Workshop on Coding and Cryptography WCC (2013), vol. 2013.

  26. Gaborit P., Ruatta O., Schrek J.: On the complexity of the rank syndrome decoding problem. IEEE Transactions on Information Theory 62(2), 1006–1019 (2015).

    Article  MathSciNet  MATH  Google Scholar 

  27. Gaborit, P., Schrek, J., Zémor, G.: Full cryptanalysis of the Chen identification protocol. In International Workshop on Post-Quantum Cryptography (2011), Springer, pp. 35–50.

  28. Gaborit P., Zémor G.: On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Transactions on Information Theory 62(12), 7245–7252 (2016).

    Article  MathSciNet  MATH  Google Scholar 

  29. Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In 45th ACM STOC (June 2013), D. Boneh, T. Roughgarden, and J. Feigenbaum, Eds., ACM Press, pp. 467–476.

  30. Gennaro R., Lindell Y.: A framework for password-based authenticated key exchange. ACM Transactions on Information and System Security 9(2), 181–234 (2006).

    Article  MATH  Google Scholar 

  31. Halevi S., Kalai Y.T.: Smooth projective hashing and two-message oblivious transfer. Journal of Cryptology 25(1), 158–193 (2012).

    Article  MathSciNet  MATH  Google Scholar 

  32. Hofheinz, D., Hövelmanns, K., Kiltz, E.: A modular analysis of the Fujisaki-Okamoto transformation. In TCC 2017, Part I (Nov. 2017), Y. Kalai and L. Reyzin, Eds., vol. 10677 of LNCS, Springer, Heidelberg, pp. 341–371.

  33. Kalai, Y. T.: Smooth projective hashing and two-message oblivious transfer. In EUROCRYPT 2005 (May 2005), R. Cramer, Ed., vol. 3494 of LNCS, Springer, Heidelberg, pp. 78–95.

  34. Katz, J., Vaikuntanathan, V.: Round-optimal password-based authenticated key exchange. In TCC 2011 (Mar. 2011), Y. Ishai, Ed., vol. 6597 of LNCS, Springer, Heidelberg, pp. 293–310.

  35. Katz, J., Vaikuntanathan, V.: Smooth projective hashing and password-based authenticated key exchange from lattices. In ASIACRYPT 2009 (Dec. 2009), M. Matsui, Ed., vol. 5912 of LNCS, Springer, Heidelberg, pp. 636–652.

  36. Kawachi, A., Tanaka, K., Xagawa, K.: Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In International Conference on the Theory and Application of Cryptology and Information Security (2008), Springer, pp. 372–389.

  37. Ling, S., Nguyen, K., Stehlé, D., Wang, H.: Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In PKC 2013 (Feb. / Mar. 2013), K. Kurosawa and G. Hanaoka, Eds., vol. 7778 of LNCS, Springer, Heidelberg, pp. 107–124.

  38. Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd ACM STOC (May 1990), ACM Press, pp. 427–437.

  39. Ore O.: On a special class of polynomials. Transactions of the American Mathematical Society 35(3), 559–584 (1933).

    Article  MathSciNet  MATH  Google Scholar 

  40. Persichetti, E.: Code-based public-key encryption resistant to key leakage. In International Conference on Availability, Reliability, and Security (2013), Springer, pp. 44–54.

  41. Pointcheval, D., Stern, J.: Security proofs for signature schemes. In International Conference on the Theory and Applications of Cryptographic Techniques (1996), Springer, pp. 387–398.

  42. Stern J.: A new paradigm for public key identification. IEEE Transactions on Information Theory 42(6), 1757–1768 (1996).

    Article  MathSciNet  MATH  Google Scholar 

  43. Véron P.: Improved identification schemes based on error-correcting codes. Applicable Algebra in Engineering, Communication and Computing 8(1), 57–69 (1997).

    Article  MathSciNet  MATH  Google Scholar 

  44. Zhang, J., Yu, Y.: Two-round PAKE from approximate SPH and instantiations from lattices. In ASIACRYPT 2017, Part III (Dec. 2017), T. Takagi and T. Peyrin, Eds., vol. 10626 of LNCS, Springer, Heidelberg, pp. 37–67.

Download references

Author information

Authors and Affiliations

  1. Worldline, 23 rue de la Pointe, 59139, Noyelles-les-Seclin, France

    Slim Bettaieb, Loïc Bidoux & Yann Connan

  2. University of Limoges, 123 Avenue Albert Thomas, 87000, Limoges, France

    Olivier Blazy & Philippe Gaborit

  3. Technology Innovation Institute, Abu Dhabi, UAE

    Loïc Bidoux

Authors
  1. Slim Bettaieb
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Loïc Bidoux
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Olivier Blazy
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yann Connan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Philippe Gaborit
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yann Connan.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue: On Coding Theory and Combinatorics: In Memory of Vera Pless”

Appendices

Appendices

1.1 Appendix 1: Proofs of theorem 3

The protocol depicted in Fig. 5 is a statistical zero-knowledge proof in the random oracle model.

Proof

The proof uses techniques in the same spirit of those in [36, 37, 42]. Therefore, we construct a simulator \({\mathsf {S}}\) which, given the public inputs of the protocol and interacting with a cheating verifier \(\widetilde{{\mathsf {V}}}\), outputs a simulated transcript with probability \(\frac{2}{3}\) that is statistically close to the distribution of the real transcript. The public inputs are \(({\mathbf {H}}, \varvec{c})\), the simulator \({\mathsf {S}}\) starts by choosing a random \({\bar{ch}} \in \{0, 1, 2\}\), which is a prediction of the challenge that \(\widetilde{{\mathsf {V}}}\) will not choose.

\(\diamondsuit \) Case \({\bar{ch}} = 0\):

\({\mathsf {S}}\) samples:

$$\begin{aligned} \begin{array}{lll} \mathbf {Q}^\prime {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_m(q)&{} \mathbf {P}^{\prime }_1, \mathbf {P}^{\prime }_2, \mathbf {P}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_n(q); &{} \mathbf {P}^{\prime }_4 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_k(q); \\ \varvec{v}^{\prime }_1, \varvec{v}^{\prime }_2, \varvec{v}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathscr {V}}; &{} \varvec{v}^{\prime }_4 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; \\ (\varvec{r}^{\prime }_1, \varvec{r}^{\prime }_2, \varvec{r}^{\prime }_3) {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathfrak {S}}_{w}^{3}({\mathscr {V}}); &{} \varvec{r}^{\prime }_4 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; &{} \varvec{z}^{\prime }_1, \varvec{z}^{\prime }_2, \varvec{z}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}1^{\mathfrak {K}}; \\ \end{array} \end{aligned}$$

and sends the commitment CMT:=\((cm^{\prime }_1 ~|~ cm^{\prime }_2 ~|~ cm^{\prime }_3)\) to \(\widetilde{{\mathsf {V}}}\), where:

  • \(cm^{\prime }_1 = \text {Hash}(\mathbf {Q}^{\prime }~|~\Vert _{i=1}^{4} \mathbf {P}^{\prime }_i ~|~ \sum _{i=1}^{4} {\mathbf {H}}_i ({\varvec{v}^{\prime }_i}^\top + {\varvec{r}^{\prime }_i}^\top ) ~|~ \varvec{z}^{\prime }_1)\)

  • \(cm^{\prime }_2 = \text {Hash}(\Vert _{i=1}^{4} \mathbf {Q}^\prime * \varvec{v}^{\prime }_i \mathbf {P}^{\prime }_i ~|~ \varvec{z}^{\prime }_2)\)

  • \(cm^{\prime }_3 = \text {Hash}(\Vert _{i=1}^{4} \mathbf {Q}^\prime * (\varvec{v}^\prime _i + \varvec{r}^\prime _i)\mathbf {P}^\prime _i ~|~ \varvec{z}^{\prime }_3)\)

Receiving a challenge ch from \(\widetilde{{\mathsf {V}}}\), the simulator \({\mathsf {S}}\) responds as follows:

  • If \(ch = 0\), Output \(\perp \) and abort.

  • If \(ch = 1\), Send RSP:=\((\mathbf {Q}^\prime ~|~ \Vert _{i=1}^4 \mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^4 \varvec{v}^\prime _i + \varvec{r}^\prime _i ~|~ \varvec{z}^{\prime }_1 ~|~ \varvec{z}^{\prime }_3)\)

  • If \(ch = 2\), Send RSP:=\((\Vert _{i=1}^4 \mathbf {Q}^{\prime } * \varvec{v}^{\prime }_i\mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^4 \mathbf {Q}^{\prime } * \varvec{r}^{\prime }_i\mathbf {P}^{\prime }_i ~|~ \varvec{z}^{\prime }_2 ~|~ \varvec{z}^{\prime }_3)\)

\(\diamondsuit \) Case \({\bar{ch}} = 1\):

\({\mathsf {S}}\) samples:

$$\begin{aligned} \begin{array}{lll} \mathbf {Q}^\prime {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_m(q); &{} \mathbf {P}^{\prime }_1, \mathbf {P}^{\prime }_2, \mathbf {P}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_n(q); &{} \mathbf {P}^{\prime }_4 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_k(q); \\ \varvec{v}^{\prime }_1, \varvec{v}^{\prime }_2, \varvec{v}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathscr {V}}; &{} \varvec{v}^{\prime }_4 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; \\ (\varvec{r}^{\prime }_1, \varvec{r}^{\prime }_2, \varvec{r}^{\prime }_3) {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathfrak {S}}_{w}^{3}({\mathscr {V}}); &{} \varvec{r}^{\prime }_4 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; &{} \varvec{z}^{\prime }_1, \varvec{z}^{\prime }_2, \varvec{z}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}1^{\mathfrak {K}}; \\ \end{array} \end{aligned}$$

and sends the commitment CMT:=\((cm^{\prime }_1 ~|~ cm^{\prime }_2 ~|~ cm^{\prime }_3)\) to \(\widetilde{{\mathsf {V}}}\), where:

  • \(cm^{\prime }_1 = \text {Hash}(\mathbf {Q}^{\prime }~|~ \Vert _{i=1}^{4} \mathbf {P}^{\prime }_i ~|~ \sum _{i=1}^{4} {\mathbf {H}}_i {\varvec{v}^{\prime }_i}^\top ~|~ \varvec{z}^{\prime }_1)\)

  • \(cm^{\prime }_2 = \text {Hash}(\Vert _{i=1}^{4} \mathbf {Q}^\prime * \varvec{v}^{\prime }_i \mathbf {P}^{\prime }_i ~|~ \varvec{z}^{\prime }_2)\)

  • \(cm^{\prime }_3 = \text {Hash}(\Vert _{i=1}^{4} \mathbf {Q}^\prime * (\varvec{v}^\prime _i + \varvec{r}^\prime _i)\mathbf {P}^\prime _i ~|~ \varvec{z}^{\prime }_3)\)

Receiving a challenge ch from \(\widetilde{{\mathsf {V}}}\), the simulator \({\mathsf {S}}\) responds as follows:

  • If \(ch = 0\),  Send RSP:=\((\mathbf {Q}^\prime ~|~ \Vert _{i=1}^4 \mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^4 \varvec{v}^{\prime }_i ~|~ \varvec{z}^{\prime }_1 ~|~ \varvec{z}^{\prime }_2)\)

  • If \(ch = 1\),  Output \(\perp \) and abort.

  • If \(ch = 2\),  Send RSP:=\((\Vert _{i=1}^4 \mathbf {Q}^{\prime } * \varvec{v}^{\prime }_i\mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^4 \mathbf {Q}^{\prime } * \varvec{r}^{\prime }_i\mathbf {P}^{\prime }_i ~|~ \varvec{z}^{\prime }_2 ~|~ \varvec{z}^{\prime }_3)\)

\(\diamondsuit \) Case \({\bar{ch}} = 2\):

Using linear algebra, \({\mathsf {S}}\) computes a vector \(\varvec{r}^\prime = (\varvec{r}^{\prime }_1, \varvec{r}^{\prime }_2, \varvec{r}^{\prime }_3, \varvec{r}^{\prime }_4)\), such that \({\mathbf {H}}{\varvec{r}^\prime }^{\top } = \varvec{c}^\top \).

Next, it samples:

$$\begin{aligned} \begin{array}{lll} \mathbf {Q}^\prime {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_m(q); &{} \mathbf {P}^{\prime }_1, \mathbf {P}^{\prime }_2, \mathbf {P}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_n(q); &{} \mathbf {P}^{\prime }_4 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_k(q); \\ \varvec{v}^{\prime }_1, \varvec{v}^{\prime }_2, \varvec{v}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathscr {V}}; &{} \varvec{v}^{\prime }_4 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; &{} \varvec{z}^{\prime }_1, \varvec{z}^{\prime }_2, \varvec{z}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}1^{\mathfrak {K}}; \\ \end{array} \end{aligned}$$

and sends the commitment CMT:=\((cm^{\prime }_1 ~|~ cm^{\prime }_2 ~|~ cm^{\prime }_3)\) to \(\widetilde{{\mathsf {V}}}\), where:

  • \(cm^{\prime }_1 = \text {Hash}(\mathbf {Q}^{\prime } ~|~ \Vert _{i=1}^{4} \mathbf {P}^{\prime }_i ~|~ \sum _{i=1}^{4} {\mathbf {H}}_i {\varvec{v}^{\prime }_i}^\top ~|~ \varvec{z}^{\prime }_1)\)

  • \(cm^{\prime }_2 = \text {Hash}(\Vert _{i=1}^{4} \mathbf {Q}^\prime * \varvec{v}^{\prime }_i \mathbf {P}^{\prime }_i ~|~ \mathbf {P}^{\prime }_4 ~|~ \varvec{z}^{\prime }_2)\)

  • \(cm^{\prime }_3 = \text {Hash}(\Vert _{i=1}^{4} \mathbf {Q}^\prime * (\varvec{v}^\prime _i + \varvec{r}^\prime _i)\mathbf {P}^\prime _i ~|~ \varvec{z}^{\prime }_3)\)

Receiving a challenge ch from \(\widetilde{{\mathsf {V}}}\), the simulator \({\mathsf {S}}\) responds as follows:

  • If \(ch = 0\),  Send RSP:=\((\mathbf {Q}^\prime ~|~ \Vert _{i=1}^4 \mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^4 \varvec{v}^{\prime }_i ~|~ \varvec{z}^{\prime }_1 ~|~ \varvec{z}^{\prime }_2)\)

  • If \(ch = 1\), Send RSP:=\((\mathbf {Q}^\prime ~|~ \Vert _{i=1}^4 \mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^4 \varvec{v}^{\prime }_i + \varvec{r}^{\prime }_i ~|~ \varvec{z}_1 ~|~ \varvec{z}_3)\)

  • If \(ch = 2\),  Output \(\perp \) and abort.

It can be seen that the probability that the simulator outputs \(\perp \) is close to \(\frac{1}{3}\). Additionally, when the simulator does not halt, the distribution of the generated transcripts is statistically close to the distribution of the real transcript when the hash function is modeled as a random oracle. Therefore, we have build a simulator that succeeds the protocol with probability \(\frac{2}{3}\) without having any information about the secret values. \(\square \)

1.2 Appendix 2: Proof of theorem 4

If there exists a PPT cheating prover \(\widetilde{{\mathsf {P}}}\) who convinces the verifier with probability \(\frac{2}{3} + \varepsilon \), where \(\varepsilon \) is non-negligible, then there exists a PPT knowledge extractor who outputs with overwhelming probability a tuple \((\varvec{y}_1, \varvec{y}_2, \varvec{y}_3, \varvec{y}_4)\) such that \(\sum _{i=1}^4{\mathbf {H}}_i\varvec{y}^{\top }_i = \varvec{c}^\top \) with \((\varvec{y}_1, \varvec{y}_2, \varvec{y}_3)\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\).

Proof

We show how to construct a knowledge extractor \({\mathscr {K}}\). Let \(\widetilde{{\mathsf {P}}}\) be the cheating prover who convinces the verifier with probability \(\frac{2}{3} + \varepsilon \). Applying the technique of Véron [43], that rewinds \(\widetilde{{\mathsf {P}}}\) a number of times polynomial in \(\frac{1}{\varepsilon }\), the knowledge extractor can obtain with overwhelming probability a commitment, for which \(\widetilde{{\mathsf {P}}}\) can correctly answer all three challenges. Therefore, \({\mathscr {K}}\) obtains the following equations:

  • \(cm_1 = \text {Hash}(\dot{\mathbf {Q}}~|~\Vert _{i=1}^4 \dot{\mathbf {P}_i} ~|~ \sum _{i=1}^4 {\mathbf {H}}_i\dot{\varvec{v}_i}^\top ) = \text {Hash}(\ddot{\mathbf {Q}}~|~ \Vert _{i=1}^4 \ddot{\mathbf {P}_i} ~|~ \sum _{i=1}^4 {\mathbf {H}}_i\ddot{\varvec{v}_i}^\top -\varvec{c}^\top )\)

  • \(cm_2 = \text {Hash}(\Vert _{i=1}^4 \dot{\mathbf {Q}} * \dot{\varvec{v}_i} \dot{\mathbf {P}_i}) = \text {Hash}(\Vert _{i=1}^4 \tilde{\varvec{v}_i})\)

  • \(cm_3 = \text {Hash}(\Vert _{i=1}^4 \ddot{\mathbf {Q}} * \ddot{\varvec{v}_i}\ddot{\mathbf {P}_i}) = \text {Hash}(\Vert _{i=1}^4 \tilde{\varvec{v}_i} + \tilde{\varvec{r}_i})\)

  • \((\tilde{\varvec{r}_1}, \tilde{\varvec{r}_2}, \tilde{\varvec{r}_3})\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\).

Since Hash is modeled as a random oracle (an adversary cannot find a collision on it), it follows that:

  • \(\dot{\mathbf {Q}} = \ddot{\mathbf {Q}}\) and \(\forall i \in [\![1,4]\!],~ \dot{\mathbf {P}_i} = \ddot{\mathbf {P}_i}\) and \(\sum _{i=1}^4 {\mathbf {H}}_i\dot{\varvec{v}_i}^\top = \sum _{i=1}^4 {\mathbf {H}}_i\ddot{\varvec{v}_i}^\top - \varvec{c}^\top \)

  • \(\forall i \in [\![1,4]\!],~ \dot{\mathbf {Q}} * \dot{\varvec{v}_i}\dot{\mathbf {P}_i} = \tilde{\varvec{v}_i},~ \ddot{\mathbf {Q}} * \ddot{\varvec{v}_i}\ddot{\mathbf {P}_i} = \tilde{\varvec{v}_i} + \tilde{\varvec{r}_i}\)

Let \(i \in [\![1,4]\!]\). We have \(\ddot{\mathbf {Q}} * \ddot{\varvec{v}_i}\ddot{\mathbf {P}_i} = \dot{\mathbf {Q}} * \dot{\varvec{v}_i} \dot{\mathbf {P}_i} = \tilde{\varvec{v}_i} + \tilde{\varvec{r}_i}\). It follows that \(\dot{\mathbf {Q}} * (\ddot{\varvec{v}_i} - \dot{\varvec{v}_i}) \dot{\mathbf {P}_i} = \tilde{\varvec{r}_i}\), which implies that \((\ddot{\varvec{v}_i} - \dot{\varvec{v}_i}) = \dot{\mathbf {Q}}^{-1} * \tilde{\varvec{r}_i} \dot{\mathbf {P}_i}^{-1}\).

\(\forall i \in [\![1,4]\!],~ (\ddot{\varvec{v}_i} - \dot{\varvec{v}_i}) = \dot{\mathbf {Q}}^{-1} * \tilde{\varvec{r}_i} \dot{\mathbf {P}_i}^{-1}\)

Since \(\dot{\mathbf {Q}}^{-1}\in {{\mathsf {G}}}{{\mathsf {L}}}_m(q)\) and \(\dot{\mathbf {P}_i}^{-1}\in {{\mathsf {G}}}{{\mathsf {L}}}_m(q)\), we have \((\ddot{\varvec{v}_1} - \dot{\varvec{v}_1}, \ddot{\varvec{v}_2} - \dot{\varvec{v}_2}, \ddot{\varvec{v}_3} - \dot{\varvec{v}_3}) \in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\). Therefore, the knowledge extractor \({\mathscr {K}}\) obtains vectors \(\varvec{y}_i = \ddot{\varvec{v}_i} - \dot{\varvec{v}_i}\), with \(i \in [\![1,4]\!]\), such that: \(\sum _{i=1}^4 {\mathbf {H}}_i\varvec{y}_i^\top = \varvec{c}^\top \) and \((\varvec{y}_1, \varvec{y}_2, \varvec{y}_3)\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\). \(\square \)

1.3 Appendix 3: Proof of RQC ciphertexts validity for identical plaintexts

Fig. 8
figure 8

Proof of RQC ciphertexts validity for identical plaintexts

Full size image

1.4 Appendix 4: Proof of theorem 5

The protocol depicted in figure 8 is a statistical zero-knowledge proof in the random oracle model.

Proof

The proof uses techniques in the same spirit of those in [36, 37, 42]. Therefore, we construct a simulator \({\mathsf {S}}\) which is given the public inputs of the protocol and interacting with a cheating verifier \(\widetilde{{\mathsf {V}}}\), outputs a simulated transcript with probability \(\frac{2}{3}\) that is statistically close to the distribution of the real transcript. The public inputs are \(({\mathbf {H}}, \varvec{c})\), the simulator \({\mathsf {S}}\) starts by choosing a random \({\bar{ch}} \in \{0, 1, 2\}\), which is a prediction of the challenge that \(\widetilde{{\mathsf {V}}}\) will not choose.

\(\diamondsuit \) Case \({\bar{ch}} = 0\):

\({\mathsf {S}}\) samples:

$$\begin{aligned} \begin{array}{lll} \mathbf {Q}^\prime {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_m(q); &{} \mathbf {P}^{\prime }_1, \mathbf {P}^{\prime }_2, \dots , \mathbf {P}^{\prime }_6 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_n(q); &{} \mathbf {P}^{\prime }_7 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_k(q); \\ \varvec{v}^{\prime }_1, \varvec{v}^{\prime }_2, \dots , \varvec{v}^{\prime }_6 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathscr {V}}; &{} \varvec{v}^{\prime }_7 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; &{}\varvec{z}^{\prime }_1, \varvec{z}^{\prime }_2, \varvec{z}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}1^{\mathfrak {K}}; \\ (\varvec{r}^{\prime }_1, \varvec{r}^{\prime }_2, \varvec{r}^{\prime }_3)\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}}); &{} (\varvec{r}^{\prime }_4, \varvec{r}^{\prime }_5, \varvec{r}^{\prime }_6)\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}}); &{} \varvec{r}^{\prime }_7 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; \\ \end{array} \end{aligned}$$

and sends the commitment CMT:=\((cm^{\prime }_1 ~|~ cm^{\prime }_2 ~|~ cm^{\prime }_3)\) to \(\widetilde{{\mathsf {V}}}\), where:

  • \(cm^{\prime }_1 = \text {Hash}(\mathbf {Q}^{\prime }~|~\Vert _{i=1}^{7} \mathbf {P}^{\prime }_i ~|~ \sum _{i=1}^{7} {\mathbf {H}}_i ({\varvec{v}^{\prime }_i}^\top + {\varvec{r}^{\prime }_i}^\top ) ~|~ \varvec{z}^{\prime }_1)\)

  • \(cm^{\prime }_2 = \text {Hash}(\Vert _{i=1}^{7} \mathbf {Q}^\prime * \varvec{v}^{\prime }_i \mathbf {P}^{\prime }_i ~|~ \varvec{z}^{\prime }_2)\)

  • \(cm^{\prime }_3 = \text {Hash}(\Vert _{i=1}^{7} \mathbf {Q}^\prime * (\varvec{v}^\prime _i + \varvec{r}^\prime _i)\mathbf {P}^\prime _i ~|~ \varvec{z}^{\prime }_3)\)

Receiving a challenge ch from \(\widetilde{{\mathsf {V}}}\), the simulator \({\mathsf {S}}\) responds as follows:

  • If \(ch = 0\), Output \(\perp \) and abort.

  • If \(ch = 1\), Send RSP:=\((\mathbf {Q}^\prime ~|~ \Vert _{i=1}^7 \mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^7 \varvec{v}^\prime _i + \varvec{r}^\prime _i ~|~ \varvec{z}^{\prime }_1 ~|~ \varvec{z}^{\prime }_3)\)

  • If \(ch = 2\), Send RSP:=\((\Vert _{i=1}^7 \mathbf {Q}^{\prime } * \varvec{v}^{\prime }_i\mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^7 \mathbf {Q}^{\prime } * \varvec{r}^{\prime }_i\mathbf {P}^{\prime }_i ~|~ \varvec{z}^{\prime }_2 ~|~ \varvec{z}^{\prime }_3)\)

\(\diamondsuit \) Case \({\bar{ch}} = 1\)

\({\mathsf {S}}\) samples:

$$\begin{aligned} \begin{array}{lll} \mathbf {Q}^\prime {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_m(q); &{} \mathbf {P}^{\prime }_1, \mathbf {P}^{\prime }_2, \dots , \mathbf {P}^{\prime }_6 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_n(q); &{} \mathbf {P}^{\prime }_7 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_k(q); \\ \varvec{v}^{\prime }_1, \varvec{v}^{\prime }_2, \dots , \varvec{v}^{\prime }_6 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathscr {V}}; &{} \varvec{v}^{\prime }_7 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; &{} \varvec{z}^{\prime }_1, \varvec{z}^{\prime }_2, \varvec{z}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}1^{\mathfrak {K}};\\ (\varvec{r}^{\prime }_1, \varvec{r}^{\prime }_2, \varvec{r}^{\prime }_3)\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}}); &{} (\varvec{r}^{\prime }_4, \varvec{r}^{\prime }_5, \varvec{r}^{\prime }_6) \in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}}); &{} \varvec{r}^{\prime }_7 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; \\ \end{array} \end{aligned}$$

and sends the commitment CMT:=\((cm^{\prime }_1 ~|~ cm^{\prime }_2 ~|~ cm^{\prime }_3)\) to \(\widetilde{{\mathsf {V}}}\), where:

  • \(cm^{\prime }_1 = \text {Hash}(\mathbf {Q}^{\prime }~|~ \Vert _{i=1}^{7} \mathbf {P}^{\prime }_i ~|~ \sum _{i=1}^{7} {\mathbf {H}}_i {\varvec{v}^{\prime }_i}^\top ~|~ \varvec{z}^{\prime }_1)\)

  • \(cm^{\prime }_2 = \text {Hash}(\Vert _{i=1}^{7} \mathbf {Q}^\prime * \varvec{v}^{\prime }_i \mathbf {P}^{\prime }_i ~|~ \varvec{z}^{\prime }_2)\)

  • \(cm^{\prime }_3 = \text {Hash}(\Vert _{i=1}^{7} \mathbf {Q}^\prime * (\varvec{v}^\prime _i + \varvec{r}^\prime _i)\mathbf {P}^\prime _i ~|~ \varvec{z}^{\prime }_3)\)

Receiving a challenge ch from \(\widetilde{{\mathsf {V}}}\), the simulator \({\mathsf {S}}\) responds as follows:

  • If \(ch = 0\),  Send RSP:=\((\mathbf {Q}^\prime ~|~ \Vert _{i=1}^7 \mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^7 \varvec{v}^{\prime }_i ~|~ \varvec{z}^{\prime }_1 ~|~ \varvec{z}^{\prime }_2)\)

  • If \(ch = 1\),  Output \(\perp \) and abort.

  • If \(ch = 2\),  Send RSP:=\((\Vert _{i=1}^7 \mathbf {Q}^{\prime } * \varvec{v}^{\prime }_i\mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^7 \mathbf {Q}^{\prime } * \varvec{r}^{\prime }_i\mathbf {P}^{\prime }_i ~|~ \varvec{z}^{\prime }_2 ~|~ \varvec{z}^{\prime }_3)\)

\(\diamondsuit \) Case \({\bar{ch}} = 2\)

Using linear algebra, \({\mathsf {S}}\) computes a vector \(\varvec{r}^\prime = (\varvec{r}^{\prime }_1, \varvec{r}^{\prime }_2 \dots \varvec{r}^{\prime }_7)\), such that \({\mathbf {H}}{\varvec{r}^\prime }^{\top } = \varvec{c}^\top \).

Next, it samples:

$$\begin{aligned} \begin{array}{lll} \mathbf {Q}^\prime {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_m(q); &{} \mathbf {P}^{\prime }_1, \mathbf {P}^{\prime }_2, \dots , \mathbf {P}^{\prime }_6 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_n(q); &{} \mathbf {P}^{\prime }_7 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{{\mathsf {G}}}{{\mathsf {L}}}_k(q); \\ \varvec{v}^{\prime }_1, \varvec{v}^{\prime }_2, \dots , \varvec{v}^{\prime }_6 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathscr {V}}; &{} \varvec{v}^{\prime }_7 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}{\mathbb {F}}_{q^m}^k; &{} \varvec{z}^{\prime }_1, \varvec{z}^{\prime }_2, \varvec{z}^{\prime }_3 {\mathop {\leftarrow }\limits ^{{}_{~\$}}}1^{\mathfrak {K}}; \\ \end{array} \end{aligned}$$

and sends the commitment CMT:=\((cm^{\prime }_1 ~|~ cm^{\prime }_2 ~|~ cm^{\prime }_3)\) to \(\widetilde{{\mathsf {V}}}\), where:

  • \(cm^{\prime }_1 = \text {Hash}(\mathbf {Q}^{\prime } ~|~ \Vert _{i=1}^{7} \mathbf {P}^{\prime }_i ~|~ \sum _{i=1}^{7} {\mathbf {H}}_i {\varvec{v}^{\prime }_i}^\top ~|~ \varvec{z}^{\prime }_1)\)

  • \(cm^{\prime }_2 = \text {Hash}(\Vert _{i=1}^{7} \mathbf {Q}^\prime * \varvec{v}^{\prime }_i \mathbf {P}^{\prime }_i ~|~ \mathbf {P}^{\prime }_7 ~|~ \varvec{z}^{\prime }_2)\)

  • \(cm^{\prime }_3 = \text {Hash}(\Vert _{i=1}^{7} \mathbf {Q}^\prime * (\varvec{v}^\prime _i + \varvec{r}^\prime _i)\mathbf {P}^\prime _i ~|~ \varvec{z}^{\prime }_3)\)

Receiving a challenge ch from \(\widetilde{{\mathsf {V}}}\), the simulator \({\mathsf {S}}\) responds as follows:

  • If \(ch = 0\),  Send RSP:=\((\mathbf {Q}^\prime ~|~ \Vert _{i=1}^7 \mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^7 \varvec{v}^{\prime }_i ~|~ \varvec{z}^{\prime }_1 ~|~ \varvec{z}^{\prime }_2)\)

  • If \(ch = 1\),  Send RSP:=\((\mathbf {Q}^\prime ~|~ \Vert _{i=1}^7 \mathbf {P}^{\prime }_i ~|~ \Vert _{i=1}^7 \varvec{v}^{\prime }_i + \varvec{r}^{\prime }_i ~|~ \varvec{z}_1 ~|~ \varvec{z}_3)\)

  • If \(ch = 2\),  Output \(\perp \) and abort.

It can be seen that the probability that the simulator outputs \(\perp \) is close to \(\frac{1}{3}\). Additionally, when the simulator does not halt, the distribution of the generated transcripts is statistically close to the distribution of the real transcript when the hash function is modeled as a random oracle. Therefore, we have build a simulator that succeeds the protocol with probability \(\frac{2}{3}\) without having any information about the secret values.

\(\square \)

1.5 Appendix 5: Proof of theorem 6

If there exists a PPT cheating prover \(\widetilde{{\mathsf {P}}}\) who convinces the verifier with probability \(\frac{2}{3} + \varepsilon \), where \(\varepsilon \) is non-negligible, then there exists a PPT knowledge extractor who outputs with overwhelming probability a tuple \((\varvec{y}_1, \varvec{y}_2, \dots , \varvec{y}_7)\) such that \(\sum _{i=1}^{7}{\tilde{{\mathbf {H}}}}_{i}\varvec{y}^{\top }_{i} = \varvec{c}^{\top }\), \((\varvec{y}_{1}, \varvec{y}_2, \varvec{y}_3)\in {\mathfrak {S}}_{w_{r}}^{3}({\mathscr {V}})\) and \((\varvec{y}_4, \varvec{y}_5, \varvec{y}_6)\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\).

Proof

We show how to construct a knowledge extractor \({\mathscr {K}}\). Let \(\widetilde{{\mathsf {P}}}\) be the cheating prover who convinces the verifier with probability \(\frac{2}{3} + \varepsilon \). Applying the technique of Véron [43], that rewinds \(\widetilde{{\mathsf {P}}}\) a number of times polynomial in \(\frac{1}{\varepsilon }\), the knowledge extractor can obtain with overwhelming probability a commitment, for which \(\widetilde{{\mathsf {P}}}\) can correctly answer all three challenges. Therefore, \({\mathscr {K}}\) obtains the following equations:

  • \(cm_1 = \text {Hash}(\dot{\mathbf {Q}}~|~\Vert _{i=1}^7 \dot{\mathbf {P}_i} ~|~ \sum _{i=1}^7 {\tilde{{\mathbf {H}}}}_i\dot{\varvec{v}_i}^\top ) = \text {Hash}(\ddot{\mathbf {Q}}~|~ \Vert _{i=1}^7 \ddot{\mathbf {P}_i} ~|~ \sum _{i=1}^7 {\tilde{{\mathbf {H}}}}_i\ddot{\varvec{v}_i}^\top -\varvec{c}^\top )\)

  • \(cm_2 = \text {Hash}(\Vert _{i=1}^7 \dot{\mathbf {Q}} * \dot{\varvec{v}_i} \dot{\mathbf {P}_i}) = \text {Hash}(\Vert _{i=1}^7 \tilde{\varvec{v}_i})\)

  • \(cm_3 = \text {Hash}(\Vert _{i=1}^7 \ddot{\mathbf {Q}} * \ddot{\varvec{v}_i}\ddot{\mathbf {P}_i}) = \text {Hash}(\Vert _{i=1}^7 \tilde{\varvec{v}_i} + \tilde{\varvec{r}_i})\)

  • \((\tilde{\varvec{r}_1}, \tilde{\varvec{r}_2}, \tilde{\varvec{r}_3})\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\), \((\tilde{\varvec{r}_4}, \tilde{\varvec{r}_5}, \tilde{\varvec{r}_6})\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\).

Since Hash is modeled as a random oracle (an adversary cannot find a collision on it), it follows that:

  • \(\dot{\mathbf {Q}} = \ddot{\mathbf {Q}}\) and \(\forall i \in [\![1,7]\!],~ \dot{\mathbf {P}_i} = \ddot{\mathbf {P}_i}\) and \(\sum _{i=1}^7 {\tilde{{\mathbf {H}}}}_i\dot{\varvec{v}_i}^\top = \sum _{i=1}^4 {\tilde{{\mathbf {H}}}}_i\ddot{\varvec{v}_i}^\top - \varvec{c}^\top \)

  • \(\forall i \in [\![1,7]\!],~ \dot{\mathbf {Q}} * \dot{\varvec{v}_i}\dot{\mathbf {P}_i} = \tilde{\varvec{v}_i},~ \ddot{\mathbf {Q}} * \ddot{\varvec{v}_i}\ddot{\mathbf {P}_i} = \tilde{\varvec{v}_i} + \tilde{\varvec{r}_i}\)

Let \(i \in [\![1,7]\!]\). We have \(\ddot{\mathbf {Q}} * \ddot{\varvec{v}_i}\ddot{\mathbf {P}_i} = \dot{\mathbf {Q}} * \ddot{\varvec{v}_i}\dot{\mathbf {P}_i} = \tilde{\varvec{v}_i} + \tilde{\varvec{r}_i}\). It follows that \(\dot{\mathbf {Q}} * (\ddot{\varvec{v}_i} - \dot{\varvec{v}_i}) \dot{\mathbf {P}_i} = \tilde{\varvec{r}_i}\), which implies that \((\ddot{\varvec{v}_i} - \dot{\varvec{v}_i}) = \dot{\mathbf {Q}}^{-1} * \tilde{\varvec{r}_i} \dot{\mathbf {P}_i}^{-1}\).

\( \forall i \in [\![1,7]\!],~ (\ddot{\varvec{v}_i} - \dot{\varvec{v}_i}) = \dot{\mathbf {Q}}^{-1} * \tilde{\varvec{r}_i} \dot{\mathbf {P}_i}^{-1}\)

Since \(\dot{\mathbf {Q}}^{-1}\in {{\mathsf {G}}}{{\mathsf {L}}}_m(q)\) and \(\dot{\mathbf {P}_i}^{-1}\in {{\mathsf {G}}}{{\mathsf {L}}}_m(q)\), we have \((\ddot{\varvec{v}_1} - \dot{\varvec{v}_1}, \ddot{\varvec{v}_2} - \dot{\varvec{v}_2}, \ddot{\varvec{v}_3} - \dot{\varvec{v}_3})\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\) and \((\ddot{\varvec{v}_4} - \dot{\varvec{v}_4}, \ddot{\varvec{v}_5} - \dot{\varvec{v}_5}, \ddot{\varvec{v}_6} - \dot{\varvec{v}_5})\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\). Therefore, the knowledge extractor \({\mathscr {K}}\) obtains vectors \(\varvec{y}_i = \ddot{\varvec{v}_i} - \dot{\varvec{v}_i}\), with \(i \in [\![1,7]\!]\), such that: \(\sum _{i=1}^7 {\tilde{{\mathbf {H}}}}_i\varvec{y}_i^\top = \varvec{c}^\top , (\varvec{y}_1, \varvec{y}_2, \varvec{y}_3)\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\) and \((\varvec{y}_4, \varvec{y}_5, \varvec{y}_6)\in {\mathfrak {S}}_{w_r}^{3}({\mathscr {V}})\). \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bettaieb, S., Bidoux, L., Blazy, O. et al. A gapless code-based hash proof system based on RQC and its applications. Des. Codes Cryptogr. 90, 3011–3044 (2022). https://doi.org/10.1007/s10623-022-01075-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-022-01075-7

Keywords

Mathematics Subject Classification

Search

Navigation