International Association
for Cryptologic Research

Cryptography Services @ NCC Group | NYC, SF, Chicago and Waterloo, Ontario, Canada

NCC Group Crypto Services is hiring interns for summer 2021! We're a small-ish team auditing applied crypto and doing research in the field. If you like cryptography and security, and would like to pursue a research project in any of the applied crypto areas, such as (but not limited to):

- cryptographic implementations (cryptographic protocols or primitives block ciphers, elliptic cures, hash functions, lightweight crypto, post-quantum crypto)
- cryptocurrencies (audits of novel consensus algorithms, privacy preserving technologies in this space, etc.)
- audits of existing cryptographic software

The position will possibly be fully remote. The intern will get a feel of what crypto consulting looks like and do a research project with the help of a member of NCC Group CS team. Only candidates with legal permission to work in US or Canada would be considered due to short-term nature of the job.

Closing date for applications:

Contact: cs-intern-jobs@nccgroup.com

More information: https://www.nccgroup.com/us/our-services/cyber-security/specialist-practices/cryptography-services/

Ciet et al.(2006) proposed an elegant method for trading inversions for multiplications when computing [2] P+Q from two given points P and Q on elliptic curves of Weierstrass form. Motivated by their work, this paper proposes a fast algorithm for computing [4] P with only one inversion in affine coordinates. Our algorithm that requires 1I+ 8S+ 8M, is faster than two repeated doublings whenever the cost of one field inversion is more expensive than the cost of four field multiplications plus four field squarings (ie I> 4M+ 4S). It saves one field multiplication and one field squaring in comparison with the Sakai-Sakurai method (2001). Even better, for special curves that allow" a= 0"(or" b= 0") speedup, we obtain [4] P in affine coordinates using just 1I+ 5S+ 9M (or 1I+ 5S+ 6M, respectively).

Payment Channel Networks (PCNs) have given a huge boost to the scalability of blockchain-based cryptocurrencies: Beyond improving the transaction rate, PCNs enabled cheap cross-currency payments and atomic swaps. However, current PCNs proposals either heavily rely on special scripting features of the underlying blockchain (e.g. Hash Time Lock Contracts) or are tailored to a handful of digital signature schemes, such as Schnorr or ECDSA signatures. This leaves us in an unsatisfactory situation where many currencies that are being actively developed and use different signature schemes cannot enjoy the benefits of a PCN.

In this work, we investigate whether we can construct PCNs assuming the minimal ability of a blockchain to verify a digital signature, for any signature scheme. In answering this question in the affirmative, we introduce the notion of lockable signatures, which constitutes the cornerstone of our PCN protocols. Our approach is generic and the PCN protocol is compatible with any digital signature scheme, thus inheriting all favorable properties of the underlying scheme that are not offered by Schnorr/ECDSA (e.g.\ aggregatable signatures or post-quantum security).

While the usage of generic cryptographic machinery makes our generic protocol impractical, we view it as an important feasibility result as it may serve as the basis for constructing optimized protocols for specific signature schemes. To substantiate this claim, we design a highly efficient PCN protocol for the special case of Boneh-Lynn-Shacham (BLS) signatures. BLS signatures enjoy many unique features that make it a viable candidate for a blockchain, e.g. short, unique, and aggregatable signatures. Yet, prior to our work, no PCN was known to be compatible with it (without requiring an advanced scripting language). The cost of our PCN is dominated by a handful of calls to the BLS algorithms. Our concrete evaluation of these basic operations shows that users with commodity hardware can process payments with minimal overhead.

