International Association
for Cryptologic Research

In this paper, we propose the first provable secure certificate-based proxy signature with message recovery without bilinear pairing. The notion of certificate-based cryptography was initially introduced by Gentry in 2003, in order to simplify certificate management in traditional public key cryptography(PKC)and to solve the key escrow problem in identity-based cryptosystems. To date, a number of certificate-based proxy signature(CBPS)schemes from bilinear pairing have been proposed. Nonetheless, the total computation cost of a pairing is higher than that of scalar multiplication(e.g., over elliptic curve group). Consequently, schemes without pairings would be

more appealing in terms of efficiency. According to the available research in this regard, our scheme is the first provable secure CBPS scheme with message recovery which is based on the elliptic curve discrete logarithm problem. We prove the security of the presented scheme against existential forgery under adaptive chosen message and ID attacks in the random oracle model. Moreover, the paper will also show how it would be possible to convert this scheme to the CBPS scheme without message recovery. This scheme has more applications in situations with limited bandwidth and power-constrained devices.

The Keccak hash function is a chosen of the SHA-3 competition. This function has the appropriate structural and so far it has been resistant against collision attacks. In the last few years after efforts cryptonalysis, first, the collision in the second round and near collision in the third rounds, was found. and after adi Shamir and Et al succeeded find collision in fourth round and near collision in 5 round for keccak 224,256. In this paper we propose a method that it can used, for any desired text and finds, near collision, in the second round, regardless of any probability. Our attack technique using the find the text that have the same parity such original text in theta function. It is practical for all keccak varies and it finds near collision for second round in few minute. We have named this method \" Parity Analyse\".

Asymptotical complexity of sparse equation systems over finite field $F_q$ is studied.

Let the variable sets belong to a fixed family $\\mathcal{X}=\\{X_1,\\ldots,X_m\\}$ while

the polynomials $f_i(X_i)$ are taken independently and uniformly at random from the set of all polynomials

of degree $\\leq q-1$ in each of the

variables in $X_i$. In particular, for $|X_i|\\le3$, $m=n$, we prove

the average complexity of finding all solutions to $f_i(X_i)=0, i=1,\\ldots,m$ by Gluing algorithm ( Semaev, Des. Codes Cryptogr., vol. 49 (2008), pp.47--60) is at most $

q^{\\frac{n}{5.7883}+O(\\log n)}$ for arbitrary $\\mathcal{X}$ and $q$. The proof results from a detailed analysis of 3-MaxMinMax problem, a novel problem for hyper-graphs.

This paper studies how to construct a pseudorandom generator using hard lattice problems.

We use a variation of the classical hard problem \\emph{Inhomogeneous Small Integer Solution} ISIS of lattice, say \\emph{Inhomogeneous Subset Sum Solution} ISSS. ISSS itself is a hash function. Proving the preimage sizes ISSS hash function images are almost the same, we construct a pseudorandom generator using the method in \\cite{GKL93}. Also, we construct a pseudoentropy generator using the method in \\cite{HILL99}. Most theoretical PRG constructions are not feasible in fact as they require rather long random bits as seeds. Our PRG construction only requires seed length to be $O(n^{2}\\log_{2} n)$ which is feasible practically.

We present explicit formulae and complexities of bit-parallel $GF(2^{n})$ squarers for a new class of irreducible pentanomials

$x^{n}+x^{n-1}+x^{k}+x+1$, where $n$ is odd and $1

Submission: 8 January 2014
Notification: 28 February 2014
From June 9 to June 13
Location: �le de Porquerolles, France
More Information: http://yacc.univ-tln.fr/

Recently, Shm et al. Proposed an efficient identity-based broadcast authentication scheme based on Tso et al.\'s IBS scheme with message recovery to achieve security requirements in wireless sensor networks. They claim that their scheme can achieve security requirements and mitigated DOS attack by limiting the times of signature verification failures in wireless sensor networks (WSN). However, we found that the scheme cannot attain the security level as they claimed. We will demonstrate it in this article.

A revocation mechanism in cryptosystems for a large number of users is absolutely necessary to maintain the security of whole systems. A revocable identity-based encryption (RIBE) provides an efficient revocation method in IBE that a trusted authority periodically broadcasts an update key for non-revoked users and a user can decrypt a ciphertext if he is not revoked in the update key. Boldyreva, Goyal, and Kumar (CCS 2008) defined RIBE and proposed an RIBE scheme that uses a tree-based revocation encryption scheme to revoke users. However, this approach has an inherent limitation that the number of private key elements and update key elements cannot be constant. In this paper, to overcome the previous limitation, we devise a new technique for RIBE and propose RIBE schemes with a constant number of private key elements. We achieve the following results:

