International Association
for Cryptologic Research

Ring signatures enable a user to sign messages on behalf of an arbitrary set of users, called the ring. The anonymity of the scheme guarantees that the signature does not reveal which member of the ring signed the message. The notion of linkable ring signatures (LRS) is an extension of the concept of ring signatures such that there is a public way of determining whether two signatures have been produced by the same signer. Lattice-based LRS is an important and active research line, since lattice-based cryptography has attracted more attention due to its distinctive features especially the quantum resistant. However, all the existing lattice-based LRS relied on random oracle heuristics, i.e., no lattice-based LRS in the standard model has been introduced so far. In this paper, we present a lattice-based LRS scheme based on the well- studied standard lattice assumptions (SIS and LWE) in the standard model.

This paper presents the development of cryptography since Shannon's seminal paper ``Communication Theory of Secrecy Systems'' in 1949.

Recent works challenged the Number-Theoretic Transform (NTT) as the most efficient method for polynomial multiplication in GPU implementations of Fully Homomorphic Encryption schemes such as CKKS and BFV. In particular, these works argue that the Discrete Galois Transform (DGT) is a better candidate for this particular case. However, these claims were never rigorously validated, and only intuition was used to argue in favor of each transform. This work brings some light on the dis- cussion by developing similar CUDA implementations of the CKKS cryptosystem, differing only in the underlying transform and related data structure. We ran several experiments and collected perfor- mance metrics in different contexts, ranging from the basic direct comparison between the transforms to measuring the impact of each one on the inference phase of the logistic regression algorithm. Our observations suggest that, despite some specific polynomial ring configurations, the DGT in a stan- dalone implementation does not offer the same performance as the NTT. However, when we consider the entire cryptosystem, we noticed that the effects of the higher arithmetic density of the DGT on other parts of the implementation is substantial, implying a considerable performance improvement of up to 15% on the homomorphic multiplication. Furthermore, this speedup is consistent when we consider a more complex application, indicating that the DGT suits better the target architecture.

In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small endomorphism enables polynomial-time path-finding and endomorphism ring computation (Love-Boneh [36]). As this paper neared completion, it was shown that the endomorphism ring problem in the presence of one known endomorphism reduces to a vectorization problem (Wesolowski [54]). In this paper, we give explicit classical and quantum algorithms for path-finding to an initial curve using the knowledge of one endomorphism. An endomorphism gives an explicit orientation of a supersingular elliptic curve. We use the theory of oriented supersingular isogeny graphs and algorithms for taking ascending/descending/horizontal steps on such graphs. Although the most general runtimes are subexponential, we show that every supersingular elliptic curve has (potentially large) endomorphisms whose exposure would lead to a classical polynomial-time path-finding algorithm.

Existing lattice signature schemes are much less efficient than encryption schemes due to the rejection sampling paradigm. We give a new construction which avoids rejection sampling by using temporary public keys and structured secrets in a Bliss type scheme. Structured secrets also improve existing lattice encryption schemes to nearly the same extreme efficiency. Our signing algorithm is comparative with this optimized encryption efficiency. Our signature scheme allows the same key pair work as an encryption scheme. For lightweight implementation, our techniques allow integrating of public-key encryption and signature in a simple circuit which only needs to do small integer additions as the main part of computation.

We look at two basic coding theoretic and cryptographic mechanisms developed separately and investigate relationships between them and their implications. The first mechanism is Proactive Secret Sharing (PSS), which allows randomization and repair of shares using information from other shares. PSS enables constructing secure multi-party computation protocols that can withstand mobile dynamic attacks.

This self-recovery and the redundancy of uncorrupted shares allows a system to overcome recurring faults throughout its lifetime, eventually finishing the computation (or continuing forever to maintain stored data). The second mechanismis Regenerating Codes (RC) which were extensively studied and adopted in distributed storage systems. RC are error correcting (or erasure handling) codes capable of recovering a block of a distributively held codeword from other servers' blocks. This self-healing nature enables more robustness of a code distributed over different machines. Given that the two mechanisms have a built-in self-healing (leading to stabilizing) and that both can be based on Reed Solomon Codes, it is natural to formally investigate deeper relationships between them.

