Updated: 1 hour 51 min ago

### ScanSAT: Unlocking Obfuscated Scan Chains

Tue, 01/08/2019 - 20:39
While financially advantageous, outsourcing key steps such as testing to potentially untrusted Outsourced Semiconductor Assembly and Test (OSAT) companies may pose a risk of compromising on-chip assets. Obfuscation of scan chains is a technique that hides the actual scan data from the untrusted testers; logic inserted between the scan cells, driven by a secret key, hide the transformation functions between the scan- in stimulus (scan-out response) and the delivered scan pattern (captured response). In this paper, we propose ScanSAT: an attack that transforms a scan obfuscated circuit to its logic- locked version and applies a variant of the Boolean satisfiability (SAT) based attack, thereby extracting the secret key. Our empirical results demonstrate that ScanSAT can easily break naive scan obfuscation techniques using only three or fewer attack iterations even for large key sizes and in the presence of scan compression.

### On the Bright Side of Darkness: Side-Channel Based Authentication Protocol Against Relay Attacks

Tue, 01/08/2019 - 20:38
Relay attacks are nowadays well known and most designers of secure authentication protocols are aware of them. At present, the main methods to prevent these attacks are based on the so-called distance bounding technique which consists in measuring the round-trip time of the exchanged authentication messages between the prover and the verifier to estimate an upper bound on the distance between these entities. Based on this bound, the verifier checks if the prover is sufficiently close by to rule out an unauthorized entity. Recently, a new work has proposed an authentication protocol that surprisingly uses the side-channel leakage to prevent relay attacks. In this paper, we exhibit some practical and security issues of this protocol and provide a new one that fixes all of them. Then, we argue the resistance of our proposal against both side-channel and relay attacks under some realistic assumptions. Our experimental results show the efficiency of our protocol in terms of false acceptance and false rejection rates.

### Secure and Effective Logic Locking for Machine Learning Applications

Tue, 01/08/2019 - 20:37

### Leakage-Resilient Group Signature: Definitions and Constructions

Tue, 01/08/2019 - 20:37
Group signature scheme provides group members a way to sign messages without revealing their identities. Anonymity and traceability are two essential properties in a group signature system. However, these two security properties hold based on the assumption that all the signing keys are perfectly secret and leakage-free. On the another hand, on account of the physical imperfection of cryptosystems in practice, malicious attackers can learn fraction of secret state (including secret keys and intermediate randomness) of the cryptosystem via side-channel attacks, and thus breaking the security of whole system. To address this issue, Ono et al. introduced a new security model of group signature, which captures randomness exposure attacks. They proved that their proposed construction satisfies the security require-ments of group signature scheme. Nevertheless, their scheme is only provably secure against randomness exposure and supposes the secret keys remains leakage-free. In this work, we focus on the security model of leakage-resilient group signature based on bounded leakage setting and propose three new black-box constructions of leakage-resilient group signature secure under the proposed security models.

### Characterizing overstretched NTRU attacks

Tue, 01/08/2019 - 05:15
Overstretched NTRU, an NTRU variant with a large modulus, has been used as a building block for several cryptographic schemes in recent years. Recently, two lattice \emph{subfield attacks} and a \emph{subring attack} were proposed that broke some suggested parameters for overstretched NTRU. These attacks work by decreasing the dimension of the lattice to be reduced, which improves the performance of the lattice basis reduction algorithm. However, there are a number of conflicting claims in the literature over which of these attacks has the best performance. These claims are typically based on experiments more than analysis. Furthermore, the metric for comparison has been unclear in some prior work. In this paper, we argue that the correct metric should be the lattice dimension. We show both analytically and experimentally that the subring attack succeeds on a smaller dimension lattice than the subfield attack for the same problem parameters, and also succeeds with a smaller modulus when the lattice dimension is fixed.

### Lattice-based Direct Anonymous Attestation (LDAA)