- We first devise a new technique for RIBE that combines hierarchical IBE (HIBE) scheme and a public-key broadcast encryption (PKBE) scheme by using multilinear maps. In contrast to the previous technique for RIBE, our technique uses a PKBE scheme in bilinear maps for revocation to achieve short private keys and update keys.

- Following our new technique for RIBE, we propose an RIBE scheme in 3-leveled multilinear maps that combines the HIBE scheme of Boneh and Boyen and the PKBE scheme of Boneh, Gentry, and Waters. The private key and update key of our scheme have a constant number of group elements. To prove the security of our scheme, we introduce a new complexity assumption in multilinear maps, and prove its security in the selective revocation list model.

- Next, we propose another RIBE scheme that reduces the number of public parameters by using the parallel construction technique of PKBE. We could reduce the number of public parameters by using the fact that only the trusted authority in RIBE can broadcast an update key.

Bitcoin is a potentially disruptive new crypto-currency based on a decentralized open-source protocol which is gradually gaining popularity. Perhaps the most important question that will affect Bitcoin\'s success, is whether or not it will be able to scale to support the high volume of transactions required from a global currency system.

We investigate the restrictions on the rate of transaction processing in Bitcoin as a function of both the bandwidth available to nodes and the network delay, both of which lower the efficiency of Bitcoin\'s transaction processing.

The security analysis done by Bitcoin\'s creator Satoshi Nakamoto~\\cite{nakamoto2008bitcoin} assumes that block propagation delays are negligible compared to the time between blocks---an assumption that does not hold when the protocol is required to process transactions at high rates. We improve upon the original analysis and remove this assumption.

Using our results, we are able to give bounds on the number of transactions per second the protocol can handle securely. Building on previously published measurements by Decker and Wattenhofer~\\cite{Decker2013Information}, we show these bounds are currently more restrictive by an order of magnitude than the bandwidth needed to stream all transactions. We additionally show how currently planned improvements to the protocol, namely the use of transaction hashes in blocks (instead of complete transaction records), will dramatically alleviate these restrictions.

Finally, we present an easily implementable modification to the way Bitcoin constructs its main data structure, the blockchain, that immensely improves security from attackers, especially when the network operates at high rates. This improvement allows for further increases in the number of transactions processed per second. We show that with our proposed modification, significant speedups can be gained in confirmation time of transactions as well. The block generation rate can be securely increased to more than one block per second -- a 600 fold speedup compared to today\'s rate, while still allowing the network to processes many transactions per second.

Modular multiplication of large integers is a performance-critical arithmetic operation of many public-key cryptosystems such as RSA, DSA, Diffie-Hellman (DH) and their elliptic curve-based variants ECDSA and ECDH. The computational cost of modular multiplication and related operations (e.g. exponentiation) poses a practical challenge to the widespread deployment of public-key cryptography, especially on embedded devices equipped with 8-bit processors (smart cards, wireless sensor nodes, etc.). In this paper, we describe basic software techniques to improve the performance of Montgomery modular multiplication on 8-bit AVR-based microcontrollers. First, we present a new variant of the widely-used hybrid method for multiple precision multiplication that is 10.6% faster than the original hybrid technique of Gura et al. Then, we discuss different hybrid Montgomery multiplication algorithms, including Hybrid Finely Integrated Product Scanning (HFIPS), and introduce a novel approach for Montgomery multiplication, which we call Hybrid Separated Product Scanning (HSPS). Finally, we show how to perform the modular subtraction of Montgomery reduction in a regular fashion without execution of conditional statements so as to counteract Simple Power Analysis (SPA) attacks. Our AVR implementation of the HFIPS and HSPS method outperforms the Montgomery multiplication of the MIRACL Crypto SDK by 21.6% and 14.3%, respectively, and is twice as fast as the modular multiplication of the TinyECC library.

The Department of Electrical and Electronic Engineering at Ariel University (Israel) invites applications for a tenure-track Lecturer or Senior Lecturer (Assistant Professor) position to begin in 2014.

The position is full-time, tenure-track, with eligible benefits. The candidate will teach undergraduate and graduate courses in the computer engineering track, including required courses such as Introduction to programming in C, Introduction to microprocessors, and elective courses such as Computer networking laboratory and Assembly language.

The candidate\\\'s areas of research should be in one of the following areas:

Coding, cryptography, information protection, cyber security

Computer network design and analysis

Computer architecture and parallel distributed processing

Data storage

Compilers and operating systems

Wireless sensor networks

Cloud computing

Quantum computers

