Article

Vector Commitments over Rings and Compressed $Σ$ -Protocols

Authors:

Ignacio Cascudo,

Daniel EscuderoAuthors Info & Claims

Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part I

Pages 173 - 202

https://doi.org/10.1007/978-3-031-22318-1_7

Published: 21 December 2022 Publication History

Abstract

Compressed

Σ

-Protocol Theory (CRYPTO 2020) presents an “alternative” to Bulletproofs that achieves the same communication complexity while adhering more elegantly to existing

Σ

-protocol theory, which enables their techniques to be directly applicable to other widely used settings in the context of “plug & play” algorithmics. Unfortunately, their techniques are restricted to arithmetic circuits over prime fields, which rules out the possibility of using more machine-friendly moduli such as powers of 2, which have proven to improve efficiency in applications. In this work we show that such techniques can be generalized to the case of arithmetic circuits modulo any number. This enables the use of powers of 2, which can prove to be beneficial for efficiency, but it also facilitates the use of other moduli that might prove useful in different applications.

In order to achieve this, we first present an instantiation of the main building block of the theory of compressed

Σ

-protocols, namely compact vector commitments. Our construction, which may be of independent interest, is homomorphic modulo any positive integer m, a result that was not known in the literature before. Second, we generalize Compressed

Σ

-Protocol Theory from finite fields to

Z_{m}

. The main challenge here is ensuring that there are large enough challenge sets as to fulfill the necessary soundness requirements, which is achieved by considering certain ring extensions. Our techniques have direct application for example to verifiable computation on homomorphically encrypted data.

References

[1]

Abspoel M, Cramer R, Damgård I, Escudero D, and Yuan C Hofheinz D and Rosen A Efficient information-theoretic secure multiparty computation over

Z / p^{k} Z

via galois rings Theory of Cryptography 2019 Cham Springer 471-501

[2]

Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 2087–2104. ACM Press, October 2017

[3]

Attema, T., Cramer, R.: Compressed

Σ

-protocol theory and practical application to plug & play secure algorithmics. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. Part III. LNCS, vol. 12172, pp. 513–543. Springer, Cham (2020).

[4]

Attema, T., Cramer, R., Kohl, L.: A compressed

Σ

-protocol theory for lattices. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part II. LNCS, vol. 12826, pp. 549–579. Springer, Cham (2021).

[5]

Attema, T., Fehr, S.: Parallel repetition of

(k_{1}, \dots, k_{μ})

-special-sound multi-round interactive proofs. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13507, pp. 415–443. Springer, Cham (2022).

[6]

Baum, C., Braun, L., Munch-Hansen, A., Razet, B., Scholl, P.: Appenzeller to brie: efficient zero-knowledge proofs for mixed-mode arithmetic and Z2k. In: Vigna, G., Shi, E. (eds.) ACM CCS 2021, pp. 192–211. ACM Press, November 2021

[7]

Baum, C., Braun, L., Munch-Hansen, A., Scholl, P.: Appenzeller to brie: efficient zero-knowledge proofs for mixed-mode arithmetic and z2k (2021)

[8]

Baum C, Damgård I, Lyubashevsky V, Oechsner S, and Peikert C Catalano D and De Prisco R More efficient commitments from structured lattice assumptions Security and Cryptography for Networks 2018 Cham Springer 368-385

[9]

Ben-Sasson E, Chiesa A, Riabzev M, Spooner N, Virza M, and Ward NP Ishai Y and Rijmen V Aurora: transparent succinct arguments for R1CS Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 103-128

[10]

Bendlin, R., Damgård, I., Orlandi, C., Zakarias, S.: Semi-homomorphic encryption and multiparty computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 169–188. Springer, Heidelberg (2011).

[11]

Benhamouda F, Krenn S, Lyubashevsky V, and Pietrzak K Pernul G, Ryan PYA, and Weippl E Efficient zero-knowledge proofs for commitments from learning with errors over rings Computer Security – ESORICS 2015 2015 Cham Springer 305-325

[12]

Block AR, Holmgren J, Rosen A, Rothblum RD, and Soni P Malkin T and Peikert C Time- and space-efficient arguments from groups of unknown order Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 123-152

[13]

