Linearly Homomorphic Signatures over Binary Fields and New
Tools for Lattice-Based Signatures
Dan Boneh, David Mandell Freeman
We propose a linearly homomorphic signature scheme that authenticates
vector subspaces of a given ambient space. Our system has several
novel properties not found in previous proposals:
- It is the first such scheme that authenticates vectors defined over
binary fields; previous proposals could only authenticate
vectors with large or growing coefficients.
- It is the first such scheme based on the problem of
finding short
vectors in integer lattices, and thus enjoys the worst-case
security guarantees common to lattice-based cryptosystems.
Our scheme can be used to authenticate linear transformations of
signed data, such as those arising when computing mean and Fourier
transform or in networks that use network coding. Our construction
gives an example of a cryptographic primitive --- homomorphic
signatures over $\mathbb{F}_2$ --- that can be built using lattice
methods, but cannot currently be built using bilinear maps or other
traditional algebraic methods based on factoring or discrete-log type
problems.
Security of our scheme (in the random oracle model) is based on a
new hard problem on lattices, called k-SIS, that reduces to standard
average-case and worst-case lattice problems. Our formulation of the
k-SIS problem adds to the "toolbox" of lattice-based cryptography
and may be useful in constructing other lattice-based cryptosystems.
As a second application of the new k-SIS tool, we construct an
ordinary signature scheme and prove it k-time unforgeable in the
standard model assuming the hardness of the k-SIS problem. Our
construction can be viewed as "removing the random oracle"
from the signatures of Gentry, Peikert, and Vaikuntanathan at the
expense of only allowing a small number of signatures.
Homomorphic Network Coding Signatures in the Standard
Model
Nuttapong Attrapadung, Benoit Libert
Network coding is known to provide improved resilience to packet loss
and increased throughput. Unlike traditional routing techniques, it
allows network nodes to perform transformations on packets they
receive before transmitting them. For this reason, packets cannot be
authenticated using ordinary digital signatures, which makes it
difficult to hedge against pollution attacks, where malicious nodes
inject bogus packets in the network. To address this problem, recent
works introduced signature schemes allowing to sign linear subspaces
(namely, verification can be made w.r.t. any vector of that subspace)
and which are well-suited to the network coding scenario. Currently
known network coding signatures in the standard model are not
homomorphic in that the signer is forced to sign all vectors of a
given subspace at once. This paper describes the first homomorphic
network coding signatures in the standard model: the security proof
does not use random oracles and, at the same time, the scheme allows
signing individual vectors on-the-fly and has constant
per-packet overhead in terms of signature size. The construction is
based on the dual encryption technique introduced by Waters
(Crypto'09) to prove the security of hierarchical identity-based
encryption schemes.
Efficient Attribute-Based Signatures for Non-Monotone
Predicates in the Standard Model
Tatsuaki Okamoto, Katsuyuki Takashima
This paper presents a fully secure (adaptive-predicate unforgeable and
private) attribute-based signature (ABS) scheme in the standard
model. The security of the proposed ABS scheme is proven under
standard assumptions, the decisional linear (DLIN) assumption and the
existence of collision resistance (CR) hash functions. The admissible
predicates of the proposed ABS scheme are more general than those of
the existing ABS schemes, i.e., the proposed ABS scheme is the first
to support general non-monotone predicates, which can be expressed
using NOT gates as well as AND, OR, and Threshold gates, while the
existing ABS schemes only support monotone predicates. The proposed
ABS scheme is efficient and practical. Its efficiency is comparable to
(several times worse than) that of the most efficient (almost
optimally efficient) ABS scheme the security for which is proven in
the generic group model.
Ciphertext-Policy Attribute-Based Encryption: An Expressive,
Efficient, and Provably Secure Realization
Brent Waters
We present a new methodology for realizing Ciphertext-Policy Attribute
Encryption (CP-ABE) under concrete and noninteractive cryptographic
assumptions in the standard model. Our solutions allow any encryptor
to specify access control in terms of any access formula over the
attributes in the system. In our most efficient system, ciphertext
size, encryption, and decryption time scales linearly with the
complexity of the access formula. The only previous work to achieve
these parameters was limited to a proof in the generic group model.
We present three constructions within our framework. Our first system
is proven selectively secure under a assumption that we call the
decisional Parallel Bilinear Diffie-Hellman Exponent (PBDHE)
assumption which can be viewed as a generalization of the BDHE
assumption. Our next two constructions provide performance tradeoffs
to achieve provable security respectively under the (weaker)
decisional Bilinear-Diffie-Hellman Exponent and decisional Bilinear
Diffie-Hellman assumptions.
Generic Constructions for Chosen-Ciphertext Secure Attribute
Based Encryption
Shota Yamada, Nuttapong Attrapadung, Goichiro Hanaoka, Noboru
Kunihiro
In this paper we propose generic conversions for transforming a
chosen-plaintext (CPA) secure attribute-based encryption (ABE) to a
chosen-ciphertext (CCA) secure ABE. The only known generic conversion,
to the best of our knowledge, was presented by Goyal et al. in ACM-CCS
2006, which itself subsumes the well-known IBE-to-PKE conversion by
Canetti, Halevi, and Katz proposed in Eurocrypt 2004. The method by
Goyal et al. has some restrictions that it assumes the delegatability
of the original ABE and can deal only with the key-policy type of ABE
with large attribute universe. In contrast, our methodology is
applicable also to those ABE schemes without known delegatability.
Furthermore, it works for both key-policy or ciphertext-policy flavors
of ABE and can deal with both small and large universe scheme. More
precisely, our method assumes only either delegatability or a newly
introduced property called verifiability of ABE. We then exhaustively
check the verifiability of existing ABE schemes and found that most of
them satisfy such a property, hence CCA-secure versions of these
schemes can be obtained automatically.
Expressive Key-Policy Attribute-Based Encryption with
Constant-Size Ciphertexts
Nuttapong Attrapadung, Benoit Libert, Elie de Panafieu
Attribute-based encryption (ABE), as introduced by Sahai and Waters,
allows for fine-grained access control on encrypted data. In its
key-policy flavor, the primitive enables senders to encrypt messages
under a set of attributes and private keys are associated with access
structures that specify which ciphertexts the key holder will be
allowed to decrypt. In most ABE systems, the ciphertext size grows
linearly with the number of ciphertext attributes and the only known
exceptions only support restricted forms of threshold access policies.
This paper proposes the first key-policy attribute-based encryption
(KP-ABE) schemes allowing for non-monotonic access structures
(i.e., that may contain negated attributes) and with constant
ciphertext size. Towards achieving this goal, we first show that a
certain class of identity-based broadcast encryption schemes
generically yields monotonic KP-ABE systems in the selective set
model. We then describe a new efficient identity-based revocation
mechanism that, when combined with a particular instantiation of our
general monotonic construction, gives rise to the first truly
expressive KP-ABE realization with constant-size ciphertexts. The
downside of these new constructions is that private keys have
quadratic size in the number of attributes. On the other hand, they
reduce the number of pairing evaluations to a constant, which appears
to be a unique feature among expressive KP-ABE schemes.
Faster and Lower Memory Scalar Multiplication on Supersingular
Curves in Characteristic Three
Roberto Avanzi, Clemens Heuberger
We describe new algorithms for performing scalar multiplication on
supersingular elliptic curves in characteristic three. These curves
can be used in pairing-based cryptography. Since in pairing-based
protocols besides pairing computations also scalar multiplications are
required, and the performance of the latter is not negligible,
improving it is clearly important as well. The techniques presented
here bring noticeable speed ups (up to 30% for methods using a
variable amount of memory and up to 46.7% for methods with a small,
fixed memory usage), while at the same time bringing substantial
memory reductions -- factors like 3 to 8 are not uncommon.
The starting point for our methods is a structure theorem for unit
groups of residue classes of a quadratic order associated to the
Frobenius endomorphism of the considered curves. This allows us to
define new digit sets whose elements are products of powers of certain
generators of said groups. There are of course several choices for
these generators: we chose generators associated to endomorphisms for
which we could find efficient explicit formulae in a suitable
coordinate system. A multiple-base-like scalar multiplication
algorithm making use of these digits and these formulae brings the
claimed speed up.
On the Correct Use of the Negation Map in the Pollard Rho
Method
Daniel J. Bernstein, Tanja Lange, Peter Schwabe
Bos, Kaihara, Kleinjung, Lenstra, and Montgomery recently showed that
ECDLPs on the 112-bit secp112r1 curve can be solved in an expected
time of 65 years on a PlayStation 3. This paper shows how to solve the
same ECDLPs at almost twice the speed on the same hardware. The
improvement comes primarily from a new variant of Pollard's rho method
that fully exploits the negation map without branching, and
secondarily from improved techniques for modular arithmetic.
Cryptanalysis of the RSA Subgroup Assumption from TCC
2005
Jean-Sebastien Coron, Antoine Joux, Avradip Mandal, David Naccache,
Mehdi Tibouchi
At TCC 2005, Groth underlined the usefulness of working in small RSA
subgroups of hidden order. In assessing the security of the relevant
hard problems, however, the best attack considered for a subgroup of
size $2^{2\ell}$ had a complexity of $\bigO{2^{\ell}}$. Accordingly,
$\ell=100$ bits was suggested as a concrete parameter.
This paper exhibits an attack with a complexity of roughly
$2^{\ell/2}$ operations, suggesting that Groth's original choice of
parameters was overly aggressive. It also discusses the practicality
of this new attack and various implementation issues.
(If) Size Matters: Size-Hiding Private Set Intersection
Giuseppe Ateniese, Emiliano De Cristofaro, Gene Tsudik
Modern society is increasingly dependent on, and fearful of, the
availability of electronic information. There are numerous examples of
situations where sensitive data must be -- sometimes reluctantly --
shared between two or more entities without mutual trust. As often
happens, the research community has foreseen the need for mechanisms
to enable limited (privacy-preserving) sharing of sensitive
information and a number of effective solutions have been
proposed. Among them, Private Set Intersection (PSI) techniques are
particularly appealing for scenarios where two parties wish to compute
an intersection of their respective sets of items without revealing to
each other
any other information. Thus far, "any other
information" has been interpreted to mean any information about items
not in the intersection.
In this paper, we motivate the need for Private Set Intersection
with a stronger privacy property of {\em hiding the size} of the set
held by one of the two entities ("client"). We introduce
the notion of Size-Hiding Private Set Intersection (SHI-PSI) and
propose an efficient construction secure under the RSA assumption in
the Random Oracle Model. We also show that input size-hiding is
attainable at very low additional cost.
Sub-Linear, Secure Comparison With Two Non-Colluding
Parties
Tomas Toft
The classic problem in the field of secure computation is Yao's
millionaires' problem; we consider two new protocols solving a
variation of this: a number of parties, $P_1,\ldots, P_n$, securely
hold two $\ell$-bit values, $x$ and $y$ -- e.g.~$x$ and $y$ could be
encrypted or secret shared. They wish to obtain a bit stating whether
$x$ is greater than $y$ using only secure arithmetic; this should be
done without revealing any information, even the output should remain
secret. The present setting is special in the sense that it is assumed
that two specific parties, referred to as Alice and Bob, are
non-colluding. Though this assumption is not satisfied in general, it
clearly is for the main example of this work: two-party computation
based on Paillier encryption.
The first solution requires
$\bigo(\log(\ell)(\kappa+\loglog(\ell)))$ secure arithmetic operations
in $\bigo(\log(\ell))$ rounds, where $\kappa$ is a correctness
parameter. The second solution requires only a constant number of
rounds, but increases complexity to $\bigo(\sqrt{\ell}(\kappa
+\log(\ell)))$ arithmetic operations.
For the motivating setting, each arithmetic operation requires a
constant number of Paillier encryptions to be exchanged between Alice
and Bob. This implies that both solutions require only a
sub-linear number of invocations (in the bit-length, $\ell$) of
the cryptographic primitives. This does not imply sub-linear
communication, though, as the size of each encryption transmitted is
more than $\ell$ bits.
Oblivious Transfer with Hidden Access Control Lists
Jan Camenisch, Maria Dubovitskaya, Gregory Neven, Gregory Zaverucha
Consider a database where each record has different access control
policies. These policies could be attributes, roles, or rights that
the user needs to have in order to access the record. Here we provide
a protocol that allows the users to access the database record while:
(1) the database does not learn who queries a record;
(2) the database does not learn which record is being queried, nor the
access control policy of that record;
(3) the database does not learn whether a user's attempt to access a
record was successful or not;
(4) the user can only obtain a single record per query;
(5) the user can only access those records for which she has the
correct permissions;
(6) the user does not learn any other information about the database
structure and the access control policies other than whether he was
granted access to the queried record, and if so, the content of the
record; and
(7) the users' credentials can be revoked.
Our scheme builds on the one by Camenisch, Dubovitskaya and Neven (CCS'09),
who consider oblivious transfer with access control when the access control
policies are public.
Chosen Ciphertext Secure Encryption under Factoring Assumption
Revisited
Qixiang Mei, Bao Li, Xianhui Lu, Dingding Jia
In Eurocrypt 2009, Hofheinz and Kiltz proposed a practical chosen
ciphertext (CCA) secure public key encryption under factoring
assumption based on Rabin trapdoor one-way
permutation.
We show that when the modulus is special such that $Z_N^*$ has
semi-smooth order, the instantiation of Hofheinz-Kiltz 09 scheme
(HK09) over a much smaller subgroup of quadratic residue group
(Semi-smooth Subgroup) is CCA secure as long as this type of modulus
is hard to be factored. Since the exponent domain of this
instantiation is much smaller than the original one, the efficiency is
substantially improved.
In addition, we show how to construct a practical CCA secure
encryption scheme from ElGamal trapdoor one-way function under
factoring assumption. When instantiated over Semi-smooth Subgroup,
this scheme has even better decryption efficiency than HK09
instantiation.
Chameleon All-But-One TDFs and Their Application to
Chosen-Ciphertext Security
Junzuo Lai, Robert H. Deng, Shengli Liu
In STOC'08, Peikert and Waters introduced a new powerful primitive
called lossy trapdoor functions (LTDFs) and a richer abstraction
called all-but-one trapdoor functions (ABO-TDFs). They also presented
a black-box construction of CCA-secure PKE from an LTDF and an
ABO-TDF. An important component of their construction is the use of a
strongly unforgeable one-time signature scheme for CCA-security.
In this paper, we introduce the notion of chameleon ABO-TDFs, which
is a special kind of ABO-TDFs. We give a generic as well as a concrete
construction of chameleon ABO-TDFs. Based on an LTDF and a chameleon
ABO-TDF, we presented a black-box construction, free of one-time
signature, of variant of the CCA secure PKE proposed by Peikert and
Waters.
Parallel Decryption Queries in Bounded Chosen Ciphertext
Attacks
Takahiro Matsuda, Kanta Matsuura
Whether it is possible to construct a chosen ciphertext secure (CCA
secure) public key encryption (PKE) scheme only from a chosen
plaintext secure (CPA secure) one is a fundamental open problem, and
the best known positive results regarding this problem are the
constructions of so-called bounded CCA secure schemes. Since we
can achieve the best possible security in the bounded CCA security
notions, in order to further tackle the problem, we would need other
new security notions that capture intermediate security notions that
lie between CPA and CCA security. Motivated by this situation, we
focus on "parallel" decryption queries (originally introduced
by Bellare and Sahai) for the extension of bounded CCA security, and
introduce a new security notion which we call mixed CCA
security. It captures security against adversaries that make single
and parallel decryption queries in a predetermined order, where each
parallel query can contain unboundedly many
ciphertexts. Moreover, how the decryption oracle is available before
and after the challenge is also taken into account in this new
security definition, which enables us to capture existing major
security notions that lie between CPA and CCA security in a unified
security notion. We investigate the relations among mixed CCA security
notions, and show a necessary and sufficient condition of
implications/separations between any two notions in mixed CCA
security. We also show two black-box constructions of PKE schemes with
improved security only using CPA secure schemes as building blocks.
Secure Blind Decryption
Matthew Green
In this work we construct public key encryption schemes that admit a
protocol for blindly decrypting ciphertexts. In a blind decryption
protocol, a user with a ciphertext interacts with a secret keyholder
such that the user obtains the decryption of the ciphertext and the
keyholder learns nothing about what it decrypted. While we are not the
first to consider this problem, previous works provided only weak
security guarantees against malicious users. We provide, to our
knowledge, the first practical blind decryption schemes that are
secure under a strong CCA security definition. We prove our
construction secure in the standard model under simple, well-studied
assumptions in bilinear groups. To motivate the usefulness of this
primitive we discuss several applications including distributed
privacy-preserving file systems and Oblivious Transfer schemes that
admit public contribution.
New Developments in Leakage-Resilient Cryptography
Vinod Vaikuntanathan
Much of modern cryptography is predicated on the assumption that users
have secrets which are generated using perfect randomness, and kept
perfectly secret from an attacker. The attacker is then constrained to
black-box (input/output) access to the user's program. In reality,
neither assumption holds, as evidenced by numerous side-channel
attacks that have surfaced over the last few decades.
This leads naturally to the question -- is it possible to secure
cryptography against general types of information leakage at a
fundamental, algorithmic level (as opposed to, say, solutions for
specific attacks)? This is the goal of leakage-resilient cryptography.
In this talk, we will survey recent developments in
leakage-resilient cryptography, including definitions and
constructions of various cryptographic primitives secure against
general forms of leakage. We will place particular emphasis on the new
tools and techniques that we have developed to handle information
leakage, as well as the relation between leakage-resilience and other
questions in cryptography.
On the Security of a Bidirectional Proxy Re-Encryption Scheme
from PKC 2010
Jian Weng, Yunlei Zhao, Goichiro Hanaoka
In ACM CCS 2007, Canetti and Hohenberger left an interesting open
problem of how to construct a chosen-ciphertext secure proxy
re-encryption (PRE) scheme without bilinear maps. This is a rather
interesting problem and has attracted great interest in recent
years. In PKC 2010, Matsuda, Nishimaki and Tanaka introduced a novel
primitive named re-applicable lossy trapdoor function, and then used
it to construct a PRE scheme without bilinear maps. Their scheme is
claimed to be chosen-ciphertext secure in the standard model. In this
paper, we make a careful observation on their PRE scheme, and indicate
that their scheme does not satisfy chosen-ciphertext security. The
purpose of this paper is to clarify the fact that, it is still an open
problem to come up with a chosen-ciphertext secure PRE scheme without
bilinear maps in the standard model.
Fully Secure Accountable-Authority Identity-Based
Encryption
Amit Sahai, Hakan Seyalioglu
The problem of trust is one of the biggest concerns in any
identity-based infrastructure where the key-generation authority
(called the PKG) must choose secret keys for participants and
therefore be highly trusted by all parties. While some abilities of
the PKG are intrinsic to this setting, reducing this trust as much as
possible is beneficial to both user and authority as the less trust is
placed in it, the less an honest authority can be accused of abusing
that trust. Goyal (CRYPTO 2007) defined the notion of
Accountable-Authority IBE in which a dishonest PKG who had leaked a
user's private key could be proven guilty. Later, Goyal et al. (CCS
2008) asked whether it would be possible to implicate a PKG who
produced an unauthorized decoder box, enabling decryption with a
noticeable probability but which may not actually grant access to a
well-formed key. Formally, would it be possible for a tracing
algorithm to implicate a dishonest PKG given only black-box access to
such a decoder? Goyal et al. could only provide such a scheme in the
weaker setting of selective security, where an adversary must declare
at the start of the game which identity it intends to target. In this
work, we provide the first fully secure accountable-authority IBE
scheme. We prove security from the standard DBDH assumption while
losing none of the functionality or security of the original proposal.
One-Pass HMQV and Asymmetric Key-Wrapping
Shai Halevi and Hugo Krawczyk
Consider the task of asymmetric key-wrapping, where a key-management
server encrypts a cryptographic key under the public key of a
client. When used in storage and access-control systems, it is often
the case that the server has no knowledge about the client (beyond its
public key) and no means of coordinating with it. For example, a
wrapped key used to encrypt a backup tape may be needed many years
after wrapping, when the server is no longer available, key-wrapping
standards have changed, and even the security requirements of the
client might have changed. Hence we need a flexible mechanism that
seamlessly supports different options depending on what the original
server was using and the current standards and requirements.
We show that one-pass HMQV (which we call HOMQV) is a perfect fit
for this type of applications in terms of security, efficiency and
flexibility. It offers server authentication if the server has its own
public key, and degenerates down to the standardized DHIES encryption
scheme if the server does not have a public key. The performance
difference between the unauthenticated DHIES and the authenticated
HOMQV is very minimal (essentially for free for the server and only
1/2 exponentiation for the client). We provide a formal analysis of
the protocol's security showing many desirable properties such as
sender's forward-secrecy and resilience to compromise of ephemeral
data. When adding a DEM part (as needed for key-wrapping) it yields a
secure signcryption scheme (equivalently a UC-secure messaging
protocol).
The combination of security, flexibility, and efficiency, makes
HOMQV a very desirable protocol for asymmetric key wrapping, one that
we believe should be incorporated into implementations and standards.
Linear Recurring Sequences for the UOV Key Generation
Albrecht Petzoldt, Stanislav Bulygin, Johannes Buchmann
Multivariate public key cryptography is one of the main approaches to
guarantee the security of communication in the post-quantum world. Due
to its high efficiency and modest computational requirements,
multivariate cryptography seems especially appropriate for signature
schemes on low cost devices. However, multivariate schemes are not
much used yet, mainly because of the large size of their public
keys. In [PB10] Petzoldt et al. presented an idea how to create a
multivariate signature scheme with a partially cyclic public key based
on the UOV scheme of Kipnis and Patarin [KP99]. In this paper we
use their idea to create a multivariate signature scheme whose public
key is mainly given by a linear recurring sequence (LRS). By doing so,
we are able to reduce the size of the public key by up to
86%. Moreover, we get a public key with good statistical properties.
On the Impossibility of Instantiating PSS in the Standard
Model
Rishiraj Bhattacharyya, Avradip Mandal
In this paper we consider the problem of securely instantiating
Probabilistic Signature Scheme (PSS) in the standard model. PSS,
proposed by Bellare and Rogaway [BellareR96] is a widely deployed
randomized signature scheme, provably secure (
unforgeable under
adaptively chosen message attacks) in Random Oracle Model.
Our main result is a black-box impossibility result showing that
one can not prove unforgeability of PSS against chosen message attacks
using blackbox techniques even assuming existence of ideal trapdoor
permutations (a strong abstraction of trapdoor permutations which
inherits all security properties of a random permutation, introduced
by Kiltz and Pietrzak in Eurocrypt 2009) or the recently proposed
lossy trapdoor permutations [PeikertW08]. Moreover, we show
onewayness, the most common security property of a trapdoor
permutation does not suffice to prove even the weakest security
criteria, namely unforgeability under zero message attack. Our
negative results can easily be extended to any randomized signature
scheme where one can recover the random string from a valid signature.
On-line Non-Transferable Signatures Revisited
Jacob C.N. Schuldt, Kanta Matsuura
Undeniable signatures, introduced by Chaum and van Antwerpen, and
designated confirmer signatures, introduced by Chaum, allow a signer
to control the verifiability of his signatures by requiring a verifier
to interact with the signer to verify a signature. An important
security requirement for these types of signature schemes is
non-transferability which informally guarantees that even
though a verifier has confirmed the validity of a signature by
interacting with the signer, he cannot prove this knowledge to a third
party. Recently Liskov and Micali pointed out that the commonly used
notion of non-transferability only guarantees security against an
off-line attacker which cannot influence the verifier while he
interacts with the signer, and that almost all previous schemes
relying on interactive protocols are vulnerable to on-line attacks. To
address this, Liskov and Micali formalized on-line non-transferable
signatures which are resistant to on-line attacks, and proposed a
generic construction based on a standard signature scheme and an
encryption scheme.
In this paper, we revisit on-line non-transferable signatures.
Firstly, we extend the security model of Liskov and Micali to cover
not only the sign protocol, but also the confirm and disavow protocols
executed by the confirmer. Our security model furthermore considers
the use of multiple (potentially corrupted or malicious) confirmers,
and guarantees security against attacks related to the use of signer
specific confirmer keys. We then present a new approach to the
construction of on-line non-transferable signatures, and propose a new
concrete construction which is provably secure in the standard
model. Unlike the construction by Liskov and Micali, our construction
does not require the signer to issue "fake" signatures to maintain
security, and allows the confirmer to both confirm and disavow
signatures. Lastly, our construction provides noticeably shorter
signatures than the construction by Liskov and Micali.
Round-Efficient Sub-Linear Zero-Knowledge Arguments for Linear
Algebra
Jae Hong Seo
The round complexity of interactive zero-knowledge arguments is an
important measure along with communication and computational
complexities. In the case of zero-knowledge arguments for linear
algebraic relations over finite fields, Groth proposed (at CRYPTO
2009) an elegant methodology that achieves sub-linear communication
overheads and low computational complexity. He obtained zero-knowledge
arguments of sub-linear size for linear algebra using reductions from
linear algebraic relations to equations of the form $z=\x*'\y$, where
$\x$, $\y\in\Fp^n$ are committed vectors, $z\in\Fp$ is a committed
element, and $*':\Fp^n\times\Fp^n\rightarrow\Fp$ is a bilinear
map. These reductions impose additional rounds on zero-knowledge
arguments of sub-linear size. We focus on minimizing such additional
rounds, and we reduce the rounds of sub-linear zero-knowledge
arguments for linear algebraic relations as compared with Groth's
zero-knowledge arguments for the same relations. To reduce round
complexity, we propose a general transformation from a $t$-round
zero-knowledge argument, satisfying mild conditions, to a
$(t-2)$-round zero-knowledge argument; this transformation is of
independent interest.
Signatures on Randomizable Ciphertexts
Olivier Blazy, Georg Fuchsbauer, David Pointcheval, Damien Vergnaud
Randomizable encryption allows anyone to transform a ciphertext into a
fresh ciphertext of the same message. Analogously, a randomizable
signature can be transformed into a new signature on the same message.
We combine randomizable encryption and signatures to a new primitive
as follows: given a signature on a ciphertext, anyone, knowing neither
the signing key nor the encrypted message, can randomize the
ciphertext and
adapt the signature to the fresh encryption,
thus maintaining public verifiability. Moreover, given the decryption
key and a signature on a ciphertext, one can compute ("extract") a
signature on the encrypted plaintext. As adapting a signature to a
randomized encryption contradicts the standard notion of
unforgeability, we introduce a weaker notion stating that no adversary
can, after querying signatures on ciphertexts of its choice, output a
signature on an encryption of a
new message. This is reasonable
since, due to extractability, a signature on an encrypted message can
be interpreted as an encrypted signature on the message.
Using Groth-Sahai proofs and Waters signatures, we give several
instantiations of our primitive and prove them secure under classical
assumptions in the standard model and the CRS setting. As an
application, we show how to construct an efficient non-interactive
receipt-free universally verifiable e-voting scheme. In such a scheme
a voter cannot prove what his vote was, which precludes vote
selling. Besides, our primitive also yields an efficient round-optimal
blind signature scheme based on standard assumptions, and namely for
the classical Waters signature.
Revocation for Delegatable Anonymous Credentials
Lan Nguyen, Tolga Acar
This paper introduces and formalizes \emph{homomorphic proofs} that
allow "adding" proofs and proof statements to get a new
proof of the "sum" statement. Additionally, we introduce
a construction of homomorphic proofs, and show an accumulator
scheme with delegatable non-membership proofs (ADNMP) as one of
its applications with provable security. Finally, the proposed
accumulator method extends the BCCKLS scheme [C:BCCKLS09] to create a
new provably secure revocable delegatable anonymous credential
(RDAC) system. Intuitively, the new accumulator's delegatable
non-membership (NM) proofs enable user A, without revealing her
identity, to delegate to user B the ability to prove that A's identity
is not included in a blacklist that can later be updated. The
delegation is redelegatable, unlinkable, and verifiable.
Cryptanalysis of Multivariate and Odd-Characteristic HFE
Variants
Luk Bettale, Jean-Charles Faugre, Ludovic Perret
We investigate the security of a generalization of HFE (multivariate
and odd-characteristic variants). First, we propose an improved
version of the basic Kipnis-Shamir key recovery attack against
HFE. Second, we generalize the Kipnis-Shamir attack to Multi-HFE. The
attack reduces to solve a MinRank problem directly on the public
key. This leads to an improvement of a factor corresponding to the
square of the degree of the extension field. We used recent results on
MinRank to show that our attack is polynomial in the degree of the
extension field. It appears that multi-HFE is less secure than
original HFE for equal-sized keys. Finally, adaptations of our attack
overcome several variants (i.e. minus modifier and embedding). As a
proof of concept, we have practically broken the most conservative
parameters given by Chen, Chen, Ding, Werner and Yang in 9 days for
256 bits security. All in all, our results give a more precise picture
on the (in)security of several variants of HFE proposed these last
years.
Cryptanalysis of Cryptosystems Based on Non-Commutative Skew
Polynomials
Vivien Dubois, Jean-Gabriel Kammerer
Ten years ago, Ko
et al. described a Diffie-Hellman like protocol
based on decomposition with respect to a non-commutative semigroup
law. Instantiation with braid groups had first been considered, however
intense research on braid groups revealed vulnerabilities of the group
structure and of the braid based DH problem itself.
Recently, Boucher et al. proposed a similar scheme based on
a particular non-commutative multiplication of polynomials over a
finite field. These so called skew polynomials have a well-studied
theory and have many applications in mathematics and coding theory,
however they are quite unknown in a cryptographic application.
In this paper, we show that the Diffie-Hellman problem based on skew
polynomials is susceptible to a very efficient attack. This attack
is in fact general in nature, it uses the availability of a one-sided
notion of gcd and exact division. Given such tools, one can reduce
the Diffie-Hellman problem to a linear algebra type problem.
Practical Cryptanalysis of the Identification Scheme Based on
the Isomorphism of Polynomial with One Secret Problem
Charles Bouillaguet, Jean-Charles Faugre, Pierre-Alain Fouque,
Ludovic Perret
This paper presents a practical cryptanalysis of the Identification
Scheme proposed by Patarin at Crypto 1996. This scheme relies on the
hardness of the Isomorphism of Polynomial with One Secret (IP1S), and
enjoys shorter key than many other schemes based on the hardness of a
combinatorial problem (as opposed to number-theoretic
problems). Patarin proposed concrete parameters that have not been
broken faster than exhaustive search so far. On the theoretical side,
IP1S has been shown to be harder than Graph Isomorphism, which makes
it an interesting target. We present two new deterministic algorithms
to attack the IP1S problem, and we rigorously analyze their complexity
and success probability. We show that they can solve a (big) constant
fraction of all the instances of degree two in polynomial time. We
verified that our algorithms are very efficient in practice. All the
parameters with degree two proposed by Patarin are now broken in a few
seconds. The parameters with degree three can be broken in less than a
CPU-month. The identification scheme is thus quite badly broken.