International Association
for Cryptologic Research

We generalize Zhandry's compressed oracle technique to invertible random permutations. (That is, to a quantum random oracle where the adversary has access to a random permutation and its inverse.) This enables security proofs with lazy sampling, i.e., where oracle outputs are chosen only when needed.

As an application of our technique, we show the collision-resistance of the sponge construction based on invertible permutations. In particular, this shows the collision-resistance of SHA3 (in the random oracle model).

Every user can be identified online by a unique string used for email or nickname on some of the many platforms out there. IBE systems propose a simple cryptosystem in which the public key system can be omitted by using the unique string as public identification. In this paper we present a minimal email application that uses Clifford Cocks’ proposed IBE scheme. We analyze the impact of using it inside our application and how it can be improved to better fit the need of nowadays applications.

Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS '18), we present threshold ECDSA protocols, for any number of signatories and any threshold, that improve as follows over the state of the art:

* Only the last round of our protocols requires knowledge of the message, and the other rounds can take place in a preprocessing stage, lending to a non-interactive threshold ECDSA protocol.

* Our protocols withstand adaptive corruption of signatories. Furthermore, they include a periodic refresh mechanism and offer full proactive security.

* Our protocols realize an ideal threshold signature functionality within the UC framework, in the global random oracle model, assuming Strong RSA, DDH, semantic security of the Paillier encryption, and a somewhat enhanced variant of existential unforgeability of ECDSA.

* Both protocols achieve accountability by identifying corrupted signatories in case of failure to generate a valid signature.

The protocols provide a tradeoff between the number of rounds to generate a signature and the computational and communication overhead for the identification of corrupted signatories. Namely:

* For one protocol, signature generation takes only 4 rounds (down from the current state of the art of 8 rounds), but the identification process requires computation and communication that is quadratic in the number of parties.

* For the other protocol, the identification process requires computation and communication that is only linear in the number of parties, but signature generation takes 7 rounds.

These properties (low latency, compatibility with cold-wallet architectures, proactive security, identifiable abort and composable security) make the two protocols ideal for threshold wallets for ECDSA-based cryptocurrencies.

The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto'17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. The security games used to model these protocols involve an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a certain class of black-box reductions, which we term ``oblivious''. (We do however show one lower bound on proxy re-encryption that applies to general fully black-box reductions.) The fact that our lower bounds crucially rely on ``obliviousness'' hints to the possibility that the existing upper bounds can be improved by using more sophisticated reductions. As the main technical contribution, we introduce a two-player multi-stage game called the Builder-Pebbler Game and then analyze strategies for this game to establish bounds on success probability of its players. Finally, using oracle separation techniques, we translate these bounds into cryptographic lower bounds.

In this paper, we contribute a comprehensive resource analysis for widely used cryptographic primitives across different off-the-shelf IoT platforms, and quantify the performance impact of crypto-hardware. This work builds on the newly designed crypto-subsystem of the IoT operating system RIOT, which provides seamless crypto support across software and hardware components. Our evaluations show that (i) hardware-based crypto outperforms software by considerably over 100 %, which is crucial for nodal lifetime. Despite, the memory consumption typically increases moderately. (ii) Hardware diversity, driver design, and software implementations heavily impact resource efficiency. (iii) External crypto-chips operate slowly on symmetric crypto-operations, but provide secure write-only memory for private credentials, which is unavailable on many platforms.

Correlation intractability is an important cryptographic notion that is used for establishing soundness of Fiat-Shamir over public-coin protocols. In this work, we show that symmetric-key cryptography is neither sufficient nor essential for obtaining correlation intractability. Specifically, we prove a bidirectional fully black-box separation between one-way functions (OWFs) and correlation-intractable hash (CIH). In the first direction, we show that CIH for relations as simple as degree-3 polynomials cannot be based solely on OWFs. In the other direction, we show that there exists no fully black-box construction of OWF from CIH for all sparse relations. Consequently, we infer that computationally sound Fiat-Shamir over any specific constant-round proof system does not necessarily require one-way functions.

In this paper, we present a new concept named the basic function. By the study of the basic function, we find the $O(n)$-time algorithm to calculate the probability or correlation for some property of Modulo $2^n$, including the difference-linear connective correlation coefficients, the linear approximation correlation coefficients, the differential probability, difference-boomerange connective probability, boomerange connective probability, boomerange-difference connective probability, etc.

In this tech report, we introduce a novel countermeasure against physical attacks: Inertial hardware security modules (iHSMs). Conventional systems have in common that they try to detect attacks by crafting sensors responding to increasingly minute manipulations of the monitored security boundary or volume. Our approach is novel in that we reduce the sensitivity requirement of security meshes and other sensors and increase the complexity of any manipulations by rotating the security mesh or sensor at high speed—thereby presenting a moving target to an attacker. Attempts to stop the rotation are easily monitored with commercial MEMS accelerometers and gyroscopes. Our approach leads to a HSM that can easily be built from off-the-shelf parts by any university electronics lab, yet offers a level of security that is comparable to commercial HSMs.

