International Association
for Cryptologic Research

The advent of cloud computing has given rise to a plethora of work on verifiable delegation of computation. Homomorphic signatures are a powerful tool that can be tailored for verifiable computation, as long as they are efficiently verifiable. The main advantages of homomorphic signatures are twofold: (i) public verifiability: Any third party can verify the correctness of the delegated computation; (ii) statelessness: The verifier is not required to have access to the dataset on which the computation was performed. Thus in this paper, we design a homomorphic signature suitable for multivariate polynomials of bounded degree, and which draws upon the algebraic properties of eigenvectors and leveled multilinear maps. The proposed signature yields an efficient verification process (in an amortized sense) and supports offline-online signing. Furthermore, our signature is provably secure and its size grows only linearly with the degree of the evaluated polynomial.

Recently Attrapadung (Eurocrypt 2014) proposed a generic framework for fully (adaptively) secure predicate encryption (PE) based on a new primitive, called \\textit{pair encodings}. The authors shows that if the underlying pair encoding scheme is either perfectly secure or computationally (doubly-selectively) secure, then the PE scheme will be fully secure. Although the pair encodings were solely introduced for PE, we show that these can also be used to construct predicate signatures, a signature analogue of PE. More precisely, we propose a generic construction for predicate signature (PS) from the pair encoding schemes. Our construction provides the signer privacy, and unforgeability in the adaptive-predicate model. Thereafter, we instantiate many PS schemes with new results, e.g., the first PS schemes for regular languages, the first attribute-based signature (ABS) scheme with constant-size signature in adaptive-predicate model, the unbounded ABS with large universes in key-policy flavor etc.

Following the CCA conversions of Yamada et al. (PKC 2011, 2012) and Nandi et al. (ePrint Archive: 2015/457), one can have CCA secure PE from CPA-secure PE if the primitive PE has either verifiability or delegation. We show that the fully secure CPA-construction of Attrapadung holds the verifiability if we assume a very simple condition on the underlying pair encoding scheme. The aforesaid approach degrades the performance of the resultant CCA-secure PE scheme. As an alternative, we provide a direct fully secure CCA-construction for PE from the pair encoding schemes. This costs an extra computation of group element in encryption and an extra pairing computation in decryption as compared to CPA-construction of Attrapadung.

The predicate signcryption (PSC) is a super class of the existing class, attribute-based signcryption (ABSC), where the confidentiality, unforgeability and signer privacy are well preserved. By combining the proposed frameworks for PS and PE, we provide a generic construction for PSC from the pair encodings. It achieves the perfect privacy, and the strong unforgeability and CCA security in the adaptive-predicates model. The construction has the support of ``combined-setup\'\', where the distribution of public parameters and keys in the (implicit) signature and encryption schemes are identical. The instantiations of the proposed PSC, provide many new schemes, e.g., the first PSC schemes for regular languages, the first ABSC with either constant-size signatures or constant-size keys, the unbounded ABSC with large universes in adaptive-predicates model etc.