Bois A, Cascudo I, Fiore D, and Kim D Garay JA Flexible and efficient verifiable computation on encrypted data Public-Key Cryptography – PKC 2021 2021 Cham Springer 528-558

[14]

Bootle J, Cerulli A, Chaidos P, Groth J, and Petit C Fischlin M and Coron J-S Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting Advances in Cryptology – EUROCRYPT 2016 2016 Heidelberg Springer 327-357

[15]

Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315–334. IEEE Computer Society Press, May 2018

[16]

Bünz B, Fisch B, and Szepieniec A Canteaut A and Ishai Y Transparent SNARKs from DARK compilers Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 677-706

[17]

Catalano D, Di Raimondo M, Fiore D, and Giacomelli I Kiayias A, Kohlweiss M, Wallden P, and Zikas V Mon

Z_{2^{k}}

a: fast maliciously secure two party computation on

Z_{2^{k}}

Public-Key Cryptography – PKC 2020 2020 Cham Springer 357-386

[18]

Catalano D and Fiore D Kurosawa K and Hanaoka G Vector commitments and their applications Public-Key Cryptography – PKC 2013 2013 Heidelberg Springer 55-72

[19]

Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 1825–1842. ACM Press, October 2017

[20]

Chen, S., Cheon, J.H., Kim, D., Park, D.: Verifiable computing for approximate computation. Cryptology ePrint Archive, Report 2019/762 (2019). https://eprint.iacr.org/2019/762

[21]

Cramer, R.: Modular design of secure yet practical cryptographic protocols. Ph.D. thesis, CWI and University of Amsterdam (1996)

[22]

Cramer R and Damgård I Krawczyk H Zero-knowledge proofs for finite field arithmetic, or: Can zero-knowledge be for free? Advances in Cryptology — CRYPTO ’98 1998 Heidelberg Springer 424-441

[23]

Cramer R, Damgård I, Escudero D, Scholl P, and Xing C Shacham H and Boldyreva A SPD

Z_{2^{k}}

: efficient MPC mod

2^{k}

for dishonest majority Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 769-798

[24]

Cramer R, Damgård I, and Schoenmakers B Desmedt YG Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols Advances in Cryptology — CRYPTO ’94 1994 Heidelberg Springer 174-187

[25]

Damgård, I., Escudero, D., Frederiksen, T.K., Keller, M., Scholl, P., Volgushev, N.: New primitives for actively-secure MPC over rings with applications to private machine learning. In: 2019 IEEE Symposium on Security and Privacy, pp. 1102–1120. IEEE Computer Society Press, May 2019

[26]

Damgård I and Fujisaki E Zheng Y A statistically-hiding integer commitment scheme based on groups with hidden order Advances in Cryptology — ASIACRYPT 2002 2002 Heidelberg Springer 125-142

[27]

ElGamal T A public key cryptosystem and a signature scheme based on discrete logarithms IEEE Trans. Inf. Theory 1985 31 469-472

[28]

Fiore, D., Gennaro, R., Pastro, V.: Efficiently verifiable computation on encrypted data. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 844–855. ACM Press, November 2014

[29]

Fiore D, Nitulescu A, and Pointcheval D Kiayias A, Kohlweiss M, Wallden P, and Zikas V Boosting verifiable computation on encrypted data Public-Key Cryptography – PKC 2020 2020 Cham Springer 124-154

[30]

Ganesh, C., Nitulescu, A., Soria-Vazquez, E.: Rinocchio: snarks for ring arithmetic. IACR Cryptology ePrint Archive 2021:322 (2021)

[31]

Gennaro R, Gentry C, and Parno B Rabin T Non-interactive verifiable computing: outsourcing computation to untrusted workers Advances in Cryptology – CRYPTO 2010 2010 Heidelberg Springer 465-482

[32]

Giacomelli, I., Madsen, J., Orlandi, C.: ZKBoo: faster zero-knowledge for Boolean circuits. In: Holz, T., Savage, S. (eds.) USENIX Security 2016, pp. 1069–1083. USENIX Association, August 2016

[33]

Goldreich O Foundations of Cryptography: Basic Applications 2004 Cambridge Cambridge University Press

[34]

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218–229. ACM Press, May 1987

