Applied Cryptography and Network Security

Multiparty computation can be used for privacy-friendly outsourcing of computations on private inputs of multiple parties. A computation is outsourced to several computation parties; if not too many are corrupted (e.g., no more than half), then they cannot determine the inputs or produce an incorrect output. However, in many cases, these guarantees are not enough: we need correctness even if all computation parties may be corrupted; and we need that correctness can be verified even by parties that did not participate in the computation. Protocols satisfying these additional properties are called “universally verifiable”. In this paper, we propose a new security model for universally verifiable multiparty computation, and we present a practical construction, based on a threshold homomorphic cryptosystem. We also develop a multiparty protocol for jointly producing non-interactive zero-knowledge proofs, which may be of independent interest.

Proactive secret sharing (PSS) schemes are designed for settings where long-term confidentiality of secrets is required, specifically, when all participating parties may eventually be corrupted. PSS schemes periodically refresh secrets and reset corrupted parties to an uncorrupted state; in PSS the corruption threshold of parties is replaced with a corruption rate which cannot be violated. In dynamic proactive secret sharing (DPSS) the group of participating parties can vary during the course of execution. Accordingly, DPSS is ideal when the set of participating parties changes over the lifetime of the secret or where removal of parties is necessary if they become severely corrupted. This paper presents the first DPSS scheme with optimal amortized per-secret communication in the number of parties, n: This paper requires O(1) communication, as compared to $$O(n^4)$$ or $$\exp (n)$$ in previous work. We present perfectly and statistically secure schemes with near-optimal threshold in each case. We also describe how to construct a communication-efficient dynamic proactively-secure multiparty computation (DPMPC) protocol which achieves the same thresholds.

Password-based group key exchange protocols allow group users who share only a short, low entropy password to agree on a cryptographically strong session key. One fundamental complexity measure of such protocols is its round complexity. In this paper, we present the first one-round password-based group key exchange protocol in the common random string model. Furthermore, we propose a completely new approach to remove the need for the common random string and then construct a two-round password-based group key exchange protocol that does not require any setup assumption. This is - to the best of our knowledge - the first password-based group key exchange protocol without trusted setup. Using indistinguishability obfuscation as main tool, both protocols are provably secure in the standard model.

We show how to construct a completely generic UC-secure oblivious transfer scheme from a collision-resistant chameleon hash scheme (CH) and a CCA encryption scheme accepting a smooth projective hash function (SPHF).Our work is based on the work of Abdalla et al. at Asiacrypt 2013, where the authors formalize the notion of SPHF-friendly commitments, i.e. accepting an SPHF on the language of valid commitments (to allow implicit decommitment), and show how to construct from them a UC-secure oblivious transfer in a generic way. But Abdalla et al. only gave a DDH-based construction of SPHF-friendly commitment schemes, furthermore highly relying on pairings. In this work, we show how to generically construct an SPHF-friendly commitment scheme from a collision-resistant CH scheme and an SPHF-friendly CCA encryption scheme. This allows us to propose an instanciation of our schemes based on the DDH, as efficient as that of Abdalla et al., but without requiring any pairing. Interestingly, our generic framework also allows us to propose an instantiation based on the learning with errors (LWE) assumption. For the record, we finally propose a last instanciation based on the decisional composite residuosity (DCR) assumption.

We formalize the security notions of non-malleability under selective opening attacks (NM-SO security) in two approaches: the indistinguishability-based approach and the simulation-based approach. We explore the relations between NM-SO security notions and the known selective opening security notions, and the relations between NM-SO security notions and the standard non-malleability notions.

In this paper, we introduce a new concept that we call fuzzy signature, which is a signature scheme that uses a noisy string such as biometric data as a private key, but does not require auxiliary data (which is also called helper string in the context of fuzzy extractors), for generating a signature. Our technical contributions are three-fold: (1) We first give the formal definition of fuzzy signature, together with a formal definition of a “setting” that specifies some necessary information for fuzzy data. (2) We give a generic construction of a fuzzy signature scheme based on a signature scheme with certain homomorphic properties regarding keys and signatures, and a new tool that we call linear sketch. (3) We specify a certain setting for fuzzy data, and then give concrete instantiations of these building blocks for our generic construction, leading to our proposed fuzzy signature scheme.We also discuss how fuzzy signature schemes can be used to realize a biometric-based PKI that uses biometric data itself as a cryptographic key, which we call the public biometric infrastructure (PBI).

