## IACR News

Updates on the COVID-19 situation are on the Announcement channel.

Here you can see all recent updates to the IACR webpage. These updates are also available:

#### 06 August 2021

###### Juan Carlos Garcia-Escartin, Vincent Gimeno, Julio José Moyano-Fernández
ePrint Report
Hash functions are a basic cryptographic primitive. Certain hash functions try to prove security against collision and preimage attacks by reductions to known hard problems. These hash functions usually have some additional properties that allow for that reduction. Hash functions which are additive or multiplicative are vulnerable to a quantum attack using the hidden subgroup problem algorithm for quantum computers. Using a quantum oracle to the hash, we can reconstruct the kernel of the hash function, which is enough to find collisions and second preimages. When the hash functions are additive with respect to the group operation in an Abelian group, there is always an efficient implementation of this attack. We present concrete attack examples to provable hash functions, including a preimage attack to SWIFFT and collision finding for certain multiplicative homomorphic hash schemes.
###### Hyeokdong Kwon, Hyunjun Kim, Minjoo Sim, Wai-Kong Lee, Hwajeong Seo
ePrint Report
Rainbow signature is one of the finalist in National Institute of Standards and Technology (NIST) standardization. It is also the only signature candidate that is designed based on multivariate quadratic hard problem. Rainbow signature is known to have very small signature size compared to other post-quantum candidates. In this paper, we propose an efficient implementation technique to improve performance of Rainbow signature schemes. A parallel polynomial-multiplication on a 64-bit ARMv8 processor was proposed, wherein a look-up table was created by pre-calculating the $4\times4$ multiplication results. This technique was developed based on the observation that the existing implementation of Rainbow's polynomial-multiplication relies on the Karatsuba algorithm. It is not optimal due to the divide and conquer steps involved, whereby operations on $\mathbb{F}_{16}$ are divided into many small sub-fields of $\mathbb{F}_{4}$ and $\mathbb{F}_{2}$. Further investigations reveal that when the polynomial-multiplication in Rainbow signature is operated on $\mathbb{F}_{16}$, its operand is in 4-bit. Since the maximum combinations of a $4 \times 4$ multiplication is only 256, we constructed a 256-byte look-up table. According to the 4-bit constant, only 16-byte is loaded from the table at one time. The time-consuming multiplication is replaced by performing the table look-up. In addition, it calculates up-to 16 result values per register using characteristics of vector registers available on 64-bit ARMv8 processor. With the proposed fast polynomial-multiplication technique, we implemented the optimized Rainbow III and V. These two parameter sets are performed on $\mathbb{F}_{256}$, but they use sub-field $\mathbb{F}_{16}$ in the multiplication process. Therefore, the sub-field multiplication can be replaced with the proposed table look-up technique, which in turn omitted a significant number of operations. We have carried out the experiments on the Apple M1 processor, which shows up to 167.2$\times$ and 51.6$\times$ better performance enhancement at multiplier, and Rainbow signatures, respectively, compared to the previous implementation.
###### Nusrat Farzana, Farimah Farahmandi, Mark Tehranipoor
ePrint Report
A system-on-chip (SoC) security can be weakened by exploiting the potential vulnerabilities of the intellectual property (IP) cores used to implement the design and interaction among the IPs. These vulnerabilities not only increase the security verification effort but also can increase design complexity and time-to-market. The design and verification engineers should be knowledgeable about potential vulnerabilities and threat models at the early SoC design life cycle to protect their designs from potential attacks. However, currently, there is no publicly available repository that can be used as a base to develop such knowledge in practice. In this paper, we develop ‘SoC Security Property/Rule Database’ and make it available publicly to all researchers to facilitate and extend security verification effort to address this need. The database gathers a comprehensive security vulnerability and property list. It also provides all the corresponding design behavior that should be held in the design to ensure such vulnerabilities do not exist. The database contains 67 different vulnerability scenarios for which 105 corresponding security properties have been developed till now. This paper reviews the existing database and presents the methodologies we used to gather vulnerabilities and develop such comprehensive security properties. Additionally, this paper discusses the challenges for security verification and the utilization of this database to overcome the research challenges.
###### Erik-Oliver Blass, Florian Kerschbaum, Travis Mayberry
ePrint Report
We consider the problem of a client querying an encrypted binary tree structure, outsourced to an untrusted server. While the server must not learn the contents of the binary tree, we also want to prevent the client from maliciously crafting a query that traverses the tree out-of-order. That is, the client should not be able to retrieve nodes outside one contiguous path from the root to a leaf. Finally, the server should not learn which path the client accesses, but is guaranteed that the access corresponds to one valid path in the tree. This is an extension of protocols such as structured encryption, where it is only guaranteed that the tree's encrypted data remains hidden from the server.

