Subscribe to IACR Eprint feed
Updated: 5 hours 43 min ago

ACPC: Efficient revocation of pseudonym certificates using activation codes

Mon, 04/09/2018 - 09:14
Vehicular communication (V2X) technologies allow vehicles to exchange information about the road conditions and their own status, and thereby enhance transportation safety and efficiency. For broader deployment, however, such technologies are expected to address security and privacy concerns, preventing abuse by users and by the system's entities. In particular, the system is expected to enable the revocation of malicious vehicles, e.g., in case they send invalid information to their peers or to the roadside infrastructure; it should also prevent the system from being misused for tracking honest vehicles.Both features are enabled by Vehicular Public Key Infrastructure (VPKI) solutions such as Security Credential Management Systems (SCMS), one of the leading candidates for protecting V2X communication in the United States. Unfortunately, though, SCMS's original revocation mechanism can lead to large Certification Revocation Lists (CRLs), which in turn impacts the bandwidth usage and processing overhead of the system. In this article, we propose a novel design called Activation Codes for Pseudonym Certificates (ACPC), which can be integrated into SCMS to address this issue. Our proposal is based on activation codes, short bitstrings without which certificates previously issued to a vehicle cannot be used by the latter, which are periodically distributed to non-revoked vehicles using an efficient broadcast mechanism. As a result, the identifiers of the corresponding certificates do no need to remain on the CRL for a long time, reducing the CRLs' size and streamlining their distribution and verification of any vehicle's revocation status. Besides describing ACPC in detail, we also compare it to similar-purpose solutions such as Issue First Activate Later (IFAL) and Binary Hash Tree based Certificate Access Management (BCAM).This analysis shows that our proposal not only brings security improvements (e.g., in terms of resilience against colluding system authorities), but also leads to processing and bandwidth overheads that are orders of magnitude smaller than those observed in the state of the art.

PPAD: Privacy Preserving Group-Based ADvertising in Online Social Networks

Mon, 04/09/2018 - 09:12
Services provided as free by Online Social Networks (OSN) come with privacy concerns. Users' information kept by OSN providers are vulnerable to the risk of being sold to the advertising firms. To protect user privacy, existing proposals utilize data encryption, which prevents the providers from monetizing users' information. Therefore, the providers would not be financially motivated to establish secure OSN designs based on users' data encryption. Addressing these problems, we propose the first Privacy Preserving Group-Based Advertising (PPAD) system that gives monetizing ability for the OSN providers. PPAD performs profile and advertisement matching without requiring the users or advertisers to be online, and is shown to be secure in the presence of honest but curious servers that are allowed to create fake users or advertisers. We also present advertisement accuracy metrics under various system parameters providing a range of security-accuracy trade-offs.

DeepMarks: A Digital Fingerprinting Framework for Deep Neural Networks

Mon, 04/09/2018 - 09:05
This paper proposes DeepMarks, a novel end-to-end framework for systematic fingerprinting in the context of Deep Learning (DL). Remarkable progress has been made in the area of deep learning. Sharing the trained DL models has become a trend that is ubiquitous in various fields ranging from biomedical diagnosis to stock prediction. As the availability and popularity of pre-trained models are increasing, it is critical to protect the Intellectual Property (IP) of the model owner. DeepMarks introduces the first fingerprinting methodology that enables the model owner to embed unique fingerprints within the parameters (weights) of her model and later identify undesired usages of her distributed models. The proposed framework embeds the fingerprints in the Probability Density Function (pdf) of trainable weights by leveraging the extra capacity available in contemporary DL models. DeepMarks is robust against fingerprints collusion as well as network transformation attacks, including model compression and model fine-tuning. Extensive proof-ofconcept evaluations on MNIST and CIFAR10 datasets, as well as a wide variety of deep neural networks architectures such as Convolutional Neural Networks (CNNs) and Wide Residual Networks (WRNs), corroborate the effectiveness and robustness of DeepMarks framework

Revisiting Proxy Re-Encryption: Forward Secrecy, Improved Security, and Applications

