International Association
for Cryptologic Research

So far, signature schemes based on the MPC-in-the-head approach (MPCitH) have either been designed by taking a proof system and selecting a suitable symmetric-key primitive (Picnic, CCS16), or starting with an existing primitive such as AES and trying to find the most suitable proof system (BBQ, SAC19 or Banquet, PKC21). In this work we do both: we improve certain symmetric-key primitives to better fit signature schemes, and we also propose a new signature scheme by co-designing a proof system and a new block cipher. Our concrete results are as follows.

First, we show how to provably remove the need to include the key schedule of block ciphers. This simplifies schemes like Picnic and it also leads to the fastest and smallest AES-based signatures. For example, we achieve signature sizes of around 10.8 to 14.2 KB for the 128-bit security level, on average 10% shorter than Banquet and 15% faster.

Second, we investigate a variant of AES with larger S-boxes we call LSAES, for which we can argue that it is very likely at least as strong as AES, further reducing the size of AES-based signatures to 9.9 KB.

Finally, we present a new signature scheme, Rainier, based on a new block cipher called Rain combined with a Banquet-like proof system. To the best of our knowledge, it is the first MPCitH-based signature scheme which can produce signatures that are less than 5 KB in size; it also outperforms previous Picnic and Banquet instances in all performance metrics.

An approximate homomorphic encryption scheme called CKKS (Cheon-Kim-Kim-Song) is considered one of the most promising fully homomorphic encryption (FHE) schemes since it enables computations on real and complex numbers in encrypted form. Several bootstrapping approaches were proposed for CKKS to refresh the modulus in a ciphertext. However all the existing bootstrapping approaches for CKKS rely on polynomial approximation of modulus reduction function and consequently, the quality of the message deteriorates due to polynomial approximation errors. We propose the first bootstrapping approach for the CKKS scheme without polynomial approximation of the modulus reduction function. Instead, our procedure adopts blind rotation technique from FHEW-type schemes and as a result, our approach introduces only an error that is comparable to a rescaling error. We also present several optimizations including compact representation of public keys required for bootstrapping and modified blind rotation technique for the case of sparse secret key. We demonstrate that our bootstrapping procedure can be generalized to the BGV and BFV schemes with minor modifications in the proposed algorithms.

