Implementing CAESAR candidate Prøst on ARM11

  • Thom Wiggers Radboud University Nijmegen


Prøst was a contestant in the CAESAR competition for Authenticated Encryption. I optimised Prøst for the ARM11 microprocessor architecture. By trying to find a provably minimal program for one of the sub-operations, I found a new approach to implementing MixSlices, one of the sub-operations in Prøst's permute function. This new implementation has 33% fewer arithmetic operations than the original version. Using this result and by implementing Prøst in assembly and applying micro-optimisations, a performance gain of 28% to 48% was achieved.


1. Andreeva, E., Bilgin, B., Bogdanov, A., Luykx, A., Mennink,
B., Mouha, N., and Yasuda, K. APE: authenticated
permutation-based encryption for lightweight cryptography.
Cryptology ePrint Archive, Report 2013/791.
2013. address:

2. Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B.,
Tischhauser, E., and Yasuda, K. Parallelizable and
authenticated online ciphers. Cryptology ePrint Archive,
Report 2013/790. 2013. address: http://eprint.iacr.

3. ARM Limited. Arm1176jzf-s technical reference manual.
Revision: r0p7. address: http://infocenter.arm.

4. Bellare, M., Rogaway, P., andWagner, D. A conventional
authenticated-encryption mode. 2003. Address:

5. D. J. Bernstein and T. Lange, eds. Supercop. eBACS:
ECRYPT Benchmarking of Cryptographic Systems.

6. Boyar, J., Matthews, P., and Peralta, R. Logic minimization
techniques with applications to cryptology.
Journal of Cryptology, 26(2), 2013: 280–312.

7. CAESAR: competition for authenticated encryption:
security, applicability, and robustness. Address: http:

8. Dobraunig, C., Eichlseder, M., and Mendel, F. Relatedkey
forgeries for Prøst-OTR. Cryptology ePrint Archive,
Report 2015/091. 2015. address: http://eprint.iacr.

9. Fuhs, C., and Schneider-Kamp, P. Synthesizing shortest
linear straight-line programs over GF(2) using SAT.
Proc. SAT’10, 71–84.

10. Kavun, E. B., Lauridsen, M. M., Leander, G., Rechberger,
C., Schwabe, P., and Yalc¸ın, T. Prøst v1.1. 21st June
2014. address:

11. Krawczyk, H. The order of encryption and authentication
for protecting communications (or: how secure is
ssl?) Advances in Cryptology – CRYPTO 2001. 2001,

12. Le Berre, D., and Parrain, A. The sat4j library, release
2.2 system description. Journal on Satisfiability,
Boolean Modeling and Computation, 7, 2010: 59–64.

13. McGrew, D. A., and Viega, J. The galois/counter mode
of operation (GCM). address:

14. Minematsu, K. Parallelizable rate-1 authenticated
encryption from pseudorandom functions. Cryptology
ePrint Archive, Report 2013/628. 2013. address: http:

15. Papadimitriou, C. H., and Yannakakis, M. Optimization,
approximation, and complexity classes. Journal of
Computer and System Sciences, 43(3), 1991: 425–440.

16. Rijneveld, J. Implementing Prøst on the Cortex A8
using internal parallelisation. 2015-01. Address: https:

17. Rogaway, P. Authenticated-encryption with associated-
data. Proceedings of the 9th ACM conference on
Computer and communications security. 2002, 98–107.

Author Biography

Thom Wiggers, Radboud University Nijmegen
Institute for Computing and Information Sciences
How to Cite
WIGGERS, Thom. Implementing CAESAR candidate Prøst on ARM11. Student Undergraduate Research E-journal!, [S.l.], v. 1, nov. 2015. ISSN 2468-0443. Available at: <>. Date accessed: 20 oct. 2020.