International Association
for Cryptologic Research

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.

The main approaches currently used to construct identity based encryption (IBE) schemes are based on bilinear mappings, quadratic residues and lattices. Among them, the most attractive approach is the one based on quadratic residues, due to the fact that the underlying security assumption is a well understood hard problem. The first such IBE scheme was constructed by Cocks and some of its deficiencies were addressed in subsequent works. In this paper, we will focus on two constructions that address the anonymity problem inherent in Cocks' scheme and we will tackle some of their incomplete theoretical claims. More precisely, we rigorously study Clear et. al and Zhao et. al's schemes and give accurate probabilities of successful decryption and identity detection in the non-anonymized version of the schemes. Also, in the case of Zhao \emph{et. al}'s scheme, we give a proper description of the underlying security assumptions.

Let \(q~=~2^n\), and let \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) be a generalized Galbraith--Lin--Scott (GLS) binary curve, with $\ell \ge 2$ and \((\ell, n) = 1\). We show that the GLS endomorphism on \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) induces an efficient endomorphism on the Jacobian \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\) of the genus-\(g\) hyperelliptic curve \(\mathcal{H}\) corresponding to the image of the GHS Weil-descent attack applied to \(\mathcal{E} / \mathbb{F}_{q^\ell}\), and that this endomorphism yields a factor-$n$ speedup when using standard index-calculus procedures for solving the Discrete Logarithm Problem (DLP) on \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\). Our analysis is backed up by the explicit computation of a discrete logarithm defined on a prime-order subgroup of a GLS elliptic curve over the field $\mathbb{F}_{2^{5\cdot 31}}$. A Magma implementation of our algorithm finds the aforementioned discrete logarithm in about $1,035$ CPU-days.

Luby and Rackoff used a Feistel cipher over bit strings to construct a pseudorandom permutation from pseudorandom functions in 1988 and in 2002, Patel, Ramzan, and Sundaram generalized the construction to arbitrary abelian groups. They showed that the 3-round Feistel cipher is not superpseudorandom over abelian groups but left as an open problem a proof for non-abelian groups. We give this proof.

Keywords: Feistel, non-abelian group, pseudorandom.

In this work we investigate how the choice of the key-expansion algorithm and its interaction with the round function affect the resistance of Simon-like ciphers against rotational-XOR (RX) cryptanalysis. We observe that among the key-expansion algorithms we consider, Simon is most resistant, while Simeck is much less so. Implications on lightweight ciphers design are discussed and open questions are proposed.

Deep learning techniques with neural networks are developing prominently in recent years and have been deployed in numerous applications. Despite their great success, in many scenarios it is important for the users to validate that the inferences are truly computed by legitimate neural networks with high accuracy, which is referred as the integrity of machine learning predictions. To address this issue, in this paper, we propose zkCNN, a zero knowledge proof scheme for convolutional neural networks (CNN). The scheme allows the owner of the CNN model to prove to others that the prediction of a data sample is indeed calculated by the model, without leaking any information about the model itself. Our scheme can also be generalized to prove the accuracy of a secret CNN model on public dataset.

Underlying zkCNN is a new sumcheck protocol for proving fast Fourier transforms and convolutions with a linear prover time, which is even faster than computing the result asymptotically. We also introduce several improvements and generalizations on the interactive proofs for CNN predictions, including verifying the convolutional layers, the activation function of ReLU and the max pooling. Our scheme is highly efficient in practice. It can scale to the large CNN of VGG16 with 15 million parameters and 16 layers. It only takes 163 seconds to generate the proof, which is 1000x faster than existing schemes. The proof size is 230 kilobytes, and the verifier time is only 172 milliseconds. Our scheme can further scale to prove the accuracy of the same CNN on 100 images.

Post-quantum cryptography (PQC) has a well-deserved NIST status. Our approach (R-Propping) replaces all numeric field arithmetic with GF(2^8) field operations. This method yields both classical and quantum secure protocols. The present work is dedicated to strengthening a chaotic Wolfram Class III cellular automata and discuss its usability as a cryptographical secure PRBG (pseudorandom bit generator), a building block for stream-ciphers, hashing, and other random numbers requiring protocols.

Classic Byzantine fault tolerant (BFT) protocols are designed for a specific timing model, most often one of the following: synchronous, asynchronous or partially synchronous. It is well known that the timing model and fault tolerance threshold present inherent trade-offs. Synchronous protocols tolerate up to $n/2$ Byzantine faults, while asynchronous or partially synchronous protocols tolerate only up to $n/3$ Byzantine faults. In this work, we generalize the fault thresholds of BFT and introduce a new problem called multi-threshold BFT. Multi-threshold BFT has four separate fault thresholds for safety and liveness under synchrony and asynchrony (or partial-synchrony), respectively. Decomposing the fault thresholds in this way allows us to design protocols that provide meaningful fault tolerance under both synchrony and asynchrony (or partial synchrony). We establish tight fault thresholds bounds for multi-threshold BFT and present protocols achieving them. As an example, we show a BFT state machine replication (SMR) protocol that tolerates up to $2n/3$ faults for safety under synchrony while tolerating up to $n/3$ faults for other scenarios (liveness under synchrony as well as safety and liveness under partial synchrony). This is strictly stronger than classic partially synchronous SMR protocols. We also present a general framework to transform known partially synchronous or asynchronous BFT SMR protocols to additionally enjoy the optimal $2n/3$ fault tolerance for safety under synchrony.

We introduce AOT, an anonymous communication system based on mix network architecture that uses oblivious transfer (OT) to deliver messages. Using OT to deliver messages helps AOT resist blending (n−1) attacks and helps AOT preserve receiver anonymity, even if a covert adversary controls all nodes in AOT. AOT comprises three levels of nodes, where nodes at each level perform a different function and can scale horizontally. The sender encrypts their payload and a tag, derived from a secret shared between the sender and receiver, with the public key of a Level-2 node and sends them to a Level-1 node. On a public bulletin board, Level-3 nodes publish tags associated with messages ready to be retrieved. Each receiver checks the bulletin board, identifies tags, and receives the associated messages using OT. A receiver can receive their messages even if the receiver is offline when messages are ready. Through what we call a "handshake" process, communicants can use the AOT protocol to establish shared secrets anonymously. Users play an active role in contributing to the unlinkability of messages: periodically, users initiate requests to AOT to receive dummy messages, such that an adversary cannot distinguish real and dummy requests.