Last Week's ePrint Updates

Sat, 16 Oct 2021 12:17PM
Aardvark: An Asynchronous Authenticated Dictionary with Applications to Account-based Cryptocurrencies
Derek Leung, Yossi Gilad, Sergey Gorbunov, Leonid Reyzin, Nickolai Zeldovich
applications / vector-commitments, authenticated-data-structures, cryptocurrencies

We design Aardvark, a novel authenticated dictionary with short proofs of correctness for lookups and modifications. Our design reduces storage requirements for transaction validation in cryptocurrencies by outsourcing data from validators to untrusted servers, which supply proofs of correctness of this data as needed. In this setting, short proofs are particularly important because proofs are distributed to many validators, and the transmission of long proofs can easily dominate costs. A proof for a piece of data in an authenticated dictionary may change whenever any (even unrelated) data changes. This presents a problem for concurrent issuance of cryptocurrency transactions, as proofs become stale. To solve this problem, Aardvark employs a versioning mechanism to safely accept stale proofs for a limited time. On a dictionary with 100 million keys, operation proof sizes are about 1KB in a Merkle Tree versus 100–200B in Aardvark. Our evaluation shows that a 32-core validator processes 1492– 2941 operations per second, saving about 800× in storage costs relative to maintaining the entire state.

Sat, 16 Oct 2021 02:54PM
On the security of ECDSA with additive key derivation and presignatures
Jens Groth, Victor Shoup
public-key cryptography / ECDSA

Two common variations of ECDSA signatures are additive key derivation and presignatures. Additive key derivation is a simple mechanism for deriving many subkeys from a single master key, and is already widely used in cryptocurrency applications with the Hierarchical Deterministic Wallet mechanism standardized in Bitcoin Improvement Proposal 32 (BIP32). Because of its linear nature, additive key derivation is also amenable to efficient implementation in the threshold setting. With presignatures, the secret and public nonces used in the ECDSA signing algorithm are precomputed. In the threshold setting, using presignatures along with other precomputed data allows for an extremely efficient ``online phase'' of the protocol. Recent works have advocated for both of these variations, sometimes combined together. However, somewhat surprisingly, we are aware of no prior security proofs of either of these variations in isolation, let alone in combination with one another. In this paper, we provide a thorough analysis of these variations, both in isolation and in combination. Our analysis is in the generic group model (GGM). Importantly, we do not modify ECDSA or weaken the standard notion of security in any way. Of independent interest, we also present a version of the GGM that is specific to elliptic curves. This EC-GGM better models some of the idiosyncrasies (such as the conversion function and malleability) of ECDSA. In addition to this analysis, we report security weaknesses in these variations that apparently have not been previously reported. For example, we show that when both variations are combined, there is a cube-root attack on ECDSA, which is much faster than the best known, square-root attack on plain ECDSA. We also present two mitigations against these weaknesses: re-randomized presignatures and homogeneous key derivation. Each of these mitigations is very lightweight, and when used in combination, the security is essentially the same as that of plain ECDSA (in the EC-GGM).

Sat, 16 Oct 2021 08:04PM
Disappearing Cryptography in the Bounded Storage Model
Jiaxin Guan, Mark Zhandry
foundations / Bounded Storage Model, Obfuscation, Constructions

In this work, we study disappearing cryptography in the bounded storage model. Here, a component of the transmission, say a ciphertext, a digital signature, or even a program, is streamed bit by bit. The stream is too large for anyone to store in its entirety, meaning the transmission effectively disappears once the stream stops. We first propose the notion of online obfuscation, capturing the goal of disappearing programs in the bounded storage model. We give a negative result for VBB security in this model, but propose candidate constructions for a weaker security goal, namely VGB security. We then demonstrate the utility of VGB online obfuscation, showing that it can be used to generate disappearing ciphertexts and signatures. All of our applications are not possible in the standard model of cryptography, regardless of computational assumptions used.

Sun, 17 Oct 2021 12:28AM
Privacy-Preserving COVID-19 Contact Tracing App: A Zero-Knowledge Proof Approach
Joseph K. Liu, Man Ho Au, Tsz Hon Yuen, Cong Zuo, Jiawei Wang, Amin Sakzad, Xiapu Luo, Li Li, Kim-Kwang Raymond Choo
applications / COVID-19, Zero-knowledge proof

In this paper, we propose a privacy-preserving contact tracing protocol for smart phones, and more specifically Android and iOS phones. The protocol allows users to be notified, if they have been a close contact of a confirmed patient. The protocol is designed to strike a balance between privacy, security, and scalability. Specifically, the app allows all users to hide their past location(s) and contact history from the Government, without affecting their ability to determine whether they have close contact with a confirmed patient whose identity will not be revealed. A zero-knowledge protocol is used to achieve such a user privacy functionality. In terms of security, no user can send fake messages to the system to launch a false positive attack. We present a security model and formally prove the security of the protocol. To demonstrate scalability, we evaluate an Android and an iOS implementation of our protocol. A comparative summary shows that our protocol is the most comprehensive and balanced privacy-preserving contact tracing solution to-date.

Sun, 17 Oct 2021 04:07AM
Hybrid Steganography deployed in hospitals for compression of medical images
Avinash Vijayarangan, K.R. Sekar, R. Srikanth
applications / Big medical Data, Data Security, Knight Tour, Steganography, Discrete Wavelet Transform and Lossless Image Compression

With the fast-growing technology and emerging innovations in the research arena, privacy and preservation of data predominantly in the medical field are highly essential. At the same time, there is a need for minimized storage of voluminous data in the medical repository. The inspiration for this research work to formulate the hybrid methodologies using improved Steganography, wavelet transform, and lossless compression for privacy and preservation of medical big data images and patient information in the medical big data repositories. The novelty of the work focuses on the preservation of patient’s information using enhanced security and optimized big data image storage, which helps the pharmacology professionals to store double the amount of information in the same storage space of the medical big data repository. The secure storage, fast retrieval of image, and minimum computation are the basic ideology of the work. The research work adopts a fast and optimized approach of the Knight Tour algorithm for embedding the patient’s data in their medical image and a Discrete Wavelet Transform (DWT) for the safeguarding of the cover image. Furthermore, a lossless wavelet packet compression is applied to minimize the storage size and to maximize storage efficiency. The outcome of the work achieves a higher level of data security without loss in the quality of the image. In addition, the preservation of the reduced size image will be easy to accommodate and can store bountiful images in the repository. A proposed hybrid method of compression in order to get high resolution on spatial and frequency domains will provide an edge.

Sun, 17 Oct 2021 09:42AM
Rinocchio: SNARKs for Ring Arithmetic
Chaya Ganesh, Anca Nitulescu, Eduardo Soria-Vazquez
cryptographic protocols / Proofs and Arguments, SNARKs, Ring Arithmetic, Galois Rings, Zero Knowledge

Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive efficient verification of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be efficiently represented as either Boolean or arithmetic circuits over finite fields. For most constructions, the choice of the prime field $\mathbb{F}_p$ is limited by the existence of groups of matching order for which secure bilinear maps exist. In this work we overcome such restrictions and enable verifying computations over rings. We construct the first designated-verifier SNARK for statements which are represented as circuits over a broader kind of commutative rings, namely those containing big enough exceptional sets. Exceptional sets consist of elements such that their pairwise differences are invertible. Our contribution is threefold: We first introduce Quadratic Ring Programs (QRPs) as a characterization of NP where the arithmetic is over a ring. Second, inspired by the framework in Gennaro, Gentry, Parno and Raykova (EUROCRYPT 2013), we design SNARKs over rings in a modular way. We generalize pre-existent assumptions employed in field-restricted SNARKs to encoding schemes over rings. As our encoding notion is generic in the choice of the ring, it is amenable to different settings. Finally, we propose two applications for our SNARKs. Our first application is verifiable computation over encrypted data, specifically for evaluations of Ring- LWE-based homomorphic encryption schemes. In the second one, we use Rinocchio to naturally prove statements about circuits over e.g. $\mathbb{Z}_{2^{64}}$, which closely matches real-life computer architectures such as standard CPUs.

Mon, 18 Oct 2021 12:58AM
Asymptotically-Good Arithmetic Secret Sharing over Z/(p^\ell Z) with Strong Multiplication and Its Applications to Efficient MPC
Ronald Cramer, Matthieu Rambaud, Chaoping Xing
foundations / cryptographic protocols

This paper studies information-theoretically secure multiparty computation (MPC) over rings $\Z/p^{\ell}\Z$. In the work of [TCC'19], a protocol based on the Shamir secret sharing over $\Z/p^{\ell}\Z$ was presented. As in the field case, its limitation is that the share size grows as the number of players increases. Then several MPC protocols were developed in [Asiacrypt'20] to overcome this limitation. However, (i) their offline multiplication gate has super-linear communication complexity in the number of players; (ii) the share size is doubled for the most important case, namely over $\Z/2^{\ell}\Z$ due to infeasible lifting of self-orthogonal codes from fields to rings; (iii) most importantly, the BGW model could not be applied via the secret sharing given in [Asiacrypt'20] due to lack of strong multiplication. In this paper we overcome all the drawbacks mentioned above. Of independent interest, we establish an arithmetic secret sharing with strong multiplication, which is the most important primitive in the BGW model. Of independent interest, the new multiplicative triples check, which we introduce for (i), has better asymptotic complexity than the one of [Crypto'20], both in the particular case of finite fields and when lifted over rings $\Z/p^{\ell}\Z$. Finally, we lift Reverse Multiplication Friendly Embeddings (RMFE) from fields to rings, with same (linear) complexity. Note that RMFE has become a standard amortization technique for communication complexity in MPC in the regime over many instances of the same circuit, as in \cite[Crypto'18] and [Crypto'19]. We can thus compile existing MPC protocols over fields, including [EC'21], into ones over rings $\Z/2^{\ell}\Z$ with same complexity. To obtain our theoretical results, we use the existence of lifts of curves over rings, then use the known results stating that Riemann-Roch spaces are free modules. To make our scheme practical, we start from good algebraic geometry codes over finite fields obtained from existing computational techniques. Then we present, and implement, an efficient algorithm to Hensel-lift the generating matrix of the code, such that the multiplicative conditions are preserved over rings. On the other hand, a random lifting of codes over rings does not preserve multiplicativity in general. Finally we provide efficient methods for sharing and reconstruction over rings.

Mon, 18 Oct 2021 06:12AM
Homomorphic Secret Sharing for Multipartite and General Adversary Structures Supporting Parallel Evaluation of Low-degree Polynomials
Reo Eriguchi, Koji Nuida
foundations / Homomorphic secret sharing, General adversary structure, Parallel evaluation

Homomorphic secret sharing (HSS) for a function $f$ allows input parties to distribute shares for their private inputs and then locally compute output shares from which the value of $f$ is recovered. HSS can be directly used to obtain a two-round multiparty computation (MPC) protocol for possibly non-threshold adversary structures whose communication complexity is independent of the size of $f$. In this paper, we propose two constructions of HSS schemes supporting parallel evaluation of a single low-degree polynomial and tolerating multipartite and general adversary structures. Our multipartite scheme tolerates a wider class of adversary structures than the previous multipartite one in the particular case of a single evaluation and has exponentially smaller share size than the general construction. While restricting the range of tolerable adversary structures (but still applicable to non-threshold ones), our schemes perform $\ell$ parallel evaluations with communication complexity approximately $\ell/\log\ell$ times smaller than simply using $\ell$ independent instances. We also formalize two classes of adversary structures taking into account real-world situations to which the previous threshold schemes are inapplicable. Our schemes then perform $O(m)$ parallel evaluations with almost the same communication cost as a single evaluation, where $m$ is the number of parties.

Mon, 18 Oct 2021 06:12AM
NTT software optimization using an extended Harvey butterfly
Jonathan Bradbury, Nir Drucker, Marius Hillenbrand
implementation / Number Theoretic Transform, Software optimization, IBM Z^(R) systems, Homomorphic Encryption, Intel's AVX512-IFMA

Software implementations of the number-theoretic transform (NTT) method often leverage Harvey’s butterfly to gain speedups. This is the case in cryptographic libraries such as IBM’s HElib, Microsoft’s SEAL, and Intel’s HEXL, which provide optimized implementations of fully homomorphic encryption schemes or their primitives. We extend the Harvey butterfly to the radix-4 case for primes in the range [2^31, 2^52). This enables us to use the vector multiply sum logical (VMSL) instruction, which is available on recent IBM Z^(R) platforms. On an IBM z14 system, our implementation performs more than 2.5x faster than the scalar implementation of SEAL we converted to native C. In addition, we implemented a mixed-radix implementation that uses AVX512-IFMA on Intel’s Ice Lake processor, which happens to be ~1.1 times faster than the super-optimized implementation of Intel’s HEXL. Finally, we compare the performance of some of our implementation using GCC versus Clang compilers and discuss the results.

Mon, 18 Oct 2021 06:13AM
Iterated Inhomogeneous Polynomials
Jiaxin Guan, Mark Zhandry
foundations / foundations

Let $p$ be a polynomial, and let $p^{(i)}(x)$ be the result of iterating the polynomial $i$ times, starting at an input $x$. The case where $p(x)$ is the homogeneous polynomial $x^2$ has been extensively studied in cryptography. Due to its associated group structure, iterating this polynomial gives rise to a number of interesting cryptographic applications such as time-lock puzzles and verifiable delay functions. On the other hand, the associated group structure leads to quantum attacks on the applications. In this work, we consider whether inhomogeneous polynomials, such as $2x^2+3x+1$, can have useful cryptographic applications. We focus on the case of polynomials mod $2^n$, due to some useful mathematical properties. The natural group structure no longer exists, so the quantum attacks but also applications no longer immediately apply. We nevertheless show classical polynomial-time attacks on analogs of hard problems from the homogeneous setting. We conclude by proposing new computational assumptions relating to these inhomogeneous polynomials, with cryptographic applications.

Mon, 18 Oct 2021 06:14AM
HIDE & SEEK: Privacy-Preserving Rebalancing on Payment Channel Networks
Zeta Avarikioti, Krzysztof Pietrzak, Iosif Salem, Stefan Schmid, Samarth Tiwari, Michelle Yeo
applications / Payment Channel Networks, Privacy, and Rebalancing.

Payment channels effectively move the transaction load off-chain thereby successfully addressing the inherent scalability problem most cryptocurrencies face. A major drawback of payment channels is the need to ``top up'' funds on-chain when a channel is depleted. Rebalancing was proposed to alleviate this issue, where parties with depleting channels move their funds along a cycle to replenish their channels off-chain. Protocols for rebalancing so far either introduce local solutions or compromise privacy. In this work, we present an opt-in rebalancing protocol that is both private and globally optimal, meaning our protocol maximizes the total amount of rebalanced funds. We study rebalancing from the framework of linear programming. To obtain full privacy guarantees, we leverage multi-party computation in solving the linear program, which is executed by selected participants to maintain efficiency. Finally, we efficiently decompose the rebalancing solution into incentive-compatible cycles which conserve user balances when executed atomically.

Mon, 18 Oct 2021 06:16AM
Guide to Fully Homomorphic Encryption over the [Discretized] Torus
Marc Joye
implementation / FHE, TFHE, LWE, Discretized torus, Programmable bootstrapping

First posed as a challenge in 1978 by Rivest et al., fully homomorphic encryption—the ability to evaluate any function over encrypted data— was only solved in 2009 in a breakthrough result by Gentry. After a decade of intense research, practical solutions have emerged and are being pushed for standardization. This guide is intended to practitioners. It explains the inner-workings of TFHE, a torus-based fully homomorphic encryption scheme. More exactly, it describes its implementation on a discretized version of the torus. It also explains in detail the technique of the programmable bootstrapping.

Mon, 18 Oct 2021 06:17AM
Efficient Adaptively-Secure Byzantine Agreement for Long Messages
Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, Kartik Nayak
cryptographic protocols / Byzantine agreement, blockchain, communication complexity

We investigate the communication complexity of Byzantine agreement protocols for long messages against an adaptive adversary. In this setting, prior results either achieved a communication complexity of $O(nl\cdot\poly(\kappa))$ or $O(nl + n^2 \cdot \poly(\kappa))$ for $l$-bit long messages. We improve the state of the art by presenting protocols with communication complexity $O(nl + n \cdot \poly(\kappa))$ in both the synchronous and asynchronous communication models. The synchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{2}$ corruptions and assumes a VRF setup, while the asynchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{3}$ corruptions under further cryptographic assumptions. Our protocols are very simple and combine subcommittee election with the recent approach of Nayak et al. (DISC `20). Surprisingly, the analysis of our protocols is \emph{all but simple} and involves an interesting new application of Mc Diarmid's inequality to obtain {\em optimal} corruption thresholds.

Mon, 18 Oct 2021 06:17AM
Non-interactive Distributional Indistinguishability (NIDI) and Non-Malleable Commitments
Dakshita Khurana
foundations / zero knowledge

We introduce non-interactive distributionally indistinguishable arguments (NIDI) to address a significant weakness of NIWI proofs: namely, the lack of meaningful secrecy when proving statements about $\mathsf{NP}$ languages with unique witnesses. NIDI arguments allow a prover P to send a single message to verifier V, given which V obtains a sample d from a (secret) distribution D, together with a proof of membership of d in an NP language L. The soundness guarantee is that if the sample d obtained by the verifier V is not in L, then V outputs $\bot$. The privacy guarantee is that secrets about the distribution remain hidden: for every pair of distributions $D_0$ and $D_1$ of instance-witness pairs in L such that instances sampled according to $D_0$ or $D_1$ are (sufficiently) hard-to-distinguish, a NIDI that outputs instances according to $D_0$ with proofs of membership in L is indistinguishable from one that outputs instances according to $D_1$ with proofs of membership in L. - We build NIDI arguments for sufficiently hard-to-distinguish distributions assuming sub-exponential indistinguishability obfuscation and sub-exponential one-way functions. - We demonstrate preliminary applications of NIDI and of our techniques to obtaining the first (relaxed) non-interactive constructions in the plain model, from well-founded assumptions, of: 1. Commit-and-prove that provably hides the committed message 2. CCA-secure commitments against non-uniform adversaries. The commit phase of our commitment schemes consists of a single message from the committer to the receiver, followed by a randomized output by the receiver (that need not necessarily be returned to the committer).

Mon, 18 Oct 2021 06:36AM
Compact and Malicious Private Set Intersection for Small Sets
Mike Rosulek, Ni Trieu
cryptographic protocols / private set intersection

We describe a protocol for two-party private set intersection (PSI) based on Diffie-Hellman key agreement. The protocol is proven secure against malicious parties, in the ideal permutation + random oracle model. For small sets (500 items or fewer), our protocol requires the least time and communication of any known PSI protocol, even ones that are only semi-honest secure and ones that are not based on Diffie-Hellman. It is one of the few significant improvements to the 20-year old classical Diffie-Hellman PSI protocol of Huberman, Franklin, and Hogg (ACM Elec. Commerce 1999). Our protocol is actually a generic transformation that constructs PSI from a class of key agreement protocols. This transformation is inspired by a technique of Cho, Dachman-Soled, and Jarecki (CT-RSA 2016), which we streamline and optimize in several important ways to achieve our superior efficiency.

Mon, 18 Oct 2021 07:37AM
First-Order Hardware Sharings of the AES
Siemen Dhooghe, Svetla Nikova, Vincent Rijmen
implementation / AES, DPA, Hardware, Probing Security, Threshold Implementations

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.

Mon, 18 Oct 2021 01:42PM
Efficient Perfectly Secure Computation with Optimal Resilience
Ittai Abraham, Gilad Asharov, Avishay Yanai
Perfect Security, Secure Computation

Secure computation enables $n$ mutually distrustful parties to compute a function over their private inputs jointly. In 1988 Ben-Or, Goldwasser, and Wigderson (BGW) demonstrated that any function can be computed with perfect security in the presence of a malicious adversary corrupting at most $t< n/3$ parties. After more than 30 years, protocols with perfect malicious security, with round complexity proportional to the circuit's depth, still require sharing a total of $O(n^2)$ values per multiplication. In contrast, only $O(n)$ values need to be shared per multiplication to achieve semi-honest security. Indeed sharing $\Omega(n)$ values for a single multiplication seems to be the natural barrier for polynomial secret sharing-based multiplication. In this paper, we close this gap by constructing a new secure computation protocol with perfect, optimal resilience and malicious security that incurs sharing of only $O(n)$ values per multiplication, thus, matching the semi-honest setting for protocols with round complexity that is proportional to the circuit depth. Our protocol requires a constant number of rounds per multiplication. Like BGW, it has an overall round complexity that is proportional only to the multiplicative depth of the circuit. Our improvement is obtained by a novel construction for {\em weak VSS for polynomials of degree-$2t$}, which incurs the same communication and round complexities as the state-of-the-art constructions for {\em VSS for polynomials of degree-$t$}. Our second contribution is a method for reducing the communication complexity for any depth-1 sub-circuit to be proportional only to the size of the input and output (rather than the size of the circuit). This implies protocols with \emph{sublinear communication complexity} (in the size of the circuit) for perfectly secure computation for important functions like matrix multiplication.

Mon, 18 Oct 2021 03:15PM
Universally Composable Almost-Everywhere Secure Computation
Nishanth Chandran, Pouyan Forghani, Juan Garay, Rafail Ostrovsky, Rutvik Patel, Vassilis Zikas
cryptographic protocols / Secure multi-party computation, universal composability, almost-everywhere secure computation, sparse graphs, secure message transmission

Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of whom might even be corrupted. The work by Garay and Ostrovsky [EUROCRYPT'08] on almost-everywhere MPC (AE-MPC), introduced “best-possible security” properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation—we call such parties “doomed.” In this work we provide a universally composable definition of almost-everywhere security, which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous “best-possible security” version of secure communication) in the Universal Composability (UC) framework of Canetti. Our result offers the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC.

Mon, 18 Oct 2021 03:32PM
Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties
Craig Gentry, Shai Halevi, Vadim Lyubashevsky
cryptographic protocols / Secure MPC, VSS

Non-interactive publicly verifiable secret sharing (PVSS) schemes allow parties to re-share a secret in a decentralized setting in the presence of malicious parties. A recently proposed application of PVSS schemes is to enable permissionless proof-of-stake blockchains to ``keep a secret" via a sequence of committees that share that secret. Such committees can use the secret to produce signatures on the blockchain's behalf, or to disclose hidden data conditioned on consensus that some event has occurred. Such a setting may involve thousands of parties, so the PVSS scheme that it uses must be very efficient, both in computation and communication. Yet, previous PVSS schemes have large proofs and/or require many exponentiations over large groups. We present a non-interactive PVSS scheme in which the underlying encryption scheme is based on the learning with errors (LWE) problem. While lattice-based encryption schemes are very fast, they have issues with bandwidth (long ciphertexts and public keys). We deal with the bandwidth issue in two ways. First, we adapt the Peikert-Vaikuntanathan-Waters (PVW) encryption scheme to the multi-receiver setting so that the bulk of the parties' keys is a common random string, and so that we get good amortized communication: $\Omega(1)$ plaintext/ciphertext rate (rate $\approx 1/60$ for 100 parties, $\approx 1/8$ for 1000 parties, approaching 1/2 as the number of parties grows). Second, we use bulletproofs over a DL-group of order about 256 bits to get compact proofs of correct encryption of shares. Switching from the lattice setting to the DL setting is relatively painless, as we equate the LWE modulus with the order of the group, and apply dimension reduction to vectors before the switch to minimize the number of exponentiations in the bulletproof. An implementation of our PVSS for 1000 parties showed that it's quite practical, and should remain so with up to a two order of magnitude increase in the group size.

Mon, 18 Oct 2021 04:59PM
Simulation Extractable Versions of Groth’s zk-SNARK Revisited
Oussama Amine, Karim Baghery, Zaira Pindado, Carla Ràfols
cryptographic protocols / NIZK, zk-SNARK, Simulation Extractability, Generic Group Mode, Random Oracle Model

Zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) are the most efficient proof systems in terms of proof size and verification. Currently, Groth's construction from EUROCRYPT 2016, $\mathsf{Groth16}$, is the state-of-the-art and is widely deployed in practice. $\mathsf{Groth16}$ is originally proven to achieve knowledge soundness, which does not guarantee the non-malleability of proofs. There has been considerable progress in presenting new zk-SNARKs or modifying $\mathsf{Groth16}$ to efficiently achieve \textit{strong} Simulation Extractability (SE), which is shown to be a necessary requirement in some applications. In this paper, we revise the Random Oracle (RO) based variant of $\mathsf{Groth16}$ proposed by Bowe and Gabizon, BG18, the most efficient one in terms of prover efficiency and CRS size among the candidates, and present two efficient variants. In the first variant, we show that one can save 1 pairing in the verification and also relax the RO to a collision-resistant hash function. This is achieved at the cost of a single new element in the common reference string, and one exponentiation in $G_T$ in the verification. In the second variant, we focus on the efficiency and present an SE zk-SNARK that has a minimal overhead on $\mathsf{Groth16}$. Namely, it adds only 1 element to the proof and 1 exponentiation in $G_2$ to the verification of $\mathsf{Groth16}$. We implement our proposed SE zk-SNARKs along with BG18 in the Arkworks library, and compare the efficiency of our schemes with some related works. Our empirical experiences confirm that our second SE zk-SNARK is more efficient than all previous SE schemes in most dimensions and it has very close efficiency to the original $\mathsf{Groth16}$.

Mon, 18 Oct 2021 05:22PM
Succinct LWE Sampling, Random Polynomials, and Obfuscation
Lalita Devadas, Willy Quach, Vinod Vaikuntanathan, Hoeteck Wee, Daniel Wichs
Indistinguishability Obfuscation, Learning with Errors, LWE sampling

We present a construction of indistinguishability obfuscation (iO) that relies on the learning with errors (LWE) assumption together with a new notion of succinctly sampling pseudo-random LWE samples. We then present a candidate LWE sampler whose security is related to the hardness of solving systems of polynomial equations. Our construction improves on the recent iO candidate of Wee and Wichs (Eurocrypt 2021) in two ways: first, we show that a much weaker and simpler notion of LWE sampling suffices for iO; and secondly, our candidate LWE sampler is secure based on a compactly specified and falsifiable assumption about random polynomials, with a simple error distribution that facilitates cryptanalysis.

Mon, 18 Oct 2021 05:51PM
The irreducible vectors of a lattice: Some theory and applications
Emmanouil Doulgerakis, Thijs Laarhoven, Benne de Weger
foundations / lattices, relevant vectors, irreducible vectors, sieving algorithms

The main idea behind lattice sieving algorithms is to reduce a sufficiently large number of lattice vectors with each other so that a set of short enough vectors is obtained, including a basis of the lattice. It is therefore natural to study vectors which cannot be reduced. In this work we give a concrete definition of an irreducible vector and study the properties of the set of all such vectors. We show that the set of irreducible vectors is a subset of the set of relevant vectors and study its properties. For extremal lattices this set may contain as many as $2^n$ vectors, which leads us to define the notion of a complete system of irreducible vectors, whose size can be upper-bounded by the kissing number. We study properties of this set and observe a close relation to heuristic sieving algorithms. Finally we briefly examine the use of this set in the study of lattice problems such as SVP, SIVP and CVPP. The introduced notions, as well as various results derived along the way, may provide further insights into lattice algorithms and motivate new research into understanding these algorithms better.

Mon, 18 Oct 2021 07:27PM
Quantum Key-length Extension
Joseph Jaeger, Fang Song, Stefano Tessaro
secret-key cryptography / post-quantum cryptography, block ciphers, quantum random oracle model, concrete security, provable security

Should quantum computers become available, they will reduce the effective key length of basic secret-key primitives, such as blockciphers. To address this we will either need to use blockciphers with inherently longer keys or develop key-length extension techniques to amplify the security of a blockcipher to use longer keys. We consider the latter approach and revisit the FX and double encryption constructions. Classically, FX was proven to be a secure key-length extension technique, while double encryption fails to be more secure than single encryption due to a meet-in-the-middle attack. In this work we provide positive results, with concrete and tight bounds, for the security of both of these constructions against quantum attackers in ideal models. For FX, we consider a partially-quantum model, where the attacker has quantum access to the ideal primitive, but only classical access to FX. This is a natural model and also the strongest possible, since effective quantum attacks against FX exist in the fully-quantum model when quantum access is granted to both oracles. We provide two results for FX in this model. The first establishes the security of FX against non-adaptive attackers. The second establishes security against general adaptive attackers for a variant of FX using a random oracle in place of an ideal cipher. This result relies on the techniques of Zhandry (CRYPTO '19) for lazily sampling a quantum random oracle. An extension to perfectly lazily sampling a quantum random permutation, which would help resolve the adaptive security of standard FX, is an important but challenging open question. We introduce techniques for partially-quantum proofs without relying on analyzing the classical and quantum oracles separately, which is common in existing work. This may be of broader interest. For double encryption, we show that it amplifies strong pseudorandom permutation security in the fully-quantum model, strengthening a known result in the weaker sense of key-recovery security. This is done by adapting a technique of Tessaro and Thiruvengadam (TCC '18) to reduce the security to the difficulty of solving the list disjointness problem and then showing its hardness via a chain of reductions to the known quantum difficulty of the element distinctness problem.

Tue, 19 Oct 2021 03:00AM
SIDH Proof of Knowledge
Luca De Feo, Samuel Dobson, Steven D. Galbraith, Lukas Zobernig
public-key cryptography / Post-quantum cryptography, Diffie-Hellman key exchange, supersingular elliptic curves, isogenies, SIDH, proof of knowledge, public key verification

We demonstrate the soundness proof for the De Feo-Jao-Plût identification scheme (the basis for SIDH signatures) contains an invalid assumption and provide a counterexample for this assumption — thus showing the proof of soundness is invalid. As this proof was repeated in a number of works by various authors, multiple pieces of literature are affected by this result. Due to the importance of being able to prove knowledge of an SIDH key (for example, to prevent adaptive attacks), soundness is a vital property. We propose a modified identification scheme fixing the issue with the De Feo-Jao-Plût scheme, and provide a proof of security of this new scheme. We also prove that a modification of this scheme allows the torsion points in the public key to be verified too. This results in a secure proof of knowledge for SIDH keys. In particular, these schemes provide a non-interactive way of verifying that SIDH public keys are well formed as protection against adaptive attacks, more efficient than generic NIZKs.

Tue, 19 Oct 2021 03:41AM
Oblivious Message Retrieval
Zeyu Liu, Eran Tromer
cryptographic protocols / Private Messaging, Privacy-Preserving Cryptocurrencies, Fully Homomorphic Encryption

Anonymous message delivery systems, such as private messaging services and privacy-preserving payment systems, need a mechanism for recipients to retrieve the messages addressed to them, without leaking metadata or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale. We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. These servers operate obliviously and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding (unlike in prior schemes), and are post-quantum secure. Our starting point is an asymptotically-efficient approach, using Fully Homomorphic Encryption and homomorphically-encoded Sparse Random Linear Codes. We then address the concrete performance using a bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations. This reduces the digest size to a few bits per message scanned. Concretely, the servers' cost is a couple of USD per million messages scanned, and the resulting digests can be decoded by recipients in under 20ms. Our schemes can thus practically attain the strongest form of receiver privacy for current applications such as privacy-preserving cryptocurrencies.

Tue, 19 Oct 2021 02:14PM
Three Input Exclusive-OR Gate Support For Boyar-Peralta's Algorithm (Extended Version)
Anubhab Baksi, Vishnu Asutosh Dasu, Banashri Karmakar, Anupam Chattopadhyay, Takanori Isobe
secret-key cryptography /

The linear layer, which is basically a binary non-singular matrix, is an integral part of cipher construction in a lot of private key ciphers. As a result, optimising the linear layer for device implementation has been an important research direction for about two decades. The Boyar-Peralta's algorithm (SEA'10) is one such common algorithm, which offers significant improvement compared to the straightforward implementation. This algorithm only returns implementation with XOR2 gates, and is deterministic. Over the last couple of years, some improvements over this algorithm has been proposed, so as to make support for XOR3 gates as well as make it randomised. In this work, we take an already existing improvement (Tan and Peyrin, TCHES'20) that allows randomised execution and extend it to support three input XOR gates. This complements the other work done in this direction (Banik et al., IWSEC'19) that also supports XOR3 gates with randomised execution. Further, noting from another work (Maximov, Eprint'19), we include one additional tie-breaker condition in the original Boyar-Peralta's algorithm. Our work thus collates and extends the state-of-the-art, at the same time offers a simpler interface. We show several results that improve from the lastly best-known results.

Tue, 19 Oct 2021 03:24PM
Short Identity-Based Signatures with Tight Security from Lattices
Jiaxin Pan, Benedikt Wagner
public-key cryptography / Identity-based signatures, tight security, short integer solution assumption, lattices

We construct a short and adaptively secure identity-based signature scheme tightly based on the well-known Short Integer Solution (SIS) assumption. Although identity-based signature schemes can be tightly constructed from either standard signature schemes against adaptive corruptions in the multi-user setting or a two-level hierarchical identity-based encryption scheme, neither of them is known with short signature size and tight security based on the SIS assumption. Here ``short'' means the signature size is independent of the message length, which is in contrast to the tree-based (tight) signatures. Our approach consists of two steps: Firstly, we give two generic transformations (one with random oracles and the other without) from non-adaptively secure identity-based signature schemes to adaptively secure ones tightly. Our idea extends the similar transformation for digital signature schemes. Secondly, we construct a non-adaptively secure identity-based signature scheme based on the SIS assumption in the random oracle model.

Tue, 19 Oct 2021 03:42PM
Secret Keys in Genus-2 SIDH
Sabrina Kunzweiler, Yan Bo Ti, Charlotte Weitkämper
public-key cryptography / Isogeny-based cryptography, Genus-2 SIDH, cryptanalysis, adaptive attack

We present a polynomial-time adaptive attack on the genus-2 variant of the SIDH protocol (G2SIDH) and describe an improvement to its secret selection procedure. G2SIDH is a generalisation of the Supersingular Isogeny Diffie--Hellman key exchange into the genus-2 setting which was proposed by Flynn and Ti. G2SIDH is able to achieve the same security as SIDH while using fields a third of the size. We analyze the keyspace of G2SIDH and achieve an improvement to the secret selection by using symplectic bases for the torsion subgroups. This allows for the near uniform sampling of secrets without needing to solve multiple linear congruences as suggested by Flynn--Ti. More generally, using symplectic bases enables us to classify and enumerate isogeny kernel subgroups and thus simplify the secret sampling step for general genus-2 SIDH-style constructions. The proposed adaptive attack on G2SIDH is able to recover the secret when furnished with an oracle that returns a single bit of information. We ensure that the maliciously generated information provided by the attacker cannot be detected by implementing simple countermeasures, forcing the use of the Fujisaki--Okamoto transform for CCA2-security. We demonstrate this attack and show that it is able to recover the secret isogeny in all cases of G2SIDH using a symplectic basis before extending the strategy to arbitrary bases.

Tue, 19 Oct 2021 06:03PM
Fault Attacks In Symmetric Key Cryptosystems
Anubhab Baksi, Shivam Bhasin, Jakub Breier, Dirmanto Jap, Dhiman Saha
secret-key cryptography / fault attack, countermeasure, symmetric key, systemization of knowledge

Fault attacks are among the well-studied topics in the area of cryptography. These attacks constitute a powerful tool to recover the secret key used in the encryption process. Fault attacks work by forcing a device to work under non-ideal environmental conditions (such as high temperature) or external disturbances (such as glitch in the power supply) while performing a cryptographic operation. The recent trend shows that the amount of research in this direction; which ranges from attacking a particular primitive, proposing a fault countermeasure, to attacking countermeasures; has grown up substantially and going to stay as an active research interest for a foreseeable future. Hence, it becomes apparent to have a comprehensive yet compact study of the (major) works. This work, which covers a wide spectrum in the present day research on fault attacks that fall under the purview of the symmetric key cryptography, aims at fulfilling the absence of an up-to-date survey. We present mostly all aspects of the topic in a way which is not only understandable for a non-expert reader, but also helpful for an expert as a reference.

Wed, 20 Oct 2021 01:55AM
Collusion Resistant Revocable Ring Signatures and Group Signatures from Hard Homogeneous Spaces
Yi-Fu Lai, Samuel Dobson
public-key cryptography / group signature, isogeny cryptography, ring signature, post-quantum cryptography

Both ring signatures and group signatures are useful privacy tools, allowing signers to hide their identities within a set of other public keys, while allowing their signatures to be validated with respect to the entire set. Group signature schemes and revocable ring signature schemes both provide the additional ability for certain authorized members to revoke the anonymity on a signature and reveal the true signer—allowing management of abuse in the scheme. This work consists of two parts. Firstly, we introduce a stronger security notion—collusion resistance—for revocable ring signatures and show how to derive a group signature scheme from it, which provides a new approach to obtaining group signatures. This improves on the existing weak security model (e.g. with selfless anonymity) which fails to guarantee anonymity of members whose keys are exposed. Our stronger notion requires that the scheme remains secure against full key exposure in the anonymity game, and allows collusion among arbitrary members in the revocability game. Secondly (and more concretely), we construct a practical collusion-resistant revocable ring signature scheme based on hard homogenous spaces (HHS), and thus obtain a group signature scheme based on isogenies. To the best of our knowledge, the schemes given in this work are the first efficient post-quantum (collusion-resistant) revocable ring signature scheme, and the first efficient isogeny-based group signature scheme in the literature.

Wed, 20 Oct 2021 06:37AM
Collusion-Deterrent Threshold Information Escrow
Easwar Vivek Mangipudi, Donghang Lu, Alexandros Psomas, Aniket Kate
Escrows, Oblivious Transfer, Game Theory, Smart Contracts

An information escrow (IE) service allows its users to encrypt a message such that the message is unlocked only when a user-specified condition is satisfied. Its instantiations include timed-release encryption and allegation escrows with applications ranging from e-auctions to the #metoo movement. The proposed IE systems typically employ threshold cryptography towards mitigating the single-point-of-failure problem. Here, a set of escrow agents securely realize the IE functionality as long as a threshold or more number of agents behave honestly. Nevertheless, these threshold information escrow (TIE) protocols are vulnerable to premature, and undetectable unlocking of messages through collusion among rational agents offering the IE service. This work presents a provably secure TIE scheme in the mixed-behavior model consisting of rational and malicious escrow agents, where any collusion attempt among the agents towards premature decryption results in penalization through a loss of (crypto-)currency and getting banned from the system. The proposed collusion-deterrent escrow (CDE) scheme introduces a novel incentive-penalty mechanism using a user-induced information asymmetry among the agents, and as a result, they stay honest until the user-specified decryption condition is met. In particular, each agent makes a cryptocurrency deposit before the start of the protocol instance such that the deposit amount is returned to the agent when the user-specified condition is met or can be transferred by anyone who holds a secret key corresponding to a public key associated with the instance. Using a novel combination of oblivious transfer, robust bit watermarking, and secure multi-party computation, CDE ensures that whenever the agents collude to prematurely decrypt the user data, there would be one or more whistle-blower agents who can withdraw/transfer the deposits of all other agents thereby penalizing them. We model collusion as a game induced among rational agents offering the CDE service and show in game- theoretic terms that the agents do not collude at equilibrium. We also present a prototype implementation of the CDE protocol and demonstrate its efficiency towards use in practice. By raising the bar for collusion significantly, this work offers an important step towards weakening the strong non- collusion assumption pervasive across multi-party computation applications.

Wed, 20 Oct 2021 08:52AM
A PCP Theorem for Interactive Proofs and Applications
Gal Arnon, Alessandro Chiesa, Eylon Yogev
foundations / interactive proofs; probabilistically checkable proofs; interactive oracle proofs

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads $O(1)$ bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multiple rounds while reading a small number of bits from each prover message. While PCPs are relatively well understood, the power captured by IOPs (beyond NP) has yet to be fully explored. We present a generalization of the PCP theorem for interactive languages. We show that any language decidable by a $k(n)$-round IP has a $k(n)$-round public-coin IOP, where the verifier makes its decision by reading only $O(1)$ bits from each (polynomially long) prover message and $O(1)$ bits from each of its own (random) messages to the prover. Our result and the underlying techniques have several applications. We get a new hardness of approximation result for a stochastic satisfiability problem, we show IOP-to-IOP transformations that previously were known to hold only for IPs, and we formulate a new notion of PCPs (index-decodable PCPs) that enables us to obtain a commit-and-prove SNARK in the random oracle model for nondeterministic computations.

Wed, 20 Oct 2021 07:53PM
Constructing Secure Multi-Party Computation with Identifiable Abort
Nicholas-Philip Brandt, Sven Maier, Tobias Müller, Jörn Müller-Quade
foundations / Multi-Party Computation, Identifiable Abort, Conflict Graph, Universal Composability

We propose an intuitive approach for constructing and analyzing Multi-Party Computation protocols with Identifiable Abort (ID-MPC) based on simple graph-theory. On a high level, in our approach, honest parties publicly announce conflicts with malicious parties via broadcast whenever they catch them misbehaving, thus inducing a Conflict Graph (CG). We directly link the sufficient and necessary conditions for the (identifiable) abort of a protocol to publicly verifiable graph-theoretical properties of the Conflict Graph. To demonstrate its power, we use our technique to reduce the necessary requirements for ID-MPC in the Universal Composability framework with a dishonest majority. State-of-the-art protocols in the dishonest majority setting are posited in the Correlated-Randomness model where one n-party setup provides randomness that is n-wise correlated to all other parties’ randomness. Using our technique we are able to reduce the degree of correlation in the this randomness from $n$ to $n-1$. Additionally, if $n$ is sufficiently small, then our upper bound can be transitively expanded, i.e., for $t \leq n−3$ corruptions among $n$ parties we can construct $n$-party ID-MPC from correlated randomness among each set of $t+2$ parties.

Thu, 21 Oct 2021 03:08AM
smartFHE: Privacy-Preserving Smart Contracts from Fully Homomorphic Encryption
Ravital Solomon, Ghada Almashaqbeh
cryptographic protocols / fully homomorphic encryption, zero knowledge proofs, blockchain

Despite the great potential and flexibility of smart contract-enabled blockchains, building privacy-preserving applications using these platforms remains an open question. Existing solutions fall short in achieving this goal since they support a limited operation set, enable private computation on inputs belonging to only one user, or even ask the users themselves to coordinate and perform the computation off-chain. To address these limitations, we propose smartFHE, a framework to support private smart contracts using fully homomorphic encryption (FHE). To the best of our knowledge, smartFHE is the first to use FHE in the blockchain model; it is also the first to allow for building arbitrary smart contracts that operate on multiple users' inputs on-chain while preserving input/output privacy. smartFHE does not overload the user since miners are instead responsible for performing the private computation. This is achieved by employing (single and multi-key) FHE so miners can compute over encrypted data and account balances, along with efficient zero-knowledge proof systems (ZKPs) so users can prove well-formedness of their private inputs. Crucially, our framework is modular as any FHE and ZKP scheme can be used so long as they satisfy certain requirements with respect to correctness and security. We formulate a notion for a privacy-preserving smart contract (PPSC) scheme and show a concrete instantiation. We provide formal definitions along with proofs of the correctness and security of our construction. Finally, we include preliminary benchmarks to evaluate the feasibility of our instantiation.

Thu, 21 Oct 2021 04:22AM
HashSplit: Exploiting Bitcoin Asynchrony to Violate Common Prefix and Chain Quality
Muhammad Saad, Afsah Anwar, Srivatsan Ravi, David Mohaisen
applications / Blockchain, Consensus

The safety of the Bitcoin blockchain relies on strong network synchrony. Therefore, violating the blockchain safety requires strong adversaries who control a mining pool with 51% hash rate. In this paper, we show that the network synchrony does not hold in the real world Bitcoin network, which can be exploited to amortize the cost of various attacks. Towards that, first we construct the Bitcoin ideal world functionality to formally specify its ideal execution model in a synchronous network. We then develop a large-scale data collection system through which we connect with more than 36K IP addresses of the Bitcoin nodes and identify 359 mining nodes. We contrast the Bitcoin ideal functionality against real world measurements to expose network anomalies that can be exploited to optimize the existing attacks. Particularly, we observe high block propagation delay in the Bitcoin network causing weak network synchronization: on average, in 9.97 minutes, only 39% nodes have the up-to-date blockchain. Through a fine-grained analysis, we discover non-uniform block propagation delay among the mining nodes showing that the Bitcoin network is asynchronous. To realize the threat of asynchronous network, we present the HashSplit attack that allows an adversary to orchestrate concurrent mining on multiple branches of the blockchain to violate common prefix and chain quality properties. We also propose the attack countermeasures by releasing a Bitcoin Core version that closely models the Bitcoin ideal functionality. Our measurements, theoretical modeling, pro-posed attack, and countermeasures open new directions in the security evaluation of Bitcoin and similar blockchain systems

Thu, 21 Oct 2021 08:35AM
UC Non-Interactive, Proactive, Threshold ECDSA
Ran Canetti, Nikolaos Makriyannis, Udi Peled
cryptographic protocols / ECDSA, proactive, composability, signatures, threshold cryptography, distributed cryptography

Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS ’18), we present a threshold ECDSA protocol, for any number of signatories and any threshold, that improves as follows over the state of the art: * Signature generation takes only 4 rounds (down from the current 8 rounds), with a comparable computational cost. Furthermore, 3 of these rounds can take place in a preprocessing stage before the signed message is known, lending to a non-interactive threshold ECDSA protocol. * The protocol withstands adaptive corruption of signatories. Furthermore, it includes a periodic refresh mechanism and offers full proactive security. * The protocol realizes an ideal threshold signature functionality within the UC framework, in the global random oracle model, assuming Strong RSA, semantic security of the Paillier encryption, and a somewhat enhanced variant of existential unforgeability of ECDSA. These properties (low latency, compatibility with cold-wallet architectures, proactive security, and composable security) make the protocol ideal for threshold wallets for ECDSA-based cryptocurrencies.

Thu, 21 Oct 2021 01:56PM
UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts
Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, Udi Peled
cryptographic protocols / composability, accountability, identifiable abort, signatures, threshold cryptography, distributed cryptography, multiparty computation, Blockchain, MPC, UC, malicious adversaries

Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS '18), we present threshold ECDSA protocols, for any number of signatories and any threshold, that improve as follows over the state of the art: * Only the last round of our protocols requires knowledge of the message, and the other rounds can take place in a preprocessing stage, lending to a non-interactive threshold ECDSA protocol. * Our protocols withstand adaptive corruption of signatories. Furthermore, they include a periodic refresh mechanism and offer full proactive security. * Our protocols realize an ideal threshold signature functionality within the UC framework, in the global random oracle model, assuming Strong RSA, DDH, semantic security of the Paillier encryption, and a somewhat enhanced variant of existential unforgeability of ECDSA. * Both protocols achieve accountability by identifying corrupted signatories in case of failure to generate a valid signature. The protocols provide a tradeoff between the number of rounds to generate a signature and the computational and communication overhead for the identification of corrupted signatories. Namely: * For one protocol, signature generation takes only 4 rounds (down from the current state of the art of 8 rounds), but the identification process requires computation and communication that is quadratic in the number of parties. * For the other protocol, the identification process requires computation and communication that is only linear in the number of parties, but signature generation takes 7 rounds. These properties (low latency, compatibility with cold-wallet architectures, proactive security, identifiable abort and composable security) make the two protocols ideal for threshold wallets for ECDSA-based cryptocurrencies.

Thu, 21 Oct 2021 03:49PM
SSE and SSD: Page-Efficient Searchable Symmetric Encryption
Angèle Bossuat, Raphael Bost, Pierre-Alain Fouque, Brice Minaud, Michael Reichle
cryptographic protocols / symmetric searchable encryption, provable security, implementation, bin packing

Searchable Symmetric Encryption (SSE) enables a client to outsource a database to an untrusted server, while retaining the ability to securely search the data. The performance bottleneck of classic SSE schemes typically does not come from their fast, symmetric cryptographic operations, but rather from the cost of memory accesses. To address this issue, many works in the literature have considered the notion of locality, a simple design criterion that helps capture the cost of memory accesses in traditional storage media, such as Hard Disk Drives. A common thread among many SSE schemes aiming to improve locality is that they are built on top of new memory allocation schemes, which form the technical core of the constructions. The starting observation of this work is that for newer storage media such as Solid State Drives (SSDs), which have become increasingly common, locality is not a good predictor of practical performance. Instead, SSD performance mainly depends on page efficiency, that is, reading as few pages as possible. We define this notion, and identify a simple memory allocation problem, Data-Independent Packing (DIP), that captures the main technical challenge required to build page-efficient SSE. As our main result, we build a page-efficient and storage-efficient data-independent packing scheme, and deduce the Tethys SSE scheme, the first SSE scheme to achieve at once O(1) page efficiency and O(1) storage efficiency. The technical core of the result is a new generalization of cuckoo hashing to items of variable size. Practical experiments show that this new approach achieves excellent performance.

Thu, 21 Oct 2021 09:22PM
Spectrum: High-Bandwidth Anonymous Broadcast with Malicious Security
Zachary Newman, Sacha Servan-Schreiber, Srinivas Devadas
applications / anonymity, metadata, privacy, communication, broadcasting, malicious, security

We present Spectrum, a high-bandwidth, metadata-private file broadcasting system with malicious security guarantees. In Spectrum, a small number of broadcasters share a document with many subscribers via two or more non-colluding servers. Subscribers generate cover traffic, hiding which users are broadcasters and which users are simply consumers. To drastically improve latency and throughput, Spectrum optimizes for few broadcasters and many subscribers, common in real-world broadcast settings. To prevent malicious clients from disrupting broadcasts with malformed requests, we introduce a new blind access control technique that allows servers to reject malicious users. We also ensure security against malicious servers which collude with clients. We implement and evaluate Spectrum. Compared to the state-of-the-art in cryptographic anonymous communication systems, Spectrum’s peak throughput is 4–12,500× faster (and commensurately cheaper) in a broadcast setting. Deployed on two commodity servers, Spectrum allows broadcasters to share 1 GB in 13h 20m with an anonymity set of 10,000 (for a total cost of about $6.84). This corresponds to an anonymous upload of two full-length 720p documentary movies. Operational costs scale roughly linearly in the size of the file and total number of users, and Spectrum parallelizes trivially with more hardware.

Fri, 22 Oct 2021 10:05AM
DeCSIDH: Delegating isogeny computations in the CSIDH setting
Robi Pedersen
public-key cryptography / Post-quantum cryptography, Isogeny-based cryptography, CSIDH, Secure computation outsourcing, Lightweight cryptography

Delegating heavy computations to auxiliary servers, while keeping the inputs secret, presents a practical solution for computationally limited devices to use resource-intense cryptographic protocols, such as those based on isogenies, and thus allows the deployment of post-quantum security on mobile devices and in the internet of things. We propose two algorithms for the secure and verifiable delegation of isogeny computations in the CSIDH setting. We then apply these algorithms to different instances of CSIDH and to the signing algorithms SeaSign and CSI-FiSh. Our algorithms present a communication-cost trade-off. Asymptotically (for high communication), the cost for the delegator is reduced by a factor 9 for the original CSIDH-512 parameter set and a factor 30 for SQALE'd CSIDH-4096, while the relative cost of SeaSign vanishes. Even for much lower communication cost, we come close to these asymptotic results. Using the knowledge of the class group, the delegation of CSI-FiSh is basically free (up to element generation) already at a very low communication cost.

Fri, 22 Oct 2021 10:22AM
As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!
Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic
public-key cryptography / accountability Byzantine consensus

It is known that the agreement property of the Byzantine consensus problem among $n$ processes can be violated in a non-synchronous system if the number of faulty processes exceeds $t_0 =n/3$. In this paper, we investigate the accountable Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (i.e., when the number of faulty processes does not exceed $t_0$) and allowing correct processes to obtain a proof of culpability of $t_0 + 1$ faulty processes whenever correct processes disagree. We present four complementary contributions: (i) We introduce $ABC$: a simple yet efficient transformation of any Byzantine consensus protocol to an accountable one. $ABC$ introduces an overhead of (1) only two all-to-all communication rounds and $O(n^2)$ additional bits in executions with up to $t_0$ faults, and (2) three all-to-all communication rounds and $O(n^3)$ additional bits in executions with more faults. (ii) We prove a tight lower bound on the communication complexity needed for any accountable Byzantine consensus protocol. In particular, we show that any algorithm incurs a cubic communication complexity in an execution in which disagreement occurs and that this bound is tight by applying $ABC$ to the binary DBFT consensus protocol. (iii) We demonstrate that, when applied to an optimal Byzantine consensus protocol, $ABC$ constructs an accountable Byzantine consensus protocol that is (1) optimal in solving consensus whenever consensus is solvable, and (2) optimal in obtaining accountability whenever disagreement happens. (iv) We generalize $ABC$ to other distributed computing problems besides the classic consensus problem. We characterize a class of agreement tasks, including reliable and consistent broadcast, that $ABC$ renders accountable.

Fri, 22 Oct 2021 07:35PM
Plactic signatures
Daniel R. L. Brown
public-key cryptography / digital signature, combinatorics, plactic monoid, semistandard tableau

Plactic signatures use the plactic monoid (semistandard tableaus with Knuth’s associative multiplication) and full-domain hashing (SHAKE).

Fri, 22 Oct 2021 09:27PM
Bandersnatch: a fast elliptic curve built over the BLS12-381 scalar field
Simon Masson, Antonio Sanso, Zhenfei Zhang
public-key cryptography / elliptic curve scalar multiplication GLV method benchmarks

In this short note, we introduce Bandersnatch, a new elliptic curve built over the BLS12-381 scalar field. The curve is equipped with an efficient endomorphism, allowing a fast scalar multiplication algorithm. Our benchmark shows that the multiplication is 42% faster, compared to another curve, called Jubjub, having similar properties. Nonetheless, Bandersnatch does not provide any performance improvement for either rank 1 constraint systems (R1CS) or multi scalar multiplications, compared to the Jubjub curve.