The University of Luxembourg (http://wwwen.uni.lu/) is seeking a PhD student to work on Authenticated Key Exchange and Quantum Key Distribution, under the supervision of Professor Peter Y.A. Ryan. The position is for three years, and may be extended to four.

More information is available at:

http://emea3.mrted.ly/trc1

If you are interested, please apply via this link. Applications will be considered as soon as they are received.

With organizations increasingly willing to outsource their network functions (e.g., firewalls, traffic shapers and intrusion detection systems) to the cloud, aiming to reduce the cost and complexity of maintaining networking infrastructures, the industry including Cisco, Arista, Alcatel-Lucent and alike are offering network function virtualization (NFV)-based solutions. However, outsourcing network functions in its current setting implies that sensitive network policies, such as firewall rules, are revealed to the cloud provider.

In this paper, we investigate the use of cryptographic primitives for processing outsourced network functions, so that the provider does not learn any sensitive information. We present a cryptographic treatment of privacy-preserving outsourcing of network functions, introducing security definitions as well as an abstract model of generic network functions, and then propose a few instantiations using partial homomorphic encryption and public-key encryption with keyword search. We show a proof-of-concept implementation of our constructions and show that network functions can be privately processed by an untrusted cloud provider in a few milliseconds.

In this paper, we consider the following question: Does composing protocols having game-theoretic security result in a secure protocol in the sense of game-theoretic security? In order to discuss the composability of game-theoretic properties, we study security of cryptographic protocols in terms of the universal composability (UC) and game theory simultaneously. The contribution of this paper is the following: (i) We propose a compiler of two-party protocols in the local universal composability (LUC) framework such that it transforms any two-party protocol secure against semi-honest adversaries into a protocol secure against malicious adversaries in the LUC framework; (ii) We consider the application of our compiler to oblivious transfer (OT) protocols, by which we obtain a construction of OT meeting both UC security and game-theoretic security.

We prove that a known approach to improve Shamir\'s celebrated secret sharing scheme; i.e., adding an information-theoretic authentication tag to the secret, can make it robust for $n$ parties against any collusion of size $\\delta n$, for any constant $\\delta \\in (0, 1/2)$. This result holds in the so-called \"non-rushing\" model in which the $n$ shares are submitted simultaneously for reconstruction. We thus obtain an efficient and robust secret sharing scheme in this model that is essentially optimal in all parameters including the share size which is $k(1+o(1)) + O(\\kappa)$, where $k$ is the secret length and $\\kappa$ is the security parameter. Like Shamir\'s scheme, in this modified scheme any set of more than $\\delta n$ honest parties can efficiently recover the secret.

Using algebraic geometry codes instead of Reed-Solomon codes, we decrease the share length to a constant (only depending on $\\delta$) while the number of shares $n$ can grow independently. In this case, when $n$ is large enough, the scheme satisfies the \"threshold\" requirement in an approximate sense; i.e., any set of $\\delta n(1+\\rho)$ honest parties, for arbitrarily small $\\rho > 0$, can efficiently reconstruct the secret.

The purpose of this lecture note is to introduce lattice based cryptography, which is thought to be a cryptosystem of post-quantum age. We have tried to give as many details possible specially for novice on the subject. Something may be trivial to an expert but

not to a novice.

Many fundamental problems about lattice are thought to be hard even against quantum computer, compared to factorization problem which can be solved easily with quantum computer, via the celebrated Shor factorization quantum algorithm. The rst part of our presentation is based on slides of Christ Peikert 2013 Bonn lecture (crypt@b-it2013). We, more or less, give somewhat detailed explanation of Professor Peikert\'s lecture slides. We unfortunately could not attend his Bonn class. We are afraid that there are many mistakes in this note; if any, they are due to our misunderstanding of the material. Part II of our lecture note is on ring LWE, based on the paper \\A tool-kit for Ring-LWE Cryptography\" by Lyubashevsky, Peikert and Regev. Part III is about multilinear maps together with cryptanalysis of GGH map due to Hu and Jia. Our presentation follows professor Steinfeld\'s lecture slides on GGHLite, and the paper by Yupu Hu and Huiwen Jia. When you read this lecture note, the corresponding original paper should be accompanied. We thank professor Jung Hee Cheon for introducing the subject and asking Dong Pyo Chi to give a lecture on the subject at the department of mathematics in Seoul National University. We also thank Hyeongkwan Kim for many helps, especially many corrections and improvements of the manuscript during the 2015 Summer session at UNIST. We also thank the students who took the classes at SNU and UNIST. The lecture was given by a novice for novice, so many mistakes are unavoidable. If the reader lets us know any errors, we will very much appreciate it.

Lattice-based cryptography is the use of conjectured hard

problems on point lattices in $\\R^{n}$ as the foundation for secure

cryptographic constructions. Attractive features of lattice

cryptography include: apparent resistance to quantum attacks

(in contrast with most number-theoretic cryptography), high asymptotic

efficiency and parallelism, security under worst-case

intractability assumptions, and solutions to long-standing open

problems in cryptography.

This work surveys most of the major developments in lattice

cryptography over the past ten years. The main focus is on the

foundational short integer solution (SIS) and learning

with errors (LWE) problems (and their more efficient ring-based

variants), their provable hardness assuming the worst-case

intractability of standard lattice problems, and their many

cryptographic applications.

Existing standards (ZigBee and Bluetooth Low Energy) for networked low-power wireless devices do not support secure association (or pairing) of new devices into a network: their association process is vulnerable to man-in-the-middle attacks. This paper addresses three essential aspects in attaining secure association for such devices.

First, we define a user-interface primitive, oblivious comparison, that allows users to approve authentic associations and abort compromised ones. This distills and generalizes several existing approve/abort mechanisms, and moreover we experimentally show that OC can be implemented using very little hardware: one LED and one switch.

Second, we provide a new Message Recognition Protocol (MRP) that allows devices associated using oblivious comparison to exchange authenticated messages without the use of public-key cryptography (which exceeds the capabilities of many IoT devices). This protocol improves upon previously proposed MRPs in several respects.

Third, we propose a robust definition of security for MRPs that is based on universal composability, and show that our MRP satisfies this definition.

This note describes a polynomial attack on the new multilinear map over the integers presented by Coron, Lepoint and Tibouchi at CRYPTO 2015 (CLT15). This version is a fix of the first multilinear map over the integers presented by the same authors at CRYPTO 2013 (CLT13) and broken by Cheon et al. at EUROCRYPT 2015. The attack essentially downgrades CLT15 to its original version CLT13, and leads to a full break of the multilinear map for virtually all applications. A more complete version of the paper will be made available in the coming weeks. Nevertheless the main attack is given in full details.

We study ballot secrecy and ballot independence for election schemes. First, we propose a definition of ballot secrecy as an indistinguishability game in the computational model of cryptography. Our definition builds upon and strengthens earlier definitions to ensure that ballot secrecy is preserved in the presence of an adversary that controls the bulletin board and communication channel. Secondly, we propose a definition of ballot independence as a straightforward adaptation of a non-malleability definition for asymmetric encryption. We also provide a simpler, equivalent definition as an indistinguishability game. Thirdly, we prove that ballot independence is necessary in election schemes satisfying ballot secrecy. Finally, we demonstrate the applicability of our results by analysing Helios. Our analysis identifies a new attack against Helios, which enables an adversary to determine if a voter did not vote for the adversary\'s chosen candidate. The attack requires the adversary to control the bulletin board or communication channel, thus, it could not have been detected by earlier definitions of ballot secrecy.

This paper sets speed records on well-known Intel chips for the Curve25519 elliptic-curve Diffie-Hellman scheme and the Ed25519 digital signature scheme. In particular, it takesonly 159 128 Sandy Bridge cycles or 156 995 Ivy Bridge cycles to compute a Diffie-Hellman shared secret, while the previous records are 194 036 Sandy Bridge cycles or 182 708 Ivy Bridge cycles.

There have been many papers analyzing elliptic-curve speeds on Intel chips, and they all use Intel\'s serial 64 x 64 -> 128-bit multiplier for field arithmetic. These papers have ignored the 2-way vectorized 32 x 32 -> 64-bit multiplier on Sandy Bridge and Ivy Bridge: it seems obvious that the serial multiplier is faster. However, this paper uses the vectorized multiplier. This is the first speed record set for elliptic-curve cryptography using a vectorized multiplier on Sandy Bridge and Ivy Bridge. Our work suggests that the vectorized multiplier might be a better choice for elliptic-curve computation, or even other types of computation that involve prime-field arithmetic, even in the case where the computation does not exhibit very nice internal parallelism.

The selection of polynomials to represent number fields crucially determines the efficiency of the Number Field Sieve (NFS) algorithm for solving the discrete log problem in a finite field. An important recent work due to Barbulescu et al builds upon existing works to propose two new methods for polynomial selection when the target field has a composite order. These methods are called the generalised Joux-Lercier (GJL) and the Conjugation methods. In this work, we propose a new method for polynomial selection for the NFS algorithm in fields $\\mathbb{F}_{p^n}$, with $n>1$. The new method both subsumes and generalises the GJL and the Conjugation methods. Asymptotic analysis for the new polynomial selection method is performed for both the classical NFS and the multiple NFS (MNFS) algorithms. For medium and large prime characteristic, the new method does not provide any new asymptotic result. For the boundary case, the complexity of the new method interpolates between that of the Conjugation and the GJL methods for both classical and multiple NFS algorithms. In particular, for $p=L_Q(2/3,c_p)$, as $c_p$ grows the complexity of the new method is lower than that of the GJL method and hence becomes the new state of the art.

Policies are the corner stones of today\'s computer systems. They define secure states and safe operations. A common problem with policies is that their enforcement is often in conflict with user privacy. In order to check the satisfiability of a policy, a server usually needs to collect from a client some information which may be private. In this work we introduce the notion of secure set-based policy checking (SPC) that allows the server to verify policies while preserving the client\'s privacy. SPC is a generic protocol that can be applied in many policy-based systems. As an example, we show how to use SPC to build a password registration protocol so that a server can check whether a client\'s password is compliant with its password policy without seeing the password. We also analyse SPC and the password registration protocol and provide security proofs. To demonstrate the practicality of the proposed primitives, we report performance evaluation results based on a prototype implementation of the password registration protocol.

The proof-of-work is a central concept in modern cryptocurrencies, but the requirement for fast verification so

far made it an easy prey for GPU-, ASIC-, and botnet-equipped users. The attempts to rely on

memory-intensive computations in order to remedy the disparity between architectures have

resulted in slow or broken schemes.

In this paper we solve this open problem and show how to construct an \\emph{asymmetric} proof-of-work (PoW) based on a computationally hard problem, which requires a lot of memory to generate a proof (called \"memory-hardness\" feature) but is instant to verify. Our primary proposal is a PoW based on the

generalized birthday problem and enhanced Wagner\'s algorithm for it. We introduce the new technique of \\emph{algorithm binding} to prevent cost amortization and demonstrate that possible parallel implementations are constrained by memory bandwidth. Our scheme has tunable and steep time-space tradeoffs, which impose large computational penalties if less memory is used.

Our solution is practical and ready to deploy: a reference implementation of a proof-of-work requiring 700 MB of RAM runs in 30 seconds on a 1.8 GHz CPU,

increases the computations by the factor of 1000 if memory is halved, and presents a proof of just 148 bytes long.

Thispaperaddressesthesecureoutsourcingproblemforlarge-scalematrixcomputationto a public cloud. We propose a novel public-key weave ElGamal encryption (WEE) scheme for encrypting a matrix over the field Zp. The scheme has the echelon transformation property. We can apply a series of elementary row/column operations to transform an encrypted matrix under our WEE scheme into the row/column echelon form. The decrypted result matches the result of the corresponding operations performed on the original matrix. For security, our WEE scheme is shown to be entry irrecoverable for non-zero entries under the computational Diffie-Hellman assumption.

By using our WEE scheme, we propose five secure outsourcing protocols of Gaussian elimination, Gaussian-Jordan elimination, matrix determinant, linear system solver, and matrix inversion. Each of these protocols preserves data privacy for clients (data owners). Furthermore, the linear system solver and matrix inversion protocols provide a cheating-resistant mechanism to verify correctness of computation results. Our experimental result shows that our protocols gain efficiency significantly for an outsourcer. Our outsourcing protocol solves a linear system of n = 1, 000 equations and m = 1, 000 unknown variables about 472 times faster than a non-outsourced version. The efficiency gain is more substantial when (n, m) gets larger. For example, when n = 10, 000 and m = 10, 000, the protocol can solve it about 56, 274 times faster. Our protocols can also be easily implemented in parallel computation architecture to get more efficiency improvement.

Signatures with partially message recovery

in which some parts of messages are not transmitted

with signatures to make them shorter are useful where

bandwidth is one of the crucial concern and especially

in case of signing short messages in applications such

as time stamping, certified email services and identitybased

cryptosystems. In this paper, to have quantum-attackresistant

short signatures, a signature scheme with partially

message recovery from coding theory is proposed. The

security of the proposed scheme is proved under Goppa

Parametrized Bounded Decoding and the Goppa Code

Distinguishing assumptions in the random oracle model.

Relying on the partially message recovery property, the

proposal is shorter than the Dallot signature scheme, the

only provably secure and practical code-based signature

scheme. We should highlight that our scheme can be used

as a building block of code-based signature schemes with

additional properties since it compared to Dallot signature

scheme not only improves its communication overhead but

also it preserves its signature efficiency.

The power of a statistical attack is inversely proportional to the number of plaintexts

necessary to recover information on the encryption key. By

analyzing the distribution of the random variables involved in the attack,

cryptographers aim to provide a good estimate of the data

complexity of such an attack. In this paper, we analyze the

hypotheses made in simple, multiple, and multidimensional

linear attacks that use either non-zero or zero correlations, and provide more accurate estimates of the data complexity of

these attacks. This is achieved by taking, for the first time, into consideration the key variance of the statistic for both

the right and wrong keys.

For the family of linear attacks we differentiate between the attacks which are performed in the known-plaintext

and those in the distinct-known-plaintext model. By this differentiation, we improve the

data complexity of some attacks by applying the distinct-known-plaintext model.

From the analysis provided in this paper, it follows that

the number of attacked

rounds in the multidimensional linear context is impacted by the fact that the expected capacity of a multidimensional linear

approximation for a random permutation is not equal to

zero as previously assumed. The impact of the result is relatively important, since it weakens most existing multidimensional linear attacks.

From the link between

differential and linear cryptanalysis we also derive a new estimate of the

data complexity of a truncated differential attack. The theory developed

in this paper is backed up by different experiments.

Radio Frequency Identification (RFID) is a modern communication technology, which provides authentication and identification through a nonphysical contact. Recently, the use of this technology is almost developed in healthcare environments. Although RFID technology can prepare sagacity in systems, privacy and security issues ought to be considered before. Recently, in 2015, Li et al. proposed a hash-based RFID authentication protocol in medication verification for healthcare. In this paper, we study this protocol and show that Li et al.\'s protocol is vulnerable to traceability, impersonation and DoS attacks. So it does not provide the privacy and security of RFID end-users. Therefore, we propose an improved secure and efficient RFID authentication protocol to enhance the performance of Li et al.\'s method. Our analyze show that the existing weaknesses of Li et al.\'s protocol are eliminated in our proposed protocol.

We demonstrate a prototype implementation of a provably secure protocol that supports privacy-preserving mutual authentication between a server and a constrained device. Our proposed protocol is based on a physically unclonable function (PUF) and it is optimized for resource-constrained platforms. The reported results include a full protocol analysis, the design of its building blocks, their integration into a constrained device, and finally its performance evaluation. We show how to obtain efficient implementations for each of the building blocks of the protocol, including a fuzzy extractor with a novel helper-data construction technique, a truly random number generator (TRNG), and a pseudo-random function (PRF). The prototype is implemented on a SASEBO-GII board, using the on-board SRAM as the source of entropy for the PUF and the TRNG. We present three different implementations. The first two execute on a MSP430 soft-core processor and have a security level of 64-bit and 128-bit respectively. The third uses a hardware accelerator and has 128-bit security level. To our best knowledge, this work is the first effort to describe the end-to-end design and evaluation of a privacy-preserving PUF-based authentication protocol.