International Association
for Cryptologic Research

3kf9 is a three-key CBC-type MAC that enhances the standardized integrity algorithm f9 (3GPP-MAC). It has beyond-birthday-bound security and is expected to be a possible candidate in constrained environments when instantiated with lightweight blockciphers. Two variants 2kf9 and 1kf9 were proposed to reduce key size for efficiency, but recently, Leurent et al. (CRYPTO'18) and Shen et al. (CRYPTO'21) pointed out critical flaws on these two variants and invalidated their security proofs with birthday-bound attacks.

In this work, we revisit previous constructions of key-reduced variants of 3kf9 and analyze what went wrong in security analyzes. Interestingly, we find that a single doubling at the end can not only fix 2kf9 to go beyond the birthday bound, but also help 1kf9 to go beyond the birthday bound. We then propose two new key-reduced variants of 3kf9, called n2kf9 and n1kf9. By leveraging previous attempts, we prove that n2kf9 is secure up to 2^{2n/3} queries, and prove that n1kf9 is secure up to 2^{2n/3} queries when the message space is prefix-free. We also provide beyond-birthday analysis of n2kf9 in the multi-user setting. Note that compared to EMAC and CBC-MAC, the additional cost to provide a higher security guarantee is expected to be minimal for n2kf9 and n1kf9. It only requires one additional blockcipher call and one doubling.

Some of the most efficient protocols for Multi-Party Computation (MPC) use a two-phase approach where correlated randomness, in particular Beaver triples, is generated in the offline phase and then used to speed up the online phase. Recently, more complex correlations have been introduced to optimize certain operations even further, such as matrix triples for matrix multiplications. In this paper, our goal is to speed up the evaluation of multivariate polynomials and therewith of whole arithmetic circuits in the online phase. To this end, we introduce a new form of correlated randomness: arithmetic tuples. Arithmetic tuples can be fine tuned in various ways to the constraints of application at hand, in terms of round complexity, bandwidth, and tuple size. We show that for many real-world setups an arithmetic tuples based online phase outperforms state-of-the-art protocols based on Beaver triples.

We describe an efficient algorithm for testing and recovering linear equivalence between a pair of $k$-to-$1$ discrete functions with a specific structure. In particular, for $k = 3$ this applies to many APN functions over fields of even characteristic, and for $k = 2$ this applies to all known planar functions over fields of odd characteristic. Our approach is significantly faster than all known methods for testing equivalence, and allows linear equivalence to be tested in practice for dimensions much higher than what has been possible before (for instance, we can efficiently test equivalence for $n = 12$ or $n = 14$ in the case of 3-to-1 APN functions over $\mathbb{F}_{2^n}$, and for $n = 8$ or $n = 9$ in the case of 2-to-1 planar functions over $\mathbb{F}_{3^n}$ within a few minutes even in the worst case). We also develop supplementary algorithms allowing our approach to be extended to the more general case of EA-equivalence. Classifying 3-to-1 APN functions over $\mathbb{F}_{2^n}$ for dimensions as high as $n = 14$ up to EA-equivalence can be performed in a matter of minutes using the developed framework.

In this paper, we propose a noncommutative-ring based unbalanced oil and vinegar signature scheme with key-randomness alignment: NOVA (Noncommutative Oil and Vinegar with Alignment). Instead of fields or even commutative rings, we show that noncommutative rings can be used for algebraic cryptosystems. At the same or better level of security requirement, NOVA has a much smaller public key than UOV (Unbalanced Oil and Vinegar), which makes NOVA practical in most situations. We use Magma to actually implement and give a detailed security analysis against known major attacks.

Permutation polynomials with low $c$-differential uniformity and boomerang uniformity have wide applications in cryptography. In this paper, by utilizing the Weil sums technique and solving some certain equations over $\mathbb{F}_{2^n}$, we determine the $c$-differential uniformity and boomerang uniformity of these permutation polynomials: (1) $f_1(x)=x+\mathrm{Tr}_1^n(x^{2^{k+1}+1}+x^3+x+ux)$, where $n=2k+1$, $u\in\mathbb{F}_{2^n}$ with $\mathrm{Tr}_1^n(u)=1$; (2) $f_2(x)=x+\mathrm{Tr}_1^n(x^{{2^k}+3}+(x+1)^{2^k+3})$, where $n=2k+1$; (3) $f_3(x)=x^{-1}+\mathrm{Tr}_1^n((x^{-1}+1)^d+x^{-d})$, where $n$ is even and $d$ is a positive integer. The results show that the involutions $f_1(x)$ and $f_2(x)$ are APcN functions for $c\in\mathbb{F}_{2^n}\backslash \{0,1\}$. Moreover, the boomerang uniformity of $f_1(x)$ and $f_2(x)$ can attain $2^n$. Furthermore, we generalize some previous works and derive the upper bounds on the $c$-differential uniformity and boomerang uniformity of $f_3(x)$.

