International Association
for Cryptologic Research

The overlap-free splitting method, i.e., even-odd splitting and its generalization, can reduce the XOR delay of a Karatsuba multiplier. We use this method to derive Karatsuba formulae with one less XOR delay in each recursive iteration. These formulae need more multiplication operations, and are trade-offs between space and time.

We also show that ``finding common subexpressions'' performs better than ``the refined identity'' in 4-term formula: we reduce the number of XOR gates given by Cenk, Hasan and Negre in IEEE T. Computers in 2014.

We consider the computation of sparse, $(\varepsilon, \delta)$-differentially private (DP) histograms in the two-server model of secure multi-party computation (MPC), which has recently gained traction in the context of privacy-preserving measurements of aggregate user data. We introduce protocols that enable two semi-honest non-colluding servers to compute histograms over the data held by multiple users, while only learning a private view of the data. Our solution achieves the same asymptotic $\ell_\infty$-error of $O\left(\frac{\log(1/\delta)}{\varepsilon}\right)$ as in the central model of DP, but $\textit{without}$ relying on a trusted curator. The server communication and computation costs of our protocol are independent of the number of histogram buckets, and are linear in the number of users, while the client cost is independent of the number of users, $\varepsilon$, and $\delta$. Its linear dependence on the number of users lets our protocol scale well, which we confirm using microbenchmarks: for a billion users, $\varepsilon = 0.5$, and $\delta = 10^{-11}$, the per-user cost of our protocol is only $1.04$ ms of server computation and $275$ bytes of communication. In contrast, a baseline protocol using garbled circuits only allows up to $10^6$ users, where it requires 600 KB communication per user.

In this paper, we present the first side-channel attack on a higher-order masked implementation of an IND-CCA secure lattice-based key encapsulation mechanism (KEM). Our attack exploits a vulnerability in the procedure for the arithmetic to Boolean conversion which we discovered. On the example of Saber KEM, we demonstrate successful message and secret key recovery attacks on the second- and third-order masked implementations running on a different device than the profiling one. In our experiments, we use the latest publicly available higher-order masked implementation of Saber KEM in which all known vulnerabilities are patched. The presented approach is not specific to Saber and can be potentially applied to other lattice-based PKE and KEM algorithms, including CRYSTALS-Kyber which has been recently selected for standardization by NIST.

A secure $n$-bit tweakable block cipher (TBC) using $t$-bit tweaks can be modeled as a tweakable uniform random permutation, where each tweak defines an independent random $n$-bit permutation. When an input to this tweakable permutation is fixed, it can be viewed as a perfectly secure $t$-bit random function. On the other hand, when a tweak is fixed, it can be viewed as a perfectly secure $n$-bit random permutation, and it is well known that the sum of two random permutations is pseudorandom up to $2^n$ queries.

A natural question is whether one can construct a pseudorandom function (PRF) beyond the block and the tweak length bounds using a small number of calls to the underlying tweakable permutations. As a positive answer to this question, we propose two PRF constructions based on tweakable permutations, dubbed $\mathsf{XoTP1}_c$ and $\mathsf{XoTP2}_c$, respectively. Both constructions are parameterized by $c$, giving a $(t+n-c)$-to-$n$ bit PRF.

When $t<2n$, $\mathsf{XoTP1}_{\frac{t}{2}}$ becomes an $(n+\frac{t}{2})$-to-$n$ bit pseudorandom function, which is secure up to $2^{n+\frac{t}{2}}$ queries. $\mathsf{XoTP2}_{\frac{t}{3}}$ is even better, giving an $(n+\frac{2t}{3})$-to-$n$ bit pseudorandom function, which is secure up to $2^{n+\frac{2t}{3}}$ queries, when $t<3n$. These PRFs provide security beyond the block and the tweak length bounds, making two calls to the underlying tweakable permutations.

In order to prove the security of $\mathsf{XoTP1}$ and $\mathsf{XoTP2}$, we firstly extend Mirror theory to $q \gg 2^n$, where $q$ is the number of equations. From a practical point of view, our constructions can be used to construct TBC-based MAC finalization functions and CTR-type encryption modes with stronger provable security compared to existing schemes.