Multivariate public key cryptography which relies on MQ (Multivariate Quadratic) problems is one of the main approaches to guarantee the security of communication in the post-quantum world. In this paper, we propose a combined MQ signature scheme based on the yet unbroken UOV (Unbalanced Oil and Vinegar) signature if parameters are properly chosen. Our scheme can not only reduce the public key size of the UOV signature, but also provide more tighter bound of security against chosen-message attack in the random oracle model. On the other hand, we propose a proxy signature scheme based on our proposed combined signature scheme. Additionally, we give a strict security proof for our proxy signature scheme. Finally, we present experiments for all of our proposed schemes and the baseline schemes. Comparisons with related schemes show that our work has some advantages on performance along

with more strict security.

PMI+ is a Multivariate Quadratic (MQ) public key algorithm used for encryption and decryption operations, and belongs to post quantum cryptography.We designs a hardware on FPGAs to efficiently implement PMI+ in this paper.Our main contributions are that,firstly, a hardware architecture of encryption and decryption of PMI+ is developed, and description of corresponding hardware algorithm is proposed;secondly, basic arithmetic units are implemented with higher efficiency that multiplication, squaring, vector dot product and power operation are implemented in full parallel;and thirdly, an optimized implementation for core module, including optimized large power operation, is achieved. The encryption and decryption hardware of PMI+ is efficiently realized on FPGA by the above optimization and improvement.It is verified by experiments that the designed hardware can complete an encryption operation within 497 clock cycles, and the clock frequency can be up to 145.6MHz,and the designed hardware can complete a decryption operation within 438 clock cycles wherein the clock frequency can be up to 37.04MHz.

We design and build a system that enables clients to verify the outputs of programs executed by untrusted servers. A server provides a succinct non-interactive zero-knowledge proof (also known as a zk-SNARK), which the client verifies to ascertain correct execution.

The system has two components: a cryptographic proof system for verifying satisfiability of arithmetic circuits, and a circuit generator to translate program executions to such circuits. Our design of both components improves in functionality and efficiency over previous work, as follows.

Our circuit generator is the first to be universal: it does not need to know the program, but only a bound on its running time. It is also the first to support programs expressed as code for a von Neumann RISC random-access memory architecture, where programs may use just-in-time compilation and self-modifying code. Moreover, the dependence on program size is additive (instead of multiplicative as in prior works), allowing efficient verification of large programs.

The cryptographic proof system significantly improves proving and verification times, using a new pairing-based cryptographic library tailored to the protocol.

We evaluated our system for programs with up to 10,000 instructions, running for up to 32,000 machine steps, each of which can arbitrarily access random-access memory; and demonstrated it executing programs that use just-in-time compilation. Our proofs are 230 bytes long at 80 bits of security, or 288 bytes long at 128 bits of security. Typical verification time is 5 ms, regardless of the original program\'s running time.

We consider the problem of outsourced computation that operates on encrypted inputs supplied by multiple independent parties. To facilitate fine-grained access control, it would be desirable if each party could encrypt her input under an appropriate access policy. Moreover, a party should only be authorized to decrypt the result of a computation performed on a set of encrypted inputs if his credentials satisfy the composition of all input policies. There has been limited success so far achieving homomorphic encryption in the functional setting; that is, for primitives such as Ciphertext-Policy Attribute Based Encryption (CP-ABE) and Identity Based Encryption (IBE). We introduce a new primitive that captures homomorphic encryption with support for access policies and policy composition. We then present a generic construction using CP-ABE and multikey Fully-Homomorphic encryption (FHE). Furthermore, we show that a CP-ABE scheme that is homomorphic for circuits of polylogarithmic depth in some parameter $m$ implies a CP-ABE scheme that is homomorphic for circuits of arity $m$ and unbounded depth.

In a public-key encryption scheme,

if a sender is not concerned about the security of a message and

is unwilling to generate costly randomness,

the security of the encrypted message can be compromised.

This is caused by the \\emph{laziness} of the sender.

In this work, we characterize \\emph{lazy parties} in cryptography.

Lazy parties are regarded as honest parties in a protocol,

but they are not concerned about the security of the protocol in

a certain situation.

In such a situation, they behave in an honest-looking way, and are unwilling to do a costly task.

We study, in particular, public-key encryption with lazy parties.

Specifically, as the first step toward understanding the behavior of lazy parties

in public-key encryption, we consider a rather simple setting in which

the costly task is to generate randomness used in algorithms,

and parties can choose either costly good randomness or cheap bad randomness.

We model lazy parties as rational players who behaves rationally to

maximize their utilities, and define a security game between lazy parties

and an adversary.

A secure encryption scheme requires that the game is conducted by

lazy parties in a secure way if they follow a prescribed strategy,