Hierarchical secret sharing is an important key management technique since it is specially customized for hierarchical organizations with different departments allocated with different privileges, such as the government agencies or companies. Hierarchical access structures have been widely adopted in secret sharing schemes, where efficiency is the primary consideration for various applications. How to design an efficient hierarchical secret sharing scheme is an important issue. In 2007, a famous hierarchical secret sharing (HSS) scheme was proposed by Tassa based on Birkhoff interpolation, and later, based on the same method, many other HSS schemes were proposed. However, these schemes all depend on Polya's condition, which is a necessary condition not a sufficient condition. It cannot guarantee that Tassa's HSS scheme always exists. Furthermore, this condition needs to check the non-singularity of many matrices. We propose a hierarchical multi-secret sharing scheme based on the linear homogeneous recurrence (LHR) relations and the one-way function. In our scheme, we select $m$ linearly independent homogeneous recurrence relations. The participants in the highly-ranked subsets $\gamma_1, \gamma_2 ,\cdots, \gamma_{j-1}$ join in the $j$-th subset to construct the $j$-th LHR relation. In addition, the proposed hierarchical multi-secret sharing scheme just requires one share for each participant, and keeps the same computational complexity. Compared with the state-of-the-art hierarchical secret sharing schemes, our scheme has high efficiency.

Today, users' data is gathered and analyzed on a massive scale. While user data analytics such as personalized advertisement need to make use of this data, users may not wish to divulge their information without security and privacy guarantees. Private Stream Aggregation (PSA) allows the secure aggregation of time-series data, affording security and privacy to users' private data, which is much more efficient than general secure computation such as homomorphic encryption, multiparty computation, and secure hardware based approaches. Earlier PSA protocols face limitations including needless complexity or a lack of post-quantum security. In this work, we present SLAP, a lattice-based PSA protocol. SLAP features two variants with post-quantum security, with simpler and more efficient computations enabled by (1) the white- box approach that builds the encryption directly from the Ring Learning With Error assumption and (2) the state-of-the-art algorithmic optimization in lattice-based cryptography. We show that SLAP meets the security and privacy requirements of PSA, and show experimentally the improvements of SLAP over similar work. We show a speedup of 20.76x over the previous state-of-the-art lattice-based PSA work's aggregation, and apply techniques including RNS, NTT, and batching to obtain a throughput of over 600,000 aggregations per second.

Ransomware is a type of malware that blocks an user’s access to files and requests him/her a ransom. The main approach of an attacker is to encrypt the user’s files and give him/her the decrypting tool only after he/she pays the requested amount of money. The payment is usually done in difficult to trace currencies. In this paper, we provide a review of the ransomware phenomenon, making a clear distinction between the threats before and after WannaCry (which appeared in May 2017). Initially, we give two taxonomy examples from the literature and one designed by us. The first two taxonomies use ”Platform”, ”Cryptosystem”/”Crypto”, ”Severity”, ”Attack” and ”Target” as criteria (the terms appear in one of them or both), but we have chosen ”Target Zone”, ”Propagation”, ”Payment” and ”Weakness”. We further describe/compare ransomware programs, taking into account several aspects including how they work (e.g., encryption methods), whom they target (e.g., individuals/organizations), what impact they have and what weaknesses can be used to provide countermeasures (besides the general prevention techniques that we mention briefly).

In 2017, Tang et al. have introduced a generic construction for bent functions of the form $f(x)=g(x)+h(x)$, where $g$ is a bent function satisfying some conditions and $h$ is a Boolean function. Recently, Zheng et al. generalized this result to construct large classes of bent vectorial Boolean function from known ones in the form $F(x)=G(x)+h(X)$, where $G$ is a bent vectorial and $h$ a Boolean function. In this paper we further generalize this construction to obtain vectorial bent functions of the form $F(x)=G(x)+\mathbf{H}(X)$, where $\mathbf{H}$ is also a vectorial Boolean function. This allows us to construct new infinite families of vectorial bent functions, EA-inequivalent to $G$, which was used in the construction. Most notably, specifying $\mathbf{H } (x)=\mathbf{h} (Tr_1^n(u_1x),\ldots,Tr_1^n(u_tx))$, the function $\mathbf{h} :\mathbb{F}_2^t \rightarrow \mathbb{F}_{2^t}$ can be chosen arbitrary which gives a relatively large class of different functions for a fixed function $G$. We also propose a method of constructing vectorial $(n,n)$-functions having maximal number of bent components.