In this work, we present an almost-surely terminating asynchronous Byzantine agreement (ABA) protocol for $n$ parties. Our protocol requires ${\cal O}(n^2)$ expected time and is secure against a computationally-unbounded malicious (Byzantine) adversary, characterized by a non-threshold adversary structure ${\cal Z}$, which enumerates all possible subsets of potentially corrupt parties. Our protocol has optimal resilience where ${\cal Z}$ satisfies the ${\cal Q}^{(3)}$ condition; i.e. union of no three subsets from ${\cal Z}$ covers all the $n$ parties. To the best of our knowledge, this is the first almost-surely terminating ABA protocol with ${\cal Q}^{(3)}$ condition. Previously, almost-surely terminating ABA protocol is known with non-optimal resilience where ${\cal Z}$ satisfies the ${\cal Q}^{(4)}$ condition; i.e. union of no four subsets from ${\cal Z}$ covers all the $n$ parties. To design our protocol, we present a shunning asynchronous verifiable secret-sharing (SAVSS) scheme with ${\cal Q}^{(3)}$ condition, which is of independent interest.

Over the last years, the side-channel analysis of Post-Quantum Cryptography (PQC) candidates in the NIST standardization initiative has received increased attention. In particular, it has been shown that some post-quantum Key Encapsulation Mechanisms (KEMs) are vulnerable to Chosen-Ciphertext Side-Channel Attacks (CC-SCA). These powerful attacks target the re-encryption step in the Fujisaki-Okamoto (FO) transform, which is commonly used to achieve CCA security in such schemes. To sufficiently protect PQC KEMs on embedded devices against such a powerful CC-SCA, masking at increasingly higher order is required, which induces a considerable overhead. In this work, we propose to use a conceptually simple construction, the $\mathcal{E}t\mathcal{S}$ KEM, that alleviates the impact of CC-SCA. It uses the Encrypt-then-Sign ($\mathcal{E}t\mathcal{S}$) paradigm introduced by Zheng at ISW ’97 and further analyzed by An, Dodis and Rabin at EUROCRYPT ’02, and instantiates a postquantum authenticated KEM in the outsider-security model. While the construction is generic, we apply it to the CRYSTALS-Kyber KEM, relying on the CRYSTALS-Dilithium and Falcon signature schemes. We show that a CC-SCA-protected $\mathcal{E}t\mathcal{S}$ KEM version of CRYSTALS-Kyber requires less than 10% of the cycles required for the CC-SCA-protected FO-based KEM, at the cost of additional data/communication overhead. We additionally show that the cost of protecting the $\mathcal{E}t\mathcal{S}$ KEM against fault injection attacks, necessarily due to the added signature verification, remains negligible compared to the large cost of masking the FO transform at higher orders. Lastly, we discuss relevant embedded use cases for our $\mathcal{E}t\mathcal{S}$ KEM construction.

Fully Homomorphic Encryption (FHE) is a powerful cryptographic primitive that enables performing computations over encrypted data without having access to the secret key. We introduce OpenFHE, a new open-source FHE software library that incorporates selected design ideas from prior FHE projects, such as PALISADE, HElib, and HEAAN, and includes several new design concepts and ideas. The main new design features can be summarized as follows: (1) we assume from the very beginning that all implemented FHE schemes will support bootstrapping and scheme switching; (2) OpenFHE supports multiple hardware acceleration backends using a standard Hardware Abstraction Layer (HAL); (3) OpenFHE includes both user-friendly modes, where all maintenance operations, such as modulus switching, key switching, and bootstrapping, are automatically invoked by the library, and compiler-friendly modes, where an external compiler makes these decisions. This paper focuses on high-level description of OpenFHE design, and the reader is pointed to external OpenFHE references for a more detailed/technical description of the software library.

In recent work, Backendal, Haller, and Paterson identified several exploitable vulnerabilities in the cloud storage provider MEGA. They demonstrated an RSA key recovery attack in which a malicious server can recover the client’s RSA private key. Their attack uses binary search to recover the private RSA key after 1023 client logins, and optionally could be combined with lattice methods for factoring with partial knowledge to reduce the number of logins to 512 in theory, or 683 in the published proof of concept. In this note, we give an improved attack that requires only six client logins to recover the secret key. Our optimized attack combines several techniques, including a modification of the extended hidden number problem and the structure of RSA keys, to exploit additional information revealed by MEGA’s protocol vulnerabilities. MEGA has emphasized that users who had logged in more than 512 times could have been exposed; these improved attacks show that this bound was conservative, and that unpatched clients should be considered vulnerable under a much more realistic attack scenario.

Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of $n$ mutually distrusting parties with private inputs to securely compute any publicly-known function of their inputs, by keeping their respective inputs as private as possible. While several works in the past have addressed the problem of designing communication-efficient MPC protocols in the synchronous communication setting, not much attention has been paid to the design of efficient MPC protocols in the asynchronous communication setting. In this work, we focus on the design of efficient asynchronous MPC (AMPC) protocol with statistical security, tolerating a computationally unbounded adversary, capable of corrupting up to $t$ parties out of the $n$ parties. The seminal work of Ben-Or, Kelmer and Rabin (PODC 1994) and later Abraham, Dolev and Stern (PODC 2020) showed that the optimal resilience for statistically-secure AMPC is $t < n/3$. Unfortunately, the communication complexity of the protocol presented by Ben-Or et al is significantly high, where the communication complexity per multiplication is $\Omega(n^{13} \kappa^2 \log n)$ bits (where $\kappa$ is the statistical-security parameter). To the best of our knowledge, no work has addressed the problem of improving the communication complexity of the protocol of Ben-Or at al. In this work, our main contributions are the following. -- We present a new statistically-secure AMPC protocol with the optimal resilience $t < n/3$ and where the communication complexity is ${\mathcal O}(n^4 \kappa)$ bits per multiplication. Apart from improving upon the communication complexity of the protocol of Ben-Or et al, our protocol is relatively simpler and based on very few sub-protocols, unlike the protocol of Ben-Or et al which involves several layers of subprotocols. A central component of our AMPC protocol is a new and simple protocol for verifiable asynchronous complete secret-sharing (ACSS), which is of independent interest. -- As a side result, we give the security proof for our AMPC protocol in the standard universal composability (UC) framework of Canetti (FOCS 2001, JACM 2020), which is now the defacto standard for proving the security of cryptographic protocols. This is unlike the protocol of Ben-Or et al, which was missing the formal security proofs.

The Number Field Sieve and its numerous variants is the best algorithm to compute discrete logarithms in medium and large characteristic finite fields. When the extension degree $n$ is composite and the characteristic~$p$ is of medium size, the Tower variant (TNFS) is asymptotically the most efficient one. Our work deals with the last main step, namely the individual logarithm step, that computes a smooth decomposition of a given target~$T$ in the finite field thanks to two distinct phases: an initial splitting step, and a descent tree. In this article, we improve on the current state-of-the-art Guillevic's algorithm dedicated to the initial splitting step for composite~$n$. While still exploiting the proper subfields of the target finite field, we modify the lattice reduction subroutine that creates a lift in a number field of the target $T$. Our algorithm returns lifted elements with lower degrees and coefficients, resulting in lower norms in the number field. The lifted elements are not only much likely to be smooth because they have smaller norms, but it permits to set a smaller smoothness bound for the descent tree. Asymptotically, our algorithm is faster and works for a larger area of finite fields than Guillevic's algorithm, being now relevant even when the medium characteristic $p$ is such that $L_{p^n}(1/3) \leq p< L_{p^n}(1/2)$. In practice, we conduct experiments on $500$-bit and $700$-bit composite finite fields: Our method becomes more efficient as the largest non trivial divisor of $n$ grows, being thus particularly adapted to even extension degrees.

Xifrat1 is a family of cryptosystems based on abelian quasigroups and is the redesigned successor to the previous Xifrat0 cryptosystems. This paper discuss and attempt to argue its security, and provide this as foundation for future reasoning and/or refuting of its security.

Blind signatures are a fascinating primitive which allow a user to obtain signatures from a signer, while hiding the message. Tremendously useful, these have been studied extensively for decades. Yet, to the best of our knowledge, all concretely practical blind signatures rely on non-standard assumptions and/or achieve sub-optimal round complexity.

In this work, we provide an efficient, round-optimal (two-round) blind signature scheme from the hardness of the discrete log (DL) problem {\it and} the learning with errors problem in the (non black-box) random oracle model. Our construction enjoys {\it post-quantum} blindness and does not rely on idealizations such as the algebraic group model or generic group model. We provide a concrete instantiation of our construction. Specifically, our blind signature size and verification time is the same as base Schnorr signature scheme which is used for a building block, making the signature extremely short and the verification extremely fast.

To the best of our knowledge, ours is the first efficient candidate from standard assumptions which simultaneously achieves (very) short signatures, fast verification time, post-quantum blindness and round optimality.

Mass surveillance targets many users at the same time with the goal of learning as much as possible. Intuitively, breaking many users’ cryptography simultaneously should be at least as hard as that of only breaking a single one, but ideally security degradation is gradual: an adversary ought to work harder to break more. Bellare, Ristenpart and Tessaro (Crypto’12) introduced the notion of multi-instance security to capture the related concept for password hashing with salts. Auerbach, Giacon and Kiltz (Eurocrypt’20) motivated the study of public key encryption (PKE) in the multi-instance setting, yet their technical results are exclusively stated in terms of key encapsulation mechanisms (KEMs), leaving a considerable gap. We investigate the multi-instance security of public key encryption. Our contributions are twofold. Firstly, we define and compare possible security notions for multi-instance PKE, where we include PKE schemes whose correctness is not perfect. Secondly, we observe that, in general, a hybrid encryption scheme of a multi-instance secure KEM and an arbitrary data encapsulation mechanism (DEM) is unlikely to inherit the KEM’s multi-instance security. Yet, we show how with a suitable information-theoretic DEM, and a computationally secure key derivation function if need be, inheritance is possible. As far as we are aware, ours is the first inheritance result in the challenging multi-bit scenario.

The paper is dedicated to computer evaluation of parameters of members of family A(n, F_q) , n ≥ 2 of small world algebraic graphs of large girth with well defined projective limit. We present the applications of these computations to some optimisation problems for algebraic graphs over various field and Cryptography. We show the impact of high girth property of known family of graphs A(n, F_q) on properties of fast stream ciphers based on these graphs. Finally we modify these symmrtric encryption algorithms to make them resistant to linearization attacks.

We provide the first $\mathit{constant}$-$\mathit{round}$ construction of post-quantum non-malleable commitments under the minimal assumption that $\mathit{post}$-$\mathit{quantum}$ $\mathit{one}$-$\mathit{way}$ $\mathit{functions}$ exist. We achieve the standard notion of non-malleability with respect to commitments. Prior constructions required $\Omega(\log^*\lambda)$ rounds under the same assumption.

We achieve our results through a new technique for constant-round non-malleable commitments which is easier to use in the post-quantum setting. The technique also yields an almost elementary proof of security for constant-round non-malleable commitments in the classical setting, which may be of independent interest.

As an application, when combined with existing work, our results yield the first constant-round post-quantum secure multiparty computation under the $\mathit{polynomial}$ hardness of quantum fully-homomorphic encryption and quantum learning with errors.

We introduce the notion of a universal random oracle. Analogously to a classical random oracle it idealizes hash functions as random functions. However, as opposed to a classical random oracle which is created freshly and independently for each adversary, the universal random oracle should provide security of a cryptographic protocol against all adversaries simultaneously. This should even hold if the adversary now depends on the random function. This reflects better the idea that the strong hash functions like SHA-2 and SHA-3 are fixed before the adversary decides upon the attack strategy.

Besides formalizing the notion of the universal random oracle model we show that the model is asymptotically equivalent to Unruh's auxiliary-input random oracle model (Crypto 2007). In Unruh's model the adversary receives some inefficiently computed information about the random oracle as extra input. Noteworthy, while security in the universal random oracle model implies security in the auxiliary-input random oracle model tightly, the converse implication introduces an inevitable security loss. This implies that the universal random oracle model provides stronger guarantees in terms of concrete security. Validating the model we finally show, via a direct proof with concrete security, that a universal random oracle is one-way.

