International Association
for Cryptologic Research

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

In this paper we present our observations about NIST's Compression estimate test given in SP-800 90B. We observe that steps 4 and 7 of the test may be re-framed to gain efficiency. Based on our observations, we propose a modified algorithm for the test which is twice as fast as the NIST's algorithm. We further claim that the values of probability and min-entropy in the example given for the test are incorrect. We also provide computational evidence in support of this claim.

Attribute-based encryption (ABE) is an advanced cryptographic tool and useful to build various types of access control systems. Toward the goal of making ABE more practical, we propose key-policy (KP) and ciphertext-policy (CP) ABE schemes, which first support unbounded sizes of attribute sets and policies with negation and multi-use of attributes, allow fast decryption, and are fully secure under a standard assumption, simultaneously. The proposed schemes are more expressive than previous schemes and efficient enough. We also implement our schemes in 128-bit security level and present their benchmarks for an ordinary personal computer and smartphones. They show that all algorithms run in one second with the personal computer when they handle any policy or attribute set with one hundred attributes.

Ratcheting communication strengthens privacy, specifically in the presence of internal state exposures or random coin corruptions. This is called post-compromise security. There have been several such secure protocols proposed in the last few years. The strongest level of security comes with a high cost, because of the need for HIBE or at least public-key cryptography.

In this paper, we first design a lightweight protocol called liteARCAD which is solely based on symmetric cryptography, hence only forward secure.

We then present a generic hybrid protocol allowing to compose any two protocols so that the sender can select which of the two protocols to use. When composing liteARCAD and a post-compromise secure protocol, the sender can decide to ratchet or not. For instance, the sender can ratchet once a while, or after letting his device unattended. When doing so with infrequent ratchet, we obtain the strongest security at the price of efficient symmetric cryptography.

We then propose the notion of security awareness. This lets a sender learns, after a while, if his message was safely received (i.e. if it was received and if no adversary can decrypt it, except from trivial attacks) and that no finished active attack occurred (i.e. active attack must continue forever or be detected). We finally propose a generic strengthening to add security awareness to any protocol.

While fair exchange of goods is known to be impossible without assuming a trusted party, smart contracts in cryptocurrencies forgo such parties by assuming trust in the currency system. They allow a seller to sell a digital good, which the buyer will obtain if and only if she pays. Zero-knowledge contingent payments (zkCP) show that, despite the limited expressiveness of its scripting language, this is even possible in Bitcoin by using zero-knowledge proofs.

At CCS'17, Campanelli, Gennaro, Goldfeder and Nizzardo showed that the zkCP protocol was flawed, in that the buyer could obtain information about the good without paying. They proposed countermeasures to repair zkCP and moreover observed that zkCP cannot be used when a service is sold. They introduce the notion of ZK contingent payments for services and give an instantiation based on a witness-indistinguishable (WI) proof system.

We show that the main countermeasures they proposed are not sufficient and present an attack against their fixed zkCP scheme. We also show that their realization of zkCP for services is insecure, as the buyer could learn the desired information (i.e., whether the service was provided) without paying; in particular, we show that WI of the used proof system is not enough.

In somewhat homomorphic encryption schemes (e.g. B/FV, BGV) the size of ciphertexts and the execution performance of homomorphic operations depends heavily on the multiplicative depth. The multiplicative depth is the maximal number of consecutive multiplications for which an homomorphic encryption scheme was parameterized. In this work we propose an improved multiplicative depth minimization heuristic. In particular, a new circuit rewriting operator is introduced, the so called cone rewrite operator. The results we obtain using the new method are relevant in terms of accuracy and performance. Smaller multiplicative depths for a benchmark of Boolean circuits are obtained when compared to a previous work found in the literature. In average, the multiplicative depth is highly improved and the new heuristic execution time is significantly lower. The proposed rewrite operator and heuristic are not limited to Boolean circuits, but can also be used for arithmetic circuits.

Over the last few years there has been a surge of new cryptographic results, including laconic oblivious transfer, (anonymous/ hierarchical) identity-based encryption, trapdoor functions, chosen-ciphertext security transformations, designated-verifier zero knowledge proofs, due to a beautiful framework recently introduced in the works of Cho et al. [Crypto 2017], and D{\"{o}}ttling and Garg [Crypto 2017]. The primitive of one-way function with encryption (OWFE) and its relatives (chameleon encryption, one-time signatures with encryption, hinting PRGs, trapdoor hash encryption, batch encryption) have been a centerpiece in all these results.

While there exist multiple realizations of OWFE (and its relatives) from a variety of assumptions such as CDH, Factoring, and LWE, all such constructions fall under the same general ``missing block" framework. Although this framework has been instrumental in opening up a new pathway towards various cryptographic functionalities via the abstraction of OWFE (and its relatives), it has been accompanied with undesirable inefficiencies that has inhibited a much wider adoption in many practical scenarios. Motivated by the surging importance of the OWFE abstraction (and its relatives), a natural question to ask is whether the existing approaches can be diversified to not only obtain more constructions from different assumptions, but also in developing newer frameworks. We believe answering this question will eventually lead to important and previously unexplored performance trade-offs in the overarching applications of this novel cryptographic paradigm.

In this work, we propose a new ``accumulation-style" framework for building a new class of OWFE as well as hinting PRG constructions with a special focus on achieving shorter ciphertext size and shorter public parameter size (respectively). Such performance improvements parlay into shorter parameters in their corresponding applications. Briefly, we explore the following performance trade-offs --- (1) for OWFE, our constructions outperform in terms of ciphertext size as well as encryption time, but this comes at the cost of larger evaluation and setup times, (2) for hinting PRGs, our constructions provide a rather dramatic trade-off between evaluation time versus parameter size, with our construction leading to significantly shorter public parameter size. We also provide concrete performance measurements for our constructions and compare them with existing approaches. We believe highlighting such trade-offs will lead to a wider adoption of these abstractions in a practical sense.