International Association
for Cryptologic Research

Proof-of-Stake (PoS) distributed ledgers are the most common alternative to Bitcoin’s Proof-of-Work (PoW) paradigm, replacing the hardware dependency with stake, i.e., assets that a party controls. Similar to PoW’s mining pools, PoS’s stake pools, i.e., collaborative entities comprising of multiple stakeholders, allow a party to earn rewards more regularly, compared to participating on an individual basis. However, stake pools tend to increase centralization, since they are typically managed by a single party that acts on behalf of the pool’s members. In this work we propose Conclave, a formal design of a Collective Stake Pool, i.e., a decentralized pool with no single point of authority. We formalize Conclave as an ideal functionality and implement it as a distributed protocol, based on standard cryptographic primitives. Among Conclave’s building blocks is a weighted threshold signature scheme (WTSS); to that end, we define a WTSS ideal functionality — which might be of independent interest — and propose two constructions based on threshold ECDSA, which enable (1) fast trustless setup and (2) identifiable aborts.

This short note shows that NTRU in NIST PQC Round~3 finalist is anonymous in the QROM if the underlying NTRU PKE is strongly disjoint-simulatable and a hybrid PKE scheme constructed from NTRU as KEM and appropriate DEM is anonymous and robust.

This solves the the open problem to investigate anonymity and robustness of NTRU posed by Grubbs, Maram, and Paterson (Cryptography ePrint Archive 2021/708).}

The Boneh-Katz transformation (CT-RSA 2005) converts a selectively-secure identity/tag-based encryption scheme into a public-key encryption scheme secure against chosen-ciphertext attacks. We show that if the underlying primitives are pseudorandom, then the public-key encryption scheme obtained by the Boneh-Katz transformation is also pseudorandom. A similar result holds for oblivious sampleability (Canetti and Fischlin (CRYPTO 2001)).

As applications, we can construct

* pseudorandom and obliviously-samplable public-key encryption schemes from lattices and codes,

* universally-composable non-interactive bit-commitment from lattices,

* public-key steganography which is steganographically secure against adaptive chosen-covertext attacks and steganographic key-exchange from lattices and codes,

* anonymous authenticated key exchange from lattices and codes,

* public-key encryption secure against simulation-based, selective-opening chosen-ciphertext attacks from lattices and codes.

Garbled circuits are a fundamental cryptographic building block to encode Boolean circuits as a sequence of encrypted values. This sequence allows two parties to securely evaluate the circuit, e.g., without revealing their respective inputs. At the heart of any garbling scheme lies a randomized algorithm projecting the plain values into a larger domain. Emerging from a large body of work, the common paradigm meets two implicit properties: the circuit is garbled progressively gate-wise; and all underlying algorithms are linear. In this setting, the communication complexity is measured in the number of sent ciphertexts and shown to be optimal with a scheme sending two ciphertexts per AND gate and no ciphertexts per XOR gate (Zahur, Rosulek and Evans, Eurocrypt'15).

We revisit the common paradigm and extend the seminal work of Bellare, Hoang, and Rogaway from CCS 2012 to present for the first time an abstraction of the garbling algorithm itself. This abstraction highlights how Yao's work (Yao, FOCS'86) and all its optimizations focused on improving just one aspect of the garbling. We then discuss how improving the other aspects could provide new ways to overcome the limitations of existing schemes. As a proof of concept we present a non-bijective scheme avoiding Zahur et al.'s bound, achieving a communication complexity of a single data item which is not a ciphertext.

The existence of one-way functions implies secure digital signatures, but not public-key encryption (at least in a black-box setting). Somewhat surprisingly, though, efficient public-key encryption schemes appear to be much easier to construct from concrete algebraic assumptions (such as the factoring of Diffie-Hellman-like assumptions) than efficient digital signature schemes. In this work, we provide one reason for this apparent difficulty to construct efficient signature schemes.

