Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. / Chase, Melissa; Derler, David; Goldfeder, Steven; Orlandi, Claudio; Ramacher, Sebastian; Rechberger, Christian; Slamanig, Daniel; Zaverucha, Greg.

CCS 2017 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York, NY, USA : Association for Computing Machinery, 2017. p. 1825-1842 (CCS '17).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Chase, M, Derler, D, Goldfeder, S, Orlandi, C, Ramacher, S, Rechberger, C, Slamanig, D & Zaverucha, G 2017, Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. in CCS 2017 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, New York, NY, USA, CCS '17, pp. 1825-1842, ACM SIGSAC Conference on Computer and Communications Security , Dallas, United States, 30/10/2017. https://doi.org/10.1145/3133956.3133997

APA

Chase, M., Derler, D., Goldfeder, S., Orlandi, C., Ramacher, S., Rechberger, C., Slamanig, D., & Zaverucha, G. (2017). Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. In CCS 2017 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (pp. 1825-1842). Association for Computing Machinery. CCS '17 https://doi.org/10.1145/3133956.3133997

CBE

Chase M, Derler D, Goldfeder S, Orlandi C, Ramacher S, Rechberger C, Slamanig D, Zaverucha G. 2017. Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. In CCS 2017 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York, NY, USA: Association for Computing Machinery. pp. 1825-1842. (CCS '17). https://doi.org/10.1145/3133956.3133997

MLA

Chase, Melissa et al. "Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives". CCS 2017 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York, NY, USA: Association for Computing Machinery. (CCS '17). 2017, 1825-1842. https://doi.org/10.1145/3133956.3133997

Vancouver

Chase M, Derler D, Goldfeder S, Orlandi C, Ramacher S, Rechberger C et al. Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. In CCS 2017 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York, NY, USA: Association for Computing Machinery. 2017. p. 1825-1842. (CCS '17). https://doi.org/10.1145/3133956.3133997

Author

Chase, Melissa ; Derler, David ; Goldfeder, Steven ; Orlandi, Claudio ; Ramacher, Sebastian ; Rechberger, Christian ; Slamanig, Daniel ; Zaverucha, Greg. / Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. CCS 2017 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York, NY, USA : Association for Computing Machinery, 2017. pp. 1825-1842 (CCS '17).

Bibtex

@inproceedings{9ba10266beb942c08eb299a84a615eb0,
title = "Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives",
abstract = "We propose a new class of post-quantum digital signature schemes that: (a) derive their security entirely from the security of symmetric-key primitives, believed to be quantum-secure, and (b) have extremely small keypairs, and, (c) are highly parameterizable. In our signature constructions, the public key is an image y = f (x) of a one-way function f and secret key x. A signature is a non-interactive zero-knowledge proof of x, that incorporates a message to be signed. For this proof, we leverage recent progress of Giacomelli et al. (USENIX'16) in constructing an efficient {\'O}-protocol for statements over general circuits. We improve this {\'O}-protocol to reduce proof sizes by a factor of two, at no additional computational cost. While this is of independent interest as it yields more compact proofs for any circuit, it also decreases our signature sizes. We consider two possibilities to make the proof non-interactive: The Fiat-Shamir transform and Unruh's transform (EUROCRYPT'12, '15,'16). The former has smaller signatures, while the latter has a security analysis in the quantum-accessible random oracle model. By customizing Unruh's transform to our application, the overhead is reduced to 1.6x when compared to the Fiat-Shamir transform, which does not have a rigorous post-quantum security analysis. We implement and benchmark both approaches and explore the possible choice of f , taking advantage of the recent trend to strive for practical symmetric ciphers with a particularly low number of multiplications and end up using LowMC (EUROCRYPT'15).",
keywords = "block cipher, post-quantum cryptography, signatures, zero-knowledge, Block Cipher, Fiat-Shamir, Implementation, Post-quantum cryptography, Signatures, Unruh, Zero-Knowledge, block cipher, implementation, zero-knowledge, signatures",
author = "Melissa Chase and David Derler and Steven Goldfeder and Claudio Orlandi and Sebastian Ramacher and Christian Rechberger and Daniel Slamanig and Greg Zaverucha",
year = "2017",
month = oct,
day = "30",
doi = "10.1145/3133956.3133997",
language = "English",
isbn = "978-1-4503-4946-8",
series = "CCS '17",
pages = "1825--1842",
booktitle = "CCS 2017 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security",
publisher = "Association for Computing Machinery",
note = "null ; Conference date: 30-10-2017 Through 03-11-2017",
url = "https://ccs2017.sigsac.org/",

}

RIS

TY - GEN

T1 - Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives

AU - Chase, Melissa

AU - Derler, David

AU - Goldfeder, Steven

AU - Orlandi, Claudio

AU - Ramacher, Sebastian

AU - Rechberger, Christian

AU - Slamanig, Daniel

AU - Zaverucha, Greg

PY - 2017/10/30

Y1 - 2017/10/30

N2 - We propose a new class of post-quantum digital signature schemes that: (a) derive their security entirely from the security of symmetric-key primitives, believed to be quantum-secure, and (b) have extremely small keypairs, and, (c) are highly parameterizable. In our signature constructions, the public key is an image y = f (x) of a one-way function f and secret key x. A signature is a non-interactive zero-knowledge proof of x, that incorporates a message to be signed. For this proof, we leverage recent progress of Giacomelli et al. (USENIX'16) in constructing an efficient Ó-protocol for statements over general circuits. We improve this Ó-protocol to reduce proof sizes by a factor of two, at no additional computational cost. While this is of independent interest as it yields more compact proofs for any circuit, it also decreases our signature sizes. We consider two possibilities to make the proof non-interactive: The Fiat-Shamir transform and Unruh's transform (EUROCRYPT'12, '15,'16). The former has smaller signatures, while the latter has a security analysis in the quantum-accessible random oracle model. By customizing Unruh's transform to our application, the overhead is reduced to 1.6x when compared to the Fiat-Shamir transform, which does not have a rigorous post-quantum security analysis. We implement and benchmark both approaches and explore the possible choice of f , taking advantage of the recent trend to strive for practical symmetric ciphers with a particularly low number of multiplications and end up using LowMC (EUROCRYPT'15).

AB - We propose a new class of post-quantum digital signature schemes that: (a) derive their security entirely from the security of symmetric-key primitives, believed to be quantum-secure, and (b) have extremely small keypairs, and, (c) are highly parameterizable. In our signature constructions, the public key is an image y = f (x) of a one-way function f and secret key x. A signature is a non-interactive zero-knowledge proof of x, that incorporates a message to be signed. For this proof, we leverage recent progress of Giacomelli et al. (USENIX'16) in constructing an efficient Ó-protocol for statements over general circuits. We improve this Ó-protocol to reduce proof sizes by a factor of two, at no additional computational cost. While this is of independent interest as it yields more compact proofs for any circuit, it also decreases our signature sizes. We consider two possibilities to make the proof non-interactive: The Fiat-Shamir transform and Unruh's transform (EUROCRYPT'12, '15,'16). The former has smaller signatures, while the latter has a security analysis in the quantum-accessible random oracle model. By customizing Unruh's transform to our application, the overhead is reduced to 1.6x when compared to the Fiat-Shamir transform, which does not have a rigorous post-quantum security analysis. We implement and benchmark both approaches and explore the possible choice of f , taking advantage of the recent trend to strive for practical symmetric ciphers with a particularly low number of multiplications and end up using LowMC (EUROCRYPT'15).

KW - block cipher, post-quantum cryptography, signatures, zero-knowledge

KW - Block Cipher

KW - Fiat-Shamir

KW - Implementation

KW - Post-quantum cryptography

KW - Signatures

KW - Unruh

KW - Zero-Knowledge

KW - block cipher

KW - implementation

KW - zero-knowledge

KW - signatures

U2 - 10.1145/3133956.3133997

DO - 10.1145/3133956.3133997

M3 - Article in proceedings

SN - 978-1-4503-4946-8

T3 - CCS '17

SP - 1825

EP - 1842

BT - CCS 2017 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

PB - Association for Computing Machinery

CY - New York, NY, USA

Y2 - 30 October 2017 through 3 November 2017

ER -