Competitions are widely viewed as the safest way to select cryptographic algorithms. This paper surveys procedures that have been used in cryptographic competitions, and analyzes the extent to which those procedures reduce security risks.

Cryptocurrencies and decentralized ledger technology has been widely adopted over the last decades. However, there isn’t yet a decentralized exchange that protects users’ privacy from end to end. In this paper, we construct the first ledger-based decentralized token exchange with strong privacy guarantees. We propose the first Decentralized Anonymous eXchange scheme (DAX scheme) based on automated market maker (AMM) and zkSNARK and present a formal definition of its security and privacy properties.

Homomorphic encryption (HE) is considered as one of the most important primitives for privacy-preserving applications. However, an efficient approach to evaluate both polynomial and non-polynomial functions on encrypted data is still absent, which hinders the deployment of HE to real-life applications. To address this issue, we propose a practical framework PEGASUS. PEGASUS can efficiently switch back and forth between a packed CKKS ciphertext and FHEW ciphertexts without decryption, allowing us to evaluate arithmetic functions efficiently on the CKKS side, and to evaluate look-up tables on FHEW ciphertexts. Our FHEW ! CKKS conversion algorithm is more practical than the existing methods. We improve the computational complexity from linear to sublinear. Moreover, the size of our conversion key is significantly smaller, e.g., reduced from 80 gigabytes to 12 megabytes. We present extensive benchmarks of PEGASUS, including sigmoid/ReLU/min/max/division, sorting and max-pooling. To further demonstrate the capability of PEGASUS, we developed two more applications. The first one is a private decision tree evaluation whose communication cost is about two orders of magnitude smaller than the previous HE-based approaches. The second one is a secure K-means clustering that is able to run on thousands of encrypted samples in minutes that outperforms the best existing system by 14  – 20. To the best of our knowledge, this is the first work that supports practical K-means clustering using HE in a single server setting.

$P_4$-free graphs-- also known as cographs, complement-reducible graphs, or hereditary Dacey graphs--have been well studied in graph theory. We introduce the graph properties of partitioning and covering the edges of a graph with the minimum number of $P_4$-free graphs, namely, the $P_4$-free partition and $P_4$-free cover numbers. We prove that computing these numbers is \npol-complete, even for bipartite graphs. We present bipartite graph constructions where these numbers are at least ${\epsilon N^{1-2\epsilon}}$, for $\epsilon\in\{1/3,1/4,1/5,\dotsc\}$, where $N$ is the number of vertices in each partite set. Finally, we upper bound these numbers for bipartite graphs encoding well-studied Boolean functions from circuit complexity, such as set intersection, set disjointness, and inequality.

Our work encodes joint probability distributions and Boolean functions as equivalent bipartite graphs and studies the $P_4$-free partition and cover numbers of these graphs. Leveraging this connection, we present representative applications of these graph properties and their estimates to information-theory and circuit complexity. For applications in information theory, we consider a system where a setup samples from a joint distribution and gives the participants, Alice and Bob, their portion from this joint sample. The objective of Alice and Bob is to non-interactively establish a shared key and extract the left-over entropy from their portion of the samples as independent private randomness. A genie, who observes the joint sample, provides an appropriate assistance to help Alice and Bob with their objective. Lower bounds to the minimum size of the genie's assistance translates into communication and cryptographic lower bounds. We show that (the $\log_2$ of) the $P_4$-free partition number of a graph encoding the joint distribution that the setup uses is equivalent to the size of the genie's assistance. Consequently, the joint distributions corresponding to the bipartite graphs constructed above with high $P_4$-free partition number correspond to joint distributions requiring more assistance from the genie.

