Efficient lattice-based polynomial evaluation and batch ZK arguments

Veronika Kuchta; Amin Sakzad; Ron Steinfeld; Joseph K. Liu

doi:10.1007/978-3-030-81652-0_1

Efficient lattice-based polynomial evaluation and batch ZK arguments

Veronika Kuchta, Amin Sakzad, Ron Steinfeld, Joseph K. Liu

Department of Software Systems & Cybersecurity

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

1 Citation (Scopus)

Abstract

In this paper we provide an efficient construction of a lattice-based polynomial argument and a polynomial batch-protocol, where the latter contains the polynomial argument as a building block. Our contribution is motivated by the discrete log based construction (EUROCRYPT’16), where in our case we employ different techniques to obtain a communication efficient lattice-based scheme. In the zero-knowledge polynomial batch-protocol, we prove the knowledge of an easy relation between two polynomials which also allows batching of several instances of the same relation. Our batch-protocol is applicable to an efficient lattice-based range proof construction which represents a useful application in cryptocurrencies. In contrast to the existing range proof (CRYPTO’19), our proof is more efficient for large number of batched instances.

Original language	English
Title of host publication	Selected Areas in Cryptography - Halifax, NS, Canada (Virtual Event), Revised Selected Papers October 21–23, 2020,
Editors	Orr Dunkelman, Michael J. Jacobson, Jr., Colin O’Flynn
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	3-33
Number of pages	31
ISBN (Electronic)	9783030816520
ISBN (Print)	9783030816513
DOIs	https://doi.org/10.1007/978-3-030-81652-0_1
Publication status	Published - 2021
Event	Selected Areas in Cryptography 2020 - Virtual, Canada Duration: 21 Oct 2020 → 23 Oct 2020 Conference number: 27th https://link.springer.com/book/10.1007/978-3-030-81652-0 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12804
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Selected Areas in Cryptography 2020
Abbreviated title	SAC 2020
Country/Territory	Canada
Period	21/10/20 → 23/10/20
Internet address	https://link.springer.com/book/10.1007/978-3-030-81652-0 (Proceedings)

Access to Document

10.1007/978-3-030-81652-0_1

Cite this

Kuchta, V., Sakzad, A., Steinfeld, R., & Liu, J. K. (2021). Efficient lattice-based polynomial evaluation and batch ZK arguments. In O. Dunkelman, M. J. Jacobson, Jr., & C. O’Flynn (Eds.), Selected Areas in Cryptography - Halifax, NS, Canada (Virtual Event), Revised Selected Papers October 21–23, 2020, (pp. 3-33). (Lecture Notes in Computer Science; Vol. 12804). Springer. https://doi.org/10.1007/978-3-030-81652-0_1

Kuchta, Veronika ; Sakzad, Amin ; Steinfeld, Ron et al. / Efficient lattice-based polynomial evaluation and batch ZK arguments. Selected Areas in Cryptography - Halifax, NS, Canada (Virtual Event), Revised Selected Papers October 21–23, 2020, . editor / Orr Dunkelman ; Michael J. Jacobson, Jr. ; Colin O’Flynn. Cham Switzerland : Springer, 2021. pp. 3-33 (Lecture Notes in Computer Science).

@inproceedings{d0220172aa374a508b95f2a6a565024c,

title = "Efficient lattice-based polynomial evaluation and batch ZK arguments",

abstract = "In this paper we provide an efficient construction of a lattice-based polynomial argument and a polynomial batch-protocol, where the latter contains the polynomial argument as a building block. Our contribution is motivated by the discrete log based construction (EUROCRYPT{\textquoteright}16), where in our case we employ different techniques to obtain a communication efficient lattice-based scheme. In the zero-knowledge polynomial batch-protocol, we prove the knowledge of an easy relation between two polynomials which also allows batching of several instances of the same relation. Our batch-protocol is applicable to an efficient lattice-based range proof construction which represents a useful application in cryptocurrencies. In contrast to the existing range proof (CRYPTO{\textquoteright}19), our proof is more efficient for large number of batched instances.",

author = "Veronika Kuchta and Amin Sakzad and Ron Steinfeld and Liu, {Joseph K.}",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.; Selected Areas in Cryptography 2020, SAC 2020 ; Conference date: 21-10-2020 Through 23-10-2020",

year = "2021",

doi = "10.1007/978-3-030-81652-0_1",

language = "English",

isbn = "9783030816513",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "3--33",

editor = "Orr Dunkelman and {Jacobson, Jr.}, {Michael J.} and Colin O{\textquoteright}Flynn",

booktitle = "Selected Areas in Cryptography - Halifax, NS, Canada (Virtual Event), Revised Selected Papers October 21–23, 2020,",

url = "https://link.springer.com/book/10.1007/978-3-030-81652-0",

}

