International Association
for Cryptologic Research

Keeping privacy for every entity in outsourced computation is always a crucial issue. For efficient secure computation, homomorphic encryption (HE) can be one of nice solutions. Especially, multikey homomorphic encryption (MKHE) which allows homomorphic evaluation on encrypted data under different keys can be one of the simplest solutions for a secure computation which handles multiple users' data. However, the current main problem of MKHE is that the dimension of its evaluated ciphertext relies on the number of users. To solve this problem, there are several variants of multikey homomorphic encryption schemes to keep the size of ciphertext constant for a fixed number of users. However, users interact one another before computation to provide their inputs, which increases setup complexity. Moreover, all the existing MKHE schemes and their variants have unique benefits which cannot be easily achieved at the same time in one scheme. In other words, each type of scheme has a suitable computational scenario to put its best performance.

In this paper, we suggest more efficient evaluation key generation algorithm for the existing variants of MKHE schemes which have no ciphertext expansion for a fixed number of users. Our method only requires a very simple and minor pre-processing; distributing public keys, which is not counted as a round at all in many other applications. As a result, participants have less communication, computation, and memory cost in online phase. Moreover, we provide a practical conversion algorithm between the two types of schemes in order to \emph{efficiently} utilize both schemes' advantages together in more various applications. We also provide detailed comparison among similar results so that users can choose a suitable scheme for their homomorphic encryption based application scenarios.

Mixed Integer Linear Programming (MILP) solvers have become one of the most powerful tools for searching cryptographic characteristics, including differentials, impossible differentials, and division trails. Generally, one MILP problem can be formulated by several different MILP models, and the models with fewer constraints and variables are usually easier to solve. How to model a problem with the least number of constraints is also an interesting mathematical problem. In this paper, we discuss this problem in a general form. Specifically, given a set $C \subset F_2^n$, let $L$ be a set of inequalities, and we say $L$ describes $C$ if the inequalities in $L$ only involve $n$ variables and the solution set to $L$ is exactly $C$. Our goal is to find such a set $L$ with the least number of inequalities. We present a brand new approach, named as SuperBall approach, for resolving this problem completely. Our approach is able to generate all available inequalities. Once these inequalities are obtained, Sasaki and Todo's method is used to find out the smallest subset of inequalities that describes $C$. If Sasaki and Todo's method succeeds, the found subset will be proved as the smallest. As a result, we found the smallest subsets of inequalities that describe the Sboxes of Keccak and APN-6. The previous best results were 34 and 167, presented in FSE 2020, and we decreased these numbers to 26 and 145. Moreover, we can prove these numbers are the smallest in case no dummy variables are involved.

The Messaging Layer Security (MLS) project is an IETF effort aiming to establish an industry- wide standard for secure group messaging (SGM). Its development is supported by several major secure-messaging providers (with a combined user base in the billions) and a growing body of academic research. MLS has evolved over many iterations to become a complex, non-trivial, yet relatively ad-hoc cryptographic protocol. In an effort to tame its complexity and build confidence in its security, past analyses of MLS have restricted themselves to sub-protocols of MLS—most prominently a type of sub-protocol embodying so-called continuous group key agreement (CGKA). However, to date the task of proving or even defining the security of the full MLS protocol has been left open. In this work, we fill in this missing piece. First, we formally capture the security of SGM protocols by defining a corresponding security game, which is parametrized by a safety predicate that characterizes the exact level of security achieved by a construction. Then, we cast MLS as an SGM protocol, showing how to modularly build it from the following three main components (and some additional standard cryptographic primitives) in a black-box fashion: (a) CGKA, (b) forward-secure group AEAD (FS-GAEAD), which is a new primitive and roughly corresponds to an “epoch” of group messaging, and (c) a so-called PRF-PRNG, which is a two-input hash function that is a pseudorandom function (resp. generator with input) in its first (resp. second) input. Crucially, the security predicate for the SGM security of MLS can be expressed purely as a function of the security predicates of the underlying primitives, which allows to swap out any of the components and immediately obtain a security statement for the resulting SGM construction. Furthermore, we provide instantiations of all component primitives, in particular of CGKA with MLS’s TreeKEM sub-protocol (which we prove adaptively secure) and of FS-GAEAD with a novel construction (which has already been adopted by MLS). Along the way we introduce a collection of new techniques, primitives, and results with applications to other SGM protocols and beyond. For example, we extend the Generalized Selective Decryption proof technique (which is central in CGKA literature) and prove adaptive security for another (practical) more secure CGKA protocol called RTreeKEM (Alwen et al., CRYPTO ’20). The modularity of our approach immediately yields a corollary characterizing the security of an SGM construction using RTreeKEM.

