International Association
for Cryptologic Research

In the context of second layer payments in Bitcoin, and specifically the Lightning Network, we propose a design for a lightweight watchtower that does not need to store signed justice transactions. We alter the structure of the opening and commitment transactions in Lightning channels to encode justice transactions as part of the commitment transactions. With that, a watchtower just needs to watch for specific cheating commitment transaction IDs on the blockchain and can extract signed justice transactions directly from these commitment transactions that appear on the blockchain. Our construction saves an order of magnitude in storage over existing watchtower designs. In addition, we let the watchtower prove to each channel that it has access to all the data required to do its job, and can therefore be paid-per-update.

Distributed key generation (DKG) is a fundamental building block for a variety of cryptographic schemes and protocols, such as threshold cryptography, multi-party coin tossing schemes, public randomness beacons and consensus protocols. More recently, the surge in interest for blockchain technologies, and in particular the quest for developing scalable protocol designs, has renewed and strengthened the need for efficient and practical DKG schemes. Surprisingly, given the broad range of applications and available body of research, fully functional and readily available DKG protocol implementations still remain limited. We hereby aim to close this gap by presenting an open source, fully functional, well documented, and economically viable DKG implementation that employs Ethereum's smart contract platform as a communication layer. The efficiency and practicability of our protocol is demonstrated through the deployment and successful execution of a DKG contract in the Ropsten testnet. Given the current Ethereum block gas limit, it is possible to support up to $ 256 $ participants, while still ensuring that the key generation process can be verified at smart contract level. Further, we present a generalization of our underlying DKG protocol that is suitable for distributed generation of keys for discrete logarithm based cryptosystems.

A traitor tracing scheme is a multi-user public-key encryption scheme where each user in the system holds a decryption key that is associated with the user's identity. Using the public key, a content distributor can encrypt a message to all of the users in the system. At the same time, if a malicious group of users combine their respective decryption keys to build a "pirate decoder," there is an efficient tracing algorithm that the content distributor can use to identify at least one of the keys used to construct the decoder. A trace-and-revoke scheme is an extension of a standard traitor tracing scheme where there is an additional key-revocation mechanism that the content distributor can use to disable the decryption capabilities of compromised keys.

Trace-and-revoke schemes are generally difficult to construct. Existing constructions from standard assumptions can only tolerate bounded collusions (i.e., there is an a priori bound on the number of keys an adversary obtains), have system parameters that scale exponentially in the bit-length of the identities, or satisfy weaker notions of traceability that are vulnerable to certain types of "pirate evolution" attacks. In this work, we provide the first construction of a trace-and-revoke scheme that is fully collusion resistant and capable of supporting arbitrary identities (i.e., the identities can be drawn from an exponential-size space). Our scheme supports public broadcast and secret tracing, and can be based on the sub-exponential hardness of the LWE problem (with a super-polynomial modulus-to-noise ratio). Our construction relies on a combination of both algebraic and combinatorial techniques for traitor tracing.

Hardware reverse engineering is a powerful and universal tool for both security engineers and adversaries. From a defensive perspective, it allows for detection of intellectual property infringements and hardware Trojans, while it simultaneously can be used for product piracy and malicious circuit manipulations. From a designer’s perspective, it is crucial to have an estimate of the costs associated with reverse engineering, yet little is known about this, especially when dealing with obfuscated hardware. The contribution at hand provides new insights into this problem, based on algorithms with sound mathematical underpinnings.

Our contributions are threefold: First, we present the graph similarity problem for automating hardware reverse engineering. To this end, we improve several state-of-the-art graph similarity heuristics with optimizations tailored to the hardware context. Second, we propose a novel algorithm based on multiresolutional spectral analysis of adjacency matrices. Third, in three extensively evaluated case studies, namely (1) gate-level netlist reverse engineering, (2) hardware Trojan detection, and (3) assessment of hardware obfuscation, we demonstrate the practical nature of graph similarity algorithms.

