# Selected Areas in Cryptography

Benjamin Smith, Huapeng Wu

► To cite this version:

Benjamin Smith, Huapeng Wu. Selected Areas in Cryptography. SAC 2022 - International Conference on Selected Areas in Cryptography, Lecture Notes in Computer Science, LNCS-13742, Springer International Publishing, 2022, Selected Areas in Cryptography, 978-3-031-58410-7. 10.1007/978-3-031-58411-4. hal-04579052

HAL Id: hal-04579052

https://inria.hal.science/hal-04579052v1

Submitted on 8 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
**Founding Editors**

Gerhard Goos

Juris Hartmanis

**Editorial Board Members**

Elisa Bertino, Purdue University, West Lafayette, IN, USA

Wen Gao, Peking University, Beijing, China

Bernhard Steffen, TU Dortmund University, Dortmund, Germany

Moti Yung, Columbia University, New York, NY, USA
The series Lecture Notes in Computer Science (LNCS), including its subseries Lecture Notes in Artificial Intelligence (LNAI) and Lecture Notes in Bioinformatics (LNBI), has established itself as a medium for the publication of new developments in computer science and information technology research, teaching, and education.

LNCS enjoys close cooperation with the computer science R & D community, the series counts many renowned academics among its volume editors and paper authors, and collaborates with prestigious societies. Its mission is to serve this international community by providing an invaluable service, mainly focused on the publication of conference and workshop proceedings and postproceedings. LNCS commenced publication in 1973.
Benjamin Smith · Huapeng Wu
Editors

Selected Areas
in Cryptography

29th International Conference, SAC 2022

Windsor, ON, Canada, August 24–26, 2022

Revised Selected Papers

<figure><img src="image_2.png" /></figure>

Springer
Editors

Benjamin Smith
Inria and École Polytechnique
Institut Polytechnique de Paris
Palaiseau, France

Huapeng Wu
Electrical and Computer Engineering
University of Windsor
Windsor, ON, Canada

ISSN 0302-9743
Lecture Notes in Computer Science
ISBN 978-3-031-58410-7

https://doi.org/10.1007/978-3-031-58411-4

ISSN 1611-3349 (electronic)
ISBN 978-3-031-58411-4 (eBook)

© The Editor(s) (if applicable) and The Author(s), under exclusive license
to Springer Nature Switzerland AG 2024

This work is subject to copyright. All rights are solely and exclusively licensed by the Publisher, whether
the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of
illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission
or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar
methodology now known or hereafter developed.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication
does not imply, even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.

The publisher, the authors and the editors are safe to assume that the advice and information in this book
are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the
editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors
or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in
published maps and institutional affiliations.

This Springer imprint is published by the registered company Springer Nature Switzerland AG
The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

Paper in this product is recyclable.
# Preface

Selected Areas in Cryptography (SAC) is Canada's annual cryptography research conference, held since 1994. The 29th edition of SAC took place at the University of Windsor, in Ontario, from August 24 to 26, 2022. Due to the ongoing COVID-19 pandemic, SAC 2022 was a hybrid event, with talks and discussion streamed online. The conference was preceded by a two-day summer school on August 22 and 23, with tutorials on isogeny-based cryptography and real-world post-quantum cryptography from Javad Doliskani, Benjamin Smith, and Douglas Stebila.

Each SAC conference covers four areas of research in cryptography. Three of these areas are permanent:

- Design and analysis of symmetric key primitives and cryptosystems, including block and stream ciphers, hash functions, MAC algorithms, cryptographic permutations, and authenticated encryption schemes;

- Efficient implementations of symmetric, public key, and post-quantum cryptography;

- Mathematical and algorithmic aspects of applied cryptography, including post-quantum cryptology.

The fourth area is selected as a special topic for each edition of SAC. For SAC 2022, this area was

- Theory and practice of isogeny-based cryptography.