In Ciphertext-Policy Attribute-Based Encryption (CP-ABE), a user’s decryption key is associated with attributes which in general are not related to the user’s identity, and the same set of attributes could be shared between multiple users. From the decryption key, if the user created a decryption blackbox for sale, this malicious user could be difficult to identify from the blackbox. Hence in practice, a useful CP-ABE scheme should have some tracing mechanism to identify this ‘traitor’ from the blackbox. In addition, being able to revoke compromised keys is also an important step towards practicality, and for scalability, the scheme should support an exponentially large number of attributes. However, none of the existing traceable CP-ABE schemes simultaneously supports revocation and large attribute universe. In this paper, we construct the first practical CP-ABE which possesses these three important properties: (1) blackbox traceability, (2) revocation, and (3) supporting large universe. This new scheme achieves the fully collusion-resistant blackbox traceability, and when compared with the latest fully collusion-resistant blackbox traceable CP-ABE schemes, this new scheme achieves the same efficiency level, enjoying the sub-linear overhead of $$O(\sqrt{N})$$, where N is the number of users in the system, and attains the same security level, namely, the fully collusion-resistant traceability against policy-specific decryption blackbox, which is proven in the standard model with selective adversaries. The scheme supports large attribute universe, and attributes do not need to be pre-specified during the system setup. In addition, the scheme supports revocation while keeping the appealing capability of conventional CP-ABE, i.e. it is highly expressive and can take any monotonic access structures as ciphertext policies.

An order query takes as input a set of elements from a list (ordered sequence) $$\mathcal {L}$$, and asks for this set to be ordered using the total order induced by $$\mathcal {L}$$. We introduce two formal models for answering order queries on a list in a verifiable and private manner. Our first model, called zero-knowledge list (ZKL), generalizes the standard two-party model of membership queries on a set to order queries on a list in zero-knowledge. We present a construction of ZKL based on zero-knowledge sets and a homomorphic integer commitment. Our second model, privacy-preserving authenticated list (PPAL), extends authenticated data structures by adding a zero-knowledge privacy requirement. This is a three-party model, where a list is outsourced by a trusted owner to an untrusted cloud server, which answers order queries issued by clients and returns proofs of the answers. PPAL supports data integrity against a malicious server and privacy protection against a malicious client. Though PPAL can be implemented using our ZKL construction, this construction is not as efficient as desired in cloud applications. We present an efficient PPAL construction based on our novel technique of blinded bilinear accumulators and bilinear maps. Both our models are provably secure in the Random Oracle model and are zero-knowledge (e.g., hiding even the size of the list). We also show that the ZKL and PPAL frameworks can be extended to support fundamental statistical queries efficiently and in zero-knowledge.

Enabling private database queries is an important and challenging research problem with many real-world applications. The goal is such that the client obtains the results of its queries without learning anything else about the database, while the outsourced server learns nothing about the queries or data, including access patterns. The secure-computation-over-ORAM architecture offers a promising approach to this problem, permitting sub-linear time processing of the queries (after pre-processing) without compromising security.In this work we examine the feasibility of this approach, focusing specifically on secure-computation protocols based on somewhat-homomorphic encryption (SWHE). We devised and implemented secure two-party protocols in the semi-honest model for the path-ORAM protocol of Stefanov et al. This provides access by index or keyword, which we extend (via pre-processing) to limited conjunction queries and range queries. The SWHE schemes we consider allow easy batching or “SIMD” operations, and also let us vary the plaintext space in use. These capabilities let us devise many sub-protocols that are interesting in their own right, for tasks such as encrypted comparisons, blinded permutations, and the really expensive ORAM eviction step.We implemented our protocols on top of the HElib homomorphic encryption library. Our basic single-threaded implementation takes about 30 min to process a query on a database with $$2^{22}$$ records and 120-bit long keywords, providing a cause for optimism about the viability of this direction, and we expect a better optimized implementation to be much faster.

