Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:
To receive your credentials via mail again, please click here.
You can also access the full news archive.
In this work, we consider two very natural extensions of secret sharing. In the first, which we call distributed secret sharing, there is no trusted dealer at all, and instead the role of the dealer is distributed amongst the parties themselves. Distributed secret sharing can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing, and may be useful in settings where the secret is so sensitive that no one individual dealer can be trusted with the secret. Our second notion is called functional secret sharing, which incorporates some of the features of functional encryption into secret sharing by providing more fine-grained access to the secret. Qualified subsets of parties do not learn the secret, but instead learn some function applied to the secret, with each set of parties potentially learning a different function.
Our main result is that both of the extensions above are equivalent to several recent cutting-edge primitives. In particular, general-purpose distributed secret sharing is equivalent to witness PRFs, and general-purpose functional secret sharing is equivalent to indistinguishability obfuscation. Thus, our work shows that it is possible to view some of the recent developments in cryptography through a secret sharing lens, yielding new insights about both these cutting-edge primitives and secret sharing.
In this paper, we apply the list decoding method to solve search version of LWE. Our algorithm runs in probabilistic polynomial time and results in specific security estimates for a large range of parameters. To our knowledge, it is the first time to apply the list decoding method to recover the key of LWE.
Our algorithm improves Laine and Lauter\'s result.
the nonce and the authentication tag. These expansions can be problematic
when messages are relatively short and communication cost is high.
This paper studies a form of AE scheme whose ciphertext is only expanded by
nonce, with the help of stateful receiver which also enables detection of replays.
While there is a scheme having this feature, called AERO, proposed by McGrew and Foley,
there is no formal treatment based on the provable security framework.
We propose a provable security framework for such AE schemes, which we call MiniAE, and
show several secure schemes using standard symmetric crypto primitives.
Most notably, one of our schemes
has a similar structure as OCB mode of operation and uses only one blockcipher call
to process one input block, thus the computation cost is comparable to the
nonce-based encryption-only schemes.
Specifically, we consider private-coin argument systems where the answers of the prover can be predicted, given the private randomness of the verifier.
We show that predictable arguments of knowledge (PAoK) can be made extremely laconic, with the prover sending a single bit, and assumed to have only one round (two messages) without loss of generality. We then explore constructs of PAoK. For specific relations we obtain PAoK from Extractable Hash Proof systems (Wee, Crypto \'10); we also show that PAoK are equivalent to Extractable Witness Encryption. Unfortunately, the latter poses serious doubts on the existence of PAoK for all NP. However, we show that for the class of random self-reducible problems in NP we can avoid the problem relying on the assumption of public-coin differing-inputs obfuscation (Ishai et al., TCC \'15).
Finally, we apply PAoK in the context of leakage-tolerant PKE protocols.
At PKC \'13 Nielsen et al. have shown that any leakage-tolerant PKE protocol requires long keys already when it tolerates super-logarithmic leakage.
We strengthen their result proving a more fine-grained lower bound for any constant numbers bits of leakage.
- n-KDM-projection security, an extension of circular security, where the adversary may also ask for encryptions of negated secret key bits;
- a (1-o(1)) resilience rate in the bounded-memory leakage model of Akavia et al. (TCC 2009); and
- Auxiliary-input security against subexponentially-hard functions.
We introduce homomorphic weak pseudorandom functions, a homomorphic version of the weak PRFs proposed by Naor and Reingold (FOCS \'95) and use them to realize our base encryption scheme. We obtain homomorphic weak PRFs under assumptions including subgroup indistinguishability (implied, in particular, by QR and DCR) and homomorphic hash-proof systems (HHPS). As corollaries of our results, we obtain (1) a projection-secure encryption scheme (as well as a scheme with a (1-o(1)) resilience rate) based solely on the HHPS assumption, and (2) a unifying approach explaining the results of Boneh et al (CRYPTO \'08) and Brakerski and Goldwasser (CRYPTO \'10). Finally, by observing that Applebaum\'s KDM amplification method (EUROCRYPT \'11) preserves both types of leakage resilience, we obtain schemes providing at the same time high leakage resilience and KDM security against any fixed polynomial-sized circuit family.
that multiplication in GF$(2^k)$ with a Type 1 optimal normal
basis for can be performed using $k^2-1$ XOR gates irrespective
of the choice of the irreducible polynomial generating the field.
The previous results achieved this bound only with special
irreducible polynomials. Furthermore, the decomposition method
performs the multiplication operation using $1.5k(k-1)$ XOR gates
for Type 2a and 2b optimal normal bases, which matches previous
constructions secure in the idealized random oracle model. Indeed, the best known solution based on simple assumptions requires 2.8 kB per signature for currently recommended parameters. Reducing this size and presenting techniques for shorter signatures are thus natural questions. In this paper, our first contribution is to significantly reduce this overhead. Namely, we obtain the first fully anonymous group signatures based on simple assumptions with signatures shorter than 2 kB at the 128-bit security level. In dynamic (resp. static) groups, our signature length drops to 1.8 kB (resp. 1 kB). This improvement is enabled by two technical tools. As a result of independent interest, we first construct a new structure-preserving signature based on simple assumptions which shortens the best previous scheme by 25%. Our second tool is a new method for attaining anonymity in the strongest sense using a new CCA2-secure encryption scheme which is simultaneously a Groth-Sahai commitment.