International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News

Updates on the COVID-19 situation are on the Announcement channel.

Here you can see all recent updates to the IACR webpage. These updates are also available:

RSS symbol icon
via RSS feed
Twitter bird icon
via Twitter
Weibo icon
via Weibo
Facebook icon
via Facebook

05 September 2019

Lilya Budaghyan, Tor Helleseth, Nikolay Kaleyski
ePrint Report ePrint Report
The binomial $B(x) = x^3 + \beta x^{36}$ (where $\beta$ is primitive in $\mathbb{F}_{2^4}$) over $\mathbb{F}_{2^{10}}$ is the first known example of an Almost Perfect Nonlinear (APN) function that is not CCZ-equivalent to a power function, and has remained unclassified into any infinite family of APN functions since its discovery in 2006. We generalize this binomial to an infinite family of APN quadrinomials of the form $x^3 + a (x^{2^i+1})^{2^k} + b x^{3 \cdot 2^m} + c (x^{2^{i+m}+2^m})^{2^k}$ from which $B(x)$ can be obtained by setting $a = \beta$, $b = c = 0$, $i = 3$, $k = 2$. We show that for any dimension $n = 2m$ with $m$ odd and $3 \nmid m$, setting $(a,b,c) = (\beta, \beta^2, 1)$ and $i = m-2$ or $i = (m-2)^{-1} \mod n$ yields an APN function, and verify that for $n = 10$ the quadrinomials obtained in this way for $i = m-2$ and $i = (m-2)^{-1} \mod n$ are CCZ-inequivalent to each other, to $B(x)$, and to any other known APN function over $\mathbb{F}_{2^{10}}$.
Expand
Louis Tajan, Dirk Westhoff, Frederik Armknecht
ePrint Report ePrint Report
In the area of cloud computing, judging the fulfillment of service-level agreements on a technical level is gaining more and more importance. To support this we introduce privacy preserving set relations as inclusiveness and disjointness based on Bloom filters. We propose to compose them in a slightly different way by applying a keyed hash function. Besides discussing the correctness of the set relations, we analyze how this impacts the privacy of the sets content as well as providing privacy on the sets cardinality. Indeed, our solution proposes to bring another layer of privacy on the sizes. We are in particular interested how the overlapping bits of a Bloom filter impact the privacy level of our approach. We concretely apply our solution to a use case of cloud security audit on access control and present our results with real-world parameters.
Expand

02 September 2019

Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, Thomas Peyrin
ePrint Report ePrint Report
In this article, we propose two new families of very lightweight and efficient authenticated encryption with associated data (AEAD) modes, Romulus and Remus, that provide security beyond the birthday bound with respect to the block-length $n$. The former uses a tweakable block cipher (TBC) as internal primitive and can be proven secure in the standard model. The later uses a block cipher (BC) as internal primitive and can be proven secure in the ideal cipher model. Both our modes allow to switch very easily from nonce-respecting to nonce-misuse scenario.

Previous constructions, such as ThetaCB, are quite computationally efficient, yet needing a large memory for implementation, which makes them unsuitable for platforms where lightweight cryptography should play a key role. Romulus and Remus break this barrier by introducing a new architecture evolved from a BC mode COFB. They achieve the best of what can be possible with TBC -- the optimal computational efficiency (rate-1 operation) and the minimum state size of a TBC mode (i.e., $(n+t)$-bit for $n$-bit block, $t$-bit tweak TBC), with almost equivalent provable security as ThetaCB. Actually, our comparisons show that both our designs present superior performances when compared to all other recent lightweight AEAD modes, being BC-based, TBC-based or sponge-based, in the nonce-respecting or nonce-misuse scenario.

We eventually describe how to instantiate Romulus and Remus modes using the Skinny lightweight tweakable block cipher proposed at CRYPTO 2016, including the hardware implementation results.
Expand
Jing Yang, Thomas Johansson, Alexander Maximov
ePrint Report ePrint Report
SNOW 3G is a stream cipher designed in 2006 by ETSI/SAGE, serving in 3GPP as one of the standard algorithms for data confidentiality and integrity protection. It is also included in the 4G LTE standard. In this paper we derive vectorized linear approximations of the finite state machine of SNOW 3G. In particular, we show one 24-bit approximation with a bias around $2^{-37}$ and one byte-oriented approximation with a bias around $2^{-40}$. We then use the approximations to launch attacks on SNOW 3G. The first approximation is used in a distinguishing attack resulting in an expected complexity of $2^{172}$ and the second one can be used in a standard fast correlation attack resulting in key recovery in an expected complexity of $2^{177}$. If the key length in SNOW 3G would be increased to 256 bits, the results show that there are then academic attacks on such a version faster than the exhaustive key search.
Expand
Sanjam Garg, Mohammad Hajiabadi, Rafail Ostrovsky
ePrint Report ePrint Report
Substantial work on trapdoor functions (TDFs) has led to many powerful notions and applications. However, despite tremendous work and progress, all known constructions have prohibitively large public keys.

In this work, we introduce new techniques for realizing so-called range-trapdoor hash functions with short public keys. This notion, introduced by Döttling et al. [Crypto 2019], allows for encoding a range of indices into a public key in a way that the public key leaks no information about the range, yet an associated trapdoor enables recovery of the corresponding input part. We give constructions of range-trapdoor hash functions, where for a range $I$ the public key consists of $O(n)$ group elements, improving upon $O(n |I|)$ achieved by Döttling et al. Moreover, by designing our evaluation algorithm in a special way involving Toeplitz matrix multiplication and by showing how to perform fast-Fourier transforms in the exponent, we arrive at $O(n \log n)$ group operations for evaluation, improving upon $O(n^2)$, required of previous constructions. Our constructions rely on power-DDH assumptions in pairing-free groups. As applications of our results we obtain

