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.
is indifferentiable from a RO (with standard, good bounds) when applications use keys of a fixed length less than d − 1.
lattice schemes. The novel scheme is obtained as a result of a modification of the rejection sampling algorithm that is at the heart of Lyubashevsky\'s signature scheme (Eurocrypt, 2012) and several other lattice primitives. Our new rejection sampling algorithm which samples from a bimodal Gaussian distribution, combined with a modified
scheme instantiation, ends up reducing the standard deviation of the resulting
signatures by a factor that is asymptotically square root in the security
parameter. The implementations of our signature scheme for security levels of
128, 160, and 192 bits compare very favorably to existing schemes such as
RSA and ECDSA in terms of efficiency. In addition, the new scheme has shorter
signature and public key sizes than all previously proposed lattice signature
As part of our implementation, we also designed several novel algorithms which
could be of independent interest. Of particular note, is a new algorithm for
efficiently generating discrete Gaussian samples over Z^n. Current
algorithms either require many high-precision floating point exponentiations
or the storage of very large pre-computed tables, which makes them completely
inappropriate for usage in constrained devices. Our sampling algorithm
reduces the hard-coded table sizes from linear to logarithmic as compared to
the time-optimal implementations, at the cost of being only a small factor
In this paper, we propose an improved SAS scheme that has a shorter signature size compared with that of Lee et al.\'s SAS scheme. Our SAS scheme is also secure without random oracles under static assumptions. To achieve the improvement, we devise a new public-key signature scheme that supports multi-users and public re-randomization. Compared with the SAS scheme of Lee et al., our SAS scheme employs new techniques which allow us to reduce the size of signatures by increasing the size of the public keys (obviously, since signature compression is at the heart of aggregate signature this is a further step in understanding the aggregation capability of such schemes).