International Association
for Cryptologic Research

Over the past decade, besides authentication, ownership

management protocols have been suggested to transfer or

delegate the ownership of RFID tagged items. Recently, Niu et

al. have proposed an authentication and ownership management

protocol based on 16-bit pseudo random number generators and

exclusive-or operations which both can be easily implemented on

low-cost RFID passive tags in EPC global Class-1 Generation-2

standard. They claim that their protocol offers location and data

privacy and also resists against desynchronization attack. In this

paper, we analyze the security of their proposed authentication

and ownership management protocol and show that the protocol

is vulnerable to secret disclosure and desynchronization attacks.

The complexity of most of the attacks are only two runs of the

protocol and the success probability of the attacks are almost 1.

We highlight the privacy risks associated with the HTML5 Battery Status API. We put special focus on its implementation in the Firefox browser. Our study shows that websites can discover the capacity of users\' batteries by exploiting the high precision readouts provided by Firefox on Linux. The capacity of the battery, as well as its level, expose a fingerprintable surface that can be used to track web users in short time intervals. Our analysis shows that the risk is much higher for old or used batteries with reduced capacities, as the battery capacity may potentially serve as a tracking identifier. The fingerprintable surface of the API could be drastically reduced without any loss in the API\'s functionality by reducing the precision of the readings. We propose minor modifications to Battery Status API and its implementation in the Firefox browser to address the privacy issues presented in the study. Our bug report for Firefox was accepted and a fix is deployed.

We propose a new type of score function for Tardos traitor tracing codes. It is related to the recently introduced tally-based score function, but it utilizes more of the information available to the decoder. It does this by keeping track of sequences of symbols in the distributed codewords instead of looking at columns of the code matrix individually.

We derive our new class of score functions from a Neyman-Pearson hypothesis test and illustrate its performance with simulation results.

Finally we derive a score function for (medical) group testing applications.

A new systematic authentication scheme based on the Gray map

over Galois rings is introduced. The Gray map determines an isometry between

the Galois ring and a vector space over a Galois eld. The introduced code

attains optimal impersonation and substitution probabilities.

Recent results of Cascudo, Cramer, and Xing on the construction of arithmetic secret sharing schemes are improved by using some new bounds on the torsion limits of algebraic function fields. Furthermore, new bounds on the torsion limits of certain towers of function fields are given.

