International Association
for Cryptologic Research

To gain strong confidence in the security of a public-key scheme, it

is most desirable for the security proof to feature a \\emph{tight}

reduction between the adversary and the algorithm solving the

underlying hard problem. Recently, Chen and Wee (Crypto\\,\'13) described the first Identity-Based Encryption scheme with almost

tight security under a standard assumption. Here, ``almost tight\'\'

means that the security reduction only loses a factor $O(\\lambda)$

-- where $\\lambda$ is the security parameter -- instead of a factor

proportional to the number of adversarial queries. Chen and Wee

also gave the shortest signatures whose security almost tightly

relates to a simple assumption in the standard model. Also recently,

Hofheinz and Jager (Crypto\\,\'12) constructed the first CCA-secure

public-key encryption scheme in the multi-user setting with tight

security. These constructions give schemes that are significantly

less efficient in length (and thus, processing) when compared with

the earlier schemes with loose reductions in their proof of

security. Hofheinz and Jager\'s scheme has a ciphertext of a few

hundreds of group elements, and they left open the problem of

finding truly efficient constructions. Likewise, Chen and Wee\'s

signatures and IBE schemes are somewhat less efficient than previous

constructions with loose reductions from the same assumptions. In

this paper, we consider space-efficient schemes with security almost

tightly related to standard assumptions. As a step in solving the

open question by Hofheinz and Jager, we construct an efficient

CCA-secure public-key encryption scheme whose chosen-ciphertext

security in the multi-challenge, multi-user setting almost tightly

relates to the DLIN assumption (in the standard model). Quite

remarkably, the ciphertext size decreases to $69$ group elements

under the DLIN assumption whereas the best previous solution required about $400$ group elements. Our scheme is obtained by taking advantage of a new almost tightly secure signature scheme (in the standard model) we develop here and which is based on the recent concise proofs of linear subspace membership in the quasi-adaptive

non-interactive zero-knowledge setting (QA-NIZK) defined by Jutla

and Roy (Asiacrypt\\,\'13). Our signature scheme reduces the length of the previous such signatures (by Chen and Wee) by $37\\%$ under the Decision Linear assumption, by almost $50\\%$ under the $K$-LIN assumption, and it becomes only $3$ group elements long under the Symmetric eXternal Diffie-Hellman assumption. Our signatures are obtained by carefully combining the proof technique of Chen and Wee and the above mentioned QA-NIZK proofs.

By replacing the brute-force list search in sieving algorithms with angular locality-sensitive hashing, we get both theoretical and practical speed-ups for finding shortest vectors in lattices. Optimizing for time, we obtain a heuristic time and space complexity for solving SVP of 2^(0.3366n). Preliminary experiments show that the proposed HashSieve algorithm already outperforms the GaussSieve in low dimensions, and that the practical increase in the space complexity is much smaller than the asymptotic bounds suggest. Using probing we show how we can further reduce the space complexity at the cost of slightly increasing the time complexity.

We introduce the concept of universal signature aggregators. In a universal signature aggregator system, a third party, using a set of common reference parameters, can aggregate a collection of signatures produced from any set of signing algorithms (subject to a chosen length constraint) into one short signature whose length is independent of the number of signatures aggregated. In prior aggregation works, signatures can only be aggregated if all signers use the same signing algorithm (e.g., BLS) and shared parameters. A universal aggregator can aggregate across schemes even in various algebraic settings (e.g., BLS, RSA, ECDSA), thus creating novel opportunities for compressing authentication overhead. It is especially compelling that existing public key infrastructures can be used and that the signers do not have to alter their behavior to enable aggregation of their signatures.

We provide multiple constructions and proofs of universal signature aggregators based on indistinguishability obfuscation and other supporting primitives. We detail our techniques as well as the tradeoffs in features and security of our solutions.

In this survey, we discuss an emerging concept of decoy-based information security, or security without computational assumptions.

In particular, we show how this concept can be implemented to

provide security against (passive) computationally unbounded adversary in some public-key encryption protocols. In the world of symmetric cryptography, decoy-based security finds a wide range of applications, notably to secure delegation of computation to another party. We single out the scenario where a computationally limited party wants to send an encrypted message to a computationally superior party using the RSA protocol, thereby providing another kind of application of decoy ideas in a public-key setting. With typical RSA parameters, decoy-based method of delegation of computation improves the efficiency for the sender by several orders of magnitude.

In this paper, we investigate the Mixed-integer Linear Programming (MILP) modelling of the differential and linear behavior of a wide rang of block ciphers.

The differential and linear behavior of the transformations involved in a block cipher can be described by a set $P \\subseteq \\{0,1\\}^n \\subseteq \\mathbb{R}^n$.

We show that $P$ is exactly the set of all 0-1 solutions of the H-representation of the convex hull of $P$. In addition, we can find a small number of inequalities in the H-representation of the convex hull of $P$ such that the set of all 0-1 solutions of these inequalities equals $P$.

~~~~~~Based on these discoveries and MILP technique, we propose an automatic method for finding high probability (related-key) differential or linear characteristics of block ciphers. Compared with Sun {\\it et al.}\'s {\\it heuristic} method presented in Asiacrypt 2014, the new method is {\\it exact} for most ciphers in the sense that every feasible 0-1 solution of the MILP model generated by the new method corresponds to a valid characteristic, and therefore there is no need to repeatedly add valid cutting-off inequalities into the MILP model as is done in Sun {\\it et al.}\'s method; the new method is more powerful which allows us to get the {\\it exact lower bounds} of the number of differentially or linearly active S-boxes; and the new method is more efficient which is able to obtain characteristic enjoying higher probability or covering more rounds of a cipher with less computational effort.

~~~~~Moreover, by employing a type of specially constructed linear inequalities which can remove {\\it exactly one} feasible 0-1 solution from the feasible region of an MILP problem, we propose a method for automatic enumeration of {\\it all} (related-key) differential or linear characteristics with some predefined properties, {\\it e.g.}, characteristics with given input or/and output difference/mask, or with limited number of active S-boxes. Such a method is very useful in the

automatic (related-key) differential analysis, truncated (related-key) differential analysis, linear hull analysis, and the automatic construction of (related-key) boomerang/rectangle distinguishers.

~~~~~~The methods presented in this paper are implemented and extensive experiments are performed. To demonstrate the usefulness of these methods, we apply them to SIMON, PRESENT, Serpent, LBlock, DESL, and we obtain improved cryptanalytic results. For example, we find single-key differentials covering 16 and 22 rounds of SIMON48 and SIMON64 (block ciphers designed by the U.S. National Security Agency) respectively. These are the longest differentials for SIMON48 and SIMON64 published so far.

Being required in many applications, modular exponentiations form the most expensive part of modern cryptographic primitives. It is a significant challenge for resource-constrained mobile devices to perform these heavy computations (e.g., mobile devices that require secure cryptographic computations or RFID tags). Cloud services can significantly enhance the computational capability of these devices. In this way, expensive computations at client side can significantly be reduced by means of secure outsourcing modular exponentiations to a potentially untrusted server S. In this paper, we study this problem which is an active research area of mobile and cloud computing, and mostly known as secure outsourced computation. We propose new efficient outsourcing algorithms for modular exponentiations using only one untrusted cloud service provider solving an open problem highlighted in [11]. These algorithms cover each possible case ranging from public-base & private-exponent, private-base & public-exponent, private-base & private-exponent to the most general private-basis & private-exponents simultaneous modular exponentiations. Our algorithms are the most efficient outsourced computation algorithms to date which use single untrusted server and have the best checkability (verifiability) property. Finally, we give two different real-life applications for outsourcing within the realm of Oblivious Transfer protocols and Blind Signatures.

Physical Unclonable Functions (PUFs) are specialized circuits with applications including key generation and challenge-response authentication. PUF properties such as low cost and resistance to invasive attacks make PUFs well-suited to embedded devices. Yet, given how infrequently the specialized capabilities of a PUF may be needed, the silicon area dedicated to it is largely idle. This inefficient resource usage is at odds with the cost minimization objective of embedded devices. Motivated by this inefficiency, we propose the Bitline PUF -- a novel PUF that uses modified wordline drivers together with SRAM circuitry to enable challenge-response authentication. The number of challenges that can be applied to the Bitline PUF grows exponentially with the number of SRAM rows, and these challenges can be applied at any time without power cycling. This paper presents in detail the workings of the Bitline PUF, and shows that it achieves high throughput, low latency, and uniqueness across instances. Circuit simulations indicate that the Bitline PUF responses have a nominal bit-error-rate (BER) of 0.023 at 1.2 V supply and 27C, and that BER does not exceed 0.076 when supply voltage is varied from 1.1 V to 1.3 V, or when temperature is varied from 0C to 80C. Because the Bitline PUF leverages existing SRAM circuitry, its area overhead is only a single flip-flop and two logic gates per row of SRAM. The combination of high performance and low cost makes the Bitline PUF a promising candidate for commercial adoption and future research.

Submission: 22 November 2015
Notification: 15 January 2015
From June 30 to July 2
Location: Philadelphia, USA
More Information: https://www.petsymposium.org/2015/

Submission: 20 October 2014
From December 16 to December 17
Location: Beijing, China
More Information: http://crypto.fudan.edu.cn/intrust2014/

LED and PHOTON are new ultra-lightweight cryptographic algorithms aiming at resource-constrained devices. In this article, we describe three different hardware architectures of the LED and PHOTON family optimized for Field-Programmable Gate Array (FPGA) devices. In the first architecture we propose a round-based implementation while the second is a fully serialized architecture performing operations on a single cell per clock cycle. Then, we propose a novel architecture that is designed with a focus on utilizing commonly available building blocks (SRL16). This new architecture, organized in a complex scheduling of the operations, seems very well suited for recent designs that use serial matrices. We implemented both the lightweight block cipher LED and the lightweight hash function PHOTON on the Xilinx FPGA series Spartan-3 (low-cost) and Artix-7 (high-end) devices and our new proposed architecture provides very competitive area-throughput trade-offs. In comparison with other recent lightweight block ciphers, the implementation results of LED show a significant improvement of hardware efficiency and we obtain the smallest known FPGA implementation (as of today) of any hash function.

In this paper we define a trapdoor function called SBIM(Q) by using multivariate polynomials over the field of rational numbers $\\mathbb Q.$ The public key consists of $2n$ multivariate polynomials with $3n$ variables $y_1,\\dots,y_n,$ $z_1,\\dots,z_{2n}$. The $y_i$ variables take care for the information content, while the $z_i$ variables are for redundant information. Thus, for encryption of a plaintext of $n$ rational

numbers, a ciphertext of $2n$ rational numbers is used. The security is based on the fact that there are infinitely many solutions of a system with $2n$ polynomial equations of $3n$ unknowns.

The public key is designed by quasigroup transformations obtained from quasigroups presented in matrix form. The quasigroups presented in matrix form allow numerical as well as symbolic computations, and here we exploit that possibility. The private key consists of several $1\\times n$ and $n\\times n$ matrices over $\\mathbb Q$, and one $2n\\times 2n$ matrix.

Search of rich Boolean function for designing a good cryptosystem

is most important. In this search from the infinite domain of integers,cases where rejection of integers for the existence of Generalized bent

function is very helpful. With the help of some necessary condition

of GBF here we show the non existence of [n,5] type Generalized Bent

functions.

From May 31 to June 5
Location: Sibenik, Croatia
More Information: http://summerschool-croatia15.cs.ru.nl/

In this paper, we propose an efficient and provably secure certificateless public key cryptography (CL-PKC) based authenticated group key agreement (CL-AGKA) protocol that meets practicability, simplicity, and strong notions of security. Our protocol focuses on certificateless public key cryptography (CL-PKC) which simplifies the complex certificate management in the traditional public key cryptography (PKC) and resolves the key escrow problem in identity-based cryptography (IBC). The authenticated group key exchange (AGKA) protocols allow participants to communicate over a public network to exchange a shared secret key. The CL-AGKA protocol is designed to established a group key between group of participants by ensuring that no other outsiders can learn any information about the agreed session key. Our CL-AGKA protocol presents a security notion in random oracle model. It is formally proven that our CL-AGKA protocol provides strong Authenticated Key Exchange (AKE) security. Thus, the proposed protocol provides provable security along with low message exchange cost and computational cost to form the shared group key.

Present-day public-key cryptosystems such as RSA and Elliptic Curve Cryptography (ECC) will become insecure when quantum computers become a reality. This paper presents the new state of the art in efficient software implementations of a post-quantum secure public-key encryption scheme based on the ring-LWE problem. We use a 32-bit ARM Cortex-M4F microcontroller as the target platform. Our contribution includes optimization techniques for fast discrete Gaussian sampling and efficient polynomial multiplication. This implementation beats all known software implementations, on any architecture, by at least one order of magnitude. We further show that our scheme beats all ECC-based public-key encryption schemes by at least one order of magnitude. At 128-bit security we require 121166 cycles per encryption and 43324 cycles per decryption, while at a 256-bit security we require 261939 cycles per encryption and 96520 cycles per decryption. Gaussian sampling is done at an average of 28.5 cycles per sample.

Security is one of the most important features of industrial products. Cryptographic algorithms are mainly used for this purpose to obtain confidentiality and integrity of data in industry. One of the main concerns of researchers in designing cryptographic algorithms is efficiency in either software implementation or hardware implementation. However, the efficiency of some well-known algorithms is highly questionable. The main goal of this paper is to present a novel processor architecture called CIARP (stands for Crypto Instruction-Aware RISC Processor) being feasible for high speed implementation of low throughput cryptographic algorithms. CIARP has been designed based on a proposed instruction set named Crypto Specific Instruction Set (CSIS), that can speed up encryption and decryption processes of data.

We give a detailed account of the use of \\(\\mathbb{Q}\\)-curve reductions to construct elliptic curves over \\(\\mathbb{F}_{p^2}\\) with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant--Lambert--Vanstone (GLV) and Galbraith--Lin--Scott (GLS) endomorphisms.

Like GLS (which is a degenerate case of our construction), we offer the advantage over GLV of selecting from a much wider range of curves, and thus finding secure group orders when \\(p\\) is fixed for efficient implementation.

Unlike GLS, we also offer the possibility of constructing twist-secure curves.

We construct several one-parameter families of elliptic curves over \\(\\mathbb{F}_{p^2}\\) equipped with efficient endomorphisms for every \\(p > 3\\), and exhibit examples of twist-secure curves over \\(\\mathbb{F}_{p^2}\\) for the efficient Mersenne prime \\(p = 2^{127}-1\\).

The Protocol for Lightweight Authentication of Identity (PLAID) aims at secure and private authentication between a smart card and a terminal. Originally developed by a unit of the Australian Department of Human Services for physical and logical access control, PLAID has now been standardized as an Australian standard AS-5185-2010 and is currently in the fast track standardization process for ISO/IEC 25182-1.2. We present a cryptographic evaluation of PLAID. As well as reporting a number of undesirable cryptographic features of the protocol, we show that the privacy properties of PLAID are significantly weaker than claimed: using a variety of techniques we can fingerprint and then later identify cards. These techniques involve a novel application of standard statistical and data analysis techniques in cryptography. We also discuss countermeasures to our attacks.

This paper shows how to securely authenticate messages using just 29 bit operations per authenticated bit, plus a constant overhead per message. The authenticator is a standard type of \"universal\" hash function providing information-theoretic security; what is new is computing this type of hash function at very high speed.

At a lower level, this paper shows how to multiply two elements of a field of size 2^128 using just 9062 \\approx 71 * 128 bit operations, and how to multiply two elements of a field of size 2^256 using just 22164 \\approx 87 * 256 bit operations. This performance relies on a new representation of field elements and new FFT-based multiplication techniques.

This paper\'s constant-time software uses just 1.89 Core 2 cycles per byte to authenticate very long messages. On a Sandy Bridge it takes 1.43 cycles per byte, without using Intel\'s PCLMULQDQ polynomial-multiplication hardware. This is much faster than the speed records for constant-time implementations of GHASH without PCLMULQDQ (over 10 cycles/byte), even faster than Intel\'s best Sandy Bridge implementation of GHASH with PCLMULQDQ (1.79 cycles/byte), and almost as fast as state-of-the-art 128-bit prime-field MACs using Intel\'s integer-multiplication hardware (around 1 cycle/byte).

The focus of this paper is on differential privacy of streaming data using sketch-based algorithms. Previous works, like Dwork {\\it et al.} (ICS 2010, STOC 2010), explored random sampling based streaming algorithms. We work in the well studied streaming model of computation, where the database is stored in the form of a matrix and a curator can access the database row-wise or column-wise.

Dwork {\\it et al.} (STOC 2010) gave impossibility result for any non-trivial query on a streamed data with respect to the user level privacy. Therefore, in this paper, we restrict our attention to the event level privacy. {We provide optimal, up to logarithmic factor, space differentially private mechanism in the streaming model for three basic linear algebraic tasks: matrix multiplication, linear regression, and low rank approximation, while incurring significantly less additive error}.

Our approach for matrix multiplication and linear regression has some similarities with Blocki {\\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 2013) on the superficial level, but there are some subtle differences. For example, they perform an affine transformation to convert the private matrix in to a set of $\\{\\sqrt{w/n},1\\}^n$ vectors for some appropriate $w$, while we perform an input perturbation that raises the singular value of the private matrix. %On a high level, the mechanism for linear regression and matrix multiplication can be seen as a private analogue of the known streaming algorithms. In order to get a streaming algorithm for low rank approximation, we have to reuse the random Gaussian matrix in a specific way. We prove that the resulting distribution also preserve differential privacy.

We do not make any assumptions, like singular value separation, as made in the earlier works of Hardt and Roth (STOC 2013) and Kapralov and Talwar (SODA 2013). Further, we do not assume normalized row as in the work of Dwork {\\it et al.} (STOC 2014). All our mechanisms, in the form presented, can also be computed in the distributed setting of Biemel, Nissim, and Omri (CRYPTO 2008).