Secure multiparty computation (MPC) has been proposed to allow multiple mutually distrustful data owners to jointly train machine learning (ML) models on their combined data. However, the datasets used for training ML models might be under the control of an adversary mounting a data poisoning attack, and MPC prevents inspecting training sets to detect poisoning. We show that multiple MPC frameworks for private ML training are susceptible to backdoor and targeted poisoning attacks. To mitigate this, we propose SafeNet, a framework for building ensemble models in MPC with formal guarantees of robustness to data poisoning attacks. We extend the security definition of private ML training to account for poisoning and prove that our SafeNet design satisfies the definition. We demonstrate SafeNet's efficiency, accuracy, and resilience to poisoning on several machine learning datasets and models. For instance, SafeNet reduces backdoor attack success from $100\%$ to $0\%$ for a neural network model, while achieving $39\times$ faster training and $36 \times$ less communication than the four-party MPC framework of Dalskov et al.

Many applications that benefit from data offload to cloud services operate on private data. A now-long line of work has shown that, even when data is offloaded in an encrypted form, an adversary can learn sensitive information by analyzing data access patterns. Existing techniques for oblivious data access—that protect against access pattern attacks—require a centralized, stateful and trusted, proxy to orchestrate data accesses from applications to cloud services. We show that, in failure-prone deployments, such a centralized and stateful proxy results in violation of oblivious data access security guarantees and/or system unavailability. Thus, we initiate the study of distributed, fault-tolerant, oblivious data access. We present SHORTSTACK , a distributed proxy architecture for oblivious data access in failure-prone deployments. SHORTSTACK achieves the classical obliviousness guarantee—access patterns observed by the adversary being independent of the input—even under a powerful passive persistent adversary that can force failure of arbitrary (bounded-sized) subset of proxy servers at arbitrary times. We also introduce a security model that enables studying oblivious data access with distributed, failure-prone, servers. We provide a formal proof that SHORTSTACK enables oblivious data access under this model, and show empirically that SHORTSTACK performance scales near-linearly with number of distributed proxy servers.

Recent works to improve privacy and auditability in permissioned blockchains like Hyperledger Fabric rely on Idemix, the only anonymous credential system that has been integrated to date. The current Idemix implementation in Hyperledger Fabric (v2.4) only supports a fixed set of attributes, it does not support revocation features, nor does it support anonymous endorsement of transactions (in Fabric, transactions need to be approved by a subset of peers before consensus). A prototype Idemix extension by Bogatov et al. (CANS, 2021) was proposed to include revocation, auditability, and to gain privacy for users. We explore how to gain efficiency, functionality, and further privacy departing from recent works on anonymous credentials based on Structure-Preserving Signatures on Equivalence Classes. As a result, we propose Protego and Protego Duo, two alternatives for Idemix and its recent extensions. We discuss how they can be used in the permissioned blockchain setting and integrated to Hyperledger Fabric. We also provide a prototype implementation and benchmarks showing that both alternatives are twice as fast as state-of-the-art-approaches.

Random sampling from specified distributions is an important tool with wide applications for analysis of large-scale data. In this paper we study how to randomly sample when the distribution is partitioned among two parties' private inputs. Of course, a trivial solution is to have one party send a (possibly encrypted) description of its weights to the other party who can then sample over the entire distribution (possibly using homomorphic encryption). However, this approach requires communication that is linear in the input size which is prohibitively expensive in many settings. In this paper, we investigate secure 2-party sampling with \emph{sublinear communication} for many standard distributions. We develop protocols for $L_1$, and $L_2$ sampling. Additionally, we investigate the feasibility of sublinear product sampling, showing impossibility for the general problem and showing a protocol for a restricted case of the problem. We additionally show how such product sampling can be used to instantiate a sublinear communication 2-party exponential mechanism for differentially-private data release.

An important theme in research on attribute-based encryption (ABE) is minimizing the sizes of the secret keys and ciphertexts. In this work, we present two new ABE schemes with *constant-size* secret keys, that is, the key size is independent of the sizes of policies or attributes, and dependent only on the security parameter lambda.