We prove that a PSS scheme can be converted into an RC scheme, and that under some conditions RC can be utilized to instantiate a PSS scheme. This allows us, in turn, to leverage recent results enabling more efficient polynomial interpolation (due to Guruswami and Wooters) to improve the efficiency of a PSS scheme. We also show that if parameters are not carefully calibrated, such interpolation techniques (allowing partial word leakage) may be used to attack a PSS scheme over time. Secondly, the above relationships give rise to extended (de)coding notions. Our first example is mapping the generalized capabilities of adversaries (called generalized adversary structures) from the PSS realm into the RC one. Based on this we define a new variant of RC we call Generalized-decoding Regenerating Code (GRC) where not all network servers have a uniform sub-codeword (motivated by non-uniform probability of attacking different servers case). We finally highlight several interesting research directions due to our results, e.g., designing new improved GRC, and more adaptive RC re-coding techniques.

Spatial Encryption (SE), which involves encryption and decryption with affine/vector objects, was introduced by Boneh and Hamburg at Asiacrypt 2008. Since the introduction, SE has been shown as a versatile and elegant tool for implementing many other important primitives such as (Hierarchical) Identity-based Encryption ((H)IBE), Broadcast (H)IBE, Attribute-based Encryption, Forward-secure cryptosystems.

In this paper, we revisit SE toward a more compact SE in the lattice setting. In doing that, we introduce a novel primitive called Delegatable Multiple Inner Product Encryption (DMIPE), which is a delegatable generalization of Inner Product Encryption (IPE) but different from the Hierarchical IPE (HIPE) (Okamoto and Takashima at Asiacrypt 2009). We point out that DMIPE and SE are equivalent in the sense that there are security-preserving conversions between them. As a proof of concept, we then successfully instantiate a concrete DMIPE construction relying on the hardness of the decisional learning with errors problem. The DMIPE design in turn implies a more compact lattice-based SE in terms of sizes, in comparison with SEs converted from HIPE (e.g., Xagawa’s HIPE at PKC 2013) using the framework by Chen at al. (Designs, Codes, and Cryptography, 2014). Furthermore, we show that SE can also be used to implement the Allow-/Deny-list encryption, which subsumes, e.g., puncturable encryption (Green and Miers at IEEE S&P 2015) among others

Harvey butterflies and their variants are core primitives in many optimized number-theoretic transform (NTT) implementations, such as those used by the HElib and SEAL homomorphic encryption libraries. However, these butterflies are not constant-time algorithms and may leak secret data when incorrectly implemented. Luckily for SEAL and HElib, the compilers optimize the code to run in constant-time. We claim that relying on the compiler is risky and demonstrate how a simple code modification can cause leakage, which can reduce the hardness of the ring learning with errors (R-LWE) instances used by these libraries, for example, from 2^128 to 2^104.

The continuous learning with errors (CLWE) problem was recently introduced by Bruna et al. (STOC 2021). They showed that its hardness implies infeasibility of learning Gaussian mixture models, while its tractability implies efficient Discrete Gaussian Sampling and thus asymptotic improvements in worst-case lattice algorithms. No reduction between CLWE and LWE is currently known, in either direction. We propose four public-key encryption schemes based on the hardness of CLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Some of our schemes are based on hCLWE, a homogeneous variant, which is no easier than CLWE. Our schemes yield a polynomial-time algorithm for solving hCLWE, and hence also CLWE, using a Statistical Zero-Knowledge oracle.

Intellectual property (IP) cores are essential to creating modern system-on-chips (SoCs). Protecting the IPs deployed in modern SoCs has become more difficult as the IP houses have been established across the globe over the past three decades. The threat posed by IP piracy and overuse has been a topic of research for the past decade or so and has led to creation of a field called watermarking. IP watermarking aims of detecting unauthorized IP usage by embedding excess, nonfunctional circuitry into the SoC. Unfortunately, prior work has been built upon assumptions that cannot be met within the modern SoC design and verification processes. In this paper, we first provide an extensive overview of the current state-of-the-art IP watermarking. Then, we challenge these dated assumptions and propose a new path for future effective IP watermarking approaches suitable for today's complex SoCs in which IPs are deeply embedded.

We determine the exact AND-gate cost of checking if $a\leq x < b$, where $a$ and $b$ are constant integers. Perhaps surprisingly, we find that the cost of interval checking never exceeds that of a single comparison and, in some cases, it is even lower.

Visa Research is a team of world-class research scientists. Our mission is to conduct research on the most challenging problems in the payment industry and provide technical thought leadership for the company’s future. Visa Research engages with internal and external partners to identify and research critical ideas that may have an impact to the payment ecosystem.  Our research agenda focuses on three key areas: Artificial Intelligence, Security, and the Future of Payments.

The Visa Research Advanced Cryptography team is seeking researchers in the following areas:

• Multi-Party Computation
• Fully Homomorphic Encryption/Lattice-Based Cryptography
• Zero-Knowledge Proofs