Let us consider a situation where a client (Alice) frequently buys a certain kind of product from a shop (Bob) (e.g., an online music service sells individual songs at the same price, and a client buys songs multiple times in a month). In this situation, Alice and Bob would like to aggregate the total transactions and pay once per month because individual payments are troublesome. Though optimistic fair exchange (OFE) has been considered in order to swap electronic items simultaneously, known OFE protocols cannot provide such aggregate function efficiently because various costs are bounded by the number of transactions in the period. In order to run this aggregation procedure efficiently, we introduce a new kind of OFE called Accumulable OFE (AOFE) that allows clients to efficiently accumulate payments in each period. In AOFE, any memory costs, computational costs, and communication complexity of the payment round must be constant in terms of the number of transactions. Since a client usually has just a low power and poor memory device, these efficiency are desirable in practice. Currently known approaches (e.g., based on verifiably encrypted signature scheme) are not very successful for constructing AOFE. Thus, we consider a new approach based on a new cryptographic primitive called verifiably encrypted homomorphic signature scheme (VEHS). In this paper, we propose a generic construction of AOFE from VEHS, and also present a concrete VEHS scheme over a composite-order bilinear group by using the dual-form signature techniques. This VEHS scheme is also of independent interest. Since we can prove the security of VEHS without random oracles, our AOFE protocol is also secure without random oracles. Finally, we implemented our AOFE protocol, and it is efficient enough for practical use.

Collaborative editing cloud servers allow a group of online users to concurrently edit a document. Every user achieves consistent views of the document by applying others’ modifications, which are pushed by the cloud servers. The cloud servers repeatedly transform, order, broadcast modifications,and merge them into a joint version in a real-time manner (typically, less than one second). However, in existing solutions such as Google Docs and Cloud9, the servers employ operational transformation to resolve edit conflicts and achieve consistent views for each online user, so all inputs (and the document) are processed as plaintext by the cloud servers. In this paper, we propose LightCore, a collaborative editing cloud service for sensitive data against honest-but-curious cloud servers. A LightCore client applies stream cipher algorithms to encrypt input characters that compose the text of the document before the user sends them to servers, while the keys are shared by all authorized users and unknown to the servers. The byte-by-byte encryption feature of stream cipher enables the servers to finish all heavy processing and provide collaborative editing cloud services as the existing solutions without the protections against curious servers. Therefore, the lightweight load of clients is kept while the users’ sensitive data are protected. We implement LightCore supporting two different methods to generate keystreams, i.e., the “pure” stream cipher and the CTR mode of block cipher. Note that the document is usually modified by collaborative users for many times, and the sequence of text segments is not input and encrypted in chronological order. So, different from the stateless CTR mode of block cipher, the overall performance of high-speed but stateful stream cipher varies significantly with different key update rules and use scenarios. The analysis and evaluation results on the prototype system show that, LightCore provides secure collaborative editing services for resource-limited clients. Finally, we suggest the suitable keystream policy for different use scenarios according to these results.

Named Data Networking (NDN) is an instance of information-centric network architecture designed as a candidate replacement for the current IP-based Internet. It emphasizes efficient content distribution, achieved via in-network caching and collapsing of closely-spaced content requests. NDN also offers strong security and explicitly decouples content from entities that distribute it. NDN is widely assumed to provide better privacy than IP, mainly because NDN packets lack source and destination addresses. In this paper, we show that this assumption does not hold in practice. In particular, we present several algorithms that help locate consumers by taking advantage of NDN router-side content caching. We use simulations to evaluate these algorithms on a large and realistic topology, and validate the results on the official NDN testbed. Beyond locating consumers, proposed techniques can also be used to detect eavesdroppers.