* We construct the first key-policy ABE scheme for circuits with constant-size secret keys, |sk_f|=poly(lambda), which concretely consist of only three group elements. The previous state-of-the-art construction by [Boneh et al., Eurocrypt '14] has key size polynomial in the maximum depth d of the policy circuits, |sk_f|=poly(d,lambda). Our new scheme removes this dependency of key size on d while keeping the ciphertext size the same, which grows linearly in the attribute length and polynomially in the maximal depth, |ct|=|x|poly(d,lambda).

* We present the first ciphertext-policy ABE scheme for Boolean formulae that simultaneously has constant-size keys and succinct ciphertexts of size independent of the policy formulae, in particular, |sk_f|=poly(lambda) and |ct_x|=poly(|x|,lambda). Concretely, each secret key consists of only two group elements. Previous ciphertext-policy ABE schemes either have succinct ciphertexts but non constant-size keys [Agrawal--Yamada, Eurocrypt '20; Agrawal--Wichs--Yamada, TCC '20], or constant-size keys but large ciphertexts that grow with the policy size, as well as the attribute length. Our second construction is the first ABE scheme achieving *double succinctness*, where both keys and ciphertexts are smaller than the corresponding attributes and policies tied to them.

Our constructions feature new ways of combining lattices with pairing groups for building ABE and are proven selectively secure based on LWE and in the generic (pairing) group model. We further show that when replacing the LWE assumption with its adaptive variant introduced in [Quach--Wee--Wichs FOCS '18] the constructions become adaptively secure.

We propose a mechanism for generating and manipulating protein polymers to obtain a new type of consumable storage that exhibits intriguing cryptographic "self-destruct" properties, assuming the hardness of certain polymer-sequencing problems. To demonstrate the cryptographic potential of this technology, we first develop a formalism that captures (in a minimalistic way) the functionality and security properties provided by the technology. Next, using this technology, we construct and prove security of two cryptographic applications that are currently obtainable only via trusted hardware that implements logical circuitry (either classical or quantum). The first application is a password-controlled secure vault where the stored data is irrecoverably erased once a threshold of unsuccessful access attempts is reached. The second is (a somewhat relaxed version of) one-time programs, namely a device that allows evaluating a secret function only a limited number of times before self-destructing, where each evaluation is made on a fresh user-chosen input. Finally, while our constructions, modeling, and analysis are designed to capture the proposed polymer-based technology, they are sufficiently general to be of potential independent interest.

Fully Homomorphic Encryption (FHE) allows for secure computation on encrypted data. It enables a variety of theoretical and practical applications, but is still several orders of magnitudes too slow to be practical. We present BASALISC, an architecture family of FHE hardware accelerators that aims to substantially accelerate FHE computations in the cloud. BASALISC implements Brakerski, Gentry, and Vaikuntanathan's (BGV) scheme and supports a range of parameter sets. In contrast to many prior studies, we directly support and implement BGV bootstrapping - the noise removal capability necessary to support arbitrary-depth computation.

BASALISC exploits data representation in residue number systems and number-theoretic transforms to realize massive FHE parallelism. We propose a new generalized version of bootstrapping that can be implemented with optimized Montgomery multipliers that cost 46% less in silicon area and 40% less in power consumption versus traditional approaches. BASALISC is a Reduced Instruction Set Computing (RISC) architecture with a four-layer memory hierarchy, including a two-dimensional conflict-free inner memory layer that enables 32 Tb/s radix-256 number-theoretic transform (NTT) computations without pipeline stalls. Our conflict-resolution data permutation hardware is re-used to compute BGV automorphisms without additional hardware and without throughput penalty. BASALISC additionally includes a custom multiply-accumulate unit familiar in Digital Signal Processing (DSP) architectures, with which we accelerate tight BGV key switching loops. The BASALISC computation units and inner memory layers are designed in asynchronous logic, allowing them to run at different speeds to optimize each function. BASALISC is designed for Application-Specific Integrated Circuit (ASIC) implementation with a 1 GHz operational frequency, and is already underway toward tape-out with a 150mm2 die size in a 12nm Global Foundries process.

The BASALISC toolchain comprises both a custom compiler and a joint performance and correctness simulator. We evaluate BASALISC in multiple ways: we study its physical realizability; we emulate and formally verify its core functional units; and we study its performance on a single iteration of logistic regression training over encrypted data. For this application, comprising from up to 900K high-level BASALISC instructions (including 513 bootstraps) down to 27B low-level instructions, we show a speedup of at least 2,025x over HElib - a popular software FHE library - running on a Xeon-class processor.

We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM). Applying our results to lattice parameters from the literature, we find that our algorithm outperforms previous algorithms, assuming unit cost access to a QRACM.

On a technical level, we show how to obtain a quantum speedup on the search for Fast Fourier Transform (FFT) coefficients above a given threshold by leveraging the relative sparseness of the FFT and using quantum amplitude estimation. We also discuss the applicability of the Quantum Fourier Transform in this context. Furthermore, we give a more rigorous analysis of the classical and quantum expected complexity of guessing part of the secret vector where coefficients follow a discrete Gaussian (mod \(q\)).

We revisit the question of what should be the definition of bit security, previously answered by Micciancio-Walter (Eurocrypt 2018) and Watanabe-Yasunaga (Asiacrypt 2021). Our new definition is simple, but (i) captures both search and decision primitives in a single framework like Micciancio-Walter, and (ii) has a firm operational meaning like Watanabe-Yasunaga. It also matches intuitive expectations and can be easily well-estimated in terms of Kullback-Leibler divergence. Along the way of defining bit security and justifying our definition, we raise undervalued concepts such as allowing aborts in security games, considering partial adversaries, and verifiability in security games.

Isogeny-based cryptography is a promising approach for post-quantum cryptography.

The best-known protocol following that approach is the supersingular isogeny Diffie-Hellman protocol (SIDH); this protocol was turned into the CCA-secure key encapsulation mechanism SIKE, which was submitted to and remains in the third round of NIST's post-quantum standardization process as an ``alternate'' candidate.

Isogeny-based cryptography generally relies on the conjectured hardness of computing an isogeny between two isogenous elliptic curves, and most cryptanalytic work referenced on SIKE's webpage exclusively focuses on that problem.

Interestingly, the hardness of this problem is sufficient for neither SIDH nor SIKE. In particular, these protocols reveal additional information on the secret isogeny, in the form of images of specific torsion points through the isogeny.

This paper surveys existing cryptanalysis approaches exploiting this often called ``torsion point information'', summarizes their current impact on SIKE and related algorithms, and suggests some research directions that might lead to further impact.

Private set union (PSU) allows two parties to compute the union of their sets without revealing anything except the union and it has found numerous applications in practice. Recently, some computationally efficient PSU protocols have been designed in the balanced case, but a potential limitation with these approaches is the communication complexity, which scales linearly with the size of the larger set. This is of particular concern when performing PSU in the unbalanced case, where one party is a constrained device (cellphone) holding a small set, and another is a large service provider.

In this work, we propose a generic framework of using the leveled fully homomorphic encryption and a newly introduced protocol called permute matrix Private EQuality Test (pm-PEQT) to construct the \emph{unbalanced} PSU that is secure against semi-honest adversaries. By instantiating the pm-PEQT, we obtain fast unbalanced PSU protocols with a small communication overhead. Our protocol has communication complexity \emph{linear in the size of the smaller set, and logarithmic in the larger set}. More precisely, if the set sizes are $|X|\ll |Y|$, our protocol achieves a communication overhead of $O(|X|\log |Y|)$.

Finally, we implement our protocols that can compare with the state-of-the-art PSU. Experiments show that our protocols are more efficient than all previous protocols in the unbalanced case, especially, the larger the difference of two set sizes, the better our protocols perform. Our running-time-optimized benchmarks show that it takes 18.782 seconds of computation and 2.179 MB of communication to compute the union between $2^{10}$ strings and $2^{19}$ strings. Compared to prior secure PSU proposed by Jia et al. (Usenix Security 2022), this is roughly a $300 \times$ reduction in communication and $20 \times$ reduction in computational overhead with a single thread in WAN/LAN settings.

Private set operations allow two parties perform secure computation on two private sets, such as intersection or union related functions. In this paper, we identify a framework for performing private set operations. At the technical core of our framework is multi-query reverse private membership test (mqRPMT), which is a natural extension of RPMT recently proposed by Kolesnikov et al. (ASIACRYPT 2019). In mqRPMT, a client with set $X = (x_1, \dots, x_n)$ interacts with a server holding a set $Y$. As a result, the server only learns a bit vector $(e_1, \dots, e_n)$ indicating whether $x_i \in Y$ but without knowing the value of $x_i$, while the client learns nothing. We present two constructions of mqRPMT from newly introduced cryptographic primitive and protocol. One is is based on commutative weak pseudorandom function (cwPRF), the other is based on permuted oblivious pseudorandom functions (pOPRF). Both cwPRF and pOPRF can be instantiated from the decisional Diffie-Hellman like assumptions in the random oracle model. We also introduce a slight weak version of mqRPMT dubbed mqRPMT$^*$, in which the client learns the cardinality of $X \cup Y$. We show mqRPMT$^*$ can be build from a category of mqPMT called Sigma-mqPMT, which in turn can be realized from the DDH assumption or oblivious polynomial evaluation. This makes the first step towards establishing the relation between the two building blocks.

We demonstrate the practicality of our framework with implementations. By plugging our cwPRF-based mqRPMT to the general framework, we obtain the first PSU protocol with strict linear complexity. For input sets of size $2^{20}$, the resulting PSU protocol requires roughly 80 MB bandwidth, and 50 seconds using 8 threads. To the best of our knowledge, it requires the least communication among all the known PSU protocols. By plugging our FHE-based mqRPMT$^*$ to the general framework, we obtain a PSU$^*$ suitable for unbalanced setting, whose communication complexity is linear in the size of the smaller set, and logarithmic in the larger set.

Mysten Labs is looking for 2 interns in blockchain cryptography with a focus in any of the following topics: Private NFTs, Anonymous Transactions, Key Loss Protection, Multi-Signatures and Zero Knowledge Proofs.

Successful applicants will work closely with experts in both academia and industry including George Danezis, Konstantinos Chalkias, Foteini Baldimtsi, Alberto Sonnino, François Garillot, Sam Blackshear, Lefteris Kokoris-Kogias, while enjoying a high degree of ownership & autonomy in working conditions & task prioritization.

Ideal candidate expectations:
- PhD or PostDoc researcher - or - engineer in cryptography, software security or distributed systems.

- at least one publication in any of the top cryptography, privacy and security conferences, such as: CCS, S&P, CRYPTO, USENIX SECURITY, EUROCRYPT, ASIACRYPT, NDSS, FC, AsiaCCS, EUROS&P, PETS, CT-RSA, ESORICS etc.

- Understanding of fundamental cryptographic schemes & underlying math for any of the following: hash functions, finite field arithmetic, polynomials (FFT) & elliptic curves, bilinear pairings, threshold signatures.

- Experience implementing high-performance & parallelizable protocols in languages such as Rust, Go, Java, or C/C++, and Github portfolio or productionized implementation will be a plus.

Our team is 100% remote & we are hiring across the world. Here at Mysten Labs, you’ll be joining a world class team with tremendous growth potential. We raised our 1st funding round ($36m series A) from top Silicon Valley VCs led by Andreessen Horowitz (a16z) with participation from Redpoint, Lightspeed, Coinbase Ventures, Electric Capital, Standard Crypto, NFX, Slow Ventures, Scribble Ventures, Samsung Next, Lux Capital etc.

HOW TO APPLY: Applicants are invited to e-mail their CV (use title: Summer 2022 Cryptography Internship) to jobs@mystenlabs.com

Closing date for applications:

Contact: Kostas Chalkias (Chief Cryptographer)

We are looking for a cryptography engineer who will be part of the Blockchain Technology Security Group to build foundational services for JP Morgan distributed ledger technology initiatives. In this role, you will be designing and coding security components and applications. You will have the exciting challenge of working on cutting-edge technology and building enterprise solutions that cater to all the lines of business. You’ll work in a collaborative, trusting, thought-provoking environment—one that encourages diversity of thought and creative solutions that are in the best interests of our customers globally

 

Qualifications

• Experience as applied cryptographer
• Experience with OpenSSL /TLS API; threading and socket programming in Linux, HSMs, and PKCS #11
• Solid understanding of Linux OS with strong knowledge of object oriented programming; specifically high-level languages such as Java, Python, Go, and node.js, C, C++ and Bash
• Familiar/Experience building solutions for digital assets and distributed ledger technology (blockchain) with focus on algorithms and data structures
• Desirable: Experience with multi-party computation (MPC) & HSMs and custody crypto assets

Closing date for applications:

Contact: France Law (france.law@jpmchase.com)

We have a Chair of Junior Professor at Telecom Paris, Institut Polytechnique de Paris, the priority themes for this position are cryptography, data protection, network security, and software security. This 5-year contract Chair has several advantages: a maximum teaching load of 64h per year; associated funding of 320 K€ available at the start of the work; competitive salary; no requirement of the French language; after a 5-year contract, the junior professor can be directly appointed as a Full professor (a permanent, tenured position). Application deadline: August 31, 2022. More information on this position: https://institutminestelecom.recruitee.com/l/en/o/chaire-de-professeur-ou-professeure-junior-en-securite-des-grandes-infrastructures-numeriques-a-telecom-paris

Closing date for applications:

Contact: Hieu Phan (hieu.phan@telecom-paris.fr)

More information: https://institutminestelecom.recruitee.com/l/en/o/chaire-de-professeur-ou-professeure-junior-en-securite-des-grandes-infrastructures-numeriques-a-telecom-paris