SOFIA: MQ-based signatures in the QROM

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

doi:10.1007/978-3-319-76581-5_1

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 proceeding › Conference contribution › Academic › peer-review

14 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.

Original language	English
Title of host publication	Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
Editors	Michel Abdalla, Ricardo Dahab
Publisher	Springer
Pages	3-33
Number of pages	31
ISBN (Print)	9783319765778
DOIs	https://doi.org/10.1007/978-3-319-76581-5_1
Publication status	Published - 2018
Event	21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018) - Rio de Janeiro, Brazil Duration: 25 Mar 2018 → 29 Mar 2018 Conference number: 21 https://pkc.iacr.org/2018/

Publication series

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

Conference

Conference	21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018)
Abbreviated title	PKC2018
Country/Territory	Brazil
City	Rio de Janeiro
Period	25/03/18 → 29/03/18
Internet address	https://pkc.iacr.org/2018/

Funding

This work was supported by the Netherlands Organization for Scientific Research (NWO) under Veni 2013 project 13114, by the European Commission through the ICT Programme under contract ICT-645622 PQCRYPTO and by the Faculty of Computer Science and Engineering at the “Ss. Cyril and Methodius” University.

Keywords

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

Access to Document

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

Cite this

Chen, M. S., Hülsing, A., Rijneveld, J., Samardjiska, S., & Schwabe, P. (2018). SOFIA: MQ-based signatures in the QROM. In M. Abdalla, & R. Dahab (Eds.), 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. https://doi.org/10.1007/978-3-319-76581-5_1

Chen, Ming Shing ; Hülsing, Andreas ; Rijneveld, Joost et al. / 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. editor / Michel Abdalla ; Ricardo Dahab. 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{\textquoteright}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{\textquoteright}s transform, Vectorized implementation, Unruh's transform",

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",

editor = "Michel Abdalla and Ricardo Dahab",

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

address = "Germany",

note = "21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018), PKC2018 ; Conference date: 25-03-2018 Through 29-03-2018",

url = "https://pkc.iacr.org/2018/",

}

Chen, MS, Hülsing, A, Rijneveld, J, Samardjiska, S & Schwabe, P 2018, SOFIA: MQ-based signatures in the QROM. in M Abdalla & R Dahab (eds), 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. https://doi.org/10.1007/978-3-319-76581-5_1

SOFIA: MQ-based signatures in the QROM. / Chen, Ming Shing; Hülsing, Andreas; Rijneveld, Joost et al.
Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings. ed. / Michel Abdalla; Ricardo Dahab. 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 proceeding › Conference contribution › Academic › peer-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

N1 - Conference code: 21

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

KW - Unruh's transform

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

AN - SCOPUS:85044008500

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

A2 - Abdalla, Michel

A2 - Dahab, Ricardo

PB - Springer

T2 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2018)

Y2 - 25 March 2018 through 29 March 2018

ER -

Chen MS, Hülsing A, Rijneveld J, Samardjiska S, Schwabe P. SOFIA: MQ-based signatures in the QROM. In Abdalla M, Dahab R, editors, 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)). doi: 10.1007/978-3-319-76581-5_1

SOFIA: MQ-based signatures in the QROM

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this