To this end, we initiate the study of Iterative Oblivious Pseudorandom Functions (iOPRFs), new primitives providing two-sided, fully malicious security for these types of applications. We present a first, efficient iOPRF construction secure against both malicious clients and servers in the standard model, based on the DDH assumption. We demonstrate that iOPRFs are useful to implement different interesting applications, including an RFID authentication protocol and a protocol for private evaluation of outsourced decision trees. Finally, we implement and evaluate our full iOPRF construction and show that it is efficient in practice.
###### Quoc Huy Do, Pedram Hosseyni, Ralf Kuesters, Guido Schmitz, Nils Wenzler, Tim Wuertele
ePrint Report
Payment is an essential part of e-commerce. Merchants usually rely on third-parties, so-called payment processors, who take care of transferring the payment from the customer to the merchant. How a payment processor interacts with the customer and the merchant varies a lot. Each payment processor typically invents its own protocol that has to be integrated into the merchant’s application and provides the user with a new, potentially unknown and confusing user experience.

Pushed by major companies, including Apple, Google, Mastercard, and Visa, the W3C is currently developing a new set of standards to unify the online checkout process and “streamline the user’s payment experience”. The main idea is to integrate payment as a native functionality into web browsers, referred to as the Web Payment APIs. While this new checkout process will indeed be simple and convenient from an end-user perspective, the technical realization requires rather significant changes to browsers.

Many major browsers, such as Chrome, Firefox, Edge, Safari, and Opera, already implement these new standards, and many payment processors, such as Google Pay, Apple Pay, or Stripe, support the use of Web Payment APIs for payments. The ecosystem is constantly growing, meaning that the Web Payment APIs will likely be used by millions of people worldwide.

So far, there has been no in-depth security analysis of these new standards. In this paper, we present the first such analysis of the Web Payment APIs standards, a rigorous formal analysis. It is based on the Web Infrastructure Model (WIM), the most comprehensive model of the web infrastructure to date, which, among others, we extend to integrate the new payment functionality into the generic browser model.

Our analysis reveals two new critical vulnerabilities that allow a malicious merchant to over-charge an unsuspecting customer. We have verified our attacks using the Chrome implementation and reported these problems to the W3C as well as the Chrome developers, who have acknowledged these problems. Moreover, we propose fixes to the standard, which by now have been adopted by the W3C and Chrome, and prove that the fixed Web Payment APIs indeed satisfy strong security properties.
###### Mojtaba Rafiee
ePrint Report
A Multi-Client Functional Encryption (MCFE) scheme for set intersection is a cryptographic primitive that enables an evaluator to learn the intersection from all sets of a pre-determined number of clients, without need to learn the plaintext set of each individual client. In this paper, we propose a flexible version of the MCFE schemes for the set intersection, called Flexible Multi-Client Functional Encryption for Set Intersection (FMCFE). In our FMCFE scheme, the evaluator can learn the intersection from any flexible choice of sets (instead of all sets). In this regard, we redefine syntax and security notions of the MCFE schemes for the FMCFE schemes. In the literature, solving multi-client set intersection problem in polynomial time, such that only the intersection result is revealed (without additional information), is an open problem. In this paper, we propose a relaxed solution using FMCFE schemes to solve secure set intersection in polynomial time. We analyze that for practical use of secure multi-client set intersection, this relaxation is necessary. We also show that our scheme has the adaptive indistinguishability-based security under passive corruption. Our proof relies on the Symmetric eXternal Diffie-Hellman (SXDH) assumption in the standard model.
###### Endre (Silur) Abraham
ePrint Report
Mainstream hash functions such as SHA or BLAKE while generally efficient in their implementations, are not suitable for zero-knowledge boolean or arithmetic circuits due to their reliance on CPU designs. As a candidate hash function that uses only on trivial arithmetics which can be generalized to zeroknowledge circuits, the Ajtai lattice SIS-hasher has been proposed. In this paper we review Micciancio’s R-SIS generalization and argue about it’s circuit complexity, then we show how this R-SIS hasher can be used as a universal dynamic hash accumulator that has constant-time update and revocation complexity, and can be run on 16-bit hardware as well as smart contracts.
###### Aydin Abadi, Steven J. Murdoch, Thomas Zacharias
ePrint Report
Private Set Intersection protocols (PSIs) allow parties to compute the intersection of their private sets, such that nothing about the sets’ elements beyond the intersection is revealed. PSIs have a variety of applications, primarily in efficiently supporting data sharing in a privacy-preserving manner. At Eurocrypt 2019, Ghosh and Nilges pro- posed three efficient PSIs based on the polynomial representation of sets and proved their security against active adversaries. In this work, we show that these three PSIs are susceptible to several serious attacks. The attacks let an adversary (1) learn the correct intersection while making its victim believe that the intersection is empty, (2) learn a certain element of its victim’s set beyond the intersection, and (3) delete multiple elements of its victim’s input set. We explain why the proofs did not identify these attacks and propose a set of mitigations
###### Zi-Yuan Liu, Yi-Fan Tseng, Raylin Tso, Masahiro Mambo, Yu-Chi Chen
ePrint Report
With the rapid development of cloud computing, an increasing number of companies are adopting cloud storage to reduce overhead. However, to ensure the privacy of sensitive data, the uploaded data need to be encrypted before being outsourced to the cloud. The concept of public-key encryption with keyword search (PEKS) was introduced by Boneh \textit{et al.} to provide flexible usage of the encrypted data. Unfortunately, most of the PEKS schemes are not secure against inside keyword guessing attacks (IKGA), so the keyword information of the trapdoor may be leaked to the adversary. To solve this issue, Huang and Li presented public key authenticated encryption with keyword search (PAEKS) in which the trapdoor generated by the receiver is only valid for authenticated ciphertexts. With their seminal work, many PAEKS schemes have been introduced for the enhanced security of PAEKS. Some of them further consider the upcoming quantum attacks. However, our cryptanalysis indicated that in fact, these schemes could not withstand IKGA. To fight against the attacks from quantum adversaries and support the privacy-preserving search functionality, we first introduce a novel generic PAEKS construction in this work. We further present the first quantum-resistant PAEKS instantiation based on lattices. The security proofs showed that our instantiation not only satisfied the basic requirements but also achieved an enhanced security model, namely the multi-ciphertext and multi-trapdoor indistinguishability. Furthermore, the comparative results indicated that with only some additional expenditure, this instantiation could provide more secure properties, making it suitable for more diverse application environments.