Mon, 04/09/2018 - 08:56
We revisit the notion of proxy re-encryption (PRE), an enhanced public-key encryption primitive envisioned by Blaze et al. (Eurocrypt'98) and formalized by Ateniese et al. (NDSS'05) for delegating decryption rights from a delegator to a delegatee using a semi-trusted proxy. PRE notably allows to craft re-encryption keys in order to equip the proxy with the power of transforming ciphertexts under a delegator's public key to ciphertexts under a delegatee's public key, while not learning anything about the underlying plaintexts. We study an attractive cryptographic property for PRE, namely that of forward secrecy. In our forward-secret PRE (fs-PRE) definition, the proxy periodically evolves the re-encryption keys and permanently erases old versions while the delegator's public key is kept constant. As a consequence, ciphertexts for old periods are no longer re-encryptable and, in particular, cannot be decrypted anymore at the delegatee's end. Moreover, delegators evolve their secret keys too, and, thus, not even they can decrypt old ciphertexts once their key material from past periods has been deleted. This, as we will discuss, directly has application in short-term data/message-sharing scenarios. Technically, we formalize fs-PRE. Thereby, we identify a subtle but significant gap in the well-established security model for conventional PRE and close it with our formalization (which we dub fs-PRE^+). We present the first provably secure and efficient constructions of fs-PRE as well as PRE (implied by the former) satisfying the strong fs-PRE^+ and PRE^+ notions, respectively. All our constructions are instantiable in the standard model under standard assumptions and our central building block are hierarchical identity-based encryption (HIBE) schemes that only need to be selectively secure.

Continuous Non-Malleable Codes in the 8-Split-State Model

Mon, 04/09/2018 - 05:15
Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography. In particular, progress in the study of non-malleable codes and the related notion of non-malleable extractors has led to new insights and progress on even more fundamental problems like the construction of multi-source randomness extractors. A large body of the recent work has focused on various constructions of non-malleable codes in the split-state model. Many variants of NMCs have been introduced in the literature i.e. strong NMCs, super strong NMCs and continuous NMCs. The most general, and hence also the most useful notion among these is that of continuous non-malleable codes, that allows for continuous tampering by the adversary. We present the first efficient information-theoretically secure continuously non-malleable code in the constant split-state model, where there is a self-destruct mechanism which ensures that the adversary loses access to tampering after the first failed decoding. We believe that our main technical result could be of independent interest and some of the ideas could in future be used to make progress on other related questions.

Generic Low-Latency Masking in Hardware

Mon, 04/09/2018 - 03:56
In this work, we introduce a generalized concept for low-latency masking that is applicable to any implementation and protection order, and (in its most extreme form) does not require on-the-fly randomness. The main idea of our approach is to avoid collisions of shared variables in nonlinear circuit parts and to skip the share compression. We show the feasibility of our approach on a full implementation of a one-round unrolled Ascon variant and on an AES S-box case study. Additionally, we discuss possible trade-offs to make our approach interesting for practical implementations. As a result, we obtain a first-order masked AES S-box that is calculated in a single clock cycle with rather high implementation costs (60.7 kGE), and a two-cycle variant with much less implementation costs (6.7 kGE). The side-channel resistance of our Ascon S-box designs up to order three are then verified using the formal analysis tool of [BGI+18]. Furthermore, we introduce a taint checking based verification approach that works specifically for our low-latency approach and allows us to verify large circuits like our low-latency AES S-box design in reasonable time.

Foundations of State Channel Networks

Sun, 04/08/2018 - 20:05
One of the main challenges that hinder further adaption of decentralized cryptocurrencies is scalability. Because current cryptocurrencies require that all transactions are processed and stored on a distributed ledger -- the so-called blockchain -- transaction throughput is inherently limited. An important proposal to significantly improve scalability are off-chain protocols, where the massive amount of transactions is executed without requiring the costly interaction with the blockchain. Examples of off-chain protocols include payment channels and networks, which are currently deployed by popular cryptocurrencies such as Bitcoin and Ethereum. A further extension of payment networks envisioned for cryptocurrencies are so-called state channel networks. In contrast to payment networks that only support carrying out off-chain payments between users, state channel networks allow execution of arbitrary complex smart contracts. The main contribution of this work is to give the first full specification for general state channel networks. Moreover, we provide formal security definitions and develop security proofs showing that our construction satisfies security against powerful adversaries. An additional benefit of our construction over most existing payment networks is the use of channel virtualization, which further reduces latency and costs in complex channel networks.

Encryption Modes with Almost Free Message Integrity

