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 granular 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)
AIMER_L1_PARAM1	0.02	0.59	0.53	5,904
AIMER_L1_PARAM2	0.02	1.36	1.28	4,880
AIMER_L1_PARAM3	0.02	4.42	4.31	4,176
AIMER_L1_PARAM4	0.02	22.29	21.09	3,840
AIMER_L3_PARAM1	0.04	1.38	1.28	13,080
AIMER_L3_PARAM2	0.04	3.59	3.44	10,440
AIMER_L3_PARAM3	0.04	9.77	9.62	9,144
AIMER_L3_PARAM4	0.04	53.38	50.73	8,352
AIMER_L5_PARAM1	0.08	2.45	2.34	25,152
AIMER_L5_PARAM2	0.08	6.26	6.07	19,904
AIMER_L5_PARAM3	0.08	18.66	17.75	17,088
AIMER_L5_PARAM4	0.08	91.76	88.83	15,392

Publications

• Seongkwang Kim, Jincheol Ha, Mincheol Son, Byeonghak Lee.
  "Mitigation on the AIM Cryptanalysis".
  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".
  Cryptology ePrint Archive. Report 2022/1387. 2022. To appear in ACM CCS 2023.

Resources

• 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

• 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".
  Cryptology ePrint Archive. Report 2023/1397. 2023. To appear in Asiacrypt 2023.
• Hyeokdong Kwon, Minjoo Sim, Gyeongju Song, Minwoo Lee, and Hwajeong Seo.
  "Evaluating KpqC Algorithm Submissions: Balanced and Clean Benchmarking Approach".
  Cryptology ePrint Archive. Report 2023/1163. 2023.
• Minwoo Lee, Kyungbae Jang, Minjoo Sim, Gyeongju Song, and Hwajeong Seo.
  "High-speed Implementation of AIM symmetric primitives within AIMer digital signature".
  Cryptology ePrint Archive. Report 2023/1151. 2023.
• Fukang Liu, Mohammad Mahzoun, Morten Øygarden, and Willi Meier.
  "Algebraic Attacks on RAIN and AIM Using Equivalent Representations".
  Cryptology ePrint Archive. Report 2023/1133. 2023.
• 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.