The onion routing (OR) network Tor provides anonymity to its users by routing their encrypted traffic through three proxies (or nodes). The key cryptographic challenge, here, is to establish symmetric session keys using a secure key exchange between the anonymous user and the selected nodes. The Tor network currently employs a one-way authenticated key exchange (1W-AKE) protocol $${\mathsf {ntor}}$$ for this purpose. Nevertheless, $${\mathsf {ntor}}$$ as well as other known 1W-AKE protocols rely solely on some classical Diffie-Hellman (DH) type assumptions for their (forward) security, and privacy of today’s anonymous communication cannot be ensured once quantum computers arrive.In this paper, we demonstrate utility of lattice-based cryptography towards solving this problem for onion routing. In particular, we present a novel hybrid 1W-AKE protocol ($${\mathsf {HybridOR}}$$) that is secure under the lattice-based ring learning with error (ring-LWE) assumption or the gap DH assumption. Due to its hybrid design, $${\mathsf {HybridOR}}$$ is not only resilient against quantum attacks but also allows the OR nodes to use the current DH public keys and subsequently requires no modification to the current Tor public key infrastructure. Moreover, thanks to the recent progress in lattice-based cryptography in the form of efficient ring-based constructions, our protocol is also computationally more efficient than the currently employed 1W-AKE protocol $${\mathsf {ntor}}$$, and it only introduces manageable communication overhead to the Tor protocol.

Divisible E-cash has been introduced twenty years ago but no construction is both fully secure in the standard model and efficiently scalable. In this paper, we fill this gap by providing an anonymous divisible E-cash construction with constant-time withdrawal and spending protocols. Moreover, the deposit protocol is constant-time for the merchant, whatever the spent value is. It just has to compute and store $$2^l$$ serial numbers when a value $$2^l$$ is deposited, compared to $$2^n$$ serial numbers whatever the spent amount (where $$2^n$$ is the global value of the coin) in the recent state-of-the-art paper. This makes a very huge difference when coins are spent in several times.Our approach follows the classical tree representation for the divisible coin. However we manage to build the values on the nodes in such a way that the elements necessary to recover the serial numbers are common to all the nodes of the same level: this leads to strong unlinkability and anonymity, the strongest security level for divisible E-cash.

Anonymous credential systems allow users to authenticate in a secure and private fashion. To protect credentials from theft as well as from being shared among multiple users, credentials can be bound to physical devices such as smart cards or tablets. However, device-bound credentials cannot be exported and backed up for the case that the device breaks down or is stolen. Restoring the credentials one by one and re-enabling the legitimate owner to use them may require significant efforts from the user. We present a mechanism that allows users to store some partial backup information of their credentials that will allow them to restore them through a single interaction with a device registration authority, while security and privacy are maintained. We therefore define anonymous credentials with backup and provide a generic construction that can be built on top of many existing credential systems.

Obtaining differential patterns over many rounds of a cryptographic primitive often requires working on local differential trail analysis. In the case of boomerang and rectangle attacks, merging two short differential trails into one long differential pattern is required. It was previously shown by Murphy that caution should be exercised as there is increased chance of running into contradictions in the middle rounds of the primitive.In this paper, we propose the use of a SAT-based constraint solver URSA as aid in analysis of differential trails and find that previous rectangle/boomerang attacks on XTEA, SHACAL-1 and SM3 primitives are based on incompatible trails. Given the C specification of the cryptographic primitive, verifying differential trail portions requires minimal work on the side of the cryptanalyst.