Specifically, we prove that a wide range of algebraic signature schemes (in which verification essentially checks a number of linear equations over a group) fall to conceptually surprisingly simple linear algebra attacks. In fact, we prove that in an algebraic signature scheme, sufficiently many signatures can be linearly combined to a signature of a fresh message. We present attacks both in known-order and hidden-order groups (although in hidden-order settings, we have to restrict our definition of algebraic signatures a little). More explicitly, we show: - the insecurity of all signature schemes in Maurer's generic group model (in pairing-free groups), as long as the signature schemes do not rely on other cryptographic assumptions, such as hash functions. - the insecurity of a natural class of signatures in hidden-order groups, where verification consists of linear equations over group elements.

We believe that this highlights the crucial role of public verifiability in digital signature schemes. Namely, while public-key encryption schemes do not require any publicly verifiable structure on ciphertexts, it is exactly this structure on signatures that invites attacks like ours and makes it hard to construct efficient signatures.

GIFT-COFB is a finalist of NIST Lightweight cryptography project that aims at standardizing authenticated encryption schemes for constrained devices. It is a block cipher-based scheme and comes with a provable security result. This paper studies the tightness of the provable security bounds of GIFT-COFB, which roughly tells that, if instantiated by a secure $n$-bit block cipher, we need $2^{n/2}$ encrypted blocks or $2^{n/2}/n$ decryption queries to break the scheme. This paper shows that the former condition is indeed tight, by presenting forgery attacks that work with $2^{n/2}$ encrypted blocks with single decryption query. This fills the missing spot of previous attacks presented by Khairallah, and confirms the tightness of the security bounds with respect to encryption. We remark that our attacks work independent of the underlying block cipher.

Machine Learning (ML) algorithms, especially deep neural networks (DNN), have proven themselves to be extremely useful tools for data analysis, and are increasingly being deployed in systems operating on sensitive data, such as recommendation systems, banking fraud detection, and healthcare systems. This underscores the need for privacy-preserving ML (PPML) systems, and has inspired a line of research into how such systems can be constructed efficiently. We contribute to this line of research by proposing a framework that allows efficient and secure evaluation of full-fledged state-of-the-art ML algorithms via secure multi-party computation (MPC). This is in contrast to most prior works on PPML, which require advanced ML algorithms to be substituted with approximated variants that are ``MPC-friendly'', before MPC techniques are applied to obtain a PPML algorithm. A drawback of the latter approach is that it requires careful fine-tuning of the combined ML and MPC algorithms, and might lead to less efficient algorithms or inferior quality ML (such as lower prediction accuracy). This is an issue for secure training of DNNs in particular, as this involves several arithmetic algorithms that are thought to be ``MPC-unfriendly'', namely, integer division, exponentiation, inversion, and square root extraction.

