International Association
for Cryptologic Research

In our previous work, we have proposed a framework which allows tools

that can check standard noninterference properties but a priori

cannot deal with cryptography to establish cryptographic

indistinguishability properties, such as privacy properties, for

Java programs. We refer to this framework as the CVJ framework

(Cryptographic Verification of Java Programs) in this paper.

While so far the CVJ framework directly supports public-key

encryption (without corruption and without a public-key

infrastructure) only, in this work we further instantiate the

framework to support, among others, public-key encryption and

digital signatures, both with corruption and a public-key

infrastructure, as well as (private) symmetric encryption. Since

these cryptographic primitives are very common in security-critical

applications, our extensions make the framework much more widely

applicable.

To illustrate the usefulness and applicability of the extensions

proposed in this paper, we apply the framework along with the tool

Joana, which allows for the fully automatic verification of

noninterference properties of Java programs, to establish

cryptographic privacy properties of a (non-trivial) cloud storage

application, where clients can store private information on a remote

server.

In our previous work, we have proposed a framework which allows tools

that can check standard noninterference properties but a priori

cannot deal with cryptography to establish cryptographic

indistinguishability properties, such as privacy properties, for

Java programs. We refer to this framework as the CVJ framework

(Cryptographic Verification of Java Programs) in this paper.

While so far the CVJ framework directly supports public-key

encryption (without corruption and without a public-key

infrastructure) only, in this work we further instantiate the

framework to support, among others, public-key encryption and

digital signatures, both with corruption and a public-key

infrastructure, as well as (private) symmetric encryption. Since

these cryptographic primitives are very common in security-critical

applications, our extensions make the framework much more widely

applicable.

To illustrate the usefulness and applicability of the extensions

proposed in this paper, we apply the framework along with the tool

Joana, which allows for the fully automatic verification of

noninterference properties of Java programs, to establish

cryptographic privacy properties of a (non-trivial) cloud storage

application, where clients can store private information on a remote

server.

Mobile text messages are currently vulnerable to inspection, modification, and replay by network operators and those that influence network operators. This paper describes a set of protocols that provide end-to-end message confidentiality, integrity, and authenticity over the high latency, low bandwidth, Short Message Service provided by GSM networks.

This paper introduces the use of channel equalization as a method of simplifying side channel analysis attacks, by eeffectively collapsing all points in a power measurement trace into a single random variable. This uses a simple Finite Impulse Response (FIR) linear equalizer, which has been studied extensively in communications systems. In addition the estimation of a channel model is used in developing the Channel Estimation Analysis (CEA), which is a generic attack requiring similar assumptions to the Correlation Power Analysis (CPA) attack. Both channel equalization and the CEA attack are straight-forward to apply to real systems, and Python examples are provided. Results of attacking unprotected AES-128 and protected AES-256RSM on a microcontroller are provided.