Sun, 04/08/2018 - 11:29
We define a new mode of operation for block ciphers which in addition to providing confidentiality also ensures message integrity. In contrast, previously for message integrity a separate pass was required to compute a cryptographic message authentication code (MAC). The new mode of operation, called Integrity Aware Parallelizable Mode (IAPM), requires a total of m+1 block cipher evaluations on a plain-text of length m blocks. For comparison, the well known CBC (cipher block chaining) encryption mode requires m block cipher evaluations, and the second pass of computing the CBC-MAC essentially requires additional m+1 block cipher evaluations. As the name suggests, the new mode is also highly parallelizable.

Can We Overcome the $n \log n$ Barrier for Oblivious Sorting?

Wed, 04/04/2018 - 16:04
It is well-known that non-comparison-based techniques can allow us to sort $n$ elements in $o(n \log n)$ time on a Random-Access Machine (RAM). On the other hand, it is a long-standing open question whether (non-comparison-based) circuits can sort $n$ elements from the domain $[1..2^k]$ with $o(k n \log n)$ boolean gates. We consider weakened forms of this question: first, we consider a restricted class of sorting where the number of distinct keys is much smaller than the input length; and second, we explore Oblivious RAMs and probabilistic circuit families, i.e., computational models that are somewhat more powerful than circuits but much weaker than RAM. We show that Oblivious RAMs and probabilistic circuit families can sort $o(\log n)$-bit keys in $o(n \log n)$ time or $o(k n \log n)$ circuit complexity where $n$ is the input length. We also show that in the balls-and-bins model of sorting where each key may carry an opaque ball that can only be moved around atomically but cannot be computed upon, our result achieves optimality, in that any oblivious algorithm or probabilistic circuit family that sorts $n$ balls each with a $k$-bit key where $k = O(\log n)$ must incur at least $\Omega(n k)$ atomic movement operations on balls. Moreover, for any such $k = O(\log n)$, our upper bound is almost tight, up to only $O(\log \log n)$ factor. We extend our result to support the case when the keys are chosen from a large space but the number of distinct keys is small. Finally, we optimize the IO efficiency of our oblivious algorithms for RAMs --- we show that even the $1$-bit special case of our algorithm can solve open questions regarding whether there exist oblivious algorithms for tight compaction and selection in linear IO.

Faster Unbalanced Private Set Intersection

Wed, 04/04/2018 - 13:11
Protocols for Private Set Intersection (PSI) are important cryptographic primitives that perform joint operations on datasets in a privacy-preserving way. They allow two parties to compute the intersection of their private sets without revealing any additional information beyond the intersection itself. Unfortunately, PSI implementations in the literature do not usually employ the best possible cryptographic implementation techniques. This results in protocols presenting computational and communication complexities that are prohibitive, particularly in the case when one of the participants is a low-powered device and there are bandwidth restrictions. This paper builds on modern cryptographic engineering techniques and proposes optimizations for a promising one-way PSI protocol based on public-key cryptography. For the case when one of the parties holds a set much smaller than the other (a realistic assumption in many scenarios) we show that our improvements and optimizations yield a protocol that outperforms the communication complexity and the run time of previous proposals by around one thousand times.

Practical attacks against the Walnut digital signature scheme

Wed, 04/04/2018 - 12:37
Recently, NIST started the process of standardizing quantum- resistant public-key cryptographic algorithms. WalnutDSA, the subject of this paper, is one of the 20 proposed signature schemes that are being considered for standardization. Walnut relies on a one-way function called E-Multiplication, which has a rich algebraic structure. This paper shows that this structure can be exploited to launch several practical attacks against the Walnut cryptosystem. The attacks work very well in practice; it is possible to forge signatures and compute equivalent secret keys for the 128-bit and 256-bit security parameters submitted to NIST in less than a second and in less than a minute respectively.

HydRand: Practical Continuous Distributed Randomness