We received 53 submissions; these were reviewed in a double-blind peer review process coordinated by the Program Committee. Regular submissions received three reviews; submissions involving members of the Program Committee received five reviews. Overall, our 34 Program Committee members, and their 28 subreviewers, wrote 172 reviews. Twenty-one of the submissions were accepted for presentation at SAC 2022 and publication in these proceedings.

There were three invited talks at SAC 2022. Nadia Heninger gave the Stafford Tavares lecture virtually: "On the passive compromise of TLS keys and other cryptanalytic adventures". Benjamin Wesolowski gave the second invited talk in person, on "Hard problems for isogeny-based cryptography". Finally, Wouter Castryck gave the third invited talk on "Efficient key recovery attacks on SIDH".

We would like to thank all of our colleagues who helped to make SAC 2022 a success, especially given the continuing complications all around the world due to the COVID-19 pandemic. We thank the Program Committee members for excellent work under a tight schedule. We are also grateful to the many others who participated in the review process: Gora Adj, Foteini Baldimtsi, Christof Beierle, Francesco Berti, Kevin Carrier, Arcangelo Castiglione, James Clements, Patrick Derbez, Thomas Espitau, Anna Lisa Ferrara, Manuela Flores, Clemente Galdi, Gayathri Garimella, Lydia Garms, Hosein Hadipour, Ryoma Ito, Amandine Jambert, Mikhail Kudinov, Norman Lahr, Fukang Liu, Liam Medley, Matthias Meijers, Mridul Nandi, Patrick Neumann, Richard Petri, Robert
Primas, Krijn Reijnders, and Florian Weber. We also thank the invited speakers for their excellent presentations, the summer school lecturers for animating a dynamic in-person event, and the SAC steering committee for their helpful advice and guidance. We are also appreciative of the financial support provided by the University of Windsor and by the Communications Security Establishment of Canada.

Finally, special thanks are due to Jo Asuncion for providing administrative assistance and we appreciate the help in the local arrangements offered by Lisa Geloso, Andria Ballo, Raqib Asif, Chen Zhang, and Hamza Bin Zaheer.

December 2023

Benjamin Smith

Huapeng Wu
# Organization

## Program Committee

<table><tr><td>Riham AlTawy</td><td>University of Victoria, Canada</td></tr><tr><td>Melissa Azouaoui</td><td>NXP Semiconductors, USA</td></tr><tr><td>Paulo Barreto</td><td>University of Washington Tacoma, USA</td></tr><tr><td>Jean-François Biasse</td><td>University of South Florida, USA</td></tr><tr><td>Olivier Blazy</td><td>École polytechnique, France</td></tr><tr><td>Claude Carlet</td><td>Université Paris 8, France and University of Bergen, Norway</td></tr><tr><td>Wouter Castryck</td><td>KU Leuven, Belgium</td></tr><tr><td>Carlos Cid</td><td>Simula UiB, Norway and Okinawa Institute of Science and Technology, Japan</td></tr><tr><td>Craig Costello</td><td>Microsoft Research, USA</td></tr><tr><td>Luca De Feo</td><td>IBM Research Europe, Switzerland</td></tr><tr><td>Maria Eichlseder</td><td>Graz University of Technology, Austria</td></tr><tr><td>Aurore Guillevic</td><td>Inria Nancy, France and Aarhus University, Denmark</td></tr><tr><td>Kathrin Hövelmanns</td><td>TU Eindhoven, the Netherlands</td></tr><tr><td>Michael J. Jacobson Jr.</td><td>University of Calgary, Canada</td></tr><tr><td>Yunwen Liu</td><td>Independent Researcher</td></tr><tr><td>Subhamoy Maitra</td><td>Indian Statistical Institute Kolkata, India</td></tr><tr><td>Kalikinkar Mandal</td><td>University of New Brunswick, Canada</td></tr><tr><td>Chloe Martindale</td><td>University of Bristol, UK</td></tr><tr><td>Barbara Masucci</td><td>University of Salerno, Italy</td></tr><tr><td>Ruben Niederhagen</td><td>Academia Sinica, Taiwan and University of Southern Denmark, Denmark</td></tr><tr><td>Abderrahmane Nitaj</td><td>University of Caen Normandy, France</td></tr><tr><td>Lorenz Panny</td><td>Academia Sinica, Taipei, Taiwan</td></tr><tr><td>Elizabeth A. Quaglia</td><td>Royal Holloway, University of London, UK</td></tr><tr><td>Francisco Rodríguez-Henríquez</td><td>CINVESTAV-IPN, México and CRC-TII, United Arab Emirates</td></tr><tr><td>Yann Rotella</td><td>Université de Versailles Saint-Quentin, France</td></tr><tr><td>Simona Samardjiska</td><td>RU Nijmegen, the Netherlands</td></tr><tr><td>Nicolas Sendrier</td><td>Inria, France</td></tr><tr><td>Leonie Simpson</td><td>Queensland University of Technology, Australia</td></tr><tr><td>Benjamin Smith</td><td>Inria and École polytechnique, Institut Polytechnique de Paris, France</td></tr></table>
Djiby Sow

