*00:17* [Pub][ePrint]
A New Method for Decomposition in the Jacobian of Small Genus Hyperelliptic Curves, by Palash Sarkar and Shashank Singh
Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in anindex calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed

a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor

basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of polynomials

required in Gaudry\'s method. Also, the total number of additions in the Jacobian required by the new method is less than

that required by Gaudry\'s method. The new method itself is quite simple and we present some example decompositions and timing

results of our implementation of the method using Magma.

*00:17* [Pub][ePrint]
Circulant Matrices and Differential Privacy, by Jalaj Upadhyay
This paper resolves an open problem raised by Blocki {\\it et al.} (FOCS 2012), i.e., whether other variants of the Johnson-Lindenstrauss transform preserves differential privacy or not? We prove that a general class of random projection matrices that satisfies the Johnson-Lindenstrauss lemma also preserves differential privacy. This class of random projection matrices requires only $n$ Gaussian samples and $n$ Bernoulli trials and allows matrix-vector multiplication in $O(n \\log n)$ time. In this respect, this work unconditionally improves the run time of Blocki {\\it et al.} (FOCS 2012) without using the graph sparsification trick of Upadhyay (ASIACRYPT 2013). For the metric of measuring randomness, we stick to the norm used by earlier researchers who studied variants of the Johnson-Lindenstrauss transform and its applications, i.e., count the number of random samples made. In concise, we improve the sampling complexity by quadratic factor, and the run time of cut queries by an $O(n^{o(1)})$ factor and that of covariance queries by an $O(n^{0.38})$ factor.Our proof for both the privacy and utility guarantee uses several new ideas. In order to improve the dimension bound, we use some known results from the domain of statistical model selection. This makes our proof short and elegant, relying just on one basic concentration inequality. For the privacy proof, even though our mechanism closely resembles that of Blocki {\\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 2013), we cannot use their proof idea. This is because the projection matrices we are interested in introduces non-trivial correlations between any two rows of the published matrix, and, therefore, we cannot invoke the composition theorem of Dwork, Rothblum and Vadhan (STOC 2009). We argue that the published matrix is not $r$-multivariate distribution; rather one matrix-variate distribution. We compute the distribution of the published matrix and then prove it preserves differential privacy.

*15:17* [Pub][ePrint]
A Decentralized Public Key Infrastructure with Identity Retention, by Conner Fromknecht, Dragos Velicanu, Sophia Yakoubov
Public key infrastructures (PKIs) enable users to look up and verify one another\'s public keys based on identities. Current approaches to PKIs are vulnerable because they do not offer sufficiently strong guarantees of \\emph{identity retention}; that is, they do not effectively prevent one user from registering a public key under another\'s already-registered identity.

In this paper, we leverage the consistency guarantees provided by cryptocurrencies such as Bitcoin and Namecoin to build a PKI that ensures identity retention.

Our system, called Certcoin, has no central authority and thus requires the use of secure distributed dictionary data structures to provide efficient support for key lookup.

*06:17* [Pub][ePrint]
Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof, by Dongdai Lin and Yujuan Quan and Jian Weng and Jun Yan
Watrous (STOC 2006) proved that plugging classical bit commitment scheme that is secure against quantum attack into the GMW-type construction of zero-knowledge gives a classical zero-knowledge proof that is secure against quantum attack. In this paper, we showed that plugging quantum bit commitment scheme (allowing quantum computation and communication) into the GMW-type construction also gives a quantum zero-knowledge proof, as one expects. However, since the binding condition of quantum bit commitment scheme is inherently different from its classical counterpart, compared with Watrous\' security proof, here we encounter new difficulty in soundness analysis. To overcome the difficulty, we take a geometric approach, managing to reduce quantum soundness analysis to classical soundness analysis.We also propose a formalization of non-interactive quantum bit commitment scheme, which may come in handy in other places. Moreover, inspired by our formalization, we generalize Naor\'s construction of bit commitment scheme to the quantum setting, achieving non-interactive commit stage.

We hope quantum bit commitment scheme can find more applications in quantum cryptography.