| Report on recent publications (#11) |
|
|
|
| Written by Giulia Biagini | ||||
| Tuesday, 04 December 2007 | ||||
|
Report on the publications from the 8th of October to the 4th of December.
In A generalization of the original Diffie-Hellman key exchange in (ℤ/pℤ)* found a new depth when Miller and Koblitz suggested that such a protocol could be used with the group over an elliptic curve.
Maze, Monico and Rosenthal extend such a generalization to the setting
of a Semi-group action on a finite set, more precisely, linear actions
of abelian semi-rings on semi-modules.
In this paper, we extend such a generalization to the linear actions of
quotient semi-rings on semi-modules. In fact, we show how the action of
quotient semi-rings on a semi-module gives rise to a generalized
Diffie-Hellman and ElGamal protocol. This leads naturally to a
cryptographic protocol whose difficulty is based on the hardness of a
particular control problem, namely the problem of steering the state of
some dynamical system from an initial vector to some final location.
A Fast Protocol for Computationally Private Information Retrieval (Andy Parrish and Jonathan Trostle)
We present a new private information retrieval (PIR) protocol. The
protocol is based on a single private, non-shared key cryptosystem; the
security of this cryptosystem is based on a new hardness (secret base)
assumption. We prove security for the secret base assumption in an
extended generic group model. We also show parameters that ensure
security against a lattice-based attack. We measure performance using
the methodology in \cite{sion}; our scheme is orders of magnitude
faster than any existing scheme and faster than the trivial protocol
for the home user scenario.
Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithm (Haining Fan and Jiaguang Sun and Ming Gu and Kwok-Yan Lam)
We describe how a recently proposed way to split
input operands allows for fast VLSI implementations of GF(2)[x]
Karatsuba-Ofman multipliers. The XOR gate delay of the proposed
multiplier is
better than that of previous Karatsuba-Ofman multipliers. For example,
it is reduced by about 33% and 25% for n = 2^i and n = 3^i (i > 1),
respectively.
Almost-everywhere Secure Computation (Juan A. Garay and Rafail Ostrovsky)
Secure multi-party computation (MPC) is a central
problem in cryptography. Unfortunately, it is well known that MPC is
possible if and only if the underlying communication network has very
large connectivity---specifically, $\Omega(t)$, where $t$ is the number
of potential corruptions in the network. This impossibility result
renders existing MPC results far less applicable in practice, since
most deployed networks have in fact a very small degree.
In this paper, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). In fact, the notion we introduce, which we call {\em almost-everywhere MPC}, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corruptions. In essence, our definition allows the adversary to {\em implicitly} wiretap some of the good nodes by corrupting sufficiently many nodes in the ``neighborhood'' of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions.
Instrumental in our constructions is a new model and
protocol for the {\em secure message transmission} (SMT) problem, which
we call {\em SMT by public discussion}, and which we use for the
establishment of pairwise secure channels in limited connectivity
networks.
The goal of this paper is to analyze the security
of dithered variants of the Merkle-Damgard mode of operation that use a
third input to indicate the position of a block in the message to be
hashed. These modes of operation for hash functions have been proposed
to avoid some structural weaknesses of the Merkle-Damgard paradigm,
e.g. that second preimages can be constructed in much less than $2^n$
work, as pointed out by Kelsey and Schneier. Among the modes of
operation that use such a third input are Rivest's dithered hashing and
Biham and Dunkelman's HAIFA proposal.
We propose several new second preimage attacks on the Merkle-Damgard
mode of operation, which can also attack Rivest's dithered hash with
almost the same complexity. When applied to Shoup's UOWHF, these
attacks can be shown to be optimal since their complexity matches
Shoup's security bound.
To construct a suitable and secure proxy
re-signature scheme is not an easy job, up to now, there exist only
three schemes, one is proposed by Blaze et al. at EUROCRYPT 1998, and
the others are proposed by Ateniese and Hohenbergerat ACM CCS 2005.
However, none of these schemes is proved in the standard model (i.e.,
do not rely on the random oracle heuristic). In this paper, based on
Waters' approach, we first propose a multi-use bidirectional proxy
re-signature scheme, denoted as $S_{mb}$, which is existentially
unforgeable in the standard model. And then, we extend $S_{mb}$ to be a
multi-use bidirectional ID-based proxy re-signature scheme, denoted by
$S_{id-mb}$, which is also existentially unforgeable in the standard
model. Both of these two proposed schemes are computationally
efficient, and their security bases on the Computational Diffie-Hellman
(CDH) assumption.
On the security defects of an image encryption scheme (Chengqing Li, Shujun Li, Muhammad Asim, Juana Nunez, Gonzalo Alvarez and Guanrong Chen)
This paper studies the security of a recently-proposed chaos-based
image encryption scheme, and points out the following problems: 1)
there exist a number of invalid keys and weak keys, and some keys
are partially equivalent for encryption/decryption; 2) given one
chosen plain-image, a subkey $K_{10}$ can be guessed with a smaller
computational complexity than that of the simple brute-force attack;
3) given at most 128 chosen plain-images, a chosen-plaintext attack
can possibly break the following part of the secret key: $\{K_i\bmod
128\}_{i=4}^{10}$, which works very well when $K_{10}$ is not too
large; 4) when $K_{10}$ is relatively small, a known-plaintext
attack can be carried out with only one known plain-image to recover
some visual information of any other plain-images encrypted by the
same key.
A Short Signature Scheme in the Standard Model (Li Kang and Xiaohu Tang and Xianhui Lu and Jia Fan)
In this paper, by elaborately choosing the parameters of Waters
Hash function, we propose a new efficient signature scheme. It is
shown that the scheme is secure against strongly unforgeable
chosen-message attacks in the standard model under Computational
Diffie-Hellman (CDH) assumption. Further, among all the known
secure signatures in the standard model, our scheme is the
shortest one and has the efficient security reduction as well.
Ceremony Design and Analysis (Carl Ellison)
The concept of ceremony is introduced as an
extension of the concept of network protocol, with human nodes
alongside computer nodes and with communication links that include UI,
human-to-human communication and transfers of physical objects that
carry data. What is out-of-band to a protocol is in-band to a ceremony,
and therefore subject to design and analysis using variants of the same
mature techniques used for the design and analysis of protocols.
Ceremonies include all protocols, as well as all applications with a
user interface, all workflow and all provisioning scenarios. A secure
ceremony is secure against both normal attacks and social engineering.
However, some secure protocols imply ceremonies that cannot be made
secure.
REMARKS ON IBE SCHEME OF WANG AND CAO (Sunder Lal and Priyam Sharma)
In this paper we analyze and find an anomaly in
the security proof of the identity-based encryption (IBE) scheme
fullM-IBE of Wang and Cao [9], which is based on mBDHP. Here we give
another proof for fullM-IBE which is based on Bilinear Diffie-Hellman
Problem (BDHP). We also obtain a tightness improvement using a stronger
assumption, namely, the Bilinear Inverse Dicision Diffie-Hellman
problem (BIDDHP).
Another Look at Automated Theorem-Proving (Neal Koblitz)
I examine the use of automated theorem-proving for
reductionist security arguments in cryptography and discuss three
papers that purport to show the potential of computer-assisted
proof-writing and proof-checking. I look at the proofs that the authors
give to illustrate the "game-hopping" technique -- for Full-Domain Hash
signatures, ElGamal encryption, and Cramer-Shoup encryption -- and ask
whether there is evidence that automated theorem-proving can contribute
anything of value to the security analysis of cryptographic protocols.
A considerable number of anonymous RFID
authentication schemes have been proposed. However, current proposals
either do not provide robust security guarantees, or suffer from
scalability issues when the number of tags issued by the system is very
large.
In this paper, we focus on approaches that reconcile these important
requirements. In particular, we seek to reduce the complexity of
identifying tags by the back-end server in anonymous RFID
authentication protocols---what we term the key-lookup problem.
We propose a compiler that transforms a generic RFID authentication
protocol (supporting anonymity) into one that achieves the same
guarantees with constant key-lookup cost even when the number of tags
is very large (billions of tags and beyond). This approach uses
a lightweight one-way trapdoor function and produces protocols that are
suitable for deployment into current tag architectures. We then explore
the issue of minimal assumptions required, and show that one-way
trapdoor functions are necessary to achieve highly scalable, robustly
secure solutions. We then relax the requirement of unlinkable
anonymity, and consider scalable solutions that are provably secure and
for which the loss of privacy is minimal.
Turbo SHA-2
(Danilo Gligoroski and Svein Johan Knapskog)
In this paper we describe the construction of
Turbo SHA-2 family of cryptographic hash functions. They are built with
design components from the SHA-2 family, but the new hash function has
three times more chaining variables, it is more robust and resistant
against generic multi-block collision attacks, its design is resistant
against generic length extension attacks and it is 2 - 8 times faster
than the original SHA-2. It uses two novel design principles in the
design of hash functions: {\em 1. Computations in the iterative part of
the compression function start by using variables produced in the
message expansion part that have the complexity level of a random
Boolean function, 2. Variables produced in the message expansion part
are not discarded after the processing of the current message block,
but are used for the construction of the three times wider chain for
the next message block.} These two novel principles combined with the
already robust design principles present in SHA-2 (such as the
nonlinear message expansion part), enabled us to build the compression
function of Turbo SHA-2 that has just 16 new variables in the message
expansion part (compared to 48 for SHA-256 and 64 for SHA-512) and just
8 rounds in the iterative part (compared to 64 for SHA-256 and 80 for
SHA-512).
Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products (Jonathan Katz and Amit Sahai and Brent Waters)
Predicate encryption is a new paradigm
generalizing, among other
things, identity-based encryption. In a predicate encryption scheme,
secret keys correspond to predicates and ciphertexts are associated
with attributes; the secret key SK_f corresponding to the predicate
f can be used to decrypt a ciphertext associated with attribute I if
and only if f(I)=1. Constructions of such schemes are currently known
for relatively few classes of predicates.
We construct such a scheme for predicates
corresponding to the evaluation of inner products over N (for some
large integer N).
This, in turn, enables constructions in which predicates correspond to
the evaluation of disjunctions, polynomials, CNF/DNF formulae, or
threshold predicates (among others). Besides serving as what we feel is
a significant step forward in the theory of predicate encryption,
our results lead to a number of applications that are interesting in
their own right.
We prove that a random map drawn from any class ${\frak C}$ of polynomial
maps from $F_q^n$ to $F_q^{n+r}$ that is (i) totally
random in the affine terms, and (ii) has a negligible chance of being
not strongly one-way, provides a secure PRNG (hence a secure stream
cipher) for any q. Plausible choices for ${\frak C}$ are semi-sparse
(i.e., the affine terms are truly random) systems and other systems
that are easy to evaluate from a small (compared to a generic map)
number of parameters.
To our knowledge, there are no other positive results for provable security of specialized polynomial systems, in particular sparse ones (which are natural candidates to investigate for speed). We can build a family of provably secure stream ciphers a rough implementation of which at the same security level can be more than twice faster than an optimized QUAD (and any other provably secure stream ciphers proposed so far), and uses much less storage. This may also help build faster provably secure hashes. We also examine the effects of recent results on specialization on security, e.g., Aumasson-Meier (ICISC 2007), which precludes Merkle-Damgaard compression using polynomials systems {uniformly very sparse in every degree} from being universally collision-free. We conclude that our ideas are consistent with and complements these new results. We think that we can build secure primitives based on specialized (versus generic) polynomial maps which are more efficient.
In most interesting cases, the security of
cryptographic protocols relies on the assumption that adversarial
entities have limited
computational power, and it is generally accepted that security
degrades progressively over time. However, some cryptographic services
(e.g., time-stamping services or digital archives) are long-lived in
nature; that is, their lifetime need not be bounded by a polynomial. In
such cases, it is impossible to guarantee security in the traditional
sense: even information theoretically secure protocols can fail if the
attacker is given sufficient run time.
This work proposes a new paradigm for long-lived computation, where computational restrictions are stated in terms of space and processing rates. In this setting, entities may live for an unbounded amount of real time, subject to the condition that only a polynomial amount of work can be done per unit real time. Moreover, the space used by these entities is allocated dynamically and must be polynomially bounded. We propose a key notion of approximate implementation, which is an adaptation of computational indistinguishability to the long-lived setting. We show that approximate implementation is preserved under polynomial parallel composition, and under exponential sequential composition. This provides core foundations for an exciting new area, namely, the analysis of long-lived cryptographic systems.
We investigate an application of RFIDs referred to in the literature as the group scanning problem, in which several tags are ``simultaneously'' scanned by a reader. The security context of this application was first discussed by Ari Juels, who presented a protocol that allows pairs of RFID tags to provide evidence of having been simultaneous scanned---a yoking proof. Our goal is to study group scanning proofs in strong adversarial models. We describe a security model for RFID group scanning proofs, and consider versions of the problem that require privacy (anonymity) of the grouped tags, and/ or forward-security properties. Our security model is based on the Universal Composability framework and supports reusability (through modularity of security guarantees). We also introduce novel protocols that realize the security models, focusing on efficient solutions based on off-the-shelf components, such as highly optimized pseudo-random function designs that require fewer than 2000 Gate-Equivalents. Differential Cryptanalysis of PRESENT (Meiqin Wang)
PRESENT is proposed by A.Bogdanov et al. in CHES 2007 for extremely constrained environments such as RFID tags and sensor networks. In this paper, we find out the differential characteristics for r-round($5 \leq r \leq 15$), then give the differential cryptanalysis on reduced-round variants of PRESENT. We attack 16-round PRESENT using $2^{64}$ chosen plaintexts, $2^{32}$ 6-bit counters, and $2^{65}$ memory accesses. Building a Collision-Resistant Compression Function from Non-Compressing Primitives (Thomas Shrimpton and Martijn Stam)
We consider how to build an efficient compression function from a small
number of random, non-compressing primitives (fixed-key blockciphers
were our original motivation). Our main goal is to achieve a level of
collision resistance as close as possible to the optimal birthday
bound. We present a $2n$-to-$n$ bit compression function based on
three independent $n$-to-$n$ bit random functions, each called only
once. We show that if the three random functions are treated as
black boxes (i.e., modelled as random oracles),
finding collisions requires $\Theta(2^{n/2}/n^c)$ queries
for $c\approx 1$. We also give a heuristic,
backed by experimental results, suggesting that the security loss is
at most four bits for block sizes up to 256 bits.
We believe this is the best result to date on the matter of building a collision resistant compression function from non-compressing functions. It also relates to an open question from Black et al. (Eurocrypt'05), who showed that compression functions that invoke a single non-compressing random function cannot suffice.
Edwards curves have attracted great interest for several reasons.
When curve parameters are chosen properly, the addition formulas use
only $10M+1S$. The formulas are {\it strongly unified}, i.e., work
without change for doublings; even better, they are {\it complete},
i.e., work without change for all inputs. Dedicated doubling formulas
use only $3M+4S$, and dedicated tripling formulas use only $9M+4S$.
This paper introduces {\it inverted Edwards coordinates}. Inverted Edwards coordinates $(X_1:Y_1:Z_1)$ represent the affine point $(Z_1/X_1,Z_1/Y_1)$ on an Edwards curve; for comparison, standard Edwards coordinates $(X_1:Y_1:Z_1)$ represent the affine point $(X_1/Z_1,Y_1/Z_1)$. This paper presents addition formulas for inverted Edwards coordinates using only $9M+1S$. The formulas are not complete but still are strongly unified. Dedicated doubling formulas use only $3M+4S$, and dedicated tripling formulas use only $9M+4S$. Inverted Edwards coordinates thus save $1M$ for each addition, without slowing down doubling or tripling.
A tripartite authenticated key agreement protocol
is designed for three entities to communicate securely over an open
network particularly with a shared key. Recently, we have improved a
one-round tripartite authenticated key agreement protocol proposed by
Lin-Li due to its vulnerability to the forging attack in our previous
report. However, we have later discovered that both the original
Lin-Li’s scheme as well as our previous enhanced protocol is vulnerable
to the insider replay attack. In this paper, we will revise our
improvements and again secure this protocol against these cryptanalytic
attacks.
Proposing a Master One-Way Function (Gideon Samid)
Making an arbitrary binary string fit as a fixed
size cipher key (via hashing) one could use an arbitrary string x as
both plaintext and key to generate a ciphertext, y defined as "the
crypto square of x", while x is the crypto square root of y. Extended
to higher powers, this formalism allows for polynomial morphology that
combines all one-way functions candidates into a single master function
which is at least as intractable as its best ingredient one-way
function. The master list has some interesting and useful attributes:
at will size for both input and output, controlled forward
computational burden, milestone computing, and of course the best
practical chance for being one-way.
We show, how to break TRIVIUM with a setup of 576
(instead of 1152) clock cycles, with an effort of 2^6 chosen IV
resynchronisations up to cycle 625 for each of the 47 recovered key
bits.
This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: – many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; – double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; – many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S-M tradeoffs and includes recent advances such as inverted Edwards coordinates.
The main conclusions are as follows. Optimized precomputations and
triplings save time for single-scalar multiplication in Jacobian
coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel
curves. However, even faster single-scalar multiplication is possible
in Jacobi intersections, Edwards curves, extended Jacobi-quartic
coordinates, and inverted Edwards coordinates, thanks to extremely fast
doublings and additions; there is no evidence that double-base chains
are worthwhile for the fastest curves. Inverted Edwards coordinates are
the speed leader.
A key agreement protocol is designed for two or more entities to agree
upon a shared secret key, which is used to preserve confidentiality and
data integrity over an open network. In 2007, Oh et al. proposed an
efficient ID-based authenticated key agreement protocol on elliptic
curve pairings, which is believed to be able to generate two session
keys securely after a protocol execution. However, we discover that
their protocol is in fact susceptible to the basic impersonation attack
as well as the key compromise impersonation attack. In this paper, we
present the imperfections of Oh et al.'s scheme and subsequently we
suggest a slight modification to the scheme which would resolve the
problems.
Hash Function Design Principles Supporting Variable Output Lengths from One Small Function (Donghoon Chang, Mridul Nandi, Jesang Lee, Jaechul Sung and Seokhie Hong)
In this paper, we introduce new hash function design principles with variable output lengths (multiple of $n$).
It is based on a function or a block cipher which has output size $n$. In the random oracle model it has
optimal collision resistance which requires $\Theta(2^{(t+1)n/2})$ queries to find $(t+1)n$-bit hash
output collisions, where $t$ is any positive integer. Similarly, in the ideal cipher model, $\Theta(2^{(t+1)n/2})$
queries are required to find $(t+1)n$-bit hash output collisions.
Algorithms and Arithmetic Operators for Computing the $\eta_T$ Pairing in Characteristic Three (Jean-Luc Beuchat and Nicolas Brisebarre and J\'er\'emie Detrey and Eiji Okamoto and Masaaki Shirase and Tsuyoshi Takagi)
Since their introduction in constructive cryptographic applications,
pairings over (hyper)elliptic curves are at the heart of an ever
increasing number of protocols. Software implementations being rather
slow, the study of hardware architectures became an active research
area.
In this paper, we discuss several algorithms to compute the $\eta_T$
pairing in characteristic three and suggest further improvements.
These algorithms involve addition, multiplication, cubing, inversion,
and sometimes cube root extraction over $\mathbb{F}_{3^m}$. We propose
a hardware accelerator based on a unified arithmetic operator able to
perform the operations required by a given algorithm. We describe the
implementation of a compact coprocessor for the field
$\mathbb{F}_{3^{97}}$ given by $\mathbb{F}_3[x]/(x^{97}+x^{12}+2)$,
which compares favorably with other solutions described in the open
literature.
Recently Manik et al. [3] proposed a novel remote
user authentication scheme using bilinear pairings. Various attacks
were discussed on this scheme. Recently, Fang et al [15] re-analyzed
these schemes and pointed out that these further proposed schemes are
not secure. They proposed an improvement to previous schemes. Recently,
Giri and Srivastava [16] observed that the improved scheme is still
insecure to off-line attack and they suggested an improvement on Feng
et al's scheme. However, the improved scheme is still insecure. In this
paper, we discuss these attacks and propose an improvement of their
scheme that provides the better security compared to the schemes
previously published
Cryptanalysis of the Random Number Generator of the Windows Operating System (Leo Dorrendorf and Zvi Gutterman and Benny Pinkas)
The pseudo-random number generator (PRNG) used by
the Windows operating system is the most commonly used PRNG. The
pseudo-randomness of the output of this generator is crucial for the
security of almost any application running in Windows. Nevertheless,
its exact algorithm was never published.
We examined the binary code of a distribution of Windows 2000, which is still the second most popular operating system after Windows XP. (This investigation was done without any help from Microsoft.) We reconstructed, for the first time, the algorithm used by the pseudo-random number generator (namely, the function CryptGenRandom). We analyzed the security of the algorithm and found a non-trivial attack: given the internal state of the generator, the previous state can be computed in $O(2^{23})$ work (this is an attack on the forward-security of the generator, an $O(1)$ attack on backward security is trivial). The attack on forward-security demonstrates that the design of the generator is flawed, since it is well known how to prevent such attacks. We also analyzed the way in which the generator is run by the operating system, and found that it amplifies the effect of the attacks: The generator is run in user mode rather than in kernel mode, and therefore it is easy to access its state even without administrator privileges. The initial values of part of the state of the generator are not set explicitly, but rather are defined by whatever values are present on the stack when the generator is called.Furthermore, each process runs a different copy of the generator, and the state of the generator is refreshed with system generated entropy only after generating 128 KBytes of output for the process running it. The result of combining this observation with our attack is that learning a single state may reveal 128 Kbytes of the past and future output of the generator.
The implication of these findings is that a buffer
overflow attack or a similar attack can be used to learn a single state
of the generator, which can then be used to predict all random values,
such as SSL keys, used by a process in all its past and future
operation. This attack is more severe and more efficient than known
attacks, in which an attacker can only learn SSL keys if it is
controlling the attacked machine at the time the keys are used.
This paper presents a critical analysis of the
AACS drive-host authentication scheme. A few weaknesses are identified
which could lead to various attacks on the scheme. In particular, we
observe that the scheme is susceptible to unknown key-share and
man-in-the-middle attacks. Modifications of the scheme are suggested in
order to provide better security. A proof of security of the modified
scheme is also presented. The modified scheme achieves better
efficiency than the original scheme.
The role of help in Classical and Quantum Zero-Knowledge (Andr\'e Chailloux and Iordanis Kerenidis)
We study the role of help in Non-Interactive
Zero-Knowledge protocols and its relation to the standard interactive
model. In the classical case, we show that help and interaction are
equivalent, answering an open question of Ben-Or and Gutfreund
(\cite{BG03}). This implies a new complete problem for the class SZK,
the Image Intersection Density. For this problem, we also prove a
polarization lemma which is stronger than the previously known one.
In the quantum setting, we define the notion of quantum help and show in a more direct way that help and interaction are again equivalent. Moreover, we define quantum Non-Interactive Zero-Knowledge with classical help and prove that it is equal to the class of languages that have classical honest-Verifier Zero Knowledge protocols secure against quantum Verifiers (\cite{Wat06, HKSZ07}). Last, we provide new complete problems for all these quantum classes. Similar results were independently discovered by Dragos Florin Ciocan and Salil Vadhan.
In this paper, we introduce the concept of structural identity-based
encryption (SIBE). Similar to hierarchical identity-based encryption
(HIBE), entities in the system are organized into hierarchy. An
entity in SIBE can decrypt ciphertext for all its ancestors. It can
be seen as an opposite of HIBE, where an entity can decrypt the
ciphertext for all its descendants.
We formalize the notion and security requirements, propose an
efficient construction and show that our construction is secure
under appropriate assumptions in the random oracle model.
The low weight polynomial multiple problem arises in the context of stream ciphers
cryptanalysis and of efficient finite field arithmetic, and is believed to be difficult. It can be formulated as follows: given
a polynomial $f \in \F_2[X]$ of degree $d$, and a bound $n$, the task is to find a low weight multiple of
$f$ of degree at most $n$. The best algorithm known so far to
solve this problem is based on a time memory trade-off and runs in time
${\cal O}(n^{ \lceil {(w - 1)}/{2} \rceil})$ using ${\cal O}(n^{ \lceil
{(w - 1)}/{4} \rceil})$ of memory, where $w$ is the estimated minimal weight.
In this paper, we propose a new technique to find low weight multiples using
lattice basis reduction. Our algorithm runs in time ${\cal O}(n(n-d)^5)$ and uses
${\cal O}(nd)$ of memory. This improves the space needed and
gives a better theoretical time estimate when
$w \geq 12$ or when the \textit{excess degree} $n-d$ is small, say, $(n-d)^5 < n^{\lceil
{(w-3)}/{2} \rceil}$. The former situation is plausible when the bound $n$, which represents the
available keystream, is small, whereas the latter one occurs in efficient finite field arithmetic.
We also propose bounds for the minimal weight
of such multiples, supplying in this sense the state-of-the art techniques with a
method to check whether their estimated minimal weight is in the correct
range. This provides a quantitative cryptographic quality criterion for such
polynomials: the fewer low degree low weight multiples a polynomial has, the
harder becomes this type of cryptanalysis of the corresponding stream
cipher. As an example, the Bluetooth polynomial turns out to be of good
quality in this sense.
Moreover, we introduce the corresponding number problem and apply
a similar strategy to find sparse multiples of a given number with respect to the
Hamming weight of their 2-ary representation. Finally, we run our experiments using the NTL library on some known polynomials in
cryptanalysis and we confirm our analysis.\\
\textbf{Keywords: } stream ciphers analysis, low weight polynomial multiples,
lattices, shortest vector.
We show that computing $e$-th roots modulo $n$ is easier than factoring $n$ with currently known methods, given subexponential access to an oracle outputting the roots of numbers of the form $x_i + c$. Here $c$ is fixed and $x_i$ denotes small integers of the attacker's choosing. Several variants of the attack are presented, with varying assumptions on the oracle, and goals ranging from selective to universal forgeries. The computational complexity of the attack is $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ in most significant situations, which matches the {\sl special} number field sieve's ({\sc snfs}) complexity. This sheds additional light on {\sc rsa}'s malleability in general and on {\sc rsa}'s resistance to affine forgeries in particular -- a problem known to be polynomial for $x_i > \sqrt[3]{n}$, but for which no algorithm faster than factoring was known before this work.
We further analyze the solutions to the
Diophantine equations from which prime-order elliptic curves of
embedding degrees $k=3,4$ or $6$ (MNT curves) may be obtained. We give
an explicit algorithm to generate such curves. We derive a heuristic
lower bound for the number $E(z)$ of MNT curves with $k=6$ and
discriminant $D\le z$, and compare this lower bound with experimental
data.
In this paper, we will describe efficient implementations of
the Tate and Ate pairings over ordinary elliptic curves of embedding degrees
8 and 10. We will discuss the possible curve-dependent optimizations
that can be applied to evaluate the pairings. We pay particular
attention to the use of elliptic curve twists and the denominator elimination
method to make computations more efficient. Our main goal is
to draw together the best possible optimizations that can be used to
efficiently evaluate the Tate and the Ate pairings in both curves and
to give timings and appropriate interpretation on the rate of change on
the running time of our programs for both curves. To come up with an
adequate conclusion, we will compare the performance of the curves we
chose to an already experimented curve of embedding degree 12.
Idempotents in the Neighbourhood of Patterson-Wiedemann Functions having Walsh Spectra Zeros (Sumanta Sarkar and Subhamoy Maitra)
In this paper we study the neighbourhood of
$15$-variable Patterson-Wiedemann (PW) functions, i.e., the functions
that differ by a small Hamming distance from the PW functions in terms
of truth table representation. We exploit the idempotent structure of
the PW functions and interpret them as Rotation Symmetric Boolean
Functions (RSBFs). We present techniques to modify these RSBFs to
introduce zeros in the Walsh spectra of the modified functions with
minimum reduction in nonlinearity. Our technique demonstrates
15-variable balanced and $1$-resilient functions with currently best
known nonlinearities 16272 and 16264 respectively. In the process, we
find functions for which the autocorrelation spectra and algebraic
immunity parameters are best known till date.
We describe the use of explicit isogenies
to reduce Discrete Logarithm Problems (DLPs)
on Jacobians of hyperelliptic genus~$3$ curves
to Jacobians of non-hyperelliptic genus~$3$ curves,
which are vulnerable to faster index calculus attacks.
We provide algorithms which compute an isogeny
with kernel isomorphic to $(\mathbb{Z}/2\mathbb{Z})^3$
for any hyperelliptic genus~$3$ curve.
These algorithms provide a rational isogeny
for a positive fraction of all hyperelliptic genus~$3$ curves
defined over a finite field of characteristic $p > 3$.
Subject to reasonable assumptions,
our algorithms provide an explicit and efficient
reduction from hyperelliptic DLPs to non-hyperelliptic DLPs
for around $18.57\%$ of all hyperelliptic genus~$3$ curves
over a given finite field.
In this paper we provide explicit formulae to
compute bilinear pairings in compressed form, and indicate families of
curves where particularly generalised versions of the Eta and Ate
pairings due to Zhao \emph{et al.} are especially efficient.
With the new formulae it is possible to entirely avoid $\F_{p^k}$
arithmetic during pairing computation on elliptic curves over $\F_p$
with even embedding degree $k$. Using our new method all intermediate
results in the Miller loop are represented by just one $\F_{p^{k/2}}$
element and manipulated in compressed form. For certain families of
ordinary curves with embedding degree $k = 6m$ all arithmetic can be
done in a subfield of size $p^m$ and the representation can be further
compressed to two $\F_{p^m}$ elements.
We show that the LASH-$x$ hash function is vulnerable to attacks
that trade time for memory, including collision attacks as
fast as $2^{\frac{4}{11}x}$ and preimage attacks as fast as $2^{\frac47x}$.
Moreover, we describe heuristic lattice based collision attacks that
use small memory but require very long messages.
Based upon experiments, the lattice attacks are expected to find
collisions much faster than $2^{x/2}$.
All of these attacks exploit the designers' choice of an all zero IV.
We then consider whether LASH can be patched simply by changing the IV. In this case, we show that LASH is vulnerable to a $2^{\frac78x}$ preimage attack. We also show that LASH is trivially not a PRF when any subset of input bytes is used as a secret key. None of our attacks depend upon the particular contents of the LASH matrix -- we only assume that the distribution of elements is more or less uniform. Additionally, we show a generalized birthday attack on the final compression of LASH which requires $O\left(x2^{\frac{x}{2(1+\frac{107}{105})}}\right) \approx O(x2^{x/4})$ time and memory. Our method extends the Wagner algorithm to truncated sums, as is done in the final transform in LASH.
Abstract. There are some well-known conceptional
and technical issues related to a common setting of simulation
paradigm, i.e., EPT (expected polynomial time) simulator versus SPT
(strict polynomial time) adversary. In fact, it has been shown that
this setting is essential for achieving constant-round black-box
zero-knowledge protocols. Many suggestions and results have been
proposed to deal with these issues. In this paper, we propose an
alternative solution. We study a new class of machines, MPT (Markov
polynomial time), which is a cryptographic adaption of Levin's average
polynomial-time. Since MPT has good compatibility to SPT and intuitive
composition properties, we can use it as a drop-in replacement of SPT.
Moreover, it is easy to construct simulators in MPT.
Trapdoors for Hard Lattices and New Cryptographic Constructions
(Craig Gentry and Chris Peikert and Vinod Vaikuntanathan)
We show how to construct a variety of ``trapdoor'' cryptographic tools
assuming the worst-case hardness of standard lattice problems (such as
approximating the shortest nonzero vector to within small factors).
The applications include trapdoor functions with \emph{preimage
sampling}, simple and efficient ``hash-and-sign'' digital signature
schemes, universally composable oblivious transfer, and identity-based
encryption.
A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a Gaussian-like probability distribution whose standard deviation is essentially the length of the longest vector in the basis. In particular, the crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.
Proof-of-work schemes are economic measures to
deter denial-of-service attacks: service requesters compute moderately
hard functions that are easy to check by the provider. We present such
a new scheme for solution-verification protocols. Although most schemes
to date are probabilistic unbounded iterative processes with high
variance of the requester effort, our Merkle tree scheme is
deterministic, with an almost constant effort and null variance, and is
computation-optimal.
For AES 128 security level there are several natural choices for
pairing-friendly elliptic curves. In particular, as we will explain,
one might choose curves with $k=9$ or curves with $k=12$. The case
$k=9$ has not been studied in the literature, and so it is not clear
how efficiently pairings can be computed in that case. In this
paper, we present efficient methods for the $k=9$ case, including
generation of elliptic curves with the shorter Miller loop, the
denominator elimination and speed up of the final exponentiation.
Then we compare the performance of these choices. From the analysis, we conclude
that for pairing-based cryptography at the AES 128 security level,
the Barreto-Naehrig curves are the most efficient choice, and the
performance of the case $k=9$ is comparable to the Barreto-Naehrig
curves.
Irreducibility to the One-More Evaluation Problems: More May Be Less (Daniel R. L. Brown)
For a random-self-reducible function, the evaluation problem is
irreducible to the one-more evaluation problem, in the following
sense. An irreduction algorithm exists that, given a reduction
algorithm from the evaluation to the one-more evaluation problem,
solves a separator problem: the evaluation problem itself. Another
irreduction shows that if the computational Diffie-Hellman problem
is reduced to the gap Diffie-Hellman problem, then the decision
Diffie-Hellman problem is easy. Irreductions are primarily of
theoretical interest, because they do not actually prove
inequivalence between problems. What these irreductions suggest,
though, is that one-more variants of the RSA and discrete logarithm
problems may be easier than the standard variants, and that the gap
Diffie-Hellman problem may be easier than the standard
Diffie-Hellman problem.
The stream ciphers Py, Pypy and Py6 were designed by Biham and Seberry for the
ECRYPT-eSTREAM project in 2005. The ciphers were promoted to the `Focus' ciphers of the
Phase II of the eSTREAM project. However, due to some cryptanalytic results on the
ciphers, strengthened versions of the ciphers, namely TPy, TPypy and TPy6 were built. So
far there exists no attacks on TPy6. In this paper, we find hitherto unknown weaknesses in
the keystream generation algorithms of the Py6 and of its stronger variant TPy6. Exploiting
these weaknesses, a large number of distinguishing attacks are mounted on the ciphers, the
best of which works with $2^{224.6}$ data and comparable time. In the second part, we present two new
ciphers derived from the TPy6, namely TPy6-A and TPy6-B, whose performances are 2.65
cycles/byte and 4.4 cycles/byte on Pentium III. As a result, to the best of our knowledge,
on Pentium platforms TPy6-A becomes the fastest stream cipher in the literature. Based on our security analysis,
we conjecture that no attacks better than brute force are possible on the ciphers TPy6-A and
TPy6-B.
Reconfigurable Hardware Implementations of Tweakable Enciphering Schemes
(Cuauhtemoc Mancillas-Lopez and Debrup Chakraborty and Francisco Rodriguez-Henriquez)
Tweakable enciphering schemes are length preserving block cipher
modes of operation that provide a strong pseudo-random permutation.
It has been suggested that these schemes can be used as the main
building blocks for achieving in-place disk encryption. In the past
few years there has been an intense research activity towards
constructing secure and efficient tweakable enciphering schemes.
But, actual experimental performance data of these newly proposed
schemes are yet to be reported. Accordingly, in this paper we
present optimized FPGA implementations of five tweakable enciphering
schemes, namely, HCH, HCTR, XCB, EME and TET, using a 128-bit AES
core as the underlying block cipher. We report performance timings
of these modes when using both, pipelined and sequential AES
structures. The universal polynomial hash function included in the
specification of HCH, HCHfp (a variant of HCH), HCTR, XCB and TET,
was implemented using a Karatsuba-Ofman multiplier as the main
building block. We provide detailed analyses of each of the schemes
and their experimental performances achieved in various scenarios.
Our experiments show that a sequential AES core is not an attractive
option for the design of these modes as it leads to rather poor
throughputs. In contrast, by using an encryption/decryption
pipelined AES core we get a throughput of 3.67 Gbps for HCTR and by
using a encryption only pipeline AES core we get a throughput of
5.71 Gbps for EME. The performance results reported in this paper
provide experimental evidence that hardware implementations of
tweakable enciphering schemes can actually match and even outperform
the data rates achieved by state-of-the-technology disk controllers,
thus showing that they might be used for achieving provably secure
in-place hard disk encryption.
Abstract.
We show how to implement secure oblivious transfer (OT) based on the realistic assumption that quantum storage of photonic qubits is noisy. We thereby consider collective storage attacks, i.e., the dishonest party attempts to store each incoming qubit separately. Our model is similar to the model of bounded-quantum storage, however, we consider an explicit noise model inspired by present day technology. If the honest parties can perform perfect quantum operations, then we show that the protocol is secure for any amount of noise. In case the honest participants are only able to perform noisy operations themselves, we analyze a practical protocol that can be implemented with qubits encoded in the polarization or phase of weak laser pulses. We show how to derive explicit tradeoffs between the amount of storage noise, the amount of noise in the operations performed by the honest participants and the security of the protocol. Our analysis easily carries over to quantum protocols for secure identification. Secure Fractal Image Coding (Shiguo Lian)
Abstract.
In recent work, various fractal image coding methods are reported, which adopt the self-similarity of images to compress the size of images. However, till now, no solutions for the security of fractal encoded images have been provided. In this paper, a secure fractal image coding scheme is proposed and evaluated, which encrypts some of the fractal parameters during fractal encoding, and thus, produces the encrypted and encoded image. The encrypted image can only be recovered by the correct key. To keep secure and efficient, only the suitable parameters are selected and encrypted through in-vestigating the properties of various fractal parameters, including parameter space, parameter distribu-tion and parameter sensitivity. The encryption process does not change the file format, keeps secure in perception, and costs little time or computational resources. These properties make it suitable for secure image encoding or transmission. The one-way function based on computational uncertainty principle (P.F. Wang, J.P. Li)
Abstract.
This paper presents how to make use of the advantage of round-off error effect in some research areas. The float-point operation complies with the reproduce theorem without the external random perturbation. The computation uncertainty principle and the high nonlinear of chaotic system guarantee the numerical error is random and departure from the analytical result. Combining these two properties we can produce unilateral one-way function and provide a case of utilizing this function to construct encryption algorithm. The multiple-precision (MP) library is used to analyze nonlinear dynamics systems and achieve the code. As an example, we provide a scheme of encrypting a plaintext by employing the one-way function with Lorenz system. Since the numerical solution used in this scheme is beyond the maximum effective computation time (MECT) and it cannot satisfy the requirements of return-map analysis and phase space reconstruction, it can block some existing attacks. Braid Group Cryptography (David Garber) Abstract.
In the last decade, a number of public key cryptosystems based on
combinatorial group theoretic problems in braid groups have been proposed. Our
tutorial is aimed at presenting these cryptosystems and some known attacks on
them. We start with some basic facts on braid groups and on the Garside normal
form of its elements. We then present some known algorithms for solving the
word problem in the braid group. After that, we present the major public-key
cryptosystems based on the braid group. We then discuss some of the known
attacks on these cryptosystems. We finish with a discussion of future
directions.
Note: some publications could be referring to a previous date.
This happens because the submitted papers, in some websites, are
published days later its receipt.
Powered by a Zone-H(ified) version of AkoComment 3.0! DISCLAIMER: Forum postings are the opinion of the posting author alone, and should not be taken as the opinion of Fermath.info staff. The author is entirely and solely responsible for all content that he/she uploads, posts, or otherwise transmits via the website. Fermath.info staff is not responsible for such content. However, Fermath.info staff shall have the right, but not the obligation, to delete, move, or edit any content that violates this agreement or is otherwise objectionable as determined by Fermath.info staff in its sole discretion and without notice. |
||||
| < Prev | Next > |
|---|
