International Association
for Cryptologic Research

A transciphering framework converts a symmetric ciphertext into a homomorphic ciphertext on the server-side, reducing computational and communication overload on the client-side. In Asiacrypt 2021, Cho et al. proposed the RtF framework that supports approximate computation.

In this paper, we propose a family of noisy ciphers, dubbed Rubato, with a novel design strategy of introducing noise to a symmetric cipher of a low algebraic degree. With this strategy, the multiplicative complexity of the cipher is significantly reduced, compared to existing HE-friendly ciphers, without degrading the overall security. More precisely, given a moderate block size (16 to 64), Rubato enjoys a low multiplicative depth (2 to 5) and a small number of multiplications per encrypted word (2.1 to 6.25) at the cost of slightly larger ciphertext expansion (1.26 to 1.31). The security of Rubato is supported by comprehensive analysis including symmetric and LWE cryptanalysis. Compared to HERA within the RtF framework, client-side and server-side throughput is improved by 22.9% and 32.2%, respectively, at the cost of only 1.6% larger ciphertext expansion.

In this paper, we provide several improvements over the existing differential-linear attacks on ChaCha. ChaCha is a stream cipher which has $20$ rounds. At CRYPTO $2020$, Beierle et al. observed a differential in the $3.5$-th round if the right pairs are chosen. They produced an improved attack using this, but showed that to achieve a right pair, we need $2^5$ iterations on average. In this direction, we provide a technique to find the right pairs with the help of listing. Also, we provide a strategical improvement in PNB construction, modification of complexity calculation and an alternative attack method using two input-output pairs. Using these, we improve the time complexity, reducing it to $2^{221.95}$ from $2^{230.86}$ reported by Beierle et al. for $256$ bit version of ChaCha. Also, after a decade, we improve existing complexity (Shi et al: ICISC 2012) for a $6$-round of $128$ bit version of ChaCha by more than 11 million times and produce the first-ever attack on 6.5-round ChaCha$128$ with time complexity $2^{123.04}.$

Structured random strings (SRSs) and correlated randomness are important for many cryptographic protocols. In settings where interaction is expensive, it is desirable to obtain such randomness in as few rounds of communication as possible; ideally, simply by exchanging one reusable round of messages which can be considered public keys.

In this paper, we describe how to generate any SRS or correlated randomness in such a single round of communication, using, among other things, indistinguishability obfuscation. We introduce what we call a distributed sampler, which enables $n$ parties to sample a single public value (SRS) from any distribution. We construct a semi-malicious distributed sampler in the plain model, and use it to build a semi-malicious public-key PCF (Boyle et al, FOCS 2020) in the plain model. A public-key PCF can be thought of as a distributed correlation sampler; instead of producing a public SRS, it gives each party a private random value (where the values satisfy some correlation).

We introduce a general technique called an anti-rusher which compiles any one-round protocol with semi-malicious security without inputs to a similar one-round protocol with active security by making use of a programmable random oracle. This gets us actively secure distributed samplers and public-key PCFs in the random oracle model.

Finally, we explore some tradeoffs. Our first PCF construction is limited to reverse-sampleable correlations (where the random outputs of honest parties must be simulatable given the random outputs of corrupt parties); we additionally show a different construction without this limitation, but which does not allow parties to hold secret parameters of the correlation. We also describe how to avoid the use of a random oracle at the cost of relying on sub-exponentially secure indistinguishability obfuscation.

Threshold signatures are a crucial tool for many distributed protocols. As shown by Cachin, Kursawe, and Shoup (PODC `00), schemes with unique signatures are of particular importance, as they allow to implement distributed coin flipping very efficiently and without any timing assumptions. This makes them an ideal building block for (inherently randomized) asynchronous consensus protocols. The threshold-BLS signature of Boldyreva (PKC `03) is both unique and very compact, but unfortunately lacks a security proof against adaptive adversaries. Thus, current consensus protocols either rely on less efficient alternatives or are not adaptively secure. In this work, we revisit the security of the threshold BLS signature by showing the following results, assuming $t$ adaptive corruptions:

- We give a modular security proof that follows a two-step approach: 1) We introduce a new security notion for distributed key generation protocols (DKG). We show that it is satisfied by several protocols that previously only had a static security proof. 2) Assuming any DKG protocol with this property, we then prove unforgeability of the threshold BLS scheme. Our reductions are tight and can be used to substantiate real-world parameter choices.

- To justify our use of strong assumptions such as the algebraic group model (AGM) and the hardness of one-more-discrete logarithm (OMDL), we prove two impossibility results: 1) Without the AGM, there is no tight security reduction from $(t+1)$-OMDL. 2) Even in the AGM, $(t+1)$-OMDL is the weakest assumption from which any (possibly loose) security reduction exists.

This paper proposes Băhēm; a symmetric cipher that, when given a random-looking key k, a true random number generator (TRNG) and a cleartext message m to encrypt, no cryptanalysis can degrade its security below min[H(m), H(k)] bits of entropy, even under Grover's algorithm or even if it turned out that P = NP.

Aside from the cost of memory access and input/output processing, Băhēm requires only three additions (one per-session, two per-block) and one XOR operation in order to encrypt or decrypt, and is also highly parallelise-able.

Despite Băhēm's 1-bit overhead per cleartext bit, its early prototype, Alyal, achieved similar run-time speeds to OpenSSL's ChaCha20; slightly faster decryption, while slightly slower encryption when the TRNG was prepared in a file in advance. This demonstrates that Băhēm is practicality usable for many real-world application scenarios.

Later implementations, with better TRNG optimisations and parallelism, must allow the prototype a faster run-time for both, encryption and decryption.

In the artificial intelligence as a service (AIaaS) system in the client-server model, where the clients provide the data on the cloud and the server processes the data by using the deep neural network in the cloud, data privacy via homomorphic encryption is getting more important. Brakerski/Fan-Vercauteran (BFV) and Cheon-Kim-Kim-Song (CKKS) schemes are two representative homomorphic encryption schemes which support various arithmetic operations for encrypted data in the single-instruction multiple-data (SIMD) manner. As the homomorphic operations in these schemes are performed component-wisely for encrypted message vectors, the rotation operations for various cyclic shifts of the encrypted message vector are required for useful advanced operations such as bootstrapping, matrix multiplication, and convolution in convolutional neural networks. Since the rotation operation requires different Galois keys for different cyclic shifts, the servers using the conventional BFV and CKKS schemes should ask the clients having their secret keys to generate and send all of the required Galois keys. In particular, in the advanced services that require rotation operations for many cyclic shifts such as deep convolutional neural networks, the total Galois key size can be hundreds of gigabytes. It imposes substantial burdens on the clients in the computation and communication cost aspects. In this paper, we propose a new concept of \emph{hierarchical Galois key generation method} for homomorphic encryption to reduce the burdens of the clients and the server running BFV and CKKS schemes. The main concept in the proposed method is the hierarchical Galois keys, such that after the client generates and transmits a few Galois keys in the highest key level to the server, the server can generate any required Galois keys from the public key and the smaller set of Galois keys in the higher key level. This proposed method significantly reduces the number of the clients' operations for Galois key generation and the communication cost for the Galois key transmission. Since the server can generate the required Galois keys by using the received small set of Galois keys from the client, the server does not need to request additional Galois keys to the clients or to store all possible Galois keys for future use. For example, if we implement the standard ResNet-20 network for the CIFAR-10 dataset and the ResNet-18 network for the ImageNet dataset with pre-trained parameters of the CKKS scheme with the polynomial modulus degree $N=2^{16}$ and $N=2^{17}$, respectively, the server requires 265 and 617 Galois keys, which occupy 105.6GB and 197.6GB of memory, respectively. If we use the proposed three-level hierarchical Galois key system, the Galois key size generated and transmitted by the client can be reduced from 105.6GB to 3.4GB for ResNet-20 model for CIFAR-10, and reduced from 197.6GB to 3.9GB for ResNet-18 model for ImageNet.