Time–memory trade-off (TMTO) cryptanalysis is a powerful technique for practically breaking a variety of security systems in reality. There are mainly four general TMTO cryptanalysis methods, namely Hellman table cryptanalysis, rainbow table cryptanalysis, thin rainbow table cryptanalysis and thick rainbow table cryptanalysis, plus a few supplementary techniques that can be combined with a general method to produce possibly distinct TMTOs, like distinguished points. In this paper, we present a unified TMTO cryptanalysis, which we call unified rainbow table cryptanalysis, basing it on a unified rainbow table, then we describe its general combination with distinguished points, and finally we apply unified rainbow table cryptanalysis to the A5/1 stream cipher being used in the Global System for Mobile Communications (GSM). On a general-purpose graphics processing unit (GPGPU) computer with 3 NVIDIA GeForce GTX690 cards that cost about 15,000 United States dollars in total, we made a unified rainbow table of 984 GB in about 55 days, and implemented a unified rainbow table attack that had an online attack time of 9 s with a success probability of 34 % (or 56 %) when using 4 (respectively, 8) known keystreams (of 114 bits long each). If two such tables of 984 GB were generated, the attack would have an online attack time of 9 s with a success probability of 81 % when using 8 known keystreams. The practical results show again that nowadays A5/1 is rather insecure in reality and GSM should no longer use it.

There is a growing need to develop lightweight cryptographic primitives suitable for resource-constrained devices permeating in increasing numbers into the fabric of life. Such devices are exemplified none more so than by batteryless radio frequency identification (RFID) tags in applications ranging from automatic identification and monitoring to anti-counterfeiting. Pandaka is a lightweight cipher together with a protocol proposed in INFOCOM 2014 for extremely resource limited RFID tags. It is designed to reduce the hardware cost (area of silicon) required for implementing the cipher by shifting the computationally intensive task of cryptographically secure random number generation to the reader. In this paper we evaluate Pandaka and demonstrate that the communication protocol contains flaws which completely undermine the security of the cipher and make Pandaka susceptible to de-synchronisation. Furthermore, we show that, even without the protocol flaws, we can use a guess and determine method to mount an attack on the cipher for the more challenging scenario of a known-plaintext attack with an expected complexity of only $$2^{55}$$. We conclude that Pandaka needs to be amended and highlight simple measures to prevent the above attacks.

The enforcement of access control policies using cryptographic primitives has been studied for over 30 years. When symmetric cryptographic primitives are used, each protected resource is encrypted and only authorized users are given the decryption key. Hence, users may require many keys. In most schemes in the literature, keys are derived from a single key explicitly assigned to the user and publicly available information. Recent work has challenged this design by developing schemes that do not require public information, the trade-off being that a user may require more than one key. However, these new schemes, which require a chain partition of the partially ordered set on which the access control policy is based, generally require more keys than necessary. Moreover, no algorithm is known for determining the best chain partition to use. In this paper we define the notion of a tree-based cryptographic enforcement scheme, which, like chain-based schemes, requires no public information but simultaneously has lower storage requirements. We formally establish that the strong security properties of recent chain-based schemes are preserved by tree-based schemes, and provide an efficient construction for deriving a tree-based enforcement scheme from a given policy that minimizes the number of keys required.

Distributed data usage control enables data owners to constrain how their data is used by remote entities. However, many data usage policies refer to events happening within several distributed systems, e.g. “at each point in time at most two clerks might have a local copy of this contract”, or “a contract must be approved by at least two clerks before it is sent to the customer”. While such policies can intuitively be enforced using a centralized infrastructure, major drawbacks are that such solutions constitute a single point of failure and that they are expected to cause heavy communication and performance overhead. Hence, we present the first fully decentralized infrastructure for the preventive enforcement of data usage policies. We provide a thorough evaluation of our infrastructure and show in which scenarios it is superior to a centralized approach.

Search engines are the prevalently used tools to collect information about individuals on the Internet. Search results typically comprise a variety of sources that contain personal information — either intentionally released by the person herself, or unintentionally leaked or published by third parties without being noticed, often with detrimental effects on the individual’s privacy. To grant individuals the ability to regain control over their disseminated personal information, the European Court of Justice recently ruled that EU citizens have a right to be forgotten in the sense that indexing systems, such as Google, must offer them technical means to request removal of links from search results that point to sources violating their data protection rights. As of now, these technical means consist of a web form that requires a user to manually identify all relevant links herself upfront and to insert them into the web form, followed by a manual evaluation by employees of the indexing system to assess if the request to remove those links is eligible and lawful.In this work, we propose a universal framework Oblivion to support the automation of the right to be forgotten in a scalable, provable and privacy-preserving manner. First, Oblivion enables a user to automatically find and tag her disseminated personal information using natural language processing (NLP) and image recognition techniques and file a request in a privacy-preserving manner. Second, Oblivion provides indexing systems with an automated and provable eligibility mechanism, asserting that the author of a request is indeed affected by an online resource. The automated eligibility proof ensures censorship-resistance so that only legitimately affected individuals can request the removal of corresponding links from search results. We have conducted comprehensive evaluations of Oblivion, showing that the framework is capable of handling 278 removal requests per second on a standard notebook (2.5 GHz dual core), and is hence suitable for large-scale deployment.