As a representative application in communication complexity, we study communication complexity of non-deterministic protocols augmented by access to the equality oracle at the output. We show that (the $\log_2$ of) the $P_4$-free cover number of the bipartite graph encoding a Boolean function $f$ is equivalent to the minimum size of the non-deterministic input required by the parties (referred to as the communication complexity of $f$ in this model). Consequently, the functions corresponding to the bipartite graphs with high $P_4$-free cover number have high communication complexity. Furthermore, there are functions with communication complexity close to the \naive protocol where the non-deterministic input reveals the input of a party. Finally, the access to the equality oracle reduces the communication complexity of computing set intersection and disjointness by a constant factor in contrast to the model where parties do not have access to the equality oracle. In the case of computing the inequality function, we show an exponential reduction in the communication complexity.

Contemporary libraries and frameworks that make it possible to incorporate secure multi-party computation protocols and capabilities into production software systems and applications must sometimes deliver underlying capabilities (such as logical circuit synthesis) to new kinds of environments (such as web browsers or serverless cloud computing platforms). In order to illustrate some of the benefits of addressing this challenge by building a solution from the ground up that leverages the features of a contemporary and widely used programming language, we present an embedded domain-specific language that allows programmers to describe and synthesize logical circuits. Notably, this approach allows programmers to employ many of the language features and any of the programming paradigms supported by the host language. We illustrate this flexibility by considering two use cases: synthesizing circuits for relational operations and synthesizing circuits corresponding to the SHA-256 cryptographic hash function.

Delegation of signing rights can be useful to promote effective resource sharing and smooth cooperation among participants in distributed systems, and in many situations, we often need restricted delegation such as one-timeness and unlinkability rather than simple full delegation. Particularly, one-timesness cannot be achieved just by deploying cryptographic measures, and one needs to resort to some form of tamper-proofness or the assistance from external cloud servers for ``key-disabling''. In this work, we extend the latter such that a delegatee can sign a message without the delegator's involvement with the assumption that there exists at least one honest cloud server with secure erasure to achieve one-timeness. In this setting, if the delegator just shares their signing key between the delegatee and cloud servers, it may be problematic. It is because in the worst case, the delegator cannot know whether or not a signing key theft occurred because the signatures generated illegally are indistinguishable from the ones generated legally. To solve this, first we propose an efficient one-time delegation scheme of Okamoto-Schnorr signing. Further we combine the basic delegation scheme with anonymous credentials such that the delegator can detect the signing key theft even if one-time delegation is broken while also achieving unlinkability for both the delegator and cloud servers. Further we show its application to an e-cash scheme, which can prevent double-spending.

Polynomial multiplication is one of the most costly operations of ideal lattice-based cryptosystems. In this work, we study its optimization when one of the operand has coefficients close to 0. We focus on this structure since it is at the core of lattice-based Key Exchange Mechanisms submitted to the NIST call for post-quantum cryptography. In particular, we propose optimization of this operation for embedded devices by using a RSA/ECC coprocessor that provides efficient large-integer arithmetic. In this context, we compare Kronecker Substitution, already studied by Albrecht et al. in TCHES 2019, with two specific algorithms that we introduce: KSV, a variant of this substitution, and an adaptation of the schoolbook multiplication, denoted Shift&Add. All these algorithms rely on the transformation of polynomial multiplication to large-integer arithmetic. Then, thanks to these algorithms, existing coprocessors dedicated to large-integer can be re-purposed in order to speed-up post-quantum schemes. The efficiency of these algorithms depends on the component specifications and the cryptosystem parameters set. Thus, we establish a methodology to determine which algorithm to use, for a given component, by only implementing basic large-integer operations. Moreover, the three algorithms are assessed on a chip ensuring that the theoretical methodology matches with practical results. They are also compared to reference software implementations such as NTT or schoolbook multiplication.