[35]

Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 113–122. ACM Press, May 2008

[36]

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: 17th ACM STOC, pp. 291–304. ACM Press, May 1985

[37]

Groth J Fischlin M and Coron J-S On the size of pairing-based non-interactive arguments Advances in Cryptology – EUROCRYPT 2016 2016 Heidelberg Springer 305-326

[38]

Joye, M., Libert, B.: Efficient cryptosystems from

2^{k}

. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 76–92. Springer, Heidelberg (2013).

[39]

Okamoto T and Uchiyama S Nyberg K A new public-key cryptosystem as secure as factoring Advances in Cryptology — EUROCRYPT’98 1998 Heidelberg Springer 308-318

[40]

Paillier P Stern J Public-key cryptosystems based on composite degree residuosity classes Advances in Cryptology — EUROCRYPT ’99 1999 Heidelberg Springer 223-238

[41]

Pedersen TP Feigenbaum J Non-interactive and information-theoretic secure verifiable secret sharing Advances in Cryptology — CRYPTO ’91 1992 Heidelberg Springer 129-140

[42]

Schnorr CP Brassard G Efficient identification and signatures for smart cards Advances in Cryptology — CRYPTO’ 89 Proceedings 1990 New York Springer 239-252

[43]

Wahby, R.S., Tzialla, I., shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. In: 2018 IEEE Symposium on Security and Privacy, pp. 926–943. IEEE Computer Society Press, May 2018

[44]

Xie T, Zhang J, Zhang Y, Papamanthou C, and Song D Boldyreva A and Micciancio D Libra: succinct zero-knowledge proofs with optimal prover computation Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 733-764

Cited By

Tian YPang Y(2024)Efficient Zero-Knowledge Argument for Bilinear Matrix Relation over the Residue RingData Security and Privacy Protection10.1007/978-981-97-8540-7_6(87-105)Online publication date: 25-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8540-7_6
Bartoli CCascudo I(2024)On Sigma-Protocols and (Packed) Black-Box Secret Sharing SchemesPublic-Key Cryptography – PKC 202410.1007/978-3-031-57722-2_14(426-457)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57722-2_14

Index Terms

Vector Commitments over Rings and Compressed $Σ$ -Protocols
1. Information systems
  1. Data management systems
    1. Data structures

Index terms have been assigned to the content through auto-classification.

Recommendations

Succinct Verification of Compressed Sigma Protocols in the Updatable SRS Setting
Public-Key Cryptography – PKC 2024
Abstract
We propose protocols in the Compressed Sigma Protocol framework that achieve a succinct verifier. Towards this, we construct a new inner product argument and cast it in the Compressed Sigma Protocol (CSP) framework as a protocol for opening a ...
On the enumeration and classification of σ-LCD codes over finite commutative chain rings
Abstract
Let R e denote a finite commutative chain ring with the maximal ideal 〈 u 〉 and the nilpotency index e, and let R ‾ e = R e / 〈 u 〉 be the residue field of R e. Let σ 0 be an automorphism of R e, and let σ ‾ 0 be the corresponding ...
Construction of MDS self-dual codes over Galois rings

The purpose of this paper is to construct nontrivial MDS self-dual codes over Galois rings. We consider a building-up construction of self-dual codes over Galois rings as a GF(q)-analogue of (Kim and Lee, J Combin Theory ser A, 105:79---95). We give a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part I

Nov 2022

747 pages

ISBN:978-3-031-22317-4

DOI:10.1007/978-3-031-22318-1

Editors:
Eike Kiltz
Ruhr University Bochum, Bochum, Germany
,
Vinod Vaikuntanathan
Massachusetts Institute of Technology, Cambridge, MA, USA

© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 December 2022

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tian YPang Y(2024)Efficient Zero-Knowledge Argument for Bilinear Matrix Relation over the Residue RingData Security and Privacy Protection10.1007/978-981-97-8540-7_6(87-105)Online publication date: 25-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8540-7_6
Bartoli CCascudo I(2024)On Sigma-Protocols and (Packed) Black-Box Secret Sharing SchemesPublic-Key Cryptography – PKC 202410.1007/978-3-031-57722-2_14(426-457)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57722-2_14

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents