{"id":2018,"date":"2017-09-08T06:04:45","date_gmt":"2017-09-08T06:04:45","guid":{"rendered":"https:\/\/prismacloud.eu\/?p=2018"},"modified":"2018-04-03T12:16:39","modified_gmt":"2018-04-03T12:16:39","slug":"post-quantum-zero-knowledge-and-signatures-from-symmetric-key-primitives","status":"publish","type":"post","link":"https:\/\/prismacloud.eu\/post-quantum-zero-knowledge-and-signatures-from-symmetric-key-primitives\/","title":{"rendered":"Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives"},"content":{"rendered":"

Title<\/strong><\/p>\n

Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives<\/p>\n

Authors<\/strong><\/p>\n

Melissa Chase (Microsoft Research), David Derler (Graz University of Technology), Steven Goldfeder (Princeton University), Claudio Orlandi (Aarhus University), Sebastian Ramacher (Graz University of Technology), Christian Rechberger (Graz University of Technology & Denmark Technical University), Daniel Slamanig (AIT Austrian Institute of Technology), Greg Zaverucha (Microsoft Research)<\/p>\n

Abstract<\/strong><\/p>\n

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\u201916) in constructing an efficient \u03a3-protocol for statements over general circuits. We improve this \u03a3-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\u2019s transform (EUROCRYPT\u201912, 15,\u201916). The former has smaller signatures, while the latter has a security analysis in the quantum-accessible random oracle model. By customizing Unruh\u2019s 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\u201915).<\/p>\n

Venue\u00a0<\/strong><\/p>\n

24th ACM Conference on Computer and Communications Security (ACM CCS 2017)<\/p>\n

Place and Date<\/strong><\/p>\n

Dallas, Texas, USA. October 30 \u2013 November 3, 2017<\/p>\n

[Download<\/a>]<\/p>\n","protected":false},"excerpt":{"rendered":"

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\u201916) in constructing an efficient \u03a3-protocol for statements over general circuits. We improve this \u03a3-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\u2019s transform (EUROCRYPT\u201912, 15,\u201916). The former has smaller signatures, while the latter has a security analysis in the quantum-accessible random oracle model. By customizing Unruh\u2019s 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\u201915).<\/p>\n","protected":false},"author":2,"featured_media":1575,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,8],"tags":[],"_links":{"self":[{"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/posts\/2018"}],"collection":[{"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/comments?post=2018"}],"version-history":[{"count":3,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/posts\/2018\/revisions"}],"predecessor-version":[{"id":2586,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/posts\/2018\/revisions\/2586"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/media\/1575"}],"wp:attachment":[{"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/media?parent=2018"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/categories?post=2018"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prismacloud.eu\/wp-json\/wp\/v2\/tags?post=2018"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}