(1) The first construction of (rate-1) lossy TDFs with public keys consisting of a linear number of group elements (without pairings).

(2) Rate-1 string OT with receiver communication complexity of $O(n)$ group elements, where $n$ is the sender's message size, improving upon $O(n^2)$ [Crypto 2019]. This leads to a similar result in the context of private-information retrieval (PIR).

(3) Semi-compact homomorphic encryption for branching programs: A construction of homomorphic encryption for branching programs, with ciphertexts consisting of $O(\lambda n d)$ group elements, improving upon $O(\lambda^2 n d)$. Here $\lambda$ denotes the security parameter, $n$ the input size and $d$ the depth of the program.
Expand
Marcel Armour, Bertram Poettering
ePrint Report ePrint Report
This work introduces Algorithm Substitution Attacks (ASAs) on message authentication schemes. In light of revelations concerning mass surveillance, ASAs were initially introduced by Bellare, Paterson and Rogaway as a novel attack class against the confidentiality of encryption schemes. Such an attack replaces one or more of the regular scheme algorithms with a subverted version that aims to reveal information to an adversary (engaged in mass surveillance), while remaining undetected by users. While most prior work focused on subverting encryption systems, we study options to subvert symmetric message authentication protocols. In particular we provide powerful generic attacks that apply e.g. to HMAC or Carter-Wegman based schemes, inducing only a negligible implementation overhead. As subverted authentication can act as an enabler for subverted encryption (software updates can be manipulated to include replacements of encryption routines), we consider attacks of the new class highly impactful and dangerous.
Expand
David W. Archer, Jose Manuel Calderon Trilla, Jason Dagit, Alex J. Malozemoff, Yuriy Polyakov, Kurt Rohloff, Gerard Ryan
ePrint Report ePrint Report
Homomorphic Encryption (HE) is an emerging technnology that enables computing on data while the data is encrypted. A major challenge with homomorphic encryption is that it takes extensive expert knowledge to design meaningful and useful programs that are constructed from atomic HE operations.

We present RAMPARTS to address this challenge. RAMPARTS provides an environment for developing HE applications in Julia, a high-level language, the same way as ``cleartext'' applications are typically written in Julia. RAMPARTS makes the following three contributions. First, we use symbolic execution to automate the construction of an optimized computation circuit where both the circuit size and multiplicative depth are chosen by the compiler. Second, RAMPARTS automatically selects the HE parameters for the generated circuit, which is typically done manually by an HE expert. Third, RAMPARTS automatically selects the plaintext encoding for input values, and performs input and output data transformations. These three operations are not easily performed by programmers who are not HE experts. Thus, RAMPARTS makes HE more widely available and usable by the the population of programmers.

We compare our approach with Cingulata, the only previously known system that automatically generates circuits for HE computations. The HE circuits generated by RAMPARTS are significantly more efficient than the circuits compiled by Cingulata. For instance, our runtimes for key generation/circuit compilation and all online operations are more than one order of magnitude lower for a sample image processing application used for performance evaluation in our study.
Expand
Marcel Armour, Bertram Poettering
ePrint Report ePrint Report
This work introduces a new class of Algorithm Substitution Attack (ASA) on Symmetric Encryption Schemes. ASAs were introduced by Bellare, Paterson and Rogaway in light of revelations concerning mass surveillance. An ASA replaces an encryption scheme with a subverted version that aims to reveal information to an adversary engaged in mass surveillance, while remaining undetected by users. Previous work posited that a particular class of AEAD scheme (satisfying certain correctness and uniqueness properties) is resilient against subversion. Many if not all real-world constructions - such as GCM, CCM and OCB - are members of this class. Our results stand in opposition to those prior results. We present a potent ASA that generically applies to any AEAD scheme, is undetectable in all previous frameworks and which achieves successful exfiltration of user keys. We give even more efficient non-generic attacks against a selection of AEAD implementations that are most used in practice.In contrast to prior work, our new class of attack targets the decryption algorithm rather than encryption. We argue that this attack represents an attractive opportunity for a mass surveillance adversary. Our work serves to refine the ASA model and contributes to a series of papers that raises awareness and understanding about what is possible with ASAs.
Expand
Majid Khabbazian, Tejaswi Nadahalli, Roger Wattenhofer
ePrint Report ePrint Report
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.
Expand

29 August 2019

Philipp Schindler, Aljosha Judmayer, Nicholas Stifter, Edgar Weippl
ePrint Report ePrint Report
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.
Expand
Sam Kim, David J. Wu
ePrint Report ePrint Report
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.
Expand
Marc Fyrbiak, Sebastian Wallat, Sascha Reinhard, Nicolai Bissantz, Christof Paar
ePrint Report ePrint Report
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.
Expand
Toi Tomita, Wakaha Ogata adn Kaoru Kurosawa, Ryo Kuwayama
ePrint Report ePrint Report
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.
Expand
Nirvan Tyagi, Ian Miers, Thomas Ristenpart
ePrint Report ePrint Report
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.
Expand
Rishab Goyal, Venkata Koppula, Brent Waters
ePrint Report ePrint Report
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.
Expand
Kalikinkar Mandal, Guang Gong
ePrint Report ePrint Report
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.
Expand
Guilherme Perin
ePrint Report ePrint Report
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.
Expand
Zhenbin Yan, Yi Deng
ePrint Report ePrint Report
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.
Expand
Martin Zuber, Sergiu Carpov, Renaud Sirdey
ePrint Report ePrint Report
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.
Expand
Akashdeep Saha, Sayandeep Saha, Debdeep Mukhopadhyay, Bhargab Bikram Bhattacharya
ePrint Report ePrint Report
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.
Expand
◄ Previous Next ►