Mon, 01/07/2019 - 16:46
The Cloud-Edges (CE) framework, wherein small groups of Internet of Things(IoT) devices are serviced by local edge devices, enables a more scalable solution to IoT networks. The trustworthiness of the network may be ensured with Trusted Platform Modules (TPMs). This small hardware chip is capable of measuring and reporting a representation of the state of an IoT device. When connecting to a network, the IoT platform might have its state signed by the TPM in an anonymous way to prove both its genuineness and secure state through the Direct Anonymous Attestation (DAA) protocol. Currently standardised DAA schemes have their security supported on the factoring and discrete logarithm problems. Should a quantum-computer become available in the next few decades, these schemes will be broken. There is therefore a need to start developing a post-quantum DAA protocol. This paper presents a Lattice-based DAA (LDAA) scheme to meet this requirement. The security of this scheme is proved in the Universally Composable (UC) security model under the hardness assumptions of the Ring Inhomogeneous Short Integer Solution (Ring-ISIS) and Ring Learning With Errors (Ring-LWE) problems. Compared to the only other post-quantum DAA scheme available in related art, the storage requirements of the TPM are reduced twofold and the signature sizes 5 times. Moreover, experimental results show that the signing and verification operations are accelerated 1.1 and 2.0 times, respectively.

### Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications

Mon, 01/07/2019 - 16:39
We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter) common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups. Specifically, our construction has $O(\log Q)$ reduction to the SXDH, DLIN and matrix-DDH assumptions, where $Q$ is the number of simulated proofs given out. In addition, our core construction is structure-preserving, which means the public key and proofs are all group elements and the verification is entirely by checking pairing product equations. The USS-QA-NIZK primitive has many applications, including structure-preserving signatures (SPS), CCA2-secure publicly-verifiable public-key encryption (PKE), which in turn have applications to CCA-anonymous group signatures, blind signatures and unbounded simulation-sound Groth-Sahai NIZK proofs. We show that the almost tight security of our USS-QA-NIZK translates into constructions of all of the above applications with (almost) tight-security to standard assumptions such as SXDH and, more generally, $\D_k$-MDDH. Thus, we get the first publicly-verifiable (almost) tightly-secure multi-user/multi-challenge CCA2-secure PKE with practical efficiency under standard bilinear assumptions. Our (almost) tight SPS construction is also improved in the signature size over previously known constructions.

### Forward Secure Efficient Group Signature in Dynamic Setting using Lattices

Mon, 01/07/2019 - 13:30
Secret key exposure is at high risk in the computing infrastructure due to the increase in use of harmful devices. As a result, achieving forward secrecy is a preferable feature for any cryptosystem where the lifetime of a user is divided into discrete time periods. Forward secrecy preserves the security of past periods even if the secret key is exposed. In this work, we introduce the first lattice based forward secure dynamic group signature scheme. The existing forward secure group signature schemes are secure in the bilinear setting, and becomes insecure in the quantum computer period. We employ a complete binary tree whose leaves are associated with discrete time periods and label the nodes in a unique way that enables each node of the same depth to have different hamming weight. This helps the group manager to produce distinct certificates to distinct users. Our scheme withstand framing attacks, mis-identification attack and preserves anonymity under the learning with errors (LWE) and short integer solution (SIS) assumptions.

### OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-Computation Attacks

