International Association
for Cryptologic Research

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.

In 2019, Gabizon, Williamson, and Ciobotaru introduced PlonK – a fast and flexible ZK-SNARK with an updatable and universal structured reference string. PlonK uses a grand product argument to check permutations of wire values, and exploits convenient interactions between multiplicative subgroups and Lagrange bases. The following year, Gabizon and Williamson used similar techniques to develop plookup – a ZK-SNARK that can verify that each element from a list of queries can be found in a public lookup table. In this paper, we present PlonKup, a fully succinct ZK-SNARK that integrates the ideas from plookup into PlonK in an efficient way.

Recently, Ateniese et al. (CRYPTO 2019) proposed a new cryptographic primitive called matchmaking encryption (ME), which provides fine-grained access control over encrypted data by allowing both the sender and receiver to specify access control policies. The encrypted message can be decrypted correctly if and only if the attributes of the sender and receiver simultaneously meet each other's specified policies. In current ME, when users from different organizations need secret communication, they need to be managed by a single-authority center. However, it is more reasonable if users from different domains obtain secret keys from their own authority centers, respectively. Inspired by this, we extend ME to cross-domain scenarios. Specifically, we introduce the concept of the cross-domain ME and instantiate it in the identity-based setting (i.e., cross-domain identity-based ME). Then, we first formulate and design a cross-domain identity-based ME (IB-ME) scheme and prove its privacy and authenticity in the random oracle model. Further, we extend the cross-domain IB-ME to the multi-receiver setting and give the formal definition, concrete scheme and security proof. Finally, we analyze and implement the schemes, which confirms the efficiency feasibility.

About Status

As a product, Status is an open source, Ethereum-based app that gives users the power to chat, transact, and access a revolutionary world of DApps on the decentralized web. But Status is also building foundational infrastructure for the whole Ethereum ecosystem, including the Nimbus ETH 1.0 and 2.0 clients, the Keycard hardware wallet, and the Waku messaging protocol (a continuation of Whisper).

The role:

You’ll work within a small team to contribute to the design and implementation of the next generation of distributed storage solutions. This effort aligns well with the storage requirements for both the Status chat client as well as the Ethereum ecosystem at large. Familiarity with message propagation in loosely connected networks, DHTs, gossiping and routing mechanisms is highly desirable. Experience with massively distributed systems is a plus. Familiarity with off the shelf networking stacks such as libp2p or devp2p is also desirable.

Responsibilities:

Write and maintain Nim code.

Research and design core functionality.

Provide feedback on overall design decisions and participate in code reviews.

Use libp2p to build application level protocols.

Strong understanding of p2p building blocks such as gossiping, routing and discovery (DHTs), Nat traversal.

Strong understanding of TCP and UDP protocols.

Strong understanding of encryption and key exchange mechanisms.

Ability to interpret and implement solutions based on academic research.

You must have:

Strong passion for blockchain technology and decentralisation.

Strong academic or engineering background.

Experience with low level/strongly typed languages (C/C++/Go/Rust or Java/C#).

Experience with Open Source software.

Experience building networking heavy applications and p2p networking specifically

Bonus points if you have:

Contributed to an blockchain-related, open source project.

Experience with Nim.

Experience with libp2p / devp2p, networking, cryptography.

Worked on storage and file systems.

Closing date for applications:

Contact: Email: angel@status.im Discord: LilChiChi#0021

More information: https://jobs.status.im/?gh_jid=3704158