Second-layer or off-chain protocols increase the throughput of permissionless blockchains by enabling parties to lock funds into smart-contracts and perform payments through peer-to-peer communication, only resorting to the smart-contracts for protection against fraud. Current protocols have fixed time periods during which participants can dispute any fraud attempts. However, current blockchains have limited transaction processing capacity, so a fixed dispute period will not always be sufficient to deter all fraudulent behaviour in an off-chain protocol. In this work, we describe how to set adaptive dispute periods that accommodate the congestion and capacity of the underlying blockchain. Adaptive dispute periods ensure that users retain the opportunity to dispute fraudulent behaviours during blockchain congestion, while increasing second-layer protocol efficiency by reducing dispute period lengths when the number of disputes is low. We describe a non-interactive argument system for setting adaptive dispute periods under the current Ethereum Virtual Machine, and discuss how to efficiently integrate built-in support for adaptive dispute periods in any blockchain. We empirically demonstrate that an adaptive-dispute second-layer protocol can handle a larger number of disputes and prevent more fraud than its non-adaptive counterparts even when users are slow to issue disputes, due to denial of service or blockchain congestion.

Due to the constant increase and versatility of IoT devices that should keep sensitive information private, Side-Channel Analysis (SCA) attacks on embedded devices are gaining visibility in the industrial field. The integration and validation of countermeasures against SCA can be an expensive and cumbersome process, especially for the less experienced ones, and current certification procedures require to attack the devices under test using multiple SCA techniques and attack vectors, often implying a high degree of complexity.

The goal of this paper is to ease one of the most crucial and tedious steps of profiling attacks i.e. the points of interest (POI) selection and hence assist the SCA evaluation process. To this end, we introduce the usage of Estimation of Distribution Algorithms (EDAs) in the SCA field in order to automatically tune the point of interest selection. We showcase our approach on several experimental use cases, including attacks on unprotected and protected AES implementations over distinct copies of the same device, dismissing in this way the portability issue.

In this work we describe a token-based solution to Contact Tracing via Distributed Point Functions (DPF) and, more generally, Function Secret Sharing (FSS). The key idea behind the solution is that FSS natively supports secure keyword search on raw sets of keywords without a need for processing the keyword sets via a data structure for set membership. Furthermore, the FSS functionality enables adding up numerical payloads associated with multiple matches without additional interaction. These features make FSS an attractive tool for lightweight privacy-preserving searching on a database of tokens belonging to infected individuals.

WARP is proposed by S. Banik et al. in SAC 2020. It is a 128-bit lightweight block cipher with 128-bit key. WARP is based on 32-nibble type-2 Generalised Feistel Network (GFN). It uses permutation over nibbles designed to optimize the security and efficiency. Designers have provided a lower bound for the number of differentially active S-boxes but detailed differential characteristics are not provided. In this paper, we discuss MILP based search technique and present differential characteristics for 18-round and 19-round WARP with probability of $2^{-122}$ and $2^{-132}$ respectively. To the best of our knowledge, these detailed differential characteristics for WARP are presented for the first time.

The Advanced Encryption Standard (AES) is the most widely used symmetric encryption algorithm. Its security is mainly based on the structure of the S-box. In this paper, we present a new way to create S-boxes for AES and exhibit an S-box with improved cryptographic properties such as Bit Independence Criterion (BIC), periodicity, algebraic complexity, Strict Avalanche Criterion (SAC) and Distance to SAC.

Private Information Retrieval (PIR) hides access patterns when several clients query a database held by one or more servers. Prior PIR schemes have achieved sublinear communication and computation by leveraging computational assumptions, federating trust among many servers, relaxing security to permit differentially private leakage, refactoring effort into a pre-processing stage to reduce online costs, or amortizing costs over a large batch of queries.

In this work, we present an efficient PIR protocol that combines all of the above techniques to achieve constant amortized communication and computation complexity in the size of the database, and is the first to scale to more than $10^5$ queries per second deployed on an AWS micro instance. Our protocol also builds upon a new secret sharing scheme that is both incremental and non-malleable, which may be of interest to a wider audience. We leverage differentially private leakage in order to provide better trade-offs between privacy and efficiency. Our protocol provides security up to abort against malicious adversaries that can corrupt all but one party.