Skip to main content

2020 | OriginalPaper | Buchkapitel

Short Zero-Knowledge Proof of Knowledge for Lattice-Based Commitment

verfasst von : Yang Tao, Xi Wang, Rui Zhang

Erschienen in: Post-Quantum Cryptography

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Commitment scheme, together with zero-knowledge proof, is a fundamental tool for cryptographic design. Recently, Baum et al. proposed a commitment scheme (BDLOP), which is by far the most efficient lattice-based one and has been applied on several latest constructions of zero-knowledge proofs. In this paper, we propose a more efficient zero-knowledge proof of knowledge for BDLOP commitment opening with a shorter proof. There are a few technical challenges, and we develop some new techniques: First, we make an adaption of BDLOP commitment by evaluating the opening with the singular value rather than \(\ell _2\) norm in order to get compact parameters. Then, we try to use the bimodal Gaussian technique to minimize the size of the proof. Finally, utilizing a modulus-switch technique, we can retain the size of the commitment.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
It degenerates to RSIS and RLWE when \(n=1\).
 
2
We choose \(C=\frac{1}{\sqrt{2\pi }}\) empirically. Besides, for \(\delta =0\) and \(t=5\), the above probability is approximate \(2^{-112}\).
 
3
Since there is no efficient zero-knowledge proofs that can prove knowledge of the message and randomness in the commit phase, some additional element \(\mathbf{f}\) is applied for a relaxed opening, which makes the zero-knowledge proof can prove something weaker. Such property is also used in [5] and [3].
 
4
In [21], one should only use \(d=\sqrt{\frac{N\log q}{\log \delta }}\) columns and zero out the others, which results in a short vector with length as \(\min \{q,q^{\frac{N}{d}}\delta ^d\}=\min \{q,q^{\frac{2N}{d}}\}\).
 
5
In [3], a valid opening of commitment \(\mathbf{c}=\left( \begin{array}{c} \mathbf{c}_1 \\ \mathbf{c}_2\\ \end{array}\right) \) is a 3-tuple \((\mathbf{x},\mathbf{r},\mathbf{f})\) with \(\mathbf{r}=\left( \begin{array}{c} \mathbf{r}_1 \\ \cdots \\ \mathbf{r}_k\\ \end{array}\right) \in \mathcal {R}_q^k\) and \(\mathbf{f}\in \bar{\mathcal {C}}'\), where \(\bar{\mathcal {C}}'\) is a set of differences \(\mathcal {C}'-\mathcal {C}'\) excluding \(\mathbf{0}\). The verifier checks that \(\mathbf{f}\left( \begin{array}{c} \mathbf{c}_1 \\ \mathbf{c}_2\\ \end{array}\right) =\left( \begin{array}{c} \mathbf{A}_1 \\ \mathbf{A}_2\\ \end{array}\right) \mathbf{r}+\mathbf{f}\left( \begin{array}{c} \mathbf{0} \\ \mathbf{x}\\ \end{array}\right) \), and that for all i, \(\Vert \mathbf{r}_i\Vert _2\le 4\sigma \sqrt{N}\).
 
Literatur
1.
Zurück zum Zitat Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)MathSciNetCrossRef Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)MathSciNetCrossRef
4.
6.
Zurück zum Zitat Blum, M.: Coin flipping by telephone - a protocol for solving impossible problems. In: COMPCON 1982, pp. 133–137. IEEE Computer Society (1982) Blum, M.: Coin flipping by telephone - a protocol for solving impossible problems. In: COMPCON 1982, pp. 133–137. IEEE Computer Society (1982)
8.
Zurück zum Zitat 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. IEEE (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. IEEE (2018)
10.
Zurück zum Zitat Damgård, I.: On Sigma-Protocols. Lectures on Cryptologic Protocol Theory, Faculty of Science, University of Aarhus (2010) Damgård, I.: On Sigma-Protocols. Lectures on Cryptologic Protocol Theory, Faculty of Science, University of Aarhus (2010)
13.
Zurück zum Zitat Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)MathSciNetCrossRef Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)MathSciNetCrossRef
15.
Zurück zum Zitat Haitner, I., Reingold, O.: Statistically-hiding commitment from any one-way function. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 1–10. ACM (2007) Haitner, I., Reingold, O.: Statistically-hiding commitment from any one-way function. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 1–10. ACM (2007)
24.
Zurück zum Zitat Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. CoRR abs/1011.3027 (2010) Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. CoRR abs/1011.3027 (2010)
26.
Metadaten
Titel
Short Zero-Knowledge Proof of Knowledge for Lattice-Based Commitment
verfasst von
Yang Tao
Xi Wang
Rui Zhang
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-44223-1_15