International Association
for Cryptologic Research

In 2005, Juels and Weis proposed HB+, a perfectly adapted authentication protocol for resource-constrained devices such as RFID tags. The HB+ protocol is based on the Learning Parity with Noise (LPN) problem and is proven secure against active adversaries. Since a man-in-the-middle attack on HB+ due to Gilbert et al. was published, many proposals have been made to improve the HB+ protocol. But none of these was formally proven secure against general man-in-the-middle adversaries.

In this paper we present a solution to make the HB+ protocol resistant to general man-in-the-middle adversaries without exceeding the computational and storage capabilities of the RFID tag.

In order to obtain differential patterns over many rounds of a cryptographic primitive, the cryptanalyst often needs to work on local differential trail analysis. Examples include merging two differential trail parts into one or, in the case of boomerang and rectangle attacks, connecting two short trails within the quartet boomerang setting. In the latter case, as shown by Murphy in 2011, 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 and SHACAL-1 block ciphers and SM3 hash function 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.

We propose a log signing scheme that enables (a) verification of the integrity of the whole log, and (b) presentation of any record, along with a compact proof that the record has not been altered since the log was signed, without leaking any information about the contents of other records in the log. We give a formal proof of the security of the proposed scheme, discuss practical considerations, and provide an implementation case study.

In this paper, we present a simpler and more restricted variant of the universally composable security (UC) framework that is suitable for ``standard\'\' two-party and multiparty computation tasks. Many of the complications of the UC framework exist in order to enable more general tasks than classic secure computation. This generality may be a barrier to entry for those who are used to the stand-alone model of secure computation and wish to work with universally composable security but are overwhelmed by the differences. The variant presented here (called simplified universally composable security, or just SUC) is closer to the definition of security for multiparty computation in the stand-alone setting. The main difference is that a protocol in the SUC framework runs with a \\emph{fixed set of parties} who know each other\'s identities ahead of time, and machines \\emph{cannot be added dynamically} to the execution. As a result, the definitions of polynomial time and protocol composition are much simpler. In addition, the SUC framework has authenticated channels built in, as is standard in previous definitions of security, and all communication is done via the adversary in order to enable arbitrary scheduling of messages. Due to these differences, not all cryptographic tasks can be expressed in the SUC framework. Nevertheless, standard secure computation tasks (like secure function evaluation) can be expressed. Importantly, we show a natural security-preserving transformation from protocols in the SUC model to protocols in the full-fledged UC model. Consequently, the UC composition theorem holds in the SUC model, and any protocol that is proven secure under SUC can be transformed to a protocol that is secure in the UC model.

An obfuscator $\\O$ is Virtual Grey Box (VGB) for a class $\\C$ of circuits if, for any $C\\in\\C$ and any predicate $\\pi$, deducing $\\pi(C)$ given $\\O(C)$ is tantamount to deducing $\\pi(C)$ given unbounded computational resources and polynomially many oracle queries to $C$. VGB obfuscation is often significantly more meaningful than indistinguishability obfuscation (IO). In fact, for some circuit families of interest VGB is equivalent to full-fledged Virtual Black Box obfuscation.