In this paper, we propose a new leakage-resilient identity-based encryption (IBE) scheme that is secure against chosen-ciphertext attacks (CCA) in the bounded memory leakage model. It is the first CCA-secure leakage-resilient IBE scheme which does not depend on $\mathtt{q}$-type assumptions. More precisely, it is secure under the DLIN and XDH assumption for symmetric and asymmetric bilinear groups, respectively. The leakage rate 1/6 is achieved under the XDH assumption.

Messaging systems are used to spread misinformation and other malicious content, often with dire consequences. End-to-end encryption improves privacy but hinders content-based moderation and, in particular, obfuscates the original source of malicious content. We introduce the idea of message traceback, a new cryptographic approach that enables platforms to simultaneously provide end-to-end encryption while also being able to track down the source of malicious content reported by users. We formalize functionality and security goals for message traceback, and detail two constructions that allow revealing a chain of forwarded messages (path traceback) or the entire forwarding tree (tree traceback). We implement and evaluate prototypes of our traceback schemes to highlight their practicality, and provide a discussion of deployment considerations.

In a traitor tracing (TT) system for $n$ users, every user has his/her own secret key. Content providers can encrypt messages using a public key, and each user can decrypt the ciphertext using his/her secret key. Suppose some of the $n$ users collude to construct a pirate decoding box. Then the tracing scheme has a special algorithm, called $Trace$, which can identify at least one of the secret keys used to construct the pirate decoding box.

Traditionally, the trace algorithm output only the `index' associated with the traitors. As a result, to use such systems, either a central master authority must map the indices to actual identities, or there should be a public mapping of indices to identities. Both these options are problematic, especially if we need public tracing with anonymity of users. Nishimaki, Wichs, and Zhandry (NWZ) [Eurocrypt 2016] addressed this problem by constructing a traitor tracing scheme where the identities of users are embedded in the secret keys, and the trace algorithm, given a decoding box $D$, can recover the entire identities of the traitors. We call such schemes `Embedded Identity Traitor Tracing' schemes. NWZ constructed such schemes based on adaptively secure functional encryption (FE). Currently, the only known constructions of FE schemes are based on nonstandard assumptions such as multilinear maps and iO.

In this work, we study the problem of embedded identities TT based on standard assumptions. We provide a range of constructions based on different assumptions such as public key encryption (PKE), bilinear maps and the Learning with Errors (LWE) assumption. The different constructions have different efficiency trade offs. In our PKE based construction, the ciphertext size grows linearly with the number of users; the bilinear maps based construction has sub-linear ($\sqrt{n}$) sized ciphertexts. Both these schemes have public tracing. The LWE based scheme is a private tracing scheme with optimal ciphertexts (i.e., $\log(n)$). Finally, we also present other notions of traitor tracing, and discuss how they can be build in a generic manner from our base embedded identity TT scheme.

Federated Learning (FL) enables a large number of users to jointly learn a shared machine learning (ML) model, coordinated by a centralized server, where the data is distributed across multiple devices. This approach enables the server or users to train and learn an ML model using gradient descent, while keeping all the training data on users' devices. We consider training an ML model over a mobile network where user dropout is a common phenomenon. Although federated learning was aimed at reducing data privacy risks, the ML model privacy has not received much attention.

In this work, we present PrivFL, a privacy-preserving system for training (predictive) linear and logistic regression models and oblivious predictions in the federated setting, while guaranteeing data and model privacy as well as ensuring robustness to users dropping out in the network. We design two privacy-preserving protocols for training linear and logistic regression models based on an additive homomorphic encryption (HE) scheme and an aggregation protocol. Exploiting the training algorithm of federated learning, at the core of our training protocols is a secure multiparty global gradient computation on alive users' data. We analyze the security of our training protocols against semi-honest adversaries. As long as the aggregation protocol is secure under the aggregation privacy game and the additive HE scheme is semantically secure, PrivFL guarantees the users' data privacy against the server, and the server's regression model privacy against the users. We demonstrate the performance of PrivFL on real-world datasets and show its applicability in the federated learning system.