Recently, a sequence of works have made strong advances in two-round (i.e., round-optimal) secure multi-party computation (MPC). In the honest-majority setting -- the focus of this work -- Ananth et al. [CRYPTO'18, EC'19], Applebaum et al. [TCC'18, EC'19] and Garg et al. [TCC'18] have established the feasibility of general two-round MPC in standard communication models involving broadcast (BC) and private point-to-point (P2P) channels.

In this work, we set out to understand what features of the communication model are necessary for these results, and more broadly the design of two-round MPC. Focusing our study on the plain model -- the most natural model for honest-majority MPC -- we obtain the following results:

1. Dishonest majority from Honest majority: In the two round setting, honest-majority MPC and dishonest-majority MPC are surprisingly close, and often equivalent. This follows from our results that the former implies 2-message oblivious transfer, in many settings. (i) We show that without private point-to-point (P2P) channels, i.e., when we use only broadcast (BC) channels, honest-majority MPC implies 2-message oblivious transfer. (ii) Furthermore, this implication holds even when we use both P2P and BC, provided that the MPC protocol is robust against ``fail-stop'' adversaries.

2. The curious case of Identifiable Abort: While security with guaranteed output delivery (and even fairness) against malicious adversaries is impossible in two rounds, nothing is known with regards to the ``next best'' security notion, namely, security with identifiable abort (IA). We show that IA is impossible to achieve with honest-majority even if we use both P2P and BC channels. However, surprisingly, this lower bound can be overcome by replacing P2P channels with a ``bare'' (i.e., untrusted) public-key infrastructure (PKI).

These results ``explain'' that the reliance on P2P channels (together with BC) in the recent two-round protocols was in fact necessary, and that these protocols couldn't have achieved a stronger security guarantee, namely, IA. Overall, our results (put together with prior works) fully determine the best-achievable security for honest-majority MPC in different communication models in two rounds. As a consequence, they yield the following hierarchy of communication models:

BC < PTP < BC+PTP < BC+PKI

This shows that contrary to common perception, BC channel is the weakest communication model, and that a bare PKI setup is strictly stronger than P2P channels.

Secure hash functions are widely used cryptographic algorithms to secure diverse attacks. A one-way secure hash function is used in the various cryptographic area, for instance, password protection. However, most of the hash functions provide security based on static parameters and publicly known operations. Therefore, it becomes easier to attack by the attackers because all parameters and operations are predefined. The publicly known parameters and predefined operations make the oracle regenerate the key even though it is a one-way secure hash function. Moreover, the key (sensitive data) is mixed with the predefined constant where an oracle may find a way to discover the key. To address the above issues of the secure hash functions, we propose a novel and one-way secure hash algorithm, OSHA for short, to protect sensitive data against attackers. OSHA depends on a pseudo-random number generator to generate a private key. Moreover, OSHA mixes multiple private keys to generate a hash value. Furthermore, OSHA uses dynamic parameters, which is difficult for adversaries to guess. Unlike conventional secure hash algorithms, OSHA does not depend on fixed constants. It replaces the fixed constant with the private keys. Also, the key is not mixed with the private keys; hence, there is no way to recover and reverse the process for the adversaries.

We put forth a template for constructing statistical ZAPs for NP. Our template compiles NIZKs for NP in the hidden bit model (which exist unconditionally) into statistical ZAPs using a new notion of interactive hidden-bit generator (IHBG), which adapts the notion of hidden-bit generator to the plain model by building upon the recent notion of statistically-hiding extractable commitments. We provide a construction of IHBG from the explicit hardness of the decision Diffie-Hellman assumption (where explicit refers to requiring an explicit upper bound on the advantage of any polynomial-time adversary against the assumption) and the existence of statistical ZAPs for a specific simple language, building upon the recent construction of dual-mode hidden-bit generator from (Libert et al., EUROCRYPT 2020). We provide two instantiations of the underlying simple ZAP: 1. Using the recent statistical ZAP for the Diffie-Hellman language of (Couteau and Hartmann, CRYPTO 2020), we obtain statistical ZAPs for NP assuming (the explicit hardness of) DDH in $G_1$ and kernel-DH in $G_2$ (a search assumption which is weaker than DDH), where $(G_1,G_2)$ are groups equipped with an asymmetric pairing. This improves over the recent work of (Lombardi et al., EUROCRYPT 2020) which achieved a relaxed variant of statistical ZAP for NP, under a stronger assumption. 2. Using the recent work of (Couteau et al., EUROCRYPT 2020), we obtain statistical ZAPs for NP assuming the explicit hardness of DDH, together with the assumption that no efficient adversary can break the key-dependent message one-wayness of ElGamal with respect to efficient functions over groups of size $2^\secpar$ with probability better than $\poly(\secpar)/2^{(c + o(1)) \cdot \secpar}$, denoted $2^{-c\secpar}$-\OWKDM, for a constant c = 1/2, in pairing-free groups. Note that the latter is a search discrete-log-style falsifiable assumption, incomparable to DDH (in particular, it is not known to imply public-key encryption).

Information-theoretical privacy relies on randomness. Representatively, Differential Privacy (DP) has emerged as the gold standard to quantify the individual privacy preservation provided by given randomness. However, almost all randomness in existing differentially private optimization and learning algorithms is restricted to noise perturbation. In this paper, we set out to provide a privacy analysis framework to understand the privacy guarantee produced by other randomness commonly used in optimization and learning algorithms (e.g., parameter randomness).

We take mixup: a random linear aggregation of inputs, as a concrete example. Our contributions are twofold. First, we develop a rigorous analysis on the privacy amplification provided by mixup either on samples or updates, where we find the hybrid structure of mixup and the Laplace Mechanism produces a new type of DP guarantee lying between Pure DP and Approximate DP. Such an average-case privacy amplification can produce tighter composition bounds. Second, both empirically and theoretically, we show that proper mixup comes almost free of utility compromise.

Despite a long history of research and wide-spread applications to censorship resistant systems, practical steganographic systems capable of embedding messages into realistic communication distributions, like text, do not exist. We identify two primary impediments to deploying universal steganography: (1) prior work leaves the difficult problem of finding samplers for non-trivial distributions unaddressed, and (2) prior constructions have impractical minimum entropy requirements. We investigate using generative models as steganographic samplers, as they represent the best known technique for approximating human communication. Additionally, we study methods to overcome the entropy requirement, including evaluating existing techniques and designing a new steganographic protocol, called Meteor. The resulting protocols are provably indistinguishable from honest model output and represent an important step towards practical steganographic communication for mundane communication channels. We implement Meteor and evaluate it on multiple computation environments with multiple generative models.

Statistical Ineffective Fault Attacks (SIFA) have been recently proposed as very powerful key-recovery strategies on symmetric cryptographic primitives' implementations. Specically, they have been shown to bypass many common countermeasures against faults such as redundancy or infection, and to remain applicable even when side-channel countermeasures are deployed. In this work, we investigate combined side-channel and fault attacks and show that a profiled, SIFA-like attack can be applied despite not having any direct ciphertext knowledge. The proposed attack exploits the ciphertext's side-channel and fault characteristics to mount successful key recoveries, even in the presence of masking and duplication countermeasures, at the cost of both side-channel and fault profiling. We analyze the attack using simulations, discuss its requirements, strengths and limitations, and compare different approaches to distinguish the correct key. Finally, we demonstrate its applicability on an ARM Cortex-M4 device, utilizing a combination of laser-based fault injection and microprobe-based EM side-channel analysis.

We present fundamental (in-)feasibility results for the strongest security notion for Secure Multi-Party Computation (MPC) that is achievable when a majority of parties is malicious, i.e. security with Identifiable Abort. As general Universally Composable (UC) MPC requires a setup, typically in the form of a Common Reference String or Common-Randomness, we investigate whether the setup must provide randomness to all parties.

Given broadcast, we give tight bounds for the necessary and sufficient setup cardinality, i.e. number of participating parties, for UC-MPC protocols with Identifiable Abort. Concretely, we improve previous upper bounds by constructing Secure Function Evaluation for \(n\) parties (\(h\) of which are honest) from setups of cardinality \(\beta := \min(n,\lfloor n/h\rfloor+\lfloor(n-1)/h\rfloor-1)\) and broadcast. Conversely, we present the first general lower bound on the minimal setup cardinality for Identifiable Abort by proving that setups of cardinality \(\beta-1\) plus broadcast are insufficient even for a commitment among \(n\) parties. Somewhat surprisingly, we show that Oblivious Transfer plus broadcast is sufficient for \(n = 2h \geq 2\) which is consistent with the fact that in two-party MPC Identifiable Abort comes for free. We present the results in the Universal Composibility (UC) framework and assume the setup functionalities to be secure with Identifiable Abort.

Our constructions yield an efficient (poly-time) protocol for any \(n \in \mathrm{poly}(\lambda)\) where \(\lambda\) is the security parameter if at least a constant fraction \(h \in \Theta(n)\) of parties is honest. However for \(h \in \mathrm{o}(n)\) our results suggest that for efficient protocols the overall number of parties \(n\) is limited quite severely by \(\binom{n}{\beta} \in \mathrm{poly}(\lambda)\).

Secure deduplication allows removing duplicate content at third-party storage services while preserving the privacy of users’ data. However, current solutions are built with strict designs that cannot be adapted to storage service and applications with different security and performance requirements.

We present S2Dedup, a trusted hardware-based privacy-preserving deduplication system designed to support multiple security schemes that enable different levels of performance, security guarantees and space savings. An in-depth evaluation shows these trade-offs for the distinct Intel SGX-based secure schemes supported by our prototype.

Moreover, we propose a novel Epoch and Exact Frequency scheme that prevents frequency analysis leakage attacks present in current deterministic approaches for secure deduplication while maintaining similar performance and space savings to state-of-the-art approaches.

Event date: 18 November to 19 November 2021
Submission deadline: 15 August 2021
Notification: 30 September 2021

Mathematical Center in Akademgorodok announces a postdoctoral fellowship position available in cryptography and algebraic coding theory. The application deadline is June 15, 2021. Fellowship starts January 1, 2022 (or later upon mutual agreement). More details on english.nsu.ru/mca/jobs

Our research area:

Discrete mathematics;

Cryptographic boolean functions (particularly, bent functions and APN-functions);

Block ciphers and S-boxes, cryptanalysis of symmetric ciphers;

Lightweight cryptography and IoT;

Blockchain technologies and their applications;

Quantum and post quantum cryptography, etc.

More details about our group can be found on crypto.nsu.ru

Fellowship Applicant Profile

PhD within the last five years in Mathematics, Computers Science, or related field;

Maximum Age: 36;

Research focus in algebraic coding theory and cryptography;

Language proficiency in English;

Scientific publication experience;

A willingness to teach undergraduate and graduate courses and cooperate in joint scientific projects.

All applications must include the following:

A brief cover letter;

A current curriculum vitae;

Research proposal;

Contacts of two referees;

Abstract of the research proposal.

Submit your materials at english.nsu.ru/mca/jobs

Closing date for applications:

Contact: Please direct inquiries to english.nsu.ru/mca/jobs

More information: https://drive.google.com/file/d/1qKwGrjcekwejLngFwVDCeBHVLhXpoCjo/view?usp=sharing

The search for new attack techniques is a very active field: the use of X-ray illumination has been recently proved feasible to alter the content of memory cells. In this context, the French national project MITIX (Noninvasive modification of integrated circuits by X-Rays) aims at proving that X-Rays can effectively constitute a serious threat for secure implementations, even when more affordable equipment is used. Within the project, several experimental campaigns will be the basis for modelling the interaction between RX beam and the transistors, and hence propose design guidelines and/or solutions in order to protect against this novel attack technique.

The candidate is expected to analyze the sensitivity of MITIX circuits under X-ray beams thanks to simulation models and compare them with experimental results. The goal will be to reproduce the experimental conditions, possibly extending the analyses on the circuit, and extract sensitivity maps extended to a larger area of the topology.
The candidate will then be able to use the developed models and flow in order to evaluate hardening techniques or fault attack countermeasures. This subtask will consist in using the multi-physics and multi-level methodology to study and optimize the layout/routing of the cells, and extract high-level models of the injected faults. This will be essential in order to evaluate techniques from the state of the art, and propose novel solutions against fault attacks.

Closing date for applications:

Contact: Paolo Maistri (paolo.maistri at univ-grenoble-alpes.fr)
Guillaume Hubert (guillaume.hubert at onera.fr)
Alain Zergainoh (Alain.Zergainoh at univ-grenoble-alpes.fr)

More information: https://www.linkedin.com/posts/tima-laboratory_phd-thesis-proposition-3-years-activity-6802886839834288128-iMbC

The Center for Cyber Security at New York University Abu Dhabi (https://nyuad.nyu.edu/en/research/faculty-labs-and-projects/nyuad-ccs.html) is inviting applications for fully-funded research assistant, research associate, or postdoctoral associate positions within the Modern Microprocessors Architecture Lab (MoMA Lab, https://nyuad.nyu.edu/momalab). Positions are available for researchers with interests in cybersecurity. MoMA Lab focuses on systems security, with research interests on privacy-preserving computation, hardware acceleration of cryptographic primitives, industrial control systems security, as well as machine learning security. The lab’s latest work can be found at Twitter @realmomalab and Google Scholar through the lab’s website. To be considered, all applicants need to submit 1) a CV in PDF format, and 2) a research statement (up to 1 page) expressing their specific research interests. Applications will be considered immediately and on a rolling basis. The starting date is flexible. The position is intended to be initially for one year and can be extended given satisfactory performance. Different arrangements may be considered under special circumstances. A research assistant position can also lead to a PhD position with the NYU Tandon School of Engineering. Salary is dependent upon qualifications. NYU Abu Dhabi offers very competitive terms of employment including allowances for housing, transportation and home visits, in addition to health insurance and an attractive retirement plan. The UAE does not levy income tax.

Closing date for applications:

Contact: ccsad@nyu.edu

More information: https://apply.interfolio.com/80439

The Department of Computer Science and Engineering at IIT Jodhpur invites applications for faculty positions at all levels. Candidates should have a PhD degree in CSE, or a related field. The candidates are expected to have excellent research track record and commitment towards teaching. Although we are looking for strong candidates from all areas of CSE, we emphasize some areas relevant to IACR research community: Algorithms, Quantum Computation, Information Security (including hardware security), Cryptography and Cryptanalysis. About IIT Jodhpur: IITJ has a sprawling campus of over 850+ acres with 2600 students and 220+ faculty members. The department of CSE coordinates the BTech, MTech and MTech-PhD programs in CSE and AI, along with PhD in CSE. More details about the department can be found at https://cse.iitj.ac.in/. The institute also houses the Technology and Innovation Hub on CV, AR and VR and recently launched AIDE school (http://aide.iitj.ac.in/). We offer salary and benefits as per the norms of the central government. Benefits include relocation expenses, maternity/paternity leaves, a generous initiation grant, PhD student support, on campus housing (if available), access to on-campus medical facilities, access to on-campus sports facilities etc. In case of any clarification, candidates may reach out to head-cse@iitj.ac.in. Interested candidates are encouraged to apply via https://oa.iitj.ac.in/OA_REC_Faculty/.

Closing date for applications:

Contact: head-cse@iitj.ac.in

More information: https://oa.iitj.ac.in/OA_REC_Faculty/

Protocols that make use of oblivious transfer (OT) rarely require just one instance. Usually a batch of OTs is required --- notably, when generating base OTs for OT extension. There is a natural way to optimize 2-round OT protocols when generating a batch, by reusing certain protocol messages across all instances. In this work we show that this batch optimization is error-prone. We catalog many implementations and papers that have an incorrect treatment of this batch optimization, some of them leading to catastrophic leakage in OT extension protocols.

We provide a full treatment of how to properly optimize recent 2-round OT protocols for the batch setting. Along the way we show several performance improvements to the OT protocol of McQuoid, Rosulek, and Roy (ACM CCS 2020). In particular, we show an extremely simple OT construction that may be of pedagogical interest.

In this work, we prove that Multiplexer PUF~(MPUF) and $S_N$-PUF are learnable in the PAC model. First, we show that both the designs can be represented as a function of Linear Threshold Functions. We show that the noise sensitivity of $(n,k)$-MPUF and $S_N$-PUF can be bounded by $O(2^{k} \sqrt{\epsilon})$ and $O(N\sqrt{\epsilon})$ respectively. Finally, we show that as a result of bounded noise sensitivity, both the designs can be accurately approximated using low degree algorithm. Also, the number of labelled examples~(challenge-response pairs) required by the algorithm is polynomial in the input length and PAC model parameters.

We provide a new technique for secret sharing and reconstruction for Boolean circuits, applicable in ABE systems.

We show that our construction holds for Key-policy ABE and can be adapted also to Ciphertext-policy ABE. This is the most efficient solution for Attribute Based Encryption for circuits access structures using bilinear maps. Our KP-ABE system has decryption key of linear size in the number of attributes, and public parameters linear in the circuit size (Two public values for each FO-gate). We prove that our scheme is secure under the decisional bilinear Diffie-Hellman Assumption in the Selective Set Model.

In CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing PRF based on public permutations. They have proposed two beyond the birthday bound secure $n$-bit to $n$-bit PRF constructions, i.e., \textsf{SoEM22} and \textsf{SoKAC21}, which are built on public permutations, where $n$ is the size of the permutation. However, both of their constructions require two independent instances of public permutations. In FSE 2020, Chakraborti et al. have proposed a single public permutation based $n$-bit to $n$-bit beyond the birthday bound secure PRF, which they refer to as \textsf{PDMMAC}. Although the construction is minimal in the number of permutations, it requires the inverse call of its underlying permutation in their design. Coming up with a beyond the birthday bound secure public permutation based $n$-bit to $n$-bit PRF with a single permutation and two forward calls was left as an open problem in their paper. In this work, we propose $\textsf{pEDM}$, a single permutation based $n$-bit to $n$-bit PRF with two calls that do not require invertibility of the permutation. We have shown that our construction is secured against all adaptive information-theoretic distinguishers that make roughly up to $2^{2n/3}$ construction and primitive queries. Moreover, we have also shown a matching attack with similar query complexity that establishes the tightness of our security bound.

Let $\mathbb{F}_{\!q}$ be a finite field and $E\!: y^2 = x^3 + ax + b$ be an elliptic $\mathbb{F}_{\!q^2}$-curve of $j(E) \not\in \mathbb{F}_{\!q}$. This article provides a new constant-time hash function $\mathcal{H}\!: \{0,1\}^* \to E(\mathbb{F}_{\!q^2})$ indifferentiable from a random oracle. Furthermore, $\mathcal{H}$ can be computed with the cost of $3$ exponentiations in $\mathbb{F}_{\!q}$. In comparison, the actively used (indifferentiable constant-time) simplified SWU hash function to $E(\mathbb{F}_{\!q^2})$ computes $2$ exponentiations in $\mathbb{F}_{\!q^2}$, i.e., it costs $4$ ones in $\mathbb{F}_{\!q}$. In pairing-based cryptography one often uses the hashing to elliptic $\mathbb{F}_{\!q^2}$-curves $E_b\!: y^2 = x^3 + b$ (of $j$-invariant $0$) having an $\mathbb{F}_{\!q^2}$-isogeny $\tau\!: E \to E_b$ of small degree. Therefore the composition $\tau \circ \mathcal{H}\!: \{0,1\}^* \to \tau\big( E(\mathbb{F}_{\!q^2}) \big)$ is also an indifferentiable constant-time hash function.