#### 05 August 2021

###### St. George's, Grenada, 14 February - 18 February 2022
Event Calendar
Event date: 14 February to 18 February 2022
###### Join Research Centre - European Commission - Ispra, Italy
Job Posting
A Contractual Agent position FG IV in Ispra, Italy. The successful candidate will contribute to the activities of the Cyber and Digital Citizen Security Unit aiming at strengthening the citizen’ security and privacy by exploring innovative forensic technologies to support the fight against organised crimes. The successful candidate shall have a PhD degree - or a minimum of 5 years of full-time research or working experience after the first University degree giving access to doctoral (PhD) studies in the field of applied mathematics, cryptography, computer science, or machine learning and deep learning techniques, or similar. Solid knowledge and experience are required in:  Mathematics and more particularly cryptography or multi-linear algebra;  Machine learning and deep learning;  Ability to work in a multilingual and multicultural environment;  English language, at least C1 level both oral and written. The following knowledge or experience are an asset:  Experience with digital forensic techniques  Experience with High-Performance Computing platform

Closing date for applications:

Contact: Laurent Beslay jrc-e3-secretariat@ec.europa.eu

###### KU Leuven
Job Posting
In the Science, Engineering and Technology Group of KU Leuven, Faculty of Engineering Science, Department of Computer Science, there is a full-time academic vacancy for a professor in the area of secure and dependable software systems and services. This area is interpreted broadly, and includes for example the resilience, reliability and security of digital services, of software products and of Internet-based systems.
We are looking for an internationally orientated candidate with both educational competence and excellent research experience in computer science, and with extensive expertise in the field of secure and robust software systems and services. The new faculty member will become a member of the DistriNet unit, an internationally leading research group with recognized expertise in the areas of security, distributed systems and software engineering.
Candidates will be expected to develop an ambitious research programme that integrates well with the current research activities of the research group. Candidates should also be prepared to provide scientific services both within and outside the university, and to contribute to education at bachelor and master level.
DistrNet is the "sister" organization of COSIC, it deals with general security research whereas COSIC deals with cryptographic research. The two organizations are part of the CyberSecurity Flanders initiative, which supports their work.

Closing date for applications:

Contact: For more information please contact Prof. dr. ir. Wouter Joosen, tel.: +32 16 32 76 53, mail: wouter.joosen@kuleuven.be or Prof. dr. ir. Stefan Vandewalle, tel.: +32 16 32 76 54, mail: stefan.vandewalle@kuleuven.be.

###### Telecom Paris, Institut Polytechnique de Paris
Job Posting
Telecom Paris is hiring an Assistant/Associate Professor in Computer Science, with a preference for Cryptography and Cybersecurity. Application deadline: September, 24th 2021 Link: https://institutminestelecom.recruitee.com/l/en/o/maitre-de-conferences-en-informatique-fh-a-telecom-paris-cdi