Wed, 04/04/2018 - 10:20
A reliable source of randomness is not only an essential building block in various cryptographic, security, and distributed systems protocols, but also plays an integral part in the design of many new blockchain proposals. Consequently, the topic of publicly-verifiable, bias-resistant and unpredictable randomness has recently enjoyed increased attention in a variety of scientific contributions, as well as projects from the industry. In particular random beacon protocols, which are aimed at continuous operation, can be a vital component for many current Proof-of-Stake based distributed ledger proposals. We improve upon existing random beacon approaches by introducing HydRand, a novel distributed protocol based on publicly-verifiable secret sharing (PVSS) to ensure unpredictability, bias-resistance, and public-verifiability of a continuous sequence of random beacon values. Furthermore, HydRand is able to provide guaranteed output delivery of randomness at regular and predictable intervals in the presence of adversarial behavior. In comparison to existing PVSS based approaches, our solution improves scalability by lowering the communication complexity from $ \mathcal{O}(n^3) $ to $ \mathcal{O}(n^2) $. Furthermore, we are the first to present a comparison of recently described schemes in the area of random beacon protocols.

Sliding-Window Correlation Attacks Against Encryption Devices with an Unstable Clock

Wed, 04/04/2018 - 10:19
Power analysis side channel attacks rely on aligned traces. As a counter-measure, devices can use a jittered clock to misalign the power traces. In this paper we suggest a way to overcome this counter-measure, using an old method of integrating samples over time followed by a correlation attack (Sliding Window CPA). We theoretically re-analyze this general method with characteristics of jittered clocks and show that it is stronger than previously believed. We show that integration of samples over a suitably chosen window size actually amplifies the correlation both with and without jitter - as long as multiple leakage points are present within the window. We then validate our analysis on a new data-set of traces measured on a board implementing a jittered clock. Our experiments show that the SW-CPA attack with a well-chosen window size is very successful against a jittered clock counter-measure and significantly outperforms previous suggestions, requiring a much smaller set of traces to correctly identify the correct key.

A formal model of Bitcoin transactions

Wed, 04/04/2018 - 07:37
We propose a formal model of Bitcoin transactions, which is sufficiently abstract to enable formal reasoning, and at the same time is concrete enough to serve as an alternative documentation to Bitcoin. We use our model to formally prove some well-formedness properties of the Bitcoin blockchain, for instance that each transaction can only be spent once. We release an open-source tool through which programmers can write transactions in our abstract model, and compile them into standard Bitcoin transactions.

Non-Malleable Secret Sharing