Let $E_1$ be an ordinary pairing-friendly elliptic curve of embedding degree $k > 1$ over a finite field $\mathbb{F}_{\!q}$. Besides, let $E_2$ be a twist of $E_1$ of degree $d := \#\mathrm{Aut}(E_1)$ over the field $\mathbb{F}_{\!q^e}$, where $e := k/d \in \mathbb{N}$. As is customary, for a common prime divisor $r$ of the orders $N_1 := \#E_1(\mathbb{F}_{\!q})$ and $N_2 := \#E_2(\mathbb{F}_{\!q^e})$ denote by $\mathbb{G}_1 \subset E_1(\mathbb{F}_{\!q})$ and $\mathbb{G}_2 \hookrightarrow E_2(\mathbb{F}_{\!q^e})$ the eigenspaces of the Frobenius endomorphism on $E_1[r] \subset E_1(\mathbb{F}_{\!q^k})$, associated with the eigenvalues $1$, $q$ respectively.

This short note explains how to hash onto $\mathbb{G}_2$ more efficiently and why we do not need to hash directly onto $\mathbb{G}_1$. In the first case, we significantly exploit the presence of clearing the cofactor $c_2 := N_2/r$. In the second one, on the contrary, clearing the cofactor $c_1 := N_1/r$ can be fully avoided. The fact is that optimal ate pairings $a\!: \mathbb{G}_2 \!\times\! \mathbb{G}_1 \to \mu_r \subset \mathbb{F}_{\!q^k}^*$ can be painlessly (unlike $E_2(\mathbb{F}_{\!q^e}) \!\times\! \mathbb{G}_1$) extended to $\mathbb{G}_2 \!\times\! E_1(\mathbb{F}_{\!q})$, at least in main pairing-based protocols. Throughout the text we mean hashing indifferentiable from a random oracle.

At the moment, the curve BLS12-381 (with $e = 2$) is the most popular in practice. Earlier for this curve (and a number of others) the author constructed encodings $\mathbb{F}_{\!q}^2 \to E_1(\mathbb{F}_{\!q})$ and $\mathbb{F}_{\!q} \to E_2(\mathbb{F}_{\!q^2})$ computable in constant time of one exponentiation in $\mathbb{F}_{\!q}$. Combining the new ideas with these encodings, we obtain hash functions $\{0, 1\}^* \to E_1(\mathbb{F}_{\!q})$ and $\{0, 1\}^* \to \mathbb{G}_2$, which seem to be difficult to speed up even more. We also discuss how much performance gain they provide over hash functions that are actively applied in the industry.

This paper presents OnionPIR and stateful OnionPIR, two singleserver PIR schemes that significantly improve the response size and computation cost over state-of-the-art schemes. OnionPIR scheme utilizes recent advances in somewhat homomorphic encryption (SHE) and carefully composes two lattice-based SHE schemes and homomorphic operations to control the noise growth and response size. Stateful OnionPIR uses a technique based on the homomorphic evaluation of copy networks. OnionPIR achieves a response overhead of just 4.2x over the insecure baseline, in contrast to the 100x response overhead of state-of-the-art schemes. Our stateful OnionPIR scheme improves upon the recent stateful PIR framework of Patel et al. and reduces its response overhead by 22x by avoiding downloading the entire database in the offline stage. Compared to state-of-the-art stateless PIR schemes including OnionPIR, stateful OnionPIR reduces the computation cost by 7x.

The Centre for Hardware Security at TalTech invites applications for a postdoctoral researcher position. The Centre conducts research in the area of Hardware Security focusing on trustworthy integrated circuit (IC) design, electronic design automation (EDA) for secure systems, hardware trojans, reverse engineering, circuit obfuscation, and crypto hardware. The position that is currently open is for research on hardware implementation of post-quantum cryptography (PQC) algorithms. The Centre has two separate funded and ongoing efforts to demonstrate best-in-class architectures for PQC for which the candidate will be expected to contribute to: a preliminary case study has been taped out in September 2021 and the candidate is expected to lead a more mature implementation to be later taped out in 2022.

Requirements: We are looking for motivated candidates with a strong background in circuit design. Candidates must have completed a PhD program (or be about to complete). Previous expertise on Hardware Security is highly desirable but experience in other related areas (IC design, test, verification, etc.) can also be considered. The candidates are expected to have the following core skills:

Ability to describe digital circuitry (preferably in Verilog)

Familiarity with PQC algorithms

Ability to write C++/python scripts for automation of design process and validation

Familiarity w/ Cadence tools for IC design (Genus, Innovus, etc.)

Strong writing skills (English)

Other skills are considered a plus:

FPGA prototyping

Familiarity with EDA tools from other vendors (Calibre, ICC, DC, etc.)

In-depth understanding of conventional crypto algorithms and their hardware implementations

How to apply: Please submit your CV and a cover letter to Prof. Samuel Pagliarini by email (name.lastname@taltech.ee) using the subject ‘PostDoc in Hardware Security’.

Closing date for applications:

Contact: Prof. Samuel Pagliarini

More information: https://taltech.ee/en/centre-for-hardware-security

The University of Kassel has an opening of a professorship in IT-/cyber security. The position is full-time, tenured, available as soon as possible, and paid according to the pay grade W2 HBesO. The successful candidate will be expected to establish and lead a research group working on any aspect of information security (including cryptology), and preferably to integrate into the university's Research Centre for Information Technology Design. Knowledge of the German language is not a prerequisite but the successful candidate will be expected to be able to teach in German after a short while. For further details please consult the official announcement on the university's webpages.

Closing date for applications:

Contact: Prof. Martin Lange

More information: https://stellen.uni-kassel.de/jobposting/5ac159573541cad232848aa64b14896cd6f190d90?ref=homepage

We are looking for a candidate with proven scientific expertise in the field of Security & Privacy. The following areas are of particular interest:

• Formal Methods and Security
• Privacy Technologies
• Systems Security
• Usable Security & Privacy

The successful candidate will cover one of these fields or any other field in security & privacy that complements the existing strengths in the department.

The professorship will be part of the Institute of Applied Information Processing and Communications, which is an internationally visible research environment with more than 60 researchers in information security. The institute collaborates closely with research groups and industry partners around the globe. It is a central part of the recently established Cybersecurity Campus Graz, which unites basic research, education, technology transfer, and industry partners in cybersecurity all under one roof.

The new professor will build an internationally visible group, and will be an engaged teacher in the Computer Science programs at the Bachelor’s, Master’s, and PhD level. At Graz University of Technology, undergraduate courses are taught in German or English and graduate courses are taught in English.

The full description for this professorship can be found here: https://www.tugraz.at/fakultaeten/csbme/news/jobs-grants-calls/tenure-track-professor-in-security-and-privacy/

Closing date for applications:

Contact: For further questions, please contact Stefan Mangard - stefan.mangard@iaik.tugraz.at

The application should be filed online via https://survey.tugraz.at/index.php/264524 until 30.11.2021 referencing 7050/21/008.

More information: https://www.tugraz.at/fakultaeten/csbme/news/jobs-grants-calls/tenure-track-professor-in-security-and-privacy/

The Department of Computer Science at Durham University is looking for a postdoctoral researcher from 1 Jan 2022 to work on an EPSRC project on topics related to password-hashing algorithms and idealized models of computation for a period of two years. We would be interested in applicants holding (or nearing the completion of) a PhD in Cryptography (or related fields) who have strong interests in the foundational aspects of crypto, proof techniques, and definitional work. Publications at competitive venues and ability to work independently are a plus. Applicants with backgrounds in Algorithms and Complexity are also very welcome to apply.

Durham is one of the top (and oldest) universities in the UK, and the CS department hosts one of the strongest Theory groups in the UK across the ACiD and NESTiD groups. The annual salary for the position is ​​£42,149.

Closing date for applications:

Contact: Pooya Farshim. Please submit a CV containing publications and references.

More information: https://farshim.github.io/

Distributed deep learning frameworks, such as split learning, have recently been proposed to enable a group of participants to collaboratively train a deep neural network without sharing their raw data. Split learning in particular achieves this goal by dividing a neural network between a client and a server so that the client computes the initial set of layers, and the server computes the rest. However, this method introduces a unique attack vector for a malicious server attempting to steal the client's private data: the server can direct the client model towards learning a task of its choice. With a concrete example already proposed, such training-hijacking attacks present a significant risk for the data privacy of split learning clients.

In this paper, we propose SplitGuard, a method by which a split learning client can detect whether it is being targeted by a training-hijacking attack or not. We experimentally evaluate its effectiveness, and discuss in detail various points related to its use. We conclude that SplitGuard can effectively detect training-hijacking attacks while minimizing the amount of information recovered by the adversaries.