Closing date for applications:

Contact: Phan Duong Hieu (hieu.phan@telecom-paris.fr)

#### 04 August 2021

Real World Crypto
RWC invites talk proposals to be considered for presentation at the symposium. The submission deadline is Sept. 1st.

Submission information can be found at: https://rwc.iacr.org/2022/contributed.php

#### 03 August 2021

###### Jean-Sebastien Coron, Agnese Gini
ePrint Report
At Crypto '99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the $n$ weights are also hidden. As an application, they showed how to break the Boyko et al. fast generator of random pairs $(x,g^x \pmod{p})$. The Nguyen-Stern algorithm works quite well in practice for moderate values of $n$, but its complexity is exponential in $n$. A polynomial-time variant was recently described at Crypto 2020, based on a multivariate technique, but the approach is heuristic only. In this paper, we describe a proven polynomial-time algorithm for solving the hidden subset-sum problem, based on statistical learning. In addition, we show that the statistical approach is also quite efficient in practice: using the FastICA algorithm, we can reach $n=250$ in reasonable time.
###### Gilles Macario-Rat, Jacques Patarin
ePrint Report
In this paper, we present a new perturbation for the design of multivariate schemes that we call Pepper''. From this idea, we present some efficient multivariate signature schemes with explicit parameters that resist all known attacks. In particular they resist the two main (and often very powerful) attacks in this area: the GrÃ¶bner attacks (to compute a solution of the system derived from the public key) and the MinRank attacks (to recover the secret key). Pepper can also be seen as a new perturbation that can be used to strengthen many other multivariate schemes. The Pepper'' perturbation works only for public key equations of degree (at least) 3. Despite this, the size of the public key may still be reasonable since we can use larger fields (and also maybe non dense equations). Furthermore, the size of the signatures can be very short.
###### Arush Chhatrapati
ePrint Report
In this compilational work, we combine various techniques from classical cryptography and steganography to construct ciphers that conceal multiple plaintexts in a single ciphertext. We name these "multi-ciphers". Most notably, we construct and cryptanalyze a Four-In-One-Cipher: the fi rst cipher which conceals four separate plaintexts in a single ciphertext. Following a brief overview of classical cryptography and steganography, we consider strategies that can be used to creatively combine these two fields to construct multi-ciphers. Finally, we cryptanalyze three multi-ciphers which were constructed using the techniques described in this paper. This cryptanalysis relies on both traditional algorithms that are used to decode classical ciphers and new algorithms which we use to extract the additional plaintexts concealed by the multi-ciphers. We implement these algorithms in Python, and provide code snippets. The primary goal of this work is to inform others who might be otherwise unfamiliar with the fields of classical cryptography and steganography from a new perspective which lies at the intersection of these two fields. The ideas presented in this paper could prove useful in teaching cryptography, statistics, mathematics, and computer science to future generations in a unique, interdisciplinary fashion. This work might also serve as a source of creative inspiration for other cipher-making, code-breaking enthusiasts.
###### Nils Wisiol
ePrint Report
We present the LP-PUF, a novel, Arbiter PUF-based, CMOS-compatible strong PUF design. We explain the motivation behind the design choices for LP-PUF and show evaluation results to demonstrate that LP-PUF has good uniqueness, low bias, and fair bit sensitivity and reliability values. Furthermore, based on analyses and discussion of the LR and splitting attacks, the reliability attacks, and MLP attack, we argue that the LP-PUF has potential to be secure against known PUF modeling attacks, which motivates a discussion of limitations of our study and future work with respect to the LP-PUF.
###### Lejla Batina, Łukasz Chmielewski, Björn Haase, Niels Samwel, Peter Schwabe
ePrint Report
This paper describes an ECC implementation computing the X25519 key-exchange protocol on the ARM-Cortex M4 microcontroller. This software comes with extensive mitigations against various side-channel and fault attacks and is, to our best knowledge, the first to claim affordable protection against multiple classes of attacks that are motivated by distinct real-world application scenarios. We also present the results of a comprehensive side-channel evaluation. We distinguish between X25519 with ephemeral keys and X25519 with static keys and show that the overhead to protect the two is about 36% and 239% respectively. While this might seem to be a high price to pay for security, we also show that even our (most protected) static implementation is more efficient than widely deployed ECC cryptographic libraries, which offer much fewer protections.

#### 02 August 2021

###### San Francisco, USA, 7 February - 10 February 2022
Event Calendar
Event date: 7 February to 10 February 2022