## CryptoDB

### Helger Lipmaa

#### Affiliation: University of Tartu, Estonia ; Simula UiB, Norway

#### Publications

**Year**

**Venue**

**Title**

2013

ASIACRYPT

2010

EPRINT

On E-Vote Integrity in the Case of Malicious Voter Computers
Abstract

Norway has started to implement e-voting (over the Internet, and by using voters' own computers) within the next few years. The vulnerability of voter's computers was identified as a serious threat to e-voting. Therefore, in this paper, we study the vote integrity of e-voting when the voter computers cannot be trusted. For this, we first make a number of assumptions---that arose from the discussion with the representatives of Norwegian government, and have been approved by them---about the available infrastructure. In particular, we assume the existence of two out-of-band channels that do not depend on the voter computers. The first channel is used to transmit integrity check codes to the voters prior the election, and the second channel is used to transmit a check code, that corresponds to her vote, back to a voter just after his or her e-vote vast cast. For this we also introduce a new cryptographic protocol. We present the new protocol with enough details to facilitate an implementation, and also present the timings of an actual implementation.

2008

EPRINT

Private Branching Programs: On Communication-Efficient Cryptocomputing
Abstract

We polish a recent cryptocomputing method that makes it possible to cryptocompute every language in $\mathbf{L/poly}$. We give several nontrivial applications, including: (a) A CPIR protocol with log-squared communication and sublinear server-computation by giving a secure function evaluation protocol for Boolean functions with similar performance, (b) A protocol that makes it possible to compute (say) how similar is client's input to an element in server's database, without revealing any information to the server, (c) A protocol for private database updating with low amortized complexity.

2008

EPRINT

On CCA1-Security of Elgamal And Damg{\aa}rd Cryptosystems
Abstract

Denote by $X^{Y[i]}$ the assumption that the adversary, given a non-adaptive oracle access to the $Y$ oracle with $i$ free variables cannot break the assumption $X$. We show that Elgamal is CCA1-secure under the $DDH^{CCH[1]}$ assumption. We then give a simple proof that the Damg{\aa}rd cryptosystem is CCA1-secure under the $DDH^{DDH[2]}$ assumption, where the proof uses a recent trapdoor test trick by Cash, Kiltz and Shoup.

2008

EPRINT

On CCA1-Security of Elgamal And Damg{\aa}rd's Elgamal
Abstract

We establish the complete complexity landscape surrounding CCA1-security of Elgamal and Damg{\aa}rd's Elgamal (DEG). Denote by $X^{Y[i]}$ the assumption that the adversary, given a non-adaptive oracle access to the $Y$ oracle with $i$ free variables cannot break the assumption $X$. We show that the CCA1-security of Elgamal is equivalent to the $DDH^{CDH[1]}$ assumption. We then give a simple alternative to Gj{\o}steen's proof that DEG cryptosystem is CCA1-secure under the $DDH^{DDH[2]}$ assumption. We also provide several separations. We show that $DDH$ cannot be reduced to $DDH^{CDH[1]}$ in the generic group model. We give an irreduction showing that $DDH$ cannot be reduced to $DDEG^{CDEG[2]}$ (unless $\DDH$ is easy), $DDEG^{CDEG[2]}$ cannot be reduced to $DDH^{DDH[2]}$ (unless $DDEG^{CDEG[2]}$ is easy) and $DDH^{DDH[2]}$ cannot be reduced to the $DDH^{CDH[1]}$(unless $DDH^{DDH[2]}$ is easy). All those irreductions are optimal in the sense that they show that if assumption $X$ can be reduced to $Y$ in polynomial time then $X$ has to be solvable in polynomial time itself and thus \emph{both} assumptions are broken.

2007

EPRINT

New Communication-Efficient Oblivious Transfer Protocols Based on Pairings
Abstract

We construct two simple families of two-message $(n,1)$-oblivious transfer protocols based on degree-$t$ homomorphic cryptosystems with the communication of respectively $1+\lceil n/t\rceil$ and $3+\lceil n/(t+1)\rceil$ ciphertexts. The construction of both families relies on efficient cryptocomputable conditional disclosure of secret protocols; the way this is done may be of independent interest. The currently most interesting case $t=2$ can be based on the Boneh-Goh-Nissim cryptosystem. We show how to reduce the communication of virtually any existing oblivious transfer protocols by proposing a new related communication-efficient generic transformation from computationally-private information retrieval protocols to oblivious transfer protocols.

2006

EPRINT

Cryptographically Private Support Vector Machines
Abstract

We study the problem of private classification using kernel methods. More specifically, we propose private protocols implementing the Kernel Adatron and Kernel Perceptron learning algorithms, give private classification protocols and private polynomial kernel computation protocols. The new protocols return their outputs---either the kernel value, the classifier or the classifications---in encrypted form so that they can be decrypted only by a common agreement by the protocol participants. We also show how to use the encrypted classifications to privately estimate many properties of the data and the classifier. The new SVM classifiers are the first to be proven private according to the standard cryptographic definitions.

2006

EPRINT

On the Feasibility of Consistent Computations
Abstract

In many practical settings, participants are willing to deviate from
the protocol only if they remain undetected. Aumann and Lindell
introduced a concept of covert adversaries to formalize this type of
corruption. In the current paper, we refine their model to get
stronger security guarantees. Namely, we show how to construct
protocols, where malicious participants cannot learn anything beyond
their intended outputs and honest participants can detect malicious
behavior that alters their outputs. As this construction does not
protect honest parties from selective protocol failures, a valid
corruption complaint can leak a single bit of information about the
inputs of honest parties. Importantly, it is often up to the honest
party to decide whether to complain or not. This potential leakage
is often compensated by gains in efficiency---many standard
zero-knowledge proof steps can be omitted. As a concrete practical
contribution, we show how to implement consistent versions of
several important cryptographic protocols such as oblivious
transfer, conditional disclosure of secrets and private inference
control.

2006

EPRINT

Black-Box Knowledge Extraction Revisited: Universal Approach with Precise Bounds
Abstract

Rewinding techniques form the essence of many security reductions including proofs for identification and signature schemes. We propose a simple and modular approach for the construction of such proofs.
Straightforward applications of our central result include, but are not limited to, the security of identification schemes, generic signatures and ring signatures. These results are well known, however, we generalise them in such a way that our technique can be used off-the-shelf for future applications. We note that less is more: as a side-effect of our less complex analysis, all our proofs are more precise; for example, we get a new proof of the forking lemma that is $2^{15}$ times more precise than the original result by Pointcheval and Stern. Finally, we give the first precise security analysis of Blum's coin flipping protocol with $k$-bit strings, as yet another example of the strength of our results.

2005

EPRINT

A New Protocol for Conditional Disclosure of Secrets And Its Applications
Abstract

Many protocols that are based on homomorphic encryption are private only if a client submits inputs from a limited range $S$. Conditional disclosure of secrets (CDS) helps to overcome this restriction. In a CDS protocol for a set $S$, the client obtains server's secret if and only if the client's inputs belong to $S$ and thus the server can guard itself against malformed queries. We extend the existing CDS protocols to work over additively homomorphic cryptosystems for every set from $NP/poly$. The new construction is modular and easy to apply. As an example, we derive a new oblivious transfer protocol with log-squared communication and a millionaire's protocol with logarithmic communication. We also implement private, universally verifiable and robust multi-candidate electronic voting so that all voters only transmit an encryption of their vote. The only hardness assumption in all these protocols is that the underlying public-key cryptosystem is IND-CPA secure and the plaintext order does not have small factors.

2004

EPRINT

An Oblivious Transfer Protocol with Log-Squared Communication
Abstract

We propose a one-round $1$-out-of-$n$ computationally-private information retrieval protocol for $\ell$-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication $\Theta(k\cdot\log^2{n}+\ell\cdot\log{n})$, where $k$ is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private $1$-out-of-$n$ oblivious-transfer protocol for $\ell$-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model.

2003

EPRINT

Interleaving Cryptography and Mechanism Design: The Case of Online Auctions
Abstract

We propose a new cryptographically protected multi-round auction mechanism for online auctions. This auction mechanism is designed to provide (in this order) security, cognitive convenience, and round-effectiveness. One can vary internal parameters of the mechanism to trade off bid privacy and cognitive costs, or cognitive costs and the number of rounds. We are aware of no previous work that interleaves cryptography explicitly with the mechanism design.

2003

EPRINT

Cryptographic Randomized Response Techniques
Abstract

We develop cryptographically secure techniques to guarantee unconditional privacy for respondents to polls. Our constructions are efficient and practical, and are shown not to allow cheating respondents to affect the ``tally'' by more than their own vote --- which will be given the exact same weight as that of other respondents. We demonstrate solutions to this problem based on both traditional cryptographic techniques and quantum cryptography.

2003

EPRINT

On Diophantine Complexity and Statistical Zero-Knowledge Arguments
Abstract

We show how to construct practical honest-verifier statistical zero-knowledge \emph{Diophantine} arguments of knowledge (HVSZK AoK) that a committed tuple of integers belongs to an arbitrary language in bounded arithmetic. While doing this, we propose a new algorithm for computing the Lagrange representation of nonnegative integers and a new efficient representing polynomial for the exponential relation. We apply our results by constructing the most efficient known HVSZK AoK for non-negativity and the first constant-round practical HVSZK AoK for exponential relation. Finally, we propose the outsourcing model for cryptographic protocols and design communication-efficient versions of the Damg{\aa}rd-Jurik multi-candidate voting scheme and of the Lipmaa-Asokan-Niemi $(b+1)$st-price auction scheme that work in this model.

2002

EPRINT

On Optimal Hash Tree Traversal for Interval Time-Stamping
Abstract

Skewed trees constitute a two-parameter family of recursively constructed trees. Recently, Willemson proved that suitably picked skewed trees are space-optimal for interval time-stamping. At the same time, Willemson proposed a practical but suboptimal algorithm for nonrecursive traversal of skewed trees. We describe an alternative, extremely efficient traversal algorithm for skewed trees. The new algorithm is surprisingly simple and arguably close to optimal in every imaginable sense. We provide a detailed analysis of the average-case storage (and communication) complexity of our algorithm, by using the Laplace's method for estimating the asymptotic behavior of integrals. Since the skewed trees can be seen as a natural generalization of Fibonacci trees, our results might also be interesting in other fields of computer science.

2001

EPRINT

Efficient Algorithms for Computing Differential Properties of Addition
Abstract

In this paper we systematically study the differential properties of
addition modulo $2^n$. We derive $\Theta(\log n)$-time algorithms
for most of the properties, including differential probability of
addition. We also present log-time algorithms for finding good
differentials. Despite the apparent simplicity of modular addition,
the best known algorithms require naive exhaustive computation. Our
results represent a significant improvement over them. In the most
extreme case, we present a complexity reduction from
$\Omega(2^{4n})$ to $\Theta(\log n)$.

2001

EPRINT

Statistical Zero-Knowledge Proofs from Diophantine Equations
Abstract

A family $(S_t)$ of sets is $p$-bounded Diophantine if $S_t$ has a
representing $p$-bounded polynomial $R_{S,t}$, s.t. $x\in S_t \iff
(\exists y)[R_{S}(x;y)=0]$. We say that $(S_t)$ is unbounded
Diophantine if additionally, $R_{S,t}$ is a fixed $t$-independent
polynomial. We show that $p$-bounded (resp., unbounded) Diophantine
set has a polynomial-size (resp., constant-size) statistical
zero-knowledge proof system that a committed tuple $x$ belongs to
$S$. We describe efficient SZK proof systems for several
cryptographically interesting sets. Finally, we show how to prove in
SZK that an encrypted number belongs to $S$.

2001

EPRINT

Secure Vickrey Auctions without Threshold Trust
Abstract

We argue that threshold trust is not an option in most of the real-life
electronic auctions. We then propose two new cryptographic Vickrey auction schemes that involve, apart from the bidders and the seller $S$, an auction authority $A$ so that unless $S$ and $A$ collude the outcome of auctions will be correct, and moreover, $S$ will not get any information about the bids, while $A$ will learn bid statistics. Further extensions make it possible to decrease damage that colluding $S$ and $A$ can do, and to construct $(m+1)$st price auction schemes. The communication complexity between the $S$ and $A$ in medium-size auctions is at least one order of magnitude less than in the Naor-Pinkas-Sumner scheme.

2000

EPRINT

Accountable Certificate Management using Undeniable Attestations
Abstract

This paper initiates a study of accountable certificate management
methods, necessary to support long-term authenticity of digital
documents. Our main contribution is a model for accountable
certificate management, where clients receive attestations
confirming inclusion/removal of their certificates from the database
of valid certificates. We explain why accountability depends on the
inability of the third parties to create contradictory attestations.
After that we define an undeniable attester as a primitive that
provides efficient attestation creation, publishing and
verification, so that it is intractable to create contradictory
attestations. We introduce authenticated search trees and build an
efficient undeniable attester upon them. The proposed system is the
first accountable long-term certificate management system.
Moreover, authenticated search trees can be used in many
security-critical applications instead of the (sorted) hash trees to
reduce trust in the authorities, without decrease in efficiency.
Therefore, the undeniable attester promises looks like a very useful
cryptographic primitive with a wide range of applications.

#### Program Committees

- PKC 2020
- PKC 2019
- Asiacrypt 2019
- Asiacrypt 2018
- Eurocrypt 2010
- Eurocrypt 2006
- FSE 2003

#### Coauthors

- Behzad Abdolmaleki (1)
- Andris Ambainis (2)
- N. Asokan (1)
- Karim Baghery (1)
- Fabrice Benhamouda (1)
- Florian Bourse (1)
- Ahto Buldas (3)
- Philippe Dumas (1)
- Edith Elkind (1)
- Prastudy Fauzi (3)
- Jens Groth (1)
- Sven Heiberg (1)
- Markus Jakobsson (2)
- Emilia Käsper (1)
- Aggelos Kiayias (1)
- Filip Van Laenen (1)
- Peeter Laud (2)
- Sven Laur (5)
- Taneli MielikÃ¤inen (1)
- Shiho Moriai (2)
- Valtteri Niemi (1)
- Berry Schoenmakers (1)
- Janno Siim (1)
- Johan Wallén (1)
- Jan Willemson (1)
- Michal Zajac (3)
- Bingsheng Zhang (1)