How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit models.

* In general $B_2$ circuits, assuming the existence of PRFs, PRFs can be constructed in $2n + o(n)$ size, simplifying and improving the $O(n)$ bound by Ishai et al. (STOC 2008). We show that such construction is almost optimal by giving an unconditional $2n-O(1)$ lower bound.

* In logarithmic depth circuits, assuming the existence of $NC^1$ PRFs, PRFs can be constructed in $2n + o(n)$ size and $(1+\epsilon) \log n$ depth simultaneously.

* In constant depth linear threshold circuits, assuming the existence of $TC^0$ PRFs, PRFs can be constructed with wire complexity $n^{1+O(1.61^{-d})}$. We also give an $n^{1+\Omega(c^{-d})}$ wire complexity lower bound for some constant $c$.

The upper bounds are proved with generalized Levin's trick and novel constructions of "almost" universal hash functions; the lower bound for general circuits is proved via a tricky but elementary wire-counting argument; and the lower bound for $TC^0$ circuits is proved by extracting a "black-box" property of $TC^0$ circuits from the "white-box" restriction lemma of Chen, Santhanam, and Srinivasan (Theory Comput. 2018). As a byproduct, we prove unconditional tight upper and lower bounds for "almost" universal hashing, which we believe to have independent interests.

Following Natural Proofs by Razborov and Rudich (J. Comput. Syst. Sci. 1997), our results make progress in realizing the difficulty to improve known circuit lower bounds which recently becomes significant due to the discovery of several "bootstrapping results". In $TC^0$, this reveals the limitation of the current restriction-based methods; in particular, it brings new insights in understanding the strange phenomenon of "sharp threshold results" such as the one presented by Chen and Tell (STOC 2019).

In this paper we derive a suit of lemmas which allows users to internally reflect EasyCrypt programs into distributions which correspond to their denotational semantics (probabilistic reflection). Based on this we develop techniques for reasoning about rewinding of adversaries in EasyCrypt. (A widely used technique in cryptology.) We use reflection and rewindability results to prove the security of a coin-toss protocol.

Proof of reserves protocols enable cryptocurrency exchanges to prove solvency, i.e. prove that they have enough reserves to meet their liabilities towards their customers. MProve (EuroS&PW, 2019) was the first proof of reserves protocol for Monero which provided some privacy to the exchanges’ addresses. As the key images and the addresses are inherently linked in the MProve proof, an observer could easily recognize the exchange-owned address when a transaction spending from it appears on the blockchain. This is detrimental for an exchange’s privacy and becomes a natural reason for exchanges to not adopt MProve. To this end, we propose MProve+, a Bulletproofs- based (S&P, 2018) NIZK protocol, which unlinks the key images and the addresses, thus alleviating the drawback of MProve. Furthermore, MProve+ presents a promising alternative to MProve due to an order of magnitude smaller proof sizes along with practical proof generation and verification times.

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, ${\rm K}^t$, is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures: * We show, perhaps surprisingly, that the $\rm KT$ complexity is bounded-error average-case hard if and only if there exist one-way functions in *constant parallel time* (i.e., ${\sf NC}^0$). This result crucially relies on the idea of *randomized encodings*. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that ${\sf NC}^0$-computable one-way functions exist if and only if logspace-computable one-way functions exist. * Inspired by the above result, we present randomized average-case reductions among the ${\sf NC}^1$-versions and logspace-versions of ${\rm K}^t$ complexity, and the $\rm KT$ complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the $\rm KT$ complexity and a variant of ${\rm K}^t$ complexity. * We prove tight connections between the hardness of ${\rm K}^t$ complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the *Perebor Hypotheses* for complexity measures such as ${\rm K}^t$ and $\rm KT$. We show that a Strong Perebor Hypothesis for ${\rm K}^t$ implies the existence of (weak) one-way functions of near-optimal hardness $2^{n-o(n)}$. To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem. * We show that a Weak Perebor Hypothesis for ${\rm MCSP}$ implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of ${\rm MCSP}$ over a natural distribution. * Finally, we study the average-case hardness of ${\rm MKtP}$. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.

The paper provides a complete description of the digital signature scheme based on the Stern identification protocol. We also present the proof of the existential unforgeability of the scheme under the chosen message attack (EUF-CMA) in the random oracle model (ROM) under assumptions of hardness of syndrome decoding and hash function collision finding problems. Finally, we discuss the choice of the signature parameters and introduce a parameter set providing 80-bit security.