Currently, a vast majority of symmetric-key cryptographic schemes are built as block cipher modes. The block cipher is designed to be hard to distinguish from a random permutation and this is supported by cryptanalysis, while (good) modes can be proven secure if a random permutation takes the place of the block cipher. As such, block ciphers form an abstraction level that marks the border between cryptanalysis and security proofs. In this paper, we investigate a re-factored version of symmetric-key cryptography built not around the block ciphers but rather the deck function: a keyed function with arbitrary input and output length and incrementality properties. This allows for modes of use that are simpler to analyze and still very efficient thanks to the excellent performance of currently proposed deck functions. We focus on authenticated encryption modes with varying levels of robustness. Our modes have built-in support for sessions, but are also efficienty without them. As a by-product, we define a new ideal model for authenticated encryption dubbed the jammin cipher. Unlike the OAE2 security models, the jammin cipher is both a operational ideal scheme and a security reference, and addresses real-world use cases such as bi directional communication and multi-key security.

Quantum computers will break cryptographic primitives that are based on integer factorization and discrete logarithm problems. SABER is a key agreement scheme based on the Learning With Rounding problem that is quantum-safe, i.e., resistant to quantum computer attacks. This article presents a high-speed silicon implementation of SABER in a 65nm technology as an Application Specific Integrated Circuit. The chip measures 1$mm^2$ in size and can operate at a maximum frequency of 715$MHz$ at a nominal supply voltage of 1.2V. Our chip takes 10$\mu s$, 9.9$\mu s$ and 13$\mu s$ for the computation of key generation, encapsulation, and decapsulation operations of SABER. The average power consumption of the chip is 153.6$mW$. Physical measurements reveal that our design is 8.96x (for key generation), 11.80x (for encapsulation), and 11.23x (for decapsulation) faster than the best known silicon-proven SABER implementation.

Private set-intersection (PSI) is one of the most practically relevant special-purpose secure multiparty computation tasks, as it is motivated by many real-world applications. In this paper we present a new private set-intersection protocol which is laconic, meaning that the protocol only has two rounds and that the first message is independent of the set sizes. Laconic PSI can be useful in applications, where servers with large sets would like to learn the intersection of their set with smaller sets owned by resource-constrained clients and where multiple rounds of interactions are not possible.

Previously, practically relevant laconic PSI protocols were only known from factoring-type assumptions. The contributions of this work are twofold: 1) We present the first laconic PSI protocol based on assumptions over pairing-friendly elliptic curves; and 2) For the first time we provide empirical evaluation of any laconic PSI protocol by carefully implementing and optimising both our and previous protocols. Our experimental results shows that our protocol outperforms prior laconic PSI protocols.

We consider the problem of uniformly sampling supersingular elliptic curves over finite fields of cryptographic size (SRS problem). The currently best-known method combines the reduction of a suitable CM $j$-invariant and a random walk over some isogeny graph. Unfortunately, this method is not suitable for cryptographic applications because it leaks too much information about the endomorphism ring of the generated curve. This fact motivates a stricter version of the SRS problem, requiring that the sampling algorithm gives no extra information about the endomorphism ring of the output curve (cSRS problem). The known cSRS algorithms work only for small finite fields, since they involve the computation of polynomials of large degree. In this work we formally define the SRS and cSRS problems, we discuss the relevance of cSRS for cryptographic applications, and we provide a self-contained survey of the known approaches to both the problems. Afterwards, we describe and analyse some alternative techniques, based either on Hasse invariant or division polynomials, and we explain the reasons why these techniques do not readily lead to efficient cSRS algorithms.