Group homomorphic encryption represents one of the most important building blocks in modern cryptography. It forms the basis of widely-used, more sophisticated primitives, such as CCA2-secure encryption or secure multiparty computation. Unfortunately, recent advances in quantum computation show that many of the existing schemes completely break down once quantum computers reach maturity (mainly due to Shor\'s algorithm). This leads to the challenge of constructing quantum-resistant group homomorphic cryptosystems.

In this work, we prove the general impossibility of (abelian) group homomorphic encryption in the presence of quantum adversaries, when assuming the IND-CPA security notion as the minimal security requirement. To this end, we prove a new result on the probability of sampling generating sets of finite (sub-)groups if sampling is done with respect to an arbitrary, unknown distribution. Finally, we provide a sufficient condition on homomorphic encryption schemes for our quantum attack to work and discuss its satisfiability in non-group homomorphic cases. The impact of our results on recent fully homomorphic encryption schemes poses itself as an open question.

We present Lyra, a password-based key derivation scheme based on cryptographic sponges. Lyra was designed to be strictly sequential (i.e., not easily parallelizable), providing strong security even against attackers that use multiple processing cores (e.g., custom hardware or a powerful GPU). At the same time, it is very simple to implement in software and allows legitimate users to fine-tune its memory and processing costs according to the desired level of security against brute force password guessing. We compare Lyra with similar-purpose state-of-the-art solutions, showing how our proposal provides a higher security level and overcomes limitations of existing schemes. Specfically, we show that if we fix Lyra\'s total processing time t in a legitimate platform, the cost of a memory-free attack against the algorithm is exponential, while the best known result in the literature (namely, against the scrypt algorithm) is quadratic. In addition, for an identical same processing time, Lyra allows for a higher memory usage than its counterparts, further increasing the cost of brute force attacks.

Random numbers have been one of the most useful

objects in statistics, computer science, cryptography, modeling,

simulation, and other applications though it is very dicult to

construct true randomness. Many solutions (e.g., cryptographic

pseudorandom generators) have been proposed to harness or

simulate randomness and many statistical testing techniques have

been proposed to determine whether a pseudorandom generator

produces high quality randomness. NIST SP800-22 (2010) proposes

the state of art testing suite for (pseudo) random generators

to detect deviations of a binary sequence from randomness. On

the one hand, as a counter example to NIST SP800-22 test suite,

it is easy to construct functions that are considered as GOOD

pseudorandom generators by NIST SP800-22 test suite though

the output of these functions are easily distinguishable from the

uniform distribution. Thus these functions are not pseudorandom

generators by definition. On the other hand, NIST SP800-22

does not cover some of the important laws for randomness. Two

fundamental limit theorems about random binary strings are

the central limit theorem and the law of the iterated logarithm

(LIL). Several frequency related tests in NIST SP800-22 cover

the central limit theorem while no NIST SP800-22 test covers

LIL.

This paper proposes techniques to address the above challenges

that NIST SP800-22 testing suite faces. Firstly, we propose

statistical distance based testing techniques for (pseudo) random

generators to reduce the above mentioned Type II errors in NIST

SP800-22 test suite. Secondly, we propose LIL based statistical

testing techniques, calculate the probabilities, and carry out

experimental tests on widely used pseudorandom generators

by generating around 30TB of pseudorandom sequences. The

experimental results show that for a sample size of 1000 sequences

(2TB), the statistical distance between the generated sequences

and the uniform distribution is around 0.07 (with 0 for statistically

indistinguishable and 1 for completely distinguishable)

and the root-mean-square deviation is around 0.005. Though the

statistical distance 0.07 and RMSD 0.005 are acceptable for some

applications, for a cryptographic \"random oracle\", the preferred

statistical distance should be smaller than 0.03 and RMSD be

smaller than 0.001 at the sample size 1000. These results justify

the importance of LIL testing techniques designed in this paper.

The experimental results in this paper are reproducible and the

raw experimental data are available at author\'s website.

At Crypto 2012, Brakerski constructed a scale-invariant fully homomorphic encryption scheme based on the LWE problem, in which the same modulus is used throughout the evaluation process, instead of a ladder of moduli when doing \"modulus switching\". In this paper we describe a variant of the van Dijk et al. FHE scheme over the integers with the same scale-invariant property. Our scheme has a single secret modulus whose size is linear in the multiplicative depth of the circuit to be homomorphically evaluated, instead of exponential; we therefore construct a leveled fully homomorphic encryption scheme. This scheme can be transformed into a pure fully homomorphic encryption scheme using bootstrapping, and its security is still based on the Approximate-GCD problem.

We also describe an implementation of the homomorphic evaluation of the full AES encryption circuit, and obtain significantly improved performance compared to previous implementations: about 23 seconds (resp. 3 minutes) per AES block at the 72-bit (resp. 80-bit) security level on a mid-range workstation.

Finally, we prove the equivalence between the (error-free) decisional Approximate-GCD problem introduced by Cheon et al. (Eurocrypt 2013) and the classical computational Approximate-GCD problem. This equivalence allows to get rid of the additional noise in all the integer-based FHE schemes described so far, and therefore to simplify their security proof.

Support of membership revocation is a desirable functionality for any group signature scheme. Among the known revocation approaches, verifier-local revocation (VLR) seems to be the most flexible one, because it only requires the verifiers to possess some up-to-date revocation information, but not the signers. All of the contemporary VLR group signatures operate in the bilinear map setting, and all of them will be insecure once quantum computers become a reality. In this work, we introduce the first lattice-based VLR group signature, and thus, the first such scheme that is believed to be quantum-resistant. In comparison with existing lattice-based group signatures, our scheme has several noticeable advantages: support of membership revocation, logarithmic-size signatures, and weaker security assumption. In the random oracle model, our scheme is proved to be secure based on the hardness of the SIVP_soft-O(n^{1.5}) problem in general lattices - an assumption that is as weak as those of state-of-the-art lattice-based standard signatures. Moreover, our construction works without relying on encryption schemes, which is an intriguing feature for group signatures.

In this paper, we provide performance measures for software implementations of the NSA-designed Speck128 block cipher together with various existing authenticated encryption modes. We investigated Speck128 using GCM, CCM, EAX, OCB3, COPA, and PAEAD-1, and we briefly discuss performance advantages and disadvantages of each mode. Our results indicate that Speck128 is capable of performing extremely fast authenticated encryption, as fast as 3.4 cycles/byte on a modern x86-based 64-bit processor.

Submission: 10 February 2014
Notification: 14 March 2014
From June 30 to July 3
Location: Madrid, Spain
More Information: http://www.dis.uniroma1.it/~dasec/

We study in this work the potential side channel leakages of a hardware biometric comparison system that has been designed for fingerprints.

An embedded biometric system for comparison aims at comparing a stored biometric data with a freshly acquired one without the need to send the stored biometric data outside the system. Here one may try to retrieve the stored data via side channel, similarly as for embedded cryptographic modules where one may try to exploit side channel for attacking the modules.

On one hand, we show that we can find partial information by the means of simple Side Channel Analysis that may help to retrieve the stored fingerprint. On the other hand, we illustrate that reconstructing the fingerprint remains not trivial and we give some simple countermeasures to protect further the comparison algorithm.

Edwards\' elliptic curve form is popular in modern cryptographic implementations thanks to their fast, strongly unified addition formulas. Twisted Edwards curves with a = −1 are slightly faster, but their addition formulas are not complete over Fp where p ≡ 3 (mod 4). In this short note, we propose that designers specify Edwards curves, but implement scalar multiplications and the like using an isogenous twisted Edwards curve.

Submission: 1 March 2014
Notification: 22 March 2014
From June 3 to June 3
Location: Kyoto, Japan
More Information: http://conference.cs.cityu.edu.hk/asiaccsscc/

Submission: 10 February 2014
Notification: 10 March 2014
From June 3 to June 3
Location: Kyoto, Japan
More Information: http://www2.nict.go.jp/nsri/arch/asiapkc2014/

Some recent constructions based on LWE do not sample the secret uniformly at random but rather from some distribution which produces small entries. The most prominent of these is the binary-LWE problem where the secret vector is sampled from {0, 1}∗ or {−1, 0, 1}∗. We present a variant of the BKW algorithm for binary-LWE and other small secret variants and show that this variant reduces the complexity for solving binary-LWE. We also give estimates for the cost of solving binary-LWE instances in this setting and demonstrate the advantage of this BKW variant over standard BKW and lattice reduction techniques applied to the SIS problem. Our variant can be seen as a combination of the BKW algorithm with a lazy variant of modulus switching which might be of independent interest.

One of the most important applications of cryptography is the establishment of secure communication channels between two entities (e.g. a client and a server), and the protocol most widely used for this purpose is TLS.

A key goal of research in cryptography is to provide security proofs for cryptographic protocols. This task is particularly difficult if the considered protocol has not been designed with provable security in mind, as is the case for TLS.

Results on provable security differ with respect to (1) the assumptions made and (2) the statement that is proved to follow from the assumptions. It is important that the proved statement is of a form that allows for both comparisons of protocol performance, and for direct use in the proof of a higher-level protocol. Security statements should thus be exact (as opposed to asymptotic), giving precise upper bounds for the security level guaranteed by a protocol. Furthermore, a key to analyzing and designing cryptographic protocols is a modularization in which the role of each cryptographic primitive (e.g. encryption) or mechanism (e.g. nonce exchange) is made explicit, and the security of its application is proved in isolation, once and for all. The constructive cryptography framework provides a sound instantiation of this approach. A modular step constructs a specific resource from certain (assumed) resources, and the overall protocol is the composition of several such construction steps. The security proof for the overall protocol follows directly from the composition theorem as well as the individual (reasonably simple) security proofs for the modules. Moreover, the actual security statement for the overall protocol is of a standardized form, in terms of a resource, which makes it straight-forward to use the protocol in a higher-level context, with the overall security proof again following from the composition theorem.

In this paper, we provide such a constructive treatment of TLS. We provide a deconstruction of TLS into modular steps and a security proof for each step which, compared to previous work, results in the above mentioned advantages. For the key-exchange step in particular, we analyze the RSA-based and both Diffie-Hellman-based variants (with static and ephemeral server key) under a non-randomizability assumption for RSA-PKCS and the Gap Diffie-Hellman assumption, respectively; in all cases we make use of random oracles. In general, since the design of TLS is not modular, the constructive decomposition is less fine-grained than one might wish to have and than it is for a modular design. This paper therefore also suggests new insights into the intrinsic problems incurred by a non-modular protocol design such as that of TLS.

Attribute-based encryption (ABE) is a type of public key encryption that allows users to encrypt and decrypt messages based on user attributes. For instance, one can encrypt a message to any user

satisfying the boolean formula (``crypto conference attendee\'\' AND ``PhD student\'\') OR ``IACR member\'\'. One drawback is that encryption and key generation computational costs scale with the complexity of the access policy or number of attributes. In practice, this makes

encryption and user key generation a possible bottleneck for some applications.

To address this problem, we develop new techniques for ABE that split the computation for these algorithms into two phases: a preparation phase that does the vast majority of the work to encrypt a message or create a secret key *before* it knows the message or the attribute list/access control policy that will be used (or even the size of the list or policy). A second phase can then rapidly assemble an ABE ciphertext or key when the specifics become known. This concept is sometimes called ``online/offline\'\' encryption when only the message is unknown during the preparation phase; we note that the addition of unknown attribute lists and access policies makes ABE significantly more challenging.

One motivating application for this technology is mobile devices: the preparation work can be performed while the phone is plugged into a power source, then it can later rapidly perform ABE operations on the move without significantly draining the battery.

Most of the lightweight block ciphers are nibble-oriented as the implementation of a 4-bit S-box is much more compact than an 8-bit S-box. This paper proposes a novel implementation of multiplicative inverse for 8-bit S-boxes using LFSR requiring only 138 gate-equivalent. It can be shown that if such S-boxes are adopted for the AES it takes less than 50 gate-equivalent per S-box in parallel implementation. Canright\'s \\cite{Canright} implementation of the AES S-box is five times more expensive compared to this method for AES-like S-boxes. With this powerful scheme, a lightweight block cipher can be designed using an 8-bit S-box.

It is well known that almost all random subset sum

instances with density less than 0.6463... can be solved with an

$l_{2}$-norm SVP oracle by Lagarias and Odlyzko. Later, Coster

\\emph{et al.} improved the bound to 0.9408... by using a different

lattice. In this paper, we generalize this classical result to

$l_p$-norm. More precisely, we show that for $p\\in \\mathbb{Z}^{+}$,

an $l_p$-norm SVP oracle can be used to solve almost all random

subset sum instances with density bounded by $\\delta_p$, where

$\\delta_1=0.5761$ and $\\delta_p =

1/(\\frac{1}{2^p}\\log_2(2^{p+1}-2)+\\log_2(1+\\frac{1}{(2^p-1)(1-(\\frac{1}{2^{p+1}-2})^{(2^p-1)})})))$

for $p\\geq 3$(asymptotically, $\\delta_p\\approx 2^p/(p+2)$). Since

$\\delta_p$ goes increasingly to infinity when $p$ tends to infinity,

it can be concluded that an $l_p$-norm SVP oracle with bigger $p$

can solve more subset sum instances. An interesting phenomenon is

that an $l_p$-norm SVP oracle with $p\\geq 3$ can help solve almost

all random subset sum instances with density one, which are thought

to be the most difficult instances.