Skip to main content
Top

2021 | OriginalPaper | Chapter

Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments

Authors : Vadim Lyubashevsky, Ngoc Khanh Nguyen, Gregor Seiler

Published in: Public-Key Cryptography – PKC 2021

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

There has been a lot of recent progress in constructing efficient zero-knowledge proofs for showing knowledge of an \(\vec {\varvec{s}}\) with small coefficients satisfying \(\varvec{A}\vec {\varvec{s}}=\vec {\varvec{t}}\). For typical parameters, the proof sizes have gone down from several megabytes to a bit under 50KB (Esgin et al., Asiacrypt 2020). These are now within an order of magnitude of the sizes of lattice-based signatures, which themselves constitute proof systems which demonstrate knowledge of something weaker than the aforementioned equation. One can therefore see that this line of research is approaching optimality. In this paper, we modify a key component of these proofs, as well as apply several other tweaks, to achieve a further reduction of around \(30\%\) in the proof output size. We also show that this savings propagates itself when these proofs are used in a general framework to construct more complex protocols.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
For the readers familiar with the sample-preserving reduction between search and decisional LWE problems [MM11], the underlying obstacles for that reduction and the extended-LWE reduction not carrying over to the Ring-LWE setting are similar.
 
2
Indeed, much of the progress in constructions of practical classical cryptography has come from making stronger, but still plausible, assumptions that stem from discrete log or factoring.
 
3
Even smaller sizes would be of course obtained if one does no masking at all, but then the scheme would be clearly insecure.
 
4
Although Lyubashevsky et al. only consider the case \(\alpha \le 3\), it can be easily generalised by sending more garbage commitments.
 
5
Note that the length of \(\vec {\varvec{r}}\) is not \(\kappa +\lambda +n\) as in Sect. 2.9 since the prover will later in the protocol commit to \(\alpha \) garbage polynomials using the same \(\vec {\varvec{r}}\).
 
6
In [AP12] the hint is the inner product \(\langle \vec {r}, \vec {z} \rangle \) of the secret vector \(\vec {r}\) and some \(\vec {z}\) sampled from a given distribution D.
 
Literature
ADPS15.
go back to reference Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. IACR Cryptol. ePrint Arch. 2015, 1092 (2015) Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. IACR Cryptol. ePrint Arch. 2015, 1092 (2015)
Ban93.
go back to reference Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(1), 625–635 (1993)MathSciNetCrossRef Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(1), 625–635 (1993)MathSciNetCrossRef
BDK+18.
go back to reference Bos, J.W. et al.: CRYSTALS - kyber: A cca-secure module-lattice-based KEM. In: 2018 IEEE European Symposium on Security and Privacy, EuroS&P, pp. 353–367 (2018) Bos, J.W. et al.: CRYSTALS - kyber: A cca-secure module-lattice-based KEM. In: 2018 IEEE European Symposium on Security and Privacy, EuroS&P, pp. 353–367 (2018)
BL17.
go back to reference Baum, C., Lyubashevsky, V.: Simple amortized proofs of shortness for linear relations over polynomial rings. IACR Cryptology ePrint Archive 2017, 759 (2017) Baum, C., Lyubashevsky, V.: Simple amortized proofs of shortness for linear relations over polynomial rings. IACR Cryptology ePrint Archive 2017, 759 (2017)
BN20.
CLOS02.
go back to reference Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC, pp. 494–503. ACM (2002) Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC, pp. 494–503. ACM (2002)
DKL+18.
go back to reference Ducas, L., et al.: Crystals-dilithium: a lattice-based digital signature scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(1), 238–268 (2018)MathSciNetCrossRef Ducas, L., et al.: Crystals-dilithium: a lattice-based digital signature scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(1), 238–268 (2018)MathSciNetCrossRef
DKRV18.
EZS+19.
go back to reference Esgin, M.F., Zhao, R.K., Steinfeld, R., Liu, J.K., Liu, D.: Matrict: Efficient, scalable and post-quantum blockchain confidential transactions protocol. In: CCS, pp. 567–584. ACM (2019) Esgin, M.F., Zhao, R.K., Steinfeld, R., Liu, J.K., Liu, D.: Matrict: Efficient, scalable and post-quantum blockchain confidential transactions protocol. In: CCS, pp. 567–584. ACM (2019)
GKPV10.
go back to reference Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: ICS, pp. 230–240. Tsinghua University Press (2010) Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: ICS, pp. 230–240. Tsinghua University Press (2010)
HPS98.
go back to reference Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: ANTS, pp. 267–288 (1998) Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: ANTS, pp. 267–288 (1998)
LNSW13.
go back to reference Ling, S., Nguyen, K., Stehlé, D., Wang, H.: Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In: PKC, pp. 107–124 (2013) Ling, S., Nguyen, K., Stehlé, D., Wang, H.: Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In: PKC, pp. 107–124 (2013)
Lyu09.
go back to reference Lyubashevsky, V.: Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In: ASIACRYPT, pp. 598–616 (2009) Lyubashevsky, V.: Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In: ASIACRYPT, pp. 598–616 (2009)
Lyu12.
go back to reference Lyubashevsky, V.: Lattice signatures without trapdoors. In: EUROCRYPT, pp. 738–755 (2012) Lyubashevsky, V.: Lattice signatures without trapdoors. In: EUROCRYPT, pp. 738–755 (2012)
Ste93.
go back to reference Stern, J.: A new identification scheme based on syndrome decoding. In: CRYPTO, pp. 13–21 (1993) Stern, J.: A new identification scheme based on syndrome decoding. In: CRYPTO, pp. 13–21 (1993)
YAZ+19.
Metadata
Title
Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments
Authors
Vadim Lyubashevsky
Ngoc Khanh Nguyen
Gregor Seiler
Copyright Year
2021
DOI
https://doi.org/10.1007/978-3-030-75245-3_9

Premium Partner