Mon, 01/07/2019 - 12:58
Password-Authenticated Key Exchange (PAKE) protocols allow two parties that only share a password to establish a shared key in a way that is immune to offline attacks. Asymmetric PAKE (aPAKE) strengthens this notion for the more common client-server setting where the server stores a mapping of the password and security is required even upon server compromise, that is, the only allowed attack in this case is an (inevitable) offline exhaustive dictionary attack against individual user passwords. Unfortunately, current aPAKE protocols (that dispense with the use of servers' public keys) allow for pre-computation attacks that lead to the instantaneous compromise of user passwords upon server compromise, thus forgoing much of the intended aPAKE security. Indeed, these protocols use - in essential ways - deterministic password mappings or use random "salt" transmitted in the clear from servers to users, and thus are vulnerable to pre-computation attacks. We initiate the study of "Strong aPAKE" protocols that are secure as aPAKE's but are also secure against pre-computation attacks. We formalize this notion in the Universally Composable (UC) settings and present two modular constructions using an Oblivious PRF as a main tool. The first builds a Strong aPAKE from any aPAKE (which in turn can be constructed from any PAKE) while the second builds a Strong aPAKE from any authenticated key-exchange protocol secure against reverse impersonation (a.k.a.\ KCI). Using the latter transformation, we show a practical instantiation of a UC-secure Strong aPAKE in the Random Oracle model. The protocol (OPAQUE") consists of 2 messages (3 with mutual authentication), requires 3 and 4 exponentiations for server and client, respectively (2 to 4 of which can be fixed-base depending on optimizations), provides forward secrecy, is PKI-free, supports user-side hash iterations, has a built-in facility for password-based storage and retrieval of secrets and credentials, and accommodates a user-transparent server-side threshold implementation.

### On Tight Security Proofs for Schnorr Signatures

Sun, 01/06/2019 - 08:57
The Schnorr signature scheme is the most efficient signature scheme based on the discrete logarithm problem and a long line of research investigates the existence of a tight security reduction for this scheme in the random oracle model. Almost all recent works present lower tightness bounds and most recently Seurin (Eurocrypt 2012) showed that under certain assumptions the non-tight security proof for Schnorr signatures in the random oracle by Pointcheval and Stern (Eurocrypt 1996) is essentially optimal. All previous works in this direction rule out tight reductions from the (one-more) discrete logarithm problem. In this paper we introduce a new meta-reduction technique, which shows lower bounds for the large and very natural class of generic reductions. A generic reduction is independent of a particular representation of group elements. Most reductions in state-of-the-art security proofs have this property. It is desirable, because then the reduction applies generically to any concrete instantiation of the group. Our approach shows unconditionally that there is no tight generic reduction from any natural non-interactive computational problem $\Pi$ defined over algebraic groups to breaking Schnorr signatures, unless solving $\Pi$ is easy. In an additional application of the new meta-reduction technique, we also unconditionally rule out any (even non-tight) generic reduction from natural non-interactive computational problems defined over algebraic groups to breaking Schnorr signatures in the non-programmable random oracle model.

### Snow White: Provably Secure Proofs of Stake

Sat, 01/05/2019 - 19:05
Decentralized cryptocurrencies have pushed deployments of distributed consensus to more stringent environments than ever before. Most existing protocols rely on proofs-of-work which require expensive computational puzzles to enforce, imprecisely speaking, “one vote per unit of computation”. The enormous amount of energy wasted by these protocols has been a topic of central debate, and well-known cryptocurrencies have announced it a top priority to alternative paradigms. Among the proposed alternative solutions, proofs-of-stake protocols have been of particular interest, where roughly speaking, the idea is to enforce “one vote per unit of stake”. Although the community have rushed to propose numerous candidates for proofs-of-stake, no existing protocol has offered formal proofs of security, which we believe to be a critical, indispensible ingredient of a distributed consensus protocol, particularly one that is to underly a high-value cryptocurrency system. In this work, we seek to address the following basic questions: • What kind of functionalities and robustness requirements should a consensus candidate offer to be suitable in a proof-of-stake application? • Can we design a provably secure protocol that satisfies these requirements? To the best of our knowledge, we are the first to formally articulate a set of requirements for consensus candidates for proofs-of-stake. We argue that any consensus protocol satisfying these properties can be used for proofs-of-stake, as long as money does not switch hands too quickly. Moreover, we provide the first consensus candidate that provably satisfies the desired robustness properties.

### On the Security of Two-Round Multi-Signatures

Sat, 01/05/2019 - 10:19
A multi-signature scheme allows a group of signers to collaboratively sign a message, creating a single signature that convinces a verifier that every individual signer approved the message. The increased interest in technologies to decentralize trust has triggered the proposal of highly efficient two-round Schnorr-based multi-signature schemes designed to scale up to thousands of signers, namely BCJ by Bagherzandi et al. (CCS 2008), MWLD by Ma et al. (DCC 2010), CoSi by Syta et al. (S&P 2016), and MuSig by Maxwell et al. (ePrint 2018). In this work, we point out serious security issues in all currently known two-round multi-signature schemes (without pairings). First, we prove that none of the schemes can be proved secure without radically departing from currently known techniques. Namely, we show that if the one-more discrete-logarithm problem is hard, then no algebraic reduction exists that proves any of these schemes secure under the discrete-logarithm or one-more discrete-logarithm problem. We point out subtle flaws in the published security proofs of the above schemes (except CoSi, which was not proved secure) to clarify the contradiction between our result and the existing proofs. Next, we describe practical sub-exponential attacks on all schemes, providing further evidence to their insecurity. Being left without two-round multi-signature schemes, we present mBCJ, a variant of the BCJ scheme that we prove secure under the discrete-logarithm assumption in the random-oracle model. Our experiments show that mBCJ barely affects scalability compared to CoSi, allowing 16384 signers to collaboratively sign a message in about 2 seconds, making it a highly practical and provably secure alternative for large-scale deployments.

### Breakdown Resilience of Key Exchange Protocols: NewHope, TLS 1.3, and Hybrids

Sat, 01/05/2019 - 04:31
Broken cryptographic algorithms and hardness assumptions are a constant threat to real-world protocols. Prominent examples are hash functions for which collisions become known, or number-theoretic assumptions which are threatened by advances in quantum computing. Especially when it comes to key exchange protocols, the switch to quantum-resistant primitives has begun and aims to protect today’s secrets against future developments, moving from common Diffie-Hellman-based solutions to Learning-With-Errors-based approaches, often via intermediate hybrid designs. To this date there exists no security notion for key exchange protocols that could capture the scenario of breakdowns of arbitrary cryptographic primitives to argue security of prior or even ongoing and future sessions. In this work we extend the common Bellare–Rogaway model to capture breakdown resilience of key exchange protocols. Our extended model allows us to study security of a protocol even in case of unexpected failure of employed primitives, may it be hash functions, signature schemes, key derivation functions, etc. We then apply our security model to analyze two real-world protocols, showing that resilience breakdown resilience for certain primitives is achieved by both an authenticated variant of the post-quantum secure key exchange protocol NewHope (Alkim et al., USENIX Security 2016), as well as by TLS 1.3, which has recently been standardized as RFC 8446 by the Internet Engineering Task Force. Furthermore, we provide a security analysis of a generic hybrid key exchange protocol, where one of the key exchange components may become insecure. This demonstrates the utility of our stronger notion for such designs.

### Accountable Tracing Signatures from Lattices

Thu, 01/03/2019 - 14:19
Group signatures allow users of a group to sign messages anonymously in the name of the group, while incorporating a tracing mechanism to revoke anonymity and identify the signer of any message. Since its introduction by Chaum and van Heyst (EUROCRYPT 1991), numerous proposals have been put forward, yielding various improvements on security, efficiency and functionality. However, a drawback of traditional group signatures is that the opening authority is given too much power, i.e., he can indiscriminately revoke anonymity and there is no mechanism to keep him accountable. To overcome this problem, Kohlweiss and Miers (PoPET 2015) introduced the notion of accountable tracing signatures ($\mathsf{ATS}$) - an enhanced group signature variant in which the opening authority is kept accountable for his actions. Kohlweiss and Miers demonstrated a generic construction of $\mathsf{ATS}$ and put forward a concrete instantiation based on number-theoretic assumptions. To the best of our knowledge, no other $\mathsf{ATS}$ scheme has been known, and the problem of instantiating $\mathsf{ATS}$ under post-quantum assumptions, e.g., lattices, remains open to date. ~~In this work, we provide the first lattice-based accountable tracing signature scheme. The scheme satisfies the security requirements suggested by Kohlweiss and Miers, assuming the hardness of the Ring Short Integer Solution ($\mathsf{RSIS}$) and the Ring Learning With Errors ($\mathsf{RLWE}$) problems. At the heart of our construction are a lattice-based key-oblivious encryption scheme and a zero-knowledge argument system allowing to prove that a given ciphertext is a valid $\mathsf{RLWE}$ encryption under some hidden yet certified key. These technical building blocks may be of independent interest, e.g., they can be useful for the design of other lattice-based privacy-preserving protocols.

### Function Private Predicate Encryption for Low Min-Entropy Predicates

Thu, 01/03/2019 - 14:18
In this work, we propose new predicate encryption schemes for zero inner-product encryption (ZIPE) and non-zero inner-product encryption (NIPE) predicates from prime-order bilinear pairings, which are both attribute and function private in the public-key setting. Our ZIPE scheme is adaptively attribute private under the standard Matrix DDH assumption for unbounded collusions. It is additionally computationally function private under a min-entropy variant of the Matrix DDH assumption for predicates sampled from distributions with superlogarithmic min-entropy. Existing (statistically) function private ZIPE schemes due to Boneh et al. [Crypto’13, Asiacrypt’13] necessarily require predicate distributions with significantly larger min-entropy in the public-key setting. Our NIPE scheme is adaptively attribute private under the standard Matrix DDH assumption, albeit for bounded collusions. It is also computationally function private under a min-entropy variant of the Matrix DDH assumption for predicates sampled from distributions with super-logarithmic min-entropy. To the best of our knowledge, existing NIPE schemes from bilinear pairings were neither attribute private nor function private. Our constructions are inspired by the linear FE constructions of Agrawal et al. [Crypto’16] and the simulation secure ZIPE of Wee [TCC’17]. In our ZIPE scheme, we show a novel way of embedding two different hard problem instances in a single secret key - one for unbounded collusion-resistance and the other for function privacy. With respect to NIPE, we introduce new techniques for simultaneously achieving attribute and function privacy. We also show natural generalizations of our ZIPE and NIPE constructions to a wider class of subspace membership, subspace non-membership and hidden-vector encryption predicates.

### Two round multiparty computation via Multi-key fully homomorphic encryption with faster homomorphic evaluations

Thu, 01/03/2019 - 14:18
Multi-key fully homomorphic encryption (MKFHE) allows computations on ciphertexts encrypted by different users (public keys), and the results can be jointly decrypted using the secret keys of all the users involved. The NTRU-based scheme is an important alternative to post-quantum cryptography, but the NTRU-based MKFHE has the following drawbacks, which cause it inefficient in scenarios such as secure multi-party computing (MPC). One is the relinearization technique used for key switching takes up most of the time of the scheme’s homomorphic evaluation, the other is that each user needs to decrypt in sequence, which makes the decryption process complicated. We propose an efficient leveled MKFHE scheme, which improves the efficiency of homomorphic evaluations, and constructs a two-round (MPC) protocol based on this. Firstly, we construct an efficient single key FHE with less relinearization operations. We greatly reduces the number of relinearization operations in homomorphic evaluations process by separating the homomorphic multiplication and relinearization techniques. Furthermore, the batching technique and a specialization of modulus can be applied to our scheme to improve the efficiency. Secondly, the efficient single-key homomorphic encryption scheme proposed in this paper is transformed into a multi-key vision according to the method in LTV12 scheme. Finally, we construct a distributed decryption process which can be implemented independently for all participating users, and reduce the number of interactions between users in the decryption process. Based on this, a two-round MPC protocol is proposed. Experimental analysis shows that the homomorphic evaluation of the single-key FHE scheme constructed in this paper is 2.4 times faster than DHS16, and the MKFHE scheme constructed in this paper can be used to implement a two-round MPC protocol effectively, which can be applied to secure MPC between multiple users under the cloud computing environment.

### Non-Interactive Zero Knowledge and Correlation Intractability from Circular-Secure FHE

Thu, 01/03/2019 - 14:18
We construct non-interactive zero-knowledge (NIZK) arguments for $\mathsf{NP}$ from any circular-secure fully homomorphic encryption (FHE) scheme. In particular, we obtain such NIZKs under a circular-secure variant of the learning with errors (LWE) problem while only assuming a standard (poly/negligible) level of security. Our construction can be modified to obtain NIZKs which are either: (1) statistically zero-knowledge arguments in the common random string model or (2) statistically sound proofs in the common reference string model. We obtain our result by constructing a new correlation-intractable hash family [Canetti, Goldreich, and Halevi, JACM~'04] for a large class of relations, which suffices to apply the Fiat-Shamir heuristic to specific 3-message proof systems. In particular, assuming circular secure FHE, our hash function $h$ ensures that for any function $f$ of some a-priori bounded circuit size, it is hard to find an input $x$ such that $h(x)=f(x)$. This continues a recent line of works [Holmgren and Lombardi, FOCS~'18; Canetti et al., ePrint~'18] focused on instantiating special forms of correlation intractability and Fiat-Shamir under weaker assumptions. Another consequence of our hash family construction is that, assuming circular-secure FHE, the classic quadratic residuosity protocol of [Goldwasser, Micali, and Rackoff, SICOMP~'89] is not zero knowledge when repeated in parallel. We also show that, under the plain LWE assumption (without circularity), our hash family is a universal correlation intractable family for general relations, in the following sense: If there exists any hash family of some description size that is correlation-intractable for general (even inefficient) relations, then our specific construction (with a comparable size) is correlation-intractable for general (efficiently verifiable) relations.

### qSCMS: Post-quantum certificate provisioning process for V2X

Thu, 01/03/2019 - 14:16
Security and privacy are paramount in the field of intelligent transportation systems (ITS). This motivates many proposals aiming to create a Vehicular Public Key Infrastructure (VPKI) for managing vehicles’ certificates. Among them, the Security Credential Management System (SCMS) is one of the leading contenders for standardization in the US. SCMS provides a wide array security features, which include (but are not limited to) data authentication, vehicle privacy and revocation of misbehaving vehicles. In addition, the key provisioning process in SCMS is realized via the so-called \emph{butterfly key expansion}, which issues arbitrarily large batches of pseudonym certificates in response to a single client request. Although promising, this process is based on classical elliptic curve cryptography (ECC), which is known to be susceptible to quantum attacks. Aiming to address this issue, in this work we propose a post-quantum \emph{butterfly key expansion} process. The proposed protocol relies on lattice-based cryptography, which leads to competitive key, ciphertext and signature sizes. Moreover, it provides low bandwidth utilization when compared with other lattice-based schemes, and, like the original SCMS, addresses the security and functionality requirements of vehicular communication.

### Senopra: Reconciling Data Privacy and Utility via Attested Smart Contract Execution

Thu, 01/03/2019 - 14:16
The abundance of smart devices and sensors has given rise to an unprecedented large-scale data collection. While this benefits various data-driven application domains, it raises numerous security and privacy concerns. In particular, recent high-profile data breach incidents demonstrate security dangers and single point vulnerability of multiple systems. Moreover, even if the data is properly protected at rest (i.e., during storage), data confidentiality may still be compromised once it is fed as input to computations. In this paper, we introduce Senopra, a privacy-preserving data management framework that leverages trusted execution environment and confidentiality-preserving smart contract system to empower data owners with absolute control over their data. More specifically, the data owners can specify fine-grained access policies governing how their captured data is accessed. The access policies are then enforced by a policy agent that operates in an autonomous and confidentiality-preserving manner. To attain scalability and efficiency, Senopra exploits Key Aggregation Cryptosystem (KAC) for key management, and incorporates an optimisation that significantly improves KAC's key reconstruction cost. Our experimental study shows that Senopra can support privacy- preserving data management at scale with low latency.

### Multi-dimensional Packing for HEAAN for Approximate Matrix Arithmetics

Thu, 01/03/2019 - 14:15
HEAAN is a homomorphic encryption (HE) scheme for approximate arithmetics. Its vector packing technique proved its potential in cryptographic applications requiring approximate computations, including data analysis and machine learning. In this paper, we propose MHEAAN - a generalization of HEAAN to the case of a tensor structure of plaintext slots. Our design takes advantage of the HEAAN scheme, that the precision losses during the evaluation are limited by the depth of the circuit, and it exceeds no more than one bit compared to unencrypted approximate arithmetics, such as floating point operations. Due to the multi-dimensional structure of plaintext slots along with rotations in various dimensions, MHEAAN is a more natural choice for applications involving matrices and tensors. We provide a concrete two-dimensional construction and show the efficiency of our scheme on several matrix operations, such as matrix multiplication, matrix transposition, and inverse. As an application, we implement the non-interactive Deep Neural Network (DNN) classification algorithm on encrypted data and encrypted model. Due to our efficient bootstrapping, the implementation can be easily extended to DNN structure with an arbitrary number of hidden layers