AIMer Signature

About AIMer

AIMer is a signature scheme which is obtained from a zero-knowledge proof of preimage knowledge for a certain one-way function. AIMer consists of two parts: a customized version of the BN++ proof system, and the AIM one-way function. The security of both parts solely depends on the security of the underlying symmetric primitives.

Advantages

The security of AIMer depends only on the security of the underlying symmetric primitives.
Among the signature schemes whose security depends only on symmetric primitives, AIMer enjoys the smallest signature size.
AIMer enjoys small secret and public key size.
Key generation is simple and fast.
AIMer provides a trade-off between the execution time and the signature size.
AIMer is resistant to the reuse of the public randomnesses such as iv and salt.

Performance

Environment: Intel Xeon E5-1650 v3 @ 3.50 GHz with 128 GB RAM, TurboBoost and Hyper-threading disabled, gcc 7.5.0 with -O3 option.

Scheme	Keygen (ms)	Sign (ms)	Verify (ms)	Size (B)
aimer128f	0.03	0.42	0.41	5,888
aimer128s	0.03	3.18	3.13	4,160
aimer192f	0.05	1.04	1.03	13,056
aimer192s	0.05	7.94	7.86	9,120
aimer256f	0.10	2.07	2.03	25,120
aimer256s	0.10	15.26	14.81	17,056

Publications

KpqC Competition 2nd Round Submission (v2.0): (pdf)
Seongkwang Kim, Jincheol Ha, Mincheol Son, Byeonghak Lee.
"Efficacy and Mitigation of the Cryptanalysis on AIM".
Cryptology ePrint Archive. Report 2023/1474. 2023.
NIST PQC Project Submission (v1.0): (pdf)
KpqC Competition Submission (v0.9): (pdf)
Seongkwang Kim, Jincheol Ha, Mincheol Son, Byeonghak Lee, Dukjae Moon, Joohee Lee, Sangyub Lee, Jihoon Kwon, Jihoon Cho, Hyojin Yoon and Jooyoung Lee.
"AIM: Symmetric Primitive for Shorter Signatures with Stronger Security".
2023 ACM SIGSAC Conference on Computer and Communications Security (CCS 2023).

Resources

The 5th NIST PQC Standardization Conference (2024. Apr. 11): (pdf)
The 5th NIST PQC Standardization Conference (2024. Apr. 11), Poster: (pdf)
KpqC 2024 Winter Camp Slides (2024. Feb. 28): (pdf)
Submission to KpqC Competition Round 2 (v2.0): (zip)
ACM CCS 2023 Slides (2023. Nov. 27): (pdf)
KpqC 7th Workshop Slides (2023. Nov. 14): (pdf)
Summary for mitigations (2023. Sep. 25): pqc-forum/kpqc-bulletin
2nd Oxford PQC Summit Slides (2023. Sep. 05): (pdf)
2023 Ewha-KMS International Worshop on Cryptography Slides (2023. Jul. 12): (pdf)
Algebraic analysis of AIM: (github)
Submission to NIST PQC Additional Signature Round 1 (v1.0): (zip)
Submission to KpqC Competition Round 1 (v0.9): (zip)
KpqC Winter Camp Slides (2023. Feb. 24): (pdf)

Third-party Analysis

Matthias J. Kannwischer, Markus Krausz, Richard Petri, and Shang-Yi Yang.
"pqm4: Benchmarking NIST Additional Post-Quantum Signature Schemes on Microcontrollers".
Cryptology ePrint Archive. Report 2024/112. 2024.
Jolijn Cottaar, Kathrin Hövelmanns, Andreas Hülsing, Tanja Lange, Mohammad Mahzoun, Alex Pellegrini, Alberto Ravagnani, Sven Schäge, Monika Trimoska, and Benne de Weger.
"Report on evaluation of KpqC candidates".
Cryptology ePrint Archive. Report 2023/1853. 2023.
Yongryeol Choi, Mingi Kim, Youngbeom Kim, Jingyo Song, Jaehwan Jin, Heeseok Kim, and Seog Chung Seo.
"KpqBench: Performance and Implementation Security Analysis of KpqC Competition Round 1 Candidates".
Cryptology ePrint Archive. Report 2023/1437. 2023.
Kaiyi Zhang, Qingju Wang, Yu Yu, Chun Guo, and Hongrui Cui.
"Algebraic Attacks on Round-Reduced RAIN and Full AIM-III".
The 29th Annual International Conference on the Theory and Applications of Cryptology and Information Security (Asiacrypt 2023).
Hyeokdong Kwon, Minjoo Sim, Gyeongju Song, Minwoo Lee, and Hwajeong Seo.
"Evaluating KpqC Algorithm Submissions: Balanced and Clean Benchmarking Approach".
International Conference on Information Security Applications (WISA 2023).
Minwoo Lee, Kyungbae Jang, Minjoo Sim, Gyeongju Song, and Hwajeong Seo.
"High-speed Implementation of AIM symmetric primitives within AIMer digital signature".
The 7th International Conference on Mobile Internet Security (MobiSec 2023).
Fukang Liu, Mohammad Mahzoun, Morten Øygarden, and Willi Meier.
"Algebraic Attacks on RAIN and AIM Using Equivalent Representations".
IACR Transactions on Symmetric Cryptology 2023(4): 166-186.
Kyungbae Jang, Dukyoung Kim, Yujin Oh, Sejin Lim, Yujin Yang, Hyunji Kim, and Hwajeong Seo.
"Quantum Implementation of AIM: Aiming for Low-Depth".
Cryptology ePrint Archive. Report 2023/337. 2023.