Kuchta, V, Sakzad, A , Steinfeld, R & Liu, JK 2021, Efficient lattice-based polynomial evaluation and batch ZK arguments. in O Dunkelman, MJ Jacobson, Jr. & C O’Flynn (eds), Selected Areas in Cryptography - Halifax, NS, Canada (Virtual Event), Revised Selected Papers October 21–23, 2020, . Lecture Notes in Computer Science, vol. 12804, Springer, Cham Switzerland, pp. 3-33, Selected Areas in Cryptography 2020, Nova Scotia, Canada, 21/10/20. https://doi.org/10.1007/978-3-030-81652-0_1

Efficient lattice-based polynomial evaluation and batch ZK arguments. / Kuchta, Veronika; Sakzad, Amin ; Steinfeld, Ron et al.
Selected Areas in Cryptography - Halifax, NS, Canada (Virtual Event), Revised Selected Papers October 21–23, 2020, . ed. / Orr Dunkelman; Michael J. Jacobson, Jr.; Colin O’Flynn. Cham Switzerland: Springer, 2021. p. 3-33 (Lecture Notes in Computer Science; Vol. 12804).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Efficient lattice-based polynomial evaluation and batch ZK arguments

AU - Kuchta, Veronika

AU - Sakzad, Amin

AU - Steinfeld, Ron

AU - Liu, Joseph K.

N1 - Conference code: 27th

PY - 2021

Y1 - 2021

N2 - In this paper we provide an efficient construction of a lattice-based polynomial argument and a polynomial batch-protocol, where the latter contains the polynomial argument as a building block. Our contribution is motivated by the discrete log based construction (EUROCRYPT’16), where in our case we employ different techniques to obtain a communication efficient lattice-based scheme. In the zero-knowledge polynomial batch-protocol, we prove the knowledge of an easy relation between two polynomials which also allows batching of several instances of the same relation. Our batch-protocol is applicable to an efficient lattice-based range proof construction which represents a useful application in cryptocurrencies. In contrast to the existing range proof (CRYPTO’19), our proof is more efficient for large number of batched instances.

AB - In this paper we provide an efficient construction of a lattice-based polynomial argument and a polynomial batch-protocol, where the latter contains the polynomial argument as a building block. Our contribution is motivated by the discrete log based construction (EUROCRYPT’16), where in our case we employ different techniques to obtain a communication efficient lattice-based scheme. In the zero-knowledge polynomial batch-protocol, we prove the knowledge of an easy relation between two polynomials which also allows batching of several instances of the same relation. Our batch-protocol is applicable to an efficient lattice-based range proof construction which represents a useful application in cryptocurrencies. In contrast to the existing range proof (CRYPTO’19), our proof is more efficient for large number of batched instances.

UR - http://www.scopus.com/inward/record.url?scp=85113421118&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-81652-0_1

DO - 10.1007/978-3-030-81652-0_1

M3 - Conference Paper

AN - SCOPUS:85113421118

SN - 9783030816513

T3 - Lecture Notes in Computer Science

SP - 3

EP - 33

BT - Selected Areas in Cryptography - Halifax, NS, Canada (Virtual Event), Revised Selected Papers October 21–23, 2020,

A2 - Dunkelman, Orr

A2 - Jacobson, Jr., Michael J.

A2 - O’Flynn, Colin

PB - Springer

CY - Cham Switzerland

T2 - Selected Areas in Cryptography 2020

Y2 - 21 October 2020 through 23 October 2020

ER -

Kuchta V, Sakzad A , Steinfeld R , Liu JK. Efficient lattice-based polynomial evaluation and batch ZK arguments. In Dunkelman O, Jacobson, Jr. MJ, O’Flynn C, editors, Selected Areas in Cryptography - Halifax, NS, Canada (Virtual Event), Revised Selected Papers October 21–23, 2020, . Cham Switzerland: Springer. 2021. p. 3-33. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-81652-0_1

Efficient lattice-based polynomial evaluation and batch ZK arguments

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this