Programmers are used to the rounding and error properties of IEEE double precision arithmetic, however in secure computing paradigms, such as provided by Multi-Party Computation (MPC), usually a different form of approximation is provided for real number arithmetic. We compare the two standard variants using for LSSS-based MPC, with an implementation of IEEE compliant double precision using binary circuit-based MPC. We compare the relative performance, and conclude that the addition cost of IEEE compliance maybe too great for some applications. Thus in the secure domain standards bodies may wish to examine a different form of real number approximations.

Efficient lattice-based cryptography usually relies on the intractability of problems on lattices with algebraic structure such as ideal-lattices or module-lattices. It is an important open question to evaluate the hardness of such lattice problems, and their relation to the hardness of problems on unstructured lattices.

It is a known fact that an unstructured lattice can be cast as an ideal-lattice in some order of a number field (and thus, in a rather trivial sense, that ideals in orders are as general as unstructured lattices). However, it is not known whether this connection can be used to imply useful hardness results for structured lattices, or alternatively new algorithmic techniques for unstructured lattices.

In this work we show that the Order-LWE problem (a generalization of the well known Ring-LWE problem) on certain orders is at least as hard as the (unstructured) LWE problem. So in general one should not hope to solve Order-LWE more efficiently than LWE. However, we only show that this connection holds in orders that are very ``skewed'' and in particular irrelevant for cryptographic applications. We then discuss the ability to embed unstructured lattices in ``friendlier'' orders, which requires devising an algorithm for computing the conductor of relevant orders. One of our technical tools is an improved hardness result for Order-LWE, closing a gap left in prior work.

This paper describes a non-interactive process allowing a prover to convince a verifier that a modulus $n$ is the product of two primes ($p,q$) of about the same size. A further heuristic argument conjectures that $p-1$ and $q-1$ have sufficiently large prime factors for cryptographic applications.

The new protocol relies upon elementary number-theoretic properties and can be implemented efficiently using very few operations. This contrasts with state-of-the-art zero-knowledge protocols for RSA modulus proper generation assessment.

The heuristic argument at the end of our construction calls for further cryptanalysis by the community and is, as such, an interesting research question in its own right.

Our purpose is to compare how much the F5 algorithm can gain in efficiency compared to the F4 algorithm. This can be achieve as the F5 algorithm uses the concept of signatures to foresee potential useless computation which the F4 algorithm might make represented by zero rows in the reduction of a large matrix. We experimentally show that this is a modest increase in efficiency for the parameters we tested.

Often times, the ability to distinguish between random data and a public key can leads to an attack against the cryptosystem itself. In this paper, we will show experimentally a very efficient distinguisher based on the distribution of ranks of the symmetric matrices associated with the central map in the multivariate cryptosystem HFE when the degree D of the central map is very small.

This draft report provides preliminary area and clock speed results for 53 NIST Lightweight Cryptography Round 2 candidates on an ASIC cell library.

A gadget decomposition algorithm is commonly used in many advanced lattice cryptography applications which support homomorphic operation over ciphertexts to control the noise growth. For a special structure of a gadget, the algorithm is digit decomposition. If such algorithm samples from a subgaussian distribution, that is, the output is randomized, it gives more benefits on output quality. One of important advantages is Pythagorean additivity which makes resulting noise contained in a ciphertext grow much less than naive digit decomposition. Therefore, the error analysis becomes cleaner and tighter than the use of other measures like $\ell_2$ and $\ell_\infty$. Even though such advantage can also be achieved by the use of discrete Gaussian sampling, it is not preferable for practical performance due to large factor in resulting noise and the complex computation of exponential function, whereas more relaxed probability condition is required for subgaussian distribution. Nevertheless, subgaussian sampling has barely received an attention so far, thus no practical algorithms was implemented before an efficient algorithm is presented by Genis et al., recently.

In this paper, we present a practically efficient gadget decomposition algorithm where output follows a subgaussian distribution. We parallelize the existing practical subgaussian gadget decomposition algorithm, using bounded uniform distribution. Our algorithm is divided into two independent subalgorithms and only one algorithm depends on input. Therefore, the other algorithm can be considered as pre-computation. As an experimental result, our algorithm performs over 50\% better than the existing algorithm.

The voting process is fundamental to any democratic system – be it a country or a company's boardroom. Nearly forty years ago, e-voting was theoretically perceived as a more efficient replacement of the widely existing paper-based traditional voting system. Several research works have been carried out to ensure more security and efficiency in different settings for e-voting schemes. One of the fundamental building blocks of e-voting systems is the public Bulletin Board through which several security properties are achieved. After introducing Blockchain technology, the bulletin board has found a new meaningful and concrete way of distributed way of implementation. Before Blockchain technology, either such a system was theoretically assumed or perceived as a public broadcast channel with memory. In this survey, we present a concise survey of bulletin boards' evolution with a typical application to the e-voting systems. We note that bulletin boards have other applications in other joint computation areas. Still, we are interested in evolving e-voting systems based on bulletin board and how several desired security properties are realized through bulletin boards.