Traditional user authentication methods using passcode or finger movement on smartphones are vulnerable to shoulder surfing attack, smudge attack, and keylogger attack. These attacks are able to infer a passcode based on the information collection of user’s finger movement or tapping input. As an alternative user authentication approach, eye tracking can reduce the risk of suffering those attacks effectively because no hand input is required. However, most existing eye tracking techniques are designed for large screen devices. Many of them depend on special hardware like high resolution eye tracker and special process like calibration, which are not readily available for smartphone users. In this paper, we propose a new eye tracking method for user authentication on a smartphone. It utilizes the smartphone’s front camera to capture a user’s eye movement trajectories which are used as the input of user authentication. No special hardware or calibration process is needed. We develop a prototype and evaluate its effectiveness on an Android smartphone. We recruit a group of volunteers to participate in the user study. Our evaluation results show that the proposed eye tracking technique achieves very high accuracy in user authentication.

Distance bounding protocols become important since wireless technologies become more and more common. Therefore, the security of the distance bounding protocol should be carefully analyzed. However, most of the protocols are not secure or their security is proven informally. Recently, Boureanu and Vaudenay defined the common structure which is commonly followed by most of the distance bounding protocols: answers to challenges are accepted if they are correct and on time. They further analyzed the optimal security that we can achieve in this structure and proposed DBopt which reaches the optimal security bounds. In this paper, we define three new structures: when the prover registers the time of a challenge, when the verifier randomizes the sending time of the challenge, and the combined structure. Then, we show the optimal security bounds against distance fraud and mafia fraud which are lower than the bounds showed by Boureanu and Vaudenay for the common structure. Finally, we adapt the DBopt protocol according to our new structures and we get three new distance bounding protocols. All of them are proven formally. In the end, we compare the performance of the new protocols with DBopt and we see that we have a better efficiency. For instance, we can reduce the number of rounds in DB2 (one of the instances of DBopt) from 123 to 5 with the same security.

As the underground market of malware flourishes, there is an exponential increase in the number and diversity of malware. A crucial question in malware analysis research is how to define malware specifications or signatures that faithfully describe similar malicious intent and clearly stand out from other programs. It is evident that the classical syntactic signatures are insufficient to defeat state-of-the art malware. Behavior-based specifications which capture real malicious characteristics during runtime, have become more prevalent in anti-malware tasks, such as malware detection and malware clustering. This kind of specification is typically extracted from system call dependence graphs that a malware sample invokes. In this paper we present replacement attacks to poison behavior-based specifications by concealing similar behaviors among malware variants. The essence of the attacks is to replace a behavior specification to its semantically equivalent one, so that similar malware variants within one family turn out to be different. As a result, malware analysts have to put more efforts to re-analyze similar samples. We distill general attacking strategies by mining more than 5,000 malware samples’ behavior specifications and implement a compiler-level prototype to automate replacement attacks. Experiments on 960 real malware samples demonstrate effectiveness of our approach to impede multiple malware analyses based on behavior specifications, such as similarity comparison and malware clustering. In the end, we provide possible counter-measures to strengthen behavior-based malware analysis.