Research in post-quantum cryptography (PQC) aims to develop cryptographic algorithms that can withstand classical and quantum attacks. The recent advance in the PQC field has gradually switched from the theory to the implementation of cryptographic algorithms on hardware platforms. In addition, the PQC standardization process of the National Institute of Standards and Technology (NIST) is currently in its third round. It specifies ease of protection against side-channel analysis (SCA) as an essential selection criterion. Following this trend, in this paper, we evaluate side-channel leakages of existing PQC implementations using PQC-SEP, a completely automated side-channel evaluation platform at both pre-and post-silicon levels. It automatically estimates the amount of side-channel leakage in the power profile of a PQC design at early design stages, i.e., RTL, gate level, and physical layout level. It also efficiently validates side-channel leakages at the post-silicon level against artificial intelligence (AI) based SCA models and traditional SCA models. Further, we delineate challenges and approaches for future research directions.

Unique signatures are digital signatures with exactly one unique and valid signature for each message. The security reduction for most unique signatures has a natural reduction loss (in the existentially unforgeable against chosen-message attacks, namely EUF-CMA, security model under a non-interactive hardness assumption). In Crypto 2017, Guo {\it et al.} proposed a particular chain-based unique signature scheme where each unique signature is composed of $n$ BLS signatures computed sequentially like a blockchain. Under the computational Diffie-Hellman assumption, their reduction loss is $n\cdot q_H^{1/n}$ for $q_H$ hash queries and it is logarithmically tight when $n=\log{q_H}$. However, it is currently unknown whether a better reduction than logarithmical tightness for the chain-based unique signatures exists.

We show that the proposed chain-based unique signature scheme by Guo {\it et al.} must have the reduction loss $q^{1/n}$ for $q$ signature queries when each unique signature consists of $n$ BLS signatures. We use a meta reduction to prove this lower bound in the EUF-CMA security model under any non-interactive hardness assumption, and the meta-reduction is also applicable in the random oracle model. We also give a security reduction with reduction loss $4\cdot q^{1/n}$ for the chain-based unique signature scheme (in the EUF-CMA security model under the CDH assumption). This improves significantly on previous reduction loss $n\cdot q_H^{1/n}$ that is logarithmically tight at most. The core of our reduction idea is a {\em non-uniform} simulation that is specially invented for the chain-based unique signature construction.

We consider the McEliece cryptosystem with a binary Goppa code $C \subset \mathbb{F}_2^n$ specified by an irreducible Goppa polynomial $g(x) \in \mathbb{F}_{2^m}[x]$ and Goppa points $(\alpha_1, \ldots, \alpha_n) \in \mathbb{F}_{2^m}^n$. Since $g(x)$ together with the Goppa points allow for efficient decoding, these parameters form McEliece secret keys. Such a Goppa code $C$ is an $(n-tm)$-dimensional subspace of $\mathbb{F}_2^n$, and therefore $C$ has co-dimension $tm$. For typical McEliece instantiations we have $tm \approx \frac n 4$.

We show that given more than $tm$ entries of the Goppa point vector $(\alpha_1, \ldots, \alpha_n)$ allows to recover the Goppa polynomial $g(x)$ and the remaining entries in polynomial time. Hence, in case $tm \approx \frac n 4$ roughly a fourth of a McEliece secret key is sufficient to recover the full key efficiently.

Let us give some illustrative numerical examples. For ClassicMcEliece with $(n,t,m)=(3488,64,12)$ on input $64\cdot 12+1=769$ Goppa points, we recover the remaining $3488-769=2719$ Goppa points in $\mathbb{F}_{2^{12}}$ and the degree-$64$ Goppa polynomial $g(x) \in \mathbb{F}_{2^{12}}[x]$ in $1$ minute.

For ClassicMcEliece with $(n,t,m)=(8192,128,13)$ on input $128\cdot 13+1=1665$ Goppa points, we recover the remaining $8192-1665=6529$ Goppa points in $\mathbb{F}_{2^{13}}$ and the degree-$128$ Goppa polynomial $g(x) \in \mathbb{F}_{2^{13}}[x]$ in $5$ minutes.

