IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
20 November 2015
Nicolas T. Courtois
Sebastia Martin, Carles Padro, An Yang
Ciaran Mullan, Boaz Tsaban
field with $q$ elements.
Modulo a well supported number theoretic hypothesis, which holds in particular for concrete
homomorphisms proposed thus far, we provide a worst case to average case reduction for these hash functions:
upto a logarithmic factor, a random homomorphism is as secure as _any_ concrete homomorphism.
For a family of homomorphisms containing several concrete proposals in the literature,
we prove that collisions of length O(log(q)) can be found in running time O(sqrt(q)).
For general homomorphisms we offer an algorithm that, heuristically and according to experiments,
in running time O(sqrt(q)) finds collisions of length O(log(q)) for q even, and length O(log^2(q)/loglog(q))$ for arbitrary q.
While exponetial time, our algorithms are faster in practice than all earlier generic algorithms,
and produce much shorter collisions.
Fabrice Benhamouda, Javier Herranz, Marc Joye, and Benoît Libert
This paper revisits the original Goldwasser-Micali cryptosystem using 2^k-th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for k >= 2 (the case k = 1 corresponds exactly to the Goldwasser-Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular, they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function based thereon.
Koji Nuida
Helger Lipmaa
Ming Li, Yupeng Jiang, Dongdai Lin
Ming Li, Dongdai Lin
The adjacency graph of LFSRs with characteristic polynomial (1+x)^mp(x) are also discussed.
Markku-Juhani O. Saarinen
analysis covering all 57 CAESAR first round candidates and over 210
implementations. We have manually
identified security issues with three candidates, two of which are
more serious, and these ciphers been withdrawn from the competition.
We have developed a testing framework, BRUTUS, to facilitate automatic
detection of simple security lapses and susceptible statistical
structures across all ciphers.
From this testing we have security usage notes on four submissions and
statistical notes on a further four. We highlight that some of the CAESAR
algorithms pose an elevated risk if employed in real-life protocols due
to a class of adaptive chosen plaintext attacks. Although AEADs are often
defined (and are best used) as discrete primitives that authenticate and
transmit only complete messages, in practice these algorithms are
easily implemented in a fashion that outputs observable ciphertext data
when the algorithm has not received all of the (attacker-controlled)
plaintext. For an implementor, this strategy
appears to offer seemingly harmless and compliant storage and latency
advantages. If the algorithm uses the same state for secret
keying information, encryption, and integrity protection, and the
internal mixing permutation is not cryptographically strong, an attacker
can exploit the ciphertext-plaintext feedback loop to reveal secret
state information or even keying material. We conclude that
the main advantages of exhaustive, automated cryptanalysis is that it
acts as a very necessary sanity check for implementations and gives the
cryptanalyst insights that can be used to focus more specific attack
methods on given candidates.
Mihir Bellare, Viet Tung Hoang
Srinivas Devadas, Marten van Dijk, Christopher W. Fletcher, Ling Ren, Elaine Shi, Daniel Wichs
semi-honest setting).
Yongge Wang
Trinabh Gupta, Natacha Crooks, Whitney Mulhern, Srinath Setty, Lorenzo Alvisi, Michael Walfish
Sunoo Park, Krzysztof Pietrzak, Albert Kwon, Joël Alwen, Georg Fuchsbauer, Peter Gazi
ledger similar to that of Bitcoin, but where the wasteful proofs of
work are replaced by efficient \\emph{proofs of space}, recently introduced by
Dziembowski et al. Instead of requiring that a majority of the network\'s
computing power is controlled by honest miners (as in Bitcoin), our
currency requires that honest miners dedicate more net disk space than a
potential adversary.
In Spacemint, once a miner has dedicated and initialized some space,
participating in the mining process is very cheap. A new block is
added to the chain every fixed period of time, and in every period a
miner just has to make a small number of lookups to the stored space
to check if she ``wins\", and thus can efficiently add the next block
to the chain and get the mining reward. In this paper, we detail the
construction of Spacemint, analyze its security and
game-theoretic properties, and study its performance.
Our prototype shows that it takes approximately 25 seconds to prove
over a terabyte of space, and it takes a fraction of a second to verify the proof.
Shweta Agrawal, Benoit Libert, Damien Stehle
secret key can be used to derive sub-keys $SK_F$ associated with
certain functions $F$ in such a way that the decryption operation
reveals $F(M)$, if $M$ is the encrypted message, and nothing
else. Recently, \\mbox{Abdalla} {\\it et al.} gave simple and
efficient realizations of the primitive for the computation of
linear functions on encrypted data: given an encryption of a vector
$\\vec{y}$ over some specified base ring, a secret key $SK_{\\vec{x}}$ for the vector $\\vec{x}$ allows computing $\\langle \\vec{x} ,\\vec{y} \\rangle$. Their technique surprisingly allows for instantiations under standard assumptions, like the hardness of the Decision Diffie-Hellman (DDH) and Learning-with-Errors (LWE) problems. Their constructions, however, are only proved secure against selective adversaries, which have to declare the challenge messages $M_0$ and $M_1$ at the outset of the game.
In this paper, we provide constructions that provably achieve security
against more realistic {\\it adaptive} attacks (where the messages
$M_0$ and $M_1$ may be chosen in the challenge phase, based on the
previously collected information) for the same inner product functionality. Our constructions are obtained from hash proof systems endowed with homomorphic properties over the key space. They are (almost) as efficient as those of Abdalla {\\it et al.} and rely on the same hardness assumptions.
In addition, we obtain a solution based on Paillier\'s composite
residuosity assumption, which was an open problem even in the case
of selective adversaries. We also propose $\\LWE$-based schemes that
allow evaluation of inner products modulo a prime~$p$, as opposed to
the schemes of Abdalla {\\it et al.} that are restricted to evaluations of integer inner products of short integer vectors. We finally propose a solution based on Paillier\'s composite residuosity
assumption that enables evaluation of inner products modulo an RSA integer $N = pq$.
We demonstrate that the functionality of inner products over a prime field is very powerful and can be used to construct bounded collusion FE for all circuits.
Ivan Damg{\\aa}rd, Jesper Buus Nielsen, Rafail Ostovsky, Adi Rosen
Next, we consider round complexity. It is a long-standing open problem to determine whether all efficiently computable functions can also be efficiently computed in constant-round with unconditional security. Motivated by this, we consider the question of whether we can compute any function securely, while minimizing the interaction of some of the players? And if so, how many players can this apply to? Note that we still want the standard security guarantees (correctness, privacy, termi- nation) and we consider the standard communication model with secure point-to-point channels. We answer the questions as follows: for passive security, with n = 2t + 1 players and t corruptions, up to t players can have minimal interaction, i.e., they send 1 message in the first round to each of the t + 1 remaining players and receive one message from each of them in the last round. Using our result on message complexity, we show that this is (unconditionally) optimal. For malicious security with n = 3t + 1 players and t corruptions, up to t players can have minimal interaction, and we show that this is also optimal.
Hao Chen
Peng Wang, Yuling Li, Liting Zhang, Kaiyan Zheng
Anamaria Costache, Nigel P. Smart
Markku-Juhani O. Saarinen
cryptosystems have not yet matured to the level that we now expect
from RSA and Elliptic Curve implementations.
Many modern Ring-LWE and other lattice-based public key algorithms
require high precision random sampling from the Discrete Gaussian
distribution. The sampling procedure often represents the biggest
implementation bottleneck due to its memory and computational requirements.
We examine the stated requirements of precision for Gaussian
samplers, where statistical distance to the theoretical distribution is
typically expected to be below $2^{-90}$ or $2^{-128}$ for
90 or 128 ``bit\'\' security level.
We argue that such precision is excessive and give precise
theoretical arguments why half of the precision of the security parameter
is almost always sufficient. This leads to faster and more
compact implementations; almost halving implementation size in both
hardware and software.
We observe that many of the proposed algorithms for discrete Gaussian
sampling may leak significant amounts of secret information in easily
mounted timing attacks. We further offer new recommendations for practical
samplers.