International Journal of Applied Cryptography (6 papers in press)
Sieving for shortest vectors in ideal lattices: a practical perspective
by Joppe Bos, Michael Naehrig, Joop van de Pol
Abstract: The security of many lattice-based cryptographic schemes relies on the hardness of short vectors in integral lattices. We propose a new variant of the parallel Gauss sieve algorithm to compute such short vectors. It combines favourable properties of previous approaches resulting in reduced run time and memory requirement per node. Our publicly available implementation outperforms all previous Gauss sieve approaches for dimensions 80, 88, and 96. When computing short vectors in ideal lattices, we show how to reduce the number of multiplications and comparisons by using a symbolic Fourier transform. We compute a short vector in a negacyclic ideal lattice of dimension 128 in less than nine days on 1024 cores, more than twice as fast as the recent record computation for the same lattice on the same computer hardware.
Keywords: lattice cryptanalysis; parallel Gauss sieve; ideal lattices; ring LWE
Trustworthy public randomness with sloth, unicorn and trx
by Arjen K. Lenstra, Benjamin Wesolowski
Abstract: Many applications require trustworthy generation of public random numbers. It is shown how this can be achieved using a hash function that is timed to be as slow as desired (sloth), while the correctness of the resulting hash can be verified quickly. It is shown how sloth can be used for uncontestable random number generation (unicorn), and how unicorn can be used for a new trustworthy random elliptic curves service (trx) and random-sample voting.
Keywords: public random number generation; random beacon; slow-timed hash
Prover-efficient commit-and-prove zero-knowledge SNARKs
by Helger Lipmaa
Abstract: Zk-SNARKs (succinct non-interactive zero-knowledge arguments of knowledge) are needed in many applications. Unfortunately, all previous zk-SNARKs for interesting languages are either inefficient for the prover, or are non-adaptive and based on a commitment scheme that depends both on the provers input and on the language, i.e., they are not commit-and-prove (CaP) SNARKs. We propose a proof-friendly extractable commitment scheme, and use it to construct prover-efficient adaptive CaP succinct zk-SNARKs for different languages, that can all reuse committed data. In new zk-SNARKs, the prover computation is dominated by a linear number of cryptographic operations. We use batch-verification to decrease the verifier's computation; importantly, batch-verification can be used also in QAP-based zk-SNARKs.
Keywords: batch verification; commit-and-prove; CRS; NIZK; numerical NP-complete languages; range proof; Subset-Sum; zk-SNARK.
Attribute-based fully homomorphic encryption with a bounded number of inputs
by Ciaran McGoldrick, Michael Clear
Abstract: The only known way to achieve attribute-based fully homomorphic encryption (ABFHE) is through indistinguishability obfuscation. The best we can do at the moment without obfuscation is attribute-based levelled FHE, which allows circuits of an a priori bounded depth to be evaluated. This has been achieved from the learning with errors (LWE) assumption. However, we know of no other way without obfuscation of constructing a scheme that can evaluate circuits of unbounded depth. In this paper, we present an ABFHE scheme that can evaluate circuits of unbounded depth but with one limitation: there is a bound N on the number of inputs that can be used in a circuit evaluation. The bound N could be thought of as a bound on the number of independent senders. Our scheme allows N to be exponentially large so we can set the parameters so that there is no limitation on the number of inputs in practice. Our construction relies on multi-key FHE and levelled ABFHE, both of which have been realised from LWE, and therefore we obtain a concrete scheme that is secure under LWE.
Keywords: attribute-based encryption; fully homomorphic encryption;.
On the separation between the FHMQV and HMQV protocols
by Augustin P. Sarr, Philippe Elbaz-Vincent
Abstract: The HMQV protocol is under consideration for IEEE P1363 standardisation. We provide a complementary analysis of the HMQV(C) protocol. Namely, we point out a key compromise impersonation and a maninthemiddle attack in the case of a static private key leakage, showing that the HMQV(C) protocols cannot achieve their security goals. Next, we revisit the FHMQV building blocks, design and security arguments. We clarify the security and efficiency separation between HMQV and FHMQV, showing the advantages of FHMQV over HMQV.
Keywords: authenticated key exchange; FHMQV; HMQV; KCI attack; security model.
A privacy-enhanced access log management mechanism in SSO systems from nominative signatures
by Nakagawa Sanami, Takashi Nishide, Eiji Okamoto, Keita Emura, Goichiro Hanaoka, Yusuke Sakai, Akihisa Kodate
Abstract: In online services, e.g., online shopping, a service provider (SP) manages access logs containing customers' buying histories. Therefore, user's personal information, e.g., their hobbies and diversions, is revealed from the exposed logs if each customer can be linked. In fact, such information exposure has occurred owing to the popularisation of online services. To cope with this problem, SPs may only have to delete access logs, but then no illegitimate users, who accessed the server illegally, will be traced from the logs. In this paper, we propose a log management mechanism where (1) no user information is revealed even if logs are exposed, but (2) illegitimate users can be traced when necessary. Specifically, we consider single sign-on (SSO) systems, since plural access logs might be connected by one account, and this could trigger the above privacy infringement problem. We construct our privacy-enhanced access log management mechanism based on the Wang-Wang-Susilo SSO system (TrustCom 2013), which applies nominative signatures as its building block. Specifically, we realise the system by additionally applying the invisibility property of the Schuldt-Hanaoka nominative signature scheme (ACNS 2011). Finally, we estimate the efficiency of the proposed system by using Pairing-Based Cryptography (PBC) library and confirm that for each algorithm, computation time is at most just over 80 milliseconds on a PC, which seems sufficiently practical.
Keywords: nominative signature; single sign-on system; access log management.