Our results also extend to the case of erroneous Goppa points, but in this case our algorithms are no longer polynomial time.

Functional commitments (Libert et al.~[ICALP'16]) allow a party to commit to a vector $\vec v$ of length $n$ and later open the commitment at functions of the committed vector succinctly, namely with communication logarithmic or constant in $n$. Existing constructions of functional commitments rely on trusted setups and have either $O(1)$ openings and $O(n)$ parameters, or they have short parameters generatable using public randomness but have $O(\log n)$-size openings. In this work, we ask whether it is possible to construct functional commitments in which both parameters and openings can be of constant size. Our main result is the construction of the first FC schemes matching this complexity. Our constructions support the evaluation of inner products over small integers; they are built using groups of unknown order and rely on succinct protocols over these groups that are secure in the generic group and random oracle model.

Mysten is looking for a remote applied cryptographer & researcher interested in cryptographic protocols & their application to blockchains. You would work with us to design, check & implement mission-critical algorithms a range of areas, including primitives such as pairing-based crypto, signature aggregation & distributed key generation, random beacons, efficient accumulators & zero-knowledge proofs.

This role gives the opportunity to work closely with a senior team of experts in theoretical computer science, cryptography, language & systems design, while enjoying a high degree of ownership & autonomy in working conditions & task prioritization. We regularly publish to conferences like CCS, S&P, CRYPTO, NDSS, FC, AsicCCS, PETS, CT-RSA, ESORICS, ACNS etc.

While the following guidelines reflect some of our thinking about a background we would like to see in a candidate, we are committed to diversity, & more surprising profiles with a good argument to fit & capability are encouraged to apply.

Our ideal candidate would have:
- 2+ years of experience in hands-on software engineering for cryptographic operations, such as signature schemes, accumulators, key management, data encryption & compression.

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

- Experience implementing high-performance & parallelizable protocols in languages such as Rust, Go, Java, or C/C++.

- Experience implementing ZKP circuits or proof systems (Groth16, Halo, Plonk, STARKs, Marlin) is considered 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 & many other great funds & angels!

Closing date for applications:

Contact: Kostas Chalkias (Chief Cryptographer) kostas {at} mystenlabs.com

More information: https://jobs.lever.co/mystenlabs/3733dd29-260f-41ac-80a6-127bd84aabd1

Full-time remote position

You’ll be building the first ZK rollup in the Polkadot ecosystem with other exciting projects like Whirlpool Cash needing your expertise after.

As a high level blockchain developer with exposure to zero knowledge proofs, or cryptographer in the blockchain space with relevant programming skills, you’ll be working on cutting edge technology that will help shape DeFi.

Responsibilities

Design, implement and build a ZK rollup in Polkadot ecosystem (Rust-Substrate)

Collaborate with our team of elite level rust, cryptography and substrate experts

Research ZK protocols and their underlying mathematical concepts. Study, understand and communicate the latter cryptographic primitives (e.g: signatures, NIZK, key derivation) relevant in the blockchain space.

Produce technical specifications for designs & instantiations of cryptographic protocols

Investigate new zero-knowledge applications im Whirlpool that allow the user to manage their deposits without compromising their privacy

Ensure thorough project quality and security

Write highly secure Rust code

Requirements & skills:

Fluency in Rust, C++, Golang or similar languages, we are working primarily with Rust Substrate.

Experience in cryptography and blockchain infrastructure development

Familiarity with zero-knowledge schemes (Plonk and Plonky preferred).

Passion for Crypto/DeFi

Nice to have:

Experience with scalability techniques such layer 2s (Optimistic and zk-based).

Experience with implementing recursive zk-proofs.

Experience with XMCP and relay-para-chain structure.

Is interested in the Polkadot ecosystem

Perks: Competitive Crypto payments, all made in USDC.

100% remote work. No geographic restrictions.

The ability to work as an independent contractor: We treat you as your own agent and support you accordingly!

Annual Working Equipment Allowance.

Monthly Gym & Fitness Bonus

Global WeWork membership

Annual Personal Development Budget

Closing date for applications:

Contact: Maya Jerath

More information: https://incredulous.bamboohr.com/jobs/view.php?id=124

Medical Data Privacy and Privacy-Preserving ML on Healthcare Data (MDPPML) group at the University of Tübingen is looking for motivated Ph.D. students in the area of Privacy Enhancing Technologies.

Research Topics: Development and analysis of cryptography-based privacy-preserving solutions for real-world healthcare problems. Topics of interest include (but are not limited to): privacy-preserving machine learning, genomic privacy, medical privacy as well as foundations for real-world cryptography.

Your profile:

• Completed Master's degree (or equivalent) at a top university with excellent grades in computer science, or a similar area.
• Knowledge in applied cryptography/security and cryptographic protocols.
• Knowledge in machine learning.
• Very good software development skills.
• Self-motivated, reliable, creative, can work independently and want to do excellent research.

Closing date for applications:

Contact: Dr. Mete Akgün (mete.akguen@uni-tuebingen.de)

We are looking for a Cryptography Architect to join our team to help define the next generation of secure Hardware and Software implementations of Post Quantum Cryptography.

Responsibilities:

Design, implement and analyse post quantum cryptographic algorithms including key exchange algorithms and digital signature schemes

• Investigate new and future algorithms, research potential implementations and optimisation for efficient implementation.
• Develop Architectural descriptions and models of PQ Cryptographic Algorithms
• Interface with the Engineering team, provide specifications for Micro-Architectural planning and implementation.
• Perform security analysis of Post Quantum and Classical Cryptography implementations
• Research and propose secure attack resistant (SCA, Fault) implementations of Post Quantum Algorithms.

Preferred Skills and Qualifications

• PhD or degree in Cryptography, Applied Cryptography, Mathematics or Computer Science
• 2+ years of work experience or research in the field of Post-Quantum Cryptography
• Knowledge of Secure Implementations of cryptography
• Knowledge of Side-channel analysis of cryptographic primitives
• Theoretical understanding of common side-channel countermeasures
• Programming skills , C/C++, Python, Mathematics tools

Closing date for applications:

Contact: Graeme Hickey

More information: https://pqshield.com/

The Chair of Systems Engineering is conducting research in various cooperations with known industry partners and international EU-Third-Party funded projects. Tasks: Independent research in the field of systems engineering, especially in the field of cloud computing, confidential computing and cryptography. The development, publication and presentation of scientific publications at national and international conferences as well as journals are expected. Requirements: - very good university degree (M.Sc., Dipl.) in Computer Science - strong skills in distributed systems - ability to work independently and purposefully in a team - an integrative and cooperative personality with excellent communication and social skills - high engagement - fluency in English - written and oral - interest in interdisciplinary cooperation in all areas of computer science as well as with industrial partners - practical experiences with various programming languages and concepts What we offer: You join a team of enthusiastic scientists who creatively pursue their individual research work. Applications from women are particularly welcome. The same applies to people with disabilities. Your application (in English only) should include: motivation letter, CV, copy of degree certificate and proof of English language skills. Complete applications should be sent to se@mailbox.tu-dresden.de Interested? And you want to know more about it? Please contact: Prof. Dr. Christof Fetzer se@mailbox.tu-dresden.de

Closing date for applications:

Contact: Prof. Dr. Christof Fetzer se@mailbox.tu-dresden.de

Warsaw Doctoral School of Mathematics and Computer Science is looking for Ph.D. students. If you are interested in doing a Ph.D. in cryptography or blockchain at the University of Warsaw please contact Stefan Dziembowski (s.dziembowski+phd@uw.edu.pl)

Closing date for applications:

Contact: Stefan Dziembowski

More information: https://szkolydoktorskie.uw.edu.pl/en/mathematics-and-computer-sciences-recruitment-2022-2023/