International Association
for Cryptologic Research

In this paper a new public key system based on polynomials over finite fields GF(2) is developed.The security of the system is based on the difficulty of solving discrete logarithms over GF(2^k)

with sufficiently large k. The presented system has all features of ordinary public key schemes such as public key encryption and digital signatures. The security and implementation aspects of the presented system are also introduced along with comparison with other well known public- key systems.

At Crypto 2013, Coron, Lepoint, and Tibouchi~(CLT) proposed a practical Graded Encoding Scheme (GES) over the integers, which has very similar cryptographic features to ideal multilinear maps. In fact, the scheme of Coron~{\\em et al.} is the second proposal of a secure GES, and has advantages over the first scheme of Garg, Gentry, and Halevi~(GGH). For example, unlike the GGH construction, the subgroup decision assumption holds in the CLT construction. Immediately following the elegant innovations of the GES, numerous GES-based cryptographic applications were proposed. Although these applications rely on the security of the underlying GES, the security of the GES has not been analyzed in detail, aside from the original papers produced by Garg~{\\em et~al.} and Coron~{\\em et~al.}

We present an attack algorithm against the system parameters of the CLT GES. The proposed algorithm\'s complexity $\\tilde\\bO(2^{\\rho/2})$ is exponentially smaller than $\\tilde\\bO(2^{\\rho})$ of the previous best attack of Coron~{\\em et al.}, where $\\rho$ is a function of the security parameter. Furthermore, we identify a flaw in the generation of the zero-testing parameter of the CLT GES, which drastically reduces the running time of the proposed algorithm. The experimental results demonstrate the practicality of our attack.

Simple AEAD Hardware Interface (S{\\AE}HI) is a hardware cryptographic

interface aimed at CAESAR Authenticated Encryption with Associated

Data (AEAD) algorithms. Cryptographic acceleration is typically

achieved either with a coprocessor or via instruction set

extensions. ISA modifications require re-engineering the CPU core,

making the approach inapplicable outside the realm of open source

processor cores. Our proposed hardware interface is a memory-mapped

cryptographic coprocessor, implementable even on very low end FPGA

evaluation platforms. Algorithms complying to S{\\AE}HI must also

include C language API drivers that directly utilize the

memory mapping in a ``bare metal\'\' fashion. This can also

be accommodated on MMU systems.

Extended battery life and bandwidth resulting from dedicated

cryptographic hardware is vital for currently dominant computing and

communication devices: mobile phones, tablets, and Internet-of-Things

(IoT) applications. We argue that these should be priority hardware

optimization targets for AEAD algorithms with realistic payload

profiles.

We demonstrate a fully integrated implementation of WhirlBob

and Keyak AEADs on the FPGA fabric of Xilinx Zynq 7010. This low-cost

System-on-Chip (SoC) also houses a dual-core Cortex-A9 CPU, closely

matching the architecture of many embedded devices. The on-chip

coprocessor is accessible from user space with a Linux

kernel driver. An integration path exists all the way to end-user

applications.

The Vernam Algorithm has long been unable to be commercially used because it requires the key to be transmitted with the ciphertext, an obvious security hazard. What has been developed with this methodology is to take a fixed key, XOR 4 randomly selected/extracted segments of this key together forming an \'Effective Key Stream\' and XOR\'ing that with the plaintext. With both the sender and receiver possessing the fixed key, using this new methodology circumvents the requirement to send the key along with the ciphertext.

Considering the drastic reduction in computations needed, this algorithm executes at better than four times faster than the AES. With our society becoming more and more digitally oriented, faster security is needed.

