Abstract
Witness encryption is a cryptographic primitive which encrypts a message under an instance of an NP language and decrypts the ciphertext using a witness associated with that instance. In the current state of the art, most of the witness encryption constructions are based on multilinear maps. Following the construction of Choi and Vaudenay based on RSA-related problems, we suggest a novel witness key encapsulation mechanism based on the hardness of solving homogeneous linear Diophantine equations (HLE problem). Our arithmetic-based construction aims to solve an issue raised by these authors where the security might be compromised if the adversary is able to find small solutions to a homogeneous linear Diophantine equation, while avoiding the inefficiency of multilinear maps. The security of our scheme is based on a hidden group order and a knowledge assumption.
B. Tran—Supported by the Swiss National Science Foundation (SNSF) through the project grant No 192364 on Post-Quantum Cryptography.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
By Claim 1, this happens with probability at least \(1-\frac{1}{2^{n-1}}\left( 1+\frac{2}{q}\right) ^n\).
- 2.
For clarity, we omit in
the “conditioned to \(\boldsymbol{\lnot } F_\ell ({\boldsymbol{x}},{\boldsymbol{y}})\)” part.
- 3.
ibid.
References
Abusalah, H., Fuchsbauer, G., Pietrzak, K.: Offline witness encryption. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 285–303. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39555-5_16
Barak, B., et al.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_1
Bellare, M., Hoang, V.T.: Adaptive witness encryption and asymmetric password-based cryptography. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 308–331. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_14
Bombieri, E., Vaaler, J.: On Siegel’s lemma. Inventiones Mathematicae 73, 11–32 (1983)
Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_1
Choi, G., Vaudenay, S.: Towards witness encryption without multilinear maps. In: Park, J.H., Seo, S. (eds.) ICISC 2021. LNCS, vol. 13218, pp. 28–47. Springer, Cham (2021). https://doi.org/10.1007/978-3-031-08896-4_2
Choi, G.: Time in cryptography (2020). https://infoscience.epfl.ch/record/279784
Chvojka, P., Jager, T., Kakvi, S.A.: Offline witness encryption with semi-adaptive security. In: Conti, M., Zhou, J., Casalicchio, E., Spognardi, A. (eds.) ACNS 2020. LNCS, vol. 12146, pp. 231–250. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57808-4_12
Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_4
van Emde-Boas, P.: Another NP-complete partition problem and the complexity of computing short vectors in a lattice (1981). https://staff.fnwi.uva.nl/p.vanemdeboas/vectors/abstract.html. Accessed 13 Feb 2022
Faonio, A., Nielsen, J.B., Venturi, D.: Predictable arguments of knowledge. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10174, pp. 121–150. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54365-8_6
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput. 45(3), 882–929 (2016)
Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 467–476 (2013)
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 197–206. ACM (2008)
Jain, A., Lin, H., Sahai, A.: Indistinguishability Obfuscation from Well-Founded Assumptions. Cryptology ePrint Archive, Report 2020/1003 (2020)
Kaltofen, E.L., Storjohann, A.: Complexity of computational problems in exact linear algebra. In: Engquist, B. (ed.) Encyclopedia of Applied and Computational Mathematics, pp. 227–233. Springer, Heidelberg (2015)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85–103. Springer, Boston (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Lenstra, A.K., Lenstra, H.W., Lovasz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)
Lin, H., Tessaro, S.: Indistinguishability obfuscation from trilinear maps and block-wise local PRGs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 630–660. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_21
Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319–339. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19074-2_21
Liu, J., Jager, T., Kakvi, S.A., Warinschi, B.: How to build time-lock encryption. Des. Codes Crypt. 86(11), 2549–2586 (2018). https://doi.org/10.1007/s10623-018-0461-x
May, T.C.: Time-release crypto (1993). https://cypherpunks.venona.com/date/1993/02/msg00129.html. Accessed 16 Feb 2022
Merkle, R.C.: Secure communications over insecure channels. Commun. ACM 21(4), 294–299 (1978)
Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 21–39. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_2
Nymann, J.: On the probability that \(k\) positive integers are relatively prime. J. Number Theory 4(5), 469–473 (1972)
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release Crypto (1996)
Schnorr, C.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201–224 (1987)
Schnorr, C., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)
Shoup, V.: A computational introduction to number theory and algebra (2009). https://shoup.net/ntb/ntb-v2.pdf. Accessed 13 Feb 2022
Siegel, C.L.: Über einige Anwendungen Diophantischer Approximationen. Abh. Preuss. Akad. Wiss. Phys. Math. Kl 1, 41–69 (1929). reprinted as pp. 209–266 of Gesammelte Abhandlungen I. Springer, Berlin (1966)
Storjohann, A.: Algorithms for matrix canonical forms. Ph.D. thesis, ETH Zurich, Zürich (2000). https://doi.org/10.3929/ethz-a-004141007. Diss., Technische Wissenschaften ETH Zürich, Nr. 13922, 2001
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Correctness Proof
A Correctness Proof
In this section, we prove the unproved assertions of Sect. 3.1. To that end, we need some results involving abstract algebra.
Lemma 4
Let \(L\ge m\) be positive integers. Let \(\mathcal {U}\) be the uniform distribution over and \(\mathcal {Z}= \mathcal {U}\bmod {m}\). For all
, we have
Proof
Let and
. Then,
. Since
, this completes the proof. \(\square \)
Lemma 5
Let \(L\ge m\) be positive integers and \(G\trianglelefteq \mathbb {Z}^n\) be a group. Let \(\mathcal {U}\) be the uniform distribution over and let
be its projection in \(G_L\bmod {m}\). For all \(\boldsymbol{z}\in G_L\bmod {m}\), we have
Proof
Let \(\boldsymbol{z}\in G_L\bmod {m}\) and . A similar argument as in the proof of Lemma 4 establishes \(s(\boldsymbol{z})\le \lceil L/m\rceil ^n\le \left( 1+L/m\right) ^n\). On the other hand, since \(G\bmod {m}\subset G_L\), it follows that
. In particular,
. Therefore,
\(\square \)
Proof of Claim 1, page 13. Since is bijective,
and
have the same probability distributions. Thus,
solely depends on the distribution of
. Let
be fixed and assume that \(\ell \ge q\). Then, the probability that a given component of
is equal to
is at most 1/r. Since these components are identically and independently distributed, it follows that
On the other hand, assume that \(\ell < q\). By Lemma 4 applied to \(q\ge r\), we get
Summing these probabilities as \(\varepsilon _0\) ranges over establishes the desired bounds and the remaining inequality is a consequence of the Fréchet inequality. \(\square \)
Lemma 6
Let \(\textsf{ct}= ({\boldsymbol{x}},{\boldsymbol{y}})\in \mathbb {Z}^n\times \mathbb {Z}^n\) be a ciphertext produced by Algorithm 1 corresponding to a \(\textsf{HLE}\) instance and a hidden prime p and consider a nonzero vector
. Let
and assume that there exist a prime factor \(\ell \) of
and a prime factor r of \(\varphi (\ell )\) such that the event \(F_{\ell ,r}({\boldsymbol{x}},{\boldsymbol{y}})\) defined by (3.5) does not hold. If
denotes the uniform distribution over
, then
Stated otherwise, at most \(\frac{|H|}{2^n}\) elements from H give rise to a multiple of \(\ell \) under the mapping defined by (3.4).Footnote 2
Proof
Let \(\phi =\varphi (\ell )\). Since \(\ell \) is a prime factor of and \(y_i\) is invertible modulo
, the latter is invertible modulo \(\ell \) and \(\text {dlog}_\ell ({\boldsymbol{y}})\) is well-defined. In particular,
if and only if
. Without loss of generality, \({H={{\,\textrm{ker}\,}}_{}({{\boldsymbol{x}}}^{\!\top })\bmod {\phi }}\) and
are nonempty subgroups of
. If \(\boldsymbol{z}\) uniformly distributed in
, then
Fix an isomorphism where each \(m_k=r_k^{e_k}\) is a prime power and denote by
the canonical projection onto the \(r_k\)-primary component. By definition, there exist integers \(0\le e'_k \le e''_k\le e_k\) such that
By assumption, there exists k such that has no solution for \(\varepsilon \) in
. In particular, the inclusion \(\rho _k(H\cap {{\,\textrm{ker}\,}}(\text {dlog}_\ell ({\boldsymbol{y}})))\triangleleft \rho _k(H)\) is strict, namely \(e'_k < e''_k\). Therefore, \(\bar{\vartheta } \le \frac{1}{r_k^n} \le \frac{1}{2^n}\). \(\square \)
Proof of Claim 2, page 13. Let \(\phi =\varphi (\ell )\) and \(H = {{\,\textrm{ker}\,}}_{}({{\boldsymbol{x}}}^{\!\top })\bmod {\phi }\). Let \({\boldsymbol{\beta }}\) be uniformly distributed in \({{\,\textrm{ker}\,}}_{L}({{\boldsymbol{x}}}^{\!\top })\). Lemma 5 applied to \(G = {{\,\textrm{ker}\,}}_{}({{\boldsymbol{x}}}^{\!\top })\subset \mathbb {Z}^n\) implies that . By Lemma 6, at most \(\frac{|H|}{2^n}\) elements in H give rise to a multiple of \(\ell \) via \({{\boldsymbol{\beta }}\mapsto \sigma _\delta ({\boldsymbol{y}},{\boldsymbol{\beta }})}\). ThereforeFootnote 3,
\(\square \)
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Tran, B., Vaudenay, S. (2023). Extractable Witness Encryption for the Homogeneous Linear Equations Problem. In: Shikata, J., Kuzuno, H. (eds) Advances in Information and Computer Security. IWSEC 2023. Lecture Notes in Computer Science, vol 14128. Springer, Cham. https://doi.org/10.1007/978-3-031-41326-1_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-41326-1_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-41325-4
Online ISBN: 978-3-031-41326-1
eBook Packages: Computer ScienceComputer Science (R0)