Concurrent non-malleable zero-knowledge (CNMZK) protocols are zero-knowledge protocols that are secure even against adversaries that interact with multiple provers and verifiers simultaneously. Recently, the first statistical CNMZK argument for NP was constructed under the DDH assumption (Orlandi el al., TCC\'14).

In this paper, we construct a statistical CNMZK argument for NP assuming only the existence of one-way functions. The security is proven via black-box simulation, and the round complexity is poly(n). Under the existence of collision-resistant hash functions, the round complexity can be reduced to w(log n), which is known to be essentially optimal for black-box concurrent zero-knowledge protocols.

Asymmetric-key cryptographic algorithms when implemented

on systems with branch predictors, are subjected

to side-channel attacks

exploiting the deterministic branch

predictor behavior due to their key-dependent input sequences. We show that branch predictors can also

leak information through the hardware

performance monitors which are

accessible by an adversary at the

user-privilege level. This paper presents

an iterative attack which target the

key-bits of 1024 bit RSA, where in

offline phase, the system\'s underlying

branch predictor is approximated

by a theoretical predictor in literature.

Subsimulations are performed

to classify the message-space into

distinct partitions based on the event

branch misprediction and the target key

bit value. In online phase, we ascertain

the secret key bit using branch mispredictions

obtained from the hardware performance

monitors which reflect the information of branch

miss due to the underlying predictor hardware.

We theoretically prove that the probability

of success of the attack is equivalent to the accurate

modelling of the theoretical predictor to the underlying system predictor. Experimentations reveal that the

success-rate increases with message-count and reaches such a significant value so as to consider side-channel

from the performance counters as a real threat

to RSA-like ciphers due

to the underlying branch predictors and

needs to be considered for developing secured-systems.

Modular exponentiation is core to today\'s main stream

public key cryptographic systems. In this article, we generalize the

classical fractional $w$NAF method for modular exponentiation -- the

classical method uses a digit set of the form $\\{1,3,\\dots,m\\}$

which is extended here to any set of odd integers of the form

$\\{1,d_2,\\dots, d_n\\}$. We give a formula for the average density of

non-zero terms in this new representation and discuss its asymptotic

behavior when those digits are randomly chosen from a given set. We

also propose a specific method for the precomputation phase of the

exponentiation algorithm.

This paper proposes a theoretical study and a full

overview of the design, evaluation and optimization of a PUF

based on transient element ring oscillators (TERO-PUF). We

show how, by following some simple design rules and strategies,

designers can build and optimize a TERO-PUF with state of the

art PUF characteristics in a standard CMOS technology. To this

end, we analyzed the uniqueness, steadiness and randomness of

responses generated from 30 test chips in a CMOS 350nm process

in nominal and corner voltage and temperature conditions.

Response generation schemes are proposed to optimize PUF

performances and reduce its area without noticeable loss in its

output quality. In particular, we show that the large area of the

basic blocks in the TERO-PUF is balanced by the high level

of entropy extracted in each basic block. Thus, the length of

the response to the same challenge is increased. Guidelines are

provided to balance reliability and randomness of the responses

and the design area.

Authenticated encryption (AE) schemes are symmetric-key encryption schemes ensuring strong notions of confidentiality and integrity. Although various AE schemes are known, there remains significant interest in developing schemes that are more efficient, meet even stronger security notions (e.g., misuse-resistance), or satisfy certain non-cryptographic properties (e.g., being patent-free).

We present an automated approach for analyzing and synthesizing blockcipher-based AE schemes, significantly extending prior work by Malozemoff et al. (CSF 2014) who synthesize encryption schemes satisfying confidentiality only. Our main insight is to restrict attention to a certain class of schemes that is expressive enough to capture several known constructions yet also admits automated reasoning about security. We use our approach to generate thousands of AE schemes with provable security guarantees, both known (e.g., variants of OCB and CCM) and new. Implementing two of these new schemes, we find their performance competitive with state-of-the-art AE schemes.

Many papers have proposed elliptic curves which are faster and easier to implement than the NIST prime-order curves. Most of these curves have had fields of size around $2^256$, and thus security estimates of around 128 bits. Recently there has been interest in a stronger curve, prompting designs such as Curve41417 and Microsoft\'s pseudo-Mersenne-prime curves.

Here I report on the design of another strong curve, called Ed448-Goldilocks. Implementations of this curve can perform very well for its security level on many architectures. As of this writing, this curve is favored by IRTF CFRG for inclusion in future versions of TLS along with Curve25519.

Round-optimal blind signatures are notoriously hard to construct in the standard model, especially in the malicious-signer model, where blindness must hold under adversarially chosen keys. This is substantiated by several impossibility results. The only construction that can be termed theoretically efficient, by Garg and Gupta (Eurocrypt\'14), requires complexity leveraging, inducing an exponential security loss.

We present a construction of practically efficient round-optimal blind signatures in the standard model. It is conceptually simple and builds on the recent structure-preserving signatures on equivalence classes (SPS-EQ) from Asiacrypt\'14. While the traditional notion of blindness follows from standard assumptions, we prove blindness under adversarially chosen keys under an interactive variant of DDH. However, we neither require non-uniform assumptions nor complexity leveraging.

We then show how to extend our construction to partially blind signatures and to blind signatures on message vectors, which yield a construction of one-show anonymous credentials à la \"anonymous credentials light\" (CCS\'13) in the standard model.

Furthermore, we give the first SPS-EQ construction under non-interactive assumptions and show how SPS-EQ schemes imply conventional structure-preserving signatures, which allows us to apply optimality results for the latter to SPS-EQ.

We show that the common proof technique of padding a circuit before IO obfuscation is sometimes necessary. That is, assuming indistinguishability obfuscation (IO) and one-way functions exist, we define samplers Sam_0, which outputs (aux_0, C_0), and Sam_1, which outputs (aux_1, C_1) such that:

- The distributions (aux_0, iO(C_0)) and (aux_1, iO(C_1)) are perfectly distinguishable.

- For padding s = poly(lambda)$, the distributions (aux_0, iO(C_0||0^s)) and (aux_1, iO(C_1||0^s)) are computationally indistinguishable.

We note this refutes the recent \"Superfluous Padding Assumption\" of Brzuska and Mittelbach.

Commitment schemes are among cryptography\'s most important building blocks. Besides their basic properties, hidingness and bindingness, for many applications it is important that the schemes applied support proofs of knowledge. However, all existing solutions which have been proven to provide these protocols are only computationally hiding or are not resistant against quantum adversaries. This is not suitable for long-lived systems, such as long-term archives, where commitments have to provide security also in the long run. Thus, in this work we present a new post-quantum unconditionally hiding commitment scheme that supports (statistical) zero-knowledge protocols and allows to refreshes the binding property over time. The bindingness of our construction relies on the approximate shortest vector problem, a lattice problem which is conjectured to be hard for polynomial approximation factors, even for a quantum adversary. Furthermore, we provide a protocol that allows the committer to prolong the bindingness property of a given commitment, while showing in zero-knowledge fashion that the value committed to did not change. In addition, our construction yields two more interesting features: 1) the ability to \"convert\" a Pedersen commitment into a lattice-based one, and 2) the construction of a hybrid approach whose bindingness relies on the discrete logarithm

and approximate shortest vector problems.

We propose a new voting scheme, BeleniosRF, that offers both strong receipt-freeness and end-to-end verifiability. It is strongly receipt-free in the sense that even dishonest voters cannot prove how they voted. We give a game-based definition capturing this property, inspired by and improving the original receipt-freeness definition by Benaloh and Tuinstra. Built upon the Helios protocol, BeleniosRF inherits from its simplicity.

We study the question of how much interaction is needed for unconditionally secure multiparty computation. We first consider the number of messages that need to be sent to compute a non-trivial function (such as the AND of several input bits), assuming that all players have input and get output. We show that for $n$ players and $t$ corruptions,

$n(t+3)/2$ messages is necessary, this holds already for semi-honest and static corruption. Note that for functions that can be securely computed in constant round, this bound is tight up to a constant factor. For the case $t=1$ and semi-honest security, we show that $2 n$ messages is also sufficient to compute a rich class of functions efficiently, showing that the bound is exact for $t=1$.

Next, we consider round complexity.

It is a long-standing open problem to determine whether all efficiently computable functions can also be efficiently computed in constant-round with {\\em unconditional} security. Providing a positive answer seems to require completely new ideas for protocol design. Motivated by this, we consider the question of whether we can compute any function securely, while minimizing the interaction of {\\em some of} the players? And if so, how many players can this apply to? Note that we still want the standard security guarantees (correctness, privacy, termination) and we consider the standard communication model with secure point-to-point channels. We answer the questions as follows: for passive security, with $n=2t+1$ players and $t$ corruptions, up to $t$ players can have minimal interaction, i.e., they send 1 message in the first round to each of the $t+1$ remaining players and receive one message from each of them in the last round. Using our result on message complexity, we show that this is (unconditionally) optimal. For malicious security with $n=3t+1$ players and $t$ corruptions, up to $t$ players can have minimal interaction, also this is shown to be optimal.

Homomorphic encryption allows computation on encrypted data and makes it possible to securely outsource computational tasks to untrusted environments. However, all proposed schemes are quite inefficient and homomorphic evaluation of ciphertexts usually takes several seconds on high-end CPUs, even for evaluating simple functions. In this work we investigate the potential of FPGAs for speeding up those evaluation operations. We propose an architecture to accelerate schemes based on the ring learning with errors (RLWE) problem and specifically implemented the somewhat homomorphic encryption scheme YASHE, which was proposed by Bos, Lauter, Loftus, and Naehrig in 2013. Due to the large size of ciphertexts and evaluation keys, on-chip storage of all data is not possible and external memory is required. For efficient utilization of the external memory we propose an efficient double-buffered memory access scheme and a polynomial multiplier based on the number theoretic transform (NTT). For the parameter set (n=16384,log_2(q)=512) capable of evaluating 9 levels of multiplications, we can perform a homomorphic addition in 48.67 and a homomorphic multiplication in 0.94 ms.

The celebrated work of Barak et al. (Crypto\'01) ruled out the possibility of virtual black-box (VBB) obfuscation for general circuits. The recent work of Canetti, Kalai, and Paneth (TCC\'15) extended this impossibility to the random oracle model as well assuming the existence of trapdoor permutations (TDPs). On the other hand, the works of Barak et al. (Crypto\'14) and Brakerski-Rothblum (TCC\'14) showed that general VBB obfuscation is indeed possible in idealized graded encoding models. The recent work of Pass and Shelat (Cryptology ePrint 2015/383) complemented this result by ruling out general VBB obfuscation in idealized graded encoding models that enable evaluation of constant-degree polynomials in finite fields.

In this work extend the above two impossibly results for general VBB obfuscation in idealized models. In particular we prove the following two results both assuming the existence of TDPs:

* There is no general VBB obfuscation in the generic group model of Shoup (Eurocrypt\'97) for {any abelian} group. By applying our techniques to the setting of Pass and Shelat we extend their result to any (even noncommutative) finite {ring}.

* There is no general VBB obfuscation even in the {random trapdoor permutation oracle} model. Our proof extends to any number of levels of hierarchical trapdoors.

One of the most important benefits of public cloud storage is outsourcing of management and maintenance with easy accessibility and retrievability over the internet. However, outsourcing data on the cloud brings new challenges such as integrity verification and privacy of data. More concretely, once the users outsource their data on the cloud they have no longer physical control over the data and this leads to the integrity protection issue. Hence, it is crucial to guarantee proof of data storage and integrity of the outsourced data. Several pairing-based au- diting solutions have been proposed utilizing the Boneh-Lynn-Shacham (BLS) short signatures. They basically provide a desirable and efficient property of non-repudiation protocols. In this work, we propose the first ID-based privacy-preserving public auditing scheme with message recov- erable signatures. Because of message recoverable auditing scheme, the message itself is implicitly included during the verification step that was not possible in previously proposed auditing schemes. Furthermore, we point out that the algorithm suites of existing schemes is either insecure or very inefficient due to the choice of the underlying bilinear map and its baseline parameter selections. We show that our scheme is more ef- ficient than the recently proposed auditing schemes based on BLS like short signatures.

Private Set Intersection (PSI) allows two parties to compute the intersection of private sets while revealing nothing more than the intersection itself. PSI needs to be applied to large data sets in scenarios such as measurement of ad conversion rates, data sharing, or contact discovery. Existing PSI protocols do not scale up well, and therefore some applications use insecure solutions instead.

We describe a new approach for designing PSI protocols based on permutation-based hashing, which enables to reduce the length of items mapped to bins while ensuring that no collisions occur. We denote this approach as Phasing, for Permutation-based Hashing Set Intersection. Phasing can dramatically improve the performance

of PSI protocols whose overhead depends on the length of the representations of input items.

We apply Phasing to design a new approach for circuit-based PSI protocols. The resulting protocol is up to 5 times faster than the previously best Sort-Compare-Shuffle circuit of Huang et al. (NDSS 2012). We also apply Phasing to the OT-based PSI protocol of Pinkas et

al. (USENIX Security 2014), which is the fastest PSI protocol to date. Together with additional improvements that reduce the computation complexity by a logarithmic factor, the resulting protocol improves run-time by a factor of up to 20 and can also have better communication overhead than the previously best PSI protocol in that respect. The new protocol is only moderately less efficient

than an insecure PSI protocol that is currently used by real-world applications, and is therefore the first secure PSI protocol that is scalable to the demands and the constraints of current real-world settings.