We investigate the feasibility of obtaining VGB obfuscation for general circuits. We first formulate a natural strengthening of IO, called {\\em strong IO} (SIO). Essentially, $\\O$ is SIO for class $\\C$ if $\\O(C)\\approx\\O(C\')$ whenever the pair $(C,C\')$ is taken from a distribution over $\\C$ where, for all $x$, $C(x)\\neq C\'(x)$ only with negligible probability.

We then show that an obfuscator is VGB for a class $\\C$ if and only if it is SIO for $\\C$. This result is unconditional and holds for any $\\C$. We also show that, for some circuit collections, SIO implies virtual black-box obfuscation.

Finally, we formulate a slightly stronger variant of the semantic security property of graded encoding schemes [Pass-Seth-Telang Crypto 14], and show that existing obfuscators, such as the obfuscator of Barak et al. [Eurocrypt 14], are SIO for all circuits in NC$^1$, assuming that the underlying graded encoding scheme satisfies our variant of semantic security.

{\\em Put together, we obtain VGB obfuscation for all NC$^1$ circuits under assumptions that are almost the same as those used by Pass et al. to obtain IO for NC$^1$ circuits.} We also show that semantic security is in essence {\\em necessary} for showing VGB obfuscation.

Universally composable secure computation was assumed to require trusted setups, until it was realized that parties exchanging (untrusted) tamper-proof hardware tokens allow an alternative approach (Katz; EUROCRYPT 2007). This discovery initialized a line of research dealing with two different types of tokens. Using only a single stateful token, one can implement general statistically secure two-party computation (Döttling, Kraschewski, Müller-Quade; TCC 2011); though all security is lost if an adversarial token receiver manages to physically reset and rerun the token. Stateless tokens, which are secure by definition against any such resetting-attacks, however, do provably not suffice for arbitrary secure computations (Goyal, Ishai, Mahmoody, Sahai; CRYPTO 2010).

We investigate the natural question of what is possible if an adversary can reset a token at most a bounded number of times (e.g., because each resetting attempt imposes a significant risk to trigger a self-destruction mechanism of the token). Somewhat surprisingly, our results come close to the known positive results with respect to non-resettable stateful tokens. In particular, we construct polynomially many instances of statistically secure and universally composable oblivious transfer, using only a constant number of tokens. Our techniques have some abstract similarities to previous solutions, which we grasp by defining a new security property for protocols that use oracle access. Additionally, we apply our techniques to zero-knowledge proofs and obtain a protocol that achieves the same properties as bounded-query zero-knowledge PCPs (Kilian, Petrank, Tardos; STOC 1997), even if a malicious prover may issue stateful PCP oracles.

The world just witnessed the surge of a new and powerful attacker,

which was able to coerce operators and acquire the necessary keys to break the privacy of users. Once the encryption key is exposed, the only viable measure to preserve data confidentiality is to limit the adversary\'s access to the ciphertext. This may be achieved, for example, using multi-cloud storage systems. These systems spread data across multiple servers in different administrative domains, to cater for availability and fault tolerance. If the adversary can only compromise a subset of these domains, multi-cloud storage systems may prevent the adversary from accessing the entire ciphertext. However, if data is encrypted using existing encryption schemes, spreading the ciphertext on multiple servers does not entirely solve the problem since an adversary which has the encryption key, can still compromise single servers and decrypt the ciphertext stored therein.

In this paper, we leverage multi-cloud storage systems to provide data confidentiality against an adversary which has access to the encryption key, and can compromise a large fraction of the storage servers. For this purpose, we first introduce a novel security definition that captures data confidentiality in the new adversarial

model. We then propose Bastion, a primitive that is secure according to our definition and, therefore, guarantees data confidentiality even when the encryption key is exposed, as long as the adversary cannot compromise all storage servers. We analyze the security of Bastion, and we evaluate its performance by means of a prototype implementation. Our results show that Bastion incurs less than 5%

overhead compared to existing semantically secure encryption modes. We also discuss practical insights with respect to the integration of Bastion in commercial multi-cloud storage systems.

Near Field Communication (NFC) is one the most recent technologies in the area of application development and service delivery via mobile phone. NFC enables the mobile phone to act as identification and a credit card for customers. Dynamic relationships of NFC ecosystem players in an NFC transaction process make them partners in a way that sometimes they should share their access permissions on the applications that are running in the service environment. One of the technologies that can be used to ensure secure NFC transactions is cloud computing which offers wide range advantages compare to the use of a Secure Element (SE) as a single entity in an NFC enabled mobile phone. In this paper, we propose a protocol based on the concept of NFC mobile payments. Accordingly, we present an extended version of the NFC cloud Wallet model, in which, the Secure Element (SE) in the mobile device is used for customer authentication whereas the customer\'s banking credentials are stored in a cloud under the control of the Mobile Network Operator (MNO). In this circumstance, MNO plays the role of network carrier which is responsible for controlling all the credentials transferred to the end user. The proposed protocol eliminates the requirement of a shared secret between the Point Of Sale (POS) and the MNO before execution of the protocol, a mandatory requirement in the earlier version of this protocol. This makes it more practicable and user friendly. At the end, we provide a detailed analysis of the protocol where we discuss multiple attack scenarios.

Secure computation on encrypted data stored on untrusted clouds is an important goal. Existing secure arithmetic computation techniques, such as fully homomorphic encryption (FHE) and somewhat homomorphic encryption (SWH), have prohibitive performance and/or storage costs for the majority of practical applications. In this work, we investigate a new secure arithmetic computation primitive called switchable homomorphic encryption (SHE) that securely switches between existing inexpensive partially homomorphic encryption techniques to evaluate arbitrary arithmetic circuits over integers. SHE is suited for use in a two-cloud model that is practical, but which makes stronger assumptions than the standard single-cloud server model. The security of our SHE solution relies on two non-colluding parties, in which security holds as long as one of them is honest. We benchmark SHE directly against existing secure arithmetic computation techniques---FHE and SWH---on real clouds (Amazon and Rackspace)

using microbenchmarks involving fundamental operations utilized in many privacy-preserving computation applications. Experimentally, we find that SHE offers a new design point for computing on large data---it has reasonable ciphertext and key sizes, and is consistently faster by several (2--3) orders of magnitude compared to FHE and SWH on circuits involving long chain of multiplications. SHE exhibits slower performance only in certain cases, when batch (or parallel) homomorphic evaluation is possible, only against SWH schemes (which have limited expressiveness and potentially high ciphertext and key storage costs).

This paper presents a highly optimized architecture for Advanced Encryption Standard (AES) by dividing and merging (combining) different sub operations in AES algorithm. The proposed architecture uses ten levels of pipelining to achieve higher throughput and uses Block-RAM utility to reduce slice utilization which subsequently increases the efficiency. It achieves the data stream of 57 Gbps at 451 MHz working frequency and obtains 36% improvement in efficiency to the best known similar design throughput per area (Throughput/Area) and 35% smaller in slice area. This architecture can easily be embedded with other modules because of significantly reduced slice utilization.

This paper presents a standard-cell-based semi-automatic design methodology of a new conceptual countermeasure against electromagnetic (EM) analysis and fault-injection attacks. The countermeasure namely EM attack sensor utilizes LC oscillators which detect variations in the EM field around a cryptographic LSI caused by a micro probe brought near the LSI. A dual-coil sensor architecture with an LUT-programming-based digital calibration can prevent a variety of microprobe-based EM attacks that cannot be thwarted by conventional countermeasures. All components of the sensor core are semi-automatically designed by standard EDA tools with a fully-digital standard cell library and hence minimum design cost. This sensor can be therefore scaled together with the cryptographic LSI to be protected. The sensor prototype is designed based on the proposed methodology together with a 128bit-key composite AES processor in 0.18um CMOS with overheads of only 1.9% in area, 7.6% in power, and 0.2% in performance, respectively. The validity against a variety of EM attack scenarios has been verified successfully.

In this paper, we propose a novel technique, called multi-output filtering model, to study the non-randomness property of a cryptographic algorithm such as message authentication codes and block ciphers. A multi-output filtering model consists of a linear feedback shift register (LFSR) and a multi-output filtering function.

Our contribution in this paper is twofold. First, we propose an attack technique under IND-CPA using the multi-output filtering model.

By introducing a distinguishing function, we theoretically determine the success rate of this attack. In particular, we construct a distinguishing function based on the distribution of the linear complexity of component sequences, and apply it on studying $\\T$\'s $f_1$ algorithm, $\\AES$, $\\Kasumi$ and $\\Present$. We demonstrate that the success rate of the attack on $\\Kasumi$ and $\\Present$ is non-negligible, but $f_1$ and $\\AES$ are resistant to this attack.

Second, we study the distribution of the cryptographic properties of component functions of a random primitive in the multi-output filtering model. Our experiments show some non-randomness in the distribution of algebraic degree and nonlinearity for $\\Kasumi$.

Several fault attacks against pairing-based

cryptography have been described theoretically in recent

years. Interestingly, none of these have been practically

evaluated. We accomplished this task and prove that fault

attacks against pairing-based cryptography are indeed

possible and are even practical -- thus posing a serious

threat. Moreover, we successfully conducted a second-order fault attack against an open source implementation

of the eta pairing on an AVR XMEGA A1. We injected

the first fault into the computation of the Miller Algorithm

and applied the second fault to skip the final exponentiation completely. We introduce a low-cost setup that

allowed us to generate multiple independent faults in one

computation. The setup implements these faults by clock

glitches which induce instruction skips. With this setup we

conducted the first practical fault attack against a complete

pairing computation.

This article presents a secure mutual testing strategy for System-on-Chips (SoCs) that implement cryptographic functionalities. Such approach eliminates the need for an additional trusted component that is used to test security sensitive cores in a SoC, like symmetric and public-key cryptographic modules. We combine two test approaches: Logic Built In Self Test (BIST) and secure scan-chain based testing and develop a strategy that preserves the test quality of the standard test methods, enhancing security of the testing scheme. In order to minimize the area overhead of the presented solution, we re-use the existing modules in different manners: a public-key cryptographic core to build the BIST infrastructure and a symmetric one to authenticate a device under test to a test server, thus preventing an unauthorized user from accessing the test interface. By doing so, we achieve both testability and security at the minimal cost.

Given a lattice $L\\subset\\R^n$ and some target vector, this paper studies the algorithms for approximate closest vector problem (CVP$_\\gamma$) by using an approximate shortest independent vectors problem oracle (SIVP$_\\gamma$). More precisely, if the distance between the target vector and the lattice is no larger than $\\frac{c}{\\gamma n}\\lambda_1(L)$ for any constant $c>0$, we give randomized and deterministic polynomial time algorithms to find a closest vector, which improves the known result by a factor of $2c$. Moreover, if the distance between the target vector and the lattice is larger than some quantity with respect to $\\lambda_n(L)$, using $\\SIVP_\\gamma$ oracle and Babai\'s nearest plane algorithm, we can solve $\\CVP_{\\gamma\\sqrt{n}}$ in deterministic polynomial time.

Specially, if the approximate factor $\\gamma\\in(1,2)$ in the

$\\SIVP_\\gamma$ oracle, we obtain a better reduction factor for CVP.

Reputation systems are used to compute and publish reputation scores for services or products. We consider reputation systems where users are allowed to rate products that they purchased previously. To obtain trustworthy reputations, they are allowed to rate these products only once. As long as users rate products once, they stay anonymous. Everybody is able to detect users deviating from the rate-products-only-once policy and the anonymity of such dishonest users can be revoked by a system manager. In this paper we present formal models for such reputation systems and their security. Based on group signatures presented by Boneh, Boyen, and Shacham we design an efficient reputation system that meets all our requirements.

We introduce four constructions of systematic authentication codes. The first two are built over finite fields using resilient functions and they provide optimal impersonation and substitution probabilities. The other two proposed codes are defined over Galois rings, one is based on resilient maps and it attains optimal probabilities as well, while the other uses maps whose Fourier transforms get higher values. For the special case of characteristic $p^2$, those maps are bent indeed, and this case is subsumed by our general construction of characteristic $p^s$, with $s\\geq 2$.

Let N1 = p1q1 and N2 = p2q2 be two RSA moduli, not necessarily

of the same bit-size. In 2009, May and Ritzenhofen proposed a

method to factor N1 and N2 given the implicit information that p1 and

p2 share an amount of least significant bits. In this paper, we propose a generalization of their attack as follows: suppose that some unknown multiples a1p1 and a2p2 of the prime factors p1 and p2 share an amount of their Most Significant Bits (MSBs) or an amount of their Least Significant Bits (LSBs). Using a method based on the continued fraction algorithm, we propose a method that leads to the factorization of N1 and N2. Using simultaneous diophantine approximations and lattice reduction, we extend the method to factor k 3 RSA moduli Ni = piqi, i = 1, . . . , k given the implicit information that there exist unknown multiples a1p1, . . . , akpk sharing an amount of their MSBs or their LSBs. Also, this paper extends many previous works where similar results were obtained when the pi\'s share their MSBs or their LSBs.

This paper presents three new attacks on the RSA cryptosystem.

The rst two attacks work when k RSA public keys (Ni, ei)

are such that there exist k relations of the shape eix-yi\\phi(Ni)=zi or of the shape eixi-y\\phi(Ni)=zi where Ni = piqi, \\phi(Ni)=(pi-1)(qi-1)

and the parameters x, xi, y, yi, zi are suitably small in terms of the prime factors of the moduli. We show that our attacks enable us to simultaneously factor the k RSA moduli Ni. The third attack works when the prime factors p and q of the modulus N = pq share an amount of their

least signicant bits (LSBs) in the presence of two decryption exponents

d1 and d2 sharing an amount of their most signicant bits (MSBs). The

three attacks improve the bounds of some former attacks that make RSA

insecure.

Functional encryption supports restricted decryption keys that allow users to learn specific functions of the encrypted messages. Whereas the vast majority of research on functional encryption has so far focused on the privacy of the encrypted messages, in many realistic scenarios it is crucial to offer privacy also for the functions for which decryption keys are provided.

Whereas function privacy is inherently limited in the public-key setting, in the private-key setting it has a tremendous potential. Specifically, one can hope to construct schemes where encryptions of messages $m_1, \\ldots, m_T$ together with decryption keys corresponding to functions $f_1, \\ldots, f_T$, reveal essentially no information other than the values $\\{ f_i(m_j)\\}_{i,j\\in [T]}$. Despite its great potential, the known function-private private-key schemes either support rather limited families of functions (such as inner products), or offer somewhat weak notions of function privacy.

We present a generic transformation that yields a function-private functional encryption scheme, starting with any non-function-private scheme for a sufficiently rich function class. Our transformation preserves the message privacy of the underlying scheme, and can be instantiated using a variety of existing schemes. Plugging in known constructions of functional encryption schemes, we obtain function-private schemes based either on obfuscation assumptions, on the Learning with Errors assumption, or even on general public-key encryption (offering various trade-offs between security and efficiency).