Secured Embedded Architecture Lab, CSE, at Indian Institute of Technology Kharagpur (iitkgp.ac.in) invites strong PostDoc applications from highly motivated candidates working in the field of Hardware Security. The candidate should be a PhD holder in VLSI or Hardware Security related areas from a reputed institute with an excellent academic background. The candidate will be working in the Secured Embedded Architecture Laboratory (http://cse.iitkgp.ac.in/resgrp/seal) with a group of PhD students and faculty focused in the area of secured system design. The research will be aimed at working on VLSI circuits and investigating both invasive and non-invasive techniques using state-of-the-art instruments, like SEM/FIBs and XRay Microscopes for developing a methodology for assurance of hardware designs. The candidate should have excellent publication track record in IACR conferences/workshops, as well as top journals (such as IEEE/ACM Transactions or IACR journals). The candidate will be expected to collaborate with and lead a team of excellent and highly motivated PhD candidates. The candidate is expected to work in conjunction with them and also disseminate the necessary knowledge among the group via suitable course material, tutorials and regular group talks. Good communication skills are hence desirable. The candidate will be provided with a competitive salary of INR 100,000 per month (~1200 USD), along with highly subsidized housing, subsidized food in cafeteria, free healthcare at IIT hospital, travel support for international conferences, comprehensive funding for papers at top conferences like CHES, DAC, etc. performance based top up grants, and other perks and amenities.

Lab websites:

1. http://cse.iitkgp.ac.in/resgrp/seal/

2. https://sites.google.com/view/hardware-and-cyber-physical-se/home?authuser=1

3. Youtube Channel: https://www.youtube.com/channel/UC-343QYYo1bhSGW1JLXDANA

Closing date for applications:

Contact: Prof Debdeep Mukhopadhyay Computer Science and Engineering Indian Institute of Technology Kharagpur West Bengal, 721302, India

More information: http://www.iitkgp.ac.in/temporary-jobs

The Max Planck Institute for Security and Privacy (MPI-SP) and the Chair for Information Security (InfSec) at the Ruhr-University Bochum (RUB) are looking for outstanding Ph.D. candidates as part of the CASA cluster of excellence. The successful candidates will conduct research at the intersection of formal verification and system security. Examples of research areas include (but are not limited to):

• Security of smart contracts
• Formal verification of smart contracts
• Security of blockchain consensus protocols

Eligible candidates must have:

• A Master’s degree or equivalent (or be close to completing one) in computer science, mathematics, or related fields.
• Outstanding candidates with a Bachelor’s degree will also be considered.
• Excellent communication/writing skills in English; knowledge of German is not required.
• An outstanding track record in classes related to IT security, cryptography, or formal methods/mathematics.

MPI-SP and the RUB are co-located in Bochum (Germany) and offer a vibrant atmosphere for research that spans many areas of IT security, computer science, and mathematics. The successful candidates will be a member of the research groups of Dr. Clara Schneidewind and/or Prof. Dr. Ghassan Karame.

The positions are fully funded (100%) and paid according to the E-13 pay category. To apply, please send an email to both Dr. Schneidewind and Prof. Dr. Karame with the following documents in a single PDF:

• CV, including transcripts.
• A brief cover letter describing your research interests.
• Contact details of 2-3 potential references

Applications received before August 15, 2022, will receive full consideration. Late applications will be considered until the position is filled. MPI-SP and InfSec stand for a collaborative, diverse, and inclusive workplace culture and promote equal opportunities. We strongly encourage applications from members of any underrepresented group in our research area. In particular, we invite and motivate women and individuals with disabilities to apply.

Closing date for applications:

Contact: Prof. Dr. Ghassan Karame (ghassan.karame@rub.de) and Dr. Clara Schneidewind (clara.schneidewind@mpi-sp.org)

More information: https://informatik.rub.de/infsec/

The Helsinki Institute for Information Technology (HIIT) in cooperation with the Finnish Center for Artificial Intelligence (FCAI) invite applications for Postdoctoral Researchers for a term of two years with the possibility of a one year extension. HIIT offers a HIIT Postdoctoral Fellow position for two years, with the possibility of a one year extension. For more senior candidates, HIIT offers a HIIT Research Fellow position of three years, with the possibility of a two year extension. The length of the contract as well as the starting and ending dates are negotiable.

All excellent researchers in any area of ICT can be considered, but priority is given to candidates who support one (or more) of the HIIT strategic focus areas:

• Artificial Intelligence
• Computational Health
• Cybersecurity
• Data Science
• Foundations of Computing

Closing date for applications:

Contact: Russell W. F. Lai (russell.lai at aalto dot fi)

More information: https://www.aalto.fi/en/open-positions/postdoctoral-researcher-and-research-fellow-positions-in-ict

There are three postdoctoral positions open in Cryptography and Information Security (CrIS) Lab at IISc. CrIS lab is associated to the Department of Computer Science and Automation (CSA). The research focus of the lab include secure multiparty computation, fault-tolerant distributed computing, and privacy preserving machine learning, but is not limited to them.

The applicant is expected to have completed a PhD degree (recently) in Cryptography or a related subject with strong publication records. A background in theoretical aspects of secure multiparty computation and/or experience in coding for practical aspects of secure computation is expected. Postdoctoral fellows are expected to actively interact with PhD students and contribute to the lab's projects. The tenure of the position is for one year and can be extended further.

You can apply through and find further details regarding opportunities at CrIS here - https://www.csa.iisc.ac.in/~cris/opportunities.html

Closing date for applications:

Contact: Professor Arpita Patra

More information: https://www.csa.iisc.ac.in/~cris/about.html