Training deep neural networks requires large scale data, which often forces users to work in a distributed or outsourced setting, accompanied with privacy concerns. Split learning framework aims to address this concern by splitting up the model among the client and the server. The idea is that since the server does not have access to client's part of the model, the scheme supposedly provides privacy. We show that this is not true via two novel attacks. (1) We show that an honest-but-curious split learning server, equipped only with the knowledge of the client neural network architecture, can recover the input samples and also obtain a functionally similar model to the client model, without the client being able to detect the attack. (2) Furthermore, we show that if split learning is used naively to protect the training labels, the honest-but-curious server can infer the labels with perfect accuracy. We test our attacks using three benchmark datasets and investigate various properties of the overall system that affect the attacks' effectiveness. Our results show that plaintext split learning paradigm can pose serious security risks and provide no more than a false sense of security.

Chats have become an essential means of interpersonal interaction. Yet untraceable private communication remains an elusive goal, as most messengers hide content, but not communication patterns. The knowledge of communication patterns can by itself reveal too much, as happened e.g., in the context of the Arab Spring. The subliminal channel in cryptographic systems - as introduced by Simmons in his pioneering works - enables untraceable private communication in plain sight. In this context, blockchains are a natural object for subliminal communication: accessing them is innocuous, as they rely on distributed access for verification and extension. At the same time, blockchain transactions generate hundreds of thousands transactions per day that are individually signed and placed on the blockchain. This significantly increases the availability of publicly accessible cryptographic transactions where subliminal channels can be placed. In this paper we propose a public-key subliminal channel using ECDSA signatures on blockchains and prove that our construction is undetectable in the random oracle model under a common cryptographic assumption. While our approach is applicable to any blockchain platform relying on (variants of) ECDSA signatures, we present a proof of concept of our method for the popular Bitcoin protocol and show the simplicity and practicality of our approach.

We present an implementation of the hash-based post-quantum signature scheme SPHINCS+ that enables heavily memory-restricted devices to sign messages by streaming-out a signature during its computation and to verify messages by streaming-in a signature. We demonstrate our implementation in the context of Trusted Platform Modules (TPMs) by proposing a SPHINCS+ integration and a streaming extension for the TPM specification. We evaluate the overhead of our signature-streaming approach for a stand-alone SPHINCS+ implementation and for its integration in a proof-of-concept TPM with the proposed streaming extension running on an ARM Cortex-M4 platform. Our streaming interface greatly reduces the memory requirements without introducing a significant performance penalty. This is achieved not only by removing the need to store an entire signature but also by reducing the stack requirements of the key generation, sign, and verify operations. Therefore, our streaming interface enables small embedded devices that do not have sufficient memory to store an entire SPHINCS+ signature or that previously were only able to use a parameter set that results in smaller signatures to sign and verify messages using all SPHINCS+ variants. Since the streaming concept aggravates fault attacks on hash-based signature schemes, we briefly discuss countermeasures to attenuate such attacks in a signature-streaming scenario.

The BeleniosVS electronic voting scheme offers an attractive mix of verifiability and privacy properties. Moreover, using the ProVerif protocol-verification tool, BeleniosVS has automatic machine-aided analysis of (end-to-end) verifiability in 96 different threat models with the machine-aided analysis finding proofs in 22 cases and finding attacks in the remaining 74 cases. The high number of threat models covered by ProVerif delivers a much richer security analysis than the norm.

We revisit the BeleniosVS scheme and propose several refinements to the ProVerif security model and scheme which increase the number of threat models in which the scheme has verifiability from 22 to 28. Our new ProVerif security model also implies end-to-end verifiability but the requirements are easier to satisfy. Interestingly, in all six improvements, both the changes to the security model and one or more changes to the scheme are necessary to prove verifiability.

In this paper, we present a new secret trapdoor function for the design of multivariate schemes that we call ``Onyx'', suitable for encryption and signature. It has been inspired by the schemes presented in Ariadne Thread and Pepper: New mul-tivariate cryptographic schemes with public keys in degree 3. . From this idea, we present some efficient encryption and signature multivariate 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). Specific attacks due to the properties of the function and its differential are also addressed in this paper. The ``Onyx'' schemes have public key equations of degree 3. Despite this, the size of the public key may still be reasonable since we can use larger fields and smaller extension degrees. Onyx signatures can be as short as the ``birthday paradox'' allows, i.e. twice the security level, or even shorter thanks to the Feistel-Patarin construction, like many other signatures schemes based on multivariate equations.