In the recent years, many research lines on Functional Encryption (FE) have been suggested and studied regarding the functionality, security, or efficiency. These studies include quadratic FE, multi-client FE, function-hiding FE, dynamic FE and much more. Nevertheless, an open problem on a basic functionality, the single-input inner-product (IPFE), remains: can IPFE be instantiated based on the Ring Learning With Errors (RLWE) assumption?

The RLWE assumption provides quantum-resistance security while in comparison with LWE assumption gives significant performance and compactness gains. In this paper we present the first IPFE scheme whose security is guaranteed relying on the RLWE assumption. The security proof requires developing two new results on ideal lattices. The first result is a variant of Ring-LWE, that we call multi-hint extended Ring-LWE, where some hints on the secret and the noise are given. We present a reduction from RLWE problem to this variant. The second tool is a special form of Leftover Hash Lemma (LHL) over rings, which we call Ring-LHL.

To demonstrate the efficiency of our scheme we provide an optimized implementation of RLWE-based IPFE scheme and show its performance on a practical use case.

Binarized Neural Networks (BNN) provide efficient implementations of Convolutional Neural Networks (CNN). This makes them particularly suitable to perform fast and memory-light inference of neural networks running on resource-constrained devices. Motivated by the growing interest in CNN-based biometric recognition on potentially insecure devices, or as part of strong multi-factor authentication for sensitive applications, the protection of BNN inference on edge devices is rendered imperative. We propose a new method to perform secure inference of BNN relying on secure multiparty computation. While preceding papers offered security in a semi-honest setting for BNN or malicious security for standard CNN, our work yields security with abort against one malicious adversary for BNN by leveraging on Replicated Secret Sharing (RSS) for an honest majority with three computing parties. Experimentally, we implement BaNNeRS on top of MP-SPDZ and compare it with prior work over binarized models trained for MNIST and CIFAR10 image classification datasets. Our results attest the efficiency of BaNNeRS as a privacy-preserving inference technique.

Keywords: multi-party computation, homomorphic encryption, custom PSI protocols, federated analytics, privacy preserving machine learning, and differential privacy

We seek Research Scientists to identify new opportunities and help build scientifically rigorous systems focused on enhancing technological guarantees for consumer privacy while simultaneously expanding the efficiency of Facebook’s market-leading advertising systems. Challenges include leveraging privacy-enhancing technologies such as multi-party computation, homomorphic encryption, federated analytics, and differential privacy to develop privacy-focused advertising solutions (private record-linkage, fraud prevention, reporting and experimentation, and collaborative inference) — all while maintaining performance at massive scale. Minimum Qualifications

PhD in computer science, engineering, cryptography, mathematics or a related field with 2+ years of relevant experience, or MS degree with 6+ years of relevant experience architecting privacy and security solutions

Proficiency designing and implementing analytical and/or algorithmic solutions, tailored to particular business needs and tested on large data sets

Proficiency in C-family (e.g C++, Rust, Go), Python, or similar language

Experience with communicating analysis and establishing confidence among audiences who do not share your disciplinary background or training

Proven track record of innovation

Preferred Qualifications

Expertise on one or more of the following core privacy/security concepts:

Privacy technologies: e.g., homomorphic encryption, secure multi-party computation, federated analytics, trusted execution environments, data minimization, data anonymization, differential privacy

Design and analysis of cryptographic algorithms and protocols, and/or their application to data protection and privacy, authentication, payments, or digital advertising

continued on application webpage see, https://www.facebook.com/careers/v2/jobs/121739569732425/

Closing date for applications:

Contact: Apply Online or reach out to Benjamin Case (bmcase {at} fb DOT com) or Sanjay Saravanan

More information: https://www.facebook.com/careers/v2/jobs/121739569732425/

We have an open Research Fellow position at University College London, within the Information Security Research Group, to work with Professor Steven Murdoch. The Research Fellow will conduct research in the application of privacy-enhancing technologies to improve transparency of measures to prevent financial fraud and to enhance the level of consumer protection available to fraud victims.

The candidate should have (or be close to obtaining) a PhD or equivalent experience in Computer Science or a related field. Research experience in privacy-enhancing technologies, security usability, and/or payment systems is essential. A strong publication record in on or more of these fields, and experience of applied privacy-enhancing technologies is desirable.

This position is part of the REPHRAIN project (https://www.rephrain.ac.uk/), the UK National Research Centre on Privacy, Harm Reduction and Adversarial Influence Online.

The application deadline is 27 January 2021.

Closing date for applications:

Contact: Professor Steven Murdoch (s.murdoch@ucl.ac.uk)

More information: https://murdoch.is/:/rephrainjob