Douglas Stebila

Katsuyuki Takashima

Yosuke Todo

Yuntao Wang

Huapeng Wu

Cheikh Anta Diop University, Senegal

University of Waterloo, Canada

Waseda University, Japan

NTT Secure Platform Laboratories, Japan

Osaka University, Japan

University of Windsor, Canada

## Additional Reviewers

Gora Adj

Foteini Baldimtsi

Christof Beierle

Francesco Berti

Kevin Carrier

Arcangelo Castiglione

James Clements

Patrick Derbez

Thomas Espitau

Anna Lisa Ferrara

Manuela Flores

Clemente Galdi

Gayathri Garimella

Lydia Garms

Hosein Hadipour

Ryoma Ito

Amandine Jambert

Mikhail Kudinov

Norman Lahr

Fukang Liu

Liam Medley

Matthias Meijers

Mridul Nandi

Patrick Neumann

Richard Petri

Robert Primas

Krijn Reijnders

Florian Weber
Invited Talks
# On the Passive Compromise of TLS Keys and Other Cryptanalytic Adventures

Nadia Heninger

Computer Science and Engineering, University of California San Diego, 9500 Gilman Drive, La Jolla, CA, 92093-0021 USA

nadiah@cs.ucsd.edu

**Abstract.** It is well known in the cryptographic literature that the most common digital signature schemes used in practice can fail catastrophically in the presence of faults during computation. I will discuss recent joint work using passive and active network measurements to analyze organically-occurring faults in billions of digital signatures generated by tens of millions of hosts. We find that a persistent rate of apparent hardware faults in unprotected implementations has resulted in compromised certificate RSA private keys for years. Finally, we will put this work in the context of other cryptographic flaws that can be exploited in the wild.
# Hard Problems for Isogeny-Based Cryptography

Benjamin Wesolowski

Institut de Mathématiques de Bordeaux, 351, Cours de la Libération, 33405 Talence,
France

benjamin.wesolowski@ens-lyon.fr

**Abstract.** Isogeny-based cryptography is one of the few branches of public-key cryptography that promises to resist quantum attacks. The security of these cryptosystems relates to the (presumed) hardness of a variety of computational problems: finding paths in large “isogeny graphs”, computing endomorphisms of elliptic curves, or inverting group actions. We present these problems, and analyse how they relate to each other: which are equivalent, easier, or harder, and how they relate to cryptosystems.
Efficient Key Recovery Attacks on SIDH

Wouter Castryck

Department of Electrical Engineering, KU Leuven, Oude Markt 13 - bus 5005, 3000
Leuven, Belgium

wouter.castryck@gmail.com

**Abstract.** It is well known in the cryptographic literature that the most common digital signature schemes used in practice can fail catastrophically in the presence of faults during computation. I will discuss recent joint work using passive and active network measurements to analyze organically-occuring faults in billions of digital signatures generated by tens of millions of hosts. We find that a persistent rate of apparent hardware faults in unprotected implementations has resulted in compromised certificate RSA private keys for years. Finally, we will put this work in the context of other cryptographic flaws that can be exploited in the wild.
# Contents