In this work, we propose secure and efficient protocols for the above seemingly MPC-unfriendly computations (but which are essential to DNN). Our protocols are three-party protocols in the honest-majority setting, and we propose both passively secure and actively secure with abort variants. A notable feature of our protocols is that they simultaneously provide high accuracy and efficiency. This framework enables us to efficiently and securely compute modern ML algorithms such as Adam (Adaptive moment estimation) and the softmax function ``as is'', without resorting to approximations. As a result, we obtain secure DNN training that outperforms state-of-the-art three-party systems; our \textit{full} training is up to $6.7$ times faster than just the \textit{online} phase of the recently proposed FALCON (Wagh et al. at PETS'21) on the standard benchmark network for secure training of DNNs. To further demonstrate the scalability of our protocols, we perform measurements on real-world DNNs, AlexNet and VGG16, which are complex networks containing millions of parameters. The performance of our framework for these networks is up to a factor of about $12\sim 14$ faster for AlexNet and $46\sim 48$ faster for VGG16 to achieve an accuracy of $70\%$ and $75\%$, respectively, when compared to FALCON.

We study masking countermeasures for side-channel attacks against signature schemes constructed from the MPC-in-the-head paradigm, specifically when the MPC protocol uses preprocessing. This class of signature schemes includes Picnic, an alternate candidate in the third round of the NIST post-quantum standardization project. The only previously known approach to masking MPC-in-the-head signatures suffers from interoperability issues and increased signature sizes. Further, we present a new attack to demonstrate that known countermeasures are not sufficient when the MPC protocol uses a preprocessing phase, as in Picnic3.

We overcome these challenges by showing how to mask the underlying zero-knowledge proof system due to Katz–Kolesnikov–Wang (CCS 2018) for any masking order, and by formally proving that our approach meets the standard security notions of non-interference for masking countermeasures. As a case study, we apply our masking technique to Picnic. We then implement different masked versions of Picnic signing providing first order protection for the ARM Cortex M4 platform, and quantify the overhead of these different masking approaches. We carefully analyze the side-channel risk of hashing operations, and give optimizations that reduce the CPU cost of protecting hashing in Picnic by a factor of five. The performance penalties of the masking countermeasures ranged from 1.8 to 5.5, depending on the degree of masking applied to hash function invocations.

We provide three first-order sharings of the AES each allowing for a different trade-off between the number of shares and the number of register stages. All sharings use a generalization of the changing of the guards method by allowing randomness to be used in the shared S-box. As a result, the sharings have minimal randomness requirements. The sharings are written out in detail to ease implementation efforts.

We present a framework GenoPPML for privacy-preserving machine learning in the context of sensitive genomic data processing. The technology combines secure multiparty computation techniques based on the recently proposed Manticore secure multiparty computation framework for model training and fully homomorphic encryption based on TFHE for model inference. The framework was successfully used to solve breast cancer prediction problems on gene expression datasets coming from distinct private sources while preserving their privacy – the solution winning 1st place for both Tracks I and III of the genomic privacy competition iDASH'2020.

In this paper, we present preimage attacks on 4-round Keccak-224/256 as well as 4-round Keccak[$r = 640,c = 160,l = 80$] in the preimage challenges. We revisit the Crossbred algorithm for solving the Boolean multivariate quadratic (MQ) system, propose a new view for the case $D = 2$ and elaborate the computational complexity. The result shows that the Crossbred algorithm outperforms brute force theoretically and practically with feasible memory costs. In our attacks, we construct Boolean MQ systems in order to make full use of variables. With the help of solving MQ systems, we successfully improve preimage attacks on Keccak-224/256 reduced to 4 rounds. Moreover, we implement the preimage attack on 4-round Keccak[$r = 640,c = 160,l = 80$], an instance in the Keccak preimage challenges, and find 78-bit matched \textit{near preimages}. Due to the fundamental rule of solving MQ systems, the complexity elaboration of Crossbred algorithm is of independent interest.

The idea of hybrid homomorphic encryption (HHE) is to drastically reduce bandwidth requirements when using homomorphic encryption (HE) at the cost of more expensive computations in the encrypted domain. To this end, various dedicated schemes for symmetric encryption have already been proposed. However it is still unclear if those ideas are already practically useful, because (1) no cost-benefit analysis was done for use cases and (2) very few implementations are publicly available. We address this situation in several ways. After we formally define HHE in a broader sense than before, we build an open-source benchmarking framework involving several use cases covering three popular libraries. Using this framework, we explore properties of the respective HHE proposals. It turns out that even medium-sized use cases are infeasible, especially when involving integer arithmetic. Consequently, we propose Pasta, a cipher thoroughly optimized for integer HHE use cases. Pasta is designed to minimize the multiplicative depth, while also leveraging the structure of both state-of-the-art integer HE schemes (BFV and BGV) to minimize the homomorphic evaluation latency. Using our new benchmarking environment, we extensively evaluate Pasta in SEAL and HElib and compare its properties to 7 existing ciphers in two use cases. Our evaluations show that Pasta outperforms its competitors for HHE both in terms of homomorphic evaluation time and noise consumption, showing its efficiency for applications in real-world HE use cases. Concretely, Pasta outperforms Agrasta by a factor of up to 82 and Masta by a factor of up to 6 when applied to the two use cases.

Event date: 29 September to 1 October 2021
Submission deadline: 30 June 2021

We are seeking a Postdoctoral Researcher to join us in our project to ensure reliable and trustworthy power grid operation. In this project, we will approach the security challenges from three angles; secure energy transactions, secure decentralized storage for collaboration, and secure end-to-end communication for resource monitoring and control.

Your Responsibilities

• Conduct research on provable data possession and secure collaborative storage.
• Develop and improve upon techniques to provide Completeness, Correctness, and Freshness guarantees on stored data in collaborative applications.
• Implement the developed solutions

Basic Requirements

• PhD in Cryptography, Applied Cryptography, Information Theory, Mathematics, Computer Science or related areas.
• Excellent track record in reputable Cryptography and Security venues.
• Ability to perform research independently.
• Good communication skills and ability to collaborate with a team of researchers and engineers.
• Experience or interest in software prototyping.

Nice to Have

• Experience in data/message integrity research, such as Provable Data Possession, Proof of Data Retrievability.
• Familiar with or interested in Cloud and IoT concepts, DER and Grid 2.0 paradigm.

For more information, please visit ADSC's website: http://adsc.illinois.edu/.

Closing date for applications:

Contact: Interested candidates should apply online at https://my.engr.illinois.edu/apply/.

Applications are invited for a postdoctoral research position in “distributed cryptography,” a term we broadly use to encompass areas such as secure multiparty computation, cryptographic protocols, foundational aspects of blockchains, and their relation thereof. Applicants are expected to hold a PhD in computer science or related field, and must have published papers in cryptography and/or distributed computing venues. The position will be available starting in the Fall 2021, and remain open until filled. The postdoctoral researcher will have a joint appointment at Purdue University and Texas A&M University.

Closing date for applications:

Contact: To apply, please send an email, including your CV, to Juan Garay (garay@tamu.edu) and Vassilis Zikas (vzikas@cs.purdue.edu)

Ockam is designing open source protocols and libraries for end-to-end encrypted communication within IoT and other connected systems. In this role, you will be responsible for the architecture and design of cryptographic protocols within Ockam. Our goal is to make our cryptographic libraries easy to use correctly and hard to misuse, you will lead the design of these library APIs in Rust. This is an applied cryptography role which will involve researching and applying robust, peer reviewed, cryptographic primitives to the design of our protocols. The role will also involve implementing cryptographic primitives and protocols in Rust. You will also get to work with Rust FFI and our C and Elixir libraries. You'll have the chance to design protocols for - Secure Channels, Authenticated Key-Exchange, Anonymous Credentials, Key lifecycle, Authentication, Authorization etc. Interesting cryptographic building blocks that you would get to dive deep into and apply to real-world problems will include - Bi-linear parings, Zero knowledge proofs, Noise Framework, Sigma Protocols, Signature schemes like BBS+, Secure Multi Party Computation etc. Ockam is a small and extremely senior team. This role involves architecture, interface design, writing code, responsibility for testing, and publishing documentation.

Closing date for applications:

Contact: Ockam.io

More information: https://www.ockam.io/team/Applied-Cryptographer-Rust/61e07e82-0589-51de-b250-42dbceb31c3c

Recent progress in interactive zero-knowledge (ZK) proofs has improved the efficiency of proving large-scale computations significantly. Nevertheless, real-life applications (e.g., in the context of private inference using deep neural networks) often involve highly complex computations, and existing ZK protocols lack the expressiveness and scalability to prove results about such computations efficiently.

In this paper, we design, develop, and evaluate a ZK system (Mystique) that allows for efficient conversions between arithmetic and Boolean values, between publicly committed and privately authenticated values, and between fixed-point and floating-point numbers. Targeting large-scale neural-network inference, we also present an improved ZK protocol for matrix multiplication that yields a 7× improvement compared to the state-of-the-art. Finally, we incorporate Mystique in Rosetta, a TensorFlow-based privacy-preserving framework.

Mystique is able to prove correctness of an inference on a private image using a committed (private) ResNet-101 model in 28 minutes, and can do the same task when the model is public in 5 minutes, with only a 0.02% decrease in accuracy compared to a non-ZK execution when testing on the CIFAR-10 dataset. Our system is the first to support ZK proofs about neural-network models with over 100 layers with virtually no loss of accuracy.

Fully Homomorphic Encryption (FHE) schemes enable to compute over encrypted data. Among them, TFHE [CGGI17] has the great advantage of offering an efficient method for bootstrapping noisy ciphertexts, i.e., reduce the noise. Indeed, homomorphic computation increases the noise in ciphertexts and might compromise the encrypted message. TFHE bootstrapping, in addition to reducing the noise, also evaluates (for free) univariate functions expressed as look-up tables. It however requires to have the most significant bit of the plaintext to be known a priori, resulting in the loss of one bit of space to store messages. Furthermore it represents a non negligible overhead in terms of computation in many use cases.

In this paper, we propose a solution to overcome this limitation, that we call Programmable Bootstrapping Without Padding (WoP-PBS). This approach relies on two building blocks. The first one is the multiplication à la BFV [FV12] that we incorporate into TFHE. This is possible thanks to a thorough noise analysis showing that correct multiplications can be computed using practical TFHE parameters. The second building block is the generalization of TFHE bootstrapping introduced in this paper. It offers the flexibility to select any chunk of bits in an encrypted plaintext during a bootstrap. It also enables to evaluate many LUTs at the same time when working with small enough precision. All these improvements are particularly helpful in some applications such as the evaluation of Boolean circuits (where a bootstrap is no longer required in each evaluated gate) and, more generally, in the efficient evaluation of arithmetic circuits even with large integers. Those results improve TFHE circuit bootstrapping as well. Moreover, we show that bootstrapping large precision integers is now possible using much smaller parameters than those obtained by scaling TFHE ones.

Consider a server with a large set $S$ of strings $\{x_1,x_2, \dots,x_N\}$ that would like to publish a small hash $h$ of its set $S$ such that any client with a string $y$ can send the server a short message allowing it to learn $y$ if $y \in S$ and nothing otherwise. In this work, we study this problem of two-round private set intersection (PSI) with low (asymptotically optimal) communication cost, or what we call laconic private set intersection ($\ell$PSI) and its extensions. This problem is inspired by the recent general frameworks for laconic cryptography [Cho et al. CRYPTO 2017, Quach et al. FOCS'18].

We start by showing the first feasibility result for realizing $\ell$PSI based on the CDH assumption, or LWE with polynomial noise-to-modulus ratio. However, these feasibility results use expensive non-black-box cryptographic techniques leading to significant inefficiency. Next, with the goal of avoiding these inefficient techniques, we give a construction of $\ell$PSI schemes making only black-box use of cryptographic functions. Our construction is secure against semi-honest receivers, malicious senders and reusable in the sense that the receiver's message can be reused across any number of executions of the protocol. The scheme is secure under the $\phi$-hiding, decisional composite residuosity and subgroup decision assumptions.

Finally, we show natural applications of $\ell$PSI to realizing a semantically-secure encryption scheme that supports detection of encrypted messages belonging to a set of ``illegal'' messages (e.g., an illegal video) circulating online. Over the past few years, significant effort has gone into realizing laconic cryptographic protocols. Nonetheless, our work provides the first black-box constructions of such protocols for a natural application setting.

Cryptocurrency and blockchain continue to build on an innovative computation model that has paved the way for a large variety of applications. However, privacy is a huge concern as most (permissionless) blockchains log everything in the clear. This has resulted in several academic and industrial initiatives to address privacy. Starting with the UTXO model introduced by Bitcoin, initial works brought confidentiality and anonymity to payments. Recent works have expanded to support more generalized forms of private computation. Such solutions tend to be highly involved as they rely on advanced cryptographic primitives and creative techniques to handle issues related to dealing with private blockchain records (e.g. concurrency, private coin tracking to prevent double spending, efficiency). This situation makes it hard to comprehend the current state-of-the-art, much less build on top of it.

To address these challenges, we provide a systematization of knowledge for privacy-preserving solutions in blockchain. To the best of our knowledge, our work is the first of its kind. After motivating design challenges, we provide an overview of the zero-knowledge proof systems used in supporting blockchain privacy, focusing on their key features and limitations. Then, we develop a systematization of knowledge framework using which we group the state-of-the-art privacy preserving solutions under three categories: private payments, computation with input/output privacy, and function privacy. We briefly touch upon challenges and implications including misuse, regulations and compliance, usability, and limited functionality. Our work seeks to highlight open problems and research questions to guide future work directions.