Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

1
vote
1answer
37 views

Verification in Threshold RSA or Threshold Paillier

In the key generation of the threshold version of RSA or the threshold version of the Paillier cryptosystem (e.g. "Shoup - 2000 - Practical threshold signatures" or "Fouque et al. - 2000 - Sharing ...
4
votes
1answer
50 views

Lightweight primality certificates for untrusted DH parameters

Are there any light-weight techniques to generate primality certificates for custom Diffie-Hellman parameters that could be sent to the client to allow it to verify primality without needing to run ...
1
vote
2answers
71 views

Constraint about encrypted values

Let V = $[x_1,\ldots ,x_n]$ be a binary vector of length $n$, and let $E(V)$ be the entrywise encryption of this vector. Suppose I want to give to another player, $E(V)$, but also let him have the ...
-1
votes
1answer
112 views

Random number generator in a 2p2 Network

for my thesis I am trying to develop a system where nodes from a peer to peer network agree in generate a random number every tot seconds. I am stocked in this problem since almost 1 week anyone can ...
2
votes
0answers
188 views

Can Verifiable Random Functions be used to pick a random node from a pool?

Let's say that I have a decentralized system and I have a list of nodes published on a pubic log like a blockchain. I want a node A to be able to connect to another ...
2
votes
0answers
69 views

Are there any information-theoretically secure verifiable secret sharing protocols with t=n?

Disregarding matters such as efficiency and round complexity, can verifiable secret sharing be done in a way such that the secret cannot be decoded unless you have all n shares, and that this ...
3
votes
2answers
117 views

Why does the prover in an interactive proof run in exponential time with the space of the computation?

I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches. In particular, I've been watching the following YouTube video which talks ...
1
vote
4answers
130 views

Is it possible to verify and relay an encryption key with a trusted but transparent third party?

I'm wondering if it would be possible to implement this functionality with a trusted but transparent third party (maybe an Ethereum smart contract?): Bob has an encryption key. Alice has the ...
3
votes
1answer
157 views

zkSnarks - why isn't PCD more widely used?

I've been reading the paper Scalable Zero Knowledge from Cycles of Elliptic Curves, which elegantly solves (what seems to me) the main problem with zkSnarks; namely that performing non-trivial ...
3
votes
2answers
197 views

How can I prove the result of a long computation with a short string?

I have a simple program F (think of a cellular automaton) that, when executed in some input X, takes a while to complete and ...
4
votes
1answer
246 views

Proof of encrypted content

I would like to create a server that would verify a public/private key pair where the private key is encrypted with a key unknown to the server. The server should reject the keypair if the encrypted ...
2
votes
1answer
115 views

Verifiable computation on signed data

Consider the following setting. Alice receives a chunk of data from Victor, together with a cryptographic certificate of authenticity of some sort (eg hash signed with Victor’s private key). Bob ...
1
vote
1answer
67 views

how to efficiently prove the query result is empty?

Consider a simplified scenario. Suppose an untrusted server holds a set of data $A=\{ a_1,a_2,\cdots,a_n\}$. A client issues a query $b$ to the server and wants to decide if $b\in A$. The server ...
5
votes
1answer
509 views

What is the difference between signatures and VRF?

For example we have asymmetric signature scheme(RSA or ECC based) and VRF(also can be RSA/ECC based), both of them can be verified using public key of the signer/hasher and also are unique for each ...
5
votes
2answers
72 views

Swap information

Alice is trading information with Bob. Alice and Bob are in a Prisoner's Dilemma in that they'd prefer not sending their respective key while receiving each other's but would prefer an exchange taking ...
1
vote
1answer
126 views

Is there a way to verify an original author using encryption?

I feel like the title explains the problem fairly well. Is is possible to use encryption to verify a document's original author? In my case, I have a doc that I want to release online. Is there a way ...
0
votes
1answer
75 views

Verify membership of an item within a set while obscuring the number of elements in the set?

I'm wondering whether it is possible to achieve the following scenario: Say you have a set of names {Alice, Bob, Jake}. To verify that the name 'Bob' exists in the set, you can simply compare 'Bob' ...
5
votes
1answer
177 views

Only allow specific types of data to be transmitted via an end-to-end encryption service

I have a service that allows multiple parties to share domain-specific textual data. This data is also end-to-end encrypted. How can I be sure the sharing parties don't send non-domain-specific data, ...
3
votes
1answer
82 views

Public key verification schemes

I have a short question. Besides PKI, Web of Trust or secure out of band communication. Is there any other way to verify the public key of a communicating party? In other words, let's assume an ...
10
votes
3answers
336 views

Can a device prove the identity of its own code?

Say you have a computing system that has some functionality that is not in itself cryptographically secure, but you want to make sure is executed as specified, and, e.g. an adversary hasn't re-flashed ...
2
votes
1answer
156 views

Plausible Deniability in Schnorr

How does a dishonest verifier affect plausible deniability of the interactive Schnorr protocol?
1
vote
1answer
426 views

Quality test for an hardware source of randomness

Say that I developed an hardware source of randomness, which I would like to use to seed a cryptographically secure random number generator. How would I go about testing it? Are there standardized ...
9
votes
2answers
464 views

Universally verifiable random beacon

I am developing a network where potentially many many nodes (billions, in principle?) should be able to agree on a random number. I would really prefer to avoid $O(N^2)$ procedures where everyone ...
9
votes
1answer
633 views

Is there a formal language to define a cryptographic protocol?

I wanted to work on a personal project where I would attempt to identify the flaws in a cryptographic protocol. Now for that to work properly, the program should understand the syntax of protocol ...
4
votes
1answer
101 views

Why is cryptographic model not considered formal methods?

I have just started looking at different methods for analyzing the security of cryptographic protocols. According to my reading, there are two main approaches in this area. The first approach is so-...
21
votes
2answers
2k views

Formal verification in cryptography

I have seen in some places that people use formal verification and/or computer-aided verification for cryptography (tools like ProVerif, CryptoVerif, etc.). How do these approaches work?
4
votes
1answer
381 views

Simple application of verifiable random function?

I have been reading a little bit about verifiable random functions (e.g.). In the literature, these are described as "pseudo-random functions that provide a non-interactively verifiable proof for the ...
3
votes
1answer
126 views

How can I formally verify fuzzy commitment scheme based security protocol?

I am currently working on designing a security protocol which involves usage of fuzzy commitment schemes, for. eg Reed-Solomon codes which allows us to tolerate a certain level of error. I was ...
2
votes
1answer
405 views

How to calculate $v_k(s)$ in Quadratic Arithmetic Program?

In the paper Pinocchio: Nearly Practical Verifiable Computation, there are some polynomials $v_k(x)$, $w_k(x)$ and $y_k(x)$ representing the structure of there circuit. However, as in the "concrete ...
2
votes
1answer
231 views

Is succinct verification of an arbitrary data transformation theoretically possible? Is it feasible? How?

Given input string S, and transformation (i.e. computer program) T, is it possible to provide a succinct proof that another binary string S' is identical to the output T(S)? By "succinct", I ...
3
votes
1answer
350 views

Implementing forward secrecy in OpenPGP with public key authentication

I am trying to consider the feasibility of implementing an encrypted file sharing system, which both provides forward secrecy but also allows public key verification. I am stuck on the marriage ...
0
votes
0answers
208 views

arithmetic calculation problem to quadratic arithmetic program

I am reading the Pinocchio paper (verifiable computation): http://research.microsoft.com/pubs/180286/pinocchio.pdf The paper is rather hard for me. I am considering this calculation problem: $(c_1*...
1
vote
1answer
54 views

Figure 2 in the Verifiable Computation - Pinocchio

I am reading the Pinocchio paper (verifiable computation): http://research.microsoft.com/pubs/180286/pinocchio.pdf The paper is rather hard for me. For the Figure 2, I guess $v_1(x)$ should be $(r_6-...
1
vote
0answers
246 views

Zero knowledge of two factor

Here I overconfident in myself state that I can show, that n has two factors. This is not completely true, can possibly show $n$ is composite - prover generates RSA key with modulo $n$, and gives $e$ ...
0
votes
1answer
196 views

Blum primes [x=3(mod 4)] zero knowledge proof?

Lets say we have 2 primes, $p \equiv q \equiv 3 \pmod{4}$, and we make $n=p \times q$ public. I can, without revealing factors, show that $n$ has two prime factors. How can i zero knowledge prove ...
0
votes
1answer
81 views

Bit commitment, two blobs with same bit, without revealing it?

Suppose we have bit commitment scheme: $n=p*q$ and $t \in QNR_n$, with Jacobi $(\frac{t}{n})=1$ Commitment(P), random $x\in \mathbb{Z}_n$, $y=x^2t^b$, where $b$ is bit. Ok, suppose we have $y_1$ and ...
1
vote
1answer
230 views

HMAC tag to verify the key (verification in the reverse direction)

A quick question. Are there any problems with the following HMAC use-case: We have two entities ($A$ and $B$), both of them have a secret ($A$ has $S_0$ and $B$ has $S_1$) $A$ generates a random ...
2
votes
1answer
102 views

Feldman's VSSS: Showing the Correctness of shares that are Consistent

This is something with which I am struggling to get my head around. In Feldman's VSSS, I am aware that the Dealer broadcasts exponentials $a_{1},...,a_{t-1}$ of the secret $K$ and the coefficients ...
8
votes
1answer
302 views

Verifiable, Distributed Secret Santa Assignments

My family was planning a secret santa and I thought about how I might write a little web app to dole out these secret assignments. But the downsides to this approach are obvious: there's no way for ...
1
vote
1answer
861 views

Correctness vs Completeness

What is the conceptual difference between the definition of correctness and completeness in verifiable cryptographic protocols? They justify that if a statement is correct then the verification should ...
3
votes
2answers
263 views

Are formal methods used for cryptographic protocol design?

I decided to learn more about the application of formal methods to cryptographic protocols and found this interesting talk by Cathy Meadows at YouTube. After doing research about how people are using ...