and the prescribed strategy is a good equilibrium solution for the game.

Since a standard secure encryption scheme does not work for lazy parties,

we present some public-key encryption schemes that are secure for lazy parties.

Many computers emit a high-pitched noise during operation, due to vibration in some of their electronic components. These acoustic emanations are more than a nuisance: they can convey information about the software running on the computer, and in particular leak sensitive information about security-related computations. In a preliminary presentation (Eurocrypt\'04 rump session), we have shown that different RSA keys induce different sound patterns, but it was not clear how to extract individual key bits. The main problem was that the acoustic side channel has a very low bandwidth (under 20 kHz using common microphones, and a few hundred kHz using ultrasound microphones), many orders of magnitude below the GHz-scale clock rates of the attacked computers.

In this paper we describe a new acoustic cryptanalysis key extraction attack, applicable to GnuPG\'s current implementation of RSA. The attack can extract full 4096-bit RSA decryption keys from laptop computers (of various models), within an hour, using the sound generated by the computer during the decryption of some chosen ciphertexts. We experimentally demonstrate that such attacks can be carried out, using either a plain mobile phone placed next to the computer, or a more sensitive microphone placed 4 meters away.

Beyond acoustics, we demonstrate that a similar low-bandwidth attack can be performed by measuring the electric potential of a computer chassis. A suitably-equipped attacker need merely touch the target computer with his bare hand, or get the required leakage information from the ground wires at the remote end of VGA, USB or Ethernet cables.

We reformalize and recast dual-receiver encryption (DRE) proposed in CCS \'04, a public-key encryption (PKE) scheme for encrypting to two independent recipients in one shot. We start by defining the crucial soundness property for DRE, which ensures that two recipients will get the same decryption result. While conceptually simple, DRE with soundness turns out to be a powerful primitive for various goals for PKE, such as complete non-malleability (CNM) and plaintext-awareness (PA). We then construct practical DRE schemes without random oracles under the Bilinear Decisional Diffie-Hellman assumption, while prior approaches rely on random oracles or inefficient non-interactive zero-knowledge proofs. Finally, we investigate further applications or extensions of DRE, including DRE with CNM, combined use of DRE and PKE, strengthening two types of PKE schemes with plaintext equality test, off-the-record messaging with a stronger notion of deniability, etc.

The Side Channel Analysis is now a classic way to retrieve a secret key in the smart-card world. Unfortunately, most of the ensuing attacks require the plaintext or the ciphertext used by the embedded algorithm. In this article, we present a new method for exploiting the leakage of a device without this constraint. Our attack is based on a study of the leakage distribution of internal data of a cryptographic function and can be performed not only at the beginning or the end of the algorithm, but also at every instant that involves the secret key. This paper focuses on the distribution study and the resulting attack. We also propose a way to proceed in a noisy context using smart distances. We validate our proposition by practical results on an AES128 software implemented on a ATMega2561 and on the DPA contest v4.

The notion of differing-inputs obfuscation (diO) was introduced by Barak et al. (CRYPTO 2001). It guarantees that for any two circuits $C_0, C_1$, for which it is difficult to use their description and come up with an input $x$ on which they differ $C_0(x) \\neq C_1(x)$, it should also be difficult to distinguish the obfuscation of $C_0$ from that of $C_1$. This is a strengthening of indistinguishability obfuscation, where the above is only guaranteed for circuits that agree on all inputs: $C_0(x) = C_1(x)$ for all $x$. Two recent works of Ananth et al. (ePrint 2013) and Boyle et al. (TCC 2014) study the notion of diO in the setting where the attacker is also given some auxiliary information related to the circuits, showing that this notion leads to many interesting applications. One of these applications is extractable witness encryption, defined by Goldwasswer et al. (CRYPTO \'13), which in turn leads to constructions of functional encryption and reusable garbling schemes that work directly on Turing Machines rather than circuits.

In this work, we show that the existence of general-purpose diO with general auxiliary input leads to a surprising ``implausible\'\' consequence: in particular, it would show the impossibility of obfuscating a specific circuit $C^*$ with specific auxiliary input $\\aux^*$ in a way that hides some specific information. In particular, we put forth the assumption that such special-purpose obfuscation exists, and under this assumption, we show that general-purpose diO does not exist. This special-purpose obfuscation assumption isn\'t implied by diO itself and hence we do not get an unconditional impossibility result. However, the special-purpose obfuscation assumption is a falsifiable assumption which we do not know how to break for candidate obfuscation schemes. Showing the existence of general-purpose diO with general auxiliary input would necessitate showing how to break this assumption. We also give a similar result showing the impossibility of extractable witness encryption under the same special-purpose obfuscation assumption.