There have been several papers which studied the security of CRT-RSA when some bits of CRT-exponents $$d_p$$ and $$d_q$$ are known to attackers. At first, Blömer and May (Crypto 2003) proposed attacks which used the most or the least significant bits of either $$d_p$$ or $$d_q$$ . Next, Sarkar and Maitra (ACNS 2009) generalized the scenario and proposed an attack which used the most significant bits of both $$d_p$$ and $$d_q$$ . Recently, Lu et al. (ACNS 2014) proposed improved attacks for the same scenario as Blömer and May. These works showed that public RSA modulus can be factored when $$e<N^{3/8}$$ , or sizes of unknown bits are less than $$N^{1/4}$$ . In this paper, we propose improved attacks when attackers know the most/least significant bits of $$d_p$$ or/and $$d_q$$ . Unlike previous works, our attacks work in the same conditions regardless of positions of known bits; either the most or the least significant bits are not the matter. In addition, using our attacks, public RSA modulus can be factored even when an encryption exponent is full size or sizes of unknown bits are less than $$N^{1/3}$$ .

This work presents the first differential power analysis of an implementation of the McEliece cryptosystem. Target of this side-channel attack is a state-of-the-art FPGA implementation of the efficient QC-MDPC McEliece decryption operation as presented at DATE 2014. The presented cryptanalysis succeeds to recover the complete secret key after a few observed decryptions. It consists of a combination of a differential leakage analysis during the syndrome computation followed by an algebraic step that exploits the relation between the public and private key.

A common countermeasure to thwart side-channel analysis attacks is algorithmic masking. For this, algorithms that mix Boolean and arithmetic operations need to either apply two different masking schemes with secure conversions or use dedicated arithmetic units that can process Boolean masked values. Several proposals have been published that can realize these approaches securely and efficiently in software. But to the best of our knowledge, no hardware design exists that fulfills relevant properties such as efficiency and security at the same time.In this paper, we present two design strategies to realize a secure and efficient arithmetic adder for Boolean-masked values. First, we introduce an architecture based on the ripple-carry adder that targets low-cost applications. The second architecture is based on a pipelined Kogge-Stone adder and targets high-performance applications. In particular, all our implementations adopt the threshold implementation approach to improve their resistance against SCA attacks even in the presence of glitches. We evaluated the security of our designs practically against SCA using a non-specific statistical t-test. Based on our analysis, we show that our constructions not only achieve resistance against first- and (univariate) second-order attacks but also require fewer random bits per operation compared to any existing software-based approach.

A Physically Unclonable Function (PUF) can be seen as a source of randomness that can be challenged with a stimulus and responds in a way that is to some extent unpredictable. PUFs can be used to provide efficient solutions for common cryptographic primitives such as identification/authentication schemes, key storage, and hardware-entangled cryptography. Moreover, Brzuska et al. have recently shown, that PUFs can be used to construct UC secure protocols (CRYPTO 2011). Most PUF instantiations, however, only provide a static challenge/response space which limits their usefulness for practical instantiations. To overcome this limitation, Katzenbeisser et al. (CHES 2011) introduced Logically Reconfigurable PUFs (LR-PUFs), with the idea to introduce an “update” mechanism that changes the challenge/response behaviour without physically replacing or modifying the hardware.In this work, we revisit LR-PUFs. We propose several new ways to characterize the unpredictability of LR-PUFs covering a broader class of realistic attacks and examine their relationship to each other. In addition, we reconcile existing constructions with these new characterizations and show that they can withstand stronger adversaries than originally shown. Since previous constructions are insecure with respect to our strongest unpredictability notion, we propose a secure construction which relies on the same assumptions and is almost as efficient as previous solutions.

Physical unclonable functions (PUFs) exploit the intrinsic complexity and irreproducibility of physical systems to generate secret information. They have been proposed to provide higher level security as a hardware security primitive. Notably PUFs are an emerging and promising solution for establishing trust in an embedded system with low overhead with respect to energy and area. Most current PUF designs traditionally focus on exploiting process variations in CMOS (Complementary Metal Oxide Semiconductor) technology. In recent years, progress in nanoelectronic devices such as memristors has demonstrated the prevalence of process variations in scaling electronics down to the nano region. In this paper we exploit the extremely large information density available in the nanocrossbar architecture and the large resistance variations of memristors to develop on-chip memristive device based PUF (mrPUF). Our proposed architecture demonstrates good uniqueness, reliability and improved number of challenge-response pairs (CRPs). The proposed mrPUF is validated using nanodevices characteristics obtained from experimental data and extensive simulations. In addition, the performance of our mrPUF is compared with existing memristor based PUF architectures. Furthermore, we analyze and demonstrate the improved security with respect to model building attacks by expounding upon the inherent nature of nanocrossbar arrays where we use the independence between nanocrossbar columns to generate responses to challenges.