Knowledge in the application of these technologies to the following areas is a plus:

• Privacy-Preserving Machine Learning
• Digital Currencies
• Identity and Authentication

As an integral member of the team, you will conduct world-class research activities with fellow researchers, and work closely with product and technology teams to ensure the successful creation and application of disruptive and innovative security technologies.

For further details and to apply on-line:

• newly graduated or soon to graduate: https://smrtr.io/7MtBQ
• all other applicants: https://smrtr.io/7R_bd

Closing date for applications:

Contact: Gaven Watson

More information: https://smrtr.io/7R_bd

COSIC is looking for motivated PhD students to work on the implementation aspects of post-quantum cryptographic algorithms: Post-quantum cryptography is a new class of cryptographic algorithms, which resist attacks from quantum computers. They will mostly replace existing public key algorithms (RSA and ECC). Efficient implementations in hardware (FPGA, ASIC) are an essential aspect for their acceptance as replacement. On top, the implementations also need to resist physical attacks, e.g. side-channel and fault attacks. This research position will focus on the efficient and attack resistant implementations of novel post-quantum cryptographic algorithms.

Closing date for applications:

Contact: ingrid.verbauwhede[at]esat.kuleuven.be

More information: https://www.esat.kuleuven.be/cosic/vacancies/

Event date: 13 July to 17 July 2022
Submission deadline: 7 February 2022
Notification: 15 April 2022

Full time remote position We are looking for a Cryptography Research Engineer to join our team. As our Cryptographer expert, you will be working alongside a highly technical team on DeFi and all the cool things from the blockchain ecosystem. Responsibilities: Conduct research in cryptography, in particular new applications of zero-knowledge proofs. Provide written documentation and explain the complex material such that Developers and Product Managers can understand it too. Help internal and external Developers with cryptography parts, like key-management, encryption and signatures. Provide guidance on how to deal with these parts in their projects and/or check the cryptography parts in their code. Write proof-of-concept scripts (in Rust) performing cryptographic tasks, like zero-knowledge proofs or threshold signature schemes. Benchmark and test new cryptography crates on feasibility and performance, to better understand the techniques in practice. Requirements & skills Bachelor Degree in Mathematics, Physics or Computer Science. Strong background in Math/Cryptography. Zero Knowledge practical experience. Experience with system programming (Rust). Ability to communicate complex technical material to technical and non-technical team members. A self-motivated team member able to drive new projects. Passion for the crypto space. Excellent written and verbal communication skills in English. Benefits 100% remote & flexible hours Growing challenging environment Learning possibilities (conferences, meet-ups, courses, etc.) Paid time off Equipment budget Personal development budget Independent Contractor Crypto Payment (USDC)

Closing date for applications:

Contact: Nanni Sackmann

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

Blockstream was founded in 2014 by Dr. Adam Back and a group of fellow cryptographers and engineers passionate about Bitcoin and its potential to change the future of finance. Focusing on building fundamental Bitcoin infrastructure, Blockstream quickly grew into one of the leading technology power houses of the industry.

Through our sidechain technology (the Liquid Network), wallets (Blockstream Green, Blockstream Jade, AQUA), mining colocation (Blockstream Mining), satellite network (Blockstream Satellite), and protocol contributions (Bitcoin research, c-lightning), we are proud to be making global peer-to-peer finance a reality.

The research team supports Blockstream’s efforts and the wider Bitcoin ecosystem. The main focus is on signature schemes and scripting languages for the Bitcoin protocol, sidechains and the Lightning Network. Furthermore, Blockstream Research drives key open source projects in the Bitcoin space.

What You’ll Be Doing (Responsibilities):

• Contribute to open source cryptography libraries such as {rust-,}secp256k1{,-zkp} (implement new schemes, review, QA)
• Help with designing, developing and breaking new cryptographic schemes
• Devise and critically evaluate specifications of cryptographic systems, e.g., in the multi-, threshold- and aggregate-signature space.

What We Look For In You (Required Qualifications):

• Experience implementing cryptography Care about secure and misuse-resistant designs

Nice To Haves (Preferred Qualifications):

• Knowledge of Rust or C or willingness to learn C89
• Previous academic work on digital signatures, discrete logarithm based cryptography, post-quantum cryptography, zero-knowledge proofs, or other areas of cryptography
• Master's degree or PhD in Computer Science or a related field
• Familiarity with Bitcoin and Layer 2’s at a protocol level
• Familiarity with contributing to open source projects

Closing date for applications:

Contact: Andrew Poelstra, apoelstra@blockstream.com

More information: https://boards.greenhouse.io/blockstream/jobs/3846046

We present the first systematic security evaluation of multi-attribute range search schemes on symmetrically encrypted data. We present four database reconstruction attacks that apply to a broad class of schemes and rely on volume and search pattern leakage. For schemes achieving efficiency by decomposing a query into a small number of subqueries, we further show how to exploit their structure pattern, i.e., co-occurrences of subqueries. We introduce a flexible framework for building secure range search schemes by adapting a broad class of geometric search data structures (including range trees and quadtrees) to operate on encrypted data. We give four concrete range search schemes within our framework that support queries on an arbitrary number of dimensions (attributes) and offer a sliding scale of efficiency and security trade-offs. We provide a security proof for any scheme derived from our framework and a thorough analysis of the leakage of our concrete schemes, characterizing the set of equivalent databases and demonstrating information theoretic limitations on reconstruction attacks. Our attacks are the first that do not require the observation of the access pattern to reconstruct data from range queries in two and higher dimensions. Our work shows that for range queries, structure pattern leakage can be as vulnerable to attacks as access pattern leakage. We give a comprehensive evaluation of our schemes and attacks with a complexity analysis, a prototype implementation, and an experimental assessment on real-world datasets.

NTRUEncrypt is one of the first lattice-based encryption schemes. Furthermore, one of the first fully homomorphic encryption (FHE) schemes were built on the NTRU problem. What makes NTRU appealing when designing cryptosystems is the age of the problem and relatively good performance results when compared to ring learning with errors.

Unfortunately, current fully homomorphic schemes based on NTRU became extremely impractical duo to efficient sublattice attacks. Roughly speaking, these types of (leveled) homomorphic encryption schemes, to support a reasonable depth of the circuit we want to evaluate, require publishing RLWE or NTRU encryptions with a very large modulus. Unfortunately, recovering the sublattice and breaking the NTRU problem for such large moduli turns out to be easy, and to compensate, one would need to choose an impractically large dimension. We call NTRU instances with a too large modulus ``overstretched''. Due to the sublattice attacks, any serious work on practical NTRU-based fully homomorphic encryption essentially stopped.

In this paper, we reactivate research on practical FHE that can be based on NTRU. To do so, we design an efficient bootstrapping scheme in which the noise growth is small enough to keep the modulus to dimension ratio relatively small, thus avoiding the negative consequences of ``overstretching'' the modulus. Our bootstrapping algorithm is an accumulation-type bootstrapping scheme analogous to FHEW/TFHE. Finally, we show that we can use the bootstrapping procedure to compute any function over $\mathbb{Z}_p$. Consequently, we obtain one of the fastest FHE schemes to compute arithmetic circuits over finite fields.

Recently, there has been an increase in the popularity of messaging applications that use end-to-end encryption. Among them were Telegram (in October 2021 it has 550 million active users), Signal (in January 2022 it has over 50 million downloads in the Google Play Store), WhatsApp (according to Statista, in 2021 it has over 2 billion active users), Wire (until January 2022 it has been downloaded for over 1 million times on Android devices). Two distinct protocols underlying these applications are noted: MTProto (developed in Russia by Nikolai Durov) and Signal (developed in the US by Moxie Marlinspike). This paper presents the two protocols and examines from the point of view of the primitive cryptographic security used and how the authenticated encryption, key derivation and asynchronous messaging are performed.

Smart contracts are a new form of software that will revolutionize how software is written, IT systems are maintained, and applications and whole businesses are built. Smart contracts are composable and autonomous pieces of software that run on decentralized blockchains, which makes them tamperproof and unstoppable. In this paper, we describe the Internet Computer (IC), which is a radical new design of blockchain that unleashes the full potential of smart contracts, overcoming the limitations of smart contracts on traditional blockchains with respect to speed, storage costs, and computational capacity. This allows smart contracts for the first time to implement fully decentralized applications that are hosted end to end on blockchain. The IC consists of a set of cryptographic protocols that connects independently operated nodes into a collection of blockchains. These blockchains host and execute ``canisters'', the IC’s form of smart contracts. Canisters can store data, perform very general computations on that data, and provide a complete technology stack, serving web pages directly to end users. Computational and storage costs are covered by a ``reverse-gas model'', where canister developers pre-pay costs in cycles that are obtained from ICP, the native token of the IC. ICP tokens are also used for governance: the IC is governed by a decentralized autonomous organization, or DAO, which, among other things, determines changes to the topology of the network and upgrades to the protocol.