Tue, 04/03/2018 - 18:55
A number of works have focused on the setting where an adversary tampers with the shares of a secret sharing scheme. This includes literature on verifiable secret sharing, algebraic manipulation detection(AMD) codes, and, error correcting or detecting codes in general. In this work, we initiate a systematic study of what we call non-malleable secret sharing. Very roughly, the guarantee we seek is the following: the adversary may potentially tamper with all of the shares, and still, either the reconstruction procedure outputs the original secret, or, the original secret is ''destroyed'' and the reconstruction outputs a string which is completely ''unrelated'' to the original secret. Recent exciting work on non-malleable codes in the split-state model led to constructions which can be seen as 2-out-of-2 non-malleable secret sharing schemes. These constructions have already found a number of applications in cryptography. We investigate the natural question of constructing t-out-of-n non-malleable secret sharing schemes. Such a secret sharing scheme ensures that only a set consisting of t or more shares can reconstruct the secret, and, additionally guarantees non-malleability under an attack where potentially every share maybe tampered with. Techniques used for obtaining split-state non-malleable codes (or 2-out-of-2 non-malleable secret sharing) are (in some form) based on two-source extractors and seem not to generalize to our setting. Our first result is the construction of a t-out-of-n non-malleable secret sharing scheme against an adversary who arbitrarily tampers each of the shares independently. Our construction is unconditional and features statistical non-malleability. As our main technical result, we present t-out-of-n non-malleable secret sharing scheme in a stronger adversarial model where an adversary may jointly tamper multiple shares. Our construction is unconditional and the adversary is allowed to jointly-tamper subsets of up to (t-1) shares. We believe that the techniques introduced in our construction may be of independent interest. Inspired by the well studied problem of perfectly secure message transmission introduced in the seminal work of Dolev et. al (J. of ACM'93), we also initiate the study of non-malleable message transmission. Non-malleable message transmission can be seen as a natural generalization in which the goal is to ensure that the receiver either receives the original message, or, the original message is essentially destroyed and the receiver receives an ''unrelated'' message, when the network is under the influence of an adversary who can byzantinely corrupt all the nodes in the network. As natural applications of our non-malleable secret sharing schemes, we propose constructions for non-malleable message transmission.

Secure Multiplication for Bitslice Higher-Order Masking: Optimisation and Comparison

Tue, 04/03/2018 - 18:54
In this paper, we optimize the performances and compare several recent masking schemes in bitslice on 32-bit arm devices, with a focus on multiplication. Our main conclusion is that efficiency (or randomness) gains always come at a cost, either in terms of composability or in terms of resistance against horizontal attacks. Our evaluations should therefore allow a designer to select a masking scheme based on implementation constraints and security requirements. They also highlight the increasing feasibility of (very) high-order masking that are offered by increasingly powerful embedded devices, with new opportunities of high-security devices in various contexts.

On Zero-Testable Homomorphic Encryption and Publicly Verifiable Non-Interactive Arguments

Tue, 04/03/2018 - 12:59
We define and study zero-testable homomorphic encryption (ZTHE) -- a semantically secure, somewhat homomorphic encryption scheme equipped with a weak zero test that can identify trivial zeros. These are ciphertexts that result from homomorphically evaluating an arithmetic circuit computing the zero polynomial over the integers. This is a relaxation of the (strong) zero test provided by the notion of graded encodings, which identifies all encodings of zero. We show that ZTHE can suffice for powerful applications. Based on any ZTHE scheme that satisfies the additional properties of correctness on adversarial ciphertexts and multi-key homomorphism, we construct publicly verifiable non-interactive arguments for delegating computation. Such arguments were previously constructed from indistinguishability obfuscation or based on so-called knowledge assumptions. The arguments we construct are adaptively sound, based on an efficiently falsifiable assumption, and only make black-box use of the underlying cryptographic primitives. We also show that a ZTHE scheme that is sufficient for our application can be constructed based on an efficiently-falsifiable assumption over so-called "clean" graded encodings.

Secure top most significant genome variants search: iDASH 2017 competition

Tue, 04/03/2018 - 11:17
One of the 3 tracks of iDASH Privacy & Security Workshop 2017 competition was to execute a whole genome variants search on private genomic data. Particularly, the search application was to find the top most significant SNPs (Single-Nucleotide Polymorphisms) in a database of genome records labeled with control or case.Privacy and confidentiality of genome data had to be ensured using Intel SGX enclaves. The typical use-case of this application is the multi-party computation (each party possessing one or several genome records) of the SNPs which statistically differentiate control and case genome datasets. In this paper we discuss the solution submitted by our team to this competition. Our solution consists of two applications: (i) compress and encrypt genome files and (ii) perform genome processing (top most important SNPs search). We have opted for a horizontal treatment of genome records and heavily used parallel processing. Rust programming language was employed to develop both applications. Execution performance of the processing applications scales well and very good performance metrics are obtained. Contest organizers selected it as the best submission amongst other received competition entries and our team was awarded the first prize on this track.

On the cost of computing isogenies between supersingular elliptic curves

Tue, 04/03/2018 - 11:13
The security of the Jao-De Feo Supersingular Isogeny Diffie-Hellman (SIDH) key agreement scheme is based on the intractability of the Computational Supersingular Isogeny (CSSI) problem --- computing ${\mathbb F}_{p^2}$-rational isogenies of degrees $2^e$ and $3^e$ between certain supersingular elliptic curves defined over ${\mathbb F}_{p^2}$. The classical meet-in-the-middle attack on CSSI has an expected running time of $O(p^{1/4})$, but also has $O(p^{1/4})$ storage requirements. In this paper, we demonstrate that the van Oorschot-Wiener collision finding algorithm has a lower cost (but higher running time) for solving CSSI, and thus should be used instead of the meet-in-the-middle attack to assess the security of SIDH against classical attacks. The smaller parameter $p$ brings significantly improved performance for SIDH.

Multilinear maps via secret ring

Tue, 04/03/2018 - 10:56
Garg, Gentry and Halevi (GGH13) described the first candidate multilinear maps using ideal lattices. However, Hu and Jia recently presented an efficient attack on the GGH13 map, which breaks the multipartite key exchange (MPKE) and witness encryption (WE) based on GGH13. In this work, we describe a new variant of GGH13 using secret ring, which preserves the origin functionality of GGH13. The security of our variant depends upon the following new hardness problem. Given the determinant of the circular matrix of some element in a secret ring, the problem is to find this secret ring and reconstruct this element.


IACR Eprint