A straightforward way of constructing an n-bit pseudorandom function is to XOR two or more pseudorandom permutations: $$p_1\oplus \ldots \oplus p_k$$. This XOR construction has gained broad attention over the last two decades. In this work, we revisit the security of this well-established construction. We consider the case where the underlying permutations are considered secret, as well as the case where these permutations are publicly available to the adversary. In the secret permutation setting, we present a simple reduction showing that the XOR construction achieves optimal $$2^n$$ security for all $$k\ge 2$$, therewith improving a recent result of Cogliati et al. (FSE 2014). Regarding the public permutation setting, Mandal et al. (INDOCRYPT 2010) proved $$2^{2n/3}$$ security for the case $$k=2$$, but we point out the existence of a non-trivial flaw in the proof. We re-establish and generalize the claimed security bound for general $$k\ge 2$$ using a different proof approach.

A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. In this paper, we extend the formal model of PRNG with input defined by Dodis et al. at CCS 2013 to deal with partial leakage of sensitive information. The resulting security notion, termed leakage-resilient robust PRNG with input, encompasses all the previous notions, but also allows the adversary to continuously get some leakage on the manipulated data. Dodis et al. also proposed an efficient construction, based on simple operations in a finite field and a classical deterministic pseudo-random generator $$\mathbf {G}$$. Here, we analyze this construction with respect to our new stronger security model, and prove that with a stronger $$\mathbf {G}$$, it also resists leakage. We show that this stronger $$\mathbf {G}$$ can be obtained by tweaking some existing constructions based on $$\mathsf {AES}$$. We also propose a new instantiation which may be better in specific cases. Eventually, we show that the resulting scheme remains quite efficient in spite of its new security properties. It can thus be recommended in contexts where side-channel resistance is required.

Information leakage is a major concern in modern day IT-security. In fact, a malicious user is often able to extract information about private values from the computation performed on the devices. In specific settings, such as RFID, where a low computational complexity is required, it is hard to apply standard techniques to achieve resilience against this kind of attacks. In this paper, we present a framework to make cryptographic primitives based on large finite fields robust against information leakage with a bounded computational cost. The approach makes use of the inner product extractor and guarantees security in the presence of leakage in a widely accepted model. Furthermore, we show how to apply the proposed techniques to the authentication protocol Lapin, and we compare it to existing solutions.

Cryptographic protocols are commonly designed and their security proven under the assumption that the protocol parties have access to perfect (uniform) randomness. Physical randomness sources deployed in practical implementations of these protocols often fall short in meeting this assumption, but instead provide only a steady stream of bits with certain high entropy. Trying to ground cryptographic protocols on such imperfect, weaker sources of randomness has thus far mostly given rise to a multitude of impossibility results, including the impossibility to construct provably secure encryption, commitments, secret sharing, and zero-knowledge proofs based solely on a weak source. More generally, indistinguishability-based properties break down for such weak sources. In this paper, we show that the loss of security induced by using a weak source can be meaningfully quantified if the source is bounded, e.g., for the well-studied Santha-Vazirani (SV) sources. The quantification relies on a novel relaxation of indistinguishability by a quantitative parameter. We call the resulting notion differential indistinguishability in order to reflect its structural similarity to differential privacy. More concretely, we prove that indistinguishability with uniform randomness implies differential indistinguishability with weak randomness. We show that if the amount of weak randomness is limited (e.g., by using it only to seed a PRG), all cryptographic primitives and protocols still achieve differential indistinguishability.