In Broadcast Encryption (BE) systems like Pay-TV, AACS, online content sharing and broadcasting, reducing the header length (communication overhead per session) is of practical interest. The Subset Difference (SD) scheme due to Naor-Naor-Lotspiech (NNL) is the most popularly used BE scheme. It assumes an underlying full binary tree to assign keys to subsets of users. In this work, we associate short tree structures of height $a$ to nodes in the binary tree to assign keys to more subsets. This ensures that for any set of revoked users, the header length is in general less and never more than the NNL-SD scheme. Experimental studies show that the average header length is always less than that of the NNL-SD scheme and decreases as $a$ increases. User storage in the new scheme is more than that of the NNL-SD scheme but is not prohibitively expensive. By choosing a suitable value of $a$, it is possible to obtain substantial reduction in the communication overhead at the cost of a tolerable increase in the user storage.

NMAC is a mode of operation which turns a fixed input-length

keyed hash function f into a variable input-length function.

A~practical single-key variant of NMAC called HMAC is a very

popular and widely deployed message authentication code

(MAC). Security proofs and attacks for NMAC can typically

be lifted to HMAC.

NMAC was introduced by Bellare, Canetti and Krawczyk

[Crypto\'96], who proved it to be a secure pseudorandom

function (PRF), and thus also a MAC, assuming that

(1) f is a PRF and

(2) the function we get when cascading f is weakly

collision-resistant.

Unfortunately, HMAC is typically instantiated with

cryptographic hash functions like MD5 or SHA-1 for which (2)

has been found to be wrong. To restore the provable

guarantees for NMAC, Bellare [Crypto\'06] showed its

security based solely on the assumption that f is a PRF,

albeit via a non-uniform reduction.

Our first contribution is a simpler and uniform proof: If f

is an \\eps-secure PRF (against q queries) and a

\\delta-non-adaptively secure PRF (against q queries), then

NMAC^f is an (\\eps+lq\\delta)-secure PRF against q queries of

length at most l blocks each.

We then show that this \\eps+lq\\delta bound is basically

tight. For the most interesting case where lq\\delta>=\\eps

we prove this by constructing an f for which an attack with

advantage lq\\delta exists. This also violates the bound

O(l\\eps) on the PRF-security of NMAC recently claimed by

Koblitz and Menezes.

Finally, we analyze the PRF-security of a modification of

NMAC called NI [An and Bellare, Crypto\'99] that differs

mainly by using a compression function with an additional

keying input. This avoids the constant rekeying on

multi-block messages in NMAC and allows for a security proof

starting by the standard switch from a PRF to a random

function, followed by an information-theoretic analysis. We

carry out such an analysis, obtaining a tight lq^2/2^c bound

for this step, improving over the trivial bound of

l^2q^2/2^c. The proof borrows combinatorial techniques

originally developed for proving the security of CBC-MAC

[Bellare et al., Crypto\'05]. We also analyze a variant of

NI that does not include the message length in the last call

to the compression function, proving a l^{1+o(1)}q^2/2^c

bound in this case.

Enumeration algorithms are the best currently known methods to solve lattice problems, both in theory (within the class of polynomial space algorithms), and in practice (where they are routinely used to evaluate the concrete security of lattice cryptography). However, there is an uncomfortable gap between our theoretical understanding and practical performance of lattice point enumeration algorithms.

The algorithms typically used in practice have worst-case asymptotic running time $2^{O(n^2)}$, but perform extremely well in practice, at least for all values of the lattice dimension for which experimentation is feasible. At the same time, theoretical algorithms

(Kannan, Mathematics of Operation Research 12(3):415-440, 1987) are asymptotically superior (achieving $2^{O(n \\log n)}$ running time), but they are never used in practice because they incur a substantial overhead that makes them uncompetitive for all reasonable values of the lattice dimension $n$. This gap is especially troublesome when algorithms are run in practice to evaluate the concrete security of a cryptosystem, and then experimental results are extrapolated to much larger dimension where solving lattice problems is computationally infeasible.

We introduce a new class of (polynomial space) lattice enumeration algorithms that simultaneously achieve asymptotic efficiency (meeting the theoretical $n^{O(n)} = 2^{O(n \\log n)}$ time bound) and practicality, matching or surpassing the performance of practical algorithms already in moderately low dimension. Key technical contributions that allow us to achieve this result are a new analysis technique that allows us to greatly reduce the number of recursive calls performed during preprocessing (from super exponential in $n$ to single exponential, or even polynomial in $n$), a new enumeration technique that can be directly applied to projected lattice (basis) vectors, without the need to remove linear dependencies, and a modified block basis reduction method with fast (logarithmic) convergence properties. The last technique is used to obtain a new SVP enumeration procedure with $\\tilde O(n^{n/2e})$ running time, matching (even in the constant in the exponent) the optimal worst-case analysis (Hanrot and Stehl{\\\'e}, CRYPTO 2007)

of Kannan\'s theoretical algorithm, but with far superior performance

in practice.

We complement our theoretical analysis with a comprehensive set of experiments that not only support our practicality claims, but also allow to estimate the cross-over point between different versions of enumeration algorithms, as well as asymptotically faster (but not quite practical) algorithms running in single exponential $2^{O(n)}$ time and space.

MDS matrices allow to build optimal linear diffusion layers in block ciphers. However, MDS matrices cannot be sparse and usually have a large description, inducing costly software/hardware implementations.

Recursive MDS matrices allow to solve this problem by focusing on MDS

matrices that can be computed as a power of a simple companion matrix,

thus having a compact description suitable even for constrained environments. However, up to now, finding recursive MDS matrices required to perform an exhaustive search on families of companion matrices, thus limiting the size of MDS matrices one could look for. In this article we propose a new direct construction based on shortened BCH codes, allowing to efficiently construct such matrices for whatever parameters. Unfortunately, not all recursive MDS matrices can be obtained from BCH codes, and our algorithm is not always guaranteed to find the best matrices for a given set of parameters.

We propose the first practical attribute-based signature (ABS) scheme with attribute privacy without pairings in the random oracle model. Our strategy is in the Fiat-Shamir paradigm; we first provide a concrete construction of a $\\Sigma$-protocol of \\textit{boolean proof}, which is a generalization of the well-known $\\Sigma$-protocol of OR-proof, so that it can treat any monotone boolean formula instead of a single OR-gate. Then, we apply the Fiat-Shamir transformation to our $\\Sigma$-protocol of boolean proof and obtain a non-interactive witness-indistinguishable proof of knowledge system (NIWIPoK) which has a knowledge extractor in the random oracle model. Finally, by combining our NIWIPoK with a credential bundle scheme of the Fiat-Shamir signature, we obtain an attribute-based signature scheme (ABS) which possesses the property of attribute privacy. The series of constructions are obtained from a given $\\Sigma$-protocol and can be attained without pairings.

In this paper, we present new classes of public key cryptosystem over $F_2^8$ based on Reed-Solomon codes, referred to as K(XVII)SE(1)PKC

and K(XVII)$\\Sigma \\Pi$PKC, a subclass of K(XVII)SE(1)PKC.

We show that K(XVII)SE(1)PKC over $F_2^8$ can be secure against the various attacks.

We also present K(XVII)$\\Sigma \\Pi$PKC over $F_2^8$, a subclass of K(XVII)SE(1)PKC.

We show that any assertion of successfull attack on K(XVII)SE(1)PKC including K(XVII)$\\Sigma \\Pi$PKC whose parameters are properly chosen

is a coding theoretical contradiction.

We thus conclude that K(XVII)SE(1)PKC and K(XVII)$\\Sigma \\Pi$PKC would be secure against the various attacks including LLL attack.

The schemes presented in this paper would yield brand-new techniques in the field of code-based PKC.

Submission: 15 September 2014
Notification: 16 November 2014
From January 26 to January 30
Location: San Juan, Puerto Rico
More Information: http://fc15.ifca.ai/

Side-channel attacks are a powerful tool to discover the

cryptographic secrets of a chip or other device but only too often do they require too many traces or leave too many possible keys to

explore. In this paper we show that for side channel attacks on

discrete-logarithm-based systems significantly more unknown bits can

be handled by using Pollard\'s kangaroo method: if $b$ bits are

unknown then the attack runs in $2^{b/2}$ instead of $2^b$. If an

attacker has many targets in the same group and thus has reasons to

invest in precomputation, the costs can even be brought down to

$2^{b/3}$.

Usually the separation between known and unknown keybits is not this clear cut -- they are known with probabilities ranging between 100\\%

and 0\\%. Enumeration and rank estimation of cryptographic keys

based on partial information derived from cryptanalysis have become

important tools for security evaluations. They make the line between

a broken and secure device more clear and thus help security

evaluators determine how high the security of a device is. For

symmetric-key cryptography there has been some recent work on key

enumeration and rank estimation, but for discrete-logarithm-based

systems these algorithms fail because the subkeys are not

independent and the algorithms

cannot take advantage of the above-mentioned faster

attacks. We present $\\epsilon$-enumeration as a new method to

compute the rank of a key by using the probabilities together with

(variations of) Pollard\'s kangaroo algorithm and give experimental evidence.

Submission: 30 July 2014
Notification: 15 August 2014
From September 25 to September 27
Location: Jabalpur, India
More Information: http://nwc.iiitdmj.ac.in/

Since the advent of secret sharing scheme many researches have been allocated to study on this topic because it has a lot of application. For the first time Shamir and Blakley introduced the concepts of secret sharing. In their scheme, just one secret is shared. After a while, Harn present a scheme in which many secrets can be shared, but the secrets have to recover in predetermined order. In addition, in his scheme just one share is assigned to each participant. After a while, many scheme introduced such that they have not any constraint on the order of recovering secrets. These kind of scheme is called Multi Secret Sharing Scheme and it abbreviated by MSS. To the best of our knowledge, up until now, no exact definition for the security of MSS scheme has been presented. In this paper, a definition for secrecy of MSS scheme is introduced and a MSS scheme is presented based on Learning With Error (LWE). LWE is a one of lattice concepts which nowadays constitutes the core of many cryptographic constructions because the hardness of lattice problems is well studied and the hardness of these constructions can be reduced to NP-Hard problems. The advantage of using LWE is twofold, first is that the hardness of LWE is well understood, second working with it is very simple because just simple operations are used. At the end of the paper a verifiable version of presented MSS scheme is given. Verifiability is an important feature which has defined. In this kind of schemes, dishonest dealer or participants can be identified.

We are seeking six (6) highly motivated faculty members to join the Institute starting September 2015. Applications are being accepted for two assistant professors in Computer Engineering, two assistant professors in Information Technology, one assistant professor in Cyber Security, and one associate professor in Computer Science. These are all full-time tenure-track/tenure-eligible positions with a nine-month service period. Each position requires a Ph.D. (or foreign equivalent) in one of the following domains: Computer Science, Computer Engineering, Electrical Engineering, Systems Engineering, Software Engineering, Information Systems, Information Technology, or a related field. For the Computer Engineering program, we seek candidates whose research focuses on hardware aspects of big data or cyber security (architecture, embedded systems). For Information Technology, we seek candidates with research foci in HCI, cyber security or systems integration, preferably mobile systems. We seek one assistant professor whose research focuses on cyber security and is applicable to all our programs. In Computer Science, we seek applicants with research strength in software engineering, distributed computing or operating systems, as well as experience in professional accreditation activities and assessment. Please see http://www.tacoma.uw.edu/institute-technology/ for more details. Questions related to these positions are to be directed to the search committee co-chairs, Dr. Bryan Goda, at 253 692 4581 or godab (at) uw.edu; or Dr. Ankur Teredesai, at 253 692 4806 or ankurt (at) uw.edu. Although these positions are contingent on available funding and will remain open until filled, applications received before October 1, 2014 will receive priority review.

We present a round-efficient black-box construction of a general MPC protocol that satisfies composability in the plain model. The security of our protocol is proven in angel-based UC framework under the minimal assumption of the existence of semi-honest oblivious transfer protocols. When the round complexity of the underlying oblivious transfer protocol is Round(OT), the round complexity of our protocol is max(\\tilde{O}(log^2 n), O(Round(OT))). Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives \\tilde{O}(log^2 n)-round protocol under these assumptions. Previously, only an O(max(n^{\\epsilon}, Round(OT))-round protocol was shown, where \\epsilon>0 is an arbitrary constant.

We obtain our MPC protocol by constructing a \\tilde{O}(log^2 n)-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.

By introducing extra shields on Shpilrain and Ushakov\'s Ko-Lee-like protocol based on the decomposition problem of group elements we propose two new key exchange schemes and then a number of public key cryptographic protocols. We show that these protocols are free of known attacks. Particularly,if the entities taking part in our protocols create their private keys composed by the generators of the Mihailova subgroups of Bn, we show that the safety of our protocols are very highly guarantied by the insolvability of subgroup membership problem of the Mihailova subgroups.

In this paper we study the existing CRT-RSA countermeasures against fault-injection attacks.

In an attempt to classify them we get to achieve deep understanding of how they work.

We show that the many countermeasures that we study (and their variations) actually share a number of common features, but optimize them in different ways.

We also show that there is no conceptual distinction between test-based and infective countermeasures and how either one can be transformed into the other.

Furthermore, we show that faults on the code (skipping instructions) can be captured by considering only faults on the data.

These intermediate results allow us to improve the state of the art in several ways:

(a) we fix an existing and that was known to be broken countermeasure (namely the one from Shamir);

(b) we drastically optimize an existing countermeasure (namely the one from Vigilant) which we reduce to 3 tests instead of 9 in its original version, and prove that it resists not only one fault but also an arbitrary number of randomizing faults;

(c) we also show how to upgrade countermeasures to resist any given number of faults: given a correct first-order countermeasure, we present a way to design a provable high-order countermeasure (for a well-defined and reasonable fault model).

Finally, we pave the way for a generic approach against fault attacks for any modular arithmetic computations, and thus for the automatic insertion of countermeasures.

In cryptography, forward secrecy is a well-known property of key agreement protocols. It

ensures that a session key remains secure even if one of the long-term secret keys is compromised in

the future. In this paper, we investigate some forward security properties for Public-key Encryption

with Keyword Search (PEKS) schemes, which allow a client to store encrypted data and delegate

search operations to a server. The proposed properties guarantee that the client\'s privacy is protected

to the maximum extent when his private key is compromised. Motivated by the generic transformation

from anonymous Identity-Based Encryption (IBE) to PEKS, we correspondingly propose some

forward security properties for IBE, in which case we assume the attacker learns the master secret

key. We then study several existing PEKS and IBE schemes, including a PEKS scheme by Nishioka,

an IBE scheme by Boneh, Raghunathan and Segev, and an IBE scheme by Arriaga, Tang and Ryan.

Our analysis indicates that the proposed forward security properties can be achieved by some of

these schemes if the attacker is RO-non-adaptive (the attacker does not define its distributions based

on the random oracle). Finally, we show how to extend the Boyen-Waters anonymous IBE scheme

to achieve the forward security properties for adaptive attackers.

Authors propose several approaches for increasing performance of multiplicative inversion algorithm in binary fields based on Extended Euclidean Algorithm (EEA). First approach is based on Extended Euclidean Algorithm specificity: either invariant polynomial u remains intact or swaps with invariant polynomial v. It makes it possible to avoid necessity of polynomial v degree computing. The second approach is based on searching the \"next matching index\" when calculating the degree of the polynomial, since degree polynomial invariant u at least decreases by 1, then it is possible to use current value while further calculation the degree of the polynomial.