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.
We describe a new approach for designing PSI protocols based on permutation-based hashing, which enables to reduce the length of items mapped to bins while ensuring that no collisions occur. We denote this approach as Phasing, for Permutation-based Hashing Set Intersection. Phasing can dramatically improve the performance
of PSI protocols whose overhead depends on the length of the representations of input items.
We apply Phasing to design a new approach for circuit-based PSI protocols. The resulting protocol is up to 5 times faster than the previously best Sort-Compare-Shuffle circuit of Huang et al. (NDSS 2012). We also apply Phasing to the OT-based PSI protocol of Pinkas et
al. (USENIX Security 2014), which is the fastest PSI protocol to date. Together with additional improvements that reduce the computation complexity by a logarithmic factor, the resulting protocol improves run-time by a factor of up to 20 and can also have better communication overhead than the previously best PSI protocol in that respect. The new protocol is only moderately less efficient
than an insecure PSI protocol that is currently used by real-world applications, and is therefore the first secure PSI protocol that is scalable to the demands and the constraints of current real-world settings.
small payments. The approach is innovative, in that each coin may be
efficiently verified by the same or different merchants during payment. The scheme relies on a batch signature technique to efficiently sign and verify individually spent coins; coins may also be deposited in batch manner. The scheme outlined differs considerably from conventional micropayments schemes by servicing a number of cash-like properties, such as off-line processing, detection of double spent coins, and ability to spend at different merchants. Additionally, the scheme eliminates a number of processing overheads that are apparent to some existing micropayment schemes.
In this paper, we study similar construction for pseudorandom functions (PRFs), where additionally the access to a public $n$-bit (one-way) function $F$ is allowed. In particular, we show a sharp $n/2$-security bound for the simplest possible construction $F(x\\oplus k)$ and a sharp $2/3\\cdot n$-bound for the $FP(1)$-construction $F(P(x\\oplus k)\\oplus k)$, both in the random oracle model. The latter result contrasts with a sharp bound of the same order for $P(P(x\\oplus k)\\oplus \\pi(k))\\oplus k$, recently proved by Chen et. al.
One practical motivation for our research is due to the fact that operation modes of key stream generator based (KSG-based) stream ciphers can be modeled in a very straightforward way by FP-constructions. Our research shows a way to save KSG inner state length by using operation modes, which yield provable security beyond the birthday bound against time-space-data tradeoff attacks. For instance, we demonstrate that a slight change in the operation mode of the Bluetooth cipher (adding the session key twice in the initialization phase) raises the security w.r.t. to generic time-space-data tradeoff attacks from $n/2$ to $2/3\\cdot n$, where $n$ denotes the KSG inner state length.
The security of ECC is based on the hardness of the elliptic curve discrete logarithm problem (ECDLP).
Implementing and analyzing the performance of the best known methods to solve the ECDLP is useful to assess the security of ECC and choose security parameters in practice.
We present a novel many-core hardware architecture implementing the parallel version of Pollard\'s rho algorithm
to solve the ECDLP. This architecture results in a speed-up of almost 300% compared to the state of the art and we use it to estimate the monetary cost of solving the Certicom ECCp-131 challenge using FPGAs.
in the ring of cyclotomic integers are suggested to be used in most such schemes. On the other hand in computational algebraic number theory one of the main problem
is called principle ideal problem (PIP). Its goal is to find a generators of any principle ideal in the ring of algebraic integers in any number field. In this paper we establish a polynomial time reduction from approximate shortest lattice vector problem for principle ideal lattices to their PIP\'s in many cyclotomic integer rings. Combining with the polynomial time quantum algorithm for PIP of arbitrary number fields, this implies that some approximate SVP problem for principle ideal lattices within a polynomial factor in some cyclotomic integer rings can be solved by polynomial time quantum algorithm.
This paper presents two new constant-round simulatable coin-flipping protocols, based explicitly on one or a few X-commitments of short seeds and a Q-commitment of a short hash, independently of the large target length. A pseudo-random generator and a collision-resistant hash function are used to combine the separate X and Q properties (associated with short bit-strings) into a unified X&Q property amplified to the target length, thus amortizing the cost of the base commitments. In this way, the new protocols are significantly more efficient than an obvious batching or extension of coin-flippings designed (in the same security setting) for short bit-strings and based on inefficient X&Q commitments.
The first protocol, simulatable with rewinding, deviates from the traditional coin-flipping template in order to improve simulatability in case of unknown adversarial probabilities of abort, without having to use a X&Q commitment scheme. The second protocol, one-pass simulatable, derives from a new construction of a universally composable X&Q commitment scheme for large bit-strings, achieving communication-rate asymptotically close to 1. Besides the base X and Q commitments, the new commitment scheme only requires corresponding collision-resistant hashing, pseudo-random generation and application of a threshold erasure code. Alternative constructions found in recent work with comparable communication complexity require explicit use of oblivious transfer and use different encodings of the committed value.
Group signatures additionally enforce accountability by providing the group manager with a secret tracing key that can be used to identify the otherwise anonymous signer when needed.
Accountable ring signatures, introduced by Xu and Yung (CARDIS 2004), bridge the gap between the two notions. They provide maximal flexibility in choosing the ring, and at the same time maintain accountability by supporting a designated opener that can identify signers when needed.
We revisit accountable ring signatures and offer a formal security model for the primitive. Our model offers strong security definitions incorporating protection against maliciously chosen keys and at the same time flexibility both in the choice of the ring and the opener.
We give a generic construction using standard tools.
We give a highly efficient instantiation of our generic construction in the random oracle model by meticulously combining Camenisch\'s group signature scheme (CRYPTO 1997) with a generalization of the one-out-of-many proofs of knowledge by Groth and Kohlweiss (EUROCRYPT 2015). Our instantiation yields signatures of logarithmic size (in the size of the ring) while relying solely on the well-studied decisional Diffie-Hellman assumption.
In the process, we offer a number of optimizations for the recent Groth and Kohlweiss one-out-of-many proofs, which may be useful for other applications.
Accountable ring signatures imply traditional ring and group signatures. We therefore also obtain highly efficient instantiations of those primitives with signatures shorter than all existing ring signatures as well as existing group signatures relying on standard assumptions.