## Lattices and ECC

Profiling Side-Channel Attacks on Dilithium: A Small Bit-Fiddling Leak

Breaks It All .................................................................................... 3
Vincent Quentin Ulitzsch, Soundes Marzougui, Mehdi Tibouchi,
and Jean-Pierre Seifert

On the Weakness of Ring-LWE mod Prime Ideal q by Trace Map .................... 33
Tomoka Takahashi, Shinya Okumura, and Atsuko Miyaji

2DT-GLS: Faster and Exception-Free Scalar Multiplication in the GLS254

Binary Curve .................................................................................... 53
Marius A. Aardal and Diego F. Aranha

## Differential Cryptanalysis

Key-Recovery Attacks on CRAFT and WARP ........................................ 77
Ling Sun, Wei Wang, and Meiqin Wang

Differential Analysis of the Ternary Hash Function Troika ...................... 96
Christina Boura, Margot Funk, and Yann Rotella

Another Look at Differential-Linear Attacks ........................................ 116
Orr Dunkelman and Ariel Weizman

## Cryptographic Primitives

Injective Rank Metric Trapdoor Functions with Homogeneous Errors ............ 139
Étienne Burle, Philippe Gaborit, Younes Hatri, and Ayoub Otmani

PERKS: Persistent and Distributed Key Acquisition for Secure Storage

from Passwords ............................................................................ 159
Gareth T. Davies and Jeroen Pijnenburg

Improved Circuit-Based PSI via Equality Preserving Compression ............ 190
Kyoohyung Han, Dukjae Moon, and Yongha Son
## Isogeny-based Cryptography I

Revisiting Meet-in-the-Middle Cryptanalysis of SIDH/SIKE with Application to the $\$IKEp182$ Challenge

Aleksei Udovenko and Giuseppe Vitto

213

Patient Zero & Patient Six: Zero-Value and Correlation Attacks on CSIDH and SIKE

Fabio Campos, Michael Meyer, Krijn Reijnders, and Marc Stöttinger

234

An Effective Lower Bound on the Number of Orientable Supersingular Elliptic Curves

Antonin Leroux

263

## Block Ciphers

Finding All Impossible Differentials When Considering the DDT

Kai Hu, Thomas Peyrin, and Meiqin Wang

285

A Three-Stage MITM Attack on LowMC from a Single Plaintext-Ciphertext Pair

Lulu Zhang, Meicheng Liu, and Dongdai Lin

306

Collision-Based Attacks on White-Box Implementations of the AES Block Cipher

Jiqiang Lu, Mingxue Wang, Can Wang, and Chen Yang

328

## Differential Cryptanalysis II

Advancing the Meet-in-the-Filter Technique: Applications to CHAM and KATAN

Alex Biryukov, Je Sen Teh, and Aleksei Udovenko

355

Improved the Automated Evaluation Algorithm Against Differential Attacks and Its Application to WARP

Jiali Shi, Guoqiang Liu, and Chao Li

376

## Isogeny-based Cryptography II

Faster Cryptographic Hash Function from Supersingular Isogeny Graphs

Javad Doliskani, Geovandro C. C. F. Pereira, and Paulo S. L. M. Barreto

399
Protocols and PRFs

From Plaintext-Extractability to IND-CCA Security ...................... 419
Ehsan Ebrahimi

Farasha: A Provable Permutation-Based Parallelizable PRF .................... 437
Najwa Aaraj, Emanuele Bellini, Ravindra Jejurikar, Marc Manzano,
Raghvendra Rohit, and Eugenio Salazar

A Sponge-Based PRF with Good Multi-user Security .......................... 459
Arghya Bhattacharjee, Ritam Bhaumik, and Mridul Nandi

Author Index ........................................................................ 479