The adoption of deep neural networks for profiled side-channel attacks provides different capabilities for leakage detection of secure products. Research papers provide a variety of arguments with respect to model interpretability and the selection of adequate hyper-parameters for each target under evaluation. When training a neural network for side-channel leakage classification, it is expected that the trained model is able to implement an approximation function that can detect leaking side-channel samples and, at the same time, be insensible to noisy (or non-leaking) samples. This is basically a generalization situation where the model can identify main representations learned from the training set in a separate test set. Very few understanding has been achieved in order to demonstrate if a trained model is actually generalizing for the current side-channel problem. In this paper, we provide guidelines for a correct interpretation of model's generalization in side-channel analysis. We detail how class probabilities provided by the output layer are very informative for the understanding of generalization and how they can be used as an important validation metric. Moreover, we demonstrate that ensemble learning based on averaged class probabilities improves the generalization of neural networks in side-channel attacks.

Round complexity is one of the fundamental problems in zero-knowledge proof systems. Non-malleable zero-knowledge (NMZK) protocols are zero-knowledge protocols that provide security even when man-in-the-middle adversaries interact with a prover and a verifier simultaneously. It is known that constant-round public-coin NMZK Arguments for NP can be constructed by assuming the existence of collision-resistant hash functions (Pass and Rosen STOC'05) and the four-round private-coin NMZK Arguments for NP can be constructed in the plain model by assuming the existence of one-way functions (Goyal, Richelson, Rosen and Vald FOCS'14 and Ciampi, Ostrovsky, Siniscalchi and Visconti TCC'17).

In this paper, we present a six-round public-coin NMZK argument of knowledge system assuming the existence of collision-resistant hash functions and a three-round private-coin NMZK argument system from multi-collision resistance of hash functions assumption in the keyless setting.

Securing Neural Network (NN) computations through the use of Fully Homomorphic Encryption (FHE) is the subject of a growing interest in both communities. Among different possible approaches to that topic, our work focuses on applying FHE to hide the model of a neural network-based system in the case of a plain input. In this paper, using the TFHE homomorphic encryption scheme, we propose an efficient fully homomorphic method for an argmin computation on an arbitrary number of encrypted inputs and an asymptotically faster - though levelled - equivalent scheme. Using these schemes and a unifying framework for LWE-based homomorphic encryption schemes (Chimera), we implement a very time-wise efficient, homomorphic speaker recognition scheme using the neural-based embedding system VGGVox. This work can be generalized to all other similar Euclidean embedding-based recognition systems. While maintaining the best-of-class classification rate of the VGGVox system, we implement a speaker-recognition system that can classify a speech sample as coming from one of a 100 hidden model speakers in less than one second.

Protection of intellectual property (IP) cores is one of the most practical security concern for modern integrated circuit (IC) industry. Albeit being well-studied from a practical perspective, the problem of safeguarding gate-level netlists from IP-theft is still an open issue. State-of-the-art netlist protection schemes, popularly known as logic locking, are mostly ad-hoc and their security claims are based on experimental evidences and the power of heuristics used for security evaluation. Observing this fact, in this paper we propose a novel logic locking approach, for which the security claims are based on the hardness of well-studied cryptographic primitives. More precisely, for the first time we show that the mapping realized by a circuit netlist (or at least a part of it) can be hidden inside a block cipher by setting a proper secret key. Moreover, this hiding scheme can be realized in a systematic manner with fairly simple heuristics. We claim that extracting the actual mapping is equivalent to a key recovery attack on the cipher, which is believed to be hard for standard block ciphers. The proposed scheme also attains SAT attack resistance directly from the block ciphers which are known to be SAT-hard, in general. Experimental evaluation on ISCAS-85 benchmarks establishes that even for small circuits like C17 (having 6 gates), the proposed approach can successfully throttle SAT-attacks. Further, we argue that the hiding a circuit inside a block cipher is interesting by its own from a theoretical perspective, and may have several useful applications in the domain of security.

We present modifications to the MPC system SCALE-MAMBA to enable the evaluation of garbled circuit (GC) based MPC functionalities and Linear Secret Sharing (LSSS) based MPC functionalities along side each other. This allows the user to switch between different MPC paradigms to achieve the best performance. To do this we present modifications to the GC-based MPC protocol of Hazay et al. (Asiacrypt 2017) (to enable it to support reactive computation), and combine different aspects of their pre-processing phase with those of Wang et al. (CCS 2017), in order to optimize our pre-processing protocols. We also give a more efficient method for producing daBits (double authenticated Bits) than that presented in the work of Rotaru and Wood (ePrint 2019). Finally, we examine how the functionality can be integrated within the existing MPC framework SCALE-MAMBA

Recently, Lyubashevsky & Seiler (Eurocrypt 2018) showed that small polynomials in the cyclotomic ring $Z_q[X]/(X^n+1)$, where $n$ is a power of two, are invertible under special congruence conditions on prime modulus $q$. This result has been used to prove certain security properties of lattice-based constructions against unbounded adversaries. Unfortunately, due to the special conditions, working over the corresponding cyclotomic ring does not allow for efficient use of the Number Theoretic Transform (NTT) algorithm for fast multiplication of polynomials and hence, the schemes become less practical.

In this paper, we present how to overcome this limitation by analysing zeroes in the Chinese Remainder (or NTT) representation of small polynomials. As a result, we provide upper bounds on the probabilities related to the (non)-existence of a short vector in a random module lattice with no assumptions on the prime modulus. We apply our results, along with the generic framework by Kiltz et al. (Eurocrypt 2018), to a number of lattice-based Fiat-Shamir signatures so they can both enjoy tight security in the quantum random oracle model and support fast multiplication algorithms (at the cost of slightly larger public keys and signatures), such as the Bai-Galbraith signature scheme (CT-RSA 2014), Dilithium-QROM (Kiltz et al., Eurocrypt 2018) and qTESLA (Alkim et al., PQCrypto 2017). Our techniques can also be applied to prove that recent commitment schemes by Baum et al. (SCN 2018) are statistically binding with no additional assumptions on $q$.

A hash function family is called correlation intractable if for all sparse relations, it hard to find, given a random function from the family, an input output pair that satisfies the relation. Correlation intractability (CI) captures a strong Random Oracle like property of hash functions. In particular, when security holds for all sparse relations, CI suffices for guaranteeing the soundness of the Fiat-Shamir transformation from any constant round, statistically sound interactive proof to a non-interactive argument. In this paper, based on the method proposed by Chris Peikert and Sina Shiehian, we construct a hash family that is computationally correlation intractable for any polynomially bounded size circuits based on Learning with Errors Over Rings (RLWE) with polynomial approximation factors and Short Integer Solution problem over modules (MSIS), and a hash family that is somewhere statistically intractable for any polynomially bounded size circuits based on RLWE. Similarly, our construction combines two novel ingredients: a correlation intractable hash family for log depth circuits based on RLWE, and a bootstrapping transform that uses leveled fully homomorphic encryption (FHE) to promote correlation intractability for the FHE decryption circuit on arbitrary circuits. Our construction can also be instantiated in two possible modes, yielding a NIZK that is either computationally sound and statistically zero knowledge in the common random string model, or vice-versa in common reference string model. The proposed scheme is much more efficient.

Contemporary research in symbolic formal verification has led to confirming security guarantees (as well as finding attacks) in secure channel protocols such as TLS and Signal. However, formal verification in general has not managed to significantly exit the academic bubble. Verifpal is new software for verifying the security of cryptographic protocols that aims is to work better for real-world practitioners, students and engineers without sacrificing comprehensive formal verification features. In order to achieve this, Verifpal introduces a new, intuitive language for modeling protocols that is easier to write and understand than the languages employed by existing tools. Its formal verification paradigm is also designed explicitly to provide protocol modeling that avoids user error. By modeling principals explicitly and with discrete states, Verifpal models are able to be written in a way that reflects how protocols are described in the real world. At the same time, Verifpal is able to model protocols under an active attacker with unbounded sessions and fresh values, and supports queries for advanced security properties such as forward secrecy or key compromise impersonation. Verifpal has already been used to verify security properties for Signal, Scuttlebutt, TLS 1.3 and other protocols. It is a community-focused project, and available under a GPLv3 license.

Proof-of-stake (PoS) blockchain protocols are emerging as one of the most promising alternative to the energy-consuming proof-of-work protocols. However, one particularly critical threat in the PoS setting is the well-known long-range attacks caused by secret key leakage (LRSL attack). Specifically, an adversary can attempt to corrupt the secret keys corresponding to accounts possessing substantial stake at some past moment such that double-spend or erase past transactions, violating the fundamental persistence property of blockchain. Puncturable signatures, introduced by Bellare et al. (Eurocrypt 2016), provide a satisfying solution to construct practical proof-of-stake blockchain protocols resilient to LRSL attack, despite of the fact that existent constructions are not efficient enough for practical deployments.

In this paper, we provide a systematic study of puncturable signatures and explore its applications in proof-of-stake blockchain protocol. The puncturing functionality we desire is for a particular part of message, like prefix, instead of the whole message. We formalize a security model that allows adversary for adaptive signing and puncturing queries, and show a construction with efficient puncturing operation based on Bloom filter data structure and strong Diffie-Hellman assumption. In order to further improve efficiency of puncturing, we introduce another primitive, called tag-based puncturable signature and present a generic construction based on hierarchical identity based signature scheme. Finally, we use puncturable signature to construct practical proof-of-stake blockchain protocols that are resilient to LRSL attack, while previously forward secure signature is used to immunize this attack. We implement our scheme and provide experimental results showing that in comparison with forward secure signatures, our constructions of puncturable signature perform substantially better on signature size, signing and verification efficiency, significantly on key update efficiency.

In their celebrated work, Groth and Sahai [EUROCRYPT'08, SICOMP' 12] constructed non-interactive zero-knowledge (NIZK) proofs for general bilinear group arithmetic relations, which spawned the entire subfield of structure-preserving cryptography. This branch of the theory of cryptography focuses on modular design of advanced cryptographic primitives. Although the proof systems of Groth and Sahai are a powerful toolkit, their efficiency hits a barrier when the size of the witness is large, as the proof size is linear in that of the witness.

In this work, we revisit the problem of proving knowledge of general bilinear group arithmetic relations in zero-knowledge. Specifically, we construct a succinct zero-knowledge argument for such relations, where the communication complexity is logarithmic in the integer and source group components of the witness. Our argument has public-coin setup and verifier and can therefore be turned non-interactive using the Fiat-Shamir transformation in the random oracle model. For the special case of non-bilinear group arithmetic relations with only integer unknowns, our system can be instantiated in non-bilinear groups. In many applications, our argument system can serve as a drop-in replacement of Groth-Sahai proofs, turning existing advanced primitives in the vast literature of structure-preserving cryptography into practically efficient systems with short proofs.

We present a new 4-move special honest-verifier zero-knowledge proof of knowledge system for proving that a vector of Pedersen commitments opens to a so-called "one-hot" vector (i.e., to a vector from the standard orthonormal basis) from $\mathbb{Z}_p^n$. The need for such proofs arises in the contexts of symmetric private information retrieval (SPIR), end-to-end verifiable voting (E2E), and privacy-preserving data aggregation and analytics, among others. The key insight underlying the new protocol is a simple observation regarding the paucity of roots of polynomials of bounded degree over a finite field. The new protocol is fast and yields succinct proofs: For vectors of length $n$, the prover evaluates $\Theta(\lg{n})$ group operations plus $\Theta(n)$ field operations and sends just $\Theta(\lg{n})$ group and field elements, while the verifier evaluates one $n$-base multiexponentiation plus $\Theta(\lg{n})$ additional group operations and sends just $2(\lambda+\lg{n})$ bits to obtain a soundness error less than $2^{-\lambda}$. (A 5-move variant of the protocol reduces prover upload to just $2\lambda+\lg{n}$ bits for the same soundness error.) We have implemented both our new protocol and its closest competitors from the literature; in accordance with our analytic results, experiments confirm that the new protocols handily outperform existing protocols for all but the shortest of vectors (roughly, for vectors with more than 16-32 elements).

Event date: 10 February to 14 February 2020
Submission deadline: 17 September 2019
Notification: 15 November 2019