SOFIA: MQ-based signatures in the QROM

Ming Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, Peter Schwabe

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

Abstract

We propose SOFIA, the first MQ -based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh’s transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM. Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128-bit post-quantum security. The result is SOFIA-4-128 with parameters carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.

LanguageEnglish
Title of host publicationPublic-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
PublisherSpringer
Pages3-33
Number of pages31
ISBN (Print)9783319765778
DOIs
StatePublished - 2018
Event21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018) - Rio de Janeiro, Brazil
Duration: 25 Mar 201829 Mar 2018
Conference number: 21
https://pkc.iacr.org/2018/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10769 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018)
Abbreviated titlePKC2018
CountryBrazil
CityRio de Janeiro
Period25/03/1829/03/18
Internet address

Fingerprint

Random Oracle Model
Signature
ROM
Timing Attack
Identification Scheme
Security Analysis
Concretes
Signature Scheme
Maximise
Transform
Minimise
Side channel attack

Keywords

  • 5-pass identification schemes
  • Multivariate cryptography
  • Post-quantum cryptography
  • QROM
  • Unruh’s transform
  • Vectorized implementation

Cite this

Chen, M. S., Hülsing, A., Rijneveld, J., Samardjiska, S., & Schwabe, P. (2018). SOFIA: MQ-based signatures in the QROM. In Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings (pp. 3-33). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10769 LNCS). Springer. DOI: 10.1007/978-3-319-76581-5_1
Chen, Ming Shing ; Hülsing, Andreas ; Rijneveld, Joost ; Samardjiska, Simona ; Schwabe, Peter. / SOFIA: MQ-based signatures in the QROM. Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Springer, 2018. pp. 3-33 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{c2db2bce81074a94abd1590e13e4835a,
title = "SOFIA: MQ-based signatures in the QROM",
abstract = "We propose SOFIA, the first MQ -based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh’s transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM. Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128-bit post-quantum security. The result is SOFIA-4-128 with parameters carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.",
keywords = "5-pass identification schemes, Multivariate cryptography, Post-quantum cryptography, QROM, Unruh’s transform, Vectorized implementation",
author = "Chen, {Ming Shing} and Andreas H{\"u}lsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe",
year = "2018",
doi = "10.1007/978-3-319-76581-5_1",
language = "English",
isbn = "9783319765778",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "3--33",
booktitle = "Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings",
address = "Germany",

}

Chen, MS, Hülsing, A, Rijneveld, J, Samardjiska, S & Schwabe, P 2018, SOFIA: MQ-based signatures in the QROM. in Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10769 LNCS, Springer, pp. 3-33, 21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018), Rio de Janeiro, Brazil, 25/03/18. DOI: 10.1007/978-3-319-76581-5_1

SOFIA: MQ-based signatures in the QROM. / Chen, Ming Shing; Hülsing, Andreas; Rijneveld, Joost; Samardjiska, Simona; Schwabe, Peter.

Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Springer, 2018. p. 3-33 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10769 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - SOFIA: MQ-based signatures in the QROM

AU - Chen,Ming Shing

AU - Hülsing,Andreas

AU - Rijneveld,Joost

AU - Samardjiska,Simona

AU - Schwabe,Peter

PY - 2018

Y1 - 2018

N2 - We propose SOFIA, the first MQ -based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh’s transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM. Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128-bit post-quantum security. The result is SOFIA-4-128 with parameters carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.

AB - We propose SOFIA, the first MQ -based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh’s transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM. Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128-bit post-quantum security. The result is SOFIA-4-128 with parameters carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.

KW - 5-pass identification schemes

KW - Multivariate cryptography

KW - Post-quantum cryptography

KW - QROM

KW - Unruh’s transform

KW - Vectorized implementation

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

U2 - 10.1007/978-3-319-76581-5_1

DO - 10.1007/978-3-319-76581-5_1

M3 - Conference contribution

SN - 9783319765778

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 33

BT - Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings

PB - Springer

ER -

Chen MS, Hülsing A, Rijneveld J, Samardjiska S, Schwabe P. SOFIA: MQ-based signatures in the QROM. In Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. Springer. 2018. p. 3-33. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Available from, DOI: 10.1007/978-3-319-76581-5_1